Monoid

Untuk objek monoid dalam teori kategori, lihat Monoid (teori kategori).

Artikel ini bukan mengenai Monad.

Dalam aljabar abstrak, cabang matematika, monoid adalah himpunan kompleks dengan asosiatif operasi biner dan elemen identitas

Struktur aljabar antara magma dan grup. Monoid adalah semigrop dengan identitas.

Monoid adalah semigrup dengan identitas. Struktur aljabar terjadi di beberapa cabang matematika.

Misal, fungsi dari suatu himpunan membentuk monoid dengan komposisi fungsi. Secara lebih umum, dalam teori kategori, morfisme dari sebuah objek dengan membentuk sebuah monoid, dan, sebaliknya, sebuah monoid dapat dipandang sebagai kategori dengan satu objek.

Dalam ilmu komputer dan pemrograman komputer, himpunan string dari himpunan karakter adalah monoid bebas. Transisi monoid dan monoid sintaktik digunakan untuk mendeskripsikan mesin keadaan hingga. Jejak monoid dan sejarah monoid memberikan dasar untuk proses bate dan komputasi bersamaan.

Dalam ilmu komputer teoretis, studi tentang monoid sangat penting untuk teori automata (teori Krohn–Rhodes), dan teori bahasa formal (masalah ketinggian bintang) .

Lihat semigrup untuk sejarah subjek, dan beberapa sifat umum monoid lainnya.

Definisi

Misalnya S adalah himpunan dan • adalah beberapa operasi biner S × S → S, maka S dengan • adalah monoid jika memenuhi dua aksioma berikut:

Dengan kata lain, monoid adalah semigrup dengan elemen identitas. Monoid disebut sebagai magma dengan asosiasi dan identitas. Untuk alasan identitas sebagai konstanta, yaitu operasi 0-ari (atau nullari). Oleh karena itu, monoid diartikan sebagai spesifikasi rangkap (S, • , e).

Bergantung pada konteksnya, simbol untuk operasi biner dapat dihilangkan, maka operasi tersebut dilambangkan dengan penjajaran; misalnya, aksioma monoid ditulis sebagai dan . Notasi tersebut tidak menyiratkan bahwa bilangan yang dikalikan.

Monoid setiap elemen menggunakan invers adalah grup.

Struktur monoid

Submonoid

Submonoid dari sebuah monoid (M, •) adalah himpunan bagian N dari M dibawah operasi monoid dan elemen identitas e dari M. Secara simbolis, N adalah submonoid dari M jika N ⊆ M, x • y ∈ N dimana x, y ∈ N, dan e ∈ N. N dengan monoid dibawah operasi biner yang digunakan dari M.

Generator

Himpunan bagian S dari M sebagai generator dari M jika M adalah himpunan terkecil S yaitu penutupan dibawah operasi monoid, atau M adalah hasil dari penerapan operasi penutupan keuangan ke S. Jika generator dari M kardinalitas hingga, maka M sebagai dihasilkan secara hingga. Tidak setiap himpunan S akan menghasilkan monoid, karena struktur yang dihasilkan tidak memiliki elemen identitas.

Monoid komutatif

Monoid dimana operasi komutatif disebut monoid komutatif (atau abelian monoid). Monoid komutatif ditulis secara aditif. Setiap monoid komutatif dengan aljabar preorder ≤ ditentukan dari x ≤ y dan z adalah x + z = y. unit-order dari monoid komutatif M adalah elemen u dari M maka untuk setiap elemen x dari M, v dalam himpunan yang dihasilkan oleh u adalah x ≤ v. Jika M adalah kerucut positif dari terurut sebagian untul grup abelian G, dalam u adalah unit order G.

Monoid sebagian komutatif

Monoid dimana operasinya bersifat komutatif untuk semua elemennya adalah jejak monoid; jejak monoid biasanya terjadi dalam teori komputasi bersamaan.

Contoh

