Informatyka MIMUW

Definicje, oznaczenia i podstawowe własności

---

Przyjmijmy, że $\mathbb{N}=\left\{ 1,2,\ldots \right\}$ oznacza zbiór liczb naturalnych, a $\mathbb{N}_{0}$ zbiór liczb naturalnych wraz z 0. Przypomnimy teraz podstawowe wiadomości z wykładu Algebra Liniowa dotyczące struktur algebraicznych, a dokładniej struktur najprostszych, półgrup i monoidów, posiadających jedno tylko działanie.

Definicja 1.1

Zbiór $S$, w którym określone jest działanie łączne, to znaczy spełniające warunek

$\forall x,y,z \in S \;\;\; x\cdot (y\cdot z)=(x\cdot y)\cdot z$

nazywamy półgrupą.

Przykład 1.1

Zbiór liczb naturalnych z dodawaniem $(\mathbb{N},+)$ tworzy półgrupę.

Definicja 1.2

Półgrupę $M$, w której istnieje element neutralny działania, to znaczy element $1_{M}\in M$ spełniający warunek

$\forall x\in M \;\;\;1_M \cdot x=x\cdot 1_M=x$

nazywamy monoidem.

Przykład 1.2

(1) Zbiór liczb naturalnych z mnożeniem $(\mathbb{N},\cdot ,1)$ jest monoidem.

(2) Zbiór liczb naturalnych z zerem $(\mathbb{N}_{0},+,0)$ jest monoidem ze względu na dodawanie.

(3) Monoidem jest $(A^A,\circ,id_A)$ - zbiór odwzorowań dowolnego zbioru ${A}$ w siebie ze składaniem jako działaniem i identycznością jako elementem neutralnym.

Dwa pierwsze monoidy są przemienne, czyli działanie jest przemienne, a trzeci jest nieprzemienny.

Każdy monoid jest półgrupą.

Dla uproszczenia notacji będziemy opuszczać kropkę "$\cdot$" oznaczającą działanie oraz używać nazwy "jedynka" na element neutralny. Jeśli nie będzie zaznaczone inaczej, to $(\mathbf{S},\cdot )$ będzie oznaczać półgrupę, a $(\mathbf{M},\cdot ,\, 1_{\mathbf{M}})$ monoid. Ze względu na łączność działania zarówno w półgrupie, jak i w monoidzie iloczyn $x_1...x_n,$ a także $x^n=x...x$ (n razy) jest określony jednoznacznie bez potrzeby wprowadzania nawiasów. Dla dowolnych liczb naturalnych $m,n\in \mathbb{N}$ zachodzą wzory

$\begin{array} {c} x^{m+n}=x^{m}x^{n}=x^{n}x^{m},\\ (x^{m})^{n}=x^{mn}. \end{array}$

Dla dowolnego $x \in M$ przyjmujemy z definicji

$x^0 = 1_{M}.$

Strukturę monoidu $M$ przenosimy na zbiór potęgowy $\mathcal{P}(M)$ wszystkich podzbiorów monoidu $M$, określając dla dowolnych $A,B \in\mathcal{P}(M)$ działanie

$A\cdot B=\left\{ x\in {\bf M}\: :\: \exists a\in A,\: \exists b\in B\: ,\: x=ab\right\}$

$(\mathcal{P}(M),\cdot, \{1_{M}\})$ jest monoidem.
Podobnie przenosimy strukturę półgrupy z $S$ na $\mathcal{P}(S)$.
Dla dowolnego podzbioru monoidu (półgrupy) i dla dowolnej liczby $n \in \mathbb{N}$ zapis $A^n$ oznacza n-krotny iloczyn zbioru ${A}$ przez siebie rozumiany w powyższym sensie.
W szczególności $A^{1}=A.$

W przypadku monoidu przyjmujemy z definicji

$A^0 = \{ 1_{ M} \}.$

Definicja 1.3

Homomorfizmem półgrup $(S,\cdot)\;,\;\;(S',*)$ nazywamy odwzorowanie

$h~:S~\longmapsto~S'$ takie, że

$\forall x,y \in S \;\;\; h(x\cdot y)=h(x)*h(y).$

Homomorfizmem monoidów $(M,\cdot,1_{M}),\;(M',*,1_{M'})$ nazywamy odwzorowanie $h:M \longmapsto M'$

takie, że

