Monoid
Grupam podobne strukture | |||||
---|---|---|---|---|---|
Zaprtaα | Asociativnost | Identiteta | Invertibilnost | Komutativnost | |
Polgrupoid | Nepotrebno | Zahtevano | Nepotrebno | Nepotrebno | Nepotrebno |
Mala kategorija | Nepotrebno | Zahtevano | Zahtevano | Nepotrebno | Nepotrebno |
Grupoid | Nepotrebno | Zahtevano | Zahtevano | Zahtevano | Nepotrebno |
Magma | Zahtevano | Nepotrebno | Nepotrebno | Nepotrebno | Nepotrebno |
Kvazigrupa | Zahtevano | Nepotrebno | Nepotrebno | Zahtevano | Nepotrebno |
Enotska magma | Zahtevano | Nepotrebno | Zahtevano | Nepotrebno | Nepotrebno |
Zanka | Zahtevano | Nepotrebno | Zahtevano | Zahtevano | Nepotrebno |
Polgrupa | Zahtevano | Zahtevano | Nepotrebno | Nepotrebno | Nepotrebno |
Inverzna polgrupa | Zahtevano | Zahtevano | Nepotrebno | Zahtevano | Nepotrebno |
Monoid | Zahtevano | Zahtevano | Zahtevano | Nepotrebno | Nepotrebno |
Komutativni monoid | Zahtevano | Zahtevano | Zahtevano | Nepotrebno | Zahtevano |
Grupa | Zahtevano | Zahtevano | Zahtevano | Zahtevano | Nepotrebno |
Abelova grupa | Zahtevano | Zahtevano | Zahtevano | Zahtevano | Zahtevano |
^α Zaprtost, ki se uporablja v veliko virih, je ekvivalentni aksiom kot popolnost, četudi je definiran drugače. |
Mónoid M = {a, b, ...} je v matematiki par (M, *), kjer je M neprazna množica in * asociativna dvočlena operacija na M, ki zadošča pogojem:
- Za vsak a, b M, velja a * b M. (Zakon o zaprtosti).
- Za vsak a, b in c M, velja (a * b) * c = a * (b * c) (Zakon o združevanju faktorjev (Zakon o asociativnosti)).
- V M obstaja takšen element e, za katerega za vsak a M velja e * a = a * e = a (Zakon o nevtralnem elementu (identiteti)).
Drugače povedano, monoid je polgrupa z nevtralnim elementom (identiteto).
Zgledi monoidov
[uredi | uredi kodo]- Katerakoli grupa.
- Elementi vsakega enotskega kolobarja z operacijo množenja.
- Množice celih števil Z, naravnih števil N ali kompleksnih števil C z operacijo množenja.
- Množica vseh n × n matrik z matričnim množenjem.
- Množice naravnih števil N z operacijo seštevanja.
- Množica končnih znakovnih nizov, s praznim znakovnim nizom ε ≡ "" čez poljubno določeno abecedo Σ z operacijo spojitve znakovnega niza. V teoretičnem računalništvu je takšen monoid označen z Σ*, v matematiki pa se imenuje »prosti monoid čez Σ«.
- Na primer prosti idempotentni monoidi za abecedo Σ z n črkami so {1, 2, 7, 160, 332381, 2751884514766, 272622932796281408879065987, 3641839910835401567626683593436003894250931310990279692, ...} (OEIS A005345). Splošni člen takšnih monoidov je:
- a(n) = Σ C(n,k) Π (k-i 1)2^i, (pri i = 1 ... k in k = 0 ... n).
- Če izberemo poljuben objekt kategorije in imamo množico vseh morfizmov teh objektov vase z operacijo sestave (kompozicije) (glej teorijo kategorije). Primeri iz dobro znanih kategorij so:
- Množica vseh zveznih enotnih kart topološkega prostora z operacijo sestave (kompozicije).
- Množica vseh endomorfizmov določene grupe z operacijo sestave (kompozicije).
- Množica vseh funkcij iz množice nanjo z operacijo sestave (kompozicije).
Neposredno iz določitve lahko pokažemo, da je nevtralni element e edin. Potem lahko določimo obrnljive elemente: element x se imenuje obrnljiv, če obstaja tak&šen element y, za katerega velja x * y = e in y * x = e. Pokaže se, da množica vseh obrnljivih elementov z operacijo * tvori grupo. V tem smislu vsak monoid vsebuje grupo.
Vsakega monoida pa ne moremo imeti za grupo. Lahko imamo, na primer, monoid v katerem obstajata tak&šna elementa a in b, za katera vela a * b = a, pa čeprav b ni nevtralni element. Takšnega monoida ne moremo vložiti v grupo, ker v grupi lahko množimo obe strani z obratnim elementom a in bi dobili b = e, kar pa ne drži. Monoid (M, *) ima lastnost razveljavitve (oziroma je razveljaviten), če za vse a, b in c M iz a * b = a * c vedno sledi b = c in iz b * a = c * a prav tako vedno sledi b = c. Komutativni monoid, ki je razveljaviten lahko vedno vložimo v grupo. Tako cela števila (grupa z operacijo ) pridelamo iz naravnih števil (komutativen monoid z operacijo in lastnostjo razveljavitve). Nekomutativen razveljaviten monoid pa ni vložljiv v grupo.
Če je monoid razveljaviten in je končen, je v bistvu grupa.
Na kategorije lahko gledamo kot na posplošitve monoidov. Sestava (kompozicija) morfizma v kategoriji ima enake lastnosti kot monoid s tem, da vseh parov morfizmov ne moremo sestaviti. Tudi za kategorije lahko dokažemo veliko definicij in izrekov o monoidih.