• Dari 16 kemungkinan operasi Boolean biner dari empat yang memiliki identitas dua sisi komutatif dan asosiatif dan dengan demikian membuat himpunan {salah, benar} menjadi monoid komutatif. Dibawah definisi standar, AND dan XNOR menggunakan identitas sedangkan XOR dan OR memiliki identitas yang salah. Monoid dari AND dan OR untuk idempoten dari XOR dan XNOR.
• Himpunan bilangan asli adalah monoid komutatif dibawah penjumlahan (elemen identitas 0) atau perkalian (elemen identitas 1). Submonoid dari N dibawah penambahan disebut monoid numerik.
• Himpunan bilangan bulat positif adalah monoid komutatif dalam perkalian (elemen identitas 1).
• Diberikan himpunan A, himpunan himpunan bagian dari A adalah monoid komutatif dibawah (elemen identitasnya adalah A sendiri).
• Diberikan himpunan A, himpunan bagian dari A adalah monoid komutatif dibawah gabungan (elemen identitas adalah himpunan kosong).
• Generalisasi contoh sebelumnya, setiap semikis batas adalah monoid komutatif idempoten.
  • Secara khusus, setiap kisi berbatas dapat diberkahi dengan struktur monoid bertemu dan gabungan. Elemen identitas adalah bagian atas dan bawah kisi. Karena kisi-kisi, Aljabar Heyting dan Aljabar Boolean diberkahi dengan struktur monoid ini.
• Setiap himpunan singleton (x} penutupan dibawah operasi biner • bentuk monoid trivial (satu elemen) merupakan grup trivial.
• Setiap grup adalah monoid dan setiap grup abelian adalah monoid komutatif.
• Semua semigrup S dapat diubah menjadi monoid dengan menggabungkan elemen e bukan S dan menentukan e • s = s = s • e untuk semua s ∈ S. Konversi semigrup di monoid ini dilakukan oleh funktor bebas antara kategori semigrup dan kategori monoid.
  • Jadi, monoid idempoten (sebagai temukan-pertama) dapat dibentuk dengan menggabungkan elemen identitas e ke semigrup nol kiri diatas himpunan S. Monoid (disebut temukan-terakhir) bentuk dari grup nol kanan diatas S.
    • Adjoin dari sebuah identitas e ke semigrup kiri-nol dengan dua elemen (lt, gt}. Kemudian monoid idempoten dihasilkan (lt, e, gt} memodelkan urutan leksikografis dari suatu urutan yang diberi urutan elemennya, dengan e mewakili persamaan.
• Himpunan yang mendasari setiap gelanggang, dengan operasi penjumlahan atau perkalian. Menurut definisi, gelanggang memiliki identitas perkalian 1.
  • Bilangan bulat, bilangan rasional, bilangan riil, atau bilangan kompleks, dengan operasi penjumlahan atau perkalian.
  • Himpunan semua n oleh n matriks diatas gelanggang tertentu, dengan penambahan matriks atau perkalian matriks sebagai operasi.