$\forall x,y \in {M} \;\;\;h(x\cdot y)=h(x)*h(y) \;\;\; i \;\;\; h(1_{M})= 1_{M'}.$

Przykład 1.3

Odwzorowanie $h:{\mathbb{Z}}_{mod\, 3}\longrightarrow {\mathbb{Z}}_{mod\,6}$ takie, że

$\begin{array} {c} \begin{array} {l} 1\longrightarrow 4\\ 0\longrightarrow 0\\ 2\longrightarrow 2 \end{array} \end{array}$

jest homomorfizmem półgrupy $(\mathbb{Z}_{mod\,3},\cdot )$ w półgrupę $(\mathbb{Z}_{mod\,6},\cdot )$, ale nie jest homomorfizmem monoidu $(\mathbb{Z}_{mod\,3},\cdot,1 )$ w monoid $(\mathbb{Z}_{mod\,6},\cdot,1 )$, bo wartością 1 z monoidu $(\mathbb{Z}_{mod\,3},\cdot, 1 )$ nie jest jedynka monoidu $(\mathbb{Z}_{mod\,6},\cdot,1 )$.

Definicja 1.4.

Niech $(S,\cdot),\;\;(M,\cdot,1_{M})$ będą odpowiednio dowolną półgrupą, monoidem.

• $(T,\cdot)$ nazywamy podpółgrupą ${S}$ wtedy i tylko wtedy, gdy $T\subset S$ i $T^2 \subset T.$

• $(N,\cdot,1_{M})$ nazywamy podmonoidem $M$ wtedy i tylko wtedy, gdy $N$ jest podpółgrupą $M$ i $1_{M} \in N.$

Przykład 1.4.

$(\mathbb{Z}_{mod\,6},\cdot )$ jest monoidem. Podzbiór $\{2,4\}$, jako zamknięty na działanie $\cdot _{mod\, 6}$, tworzy podpółgrupę $\mathbb{Z}_{mod\, 6}$. $(\{2,4\},\cdot _{mod\, 6})$ jest monoidem z $4$ jako elementem neutralnym, ale nie podmonoidem $\mathbb{Z}_{mod\, 6}$.

Niech $X$ będzie dowolnym podzbiorem monoidu $M$. Zbiór

$X^*= \{1\}\cup X\cup X^2\cup ...\cup X^n \cup \ldots = \bigcup_{i=0}^\infty X^i$

jest podmonoidem monoidu $M$. Jest to najmniejszy, w sensie inkluzji podmonoid monoidu $M$ zawierający zbiór $X$. Gdy spełniona jest równość $X^*={M}$, to mówimy, że $X$ jest zbiorem generatorów monoidu $M$. Zachodzą następujące własności:

1. Zbiór generatorów nie jest wyznaczony jednoznacznie.

2. Dla dowolnego monoidu istnieje zbiór generatorów, jest nim w szczególności zbiór ${M}$.

Podobnie dla dowolnego podzbioru $X$ półgrupy ${S}$ zbiór

$X^+=X\cup X^2\cup...\cup X^n \cup \ldots = \bigcup_{i=1}^\infty X^i$

jest podpółgrupą ${S}$ i to najmniejszą w sensie inkluzji zawierającą zbiór $X$.
Powyższe uwagi dotyczące zbioru generatorów monoidów przenoszą się odpowiednio dla półgrup.

Przykład 1.5.

W monoidzie $(\mathbb{N}_{0},+,0)$ podmonoid generowany przez zbiór generatorów $X=\{2\}$ składa się z liczb parzystych i nieujemnych.

Definicja 1.5

Niech $S$ będzie półgrupą. Relację równoważności $\rho \subset {S}^2$ nazywamy:

(1) prawą kongruencją w półgrupie ${S}$, jeśli

$\forall x,y,z \in {S} \;\;\; x\;\rho\; y \Rightarrow xz\;\rho\; yz,$

(2) lewą kongruencją w półgrupie ${S}$, jeśli

$\forall x,y,z \in {S} \;\;\; x\;\rho\; y \Rightarrow zx\;\rho\; zy,$

(3) kongruencją, jeśli jest prawą i lewą kongruencją, tzn.

$\forall x,y,z \in {S} \;\;\; x\;\rho\; y \Rightarrow zx\;\rho\; zy \;\; i \;\; xz\;\rho\; yz.$

Zastępując w powyższej definicji półgrupę $S$ na monoid $M$ otrzymamy dualnie pojęcia prawej kongruencji, lewej kongruencji i kongruencji zdefiniowane w monoidzie.
Mając kongruencję $\rho$ określoną w półgrupie ${S}$ (monoidzie $M)$ możemy utworzyć półgrupę ilorazową ${S}/\rho$ (monoid ilorazowy ${M}/\rho$), której elementami są klasy równoważności (abstrakcji) relacji $\rho$.

Dla dowolnego homomorfizmu półgrup $h:{S}\longmapsto {S}'$ określamy relację

$Ker_h = \{ (x,y)\in {S}\times {S}\;:\;\; h(x)=h(y) \}.$
Relacja $Ker_h$ jest kongruencją w półgrupie ${S}.$

Dla homomorfizmu monoidów $h:{M}\longmapsto {M}'$ relacja $Ker_h$ jest kongruencją w monoidzie $M$.

Podstawowe twierdzenie o epimorfizmie dla struktur algebraicznych przyjmuje dla półgrup i odpowiednio dla monoidów następującą postać.

Twierdzenie 1.1

Niech $h:{S}\longmapsto {S}'$ będzie dowolnym epimorfizmem półgrupy ${S}$ na półgrupę ${S}'.$ Półgrupa ${S}'$ jest izomorficzna z półgrupą ilorazową ${S}/_{Ker_h}$.

Rysunek 1

Twierdzenie 1.2

Niech $h:{M}\longmapsto {M}'$ będzie dowolnym epimorfizmem monoidu ${M}$ na monoid ${M}'.$ Monoid ${M}'$ jest izomorficzny z monoidem ilorazowym ${M}/_{Ker_h}$.

Rysunek 2

Półgrupy wolne i monoidy wolne

Niech ${A}$ oznacza dowolny zbiór.

Definicja 2.1

Wolnym monoidem $A^*$ o bazie ${A}$ nazywamy zbiór wszystkich skończonych ciągów:

$A^*=\{ (a_1,...,a_n)\;\;:\;\;n \geq 0\;\;,\;\;a_i \in A \}$ wraz z działaniem $(a_1,...,a_n)\cdot (b_1,...,b_m) = (a_1,...,a_n,b_1,...,b_m).$

Ciąg pusty ${(n=0)}$ oznaczamy symbolem "1" i z definicji jest on elementem neutralnym określonego powyżej działania, nazywanego katenacją lub konkatenacją.

Przyjmujemy następującą konwencję zapisu: W oparciu o nią możemy stwierdzić inkluzję $A\subset A^*$.

Ta inkluzja uzasadnia użycie wprowadzonego wcześniej oznaczenia $A^*$.
$A^*$ jest najmniejszym podmonoidem monoidu $A^*$ zawierającym $A.$

Definicja 2.2

Wolną półgrupą $A^+$ nad alfabetem $A$ nazywamy zbiór wszystkich skończonych ciągów:

$A^+=\{ (a_1,...,a_n)\;\;:\;\;n > 0,\;\;\;a_i \in A \}$

wraz z działaniem katenacji.

Używa się także określeń - wolny monoid o bazie $A$ i wolna półgrupa o bazie $A$.

• Elementy alfabetu ${A}$ nazywamy literami.

• Elementy wolnego monoidu (półgrupy) nazywamy słowami i oznaczać bedziemy w wykładzie najczęściej literami $u,v,w$.

• Dowolny podzbiór wolnego monoidu (półgrupy) nazywamy językiem.

Długością słowa $w \in A^*$ nazywamy liczbę $|w|$ będącą długością ciągu określającego to słowo. Słowo puste 1, czyli odpowiadające ciągowi pustemu ma długość równą 0.

Przykład 2.1

(1) Wolna półgrupa $\{0,1\}^+$ składa się z ciągów binarnych.

(2) Wolny monoid $\{0,1\}^*$ składa się z ciągów binarnych i ciągu pustego.

Definicja 2.3

Niech $A$ i $B$ będą alfabetami. Podstawieniem nazywamy homomorfizm

$s:A^{*}\longrightarrow \mathcal{P}(B^{*}).$ Odwzorowanie $s$ jako homomorfizm monoidu $A^{*}$ w monoid $\mathcal{P}(B^{*})$ spełnia dla dowolnych $v,w\in A^{*}$ równość $s(vw)=s(v)s(w) \;\; \text{oraz}\;\; s(1)=\{1\}.$

Twierdzenie 2.1.

Niech ${A}$ oznacza dowolny zbiór, a $({M},\cdot,1_{M})$ dowolny monoid.

(1) Każde odwzorowanie

$f:A\longmapsto {M}$

daje się jednoznacznie rozszerzyć do homomorfizmu $h:A^*\longmapsto {M}.$

(2) Homomorfizm ${h}$ jest epimorfizmem wtedy i tylko wtedy, gdy $f(A)$ jest zbiorem generatorów ${M}.$

Dowód

(1) Przyjmujemy

$\forall\; a_1...a_n \in A^+\;\;\;\;h(a_1...a_n)=f(a_1)...f(a_n) \;\;\;\text{oraz}\; \;\;h(1)=1_{M}.$

Tak określone $h$ jest jedynym rozszerzeniem przekształcenia $f$.

(2) $f(A)^*=M \Leftrightarrow \forall s \in {M}\;\; s=f(a_1)...f(a_n)=h(a_1...a_n)$ dla pewnego $a_1...a_n \in A^*\Leftrightarrow h$ jest suriekcją.

Przyjmując w powyższym twierdzeniu jako $A$ dowolny zbiór generatorów monoidu ${M}$ oraz jako funkcję $f$ włożenie $id_{A}:A\longrightarrow \mathbf{M}$ równe identyczności na ${A}$ dochodzimy do następującego wniosku.

Wniosek 2.1.

Każdy monoid ${M}$ jest homomorficznym obrazem wolnego monoidu $A^*$ utworzonego nad dowolnym zbiorem generatorów ${M}.$

Udowodnione powyżej twierdzenie oraz sformułowany wniosek prawdziwy jest również dla półgrup.
Powyższe rezultaty określają rolę wolnych monoidów (półgrup) w klasie wszystkich monoidów (półgrup).

Twierdzenie 2.2.

Monoid ${M}$ jest wolny wtedy i tylko wtedy, gdy każdy element $m \in {S}={M}\setminus \{1\}$ ma jednoznaczny rozkład na elementy zbioru $A={S}\setminus {S}^2.$

Dowod

Załóżmy, że monoid ${M}$ jest wolny, to znaczy ${M}=B^*$ dla pewnego zbioru (bazy) $B.$

• Udowodnimy, że $A{}$ jest zbiorem generatorów monoidu $M$. W tym celu wykażemy, że zachodzi inkluzja
  ${S}\subset ({S}\setminus {S}^2)^+.$
  Dowód przeprowadzimy nie wprost. Załóżmy więc, że

${S}\setminus ({S}\setminus {S}^2)^+ \neq \emptyset$

i niech ${m}$ oznacza element z tego zbioru o najmniejszej długości w $B^*.$
Wnioskujemy stąd kolejno:

$m\notin ({S}\setminus {S}^2)^+$
$m\in {S}^2$
$m=s_1s_2$ dla pewnych $s_1,s_2\in {S}$,

przy czym długość $s_1,s_2$ jest silnie mniejsza niż długość $m.$ Zatem

$s_1,s_2 \in ({S}\setminus {S}^2)^+$

a to oznacza, że

$m=s_1s_2 \in ({S}\setminus {S}^2)^+.$

Otrzymana sprzeczność kończy dowód faktu, że $A={S}\setminus {S}^2$ jest zbiorem generatorów monoidu ${M}.$

• Pokażemy teraz, że $A \subset B.$
  Niech $m=b_1...b_k \in {S}\setminus {S}^2$ dla pewnych $b_i \in B$, $i=1,...,k.$
  Jeśli $k>1$, to $m\in {S}^2$, co jest sprzeczne z wyborem $m.$ Zatem ${k=1}$, co implikuje $A\subset B.$

Z definicji wolnego monoidu wynika jednoznaczność rozkładu na elementy z bazy $B$, a to pociąga za sobą jednoznaczność rozkładu na elementy z podzbioru $A={S}\setminus {S}^2.$

Niech teraz ${M}$ oznacza monoid z jednoznacznością rozkładu na elementy zbioru $A~=~S~\setminus~S^2$. Rozszerzamy identyczność $id_A:A\longmapsto {M}$ do homomorfizmu $h:A^*\longmapsto {M}.$ Z założenia wynika, że każdy element $m \in {S}$ można przedstawić jako iloczyn

$m=a_1...a_n \;\;\; gdzie \;\;\;a_i \in A \;\;\; dla \;\;\; i=1,...,n.$

Zatem

$h(a_1...a_n)=h(a_1)...h(a_n) a_1...a_n.$

Homomorfizm $h$ jest izomorfizmem, więc monoid ${M}$ jako izomorficzny z $A^*$ jest wolny.

Powyższe twierdzenie posiada swój odpowiednik dla wolnych półgrup.

Twierdzenie 2.3.

Półgrupa ${S}$ jest wolna wtedy i tylko wtedy, gdy każdy element $x \in {S}$ ma jednoznaczny rozkład na elementy zbioru ${S}\setminus {S}^2.$

Wniosek 2.2.

Baza wolnego monoidu (półgrupy) jest minimalym zbiorem generatorów.

Przyklad 2.2.

(1) Półgrupa $(\mathbb{N},+ )$ jest wolna. Każdy jej element można jednoznacznie zapisać jako sumę jedynek - $\mathbb{N}\setminus (\mathbb{N}+\mathbb{N})=\left\{ 1\right\}$.

(2) Dla $\mathbb{N}_2=\{n \in \mathbb{N}:n\geq 2\}$ półgrupa $(\mathbb{N}_2,+ )$ nie jest to półgrupą wolną.
Nie ma jednoznaczności rozkładu na elementy z $\mathbb{N}_2\setminus (\mathbb{N}_2+\mathbb{N}_2)=\{2,3\}$.
Na przykład $6=2+2+2=3+3$.