Monoid: Perbedaan antara revisi

[[Berkas:Magma to group4.svg|thumb|right|300px|Struktur aljabar antara [[Magma (aljabar) | magma]] dan [[Grup (matematika) | grup]]. Monoid adalah [[semigroupsemigrop]] dengan identitas.]]

Dalam [[aljabar abstrak]], cabang [[matematika]], '''monoid''' adalah himpunan yang dilengkapikompleks dengan [[asosiatif]] [[operasi biner]] dan [[elemen identitas]]

Monoid adalah [[semigrup]] dengan identitas. Seperti [[strukturStruktur aljabar]] terjadi di beberapa cabang matematika.

MisalnyaMisal, fungsi dari suatu himpunan menjadi dirinya sendiri membentuk monoid sehubungan dengan komposisi fungsi. Secara lebih umum, didalam [[teori kategori]], morfisme dari sebuah [[objek (teori kategori) | objek]] untuk dirinya sendiridengan 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]] yang dibangun 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]].

Lihat [[Semigrupsemigrup]] untuk sejarah subjek, dan beberapa propertisifat umum monoid lainnya.

MisalkanMisalnya '' S '' adalah [[himpunan (matematika) | himpunan]] dan • adalah beberapa [[operasi biner]] {{math|1=''S'' × ''S'' → ''S''}}, maka '' S '' dengan • adalah '''monoid''' jika memenuhi dua aksioma berikut:

; Asosiatif: Untukuntuk '' a '', '' b '' dan '' c '' dalam '' S '' padadengan persamaan {{math|1=(''a'' • ''b'') • ''c'' = ''a'' • (''b'' • ''c'')}}.

; Elemen identitas: Terdapat elemen '' e '' didalam '' S '' sehingga untuk setiap elemen '' a '' didalam '' S '' padadengan persamaan {{math|1=''e'' • ''a'' = ''a'' • ''e'' = ''a''}}.

Dengan kata lain, monoid adalah [[semigroupsemigrup]] dengan [[elemen identitas]]. IaMonoid juga dapat dianggapdisebut sebagai [[magma (aljabar) | magma]] dengan asosiasi dan identitas.<ref>Jika ''e''₁ dan ''e''₂ memenuhi persamaan di atasdiatas, lalumaka ''e''₁ = ''e''₁ • ''e''₂ = ''e''₂.</ref> Untuk alasan ini identitas dianggap sebagai [[Konstanta (matematika) | konstanta]], yaitu Operasioperasi 0-ari (atau nullari). Oleh karena itu, monoid dicirikandiartikan olehsebagai spesifikasi [[Tupelrangkap (matematika)| tiga kali lipatrangkap]] (''S'', • , ''e'').

Bergantung pada konteksnya, simbol untuk operasi biner dapat dihilangkan, sehinggamaka operasi tersebut dilambangkan dengan penjajaran; misalnya, aksioma monoid dapat ditulis sebagai <math>(ab)c = a(bc)</math> dan <math>ea=ae=a</math>. Notasi initersebut tidak menyiratkan bahwa itu adalah angkabilangan yang dikalikan.

Sebuah monoidMonoid setiap elemen memilikimenggunakan [[elemen invers | invers]] adalah [[grup (matematika) | grup]].

'''Submonoid''' dari sebuah monoid {{math | ('' M '', •)}} adalah [[subsethimpunan bagian]] '' N '' ofdari '' M '' yang ditutup di bawahdibawah operasi monoid dan berisi elemen identitas '' e '' dari '' M ''.{{sfn|Jacobson|2009}}<ref>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 ''.</ref> Secara simbolis, '' N '' adalah submonoid dari '' M '' ifjika {{math|''N'' ⊆ ''M''}}, {{math|''x'' • ''y'' ∈ ''N''}} dimana {{math|''x'', ''y'' ∈ ''N''}}, dan {{math|''e'' ∈ ''N''}}. ''N'' dengan demikian monoid di bawahdibawah operasi biner yang diwarisidigunakan dari '' M ''.

