BAB 2 KONSEP DASAR
Pada bab 2 ini, penulis akan memperkenalkan himpunan, fungsi dan sejumlah konsep awal yang terkait dengan semigrup, dimana sebagian besar akan sangat diperlukan hingga bagian akhir dari buku. Bab 2 ini juga ditulis dengan tujuan memberikan gambaran luas dan menyeluruh dari inverse semigroup yang merupakan suatu kelas dari semigrup. Hal ini menjelaskan mengapa beberapa topik yang diperdalam pada bab selanjutnya, diperkenalkan pada bab ini.
2.1 HIMPUNAN DAN FUNGSI Himpunan didefinisikan sebagai suatu koleksi M dari sejumlah obyek m yang terkait melalui suatu persepsi atau pemikiran tertentu, keanggotaan obyek terhadap koleksi dilambangkan dengan simbol “∈”, dan penulisan m ∈ M memiliki arti m adalah anggota atau elemen dari M. Himpunan dapat dideskripsikan melalui dua cara, yang pertama yaitu melalui pendefinisian langsung, sebagai contoh : - A adalah himpunan empat bilangan bulat positif pertama. - B adalah himpunan warna pada bendera negara indonesia. Cara kedua adalah dengan memaparkan anggota-anggota dari himpunan tersebut, kemudian ditutup dengan tanda kurung, sebagai contoh : A = {1,2,3,4}, dan B = {merah, putih}. Biasanya setiap elemen dari himpunan dituliskan secara unik, kecuali jika penulisan elemen secara berulang memang diperlukan. Jika jumlah anggota pada himpunan tersebut banyak sehingga menyulitkan untuk ditulis kesemua anggotanya, maka sebagai contoh himpunan 1000 bilangan bulat positif pertama, dapat dituliskan dengan cara {1,2,3, … , 1000} dimana “…” menunujukan bahwa
3
daftar tersebut berlanjut dengan cara yang sudah sewajarnya. Contoh lain dalam penulisan himpunan, yaitu pada himpunan himpunan bilangan genap positif kurang dari 20, X = {2n : n ∈ Z, dan 0 ≤ n ≤ 9}, tanda “ : “ memiliki arti “dengan” atau “dimana”, dan deskripsi tersebut dapat diinterprestasi sebagai berikut “X adalah himpunan seluruh bilangan dalam bentuk 2n, dimana n adalah bilangan bulat dan 0 ≤ n ≤ 9”. Jika setiap anggota dari himpunan A juga merupakan anggota dari himpunan B, maka A dikatakan sebagai subhimpunan dari B, dan dilambangkan dengan A ⊆ B. Jika A ⊆ B tetapi A ≠ B maka A disebut sebagai himpunan bagian dari B, dilambangkan dengan A ⊂ B. Perlu diketahui bahwa makna ⊆ dan ⊂ digunakan
secara
berbeda
untuk
berbagai buku.
Beberapa
pengarang
menggunakan A ⊂ B untuk penulisan A ⊆ B dan sebagian menggunakan A ⊊ B
sebagai pengganti dari A ⊂ B.
Misalkan A dan B adalah suatu himpunan, Fungsi f adalah pemetaan setiap anggota himpunan A kepada anggota di B. Himpunan A disebut sebagai domain dari f, himpunan B disebut sebagai kodomain dari f. Untuk mendefinisikan fungsi kita dapat menggunakan notasi f : A → B yaitu fungsi f yang memetakan setiap anggota himpunan A kepada anggota di B, dan melalui
penulisan x ↦ f(x) maka yang dimaksud adalah akibat dari f pada x ∈ A. Kita membedakan penggunaan panah → dan ↦.
Misalkan f : A → B adalah suatu fungsi, maka : (1) f disebut fungsi injektif atau satu-satu jika x ≠ y → f(x) ≠ f(y). (2) f disebut fungsi surjektif atau pada atau kepada jika b∈B, ∃a∈A→ f(a) = b. (3) f disebut fungsi bijektif jika f satu-satu dan sekaligus pada. 2.2 GRUPOID Operasi biner pada himpunan S adalah pemetaan dari S × S pada S , dimana S × S adalah himpunan seluruh pasangan terurut dari anggota - anggota di S. Apabila pemetaan biner tersebut dilambangkan dengan dot “ · ”, hasil peta dari elemen (a,b) pada S akan dilambangkan dengan a·b dan notasi · : S × S → S 4
menyatakan operasi biner · pada himpunan S yang memetakan pasangan terurut yaitu (a,b) ∈ S × S, pada a · b ∈ S. Seringkali ketika tidak terdapat bahaya ambiguitas, penulisan dot dapat kita abaikan, yaitu dengan menuliskan ab sebagai pengganti dari bentuk a · b. Contoh umum dari operasi biner adalah penjumlahan dan perkalian pada bilangan dan pada matriks. Grupoid adalah sistem ( S , · ) yang terdiri dari himpunan tak kosong S bersama dengan suatu operasi biner · di S. Contoh dari grupoid adalah (Z, +) yaitu bilangan bulat dengan operasi penjumlahan. Dalam aljabar, yakni cabang dari matematika murni. Struktur aljabar didefinisikan sebagai suatu sistem yang terdiri dari satu atau lebih himpunan yang dilengkapi dengan satu atau lebih operasi yang memenuhi sejumlah aksioma. Pembelajaran mengenai struktur aljabar sendiri merupakan bagian dari aljabar abstrak, yaitu bidang dari (matematika murni) aljabar yang mempelajari mengenai struktur aljabar dan sifat-sifat yang dimiliki olehnya. Grupoid disini merupakan salah satu contoh dari struktur aljabar, yaitu suatu himpunan, dengan operasi yang memenuhi aksioma
tertutup, yakni ∀ a, b ∈ S maka a · b ∈ S , perlu dicermati ketika kita
menyebutkan bahwa operasi yang terkait di suatu struktur aljabar adalah operasi biner, maka aksioma tertutup ini secara otomatis telah dipenuhi oleh struktur aljabar tersebut.
Operasi biner · pada himpunan S dikatakan asosiatif jika ∀ a, b, c ∈ S
berlaku a · (b · c) = (a · b) · c. Semigrup adalah grupoid (S, ·) dimana operasi pada
grupoid tersebut bersifat asosiatif. Oleh karena operasi penjumlahan pada (Z, +) bersifat asosiatif, maka (Z, +) juga merupakan contoh dari semigrup. Untuk setiap a dan b anggota dari semigrup S, a dan b dikatakan komutatif satu sama lain jika ab = ba. Yang menjadi tujuan investigasi dari bab ini bukanlah grupoid, melainkan semigrup. Tetapi di dalam bab lebih lanjut, diperlukan sistem yang lebih luas untuk mengkaji free inverse semigroup serta beberapa konsep yang terkait dengannya, sehingga membuat hal tersebut penting untuk dipelajari. Subhimpunan tak kosong T dari grupoid S disebut subgrupoid dari S jika
∀a,b∈T maka ab∈T. Irisan dari sejumlah subgrupoid dari S adalah subgrupoid
5
dari S atau himpunan kosong. Jika S adalah semigrup, maka subgrupoid dari S juga merupakan semigrup, dan kita menyebutnya sebagai subsemigrup dari S.
Misalkan S adalah grupoid, e ∈ S disebut identitas kiri jika ∀a ∈ S maka
ea = a, dan disebut identitas kanan jika ∀a∈S maka ae = e. Elemen e dari S disebut Identitas dua sisi atau elemen identitas jika e merupakan identitas kiri dan
identitas kanan dari S. Jika S hanya memuat satu identitas kiri e dan satu identitas kanan f, maka e = f, karena jika e identitas kiri maka ef = f dan f identitas kanan menyebabkan ef = e .
Elemen z dari grupoid S disebut nol kiri jika ∀a∈S maka za = z ,dan
disebut nol kanan jika ∀a∈S maka az = z. Elemen z dari S disebut elemen nol jika
z merupakan nol kiri dan nol kanan dari S.
Elemen e dari grupoid S disebut idempotent jika e · e = e. Identitas satu sisi dan elemen-nol adalah idempotent. Misalkan S adalah suatu semigrup, dan misalkan 1 adalah suatu simbol yang tidak merepresentasikan anggota-anggota dari S. Apabila operasi biner pada
S diperluas ke S ∪ 1 dengan mendefinisikan 11 = 1 dan ∀a∈S berlaku 1a = a1 =
a, terlihat langsung bahwa S ∪ 1 adalah semigrup dengan 1 sebagai elemen identitas. Kita menyebut perlakuan yang kita kenakan dari S ke S ∪ 1 tersebut dengan menambahkan elemen identitas pada S. Dengan cara yang serupa kita
juga dapat menambahkan elemen-nol pada S, definisikan,∀a∈S berlaku 00 = 0a = a0 = 0. Jika A dan B adalah sub-himpunan dari grupoid S, maka produk himpunan AB dari A dan B adalah himpunan seluruh elemen ab dari S dengan a∈A dan b∈B. Jika A = {a} maka kita dapat menuliskan aB sebagai pengganti dari AB, dan dengan cara serupa jika B = {b} , AB dapat dituliskan dengan Ab. Jika A ⊂ S, A ≠ ∅ maka yang dimaksud dengan Ideal kiri dari grupoid S adalah himpunan A, dimana SA ⊆ A. Jika AS ⊆ A maka A disebut sebagai ideal kanan dari grupoid S. Jika A adalah ideal kiri dan sekaligus merupakan ideal
6
kanan dari S, maka A kita sebut ideal. Irisan seluruh ideal kiri dari S yang memuat A (termasuk S) juga merupakan ideal kiri dari S, ideal kiri ini memuat A dan termuat di seluruh ideal kiri dari S, kita menyebutnya sebagai Ideal kiri dari S yang dibangun oleh A. Jika S adalah semigrup, maka ideal kiri dari S yang dibangun oleh A adalah A ∪ SA = S1A. Melalui pendefinisian serupa, ideal kanan dari S yang dibangun oleh A adalah A ∪ AS = AS1, dan ideal (dua-sisi) dari S yang dibangun oleh A adalah A ∪ SA ∪ AS ∪ SAS = S1AS1. Jika A hanya terdiri dari satu elemen yaitu a, maka L(a) = S1a, R(a) = S1, dan J(a) = S1aS1 berturut-turut kita sebut sebagai prinsipal-kiri, prinsipal-kanan, dan prinsipal-ideal dari S, yang dibangun oleh a.
2.3 HOMOMORFISMA Misalkan S dan S` adalah grupoids. Pemetaan φ : S → S` disebut
homomorfisma jika ∀a,b∈S φ(ab) = φ(a)φ(b), dengan operasi φ(ab) di S dan
operasi φ(a)φ(b) di S`. homomorfisma juga bisa dipandang sebagai suatu pemetaan yang mengawetkan operasi. Contoh sederhana adalah himpunan bilangan bulat dengan operasi penjumlahan, yaitu grupoid (Z, +), φ(x) = 2x adalah homomorfisma dikarenakan ∀a,b ∈ Z, φ(a + b) = 2(a + b) = 2a + 2b = φ(a) + φ(b). Range φS dari φ, yaitu himpunan setiap elemen φa dari S` dengan a ∈ S, adalah subgrupoid dari S`. Kemudian kita katakan S homomorf dengan φS, dan φS adalah image homomorfisma dari S; kita tulis dengan S ~ φS. Homomorfisma satu – satu dari S pada S` disebut juga isomorfisma dari S
pada S`. Grupoid S dan φS dikatakan isomorf dan kita tulis dengan S ≌ φS.
Homomorfisma S pada S disebut endomorfisma, dan isomorfosma S pada S disebut automorfisma.
7
2.4 RELASI, RELASI EKIVALEN, KONGRUEN Misalkan S dan T adalah semigrup, maka produk langsung dari S dan T adalah himpunan S × T dengan produk didefinisikan sebagai berikut : ∀s , s’ ∈ S, ∀t , t’ ∈ T → (s , t) (s’ , t’) = (ss’ , tt’)
Yang dimaksud dengan Relasi (biner) pada himpunan X adalah subhimpunan ρ dari produk langsung X × X , yaitu berupa koleksi pasangan terurut dari anggota-anggotadi X. Notasi (a,b)∈ ρ, a,b∈ X juga dapat ditulis dengan aρb (a berelasi ρ dengan b). Relasi kesamaan pada X, dilambangkan dengan ι : (a,b) ∈ ι ↔ a = b. Relasi universal pada X, dilambangkan dengan ω : (a,b) ∈ω → a,b∈X. dengan kata lain ω = X × X. Relasi kosong, dilambangkan dengan .
Jika ρ dan σ adalah relasi pada X maka komposisinya yaitu ρ ∘ σ
didefinisikan sebagai berikut: (a,b) ∈ ρ ∘ σ → ∃ x ∈ X , (a, x)∈ ρ dan (x,b)∈ σ.
Perlu dicermati bahwa operasi biner “ ∘ ” disini bersifat asosiatif . Kemudian
melalui penulisan ρ ⊆ σ, maka relasi yang dimaksud adalah ρ subset dari σ yaitu :
(a,b) ∈ ρ → (a,b) ∈ σ. Balikan dari relasi ρ kita lambangkan dengan ρ
-1
,
didefinisikan sebagai berikut: (a,b) ∈ ρ -1 ↔ (b,a) ∈ ρ.
Suatu relasi ρ pada himpunan X disebut relasi ekivalen jika ∀a,b,c∈X : (1) ι ⊆ ρ (aρa) disebut reflektif,
(2) ρ ⊆ ρ -1 (aρb → bρa) disebut simmetris, dan
(3) ρ ∘ ρ ⊆ ρ (aρb dan bρc→ aρc) disebut transitif.
Misalkan ρ adalah relasi pada himpunan X, dan a ∈ X , kita bentuk
himpunan ρa = {x∈ X : xρa }, aρ = {y∈ X : aρy } dan kita lambangkan family aρ dengan X/ρ . aρ disebut sebagai class ekivalen dari X modulo ρ yang memuat a. Pemetaan a → aρ disebut pemetaan kanonikal dari X pada X/ρ, dilambangkan dengan ρ♮. Jika ρ adalah relasi pada X, didefinisikan transitive closure ρ t dari ρ :
∘ ∘ ∘
8
Jika ρ0 adalah relasi pada X , maka relasi ρ1 = ρ0 ∪ ρ0 -1 ∪ ι adalah reflektif dan relasi simetris terkecil pada X yang memuat ρ0 . Transitive closure ρ = ρ1 -1 dari ρ1 adalah relasi ekivalen pada X dan memuat seluruh relasi ekivalen pada X yang memuat ρ0. ρ disebut sebagai relasi ekivalen pada X yang dibangun oleh ρ0 . Relasi ρ pada suatu grupoid S dikatakan kompatibel kanan (reguler
/homogen) jika aρb (a,b ∈ S ) → acρbc, ∀c∈S ,dan dikatakan kompatibel kiri jika
aρb (a,b ∈ S ) → caρcb, ∀c∈S. Relasi ekivalen kompatibel kanan pada S disebut
kongruen kanan . Yang dimaksud dengan kongruen pada S adalah relasi ekivalen yang kompatibel kanan dan kompatibel kiri.
Jika ρ0 adalah suatu relasi pada grupoid S, maka terdapat setidaknya satu kongruen pada S yang memuat ρ0, sebagai contoh relasi universal ω = X × X. Sehingga akan selalu terdapat ρ yaitu irisan dari seluruh kongruen pada S yang memuat ρ0, kita sebut ρ sebagai kongruen pada S yang dibangun oleh ρ0.
2.5 WORDS, ALPHABET, SYLLABLE Misalkan A adalah himpunan elemen ai , dengan i ∈ N. Kita pandang A disini sebagai Alphabet dan ai adalah letters pada alphabet tersebut, kemudian setiap symbol dalam bentuk ain, dengan n ∈ Z dinamakan syllable. Word adalah sejumlah hingga string w dari syllable yang ditulis secara juxtaposisi, sebagai contoh : a1a1-1a2-1a3a4a4-1 .Word yang tereduksi adalah word yang didapat dengan cara menghilangkan syllable-syllable berupa a1a-1 dan a-1a1, contoh : a1a1-1a2-1a3a4a4-1 → a2-1a3.
... 9
