En abstrakta algebro, branĉo de matematiko, monoida estas algebra strukturo kun ununura asocieca operacio kaj neŭtra elemento.
#000001
8 rilato al teorio de kategorioj
#000003
Supozu ke S estas aro kaj • estas iu operacio S × S → S , tiam S kun • estas monoidan se ĝi kontentigas la sekvajn du aksiomojn:
#000004
Por ĉio , b kaj c en S, la ekvacio ( • b
Tie ekzistas elemento e en S tia ke por ĉiu elemento en S, da la ekvacioj e • = • e = holdo.
#000005
Por ĉio , b kaj c en S, la ekvacio ( • b
#000006
Tie ekzistas elemento e en S tia ke por ĉiu elemento en S, da la ekvacioj e • = • e = holdo.
#000007
En aliaj vortoj, monoida estas Duongrupo kun neŭtra elemento.
Ĝi ankaŭ povas esti opiniita de kiel magmo kun asocieco kaj identeco.
La neŭtra elemento de monoida estas unika.
Monoida en kiu ĉiu elemento havas inversan estas grupo.
#000008
Depende de la kunteksto, la siglo de la operacio povas esti preterlasita, tiel ke la operacio estas indikita per apudmeto;
Tiu notacio ne implicas ke ĝi estas nombroj estantaj multobligita.
#000009
Submonoida de monoida ( M
subaro N da M kiu estas fermita sub la monoida operacio kaj enhavas la neŭtran elementon e de M estas.
Simbole, N estas al submonoida de M se N ⊆ M , x • y ∈ N kiam ajn x, y ∈ N , kaj e ∈ N .
N estas tiel al monoida sub la operacio heredita de M.
#000010
Monoida kies operacio estas kommutativa estas vokita al kommutativa monoida (aŭ, malpli ofte, abela monoida).
Kommutativaj monoidoj ofte estas skribitaj aldone.
Ĉiu kommutativa monoida estas dotita kun ĝia algebra premendanta ≤, difinita per x ≤ y ĉu tie ekzistas z tia ke x + z = y .
Ordo-unuo de kommutativa monoida M estas elemento u de M tia ke por iu elemento x el M, tie ekzistas pozitiva entjero n tia ke x -≤ Nuo .
Tio ofte estas uzita en kazo M estas la pozitiva konuso de parte ordigis
abela grupo G, en kiu kazo ni diras ke u estas ordo-unuo de G.
#000012
Monoida por kiu la operacio estas kommutativa por kelkaj, sed ne ĉiuj elementoj estas spuro monoida;
spurmonoidoj ofte okazas en la teorio de samtempa komputado.
#000013
Aparte, ĉiu saltita krado povas esti dotita kun kaj kunveno- kaj kunliga- monoida strukturo.
La neŭtraj elementoj estas la pinto kaj ĝia postaĵo de la krado, respektive.
Estante kradoj, Heyting-algebroj kaj buleaj algebroj estas dotitaj kun tiuj monoidaj strukturoj.
#000015
Tiel, idempotent monoida (foje konata kiel trovaĵ-unue) povas esti formita tuŝante neŭtran elementon e al la maldekstra nul Duongrupo super aro S.
modeligas la leksikografan ordon de sekvenco surbaze de la ordoj de ĝiaj elementoj, kun e reprezentanta egalecon.
#000016
modeligas la leksikografan ordon de sekvenco surbaze de la ordoj de ĝiaj elementoj, kun e reprezentanta egalecon.
#000017
La entjeroj, raciaj nombroj, realaj nombroj aŭ kompleksaj nombroj, kun aldono aŭ multipliko kiel operacio.
La aro de ĉiu n de n matricoj super antaŭfiksita ringo, kun matricaldono aŭ matrica multipliko kiel la operacio.
#000018
En monoida, unu povas difini pozitivajn entjerpotencojn de elemento x:
x ( n tempoj) por n > 1.
La regulo de potencoj x n + p = x n • x p estas evidentaj.
#000019
De la difino de monoida, unu povas montri ke la neŭtra elemento e estas unika.
Tiam, por iu x, oni povas meti x 0 = e kaj la regulo de potencoj daŭre estas vera kun nenegativeksponentoj.
#000020
Estas eble difini inverteblajn elementojn: elemento x estas nomita invertebla ĉu tie ekzistas elemento y tia ke x • y = e kaj y • x = e .
La elemento y estas nomita la inversa de x.
Se y kaj z estas enversoj de x, tiam de asocieco y
zks) y = z ( ksy
Tiel enversoj, se ili ekzistas, estas unikaj.
#000021
Se y estas la inversa de x, oni povas difini negativajn potencojn de x metante x −1 = y kaj al x − n = y
y ( n tempoj) por n > 1.
Kaj la regulo de eksponentoj daŭre estas konfirmita por ĉiu n, p raciaj entjeroj.
Tial la inversa de x estas kutime skribita x −1.
La aro de ĉiuj inverteblaj elementoj en monoida M, kune kun la operacio • , formas grupon.
En tiu signifo, ĉiu monoida enhavas grupon (eventuale nur la sensignifa grupo konsistanta el nur la identeco).
#000022
Tamen, ne ĉiu monoida sidas ene de grupo.
Ekzemple, estas perfekte eble havi monoidan en kiu du elementoj a kaj b ekzistas tia ke • b = tenas eĉ se b estas ne la neŭtra elemento.
Tia monoida ne povas esti enkonstruita en grupo, ĉar en la grupo ni povis plimultiĝi same helpas al la inversa de kaj farus tiu b = e , kio ne estas vera.
havas la nuligposedaĵon (aŭ estas cancelative) ĉu por ĉio , b kaj c en M, • b = • c ĉiam implicas b = c kaj b • = c • ĉiam implicas b = c .
Kommutativa monoida kun la nuligposedaĵo ĉiam povas esti enkonstruita en grupo per la Grothendieck-konstruo.
Tio estas kiel la aldonaĵogrupo de la entjeroj (grupo kun operacio-+) estas konstruita el la aldonaĵo monoida de naturaj nombroj (kommutativa monoida kun operacio-+ kaj nuligposedaĵo).
Tamen, ne-kommutativa cancelative monoida ne devas esti embedabla en grupo.
#000023
Se monoida havas la nuligposedaĵon kaj estas finhava, tiam ĝi estas fakte grupo.
Pruvo: Fiksu elementon x en la monoida.
Ekde la monoida estas finhava, x n = x m por iu m > n > 0.
Sed tiam, per nuligo ni havas tiun x m − n = e kie e estas la identeco.
Tial, x • x m − n − 1 = e , do x havas inversan.
#000024
La dekstro- kaj maldekstra-cancellative-elementoj de monoida ĉiu en victurno formas submonoidan (t.e. evidente inkludas la identecon kaj ne evidente estas fermitaj sub la operacio).
Tio signifas ke la cancelative-elementoj de iu kommutativa monoida povas esti etenditaj al grupo.
#000025
Inversa monoida estas al monoida kie por ĉiu en M, tie ekzistas unika −1 en M tia ke = • −1 • a kaj −1 = −1 • • −1 .
Se inversa monoida estas cancelative, tiam ĝi estas grupo.
#000027
En la kontraŭa direkto, zerosumfre monoida estas aldone skriba monoida en kiu + b = 0 implicas tion = 0 kaj b = 0: [9]
ekvivalente, tiel neniu elemento krom nul havas aldonaĵon inversa.
#000028
Lasu M esti monoidan, kun la operacio indikita per • kaj la neŭtra elemento indikita per e.
Tiam (maldekstre) M-leĝo (aŭ maldekstre agas super M) estas aro X kune kun operacio
M × Xa → X kiu estas kongrua kun la monoida strukturo kiel sekvas:
#000029
Tio estas la analogo en monoida teorio de (forlasita) grupa ago.
Dekstraj M-leĝo estas difinitaj laŭ simila maniero.
Monoida kun ago ankaŭ estas konata kiel funkciigisto monoida .
Gravaj ekzemploj inkludas transirsistemojn de semiautomata.
Transform-Duongrupo povas esti transformita en funkciigiston monoidan per tuŝado de la identectransformo.
#000031
Homomorfism inter du monoidoj ( M
#000032
kie e M kaj e N estas la identecoj sur M kaj N respektive.
Monoidaj homomorfismoj foje estas simple nomitaj monoidaj morfismoj.
#000033
Ne ĉiu Duongrupo homomorfism estas monoida homomorfism, ĉar ĝi eble ne mapas la identecon al la identeco de la celo monoida, eĉ se la elemento kiun ĝi mapas al la identeco supre estos identeco de la bildo de la mapado.
En kontrasto, Duongrupo homomorfism inter grupoj ĉiam estas grupo homomorfism, ĉar ĝi nepre konservas la identecon.
Ĉar por monoidoj tio ne estas ĉiam vera, estas necese deklari tion kiel aparta postulo.
#000034
Bijektive monoida homomorfism estas nomita monoida izomorfio.
Du monoidoj laŭdire estas izomorfaj ĉu ekzistas monoida izomorfio inter ili.
#000035
Al Monoids povas ricevi prezentaĵo, multe en laŭ la saman manieron kiu grupigas povas esti precizigita per grupprezento.
Oni faras tion precizigante aron de generatoroj σ, kaj aron de rilatoj sur la libera monoida σ ∗.
Oni faras tion etendante (finhavajn) duargumentajn rilatojn sur σ ∗ al monoidaj kongruecoj, kaj tiam konstruantaj la kvociento monoida, kiel supra.
#000036
Surbaze de duargumenta rilato R ⊂ σ ∗ × σ ∗ , oni difinas ĝian simetrian finon kiel R ∪ R −1 .
Tio povas esti etendita al simetria rilato E ⊂ σ ∗ × σ ∗ per difina x E y se kaj nur se x = sut kaj y = svt por kelkaj ŝnuroj u, v, s, t ∈ σ ∗ kun ( u, v
Finfine, oni prenas la refleksivan kaj transitivan finon de E, kio tiam estas monoida kongrueco.
#000037
la plaktic monoida de grado 2 estas (ĝi havas senfinan ordon).
#000039
Rilato al teorio de kategorioj
#000040
Monoids povas esti rigardita kiel aparta klaso de kategorioj.
Efektive, la aksiomoj postulitaj de monoida operacio estas samaj tiujn postulitajn de morfismo konsisto kiam limigite al la aro de ĉiuj morfismoj kies fonto kaj celo estas antaŭfiksita objekto.
#000041
Monoida estas, esence, la sama aĵo kiel kategorio kun ununura objekto.
#000042
Pli ĝuste, surbaze de monoida ( M
, oni povas konstrui malgrandan kategorion kun nur unu objekto kaj kies morfismoj estas la elementoj de M.
La kunmetaĵo de morfismoj ricevas per la monoida operacio • .
#000043
Same, monoidaj homomorfismoj estas ĵus funktoroj inter ununuraj objektokategorioj.
Tiel tiu konstruo donas ekvivalentecon inter la kategorio da (malgrandaj) monoidoj al Mon kaj al plena subkategorio de la kategorio da (malgrandaj) kategorioj Cat.
Simile, la kategorio da grupoj estas ekvivalenta al alia plena subkategorio de Cat.
#000044
En tiu signifo, teorio de kategorioj povas esti opiniita de kiel etendaĵo de la koncepto de monoida.
Multaj difinoj kaj teoremoj pri monoidoj povas esti ĝeneraligitaj ĝis malgrandaj kategorioj kun pli ol unu objekto.
Ekzemple, kvociento de kategorio kun unu objekto estas nur kvociento monoida.
#000045
Monoids, ekzakte kiel aliaj algebraj strukturoj, ankaŭ formi sian propran kategorion, Mon, kies objektoj estas monoidoj kaj kies morfismoj estas monoidaj homomorfismoj.
#000046
En komputado, multaj abstraktaj datentipoj povas esti dotitaj kun monoida strukturo.
En ofta padrono, sekvenco de elementoj de monoida estas " faldita " aŭ "akumulita" por produkti finan valoron.
Ekzemple, multaj ripeta algoritmoj-bezono ĝisdatigi iun specon de "aktuala totala" ĉe ĉiu ripeto;
tiu padrono povas esti elegante esprimita per monoida operacio.
Alternative, la asocieco de monoidaj operacioj certigas ke la operacio povas esti paraleligita utiligante prefikson sumo aŭ similan algoritmon, por utiligi multoblajn kernojn aŭ procesorojn efike.
#000048
Krome, ĉiu datenstrukturo povas esti "faldita" laŭ simila maniero, donita seriigon de it'oj elementoj.
Ekzemple, la rezulto de "faldado" duuma arbo eble malsamos depende de antaŭ-ordo vs. post-orda arbotraversal.
#000049
Apliko de monoidoj en komputado estas tielnomita MapReduce programanta modelon (vidu Encoding Map-Reduce As A Monoid With Left Folding (Ĉifrante Map-Reduce As A Monoid With Left Folding).
MapReduce, en komputiko, konsistas el du aŭ tri operacioj.
Surbaze de datenserio, "Mapo" konsistas el mapaj arbitraj datenoj al elementoj de specifa monoida.
"Redukti" konsistas el faldado de tiuj elementoj, tiel ke en la fino ni produktas nur unu elementon.
#000050
Ekzemple, se ni havas Multaron, en programo ĝi estas reprezentita kiel mapo de elementoj ĝis iliaj numeroj.
Elementoj estas nomitaj ŝlosiloj en tiu kazo.
La nombro da apartaj ŝlosiloj povas esti tro granda, kaj en tiu kazo la Multaro estas shardeita.
Por finpretigi redukton konvene, la Shuffling-scenejo regrupigas la datenojn inter la nodoj.
Se ni ne bezonas tiun paŝon, la tutan Mapon/Reduktas konsistas el mapado kaj malgrasigo;
ambaŭ operacio estas paralelizabla, la unua pro sia element-rilata naturo, ĉi-lasta pro asocieco de la monoida.
#000051
Kontinua monoida estas ordigita kommutativa monoida en kiu ĉiu direktis aron havas malplej supra ligitan kongrua kun la monoida operacio:
#000052
Tiuj du konceptoj estas proksime rilatitaj: kontinua monoida estas al kompleta monoida en kiel kiu la infinitary-sumo povas esti difinita
#000053
kie la Preciza supra rando dekstraflanke kontraŭveturas ĉiujn ne-senlimajn subarojn E de mi kaj ĉiu sumo dekstraflanke estas finhava sumo en la monoida.
#000054
Monoido aŭ Monojdo en algebro estas strukturo simila al duongrupo, formata de aro kiu enhavas neŭtran elementon kaj asociecan operacion:
#000058
Kutime oni skribas (A, *, e) por intencii duongrupo kun neŭtra elemneto e kaj kun *, kiu estas asocieca operacio.
#000059