Himpunan bagian '' S '' dari '' M '' dikatakan sebagai '''generator''' dari '' M '' jika '' M '' adalah himpunan terkecil yang berisi '' S '' yaitu [[penutupan (matematika) | ditutuppenutupan]] di bawahdibawah operasi monoid, atau setara dengan '' M '' adalah hasil dari penerapan [[operatoroperasi penutupan keuangan]] ke '' S ''. Jika ada generator dari '' M '' yang memiliki kardinalitas terbatashingga, maka '' M '' dikatakan sebagai '''dihasilkan secara terbatashingga'''. Tidak setiap himpunan '' S '' akan menghasilkan monoid, karena struktur yang dihasilkan mungkin tidak memiliki elemen identitas.

Monoid yangdimana operasinyaoperasi [[komutatif]] disebut '''monoid komutatif''' (atau, lebih jarang, '''abelian monoid'''). Monoid komutatif sering kali ditulis secara aditif. Setiap monoid komutatif diberkahi dengan '''aljabar''' [[praorderpreorder]] ing {{math | ≤}}, yang ditentukan dari {{math|''x'' ≤ ''y''}} jika adadan '' z '' makaadalah {{math|1=''x'' + ''z'' = ''y''}}.<ref>{{cite book|first1=Michel |last1=Gondran |first2=Michel |last2=Minoux |title=Graphs, Dioids and Semirings: New Models and Algorithms |year=2008 |location=Dordrecht |publisher=[[Springer-Verlag]] |isbn=978-0-387-75450-5 |zbl=1201.16038 |series=Operations Research/Computer Science Interfaces Series |volume=41 | page=13}}</ref> '''unit-order''' dari monoid komutatif '' M '' adalah elemen '' u '' dari '' M '' sehinggamaka untuk setiap elemen '' x '' dari '' M '', ada '' v '' dalam himpunan yang dihasilkan oleh '' u '' sedemikian rupaadalah {{math|''x'' ≤ ''v''}}. Ini sering digunakan jikaJika '' M '' adalah [[Grup terurut | kerucut positif]] dari [[Kumpulanhimpunan terurut sebagian | orderterurut sebagian]] untul [[grup abelian]] '' G '', dalam hal ini kami mengatakan bahwa '' u '' adalah unit order ''G''.

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

* Dari 16 kemungkinan [[tabel kebenaran#Tabel kebenaran untuk semua operatoroperasi logika biner | operatoroperasi Boolean biner]], masing-masing dari empat yang memiliki identitas dua sisi juga komutatif dan asosiatif dan dengan demikian membuat himpunan {Salahsalah, benar} menjadi monoid komutatif. Di bawahDibawah definisi standar, [[Hubungan logisRelasi logika| AND]] dan [[Biconditional logisberdwisyarat logika| XNOR]] memilikimenggunakan identitas True sedangkan [[Disjungsi eksklusif | XOR]] dan [[Disjungsi logis logika| OR]] memiliki identitas maka ituyang salah. Monoid dari AND dan OR jugauntuk [[idempoten]] sedangkan dari XOR dan XNOR.

== 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''}};

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.

[[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:

di manadimana {{mvar|r}} adalah bilangan realriil, maka {{mvar|f}} adalah homomorfisme gelanggang, karena {{mvar|f}} mempertahankan keduadua penjumlahanpenambahan:

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

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:

Perhatikan bahwa {{math|''f''}} tidak dapat diperpanjang menjadi homomorfisme gelanggang (dari bilangan kompleks ke bilangan realriil), karena tidak mempertahankantermasuk penambahan:

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

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,

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'''.

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.

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.

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.&nbsp;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>

[[Kategori: Struktur aljabar]]

[[Kategori: Teori kategori]]

[[Kategori: Teori semigrup]]