|
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 (teori kategori)|objek]] dengan membentuk sebuah monoid, dan, sebaliknya, sebuah monoid dapat dipandang sebagai kategori dengan satu objek.
Dalam [[ilmu komputer]] dan [[pemrograman komputer]], himpunan [[string (ilmu komputer)|string]] dari himpunan [[Karakter (komputasi)|karakter]] adalah [[monoid bebas]]. [[Transisi monoid]] dan [[monoid sintaksissintaktik]] 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]]) .
* Diberikan himpunan {{mvar|A}}, himpunan bagian dari {{mvar|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 (order)|kisi]] berbatasberbatas dapat diberkahi dengan struktur monoid [[gabungan dan bertemu (matematika)|bertemu]] dan [[gabungan dan bertemu (matematika)|gabungan]]. Elemen identitas adalah bagian atas dan bawah kisi. Karena kisi-kisi, [[Aljabar Heyting]] dan [[Aljabar Boolean (struktur)|Aljabar Boolean]] diberkahi dengan struktur monoid ini.
* Setiap [[himpunan singleton]] {{math|{{mset|''x''}}}} penutupan dibawah operasi biner • bentuk monoid trivial (satu elemen) merupakan [[grup trivial]].
* Setiap [[grup (matematika)|grup]] adalah monoid dan setiap [[grup abelian]] adalah monoid komutatif.
:Jadi <math>k = 0</math> maka fungsi {{mvar|f}} adalah permutasi dari <math>\{0,1,2,\dots,n-1\},</math> dan [[grup siklik]] unik dari urutan {{mvar|n}}.
== TindakanAksi dan monoid operator ==
{{main|tindakanTindakan monoid}}
Misalkan '' M '' berbentukbentuk dari monoid, dengan operasi biner dilambangkan dengan • dan elemen identitas dan dilambangkan dengan '' e ''. Kemudian aMaka (kiri) '''''M''- ari''' (atau tindakanaksi kiri di atasdiatas '' M '') adalah satu sethimpunan '' X '' bersama dengan operasi {{math|⋅ : ''M'' × ''X'' → ''X''}} yang kompatibel dengan struktur monoid sebagai berikut:
* untuk '' x '' dalam '' X '': {{math|1=''e'' ⋅ ''x'' = ''x''}};
* untuk ''a'', ''b'' pada ''M'' dan ''x'' pada ''X'': {{math|1=''a'' ⋅ (''b'' ⋅ ''x'') = (''a'' • ''b'') ⋅ ''x''}}.
Ini adalah analogi dalam teori monoid a (kiri) [[AksiGrup kelompokaksi (matematika) |grup aksi kelompok]]. Baik tindakanaksi '' M '' didefinisikan dengan cara yang serupabiasa. Sebuah monoidMonoid dengan suatu tindakan jugaaksi dikenal sebagai '''[[operatoroperasi monoid]]'''. Contoh pentingyang termasuk [[sistem transisi]] daridari [[semiautomata]]. [[transformasiTransformasi semigrup]] dapat dibuat menjadi operatoroperasi monoid dengan menggabungkan transformasi identitas.
== Monoid homomorfisme ==
[[Berkas:Exponentiation as monoid homomorphism svg.svg|thumb|x200px|[[Monoid]] homomorfisme <math>f</math> dari monoid {{math|{{color|#008000|('''N''', +, 0)}}}} ke monoid {{math|{{color|#800000|('''N''', ×, 1)}}}}, didefinisikan dari <math>f(x) = 2^x</math>. IniFungsi tersebut adalah [[Fungsi injektif|injeksi]], tetapi bukan [[Fungsi konjektur|konjektur]].]]
[[Bilangan realriil]] adalah [[gelanggang (matematika)|gelanggang]], yang memilikimenggunakan penjumlahanpenembahab dan perkalian. Himpunan semua 2 × 2 [[matriks (matematika) | matriks]] juga merupakan cincingelanggang, di bawahdibawah [[penambahan matriks]] dan [[perkalian matriks]]. Jika kita mendefinisikan fungsi antara gelanggang ini, sebagai berikut:
:<math>f(r) = \begin{pmatrix}
r & 0 \\
0 & r
\end{pmatrix}</math>
di manadimana {{mvar|r}} adalah bilangan realriil, maka {{mvar|f}} adalah homomorfisme gelanggang, karena {{mvar|f}} mempertahankan keduadua penjumlahanpenambahan:
:<math>f(r+s) = \begin{pmatrix}
r+s & 0 \\
\end{pmatrix} = f(r)\,f(s).</math>
Untuk contoh lain, bukan-nol untuk [[bilangan kompleks]] membentuk [[kelompokgrup (matematika)|kelompokgrup]] di bawahdibawah operasi perkalian, seperti halnya bilangan riil bukan-nol. (Nol harus dikeluarkandihilangkan dari kedua grup karena tidak memiliki [[perkalian invers perkalian]], yang diperlukan untuk elemen grup.) Tentukan sebuah fungsi <math>f</math> dari bilangan kompleks bukan nol ke bilangan realriil bukan nol dengan
:<math>f(z) = |z| .</math>
Artinya, <math>f</math> adalah [[nilai absolutmutlak]] (atau modulus) dari bilangan kompleks <math>z</math>. Maka <math>f</math> adalah homomorfisme kelompokgrup, karena mempertahankan perkalian:
:<math>f(z_1 z_2) = |z_1 z_2| = |z_1| |z_2| = f(z_1) f(z_2).</math>
Perhatikan bahwa {{math|''f''}} tidak dapat diperpanjang menjadi homomorfisme gelanggang (dari bilangan kompleks ke bilangan realriil), karena tidak mempertahankantermasuk penambahan:
:<math>|z_1 + z_2| \ne |z_1| + |z_2|.</math>
Sebagai contoh lain, diagram menunjukkan homomorfisme [[monoid]] <math>f</math> dari monoid <math>(\mathbb{N}, +, 0)</math> ke monoid <math>(\mathbb{N}, \times, 1)</math>. Karena nama berbeda dari operasi terkait, propertisifat pelestarian struktur yang dipenuhi oleh <math> f </math> berjumlahdihasilkan sebagai <math>f(x+y) = f(x) \times f(y)</math> anddan <math>f(0) = 1</math>.
Sebuah [[komposisiKomposisi aljabar]] <math> A </math> di atasdiatas bidang <math> F </math> memilikimenggunakan [[bentuk kuadrat]], yang disebut ''norma'', <math>N: A \to F</math>, yang merupakan homomorfisme grup dari [[grup perkalian]] dari <math> A </math> ke grup perkalian dari <math> F </math>.
== Persamaan presentasi ==
== Kaitannya dengan teori kategori ==
{{Group-like structures}}
Monoid dapat dipandang sebagai kelas khusus [[teori kategori | 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.<ref name=Awo10>{{cite book |zbl=1100.18001 |title=Category Theory |volume=49 |series=Oxford Logic Guides |first=Steve |last=Awodey |authorlink=Steve Awodey |publisher=[[Oxford University Press]] |year=2006 |isbn=0-19-856861-4 |page=10}}</ref> adalah,
: ''Monoid, pada dasarnya, sama dengan kategori dengan satu objek.''
Lebih tepatnya, diberi monoid {{math | ('' 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.<ref name=Awo10/> Jadi konstruksi ini memberikan [[kesetaraan kategori | kesetaraan]] antara [[kategori monoid | 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.<ref name=Awo10/>
Ada pula pengertian [[monoid (teori kategori) | objek monoid]] yang merupakan definisi abstrak dari apa yang dimaksud dengan monoid dalam suatu kategori. Objek monoid dalam '''[[kategori himpunan|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 "[[lipat (fungsi orde tinggi) | 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 [[paralelisasi | paralel]] dengan menggunakan [[jumlah awalan]] atau algoritma serupa, untuk memanfaatkan banyak inti atau prosesor secara efisien.
Diberikan urutan nilai tipe '' M '' dengan elemen identitas <math>\varepsilon</math> dan operasi asosiatif <math>\bullet</math>, operasi '' lipat '' didefinisikan sebagai berikut:
== Monoid lengkap ==
Sebuah '''monoid lengkap''' adalah monoid komutatif yang dilengkapi dengan operasi jumlah [[Finiter | infiniter]] <math>\Sigma_I</math> untuk [[himpunan indeks]] {{mvar | I}} apa pun yang:<ref name="droste">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</ref><ref>{{cite journal |last=Hebisch |first=Udo |title=Eine algebraische Theorie unendlicher Summen mit Anwendungen auf Halbgruppen und Halbringe |language=German |zbl=0747.08005 |journal=Bayreuther Mathematische Schriften |volume=40 |pages=21–152 |year=1992}}</ref><ref>{{cite book |last=Kuich |first=Werner |chapter=ω-continuous semirings, algebraic systems and pushdown automata |pages=[https://archive.org/details/automatalanguage0000ical/page/103 103–110] |title=Automata, Languages and Programming: 17th International Colloquium, Warwick University, England, July 16-20, 1990, Proceedings |volume=443 |series=Lecture Notes in Computer Science |editor1-first=Michael S. |editor1-last=Paterson |publisher=[[Springer-Verlag]] |year=1990 |isbn=3-540-52826-1 |url=https://archive.org/details/automatalanguage0000ical/page/103 }}</ref><ref name=Kuich11>{{cite book |last=Kuich |first=Werner |chapter=Algebraic systems and pushdown automata |zbl=1251.68135 |editor1-last=Kuich |editor1-first=Werner |title=Algebraic foundations in computer science. Essays dedicated to Symeon Bozapalidis on the occasion of his retirement |location=Berlin |publisher=[[Springer-Verlag]] |isbn=978-3-642-24896-2 |series=Lecture Notes in Computer Science |volume=7020 |pages=228–256 |year=2011}}</ref>
: <math>\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</math>
* {{PlanetMath| urlname=Monoid | title=Monoid | id=389}}
[[Kategori: Struktur aljabar]]
[[Kategori: Teori kategori]]
[[Kategori: Teori semigrup]]
| 