• Himpunan semua string hingga beberapa alfabet tetap Σ membentuk monoid dengan rangkaian string sebagai operasinya. String kosong berfungsi sebagai elemen identitas. Monoid ini dilambangkan Σ^∗ dan disebut monoid bebas di atas Σ.
• Diberikan monoid M, monoid berlawanan M^op memiliki himpunan operasi dan elemen identitas yang sama M, dan operasi ditentukan oleh x •^op y = y • x. Monoid komutatif adalah kebalikan dari monoid itu sendiri.
• Diberikan dua himpunan M dan N dengan struktur monoid (atau, secara umum, sejumlah terbatas monoid, M₁, …, M_k), produk Kartesius mereka M × N adalah monoid (masing-masing, M₁ × ⋯ × M_k). Operasi asosiatif dan elemen identitas ditentukan berpasangan.
• Monoid M. Himpunan semua fungsi dari himpunan tertentu ke M adalah monoid. Elemen identitas adalah fungsi konstanta yang memetakan nilai ke identitas M; operasi asosiatif ditentukan sesetitik.
• Monoid M dengan operasi • dan elemen identitas e, dan pertimbangkan himpunan kuasa P(M) terdiri dari semua himpunan bagian dari M. Operasi biner untuk himpunan bagian tersebut dapat ditentukan dengan S • T = ( s • t : s ∈ S, t ∈ T }. Nilai berubah ke P(M) menjadi monoid dengan elemen identitas (e}. Dengan cara yang sama, himpunan kuasa grup G adalah monoid di bawah produk himpunan bagian grup.
• Misalkan S menjadi satu himpunan. Himpunan semua fungsi S → S membentuk monoid dibawah komposisi fungsi. Identitas hanyalah fungsi identitas. Ini disebut sebagai monoid transformasi penuh dari S. Jika S hingga dengan elemen n, monoid fungsi pada S hingga dengan elemen nⁿ.
• Generalisasi contoh sebelumnya, misalkan C menjadi kategori dan X objek C. Himpunan dari semua endomorfisme dari X, dilambangkan End_C(X), membentuk monoid dibawah komposisi morfisme. Untuk lebih lanjut tentang relasi antara teori kategori dan monoid, lihat dibawah.
• Himpunan homeomorfisme kelas dari permukaan kompak dengan jumlah terhubung. Elemen unitnya adalah kelas bola-2 biasa. Selanjutnya, jika a menunjukkan kelas dari torus, dan b menunjukkan kelas bidang proyektif, maka setiap elemen c dari monoid memiliki ekspresi unik berupa c = na + mb dimana n adalah bilangan bulat positif dan m = 0, 1, atau 2. Maka 3b = a + b.
• Maka menjadi monoid siklik urutan n, yaitu . Kemudian untuk beberapa . Faktanya, setiap k tersebut memberikan monoid yang berbeda dengan urutan n, dan setiap monoid siklik isomorfik untuk salah satu dari ini.
  Selain itu, f sebagai fungsi pada titik diberikan oleh

atau, secara ekuivalen

Perkalian elemen dalam kemudian diberikan komposisi fungsi.

Jadi maka fungsi f adalah permutasi dari dan grup siklik unik dari urutan n.

Aksi dan monoid operator

Artikel utama: Tindakan monoid

Misalkan M bentuk dari monoid, dengan operasi biner dilambangkan dengan • dan elemen identitas dan dilambangkan dengan e. Maka (kiri) M-ari (atau aksi kiri diatas M) adalah satu himpunan X dengan operasi ⋅ : M × X → X yang kompatibel dengan struktur monoid sebagai berikut:

• untuk x dalam X: e ⋅ x = x;
• untuk a, b pada M dan x pada X: a ⋅ (b ⋅ x) = (a • b) ⋅ x.

Ini adalah analogi dalam teori monoid (kiri) grup aksi. Baik aksi M didefinisikan dengan cara biasa. Monoid dengan suatu aksi dikenal sebagai operasi monoid. Contoh yang termasuk sistem transisi dari semiautomata. Transformasi semigrup dapat dibuat menjadi operasi monoid dengan menggabungkan transformasi identitas.

Monoid homomorfisme

Monoid homomorfisme dari monoid (N, +, 0) ke monoid (N, ×, 1), didefinisikan dari . Fungsi tersebut adalah injeksi, bukan konjektur.

Bilangan riil adalah gelanggang yang menggunakan penembahab dan perkalian. Himpunan semua 2 × 2 matriks merupakan gelanggang, dibawah penambahan matriks dan perkalian matriks. Jika mendefinisikan fungsi antara gelanggang, sebagai berikut:

dimana r adalah bilangan riil, maka f adalah homomorfisme gelanggang, karena f mempertahankan dua penambahan:

dan perkalian:

Untuk contoh lain, bukan-nol untuk bilangan kompleks membentuk grup dibawah operasi perkalian, seperti halnya bilangan riil bukan-nol. Nol dihilangkan dari kedua grup karena tidak memiliki invers perkalian, yang diperlukan untuk elemen grup. Tentukan fungsi dari bilangan kompleks bukan nol ke bilangan riil bukan nol dengan

Artinya, adalah nilai mutlak (atau modulus) dari bilangan kompleks . Maka adalah homomorfisme grup, karena perkalian:

Perhatikan bahwa f tidak dapat diperpanjang menjadi homomorfisme gelanggang (dari bilangan kompleks ke bilangan riil), karena tidak termasuk penambahan:

Sebagai contoh lain, diagram menunjukkan homomorfisme monoid dari monoid ke monoid . Karena nama berbeda dari operasi terkait, sifat pelestarian struktur yang dipenuhi oleh dihasilkan sebagai dan .

Komposisi aljabar diatas bidang menggunakan bentuk kuadrat, yang disebut norma, , yang merupakan homomorfisme grup dari grup perkalian dari ke grup perkalian dari .

Persamaan presentasi

Artikel utama: Presentasi dari sebuah monoid

Monoid dapat diberikan presentasi, dengan cara yang sama seperti grup dapat ditentukan melalui presentasi grup. Seseorang melakukan ini dengan menentukan satu set generator Σ, dan satu set relasi pada monoid bebas Σ^∗. Seseorang melakukannya dengan memperluas (finite) relasi biner pada Σ^* ke kongruensi monoid, dan kemudian membangun monoid hasil bagi, seperti di atas.

Diberikan relasi biner R ⊂ Σ^∗ × Σ^∗, satu mendefinisikan penutupan simetrisnya sebagai R ∪ R⁻¹. Ini dapat diperluas ke hubungan simetris E ⊂ Σ^∗ × Σ^∗ dengan mendefinisikan x ~_E y jika dan hanya jika x = sut dan y = svt untuk beberapa pita u, v, s, t ∈ Σ^∗ dengan (u,v) ∈ R ∪ R⁻¹. Akhirnya, seseorang mengambil penutupan refleksif dan transitif dari E , yang kemudian merupakan kongruensi monoid.

Dalam situasi tipikal, relasi R hanya diberikan sebagai sekumpulan persamaan, sehingga . Thus, for example,

adalah presentasi persamaan untuk monoid bisiklik, dan

adalah monoid plaktik derajat 2 (memiliki urutan tak terhingga). Elemen monoid plastik ini dapat ditulis sebagai untuk integer i , j , k , karena hubungan menunjukkan bahwa ba bolak-balik dengan a dan b .

Kaitannya dengan teori kategori

Struktur grup
	Totalitas^α	Asosiatif	Identitas	Invers	Komutativitas
Semigrupoid	Tidak dibutuhkan	Dibutuhkan	Tidak dibutuhkan	Tidak dibutuhkan	Tidak dibutuhkan
Kategori Kecil	Tidak dibutuhkan	Dibutuhkan	Dibutuhkan	Tidak dibutuhkan	Tidak dibutuhkan
Grupoid	Tidak dibutuhkan	Dibutuhkan	Dibutuhkan	Dibutuhkan	Tidak dibutuhkan
Magma	Dibutuhkan	Tidak dibutuhkan	Tidak dibutuhkan	Tidak dibutuhkan	Tidak dibutuhkan
Kuasigrup	Dibutuhkan	Tidak dibutuhkan	Tidak dibutuhkan	Dibutuhkan	Tidak dibutuhkan
Magma Unital	Dibutuhkan	Tidak dibutuhkan	Dibutuhkan	Tidak dibutuhkan	Tidak dibutuhkan
Loop	Dibutuhkan	Tidak dibutuhkan	Dibutuhkan	Dibutuhkan	Tidak dibutuhkan
Semigrup	Dibutuhkan	Dibutuhkan	Tidak dibutuhkan	Tidak dibutuhkan	Tidak dibutuhkan
Semigrup invers	Dibutuhkan	Dibutuhkan	Tidak dibutuhkan	Dibutuhkan	Tidak dibutuhkan
Monoid	Dibutuhkan	Dibutuhkan	Dibutuhkan	Tidak dibutuhkan	Tidak dibutuhkan
Monoid komutatif	Dibutuhkan	Dibutuhkan	Dibutuhkan	Tidak dibutuhkan	Dibutuhkan
Grup	Dibutuhkan	Dibutuhkan	Dibutuhkan	Dibutuhkan	Tidak dibutuhkan
Grup Abelian	Dibutuhkan	Dibutuhkan	Dibutuhkan	Dibutuhkan	Dibutuhkan
^α Penutupan, yang digunakan dalam banyak sumber, merupakan aksioma yang setara dengan totalitas, meskipun didefinisikan secara berbeda.

