Prosiding Semirata FMIPA Universitas Lampung, 2013
SIFAT-SIFAT SEMIGRUP BEBAS DAN MONOID BEBAS DALAM BENTUK HIMPUNAN WORD Rolan Pane1, Sri Gemawati1, Novia Yumitha sarie2Firdaus1 Department of mathematics FMIPA Universitas Riau E-mail:
[email protected] Abstract. We discussthe characteristics of free semigroup and free monoid related
to word set. The discussionbegin withsome homomorphismtheorems and a criterion for freeness of semigroup and monoid. All characteristics of free semigroup and free monoid are expressed on theorems. Keywords:Homomorphism Theorem, A Criterion For Freeness, Word Set.
PENDAHULUAN Teori dasar dari himpunan, pemetaan, operasi biner dan relasi biner sangat diperlukan untuk mempelajari struktur aljabar.Suatu struktur aljabar (structure of algebra)adalah himpunan tak kosong dimana terdapat sedikitnya satu relasi ekivalen dan satu atau lebih operasi biner dapat didefinisikan di dalamnya. Salah satu kasus struktur aljabar adalahsemigrup. Semigrup adalah suatu struktur aljabar dengan operasi biner yang bersifat asosiatif. Operasi biner pada semigrup S sering dinotasikan dengan , yang memetakan tiap pasangan berurutan ( x, y) S S ke suatu elemen x y S . Suatu semigrup yang mempunyai identitas disebut monoid. Semigrup dan Semigrup Bebas Konsep-konsep yang akan dibahas dalam karya tulis ini merupakan materimateri pendukung yang diambil dari beberapa referensi yaitu [3], [5] dan [6]. Definisi 2.1. (Semigrup) Misalkan S suatu himpunan dan : S S S adalah operasi biner yang memetakan tiap pasangan ( x, y) S S ke suatu elemen x y S . Himpunan S adalah suatu semigrup dengan operasi didefinisikan di dalamnya, biasanya dinotasikan dengan ( S ,) atau dengan S saja, jika
operasi memenuhi sifat asosiatif, yakni untuk setiap x, y, z S berlaku : x ( y z ) ( x y) z . Definisi 2.2. (Subsemigrup)Untuk suatu subhimpunan X S dengan X Ø didefinisikan X S x1 x 2 ...x n ... | n 1, xi X , Maka X S adalah subsemigrup dari S , dan dikatakan sebagai subsemigrup yang dibangun oleh X . Definisi 2.3. (Semigrup Bebas) Misalkan diketahui S sebarang semigrup. Himpunan bagian A S membangun S secara bebas jika terdapat pemetaan 0 : A P , dengan P sembarang semigrup, yang dapat diperluas menjadi suatu homomorfisma : S P sehingga | A 0 . Maka S dikatakan suatu semigrup bebas dan pemetaan dikatakan sebagai perluasan homomorfisma dari pemetaan 0 . Definisi 2.4. (HimpunanWord) Misalkan A adalah suatu himpunan alfabet yang anggotanya disebut letter/huruf. Sembarang barisan hingga dari letter disebut word dari A . Himpunan semua word dari A , sedikitnya satu letter, dinotasikan dengan A .Tiap elemen dari A mempunyai panjang sedikitnya satu letter dan sebanyakbanyaknya adalah tak hingga. Semirata 2013 FMIPA Unila |449
Rolan Pane Dkk: Sifat-Sifat Semigrup Bebas Dan Monoid Bebas Dalam Bentuk Himpunan Word
Contoh Misalkan diketahui himpunan alfabet A {a, b} , maka himpunan word dari A adalah : A {a, b, ab, ba, aa, bb, aaa, aab,...} . Dalam [5], teorema homomorfisma, teorema kernel, teorema monomorfisma dan teorema fundamental homomorfisma diberikan sebagai berikut. Misalkan ( S ,) dan ( P,) sembarang semigrup. Untuk suatu homomorfisma : S P , didefinisikan relasi kernelnya sebagai berikut: dengan ker( ) {( x, y) | ( x) ( y)} x, y S . Teorema 2.1. Misalkan ( S ,) dan sembarang semigrup dan ( P,) terdapatsuatu homomorfisma : S P . Terdapat suatu monomorfisma tunggal : S ker( ) P sehingga diagram berikut berlaku :
Gambar 1. Diagram komutatif Bukti. Misalkan R ker( ) dan : S S R adalah suatu homomorfisma. Definisikan : S R P dengan ( xR) ( x) untuk setiap x S . terdefinisi dengan baik, yakni untuk setiap x, y S , pilih xR yR dengan ( x, y) ker( ) . Maka, ( x, y) ker( ) ( x) ( y) ( xR) ( yR) Tiap (xR) mempunyai nilai tertentu P , yang secara independen di merepresentasikan kelas kongruensi xR . Kemudian, ( xR yR) (( x y) R) ( x y) ( x) ( y ) ( xR) ( yR) . 450| Semirata 2013 FMIPA Unila
Maka, merupakan suatu homomorfisma. Selanjutnya, untuk setiap ( x, y) ker( ) berlaku : ( x) ( y) ( xR) ( yR) , Tiap pemetaan (xR) memasangkan secara tunggal (x) dengan x S . Maka (xR) merupakan pemetaan injektif. Misalkan terdapat :S RP sembarang monomorfisma yang lainnya, maka , dan ( x) ( xR) untuk setiap x S . Namun ini berarti bahwa Jadi, pemetaannya adalah . tunggal. Teorema 2.2.(Teorema Fundamental Homomorfisma) Misalkan ( S ,) dan sembarang semigrup dan ( P,) terdapatsuatu homomorfisma : S P dengan ker( ) kongruen di S . Maka S ker( ) isomorfik dengan P . Bukti. Dari Teorema 2.5, terdapat suatu monomorfisma tunggal Akan ditunjukkan : S ker( ) P . bahwa pemetaan juga surjektif sehingga merupakan suatu isomorfisma. Dari Teorema 2.4, pemetaan merupakan suatu :S S R epimorfisma. Ambil sembarang y P dengan ( x) y . Diagram komutatif pada Gambar 1 berlaku, maka : ( )( x) ( x) ( ( x)) y (u) y Untuk setiap y P terdapat u S R sedemikian hingga (u) y . Jadi, pemetaan surjektif. Karena merupakan suatu monomorfisma dan juga bersifat surjektif, maka merupakan suatu isomorfisma. Semigrup Word Bebas Pada himpunan A , didefinisikan operasi biner sebagai suatu rangkaian berurutan (catenation) dari elemen-
Prosiding Semirata FMIPA Universitas Lampung, 2013
elemen A . Operasi rangkaian pada A diilustrasikan sebagai berikut : Untuk setiap a i , b j A , terdapat elemen w1 , w2 A , dengan w1 a1a2 ...am dan w2 b1b2 ...bn , m, n 1 , yang memenuhi: w1 w2 (a1a2 ...am ) (b1b2 ...bn ) a1a2 ...amb1b2 ...bn w1w2 .
Karena operasi biner pada A merupakan suatu rangkaian berurutan (catenation) dari elemen-elemennya, maka sifat asosiatif berlaku, yakni untuk setiap dengan w1 , w2 , w3 A , w3 c1c2 ...c p
dan
ck A ,
k 1,
diperoleh : w1 (w2 w3 ) a1a2 ...am (b1b2 ...bn c1c2 ...c p ) a1a2 ...am (b1b2 ...bn c1c2 ...c p ) a1a2 ...am b1b2 ...bn c1c2 ...c p ) (a1a2 ...am b1b2 ...bn ) c1c2 ...c p (a1a2 ...am b1b2 ...bn ) c1c2 ...c p
(w1 w2 ) w3 .
Maka, A merupakan suatu semigrup. Misalkan terdapat sembarang semigrup dan sembarang pemetaan ( S ,)
0 : A S . Karena A membangun A , maka dapat didefinisikan suatu homomorfisma : A S dengan : (w1 ) (a1a2 ...am ) 0 (a1 ) 0 (a 2 ) ... 0 (a m ) Karena restriksi | A 0 terpenuhi maka dari Definisi 2.12, himpunan A merupakan suatu semigrup bebas. Teorema 3.1. Misalkan A semigrup bebas pada himpunan alfabet A , dengan R0 sembarang relasi pada A , R kongruen di A yang dibangun oleh dan R0 : A A R suatu homomorfisma. Misalkan pula ( S ,) sembarang semigrup, dan : A S suatu homomorfisma dengan (u) (v) untuk setiap (u, v) R0 . Maka terdapat suatu homomorfisma
berlaku : A R S sehingga . Bukti.Dari hipotesis teorema, pemetaan : A S adalah suatu homomorfisma dengan (u) (v) untuk setiap Maka (u, v) R0 . Karena R adalah R0 1 . kongruen terkecil di A yang memuat R0 , dan 1 adalah kongruen, maka R 1 , sehingga untuk setiap (w1 , w2 ) R diperoleh (w1 ) (w2 ) . Kemudian definisikan pemetaan : A R S dengan ( (w)) (w) , untuk setiap w A . terdefinisi dengan baik, yakni untuk setiap w1 , w2 A dengan pilih (w1 , w2 ) R , (w1 ) (w2 ) , maka ( (w1 )) (w1 ) (w2 ) ( (w2 )) Domain adalah semua elemen di A R karena setiap elemen di A R mempunyai bentuk wR dengan w A . Maka terpenuhi. Kemudian, akan ditunjukkan bahwa suatu homomorfisma. Untuk sembarang elemen w1 , w2 A , diperoleh ( (w1 )( (w2 )) ((w1 w2 ) R) (w1 w2 ) (w1 ) (w 2 ) ( (w1 )) ( (w2 )) Maka adalah suatu homomorfisma. Teorema 3.2. Untuk setiap semigrup ( S ,) terdapat suatu himpunan alfabet A dan suatu epimorfisma : A S . BuktiMisalkan sembarang X himpunan yang membangun S , pilih X S dan A suatu himpunan alfabet dengan A X , dan misalkan pemetaan
0 : A X adalah bijektif.
suatu
pemetaan
Semirata 2013 FMIPA Unila |451
Rolan Pane Dkk: Sifat-Sifat Semigrup Bebas Dan Monoid Bebas Dalam Bentuk Himpunan Word
Dari Definisi 2.12, 0 mempunyai suatu perluasan homomorfisma :A S. Karena ( X )S (X S ) (S ) , maka pemetaan surjektif. adalah suatu homomorfisma surjektif, sehingga merupakan suatu epimorfisma. Teorema 3.3.Setiap semigrup isomorfik dengan suatu semigrup word kuosien.Yakni, untuk suatu epimorfisma : A S maka S isomorfik dengan A ker( ) . Bukti. Dari Teorema 2.5, dalam bentuk himpunan word dapat dibuat diagram komutatifnya sebagai berikut :
Gambar 2. Diagram komutatif Terdapat suatu monomorfisma tunggal : A ker( ) S . Dari Teorema 2.4, pemetaan : A A R merupakan suatu epimorfisma dan dari Teorema 3.2, pemetaan : A S juga merupakan suatu epimorfisma. Ambil sembarang Diagram y S dengan ( x) y . komutatif pada Gambar 2 berlaku, maka : ( )( x) ( x) ( ( x)) y (u) y Untuk setiap y S terdapat u S R sedemikian hingga (u) y . Maka pemetaan surjektif. Karena merupakan suatu monomorfisma dan juga bersifat surjektif, maka merupakan suatu isomorfisma. Monoid Word Bebas Dari Definisi 2.7, Monoid adalahs emigrup yang mempunyai elemen 452| Semirata 2013 FMIPA Unila
identitas. Secara umum dalam [4] monoid S ' didefinisikan sebagai berikut : jika S suatu monoid, S S' jika S bukan monoid, S {e} dengan e adalah elemen identitasnya. Definisi 4.1 Suatu monoid S ' dikatakan monoid bebas jika dibangun secara bebas oleh suatu subhimpunan X dengan e S ' X . Jika X {e S ' } adalah himpunan generator untuk S ' , dan terdapat pemetaan 0 : X P , dengan P sembarang monoid, yang dapat diperluas ke suatu homomorfisma : S ' P sehingga | X 0 dan Maka S ' bebas dan (eS ' ) eP . pemetaan dikatakan sebagai perluasan homomorfisma dari pemetaan 0 . Himpunan barisan hingga dari letterletter A dan memuat identitasnya dinotasikan dengan A . Sama halnya dengan himpunan A , pada himpunan A operasi biner didefinisikan sebagai suatu rangkaian berurutan (catenation) dari elemen-elemennya. Elemen identitasnya dinotasikan dengan e . A
Sehingga, A merupakan suatu monoid. e A , maka A {e } Jika A
A
merupakan himpunan generator untuk A . Misalkan terdapat sembarang monoid S ' dan sembarang pemetaan 0 : A S ' . Untuk sembarang w1 a1 a 2 ...a m A dengan a i A , dapat didefinisikan suatu homomorfisma : A S ' dengan (w1 ) (a1a2 ...am ) 0 (a1 ) 0 (a 2 ) ... 0 (a m ) Restriksi
(e A ) eS ' ,
| A 0 terpenuhi
maka
dan
himpunan
A merupakan suatu monoid bebas. Dalam [2] dan [4] teorema-teorema yang berkaitan dengan monoid bebas diberikan sebagai berikut.
Prosiding Semirata FMIPA Universitas Lampung, 2013
Teorema 4.1 Jika S semigrup bebas, maka S ' adalah monoid bebas. Bukti. Dengan menggunakan Definisi 2.12 dan Definisi 4.1, maka pembuktian Teorema 4.1 pun terpenuhi. Teorema 4.2 Suatu monoid S ' adalah monoid bebas jika dan hanya jika S '\{eS ' } adalah suatu semigrup bebas. Bukti. () Misalkan S ' suatu monoid bebas yang dibangun secara bebas oleh X dengan eS ' X . Maka S '\{eS ' } adalah subsemigrup dari dimana S' , dengan e S ' x1 x 2 ...x n ... xi X . Misalkan pula terdapat pemetaan yang dapat diperluas 0 : X A menjadi suatu homomorfisma sedemikian hingga : S '\{eS ' } A
Dari Definisi 2.12, |X 0 . S '\{eS ' } adalah suatu semigrup bebas. ()
Selanjutnya, misalkan S '\{eS ' } adalah suatu semigrup bebas. Terdapat sembarang semigrup A dan pemetaan dapat diperluas 0 : X A yang menjadi suatu homomorfisma hingga : S '\{eS ' } A sedemikian
| X 0 . Kemudian, elemen identitas ditulis sebagai {e S ' } dapat
e S ' x1 x 2 ...x n ... dengan xi X , dimana (e S ' ) ( x1 x 2 ...x n ...) ( x1 ) ( x 2 ) ... ( x n ) ... yang juga memenuhi sifat homomorfisma. Oleh karena itu, pemetaan 0 : X A ,
dimana A adalah suatu monoid, dapat diperluas menjadi suatu homomorfisma : S' A sedemikian hingga | X 0 dengan (e S ' ) e . Maka S ' merupakan A
suatu monoid bebas. Teorema 4.3 Suatu monoid S ' bebas jika dan hanya jika S ' isomorfis ke monoid word bebas A untuk suatu alfabet A .
Bukti. Dengan menggunakan Definisi 4.1 dan pembuktian Teorema 3.4, maka pembuktian Teorema 4.3 pun terpenuhi. Kesimpulan 1. Suatu semigrup dapat diidentifikasi apakah semigrup tersebut dibangun secara bebas atau tidak berdasarkan sifat-sifat bebasnya, 2. Hubungan antara suatu semigrup word bebas dengan sembarang semigrup dapat diidentifikasi berdasarkan jenis pemetaan yang berlaku di antara kedua semigrup tersebut, 3. Dari suatu semigrup word bebas dapat dibangun suatu monoid word bebas dengan menambahkan elemen identitas pada semigrup word bebas tersebut. Hal ini juga berlaku untuk semigrup bebas biasa. DAFTAR PUSTAKA Clifford, A.H & G. B. Preston. 1961. The Algebraic Theory of Semigroups Vol I. American Mathematical Society, USA. Clifford, A.H dan G. B. Preston. 1967. The Algebraic Theory of Semigroups Vol II. American Mathematical Society, USA. Gilbert, Jimmie &Linda Gilbert. 1992. Element of Modern Algebra Third Edition. PWS-KENT, USA. Harju, Tero. 1996. Lecture Notes on Semigroups. University of Turku, Finland. Judson, Thomas W. 1997. Abstract Algebra Theory and Applications. Stephen F. Austin State University. Setiawan, Adi. 2011. Aljabar Abstrak (Teori Grupdan Teori Ring). FMIPA Universitas Kristen Satya Wacana, Salatiga.
Semirata 2013 FMIPA Unila |453
