URUTAN PARSIAL PADA SEMIGRUP DAN PADA KELASKELAS DARI SUATU SEMIGRUP Irtrianta Pasangka1, Drs. Y.D Sumanto, M.Si2, Drs. Harjito, M.Kom 3 Jurusan Matematika FSM Universitas Diponegoro Jl. Prof. H. Soedarto, S.H. Tembalang Semarang
[email protected]
ABSTRACK. Non empty set ð with binary operation â is called semigroup if the binary operation on ð is associative. An element a of semigroup ð is called regular if there exist ðĨ â ð such that ð â ðĨ â ð = ð and semigroup ð is called invers if there exist ð â ð such that ð â ð â ð = ð dan ð â ð â ð = ð. Partial order is relation which is satisfy reflexive, antysymetric and transitive. Relation â, â, â dan â is equivalent relation. Let ð be semigroup and â relation for every ðĨ â ð, âðĨ is â class that contain ðĨ. Thus obtain on relations â, â dan â. Relation âĪ is called partially order relation of regular semigroup ð if for any ðĨ, ðĶ â ð, ðĨ âĪ ðĶ if and only if âðĨ âĪ âðĶ and ðĨ = ððĶ for some ð â ðļ(âðĨ ). Relation âĪ is called partially order relation of regular semigroup ð if for any ðĨ, ðĶ â ð, ðĨ âĪ ðĶ if and only if ðĨ = ððĶ for some ð â ðļ(ð). Keywords: Semigroup, partial order.
I. PENDAHULUAN Salah satu cabang matematika yang mempelajari struktur, hubungan dan kuantitas adalah aljabar, atau ilmu yang mempelajari mengenai aturan-aturan operasi dan relasi dari himpunan, serta kemungkinan bentukan dan konsep yang muncul dari aturan-aturan tersebut. Untuk mempelajari hal-hal ini dalam aljabar digunakan simbol (biasanya berupa huruf) untuk merepresentasikan bilangan secara umum sebagai sarana penyederhanaan dan alat bantu memecahkan masalah.
Himpunan adalah dasar dari semua struktur aljabar. Himpunan merupakan sekumpulan objek yang didefinisikan secara jelas. Maksud didefinisikan secara jelas adalah objek tersebut dapat ditentukan secara tepat apakah objek itu termasuk dalam anggota himpunan tersebut atau bukan. Hubungan antara dua himpunan disebut relasi. Salah satu topik pengembangan dari jenis relasi adalah relasi ekuivalensi dan urutan parsial. Relasi ekuivalensi merupakan realasi yang memenuhi sifat refleksif, simetri dan transitif sedangkan relasi urutan parsial adalah relasi yang memenuhi sifat refleksif, anti-simetri dan transitif. Karena semigrup juga merupakan himpunan maka relasi ekuivalensi juga dikenakan pada semigrup. Penelitian tentang relasi berkembang menyesuaikan sifat â sifat salah satu contohnya yang terdapat pada relasi urutan parsial diantaranya urutan parsial pada semigrup yang telah ditulis oleh P.G. Romeo and M.S.Jisha pada tahun 2014. Berdasarkan latar belakang tersebut, dalam tugas akhir ini dibahas tentang urutan parsial pada semigrup dan pada kelas â kelas dari suatu semigrup beserta contoh â contohnya..
II.
HASIL DAN PEMBAHASAN
Urutan parsial merupakan relasi yang memenuhi sifat refleksif, anti simetris dan tansitif. Sebelumnya akan diberikan beberapa notasi dan definisi yang diperlukan dalam pembahasan selanjutnya :
Definisi 2.1[1] Diberikan semigrup ð dan ð belum tentu memiliki elemen identitas, yaitu 1 sehingga ð 1 menotasikan semigrup yang didapat dari ð dengan menambahkan elemen identitas jika diperlukan yaitu : ð1 = {
ð, ðððð ð ðððððððð ðððððĄððĄðð ðâ{1}, ðððð ð ðĄðððð ðððððððð ðððððĄððĄðð
Definisi 2.2[1] Misalkan ð adalah semigrup dan ðž â ð, maka ðž disebut ideal jika ðžS â ðž dan Sðž â ðž.
Berikut diberikan definisi ideal kiri terkecil, ideal kanan terkecil dan ideal terkecil Definisi 2.3[1] Diberikan semigrup ð dan himpunan tak kosong ðī â ð , ðī disebut ideal kiri terkecil asalkan ððī adalah ideal kiri dari ð dan ððī â ðž, dimana ðž adalah ideal kiri lain dari ð yang memuat ðī dan ðī disebut ideal kanan terkecil asalkan ðīð adalah ideal kanan dari ð dan ðīð â ðž , dimana ðž adalah ideal kanan lain dari ð yang memuat ðī. Himpunan ðī disebut ideal jika ððī â ðž dan ððī â ðž, dimana ðž adalah ideal lain dari ð yang memuat ðī.
Proposisi 2.4[1] Diberikan semigrup ð dan ðī â ð, maka : (1) ð 1 ðī merupakan ideal kiri terkecil yang memuat ðī. (2) ðīð 1 merupakan ideal kanan terkecil yang memuat ðī.
(3) ð 1 ðīð 1 merupakan ideal terkecil yang memuat ðī.
Definisi 2.5[1] Misalkan ð semigrup dan ð â ð, (1) ð 1 ð disebut ideal kiri utama yang dibangun oleh ð. (2) ðð 1 disebut ideal kanan utama yang dibangun oleh ð. (3) ð 1 ðð 1 disebut ideal utama yang dibangun oleh ð.
Selanjutnya didefinisikan relasi ekuivalen pada semigrup menggunakan ideal utama ini Definisi 2.6[2] Misalkan ð, ð adalah elemen pada semigrup S, didefinisikan a. Relasi â dengan ðâð jika dan hanya jika ð 1 ð = ð 1 ð. b. Relasi â dengan ðâð jika dan hanya jika ðð 1 = ðð 1 . c. Relasi ðĨ dengan ððĨð jika dan hanya jika ð 1 ðð 1 = ð 1 ðð 1 . d. Relasi â dengan ðâð jika dan hanya jika ðâð dan ðâð, yaitu ðð 1 = ðð 1 dan ð 1 ð = ð 1 ð.
Berikut diberikan keterkaitan antara urutan parsial dengan kelas â kelas pada semigrup Proposisi 2.7[2] Dalam semigrup ð didefinisikan relasi âĪ , relasi âðĨ âĪ âðĶ jika dan hanya jika ð 1 ðĨ â ð 1 ðĶ dan âðĨ âĪ âðĶ jika dan hanya jika ðĨð 1 â ðĶð 1 berturut â turut
merupakan relasi urutan parsial pada ð/â dan ð/â dan âðĨ âĪ âðĶ jika dan hanya jika âðĨ âĪ âðĶ dan âðĨ âĪ âðĶ adalah relasi urutan parsial pada ð/â. Bukti : a.
Diambil sebarang âðĨ , âðĶ âð§ â ð/â. Pertama akan dibuktikan memenuhi sifat refleksif. Karena bahwa ð 1 ðĨ = ð 1 ðĨ maka ð 1 ðĨ â ð 1 ðĨ untuk setiap ðĨ â ð . Jadi âðĨ âĪ âðĨ dengan kata lain âĪ memenuhi sifat refleksif. Selanjutnya jika âðĨ âĪ âðĶ dan âðĶ âĪ âðĨ âđ ð 1 ðĨ â ð 1 ðĶ dan ð 1 ðĶ â ð 1 ðĨ âđ ð1ðĨ = ð1ðĶ âđ ðĨâðĶ âđ âðĨ = âðĶ , dengan kata lain âĪ memenuhi sifat anti-simetri. Berikutnya jika âðĨ âĪ âðĶ dan âðĶ âĪ âð§ âđ ð 1 ðĨ â ð 1 ðĶ dan ð 1 ðĶ â ð 1 ð§ âđ ð1ðĨ â ð1ðĶ â ð1ð§ âđ ð1ðĨ â ð1ð§ âđ âðĨ âĪ âð§ , dengan kata lain âĪ memenuhi sifat transitif.
b.
Diambil sebarang âðĨ , âðĶ âð§ â ð/â . Pertama akan dibuktikan memenuhi sifat refleksif. Karena ðĨð 1 = ðĨð 1 maka ðĨð 1 â ðĨð 1 untuk setiap ðĨ â ð. Jadi âðĨ âĪ âðĨ dengan kata lain âĪ memenuhi sifat refleksif. Selanjutnya jika âðĨ âĪ âðĶ dan âðĶ âĪ âðĨ âđ ðĨð 1 â ðĶð 1 dan ðĶð 1 â ðĨð 1 âđ ðĨð 1 = ðĶð 1 âđ ðĨâðĶ
âđ âðĨ = âðĶ , dengan kata lain âĪ memenuhi sifat anti-simetri. Berikutnya jika âðĨ âĪ âðĶ dan âðĶ âĪ âð§ âđ ðĨð 1 â ðĶð 1 dan yð 1 â ð§ð 1 âđ ðĨð 1 â ðĶð 1 â ð§ð 1 âđ ðĨð 1 â ð§ð 1 âđ âðĨ âĪ âð§ , dengan kata lain âĪ memenuhi sifat transitif. c.
Diambil sebarang âðĨ , âðĶ âð§ â ð/â . Pertama akan dibuktikan memenuhi sifat refleksif. Diperhatikan bahwa dari bukti diatas diperoleh âðĨ âĪ âðĨ dan âðĨ âĪ âðĨ maka âðĨ âĪ âðĨ dengan kata lain âĪ memenuhi sifat refleksif. Selanjutnya jika âðĨ âĪ âðĶ dan âðĶ âĪ âðĨ âđ âðĨ âĪ âðĶ , âðĨ âĪ âðĶ dan âðĶ âĪ âðĨ , âðĶ âĪ âðĨ âđ âðĨ = âðĶ dan âðĨ = âðĶ âđ ðĨ â âðĶ dan ðĨ â âðĶ (atau ðĶ â âðĨ dan y â âðĨ ) âđ ðĨ â âðĶ (atau ðĶ â âðĨ ) âđ âðĨ = âðĶ , dengan kata lain âĪ memenuhi sifat anti-simetri. Berikutnya jika âðĨ âĪ âðĶ dan âðĶ âĪ âð§ âđ âðĨ âĪ âðĶ , âðĨ âĪ âðĶ dan âðĶ âĪ âð§ , âðĶ âĪ âð§ âđ âðĨ = âð§ dan âðĨ = âð§ âđ âðĨ âĪ âð§ ,
dengan kata lain âĪ memenuhi sifat transitif.
Berikut diberikan keterkaitan antara urutan parsial dengan semigrup invers Lemma 2.8[2] Diberikan ð semigrup invers. Untuk ðĨ, ðĶ â ð didefinisikan ðĨ âĪ ðĶ jika dan hanya jika ðĨ = ððĶ untuk ð â ðļ(ð), maka relasi âĪ adalah suatu urutan parsial pada ð.
Bukti : Diberikan sebarang ðĨ â ð, berdasarkan definisi semigrup invers maka terdapat ð â ð sehingga ðĨ = ðĨððĨ , ð = ððĨð . Diketahui bahwa untuk setiap ðĨ â ð, berdasarkan teorema 2.3.5 terdapat ð = ðĨð â ðļ(ð) sehingga ðĨ = ððĨ sehingga relasi âĪ refleksif. Selanjutnya jika ðĨ âĪ ðĶ dan ðĶ âĪ ðĨ maka ðĨ = ððĶ dan ðĶ = ð ðĨ , untuk suatu ð, ð â ðļ(ð), maka ððĨ = ð(ððĶ) = (ðð)ðĶ = ððĶ = ðĨ dan ðĨ = ððĶ = ðð ðĨ = ð ððĨ = ð ðĨ = ðĶ ; sehingga relasi âĪ anti-simetri. Berikutnya jika ðĨ âĪ ðĶ dan ðĶ âĪ ð§ maka terdapat ðĨ = ððĶ dan ðĶ = ð ð§ untuk suatu ð, ð â ðļ(ð) maka ðĨ = ððĶ = ðð ð§ = (ðð )ð§ . Perhatikan bahwa ðð â
ðð = ðð ð ð = ðð ð = ððð = ðð maka ðð â ðļ(ð) jadi ðĨ âĪ ð§; sehingga relasi âĪ transitif.
Berikut diberikan keterkaitan antara urutan parsial dengan semigrup regular Proposisi 2.9[2] Diberikan ð semigrup reguler. Untuk ðĨ, ðĶ â ð didefinisikan ðĨ âĪ ðĶ jika dan hanya jika âðĨ âĪ âðĶ dan ðĨ = ððĶ untuk suatu ð â ðļ(âðĨ ).
Maka relasi âĪ adalah suatu urutan parsial pada ð. Bukti : Diambil sebarang ðĨ, ðĶ, ð§ â ð. Karena ð semigrup reguler maka terdapat ð, ð, ð â ð sedemikian sehingga ðĨ = ðĨððĨ , ðĶ = ðĶððĶ , dan ð§ = ð§ðð§ . Diperhatikan bahwa âðĨ âĪ âðĨ . Berdasarkan Lemma 3.1.12 ðĨð â ðļ(âðĨ ) sehingga ðĨ = ðĨððĨ untuk ð = ðĨð â ðļ(âðĨ ) , ðĨ = ððĨ . Jadi ðĨ âĪ ðĨ dengan kata lain âĪ memenuhi sifat refleksif. Selanjutnya jika ðĨ âĪ ðĶ dan ðĶ âĪ ðĨ sehingga âðĨ âĪ âðĶ dan âðĶ âĪ âðĨ dan ðĨ = ððĶ, ðĶ = ððĨ untuk suatu ð â ðļ(âðĨ ) dan ð â ðļ(âðĶ ) .Diperhatikan bahwa ð â ðļ(âðĨ ) maka ð â âðĨ , ðâðĨ maka ðð 1 = ðĨð 1 . Untuk ð â ðļ(âðĶ ) maka ð â âðĶ , ðâðĶ maka ðð 1 = ðĶð 1 . Selanjutnya untuk âðĨ âĪ âðĶ dan âðĶ âĪ âðĨ â ðĨð 1 â ðĶð 1 dan ðĶð 1 â ðĨð 1 â ðð 1 = ðĨð 1 = ðĶð 1 = ðð 1 â ðð 1 = ðð 1 â ð â ð1 â ð = ðð â ðð 1 â ð â ðļ(ðð 1 ) â ð = ðð untuk suatu
ð â ð1
â ðð = ððð = ðð = ð Jadi ðĶ = ððĨ = ðððĶ = ððĶ = ðĨ, dengan kata lain âĪ memenuhi sifat anti-simetri. Berikutnya jika ðĨ âĪ ðĶ dan ðĶ âĪ ðĨ maka âðĨ âĪ âðĶ dan âðĶ âĪ âðĨ terdapat ðĨ = ððĶ dan ðĶ = ðð§ untuk suatu ð â ðļ(âðĨ ) dan ð â ðļ(âðĶ ), selanjutnya âðĨ âĪ âðĶ âđ ðĨð 1 â ðĶð 1
âđ ðð 1 = ðĨð 1 â ðĶð 1 = ðð 1 âđ ðð 1 â ðð 1 âđ ð â ð1 âđ ð = ðð â ðð 1 âđ ð â ðļ(ðð 1 ) âđ ð = ðð untuk suatu ð â ð 1 âđ ðð = ððð = ðð = ð âđ ðð = ððð = ðð = ð âđ ðĨð 1 = ðð 1 = ððð 1 âđ ðð â âðĨ Diperhatikan bahwa ð(ðð)ð = ððð = ðð, jadi ðð â ðļ(âðĨ ). Dari preposisi 3.1.10 karena âðĨ âĪ âðĶ dan âðĶ âĪ âð§ maka âðĨ âĪ âð§ . Karena âðĨ âĪ âð§ dan terdapat ðð â ðļ(âðĨ ) sehingga ðĨ = ððĶ = ððð§ diperoleh ðĨ âĪ ð§ dengan kata lain âĪ memenuhi sifat transitif.
III.
KESIMPULAN
Dari pembahasan dalam bab sebelumnya, diperoleh kesimpulan bahwa semigrup merupakan himpunan tak kosong yang didefinisikan dengan operasi biner â yang memenuhi sifat asosiatif. Urutan parsial merupakan relasi yang memenuhi sifat refleksif, anti symetri, dan transitif. Relasi â , â , ðĨ , dan â merupakan relasi ekuivalensi dan jika pada semigrup ð dikenakan relasi â, maka ð terpecah dalam kelas â kelas ekuivalensi, untuk ðĨ â ð, âðĨ menyatakan kelas â yang memuat ðĨ, yaitu âðĨ = {ðĶ â ð|ðĶâðĨ}. Himpunan semua kelas â kelas dari â ditulis dengan ð/â. Hal ini juga berlaku pada relasi â, ðĨ, dan â.
Dalam suatu semigrup ð relasi âðĨ âĪ âðĶ merupakan urutan parsial pada ð/â, relasi âðĨ âĪ âðĶ merupakan urutan parsial pada ð/â, dan relasi âðĨ âĪ âðĶ merupakan urutan parsial pada ð/â . Jika ð semigrup reguler, ðĨ âĪ ðĶ jika dan hanya jika âðĨ âĪ âðĶ dan ðĨ = ððĶ untuk suatu ð â ðļ(âðĨ ) maka relasi âĪ adalah relasi urutan parsial pada semigrup reguler ð dan relasi âĪ merupakan relasi urutan parsial pada semigrup invers jika ðĨ âĪ ðĶ dan ðĨ = ððĶ untuk suatu ð â ðļ(ð).
IV. [1]
DAFTAR PUSTAKA
Howie, J.M. 1976. An Introduction To Semigroup Theory. Akademic Press. London.
[2]
P.G. Romeo and M.S.Jisha. 2014. Natural Partial Order on Some Class of Semigroups. International Journal of Algebra, vol. 8: 479-484.