Monoid

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Monoid[1] - półgrupa, której działanie ma element neutralny. Formalnie, monoid to algebra (S, e, *), sygnatury  (0, 2), gdzie S jest niepustym zbiorem, natomiast

*\colon S \times S \to S

jest działaniem dwuargumentowym, spełniającym warunki:

  1. \forall_{a \in S}\; e *a = a *e = a       (e jest elementem neutralnym),
  2. \forall_{a, b, c \in S}\; \left(a * b\right) * c = a *\left(b * c\right)       (działanie jest łączne).

Szczególny przypadek monoidu stanowi grupa. Wynika stąd następujące zawieranie:

klasa półgrup ⊇ klasa monoidów ⊇ klasa grup.

Każdy monoid M jest izomorficzny z półgrupą wszystkich endomorfizmów pewnej algebry M. Jest to uogólnienie twierdzenia Cayley'a.

Przykłady[edytuj | edytuj kod]

  • Liczby naturalne (koniecznie z zerem) z działaniem dodawania: elementem neutralnym jest w tym przypadku zero.
  • Liczby naturalne (z zerem bądź bez) z działaniem mnożenia: elementem neutralnym tego monoidu jest 1 (w obu przykładach).
  • Każdej półgrupie (S, *) można przyporządkować jej monoid M(S) w następujący sposób[2]:
Jeśli S ma element neutralny e, to monoidem tym jest M(S) = (S, e, *),
Jeśli S nie ma elementu neutralnego, to monoidem tym jest M(S) = (S \cup \{1\}, 1, \circ), gdzie:
1 \not\in S
dla wszystkich x, y \in S x \circ y = x * y,
dla każdego x \in S spełniona jest równość x \circ 1 = 1 \circ x,
1 \circ 1 = 1.
  • Monoid wolny[3].  \left(X^*, \varepsilon, \sim\right) - zbiór słów nad alfabetem \,X\,, z \varepsilon jako słowem pustym i \,\sim\, jako operacją konkatenacji. Jeśli X \,=\, \{0, 1\}, to słowami są na przykład: 110111,\,011000,\,000,\, 1111, a przykładami konkatenacji są:


110111\,\sim\,000\,=\, 110111000,
\varepsilon\,\sim\,000\,=\,000.
  • Własność uniwersalności monoidu wolnego[4]. Po utożsamieniu elementów zbioru X ze słowami jednoelementowymi można uznać X za podzbiór monoidu wolnego X*
Uniwersalność monoidu wolnego
i: a \mapsto a,
przy czym podzbiór ten generuje X* i odwzorowanie
i: X \rightarrow X^*
ma następującą własność uniwersalności: dla dowolnego odwzorowania zbioru X w monoid M
\alpha: X \rightarrow M
istnieje jedyny taki homomorfizm
 \alpha^* : X^* \rightarrow {M}
dla którego następujący diagram jest przemienny.
  • Zbiór wszystkich odwzorowań dowolnego zbioru M w zbiór M wraz z działaniem składania odwzorowań tworzy monoid. Jedynką jest w nim odwzorowanie identycznościowe na M. Półgrupę tę nazywa się często pełną półgrupą przekształceń lub półgrupą symetryczną.
  • Jeśli \,\mathit{M}\, jest monoidem, \,\mathit{A}\, jest półgrupą, a h: \mathit{M} \rightarrow \mathit{A} jest homomorfizmem na \,\mathit{A}\,, to \,\mathit{A}\, jest monoidem[5].

Przypisy

  1. Milne J. S.: [www.jmilne.org Group Theory]. s.31. [dostęp 2011-08-23].
  2. Gerard Lallement: Semigroups and Combinatorial Applications (tłum. ros.). Wyd. 1. Mиp, 1985, s. 16. (ros.)
  3. Milne, op. cit., s. 31
  4. Milne, op. cit., s. 32
  5. Скорняков, op. cit., s. 60

Bibliografia[edytuj | edytuj kod]

  1. A. H. Clifford, G. B. Preston: The algebraic theory of semigroups. Wyd. 1. American Mathematical Society, 1964.
  2. Milne J. S.: [www.jmilne.org Group Theory]. [dostęp 2011-08-23].
  3. Скорняков Л. А.: Элементы алгебры. Москва: Наука, 1986.