Monoid: Perbedaan antara revisi

Konten dihapus Konten ditambahkan

Sebaris

Revisi per 30 November 2020 07.15

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

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

Misalnya, fungsi dari suatu himpunan menjadi dirinya sendiri membentuk monoid sehubungan dengan komposisi fungsi. Secara lebih umum, di teori kategori, morfisme sebuah objek untuk dirinya sendiri membentuk sebuah monoid, dan, sebaliknya, sebuah monoid dapat dipandang sebagai kategori dengan satu objek.

Dalam ilmu komputer dan pemrograman komputer, himpunan string yang dibangun dari himpunan karakter adalah monoid bebas. Transisi monoid dan monoid sintaksis 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 properti umum monoid lainnya.

Definisi

Misalkan S adalah himpunan dan • adalah beberapa operasi biner $S \times S \to S$ , maka S dengan • adalah monoid jika memenuhi dua aksioma berikut:

Asosiatif: Untuk a , b dan c dalam S pada persamaan $(a • b) • c = a • (b • c)$ .
Elemen identitas: Terdapat elemen e di S sehingga untuk setiap elemen a di S pada persamaan $e • a = a • e = a$ .

Dengan kata lain, monoid adalah semigroup dengan elemen identitas. Ia juga dapat dianggap sebagai magma dengan asosiasi dan identitas.^[1] Untuk alasan ini identitas dianggap sebagai konstanta, yaitu Operasi 0-ari (atau nullari). Oleh karena itu, monoid dicirikan oleh spesifikasi tiga kali lipat (S, • , e).

Bergantung pada konteksnya, simbol untuk operasi biner dapat dihilangkan, sehingga operasi tersebut dilambangkan dengan penjajaran; misalnya, aksioma monoid dapat ditulis $(ab)c=a(bc)$ dan $ea=ae=a$ . Notasi ini tidak menyiratkan bahwa itu adalah angka yang dikalikan.

Sebuah monoid setiap elemen memiliki invers adalah grup.

Struktur monoid

Submonoid

Submonoid dari sebuah monoid $(M, •)$ adalah subset N of M yang ditutup di bawah operasi monoid dan berisi elemen identitas e dari M .^[2]^[3] Secara simbolis, N adalah submonoid dari M if $N \subseteq M$ , $x • y \in N$ dimana $x, y \in N$ , dan $e \in N$ . N dengan demikian monoid di bawah operasi biner yang diwarisi dari M .

Generator

Himpunan bagian S dari M dikatakan sebagai generator dari M jika M adalah himpunan terkecil yang berisi S yaitu ditutup di bawah operasi monoid, atau setara dengan M adalah hasil dari penerapan operator penutupan keuangan ke S . Jika ada generator dari M yang memiliki kardinalitas terbatas, maka M dikatakan sebagai dihasilkan secara terbatas. Tidak setiap himpunan S akan menghasilkan monoid, karena struktur yang dihasilkan mungkin tidak memiliki elemen identitas.

Monoid komutatif

Monoid yang operasinya komutatif disebut monoid komutatif (atau, lebih jarang, abelian monoid). Monoid komutatif sering kali ditulis secara aditif. Setiap monoid komutatif diberkahi dengan aljabar praorder ing $\leq$ , yang ditentukan dari $x \leq y$ jika ada z maka $x + z = y$ .^[4] unit-order dari monoid komutatif M adalah elemen u dari M sehingga untuk setiap elemen x dari M , ada v dalam himpunan yang dihasilkan oleh u sedemikian rupa $x \leq v$ . Ini sering digunakan jika M adalah kerucut positif dari order sebagian grup abelian G , dalam hal ini kami mengatakan bahwa u adalah unit order G.

Monoid sebagian komutatif

Monoid yang operasinya bersifat komutatif untuk beberapa orang, tetapi tidak semua elemennya adalah jejak monoid; jejak monoid biasanya terjadi dalam teori komputasi bersamaan.

Contoh