Monoid dapat dipandang sebagai kelas khusus kategori. Memang, aksioma yang diperlukan dari operasi monoid persis seperti yang diperlukan dari komposisi morfisme ketika dibatasi pada himpunan semua morfisme yang sumber dan targetnya adalah objek tertentu. adalah,

Lebih tepatnya, diberi monoid ( M , •), seseorang dapat membuat kategori kecil dengan hanya satu objek dan yang morfismenya adalah elemen dari M. Komposisi morfisme diberikan oleh operasi monoid •.

Demikian juga, homomorfisme monoid hanyalah funktor antara kategori objek tunggal. Jadi konstruksi ini memberikan kesetaraan antara kategori monoid (kecil) Mon dan subkategori lengkap kategori kategori (kecil) Cat. Demikian pula, kategori grup setara dengan subkategori lengkap lainnya Cat.

Dalam pengertian ini, teori kategori dapat dianggap sebagai perluasan dari konsep monoid. Banyak definisi dan teorema tentang monoid dapat digeneralisasikan ke kategori kecil dengan lebih dari satu objek. Misalnya, hasil bagi dari kategori dengan satu objek hanyalah hasil bagi monoid.

Monoid, seperti struktur aljabar lainnya, juga membentuk kategorinya sendiri, Mon, yang objeknya monoid dan morfisme homomorfisme monoid.

Ada pula pengertian objek monoid yang merupakan definisi abstrak dari apa yang dimaksud dengan monoid dalam suatu kategori. Objek monoid dalam 'Set' hanyalah sebuah monoid.

Monoid dalam ilmu komputer

Dalam ilmu komputer, banyak tipe data abstrak dapat diberkahi dengan struktur monoid. Dalam pola yang sama, Sebuah urutan elemen monoid adalah "dilipat" atau "terakumulasi" untuk menghasilkan nilai akhir. Misalnya, banyak algoritme iteratif perlu memperbarui beberapa jenis "menjalankan total" pada setiap iterasi; pola ini dapat diekspresikan secara elegan dengan operasi monoid. Alternatifnya, asosiasi operasi monoid memastikan bahwa operasi dapat paralel dengan menggunakan jumlah awalan atau algoritma serupa, untuk memanfaatkan banyak inti atau prosesor secara efisien.

Diberikan urutan nilai tipe M dengan elemen identitas dan operasi asosiatif , operasi lipat didefinisikan sebagai berikut:

Selain itu, struktur data apa pun dapat 'dilipat' dengan cara yang sama, mengingat serialisasi elemennya. Misalnya, hasil dari "melipat" sebuah pohon biner mungkin berbeda tergantung pada pemesanan di muka vs. setelah pesanan traversal pohon.

Monoid lengkap

Sebuah monoid lengkap adalah monoid komutatif yang dilengkapi dengan operasi jumlah infiniter untuk himpunan indeks I apa pun yang:

dan

monoid kontinu adalah monoid komutatif terurut di mana setiap himpunan terarah memiliki batas atas terkecil yang kompatibel dengan operasi monoid:

Kedua konsep ini terkait erat: monoid kontinu adalah monoid lengkap di mana jumlah infiniter dapat didefinisikan sebagai

di mana supremum di sebelah kanan berjalan di atas semua himpunan bagian terbatas E dari I dan setiap jumlah di sebelah kanan adalah jumlah yang terbatas di monoid.

Lihat pula

• Relasi Green
• Monad (pemrograman fungsional)
• Semigelanggang dan Aljabar Kleene
• Masalah ketinggian bintang
• Kotak Weda

Catatan