Dari 16 kemungkinan operator Boolean biner, masing-masing dari empat yang memiliki identitas dua sisi juga komutatif dan asosiatif dan dengan demikian membuat himpunan {Salah, benar} menjadi monoid komutatif. Di bawah definisi standar, AND dan XNOR memiliki identitas True sedangkan XOR dan OR memiliki identitas maka itu salah. Monoid dari AND dan OR juga idempoten sedangkan dari XOR dan XNOR.

Tindakan dan monoid operator

Misalkan M berbentuk monoid, dengan operasi biner dilambangkan dengan • dan elemen identitas dilambangkan dengan e . Kemudian a (kiri) M- ari (atau tindakan kiri di atas M ) adalah satu set X bersama dengan operasi $\cdot : M \times X \to X$ yang kompatibel dengan struktur monoid sebagai berikut:

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

Ini adalah analogi dalam teori monoid a (kiri) aksi kelompok. Baik tindakan M didefinisikan dengan cara yang serupa. Sebuah monoid dengan suatu tindakan juga dikenal sebagai operator monoid. Contoh penting termasuk sistem transisi dari semiautomata. transformasi semigrup dapat dibuat menjadi operator monoid dengan menggabungkan transformasi identitas.

Monoid homomorfisme

Bilangan real adalah gelanggang, yang memiliki penjumlahan dan perkalian. Himpunan semua 2 × 2 matriks juga merupakan cincin, di bawah penambahan matriks dan perkalian matriks. Jika kita mendefinisikan fungsi antara gelanggang ini sebagai berikut:

f(r)={\begin{pmatrix}r&0\\0&r\end{pmatrix}}

di mana $r$ adalah bilangan real, maka $f$ adalah homomorfisme gelanggang, karena $f$ mempertahankan kedua penjumlahan:

f(r+s)={\begin{pmatrix}r+s&0\\0&r+s\end{pmatrix}}={\begin{pmatrix}r&0\\0&r\end{pmatrix}}+{\begin{pmatrix}s&0\\0&s\end{pmatrix}}=f(r)+f(s)

dan perkalian:

f(rs)={\begin{pmatrix}rs&0\\0&rs\end{pmatrix}}={\begin{pmatrix}r&0\\0&r\end{pmatrix}}{\begin{pmatrix}s&0\\0&s\end{pmatrix}}=f(r)\,f(s).

Untuk contoh lain, bukan-nol bilangan kompleks membentuk kelompok di bawah operasi perkalian, seperti halnya bilangan riil bukan-nol. (Nol harus dikeluarkan dari kedua grup karena tidak memiliki perkalian invers, yang diperlukan untuk elemen grup.) Tentukan sebuah fungsi $f$ dari bilangan kompleks bukan nol ke bilangan real bukan nol dengan

f(z)=|z|.

Artinya, $f$ adalah nilai absolut (atau modulus) dari bilangan kompleks $z$ . Maka $f$ adalah homomorfisme kelompok, karena mempertahankan perkalian:

f(z_{1}z_{2})=|z_{1}z_{2}|=|z_{1}||z_{2}|=f(z_{1})f(z_{2}).

Perhatikan bahwa $f$ tidak dapat diperpanjang menjadi homomorfisme gelanggang (dari bilangan kompleks ke bilangan real), karena tidak mempertahankan penambahan:

|z_{1}+z_{2}|\neq |z_{1}|+|z_{2}|.

Sebagai contoh lain, diagram menunjukkan homomorfisme monoid $f$ dari monoid $(\mathbb {N} ,+,0)$ ke monoid $(\mathbb {N} ,\times ,1)$ . Karena nama berbeda dari operasi terkait, properti pelestarian struktur yang dipenuhi oleh $f$ berjumlah $f(x+y)=f(x)\times f(y)$ and $f(0)=1$ .

Sebuah komposisi aljabar $A$ di atas bidang $F$ memiliki bentuk kuadrat, yang disebut norma, $N:A\to F$ , yang merupakan homomorfisme grup dari grup perkalian dari $A$ ke grup perkalian dari $F$ .

Persamaan presentasi

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 \subset Σ * \times Σ *$ , satu mendefinisikan penutupan simetrisnya sebagai $R \cup R -1$ . Ini dapat diperluas ke hubungan simetris $E \subset Σ * \times Σ *$ dengan mendefinisikan $x ~ E y$ jika dan hanya jika $x = sut$ dan $y = svt$ untuk beberapa pita $u, v, s, t \in Σ *$ dengan $(u, v) \in R \cup R -1$ . 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 $R=\{u_{1}=v_{1},\cdots ,u_{n}=v_{n}\}$ . Thus, for example,

\langle p,q\,\vert \;pq=1\rangle

adalah presentasi persamaan untuk monoid bisiklik, dan

\langle a,b\,\vert \;aba=baa,bba=bab\rangle

adalah monoid plaktik derajat 2 (memiliki urutan tak terhingga). Elemen monoid plastik ini dapat ditulis sebagai $a^{i}b^{j}(ba)^{k}$ 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.^[5] adalah,

Monoid, pada dasarnya, sama dengan kategori dengan satu objek.

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.^[5] 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.^[5]

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 $\varepsilon$ dan operasi asosiatif $\bullet$ , operasi lipat didefinisikan sebagai berikut:

\mathrm {kelipatan} :M^{*}\rightarrow M=l\mapsto {\begin{cases}\varepsilon &{\mbox{jika }}l=\mathrm {nil} \\m\bullet \mathrm {kelipatan} \,l'&{\mbox{jika }}l=\mathrm {cons} \,m\,l'\end{cases}}

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 $\Sigma _{I}$ untuk himpunan indeks $I$ apa pun yang:^[6]^[7]^[8]^[9]

\sum _{i\in \emptyset }{m_{i}}=0;\quad \sum _{i\in \{j\}}{m_{i}}=m_{j};\quad \sum _{i\in \{j,k\}}{m_{i}}=m_{j}+m_{k}\quad {\text{ for }}j\neq k

dan

\sum _{j\in J}{\sum _{i\in I_{j}}{m_{i}}}=\sum _{i\in I}(m_{i})\quad {\text{ if }}\bigcup _{j\in J}I_{j}=I{\text{ and }}I_{j}\cap I_{j'}=\emptyset \quad {\text{ for }}j\neq j'

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

a+\sup S=\sup(a+S)\ .

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

\sum _{I}a_{i}=\sup \sum _{E}a_{i}

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.^[9]

Lihat pula

Catatan

^ Jika e₁ dan e₂ memenuhi persamaan di atas, lalu e₁ = e₁ • e₂ = e₂.
^ Jacobson 2009.
^ Beberapa penulis mengabaikan persyaratan bahwa submonoid harus mengandung elemen identitas dari definisinya, hanya mensyaratkan bahwa ia memiliki elemen identitas an , yang dapat dibedakan dari elemen identitas M .
^ 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.
^ ^a ^b ^c Awodey, Steve (2006). Category Theory. Oxford Logic Guides. 49. Oxford University Press. hlm. 10. ISBN 0-19-856861-4. Zbl 1100.18001.
^ 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
^ 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.
^ 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.
^ ^a ^b 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.

[1] Jika e₁ dan e₂ memenuhi persamaan di atas, lalu e₁ = e₁ • e₂ = e₂.

[FOOTNOTEJacobson2009-2] Jacobson 2009.

[3] Beberapa penulis mengabaikan persyaratan bahwa submonoid harus mengandung elemen identitas dari definisinya, hanya mensyaratkan bahwa ia memiliki elemen identitas an , yang dapat 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.

[Awo10-5] Awodey, Steve (2006). Category Theory. Oxford Logic Guides. 49. Oxford University Press. hlm. 10. ISBN 0-19-856861-4. Zbl 1100.18001.

[droste-6] 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

[7] 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.

[8] 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.

[Kuich11-9] 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.

[1]

[2]

[3]

[4]

α

[5]

[6]

[7]

[8]

[9]