1. Jika e₁ dan e₂ memenuhi persamaan diatas, maka e₁ = e₁ • e₂ = e₂.
2. Jacobson 2009.
3. Beberapa penulis mengabaikan persyaratan bahwa submonoid mengandung elemen identitas dari definisinya, hanya mensyaratkan bahwa ia memiliki elemen identitas an dibedakan dari elemen identitas M.
4. Gondran, Michel; Minoux, Michel (2008). Graphs, Dioids and Semirings: New Models and Algorithms. Operations Research/Computer Science Interfaces Series. 41. Dordrecht: Springer-Verlag. hlm. 13. ISBN 978-0-387-75450-5. Zbl 1201.16038. 
5. Rhodes, John; Steinberg, Benjamin (2009), Teori-q dari Semigrup Hingga: Sebuah Pendekatan Baru, Springer Monographs in Mathematics, 71, Springer, hlm. 22, ISBN 9780387097817 .
6. Jacobson 2009, hlm. 29, examples 1, 2, 4 & 5.
7. Jacobson 2009, hlm. 35.
8. Awodey, Steve (2006). Category Theory. Oxford Logic Guides. 49. Oxford University Press. hlm. 10. ISBN 0-19-856861-4. Zbl 1100.18001. 
9. Droste, M., & Kuich, W. (2009). Semirings and Formal Power Series. Handbook of Weighted Automata, 3–28. DOI:10.1007/978-3-642-01492-5_1, pp. 7–10
10. Hebisch, Udo (1992). "Eine algebraische Theorie unendlicher Summen mit Anwendungen auf Halbgruppen und Halbringe". Bayreuther Mathematische Schriften (dalam bahasa German). 40: 21–152. Zbl 0747.08005. Pemeliharaan CS1: Bahasa yang tidak diketahui (link)
11. Kuich, Werner (1990). "ω-continuous semirings, algebraic systems and pushdown automata". Dalam Paterson, Michael S. Automata, Languages and Programming: 17th International Colloquium, Warwick University, England, July 16-20, 1990, Proceedings. Lecture Notes in Computer Science. 443. Springer-Verlag. hlm. 103–110. ISBN 3-540-52826-1. 
12. Kuich, Werner (2011). "Algebraic systems and pushdown automata". Dalam Kuich, Werner. Algebraic foundations in computer science. Essays dedicated to Symeon Bozapalidis on the occasion of his retirement. Lecture Notes in Computer Science. 7020. Berlin: Springer-Verlag. hlm. 228–256. ISBN 978-3-642-24896-2. Zbl 1251.68135. 

Referensi

• Howie, John M. (1995), Fundamentals of Semigroup Theory, London Mathematical Society Monographs. New Series, 12, Oxford: Clarendon Press, ISBN 0-19-851194-9, Zbl 0835.20077 
• Jacobson, Nathan (1951), Lectures in Abstract Algebra, I, D. Van Nostrand Company, ISBN 0-387-90122-1 
• Jacobson, Nathan (2009), Basic algebra, 1 (edisi ke-2nd), Dover, ISBN 978-0-486-47189-1 
• Kilp, Mati; Knauer, Ulrich; Mikhalev, Alexander V. (2000), Monoids, acts and categories. With applications to wreath products and graphs. A handbook for students and researchers, de Gruyter Expositions in Mathematics, 29, Berlin: Walter de Gruyter, ISBN 3-11-015248-7, Zbl 0945.20036 
• Lothaire, M. (1997), Combinatorics on words, Encyclopedia of Mathematics and Its Applications, 17, Perrin, D.; Reutenauer, C.; Berstel, J.; Pin, J. E.; Pirillo, G.; Foata, D.; Sakarovitch, J.; Simon, I.; Schützenberger, M. P.; Choffrut, C.; Cori, R.; Lyndon, Roger; Rota, Gian-Carlo. Foreword by Roger Lyndon (edisi ke-2nd), Cambridge University Press, doi:10.1017/CBO9780511566097, ISBN 0-521-59924-5, MR 1475463, Zbl 0874.20040 

Pranala luar

• Hazewinkel, Michiel, ed. (2001) [1994], "Monoid", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4 
• (Inggris) Weisstein, Eric W. "Monoid". MathWorld. 
• Monoid di PlanetMath.org.