90

KAPITEL III Algebraische Grundstrukturen

1. Halbgruppen, Monoide und Gruppen

Wir haben in den ersten beiden Kapiteln gewisse Gesetze kennengelernt, wie etwa das Assoziativgesetz oder das Kommutativgesetz, die bei so unterschiedlichen Strukturen, wie der Mengenalgebra oder der Addition bzw. Multiplikation von Zahlen eine Rolle spielen. In diesem Kapitel werden die allgemeinen Eigenschaften solcher Gesetze studiert. Wir werden sehen, daß diese Gesetze in sehr vielen mathematischen Objekten auftreten und daß sie auch bei Strukturen, die für die Informatik wichtig sind, eine ganz wesentliche Rolle spielen.

Definition 1.1. Sei G eine Menge. Eine (binäre) Operation oder Verknüpfung in G ist eine Abbildung γ : G × G ⟶ G. Das Bild γ((a, b)) eines Paares (a, b) ∈ G × G wird je nach Kontext bezeichnet mit

a · b, a + b, ab, a ∩ b, a ∪ b, a − b,

d.h. statt des vorangestellten Funktionszeichens (Präfixnotation oder umgekehrte polnische Notation) γ((a, b)) oder einfach γ(a, b) verwendet man gewöhnlich ein zwischen die zwei Argumente a und b gestelltes Funktionszeichen (Infixnotation). Ein nachgestelltes Funktionszeichen, z.B. ab+, wird auch Postfixnotation oder polnische Notation genannt.

Definition 1.2. Sei ∘ : G × G ∋ (a, b) ↦ a ∘ b ∈ G eine Operation. Für die Operation gilt das

(1) Assoziativgesetz: ⟺ ∀a, b, c ∈ G[(a ∘ b) ∘ c = a ∘ (b ∘ c)]. (2_{l}) Gesetz vom linksneutralen Element :⟺ ∃e_{l} ∈ G∀a ∈

G[e_{l} ∘ a = a]; (2_{r}) Gesetz vom rechtsneutralen Element :⟺ ∃e_{r} ∈ G∀a ∈

G[a ∘ e_{r} = a]; (3_{l}) Gesetz vom linksinversen Element (falls ein linksneutrales

Element e_{l} existiert): ⟺ ∀a ∈ G∃a′ ∈ G[a′ ∘ a = e_{l}]; (3_{r}) Gesetz vom rechtsinversen Element (falls ein rechtsneu-

trales Element e_{r} existiert): ⟺ ∀a ∈ G∃a′′ ∈ G[a ∘ a′′ = e_{r}];

(4) Kommutativgesetz: ⟺ ∀a, b ∈ G[a ∘ b = b ∘ a].

Übung: Formulieren Sie das Assoziativgesetz in Postfixnotation. Warum werden dabei keine Klammern benötigt?

Das Assoziativgesetz kann natürlich auch bei mehr als drei Faktoren eingesetzt werden und gestattet auch dann beliebiges Umklammern. Das kann auch formal bewiesen werden. Man kann daher bei der Produktbildung die Klammern völlig fortlassen.

Definition 1.3. Eine Menge G zusammen mit einer Operation γ : G × G ⟶ G heißt

(1) Halbgruppe: ⟺ (1) gilt;

(2) Monoid : ⟺ (1), (2_{l}) und (2_{r}) gelten;

(3) Gruppe: ⟺ (1), (2_{l}), (2_{r}), (3_{l}) und (3_{r}) gelten;

(4) kommutative oder abelsche Gruppe : ⟺ (1), (2), (3) und (4) gelten.

Beispiele 1.4. a) (ℕ, +) ist eine Halbgruppe, aber kein Monoid.

b) (ℕ, ·) ist ein Monoid, aber keine Gruppe. c) Die Menge G := Abb(M, M) der Abbildungen von M in sich zusammen mit der Komposition ∘ von Abbildungen ist ein Monoid, aber keine Gruppe.

d) Die Menge der bijektiven Abbildungen f : {1, …, n} ⟶ {1, …, n} wird mit der Komposition ∘ von Abbildungen wegen I. 2.22 eine Gruppe S_{n}, die sogenannte symmetrische Gruppe oder Permutationsgruppe.

e) (ℤ, +) ist eine kommutative Gruppe.

f) ℝ^{×} := ℝ \ {0} zusammen mit der Multiplikation ist eine kommutative Gruppe.

g) ℝ zusammen mit der Multiplikation ist ein Monoid, aber keine Gruppe.

h) Die Potenzmenge P(M) einer Menge M zusammen mit dem Durchschnitt ∩ ist ein Monoid, aber keine Gruppe.

i) Wenn G und H Halbgruppen (Monoide, Gruppen) sind, dann ist auch G × H eine Halbgruppe (ein Monoid, eine Gruppe) mit der ”komponentenweisen“ Multiplikation (g, h) · (g′, h′) = (gg′, hh′). Im Falle von Monoiden ist dann (e_{G}, e_{H}) das neutrale Element. Im Falle von Gruppen ist (g^{−1}, h^{−1}) das inverse Element von (g, h).

j) Bei Halbgruppen (Monoiden, Gruppen) mit nur endlich vielen Elementen kann man die Verknüpfung auch in Form einer Tabelle, genannt Verknüfungstafel oder Multiplikationstafel angeben. Das folgende ist ein Beispiel für eine Multiplikationstafel einer Gruppe G = {e, a, b} mit drei Elementen:

e a b e e a b a a b e b b e a

Übung: Man zeige, daß für eine Halbgruppe (Monoid, Gruppe) G und eine Menge I auch die Menge Abb(I, G) = ∏_{I} G = G^{I} mit der ”komponentenweisen“ Multiplikation eine Halbgruppe (Monoid, Gruppe) bildet.

Bemerkung 1.5. In einem Monoid gibt es nur ein linksneutrales Element e_{l} und ein rechtsneutrales Element e_{r} und diese sind gleich. Es ist nämlich e_{l} = e_{l}∘e_{r} = e_{r}. Wir sprechen dann einfach vom neutralen Element. Wenn in einer Halbgruppe die Gesetze (b_{l}) und (c_{l}) erfüllt sind, so sind auch (b_{r}) und (c_{r}) erfüllt und die Links- und Rechtsinversen a′ bzw. a′′ eines Elements a sind eindeutig bestimmt und stimmen überein. Sei nämlich a′a = e_{l} und ãa′ = e_{l}, dann ist aa′ = e_{l}(aa′) = (ãa′)(aa′) = ã((a′a)a′) = ã(e_{l}a′) = ãa′ = e_{l}. Weiter ist ae_{l} = a(a′a) = (aa′)a = e_{l}a = a. Also ist e_{l} auch rechtsneutrales Element und a′ auch Rechtsinverses von a. Ist a′a = e und aā = e, so ist a′ = a′e = a′aā = eā = ā. Damit sind linksinverse und rechtsinverse Elemente von a gleich und eindeutig bestimmt. Wir sprechen dann einfach vom inversen Element a′ von a. Das inverse Element von a′ ist a, denn aa′ = e. Das inverse Element von ab ist b′a′, denn b′a′ab = b′eb = b′b = e. Wenn die Operation durch a · b, ab, a ∗ b oder a ∘ b bezeichnet wird, schreibt man für das Inverse von a gewöhnlich a^{−1}. Wenn die Operation durch a + b bezeichnet wird, schreibt man für das Inverse −a oder (−a).

Bei konkreten Beispielen, wie z.B. der Gruppe (ℝ, +), ist man oft geneigt, auch unendliche Summen zu bilden und sie wie die endlichen Summen zu behandeln. Das ist jedoch prinzipiell nicht möglich. Wir können die Summe oder das Produkt von genau zwei Elementen bilden. Durch Iteration können wir die Addition bzw. Multiplikation auch auf Familien von n Elementen ausdehnen, wobei n ∈ ℕ ist, so daß Ausdrücke der Form a_{1}+a_{2}+…+a_{n} sinnvoll sind. Es ist aber keine unendliche Summe (Produkt) mit diesen Mitteln definierbar. Die bei reellen Zahlen definierbaren unendlichen Summen und Produkte leben von der Konvergenz von Folgen von endlichen Teilsummen (-produkten). Die meisten Reihen konvergieren nicht. Und selbst wenn sie konvergieren, kann man z.B. das Kommutativgesetz nicht unbeschränkt verwenden. Hier spielt eine zusätzliche Struktur der reellen Zahlen, die Norm oder der Absolutbetrag, eine wesentliche Rolle.

Definition 1.6. Sei A eine Menge und A^{∗} die Menge aller endlichen Folgen in A

A^{∗} := {(α, n)|n ∈ ℕ_{∘} ∧ α : {1, …, n} ⟶ A}.

A^{∗} heißt auch Kleene Abschluß von A. A heißt Alphabet, die Elemente a ∈ A Buchstaben, die Elemente von A^{∗} Wörter. Eine beliebige Menge von Wörtern über einem Alphabet A wird in der Informatik auch Sprache genannt. Die Verknüpfung in A^{∗} ist definiert durch

\begin{matrix}∘ : A^{∗} × A^{∗} ∋ ((a_{1}, …, a_{m}), (b_{1}, …, b_{n})) ↦ \\ (a_{1}, …, a_{m}, b_{1}, …, b_{n}) ∈ A^{∗} \end{matrix}

oder genauer

∘ : A^{∗} × A^{∗} ∋ ((α, m), (β, n)) ↦ (γ, m + n) ∈ A^{∗}

mit

γ(i) := \begin{cases}α(i) & für 1 ≤ i ≤ m, \\ β(i − m) & für m < i ≤ m + n. \end{cases}

Lemma 1.7. (A^{∗}, ∘) ist ein Monoid, genannt das (intern) freie von A erzeugte Monoid.

Beweis. Wir schreiben statt (a_{1}, …, a_{m}) einfach a_{1} … a_{m}. Dann ist a_{1} … a_{m} ∘ b_{1} … b_{n} = a_{1} … a_{m}b_{1} … b_{n} und

\begin{matrix}(a_{1} … a_{m} ∘ b_{1} … b_{n}) ∘ c_{1} … c_{r} = a_{1} … a_{m}b_{1} … b_{n} ∘ c_{1} … c_{r} = \\ a_{1} … a_{m}b_{1} … b_{n}c_{1} … c_{r} = a_{1} … a_{m} ∘ (b_{1} … b_{n} ∘ c_{1} … c_{r}). \end{matrix}

Das neutrale Element ist (∅, 0) mit ∅ : ∅ ⟶ A leere Abbildung. Dabei fassen wir {1, …, 0} als leere Menge auf. Die leere endliche Folge (∅, 0) in A^{∗} oder das leere Wort wird oft auch mit ϵ bezeichnet. Offenbar gilt ϵa_{1} … a_{n} = a_{1} … a_{n} = a_{1} … a_{n}ϵ.

Definition 1.8. Sei (G, ∘) eine Halbgruppe und A ⊂ G eine Teilmenge. Wir definieren eine Teilmenge Ā ⊂ G durch

Ā := {a_{1} ∘ … ∘ a_{m}|m ∈ ℕ ∧ a_{1}, …, a_{m} ∈ A}.

Wenn (G, ∘) ein Monoid ist, dann definiert man

Ā := {a_{1} ∘ … ∘ a_{m}|m ∈ ℕ_{∘} ∧ a_{1}, …, a_{m} ∈ A},

wobei im Falle m = 0 das leere Produkt das neutrale Element e sei. Wenn (G, ∘) eine Gruppe ist, dann definiert man

Ā := {a_{1}^{ϵ_{1}} ∘ … ∘ a_{m}^{ϵ_{m}}|m ∈ ℕ_{∘} ∧ a_{i} ∈ A ∧ ϵ_{i} ∈ {1, −1}}.

Man läßt also bei der Produktbildung als Faktoren auch Inverse von Elementen aus A zu. Ā heißt die von A erzeugte Menge in G. Wenn G = Ā, dann heißt G von A erzeugt.

Man spricht von den Mengen der Form Ā auch als durch A von ”innen“ erzeugt, weil alle ihre Elemente einzeln aus A konstruiert werden. In 1.12 werden wir auch eine Methode kennen lernen, wie man die Menge Ā von ”außen“ erzeugen kann.

Definition 1.9. Eine Teilmenge B ⊂ G in einer Halbgruppe, einem Monoid oder einer Gruppe (G, ∘) heißt

(1) Unterhalbgruppe, wenn ∀a, b ∈ B[a ∘ b ∈ B];

(2) Untermonoid, wenn B Unterhalbgruppe ist und e ∈ B gilt;

(3) Untergruppe, , wenn ∀a, b ∈ B[a ∘ b ∈ B ∧ a^{−1} ∈ B] und wenn B ≠ ∅.

Eine Untergruppe ist insbesondere ein Untermonoid, weil auch e = a ∘ a^{−1} ∈ B gilt. Wir sagen auch, daß B unter der Bildung von Produkten, des neutralen Elements bzw. von Inversen abgeschlossen ist. Eine Unterhalbgruppe (-monoid, -gruppe) ist selbst eine Halbgruppe (Monoid, Gruppe).

Lemma 1.10. Sei (G, ∘) eine Halbgruppe, ein Monoid oder eine Gruppe und sei A ⊂ G eine Teilmenge. Dann ist die von A erzeugte Menge Ā die kleinste Unterhalbgruppe (-monoid bzw. -gruppe), die A enthält.

Beweis. Ā ist so definiert, daß es unter der Multiplikation (bzw. e ∈ Ā, bzw. Inversenbildung) von (G, ∘) abgeschlossen ist. Es ist daher Ā eine Unterhalbgruppe (-monoid, -gruppe). Ist aber B ⊂ G eine Unterhalbgruppe (-monoid, -gruppe) mit A ⊂ B, so gilt auch Ā ⊂ B; also ist Ā kleinste Unterstruktur von G mit A ⊂ Ā.

Satz 1.11. Seien (G, ∘) eine Halbgruppe (Monoid, Gruppe) und seien B_{i}, i ∈ I Unterhalbgruppen (-monoide, -gruppen). Dann ist ⋂_{i∈I} B_{i} wieder Unterhalbgruppe (-monoid, -gruppe).

Beweis. Wenn jedes der B_{i} unter der Multiplikation (1 ∈ B_{i}, Inversenbildung) abgeschlossen ist, dann auch der Durchschnitt ⋂ B_{i}.

Satz 1.12. Sei (G, ∘) eine Halbgruppe (Monoid, Gruppe) und A ⊂ G eine Teilmenge. Dann ist

Ā = ⋂{B ⊂ G|B Unterstruktur ∧ A ⊂ B}.

Beweis. Da Ā unter den zugelassenen B ist, gilt ”⊃“. Da der Durchschnitt wieder eine Unterstruktur ist, die A enthält, und da Ā kleinste solche Unterstruktur ist, gilt ”⊂“.

Die Erzeugung von Ā muß man als eine Erzeugung von ”außen“ auffassen. Der Mechanismus der Gewinnung der einzelnen Elemente aus A wird nicht angegeben. Man erhält mit dieser Methode zwar sehr schnell die Existenz des gewünschten Objekts. Die Methode ist aber nicht konstruktiv, weil man keinen Überblick über alle Unterhalbgruppen (-monoide, -gruppen) hat, die A umfassen. Man kann einzelne Elemente von Ā nicht angeben. Im Falle von komplizierteren algebraischen Gebilden ist es jedoch oft sehr schwer, die Konstruktion der Elemente explizit anzugeben. Das war schon für Gruppen komplizierter, als für Monoide.

Dann entwickelt die Methode der Durchschnittsbildung erst ihre ganze Kraft.

2. Homomorphismen

Nachdem wir nun erste Beispiele und Eigenschaften von gewissen algebraischen Strukturen kennen, folgt nun die Einführung von Abbildungen, die mit der gegebenen Struktur verträglich sind, sogenannten Homomorphismen.

Definition 2.1. Seien (G, ∘) und (H, ·) Halbgruppen (Monoide, Gruppen). Eine Abbildung f : G ⟶ H heißt ein Homomorphismus von

(1) Halbgruppen, wenn ∀g_{1}, g_{2} ∈ G[f(g_{1} ∘ g_{2}) = f(g_{1}) · f(g_{2})],

(2) Monoiden, wenn ∀g_{1}, g_{2} ∈ G[f(g_{1}∘g_{2}) = f(g_{1})·f(g_{2})], und f(e_{G}) = e_{H}, (wobei e_{G} ∈ G und e_{H} ∈ H die neutralen Elemente sind),

(3) Gruppen, wenn ∀g_{1}, g_{2} ∈ G[f(g_{1} ∘ g_{2}) = f(g_{1}) · f(g_{2})].

Lemma 2.2. Ist f : G ⟶ H ein Homomorphismus von Gruppen, so gilt f(e_{G}) = e_{H} und ∀g ∈ G[f(g^{−1}) = f(g)^{−1}].

Beweis. f(e_{G}) · f(e_{G}) = f(e_{G} ∘ e_{G}) = f(e_{G}) ⟹ h · h = h für h = f(e_{G}). ⟹ h = h^{−1} · h · h = h^{−1} · h = e_{H} ⟹ f(e_{G}) = e_{H}. f(g)^{−1} · f(g) = e_{H} = f(e_{G}) = f(g^{−1} ∘ g) = f(g^{−1}) ∘ f(g) ⟹ f(g)^{−1} = f(g^{−1}).

Lemma 2.3. Seien G, H, K Halbgruppen (Monoide, Gruppen) und f : G ⟶ H, f′ : H ⟶ K Homomorphismen. Dann ist auch f′f : G ⟶ K ein Homomorphismus. Weiter ist id_{G} : G ⟶ G ein Homomorphismus.

Beweis. (f′f)(g_{1}·g_{2}) = f′(f(g_{1})·f(g_{2})) = (f′f)(g_{1})·(f′f)(g_{2}) und (f′f)(e_{G}) = f′(e_{H}) = e_{K}.

Definition 2.4. Ein Homomorphismus f : G ⟶ H heißt Isomorphismus, wenn es einen Homomorphismus f′ : H ⟶ G so gibt, daß ff′ = id_{H} und f′f = id_{G} . Wenn es einen Isomorphismus f : G ⟶ H gibt, dann heißen G und H isomorph, in Zeichen G ≅ H.

Bemerkung 2.5. Isomorphe Objekte sind für alle mathematischen Betrachtungen als gleichwertig anzusehen. Man kann nämlich die Verknüpfung von zwei Elementen auch durch die Verknüpfung der entsprechenden Elemente im dazu isomorphen Objekt ausdrücken, d.h. für einen Isomorphismus f : G ⟶ H und a, b ∈ G gilt

a · b = f^{−1}(f(a) · f(b)).

Ist f : G ⟶ H ein bijektiver Homomorphismus, so ist f ein Isomorphismus, denn für die eindeutig bestimmte Umkehrabbildung f^{−1}H ⟶ G gilt f^{−1}(h_{1} ·h_{2}) = f^{−1}(ff^{−1}(h_{1})·ff^{−1}(h_{2})) = f^{−1}f(f^{−1}(h_{1}) · f^{−1}(h_{2})) = f^{−1}(h_{1}) · f^{−1}(h_{2}) und f^{−1}(e_{H}) = e_{G}.

Lemma 2.6. Wenn f : G ⟶ H ein Homomorphismus ist, dann ist Bi(f) eine Unter-Halbgruppe (-Monoid, -Gruppe) von H.

Beweis. Seien h_{1}, h_{2} ∈ Bi(f). Dann gibt es g_{1}, g_{2} ∈ G mit f(g_{1}) = h_{1}, f(g_{2}) = h_{2}. Da f ein Homomorphismus ist, ist h_{1} · h_{2} = f(g_{1})·f(g_{2}) = f(g_{1}·g_{2}) ∈ Bi(f). Im Monoidfall ist außerdem e_{H} = f(e_{G}) ∈ Bi(f). Ist schließlich f ein Homomorphismus von Gruppen, dann ist h^{−1} = f(g)^{−1} = f(g^{−1}) ∈ Bi(f).

Beispiel 2.7. Ein wichtiges Beispiel für einen Isomorphismus ist die Exponential-Abbildung oder e-Funktion. Die reellen Zahlen bilden unter der Addition eine Gruppe (ℝ, +). Weiter bildet die Menge ℝ_{+} der positiven reellen Zahlen unter der Multiplikation eine Gruppe (ℝ_{+}, ·). Die Funktionalgleichung für die Exponentialfunktion exp(a + b) = exp(a) · exp(b) besagt genau daß diese Abbildung ein Homomorphismus ist. Da sie bijektiv ist, ist sie ein Isomorphismus. Die Umkehrabbildung ist ebenfalls ein Isomorphismus und genügt der Gleichung log(a·b) = log(a)+log(b).

Man merke sich zudem, daß die Gruppen (ℝ, +) und (ℝ_{+}, ·) zueinander isomorph sind.

3. Freie Halbgruppen, Monoide und Gruppen

Eine besonders nützliche Art von Strukturen sind die freien Strukturen. Man kennt sie (bis auf Isomorphie), wenn man nur ihre erzeugenden Elemente kennt. Sie erlauben es auch, besonders einfach Homomorphismen in andere Strukturen zu konstruieren. Allerdings geht ihre Definition von einer besonderen Eigenschaft aus, die sie haben, einer sogenannten universellen Eigenschaft. Daher ist ihre Definition nicht ganz leicht verständlich. Erst nach dem Beweis ihrer Existenz (und Eindeutigkeit) kann man diese Eigenschaft besser verstehen.

Definition 3.1. Sei A eine Menge. Eine Halbgruppe (Monoid, Gruppe) F (A) zusammen mit einer Abbildung ι : A ⟶ F (A) heißt eine (extern) freie Halbgruppe (Monoid, Gruppe), wenn zu jeder Halbgruppe (Monoid, Gruppe) G und zu jeder Abbildung α : A ⟶ G genau ein Homomorphismus f : F (A) ⟶ G existiert, so daß

[figure: A; F (A); ι; α; G; f]

kommutiert.

Bemerkung 3.2. Die Abbildung ι ist immer injektiv, so daß man A als Teilmenge von F (A) auffassen kann. Dann bedeutet die obige Definition, daß sich jede beliebige Zuordnung α von Elementen aus G zu den Elementen aus A auf genau eine Weise zu einem Homomorphismus von F (A) nach G fortsetzen läßt und daß jeder Homomorphismus f : F (A) ⟶ G schon vollständig durch die Werte bestimmt ist, die er auf Elementen aus A annimmt.

3. FREIE HALBGRUPPEN, MONOIDE UND GRUPPEN 101

Satz 3.3. (1) Ist F (A) mit ι : A ⟶ F (A) eine freie Halb-

gruppe (Monoid, Gruppe), so ist ι injektiv.

(2) Sind F (A) und F′(A) mit ι : A ⟶ F (A) und ι′ : A ⟶ F′(A) freie Halbgruppen (Monoide, Gruppen), so gibt genau einen Homomorphismus f : F (A) ⟶ F′(A) mit

[figure: A; F (A); ι; ι′; F′(A); f]

kommutativ (d.h. fι = ι′) und f ist ein Isomorphismus.

Beweis. (1) {1, −1} mit der Multiplikation ist eine Gruppe (Halbgruppe, Monoid). Sei ι : A ⟶ F (A) nicht injektiv. Dann gibt es a, b ∈ A mit ι(a) = ι(b) und a ≠ b. Wir definieren

α : A ⟶ \{1, −1\} durch α(c) = \begin{cases}1 & c ≠ a \\ −1 & c = a \end{cases}. Dann ist 1 =

α(b) = fι(b) = fι(a) = α(a) = −1, ein Widerspruch. Also ist ι injektiv.

(2) Die erste Aussage, daß genau ein Homomorphismus f mit fι = ι′ existiert, ist die Definition einer freien Halbgruppe (Monoid, Gruppe). Ebenso gibt es (genau) einen Homomorphismus f′ : F′(A) ⟶ F (A) mit f′ι′ = ι. Damit ist ff′ι′ = ι′ = id_{F′(A)} ι′, also ff′ = id_{F′(A)}, weil (F′(A), ι′) frei ist, und es ist f′fι = ι = id_{F (A)} ι, also f′f = id_{F (A)}, weil (F (A), ι) frei ist. Also ist f ein Isomorphismus.

Wir haben schon in 1.7 freie Monoide kennengelernt, jedoch nicht durch die oben gegebene Abbildungseigenschaft. Diese Abbildungseigenschaft beweisen wir im folgenden Satz. Ebenso geben wir hier die Konstruktion einer freien Halbgruppe an. Die Konstruktion einer freien Gruppe ist schwieriger. Da wir sie später nicht benötigen, wollen wir diese Konstruktion auch hier nicht angeben.

Satz 3.4. (1) Sei A eine Menge. Dann ist A^{∗} zusammen mit

der Einbettung von A in A^{∗} freies Monoid.

(2) Sei A eine Menge. Dann ist A^{∗} \ {ε} zusammen mit der Einbettung von A in A^{∗} \ {ε} freie Halbgruppe.

Beweis. (1) Sei α : A ⟶ G eine Abbildung in ein Monoid G. Wir definieren f : A^{∗} ⟶ G durch f(a_{1} … a_{n}) := α(a_{1}) · . . . · α(a_{n}) für n ≥ 1 und f(ε) := e_{G}. (Wir definieren das 0-fache Produkt von Elementen in G als e_{G}.) f ist eine wohldefinierte Abbildung, weil durch jedes Element a_{1} … a_{n} ∈ A^{∗} die Komponenten a_{1}, …, a_{n} ∈ A eindeutig stimmt sind. Sie werden benötigt, um den Wert f(a_{1} … a_{n}) zu beschreiben. Es ist f ein Homomorphismus, denn f(a_{1} … a_{n}∘b_{1} … b_{r}) = α(a_{1})·. . .·α(a_{n})· α(b_{1})·. . .·α(b_{r}) = f(a_{1}·. . .·a_{n})·f(b_{1}·. . .·b_{r}) und f(ε) = e_{G}. Weiter ist fι(a) = f(a) = α(a), also fι = α. Um die Eindeutigkeit von f mit fι = α zu zeigen, sei f′ : A^{∗} ⟶ G ein Homomorphismus mit f′ι = α. Dann ist f′(a_{1} … a_{n}) = f′(a_{1}∘…∘a_{n}) = f′(a_{1})·. . .· f′(a_{n}) = f′ι(a_{1}) · . . . · f′ι(a_{n}) = α(a_{1}) · . . . · α(a_{n}) = f(a_{1} … a_{n}). Weiter ist f′(ε) = e_{G} = f(ε). Also gilt f′ = f.

(2) Der Beweis verläuft ebenso wie in Teil (1). Allerdings müssen alle Referenzen zu ε ∈ A^{∗} fortgelassen werden.

Man kann auch zeigen, daß es zu jeder Menge A eine freie Gruppe ι : A ⟶ F (A) gibt. Die Konstruktion ist jedoch wesentlich komplizierter. Wir haben eine solche Konstruktion daher hier nicht mit aufgenommen.

Beispiele 3.5. (1) (ℕ, +) ist freie Halbgruppe über A = {1}. (2) (ℕ_{0}, +) ist freies Monoid über A = {1}.

(3) (ℤ, +) ist freie Gruppe über A = {1}.

4. Kongruenzrelationen und Restklassen

Wir haben gesehen, daß die freien Strukturen besonders günstige Eigenschaften haben. Wir kennen jedoch Beispiele von Halbgruppen, Monoiden bzw. Gruppen, die nicht frei sind. Wir werden in diesem Abschnitt zeigen, daß sich alle solchen Objekte zumindest mit Hilfe von freien Objekten beschreiben lassen. Dazu führen wir zunächst eine allgemeine Konstruktion der Restklassenbildung ein, wie wir sie bei der Bildung von Äquivalenzklassen in ähnlicher Weise auch schon früher kennengelernt haben. Der sogleich einzuführende Begriff der Kongruenzrelation spielt für Halbgruppen (Monoide, Gruppen) dieselbe Rolle, wie der Begriff der Äquivalenzrelation für Mengen. Insbesondere werden wir Partitionen nach einer Kongruenzrelation bilden und einen Faktorisierungssatz beweisen.

Definition 4.1. Sei G eine Halbgruppe (Monoid, Gruppe). Eine Teilmenge R ⊂ G × G heißt Kongruenzrelation, wenn R eine Äquivalenzrelation und eine Unter-Halbgruppe (-Monoid, -Gruppe) von G × G ist. Dabei ist die Multiplikation auf G × G komponentenweise definiert: (g_{1}, g_{2}) · (g′_{1}, g′_{2}) = (g_{1} · g′_{1}, g_{2} · g′_{2}).

Übung: Sei G eine Gruppe. Sei R ⊂ G × G eine Kongruenzrelation für die Halbgruppe G. Man zeige, daß R dann auch eine Kongruenzrelation für die Gruppe G ist. (Hinweis: Ist (g, h) ∈ R, so auch (h, g), (h^{−1}, h^{−1}) und (g^{−1}, g^{−1}). Dann ist (h^{−1}, h^{−1})(h, g)(g^{−1}, g^{−1}) = (g^{−1}, h^{−1}) ∈ R.)

Satz 4.2. Wenn R ⊂ G × G eine Kongruenzrelation auf G ist, dann trägt G/R genau eine Struktur einer Halbgruppe (Monoid, Gruppe), so daß die Restklassenabbildung ν : G ⟶ G/R ein Homomorphismus ist.

Beweis. Im Halbgruppenfall definieren wir eine Operation auf G/R durch das kommutative Diagramm

[figure: G × G; G/R × G/R; ν×ν; α; G/R; f]

mit α(g, h) := \overline{g · h}. Die Abbildung f existiert und ist eindeutig bestimmt, weil für (g, g′), (h, h′) ∈ R auch (g, g′) · (h, h′) = (g · h, g′ · h′) ∈ R ⊂ G × G gilt. Ist also g ∼ g′ und h ∼ h′, so ist g ·h ∼ g′ ·h′, also \overline{g · h} = \overline{g′ · h′} und damit α(g, h) = α(g′, h′) Wir schreiben die Multiplikation f(\overline{g}, \overline{h}) als \overline{g} ·\overline{h}, also gilt \overline{g} ·\overline{h} = \overline{g · h}. Die Multiplikation f : G/R×G/R ⟶ G/R ist assoziativ wegen \overline{g} · (\overline{h} · \overline{k}) = \overline{g} · (\overline{h · k}) = \overline{g · (h · k)} = \overline{(g · h) · k} = \overline{(g · h)} · \overline{k} = (\overline{g} · \overline{h}) · \overline{k}. Weiter ist die Restklassenabbildung ν : G ⟶ G/R ein Homomorphismus wegen ν(g · h) = \overline{g · h} = \overline{g} · \overline{h} = ν(g) · ν(h). Schließlich ist f eindeutig dadurch festgelegt, daß ν ein Homomorphismus ist, denn f(\overline{g}, \overline{h}) = f(ν(g), ν(h)) = (da ν ein Homomorphismus ist) ν(g · h) = \overline{g · h}. Im Falle von Monoiden kommt das neutrale Element e ∈ G hinzu. Wegen \overline{e}·\overline{g} = \overline{e · g} = \overline{g} und \overline{g} · \overline{e} = \overline{g · e} = \overline{g} ist \overline{e} neutrales Element in G/R. Weiter ist ν(e) = \overline{e}. Im Falle von Gruppen kommen inverse Elemente hinzu. Es ist \overline{g^{−1}} · \overline{g} = \overline{g^{−1} · g} = \overline{e} = \overline{g · g^{−1}} = \overline{g} · \overline{g^{−1}}, also ist \overline{g^{−1}} invers zu \overline{g} und G/R damit eine Gruppe.

Beispiele 4.3. (1) In ℕ ist die Partition

¯1 = {1}, ¯2 = {2}, ¯3 = {n ∈ ℕ|n ≥ 3}

von einer Kongruenzrelation abgeleitet, denn in

R = {(r, s)|r, s ≥ 3 ∨ r = s}

gilt (r, s) + (r′, s′) = (r + r′, s + s′) ∈ R, wie man durch Nachrechnen sofort sieht. Dann hat ℕ/R die folgende Verknüpfungstafel:

+ ¯1 ¯2 ¯3
¯1 ¯2 ¯3 ¯3
¯2 ¯3 ¯3 ¯3
¯3 ¯3 ¯3 ¯3

(2) Sei n ∈ ℕ_{0} fest gewählt. In ℤ × ℤ sei R := {(r, s) ∈ ℤ × ℤ|∃q ∈ ℤ[q · n = r − s]}. Man sieht leicht, daß R eine Kongruenzrelation (bzgl. der Addition von ℤ) ist. Die Kongruenzklassen ℤ/R sind \{¯0, ¯1, …, \overline{n − 1}\} im Falle n > 0 und {¯0, ±¯1, ±¯2, ±¯3, … } für n = 0. Die Verknüpfungstafel für n > 0 ist wegen r̄ + s̄ = \overline{r + s}

+  \overline{0}  \overline{1}  \overline{2}  \overline{3}  … \overline{n − 1}
\overline{0}  \overline{0}  \overline{1}  \overline{2}  \overline{3}  … \overline{n − 1}
\overline{1}  \overline{1}  \overline{2}  \overline{3}  \overline{4}  …  \overline{0}
⋮  ⋮  ⋮  ⋮  ⋮  ⋮
\overline{n − 1} \overline{n − 1} \overline{0}  \overline{1}  \overline{2}  … \overline{n − 2}

Im Falle n = 0 ist R die Gleichheitsrelation auf ℤ und ℤ/R ≅ ℤ (als Gruppen). In diesem Beispiel schreiben wir auch (n) := R und damit ℤ/(n) für n > 0 bzw. ℤ/(0) ≅ ℤ. Die hier betrachtete Äquivalenzrelation (n) ist die in Beispiel I. 4.2 (3) betrachtete. Die Äquivalenzrelation (n) ist auch eine Kongruenzrelation bezüglich der Multiplikation auf ℤ. ℤ ist dann ein Monoid. Die Verknüpfungstafel für n = 6 ist wegen r̄·s̄ = \overline{r · s}

\begin{matrix}· & ¯0 & ¯1 & ¯2 & ¯3 & ¯4 & ¯5 \\ ¯0 & ¯0 & ¯0 & ¯0 & ¯0 & ¯0 & ¯0 \\ ¯1 & ¯0 & ¯1 & ¯2 & ¯3 & ¯4 & ¯5 \\ ¯2 & ¯0 & ¯2 & ¯4 & ¯0 & ¯2 & ¯4 \\ ¯3 & ¯0 & ¯3 & ¯0 & ¯3 & ¯0 & ¯3 \\ ¯4 & ¯0 & ¯4 & ¯2 & ¯0 & ¯4 & ¯2 \\ ¯5 & ¯0 & ¯5 & ¯4 & ¯3 & ¯2 & ¯1 \end{matrix}

Satz 4.4. (Faktorisierungssatz oder Homomorphiesatz) Sei f : G ⟶ G′ ein Homomorphismus von Halbgruppen (Monoiden, Gruppen) und R eine Kongruenzrelation in G. Wenn für alle (a, b) ∈ R gilt f(a) = f(b), dann gibt es genau einen Homomorphismus f̄: G/R ⟶ G′, so daß

[figure: G; G/H; ν; f; G′; f̄]

kommutiert.

Beweis. Nach I. 4.9 existiert genau eine Abbildung f̄ mit f̄ν = f. Wir zeigen daher nur, daß f̄ ein Homomorphismus ist. Da ν nach 4.2 ein Homomorphismus ist gilt f̄(ā · b̄) = f̄(ν(a) · ν(b)) = f̄(ν(a · b)) = (f̄ν)(a · b) = f(a · b) = f(a) · f(b) = (f̄ν)(a)·(f̄ν)(b) = f̄(ā)·f̄(b̄) und im Falle von Monoiden f̄(ē) = (f̄ν)(e) = f(e) = e.

Der vorstehende Satz ist das allgemeine und einzige Hilfmittel, um einen Homomorphismus f̄: G/R ⟶ G′ zu definieren. Wenn man einen solchen Homomorphismus konstruieren soll, so muß man zunächst einen Homomorphismus f : G ⟶ G′ konstruieren und dann die Voraussetzungen des Satzes erfüllen. Wir wollen das an einigen Beispielen studieren.

Beispiele 4.5. (1) Definiert die folgende Angabe einen Homomorphismus:

ℤ/(6) ∋ n̄ ↦ n̄ ∈ ℤ/(3)?

Hier ist eine Eigenheit der Notation der Restklassen besonders zu beachten. Es ist ¯0 ∈ ℤ/(6) die Menge ¯0 = {0, ±6, ±12, ±18, … }. Weiter ist ¯0 ∈ ℤ/(3) eine gänzlich andere Menge, nämlich ¯0 = {0, ±3, ±6, ±9, … }. Der Leser möge sich die Elemente ¯1 ∈ ℤ/(6) und ¯1 ∈ ℤ/(3) in entsprechender Schreibweise klarmachen. Bei Verwendung der Schreibweise n̄ muß also immer klar sein, in welcher Menge dieses Element liegen soll. Wir sind insbesondere mit der obigen Angabe weit von einer identischen Abbildung entfernt. Die wichtigste Frage ist jedoch, ob die oben angegebene Zuordnung oder Relation eine (wohldefinierte) Abbildung ist. Es können nämlich verschiedene Zahlen n ∈ ℤ gleiche Elemente n̄ ∈ ℤ/(6) bestimmen, z.B. ¯1 = ¯7. Wir haben also zwei verschiedene Repräsentanten für ¯1, nämlich 1 und 7. Dann muß man überprüfen, daß in jedem solchen Fall die Bilder n̄ ∈ ℤ/(3) nicht von der besonderen Wahl des Repräsentanten n für n̄ abhängt. Also ist der Faktorisierungssatz einzusetzen. Das geschieht so: Die Abbildung α := ν_{3} : ℤ ⟶ ℤ/(3) (die Restklassenabbildung) ist nach 4.2 ein Homomorphismus. Für R = (6) ist (n, r) ∈ R genau dann, wenn n − r = q · 6 für ein q ∈ ℤ. Dann gilt aber α(n) = ν_{3}(n) = ν_{3}(r + q · 6) = ν_{3}(r + 2q · 3) = ν_{3}(r) = α(r). Also gibt es genau einen Homomorphismus f : ℤ/(6) ⟶ ℤ/(3) mit fν_{6} = ν_{3}, d.h. mit f(n̄) = ν_{3}(n) = n̄, also der gewünschte Homomorphismus. Wie sind wir nun gerade auf den Homomorphismus α := ν_{3} gekommen. Da das Dreieck

[figure: ℤ; ℤ/(6); ν; α; ℤ/(3); f]

kommutieren soll, muß, falls f überhaupt existiert, α = fν sein. Dann ergibt sich aber α(n) = fν_{6}(n) = f(n̄) = n̄ = ν_{3}(n).

(2) Definiert die folgende Angabe einen Homomorphismus:

ℤ/(6) ∋ n̄ ↦ n̄ ∈ ℤ/(4)?

Wieder setzen wir den Faktorisierungssatz ein. Als Homomorphismus α : ℤ ⟶ ℤ/(4) müssen wir wie zuvor α = ν_{4} wählen. Für (n, r) ∈ (6), also n = r+q·6 ist ν_{4}(n) = ν_{4}(r) oder (n, r) ∈ (4) zu zeigen, also müssen wir prüfen, ob n− r auch durch 4 teilbar ist, wenn es durch 6 teilbar ist. Das ist offenbar nicht der Fall und liefert und schon ein Gegenbeispiel. In ℤ/(6) ist ¯6 = ¯0 = {0, ±6, ±12, ±18, … }. Aber in ℤ/(4) ist ¯6 = {2, −4, 6, −8, 10, … } ≠ {0, ±4, ±8 ± 12, … } = ¯0, also kann die angegebene Relation keine Abbildung sein, weil ein Element ¯6 = ¯0 ∈ ℤ/(6) zwei verschiedene Bilder ¯6 ≠ ¯0 in ℤ/(4) hat.

(3) Definiert die folgende Angabe einen Homomorphismus:

ℤ/(3) ∋ n̄ ↦ \overline{n^{3}} ∈ ℤ/(3)?

Der Homomorphismus α : ℤ ⟶ ℤ/(3) muß die Abbildung α(n) = \overline{n^{3}} sein. Das ist tatsächlich ein Homomorphismus, denn

α(n + r) = \overline{(n + r)^{3}} = \overline{n^{3} + 3n^{2}r + 3nr^{2} + r^{3}}

und

α(n) + α(r) = \overline{n^{3}} + \overline{r^{3}} = \overline{n^{3} + r^{3}}.

Die beiden rechten Seiten der Gleichungen stimmen überein, weil n^{3} + 3n^{2}r + 3nr^{2} + r^{3} − n^{3} − r^{3} = (n^{2}r + nr^{2}) · 3. Ist weiterhin n ∼ r, d.h. n − r = q · 3, so ist n^{3} = (r + q · 3)^{3} = r^{3} + (r^{2}q · 3 + rq^{2} · 9 + q^{3} · 9) · 3, also α(n) = \overline{n^{3}} = \overline{r^{3}} = α(r). Damit sind die Voraussetzungen des Faktorisierungssatzes erfüllt. Tatsächlich kann man leicht nachrechnen, daß die gegebene Abbildung sogar die identische Abbildung ist.

Satz 4.6. Sei f : G ⟶ G′ ein Homomorphismus von Halbgruppen (Monoiden, Gruppen). Dann ist die zu f gehörige Äquivalenzrelation a ∼ b :⟺ f(a) = f(b) (vgl. I. 4.3) eine Kongruenzrelation.

Beweis. Sei R ⊂ G × G die gegebene Äquivalenzrelation. Seien (a, b), (a′, b′) ∈ R. Dann ist f(a · a′) = f(a) · f(a′) = f(b) · f(b′) = f(b · b), also auch (a · a′, b · b′) ∈ R. Ebenso ist im Monoidfall (e, e) ∈ R, weil R eine Äquivalenzrelation ist. Schließlich ist im Falle von Gruppen mit (a, b) ∈ R auch (a^{−1}, b^{−1}) ∈ R, denn f(a^{−1}) = f(a)^{−1} = f(b)^{−1} = f(b^{−1}).

Bemerkung 4.7. Mit der Konstruktion von G/R erhält man eine Bijektion zwischen der Menge aller Kongruenzrelationen in G und der Menge aller möglichen Restklassenobjekte G/R, d.h. der Menge aller Partitionen von G, die die Struktur einer Halbgruppe (Monoid, Gruppe) so tragen, daß ν : G ⟶ G/R ein Homomorphismus wird (vgl. I. 4.7). Die Aussagen von I. 4.10 übertragen sich sinngemäß. Insbesondere ist Bi(f) eine Unter-Halbgruppe (-Monoid, -Gruppe) für einen Homomorphismus f : G ⟶ G′, und die von ν : G/R ⟶ G′ induzierte Abbildung ν′ : G/R ⟶ Bi(f) ist ein Isomorphismus, wobei R die zu f gehörige Kongruenzrelation ist.

Definition 4.8. Sei G eine Halbgruppe (Monoid, Gruppe), die von einer Menge A erzeugt wird. Dann gibt es nach 3.1 genau einen Homomorphismus f : F (A) ⟶ G, der die Inklusion α : A ⟶ G fortsetzt. Eine Relation für G bzgl. A ist ein Paar (w_{1}, w_{2}) in F (A) × F (A) mit f(w_{1}) = f(w_{2}). Die Menge der Relationen für G bezüglich A bezeichnen wir mit R_{G}(A) := {(w_{1}, w_{2}) ∈ F (A) × F (A)|f(w_{1}) = f(w_{2})}.

Folgerung 4.9. Die Menge der Relationen für G bezüglich A ist eine Kongruenzrelation auf F (A).

Beweis. R_{G}(A) ist die Kongruenzrelation, die durch den Homomorphismus f : F (A) ⟶ G induziert wird.

Satz 4.10. Jede Halbgruppe (Monoid, Gruppe) ist isomorph zu einem Objekt F (A)/R, wobei R eine Kongruenzrelation ist.

Beweis. Sei A eine Erzeugendenmenge von G. Eine solche existiert immer, z.B. A = G. Es gibt aber im allgemeinen sehr viel kleinere Erzeugendenmengen für G. Sei R := R_{G}(A). Wir definieren einen surjektiven Homomorphismus f : F (A) ⟶ G durch das kommutative Diagramm

[figure: A; F (A); ι; α; G,; f]

wobei α : A ⟶ G die Inklusionsabbildung ist. Da A ⊂ Bi(f) und Bi(f) nach 2.6 eine Unter-Halbgruppe (-Monoid, -Gruppe) von G ist, ist nach 1.10 G = Ā ⊂ Bi(f) ⊂ G, also Bi(f) = G und damit f surjektiv. Dann induziert f : F (A) ⟶ G nach I. 4.9 und I. 4.10 (3) einen bijektiven Homomorphismus f̄: F (A)/R ⟶ G, so daß

[figure: F (A); F (A)/R; ν; f; G; f̄]

kommutiert, denn f̄(\overline{w_{1}} · \overline{w_{2}}) = f̄(\overline{w_{1} · w_{2}}) = f̄ν(w_{1} · w_{2}) = f(w_{1} · w_{2}) = f(w_{1}) · f(w_{2}) = f̄ν(w_{1}) · f̄ν(w_{2}) = f̄(\overline{w_{1}}) · f̄(\overline{w_{2}}). Im Falle von Monoiden gilt zusätzlich f̄(ε̄) = f(ε) = e.

Bemerkung 4.11. Zur Darstellung einer Halbgruppe (Monoid, Gruppe) G in der Form F (A)/R genügt es also, eine Erzeugendenmenge A für G und eine Erzeugendenmenge B für R ⊂ F (A) × F (A) anzugeben. Gibt man eine Menge A und eine Teilmenge B ⊂ F (A) × F (A) vor, so kann man daraus eine kleinste Kongruenzrelation R ⊂ F (A) × F (A) mit B ⊂ R bilden durch R := ⋂{S ⊂ F (A)×F (A)|S Kongruenzrelation ∧A ⊂ S}. Damit definieren A und B eine Halbgruppe (Monoid, Gruppe) F (A)/R durch Erzeugende A und Relationen B.

5. Restklassengruppen

Bei den Gruppen hängt die Restklassenbildung mit gewissen Untergruppen mit einer ganz besonderen Eigenschaft zusammen, die man normale Untergruppen nennt. Genauer gibt es eine Bijektion zwischen allen normalen Untergruppen einer Gruppe G und allen Kongruenzrelationen auf G. Die etwas unhandlichen Kongruenzrelationen lassen sich also durch einfachere normale Untergruppen erzetzen. Auch die Faktorgruppen oder Restklassengruppen lassen sich damit einfacher beschreiben.

Definition 5.1. Eine Untergruppe H einer Gruppe G heißt Normalteiler (oder normale Untergruppe), wenn

∀g ∈ G, h ∈ H∃h′ ∈ H[gh = h′g].

Bemerkung 5.2. Äquivalent dazu ist, daß für alle g ∈ G gilt gHg^{−1} = {ghg^{−1}|h ∈ H} ⊂ H oder daß für alle g ∈ G gilt gH = Hg. Die Bedingung läßt sich besonders einfach für abelsche (kommutative) Gruppen G erfüllen, es ist nämlich gh = hg für alle h ∈ H und alle g ∈ G. Zu g und h kann man also immer h ∈ H wählen, um die Bedingung für die Normalität zu erfüllen. Es gilt also: jede Untergruppe einer abelschen Gruppe ist eine normale Untergrppe.

Satz 5.3. Sei G eine Gruppe. Die Zuordnungen

P(G) ∋ H ↦ R ∈ P(G × G)

mit R := {(a, b)|ab^{−1} ∈ H} und

P(G × G) ∋ R ↦ H ∈ P(G)

mit H := {ab^{−1}|(a, b) ∈ R} definieren eine Bijektion zwischen der Menge der Normalteiler H von G und der Menge der Kongruenzrelationen R auf G.

Beweis. 1. Behauptung: Wenn H ein Normalteiler ist, dann ist R := {(a, b)|ab^{−1} ∈ H} eine Kongruenzrelation. Beweis: R ist reflexiv, weil a · a^{−1} = e ∈ H für alle a ∈ G gilt. Ist (a, b), (b, c) ∈ R, so ist a · b^{−1}, b · c^{−1} ∈ H, also auch a · c^{−1} = (a · b^{−1}) · (b · c^{−1}) ∈ H. Also ist (a, c) ∈ R und R damit transitiv. Ist (a, b) ∈ R, so ist a · b^{−1} ∈ H, also b · a^{−1} = (b^{−1})^{−1} · a^{−1} = (a · b^{−1})^{−1} ∈ H und damit (b, a) ∈ R. Daher ist R eine Äquivalenzrelation. Bisher haben wir nur verwendet, daß H eine Untergruppe von G ist. Seien jetzt (a, b), (c, d) ∈ R. Dann ist a · b^{−1}, c · d^{−1} ∈ H und damit (a · c) · (b · d)^{−1} = a · c · d^{−1} · b^{−1} = a · h · b^{−1} = h′ · a · b^{−1} ∈ H, wobei h = c · d^{−1} ∈ H und a · h = h′ · a, weil H ein Normalteiler ist. Damit ist auch (a · c, b · d) ∈ R. Nach der Übung im Anschluß an 4.1 ist R damit eine Kongruenzrelation.

2. Behauptung: Wenn R eine Kongruenzrelation ist, dann ist H := {ab^{−1}|(a, b) ∈ R} ein Normalteiler.

Beweis: H ist eine Untergruppe von G. Wegen (e, e) ∈ R ist e = e · e^{−1} ∈ H. Ist x = a · b^{−1} ∈ H mit (a, b) ∈ R, so ist auch (b, a) ∈ R, also x^{−1} = (a · b^{−1})^{−1} = b · a^{−1} ∈ H. Seien schließlich x = a·b^{−1} und y = c·d^{−1} in H mit (a, b), (c, d) ∈ R. Dann ist auch (a, b) · (b^{−1}, b^{−1}) · (c, d) · (d^{−1}, d^{−1}) = (a · b^{−1} · c · d^{−1}, b · b^{−1} · d · d^{−1}) = (a · b^{−1} · c · d^{−1}, e) ∈ R, also x · y = a · b^{−1} · c · d^{−1} · e^{−1} ∈ H. Sei schließlich x ∈ H und c ∈ G. Sei x = a · b^{−1} mit (a, b) ∈ R, so ist auch (c, c) · (a, b) · (b^{−1}, b^{−1}) · (c^{−1}, c^{−1}) = (c · a · b^{−1} · c^{−1}, c · b · b^{−1} · c^{−1}) = (c · a · b^{−1} · c^{−1}, e) ∈ R, also y := c · a · b^{−1} · c^{−1} ∈ H. Zu x = a · b^{−1} und c ist damit ein y ∈ H gefunden mit y · c = c · a · b^{−1} · c^{−1} · c = c · a · b^{−1} = c · x. Damit ist H ein Normalteiler.

3. Behauptung: Die Hintereinanderausführung H ↦ R ↦ H′ ist die Identität. Beweis: Es seien also

R := {(a, b)|ab^{−1} ∈ H} und H′ := {ab^{−1}|(a, b) ∈ R}.

Wir zeigen H = H′. Sei x ∈ H′. Dann ist x = ab^{−1} für ein (a, b) ∈ R. Für (a, b) gilt aber ab^{−1} ∈ H, also ist x ∈ H und damit H′ ⊂ H. Ist umgekehrt h ∈ H, so ist (h, e) ∈ R und damit h = he^{−1} ∈ H′, also auch H ⊂ H′.

4. Behauptung: Die Hintereinanderausführung R ↦ H ↦ R′ ist die Identität. Beweis: Es seien also

H := {ab^{−1}|(a, b) ∈ R} und R′ := {(a, b)|ab^{−1} ∈ H}.

Wir zeigen R = R′. Sei (a, b) ∈ R. Dann ist ab^{−1} ∈ H und daher (a, b) ∈ R′, also R ⊂ R′. Sei (a, b) ∈ R′. Dann gilt ab^{−1} ∈ H, also gibt es (c, d) ∈ R mit cd^{−1} = ab^{−1}. Wegen (b, b), (d^{−1}, d^{−1}) ∈ R folgt (a, b) = (ab^{−1}b, b) = (cd^{−1}b, b) = (c, d)(d^{−1}, d^{−1})(b, b) ∈ R, also (a, b) ∈ R und damit auch R′ ⊂ R.

Bemerkung 5.4. Man schreibt nun auch G/H := G/R. Die Kongruenzklassen \overline{a} lassen sich schreiben als \overline{a} = \{b ∈ G|(b, a) ∈ R} = {b|∃h ∈ H[b · a^{−1} = h]} = {b|∃h ∈ H[b = h · a]} = H · a = a · H. Die Verknüpfung in G/H ist \overline{a} · \overline{b} = \overline{a · b} oder (a · H) · (b · H) = (a · b) · H.

Definition 5.5. Sei H ein Normalteiler von G. Die Gruppe

G/H = {a · H|a ∈ G}

heißt Restklassengruppe oder Faktorgruppe von G modulo H.

Satz 5.6. (Faktorisierungs- oder Homomorphiesatz für Gruppen) Sei f : G ⟶ G′ ein Homomorphismus von Gruppen und H ein Normalteiler in G. Wenn f(H) = {e_{G′}}, dann gibt es genau einen Homomorphismus \overline{f} : G/H ⟶ G′, so daß

[figure: G; G/H; ν; f; G′; \overline{f}]

kommutiert.

Beweis. Nach I. 4.9 existiert \overline{f} eindeutig als Abbildung, wenn für alle a, b ∈ G mit (a, b) ∈ R gilt f(a) = f(b). Aber wenn (a, b) ∈ R ist, dann ist a · b^{−1} ∈ H, also f(a · b^{−1}) = e_{G′} und damit f(a) = f(b), denn f(a) · f(b)^{−1} = f(a · b^{−1}) = e_{G′}. Da die Multiplikation in G/H auf den Repräsentanten durchgeführt wird, gilt (wie im Beweis von 4.2) \overline{f}(\overline{a}·\overline{b}) = \overline{f}(\overline{a · b}) = \overline{f}ν(a·b) = f(a · b) = f(a) · f(b) = \overline{f}ν(a) · \overline{f}ν(b) = \overline{f}(\overline{a}) · \overline{f}(\overline{b}), also ist \overline{f} ein Homomorphismus.

Beispiele 5.7. (1) Sei n ∈ ℕ. Dann ist

S_{n} := {{1, …, n} ⟶ {1, …, n}|a bijektiv }

unter der Verknüpfung von Abbildungen eine Gruppe (I. 2.22). S_{n} heißt symmetrische Gruppe oder Permutationsgruppe. Nach (II. 4.6) ist S_{n} eine Gruppe mit n! Elementen. S_{n} hat Erzeugende

(\begin{matrix}1, 2, 3, …, n \\ 2, 1, 3, …, n \end{matrix}) und (\begin{matrix}1, 2, 3, …, n \\ 2, 3, 4, …, 1 \end{matrix}) .

Eine andere Erzeugendenmenge ist {σ_{i}} ⊂ S_{n} für i = 1, …, n − 1 mit

σ_{i}(k) := \begin{cases}i + 1, & für k = i, \\ i, & für k = i + 1, \\ k, & sonst. \end{cases}

Die σ_{i} heißen Transpositionen. Die σ_{i} erfüllen die Relationen σ_{i}σ_{j} = σ_{j}σ_{i} für i < j − 1 und 1 ≤ i, j ≤ n − 1, und σ_{i}σ_{i+1}σ_{i} = σ_{i+1}σ_{i}σ_{i+1} für 1 ≤ i ≤ n − 2, und σ_{i}^{2} = id für 1 ≤ i ≤ n − 1. Man kann S_{n} auch darstellen als F ({σ_{1}, …, σ_{n−1}})/R, wobei R die von den Relationen (σ_{i}σ_{j}, σ_{j}σ_{i}), (σ_{i}σ_{i+1}σ_{i}, σ_{i+1}σ_{i}σ_{i+1}) und (σ_{i}σ_{i}, ε) erzeugte Kongruenzrelation ist.

(2) Die Untergruppe A_{n} ⊂ S_{n} mit A_{n} = {s_{1} · . . . · s_{2t}|t ∈ ℕ_{0} ∧ s_{i} ∈ {σ_{1}, …, σ_{n−1}}} heißt Gruppe der geraden Permutationen. Man kann zeigen, daß A_{n} ⊂ S_{n} ein Normalteiler ist und daß A_{n} ≠ S_{n} gilt (n ≥ 2). Dann hat S_{n}/A_{n} genau 2 Elemente \overline{id} und \overline{σ_{1}}, denn für s_{1} · . . . · s_{t} ∈ S_{n} gilt s_{1} · . . . · s_{t} ∼ id (s_{1} · . . . · s_{t} · id^{−1} ∈ A_{n}), wenn t gerade ist, und s_{1} · . . . · s_{t} ∼ σ_{1} (s_{1} · . . . · s_{t} · σ_{1} ∈ A_{n}), wenn t ungerade ist. Dabei seien die s_{i} Transpositionen. Es genügt Elemente der Form s_{1} ·. . .·s_{t} zu betrachten, weil s_{i} = s_{i}^{−1} gilt. Die Multiplikationstafel muß daher

·  \overline{id} \overline{σ_{1}}
\overline{id} \overline{id} \overline{σ_{1}}
\overline{σ_{1}}  \overline{σ_{1}}  \overline{id}

sein. Die Abbildung \overline{f} : S_{n}/A_{n} ⟶ \{1, −1\} mit \overline{f}(\overline{id}) = 1, \overline{f}(\overline{σ}_{1}) = −1 ist ein Isomorphismus, wenn man \{1, −1\} als Gruppe mit der gewöhnlichen Multiplikation auffaßt:

\begin{matrix}· & 1 & -1 \\ 1 & 1 & -1 \\ -1 & -1 & 1 \end{matrix} .

Der Homomorphismus S_{n} ⟶^{ν} S_{n}/A_{n} ⟶^{\overline{f}} \{1, −1\} heißt Signatur oder Vorzeichen: sgn := \overline{f}ν. Eine Permutation τ ∈ S_{n} heißt gerade, wenn sie sich als Produkt einer geraden Anzahl von Transpositionen schreiben läßt. Sonst heißt sie ungerade. τ ∈ S_{n} ist genau dann gerade, wenn sgn(τ) = 1 gilt.

Satz 5.8. (Cayley) Sei G eine endliche Gruppe. Dann gibt es eine Untergruppe U einer Permutationsgruppe S_{n}, zu der G isomorph ist.

Beweis. Habe G genau n Elemente und sei

G = {e = a_{1}, …, a_{n}}.

Jedem a ∈ G ordnen wir die Permutation σ_{a} : {1, …, n} ⟶ {1, …, n} zu mit a · a_{i} = a_{σ_{a}(i)}. Offenbar gibt es zu jedem Index i genau einen Index σ_{a}(i) mit a · a_{i} = a_{σ_{a}(i)}. Daher ist σ_{a} eine Abbildung. Die Umkehrabbildung von σ_{a} ist τ := σ_{a^{−1}}, denn a_{i} = a^{−1} · a · a_{i} = a^{−1} · a_{σ_{a}(i)} = a_{τ(σ_{a}(i))} und a_{i} = a · a^{−1} · a_{i} = a · a_{ε(i)} = a_{σ_{a}(τ(i))}, also gilt τ(σ_{a}(i)) = i = σ_{a}(τ(i)). Damit ist σ_{a} bijektiv, also eine Permutation. Wir haben somit eine Abbildung σ : G ∋ a ↦ σ_{a} ∈ S_{n} definiert. Wegen a_{σ_{a·b}(i)} = (a · b) · a_{i} = a · b · a_{i} = a · a_{σ_{b}(i)} = a_{σ_{a}(σ_{b}(i))} ist σ_{a·b} = σ_{a}∘σ_{b}, also ist σ ein Homomorphismus. Schließlich ist σ injektiv, denn aus σ_{a} = σ_{b} folgt a = a·e = a·a_{1} = a_{σ_{a}(1)} = a_{σ_{b}(1)} = b · a_{1} = b Sei U := Bi(σ). Dann ist U eine Untergruppe von S_{n} und der eingeschränkte Homomorphismus σ′ : G ⟶ Bi(σ) = U bijektiv, also ein Isomorphismus.

Definition 5.9. (1) Sei G eine endliche Gruppe. Die Anzahl

der Elemente von G heißt Ordnung von G.

(2) Sei a ∈ G ein Element einer beliebigen Gruppe. Wenn es ein kleinstes n ∈ ℕ gibt mit a^{n} = a · . . . · a(n-mal)= e, dann heißt n die Ordnung von a. Gibt es kein solches n, so sagen wir, daß die Ordnung von a unendlich ist.

Man beachte, daß dieser Begriff einer Ordnung nichts zu tun hat mit dem Begriff einer geordneten Menge.

Bemerkung 5.10. Wenn es ein n ∈ ℕ mit a^{n} = e gibt, so gibt es auch ein kleinstes solches n, da ℕ wohlgeordnet ist. Wir betrachten jetzt ein Element a ∈ G in einer endlichen Gruppe. Wenn a^{r} = a^{s} ist und r < s, so ist a^{s−r} = e, denn a^{s−r} = a^{s−r}a^{r}(a^{s})^{−1} = a^{s}(a^{s})^{−1} = e. Wir betrachten die Folge a, a^{2}, a^{3}, a^{4}, . . .. Die Elemente können nicht alle paarweise verschieden sein, denn sie liegen in G und G ist endlich. Sei nun s die kleinste Zahl, so daß ein r mit 1 ≤ r < s existiert mit a^{r} = a^{s}. Sei n := s−r. Dann ist a^{n} = e, die Elemente a, a^{2}, …, a^{n} sind alle paarweise verschieden (denn n = s−r < s, weil r ≥ 1). Damit ist n die Ordnung von a. Für t > n gibt es eindeutig bestimmte q und r mit t = qn + r und 0 ≤ r < n. Dann ist a^{t} = a^{qn+r} = a^{qn}a^{r} = (a^{n})^{q}a^{r} = e^{q}a^{r} = a^{r}. Also ist {a, a^{2}, …, a^{n}} = {a, a^{2}, …, a^{n}, a^{n+1}, … }. Weiter ist a^{i} · a^{n−i} = a^{n} = e für 1 ≤ i < n, d.h. alle Elemente in {a, a^{2}, …, a^{n−1}} haben ihr inverses Element ebenfalls in dieser Menge. Insgesamt ist damit U = {a, a^{2}, …, a^{n}} eine Untergruppe der Ordnung n, die von a erzeugte zyklische Untergruppe von G. Wir haben damit allgemein bewiesen, daß ein Element der Ordnung n eine Untergruppe der Ordnung n erzeugt. Hat das Element a unendliche Ordnung (in einer unendlichen Gruppe G), so hat die von a erzeugte Untergruppe \overline{\{a\}} ebenfalls unendlich viele Elemente. Man beachte, daß es in einer unendlichen Gruppe Elemente endlicher Ordnung geben kann. In (ℝ \ {0}, ·) hat z.B. (-1) die Ordnung 2.

Satz 5.11. (Lagrange) In einer endlichen Gruppe G ist die Ordnung jeder Untergruppe U ein Teiler der Ordnung der Gruppe. Insbesondere ist die Ordnung jedes Elements ein Teiler der Ordnung der Gruppe.

Beweis. Wir definieren auf G eine Partition G/U := {aU|a ∈ G}, wobei aU := {au|u ∈ U}. Wegen e ∈ U gilt a ∈ aU, also ist ⋃_{a∈G} aU = G. Sei c ∈ aU ∩ bU. Dann ist c = au_{1} = bu_{2}, also a = bu_{2}u_{1}^{−1} ∈ bU und au = bu_{2}u_{1}^{−1}u ∈ bU. Damit ist aU ⊂ bU und analog bU ⊂ aU, d.h. aU = bU. Damit ist gezeigt, daß G/U eine Partition ist. Zwischen aU und U gibt es eine bijektive Abbildung aU ∋ x ↦ a^{−1}x ∈ U, denn wenn x = au, dann ist a^{−1}x = a^{−1}au = u ∈ U. Die Umkehrabbildung ist U ∋ u ↦ au ∈ aU. Daher haben alle Klassen aU der Partition gleich viele Elemente, etwa r Elemente. Da G = ⋃ aU eine Vereinigung von s paarweise disjunkten Mengen ist, hat G genau s · r Elemente, also ist r, die Ordnung von U, ein Teiler der Ordnung von G.

Bemerkung 5.12. Wir wissen zunächst nicht, wieviele paarweise verschiedene (und damit auch disjunkte) Mengen der Form aU wir haben. Es können a und b verschieden sein, und es kann trotzdem aU = bU gelten. Da aber G endlich ist, können nur endlich viele (oben s) solche Klassen auftreten.

Bemerkung 5.13. Bezeichnen wir U\G := {Ua|a ∈ G}, so ist dies ebenfalls eine Partition von G. Die Partitionen U\G und G/U sind im allgemeinen verschieden. Es gilt U\G = G/U genau dann, wenn U ein Normalteiler ist. Wir beachten dazu die Definition 5.1. Damit ist nur zu zeigen, daß aU = Ub impliziert aU = Ua. Aber aus aU = Ub folgt a ∈ Ub und damit wie oben Ub = Ua.

6. Ringe und Körper

Bei den Mengen von Zahlen, etwa den ganzen oder den komplexen Zahlen, haben wir Beispiele gefunden, bei denen zwei verschiedene Verknüpfungen, z.B. die Addition und die Multiplikation, auftreten. Die beiden Verknüpfungen erfüllen Eigenschaften, die nur mit beiden Verknüpfungen gemeinsam ausgedrückt werden können, wie das Assoziativgesetz. Wir werden daher jetzt die Axiome dieser Beispiele betrachten und sie verallgemeinern.

Definition 6.1. Ein Ring ist ein Tripel (R, +, ·) mit folgenden Eigenschaften

(1) (R, +) ist eine abelsche Gruppe,

(2) (R, ·) ist eine Halbgruppe,

(3) Es gelten die Distributiv-Gesetze

\begin{aligned}∀a, b, c, ∈ R[ & a · (b + c) = a · b + a · c ∧ \\ & (a + b) · c = a · c + b · c ] \end{aligned}

(wobei die Multiplikation stärker bindet (also Präzedenz hat), als die Addition: a · b + c = (a · b) + c).

Ein Ring (R, +, ·) heißt Ring mit Einselement oder unitärer Ring, wenn (R, ·) ein Monoid ist. Ein Ring heißt kommutativer Ring, wenn (R, ·) kommutativ ist. Ein Ring heißt nullteilerfrei, wenn gilt: ∀a, b ∈ R[a · b = 0 ⟹ a = 0 ∨ b = 0]. Wir schreiben im folgenden das Produkt a·b auch als ab. Das neutrale Element von (R, +) wird mit Null oder 0 bezeichnet. Das neutrale Element von (R, ·) für einen unitären Ring wird mit Eins oder 1 bezeichnet. Die Verknüpfungen + : R × R ⟶ R bzw. · : R × R ⟶ R heißen Addition bzw. Multiplikation. Das Inverse eines Elements a ∈ R unter der Addition wird mit −a oder (−a) bezeichnet, unter der Multiplikation (falls es existiert) mit a^{−1}.

Lemma 6.2. (Rechengesetze in Ringen) Seien a, b ∈ R. Dann gilt

(1) 0a = a0 = 0,

(2) (−ab) = (−a)b = a(−b),

(3) (−a)(−b) = ab,

(4) (−a) = (−1)a.

(5) Wenn 0 = 1, dann ist R = {0}.

Beweis. (1) Es ist 0a = (0 + 0)a = 0a + 0a. Durch Subtrahieren von 0a (Addieren von (−0a)) erhält man 0 = 0a. Analog ergibt sich 0 = a0.

(2) Es ist ab + (−a)b = (a + (−a))b = 0b = 0, also ist (−a)b = (−ab) invers zu ab. Analog ist a(−b) = (−ab).

(3) Es ist (−a)(−b) = (−a(−b)) = (−(−ab)) = ab.

(4) Es ist (−1)a = (−1a) = (−a).

(5) Sei 0 = 1 und a ∈ R. Dann ist a = 1a = 0a = 0.

Definition 6.3. Seien R und S Ringe und f : R ⟶ S eine Abbildung. f heißt Homomorphismus von Ringen, wenn

∀a, b ∈ R[f(a + b) = f(a) + f(b) ∧ f(a · b) = f(a) · f(b)].

Seien R und S unitäre Ringe und f : R ⟶ S eine Abbildung. f heißt Homomorphismus von unitären Ringen, wenn f : R ⟶ S ein Homomorphismus von Ringen ist und gilt f(1) = 1.

Beispiele 6.4. (1) (ℤ, +, ·), (ℚ, +, ·), (ℝ, +, ·) und (ℂ, +, ·) sind unitäre kommutative Ringe. (ℕ_{0}, +, ·) ist kein Ring, weil (ℕ_{0}, +) keine Gruppe ist.

(2) Sei n ∈ ℕ_{0} fest gewählt. Dann ist ℤ/(n) mit der Addition und Multiplikation der Kongruenzklassen definiert durch Addition und Multiplikation der Repräsentanten wie in 4.3(2)

\overline{r} + \overline{s} = \overline{r + s}, \overline{r} · \overline{s} = \overline{rs}

ein unitärer kommutativer Ring. Wegen 4.2 und 4.3(2) sind nur die Distributivgesetze zu prüfen:

\overline{r} · (\overline{s} + \overline{t}) = \overline{r} · (\overline{s + t}) = \overline{r(s + t)} = \overline{rs + rt} = \overline{rs} + \overline{rt} = \overline{r} · \overline{s} + \overline{r} · \overline{t}

und analog

(\overline{r} + \overline{s}) · \overline{t} = \overline{r} · \overline{t} + \overline{s} · \overline{t}.

(3) Restklassentests: Sei α : ℕ ⟶ ℤ eine Abbildung, deren Bild eine endliche Teilmenge X ⊂ ℤ ist und für die gilt ∀r ∈ ℕ[\overline{α(r)} = \overline{r}], wobei die Restklassen in ℤ/(n) für ein festes n ∈ ℤ betrachtet werden. Dann gilt \overline{α(r + s)} = \overline{α(r) + α(s)} und \overline{α(r · s)} = \overline{α(r) · α(s)}, denn \overline{α(r + s)} = \overline{r + s} = \overline{α(s)} = \overline{α(r) + α(s)} und \overline{α(r · s)} = \overline{r · s} = \overline{r} · \overline{s} = \overline{α(r)} · \overline{α(s)} = \overline{α(r) · α(s)}. Diese Formeln gestatten eine Überprüfung von Additions- und Multiplikationsaufgaben, indem man α(r · s) und α(r) · α(s) vergleicht. Diese müssen kongruent modulo n sein. Da X eine endliche Menge ist, sind diese Kongruenzen leicht zu überprüfen. Wenn der vermeintliche Wert des Produktes r · s unter α nicht kongruent zu α(r) · α(s) ist (letzteres Produkt ist leichter zu berechnen, evtl. aufgrund einer expliziten Multiplikationstabelle auf X), so ist bei der Berechnung von r ·s ein Fehler aufgetreten. Analoges gilt für Summen.

(4) Die Abbildung β : ℕ ⟶ ℤ sei die sogenannte Quersumme (der Dezimaldarstellung), d.h. β(a_{r} · 10^{r} + a_{r−1}10^{r−1} + … + a_{1} · 10 + a_{0}) := a_{0} + a_{1} + … + a_{r−1} + a_{r}. Dann ist 10^{i} ≡ 1 mod 9, weil 10 ≡ 1 mod 9, und damit a_{i} ·10^{i} ≡ a_{i} mod 9 und a_{r} ·10^{r} + … + a_{0} ≡ a_{r} + … + a_{0} mod 9. Also ist \overline{β(r)} = \overline{r} für alle r ∈ ℕ. Sei α die iterierte Quersummenbildung α(r) = β . . . . . . β(r), so oft iteriert, bis eine einstellige Zahl herauskommt. Dann gilt \overline{α(r)} = \overline{β … β(r)} = … = \overline{β(r)} = \overline{r}. Außerdem hat α das Bild {0, 1, 2, …, 9} = X. In X sind 2 Zahlen a und b genau dann kongruent modulo 9, wenn sie gleich sind oder 0 und 9 sind. Die Neunerprobe für die Multiplikation natürlicher Zahlen ergibt sich damit: die iterierte Quersumme des Produkts r · s stimmt mit der Quersumme des Produkts der iterierten Quersummen der einzelnen Faktoren überein, es sei denn, daß sich Resultate 0 und 9 ergeben.

(5) Die Abbildung β : ℤ ⟶ ℤ sei die sogenannte alternierende Quersumme, d.h. β(a_{r} ·10^{r} +…+a_{0}) = (−1)^{r}a_{r} +(−1)^{r−1}a_{r−1} + … + a_{0} auf ℕ und β(−r) := −β(r). Wegen −10 ≡ 1 mod 11 ergibt sich wie zuvor β(r) ≡ r mod 11. Sei α die iterierte alternierende Quersumme (stationär unter weiterer Quersummenbildung). Dann ist \overline{α(r)} = \overline{r} für alle r ∈ ℕ und die Bildmenge von α ist X = {−9, −8, −7 …, 0, 1, 2, …, 9}. Wieder gilt eine entsprechende Elferprobe für Summen und Produkte: α(r · s) ≡ α(α(r) · α(s)) mod 11.

(6) Schneidet man bei der Binärdarstellung einer natürlichen Zahl alle vorderen Stellen, bis auf die letzten 8 Stellen ab: α(a_{r} · 2^{r} + … + a_{1} · 2 + a_{0}) = a_{7} · 2^{7} + … + a_{1} · 2 + a_{0} mit a_{i} ∈ {0, 1}, so gilt wieder α(2^{8}) ≡ 0 mod 2^{8}, also \overline{α(r)} = \overline{r} in ℤ/(256).

Die Bildmenge von α ist X = {0, …, 255}. Damit ist X sogar ein vollständiges Repräsentantensystem für ℤ/(256) und es gilt α(α(r) · α(s)) = α(r · s), d.h. den Repräsentanten von \overline{r} · \overline{s} in X findet man durch Bestimmung des Repräsentanten in X von \overline{r · s}. Diese besonders einfache Bildung der Restklassen und Repräsentanten ist die Grundlage für die Rechenoperationen in CPUs z.B. in 8 Bit-Registern. Addition und Multiplikation kann man wie bei natürlichen Zahlen durchführen und dann die höherwertigen Stellen (die Überträge) fortlassen. Dann erhält man die Rechenregeln eines Ringes, z.B. ℤ/(256).

Definition 6.5. Ein Körper ist ein kommutativer Ring, bei dem die von 0 verschiedenen Elemente bei der Multiplikation eine Gruppe bilden.

Bemerkung 6.6. Sei R ein unitärer Ring. Eine Kongruenzrelation (R, R, S) (mit S ⊂ R ×R) auf R ist eine Äquivalenzrelation auf R, so daß S ein Unterring von R × R ist, d.h. sowohl eine Untergruppe von (R × R, +) als auch ein Untermonoid von (R × R, ·). Dann bilden die Äquivalenzklassen R/S wieder einen unitären Ring und ν : R ⟶ R/S ist ein Ringhomomorphismus. Weiter gilt der Faktorisierungssatz für unitäre Ringe: eine eindeutige Faktorisierung \overline{f} existiert mit

[figure: R; R/S; ν; f; R′; \overline{f}]

falls für alle (r, r′) ∈ S gilt f(r) = f(r′). Ähnlich wie wir bei Gruppen Kongruenzrelationen durch normale Untergruppen H ⊂ G beschrieben haben, können wir im Falle von unitären Ringen Kongruenzrelationen durch zweiseitige Ideale I ⊂ R beschreiben. Dabei heißt eine Teilmenge I ⊂ R ein zweiseitiges Ideal, wenn I eine Untergruppe von (R, +) ist und für alle r ∈ R und i ∈ I gilt ri, ir ∈ R. Aus einem zweiseitigen Ideal I ⊂ R gewinnt man eine Kongruenzrelation durch S := {(r, r′) ∈ R|r − r′ ∈ I} und umgekehrt erhält man aus einer Kongruenzrelation S auf R ein zweiseitiges Ideal durch I := {r − r′|(r, r′) ∈ S. Man schreibt dann auch R/S =: R/I. Die Elemente in R/I sind von der Form r + I = {r + i|i ∈ I. Die Addition und Multiplikation auf R/I ist definiert durch (r + I) + (r′ + I) := (r + r′) + I und (r + I) · (r′ + I) := r · r′ + I. Das gilt wegen \overline{r} + \overline{r′} = \overline{r + r′} und \overline{r} · \overline{r′} = \overline{r · r′}.

Satz 6.7. Für n ∈ ℕ_{0} ist ℤ/(n) genau dann ein Körper, wenn n eine Primzahl ist.

Beweis. Sei p = n eine Primzahl. Die Elemente von ℤ/(p) sind \{\overline{0}, \overline{1}, \overline{2}, …, \overline{p − 1}\}. Sei 0 < k < p. Dann gibt es a, b ∈ ℤ mit ak + bp = 1, weil k und p teilerfremd sind. Damit ist \overline{a} · \overline{k} = \overline{ak} + \overline{b} · \overline{p} = \overline{ak + bp} = \overline{1}, denn \overline{p} = \overline{0} in ℤ/(p), also ist \overline{a} invers zu \overline{k} und damit ℤ/(p) ein Körper. Sei jetzt n keine Primzahl. Ist n = 0, so ist \overline{2} ≠ ¯0. Wäre \overline{2} invertierbar, etwa \overline{1} = \overline{2} · \overline{a}, so wäre 1 ≡ 2a mod 0, also 2a = 1 in ℤ. Das ist aber nicht möglich. Ist n = 1, so hat ℤ/(1) genau ein Element. Aber ℤ/(1)∀\{\overline{0}\} = ∅ kann keine Gruppe sein. Ist schließlich n > 1, so muß n ein Produkt sein: n = ab, mit 1 < a < n, sonst wäre es eine Primzahl. Dann ist \overline{0} = \overline{n} = \overline{a}·\overline{b}, aber \overline{a} ≠ \overline{0} und \overline{b} ≠ 0. Wäre \overline{c} · \overline{a} = \overline{1}, so wäre \overline{0} = \overline{c} · \overline{0} = \overline{c} · \overline{a} · \overline{b} = \overline{1} · \overline{b} = \overline{b} im Widerspruch zu \overline{b} ≠ 0.

Beispiele 6.8. ℚ, ℝ, ℂ sind Körper, jedoch nicht ℕ und ℤ.

Bemerkung 6.9. Sei R ein unitärer Ring und X eine Menge. Dann ist Abb(X, R) = {α : X ⟶ R|α Abbildung} ein Ring mit den Operationen

(α + β)(x) := α(x) + β(x), (α · β)(x) := α(x) · β(x).

Es übertragen sich die algebraischen Eigenschaften von R auf R^{X} = Abb(X, R). So ist z.B. die Eins in R^{X} gegeben durch α(x) = 1 für alle x ∈ X. Ist R ein Körper, so ist R^{X} kein Körper, denn α ≠ 0 bedeutet nicht, daß α(x) ≠ 0 für alle x ∈ X(dann könnte man α^{−1}(x) = α(x)^{−1} definieren), sondern nur, daß es mindestens ein x ∈ X gibt mit α(x) ≠ 0. Wenn dann aber für ein weiteres y ∈ X gilt α(y) = 0, dann läßt sich α^{−1} an der Stelle y nicht sinnvoll definieren.

Definition 6.10. Sei 𝕂 der Körper ℚ, ℝ oder ℂ. Die Menge 𝕂[x] := {α : 𝕂 ⟶ 𝕂|∃a_{0}, …, a_{n} ∈ 𝕂∀b ∈ 𝕂[α(b) = a_{n}b^{n} + … + a_{1}b + a_{0}}] ist ein Unterring von 𝕂^{𝕂} und heißt Ring der Polynom(-funktionen) auf 𝕂. Wir schreiben ∑_{i=0}^{n} a_{i}x^{i} = a_{n}x^{n} + … + a_{1}x + a_{0} := α, wenn α(b) = a_{n}b^{n} + … + a_{1}b + a = 0 für alle b ∈ 𝕂. Die Addition ist gegeben durch ∑_{i=0}^{n} a_{i}x^{i} + ∑_{i=0}^{n} b_{i}x^{i} = ∑_{i=0}^{n}(a_{i} + b_{i})x^{i}, die Multiplikation durch ∑_{i=0}^{m} a_{i}x^{i} · ∑_{j=0}^{n} b_{j}x^{j} = ∑_{k=0}^{m+n} ∑_{i=0}^{k} a_{i}b_{k−i}x^{k}, wie man leicht nachrechnet.

Bemerkung 6.11. Außer den genannten Körpern ℚ, ℝ, ℂ und ℤ/(p) (p Primzahl) gibt es noch viele weitere. Insbesondere gibt es einen endlichen Körper mit n Elementen genau dann, wenn n von der Form p^{r} mit einer Primzahl p ist. Die endlichen Körper mit p^{r} Elementen heißen auch Galois-Felder GF (p^{r}). Sie werden insbesondere in der Codierungstheorie verwendet.

7. Boolesche Ringe und Algebren

Auch in der Potenzmenge einer Menge haben wir zwei Verknüpfungen betrachtet, den Durchschnitt ∩ und die Vereinigung ∪. Sie erfüllen etwas andere Gesetze, als wir sie für Ringe und Körper kennengelernt haben. Diese Gesetze sind jedoch besonders wichtig, weil man sie nicht nur in Potenzmengen findet, sondern auch bei Ausdrücken mit logischen Verknüpfungszeichen.

Definition 7.1. Sei (A, ∪, ∩,′) ein Quadrupel mit einer Menge A, binären Operationen ∪ : A × A ⟶ A und ∩ : A × A ⟶ A und einer 1-stelligen Operation ′ : A ⟶ A. Das Quadrupel (A, ∪, ∩,′) heißt eine Boolesche Algebra, wenn für alle a, b, c ∈ A gelten:

(1) (a ∪ b) ∪ c = a ∪ (b ∪ c), (a ∩ b) ∩ c = a ∩ (b ∩ c),

(2) a ∩ (b ∪ c) = (a ∩ b) ∪ (a ∩ c), a ∪ (b ∩ c) = (a ∪ b) ∩ (a ∪ c),

(3) a ∪ b = b ∪ a, a ∩ b = b ∩ a, (4) es gibt ein Element 0 ∈ A, so daß für alle a ∈ A gilt

0 ∪ a = a,

(5) es gibt ein Element 1 ∈ A, so daß für alle a ∈ A gilt 1 ∩ a = a,

(6) a ∪ a′ = 1, a ∩ a′ = 0.

Beispiele 7.2. (1) P(A), die Potenzmenge einer Menge A, zusammen mit der gewöhnlichen Vereinigung ∪, dem gewöhnlichen Durchschnitt ∩ und der Komplementbildung B′ := A \ B ist eine Boolesche Algebra.

(2) {0, 1} = B mit a ∪ b = max(a, b) und a ∩ b = min(a, b) ist eine Boolesche Algebra.

(3) P(A) mit B ∪ C = Durchschnitt (!) von B und C, B ∩ C = Vereinigung von B und C und B′ = A \ B ist eine Boolesche Algebra.

Satz 7.3. Für eine Boolesche Algebra (A, ∪, ∩,′) und Elemente a, b ∈ A gelten

(1) das Nullelement 0 und das Einselement 1 sind eindeutig bestimmt,

(2) a ∩ b = 0 ∧ a ∪ b = 1 ⟹ a′ = b,

(3) a′′ = a,

(4) 0′ = 1, 1′ = 0,

(5) a ∪ a = a = a ∩ a,

(6) a ∪ 1 = 1, a ∩ 0 = 0,

(7) a ∪ (a ∩ b) = a, a ∩ (a ∪ b) = a,

(8) (a ∪ b)′ = a′ ∩ b′, (a ∩ b)′ = a′ ∪ b′.

Beweis. (1) (A, ∪, 0) und (A, ∩, 1) sind Monoide.

(2) a′ = a′∪0 = a′∪(a∩b) = (a′∪a)∩(a′∪b) = 1∩(a′∪b) = a′∪b. Vertauscht man die Rollen von a′ und b, so erhält man b = a′ ∪b, also a′ = b.

(3) a′ ∪ a = 1 und a′ ∩ a = 0 impliziert nach (2) a′′ = a.

(4) Wegen 1 ∩ 0 = 0 und 1 ∪ 0 = 1 und (2) folgt 0′ = 1. Aus (3) folgt 0 = 0′′ = 1′.

(5) a∪a = (a∪a)∩1 = (a∪a)∩(a∪a′) = a∪(a∩a′) = a∪0 = a. Weiter ist a ∩ a = (a ∩ a) ∪ 0 = (a ∩ a) ∪ (a ∩ a′) = a ∩ (a ∪ a′) = a ∩ 1 = a.

(6) a∪1 = a∪a∪a′ = a∪a′ = 1 und a∩0 = a∩a∩a′ = a∩a′ = 0.

(7) a ∪ (a ∩ b) = (a ∪ a) ∩ (a ∪ b) = a ∩ (a ∪ b). Wir weisen jetzt a ∪ (a ∩ b) = a′′ nach. Es ist a ∪ (a ∩ b) ∪ a′ = 1 ∪ (a ∩ b) = 1 und (a ∪ (a ∩ b)) ∩ a′ = (a ∩ (a ∪ b)) ∩ a′ = 0 ∩ (a ∪ b) = 0, also ist nach (2) und (3) a ∪ (a ∩ b) = a′′ = a.

(8) Es ist (a′∩b′)∪a∪b = (a′∪a∪b)∩(b′∪a∪b) = (1∪b)∩(1∪a) = 1 ∪ 1 = 1 und a′ ∩ b′ ∩ (a ∪ b) = (a′ ∩ b′ ∩ a) ∪ (a′ ∩ b′ ∩ b) = (0 ∩ b′)∪(0∩a′) = 0∪0 = 0. Damit und mit (2) folgt (a∪b)′ = a′ ∩b′. Weiter folgt (a ∩ b)′ = (a′′ ∩ b′′)′ = (a′ ∪ b′)′′ = a′ ∪ b′.

Definition 7.4. Ein Ring R heißt ein Boolescher Ring, wenn gilt ∀r ∈ R[r^{2} = r].

Satz 7.5. Sei R ein Boolescher Ring. Dann ist R kommutativ, und es gilt ∀r ∈ R[r + r = 0].

Beweis. Für r, s ∈ R ist r +s = (r +s)^{2} = r^{2} +rs+sr +s^{2} = r+rs+sr+s ⟹ rs+sr = 0. Für s = r folgt r+r = r^{2}+r^{2} = 0. Damit ist r = −r und auch rs = −rs. Aus rs + sr = 0 folgt nun rs = sr.

Satz 7.6. (1) Sei (A, ∪, ∩,′) eine Boolesche Algebra. Dann ist (A, +, ·) ein Boolescher Ring mit

\begin{aligned}r + s & := (r ∩ s′) ∪ (r′ ∩ s) (= r△s), \\ r · s & := r ∩ s. \end{aligned}

(2) Sei (A, +, ·) ein Boolescher Ring. Dann ist (A, ∪, ∩,′) eine Boolesche Algebra mit

\begin{aligned}r ∪ s & := r + s + r · s, \\ r ∩ s & := r · s, \\ r′ & := 1 + r. \end{aligned}

Beweis. (1) 1. (a+b)+c = (((a∩b′)∪(a′∩b))∩c′)∪(((a∩b′)∪ (a′∩b))′∩c) = (a∩b′∩c′)∪(a′∩b∩c′)∪((a′∪b)∩(a∪b′)∩c) = (durch Auflösen des rechten Ausdrucks) (a∩b′∩c′)∪(a′∩b∩c′)∪(a′∩b′∩ c) ∪ (a ∩ b ∩ c) und ebenso wegen der Symmetrie des Ausdrucks a + (b + c) = (a ∩ b′ ∩ c′) ∪ (a′ ∩ b ∩ c′) ∪ (a′ ∩ b′ ∩ c) ∪ (a ∩ b ∩ c).

2. a + b = b + a, weil Vereinigung und Durchschnitt kommutativ sind.

3. a + 0 = (a ∩ 0′) ∪ (a′ ∩ 0) = (a ∩ 1) ∪ 0 = a, also existiert ein neutrales Element.

4. a+a = (a∩a′)∪(a′ ∩a) = 0, also existieren inverse Elemente.

5. (A, ·) ist ein Monoid.

6. (a + b) · c = ((a′ ∩ b) ∪ (a ∩ b′)) ∩ c = (a′ ∩ b ∩ c) ∪ (a ∩ b′ ∩ c) = (a∩c∩(b′∪c′))∪((a′∪c′)∩b∩c) = (a∩c∩(b∩c)′)∪((a∩)′∩b∩c) = a · c + b · c. Damit ist A ein Ring. Wegen a ∩ a = a = a · a ist A ein Boolescher Ring.

(2) 1. a ∪ b = a + b + a · b = b + a + b · a = b ∪ a.

2. (a ∪ b) ∪ c = (a + b + ab) + c + (a + b + ab)c = a + b + c + ab + ac + bc + abc = a + (b + c + bc) + a(b + c + bc) = a ∪ (b ∪ c).

3. 0 ∪ a = 0 + a + 0a = a.

4. a ∪ a′ = a + a′ + aa′ = a + 1 + a + a + a = 1 und a ∩ a′ = a(1 + a) = a + a = 0.

5. (A, ∩, 1) ist trivialerweise ein kommutatives Monoid.

6. a ∩ (b ∪ c) = a(b + c + bc) = ab + ac + abc = ab + ac + abac = (a∩b)∪(a∩c) und a∪(b∩c) = a+bc+abc = a+ab+ab+ac+bc+ abc+ac+abc+abc = (a+b+ab)(a+c+ac) = (a∪b)∩(a∪c).

Bemerkung 7.7. Tatsächlich erhält man wechselseitig aus den Strukturen der Booleschen Algebra und des Booleschen Ringes und beim zweimaligen Übergang die alten Strukturen zurück. Es ist nämlich a + b + ab = (((a ∩ b′) ∪ (a′ ∩ b)) ∩ (a ∩ b)) ∪ (((a ∩ b′) ∪ (a′ ∩b))′ ∩a∩b) = ((1∩(a∪b)∩(a′ ∪b′)∩1)∩(a′ ∪b′))∪((1∩(a∪ b) ∩ (a′ ∪ b′) ∩ 1)′ ∩ a ∩ b) = ((a ∪ b) ∩ (a′ ∪ b′)) ∪ (((a′ ∩ b′) ∪ (a ∩ b)) ∩ a ∩ b) = (a′ ∩ b) ∪ (a ∩ b′) ∪ (a′ ∩ b′ ∩ a ∩ b) ∪ (a ∩ b ∩ a ∩ b) = (a′ ∩ b) ∪ (a ∩ b′) ∪ (a ∩ b) = (a′ ∩ b) ∪ (a ∩ (b′ ∪ b)) = (a′ ∩ b) ∪ a = (a′ ∪ a) ∩ (a ∪ b) = 1 ∩ (a ∪ b) = a ∪ b. Weiter ist (a∩b′)∪(a′∩b) = a(1+b)+(1+a)b+a(1+b)(1+a)b = a + ab + b + ab + ab + ab + ab + ab = a + b. Schließlich ist 1 + a = (1′ ∩ a) ∪ (1 ∩ a′) = (0 ∩ a) ∪ a′ = 0 ∪ a′ = a′.

Bemerkung 7.8. Boolesche Algebren und Boolesche Ringe sind algebraische Strukturen. Es lassen sich Kongruenzrelationen und Restklassenstrukturen bilden. Der Faktorisierungssatz gilt. Jede Boolesche Algebra läßt sich als Restsklassenalgebra einer freien Booleschen Algebra darstellen, insbesondere durch Erzeugende und Relationen. Wenn A eine Boolesche Algebra ist, dann ist auch Abb(X, A) = A^{X} eine Boolesche Algebra mit komponentenweisen Operationen.

Man weiß viel über die Struktur von Booleschen Algebren. Besonders im endlichen Fall kann man diese Struktur vollständig beschreiben. Wir geben hier den entsprechenden Satz zur Information an, ohne allerdings den Beweis durchzuführen.

Satz 7.9. Jede endliche Boolesche Algebra ist isomorph zur Booleschen Algebra auf der Potenzmenge P(M) einer endlichen Menge M. Sie ist außerdem isomorph zu einer Booleschen Algebra der Form B^{n}, wobei B = {0, 1} die Struktur einer Booleschen Algebra wie in Beispiel 7.2 (2) trägt.

Definition 7.10. Sei A eine Boolesche Algebra. Eine Abbildung f ∈ Abb(A^{n}, A) aus der Booleschen Algebra Abb(A^{n}, A) heißt Boolesche Funktion mit Werten in A. Wir schreiben f = f(x_{1}, …, x_{n}). Die Booleschen Funktionen x_{i} : A×…×A ∋ (a_{1}, …, a_{n}) ↦ a_{i} ∈ A heißen Projektionen (oder Variable), die Booleschen Funktionen A×…×A ∋ (a_{1}, …, a_{n}) ↦ b ∈ A für festes b ∈ A konstante Abbildungen. Da sie in der Booleschen Algebra Abb(A^{n}, A) liegen, kann man die kleinste von den Konstanten b ∈ A und den Variablen x_{1}, …, x_{n} (mit ∪, ∩, ′) erzeugte Boolesche Unteralgebra A[x_{1}, …, x_{n}] ⊂ Abb(A^{n}, A) bilden. A[x_{1}, …, x_{n}] heißt Boolesche Algebra der Polynomfunktionen.

Bemerkung 7.11. Die freie Boolesche Algebra über den Erzeugenden X_{1}, …, X_{n} mit Konstanten A ist A[X_{1}, …, X_{n}], die Algebra der formalen Ausdrücke, die mit Elementen a ∈ A, X_{1}, …, X_{n}, ∪, ∩ und ′ gebildet werden können modulo den Relationen für Boolesche Algebren, heißt Boolesche Algebra der Polynome über A. Die Abbildung X_{i} ↦ x_{i} induziert einen Homomorphismus von Booleschen Algebren

A[X_{1}, …, X_{n}] ⟶ A[x_{1}, …, x_{n}].

Man unterscheidet daher Polynome und Polynomfunktionen.

Satz 7.12. (1) Zu jeder Booleschen Polynomfunktion

f : A^{n} ⟶ A

gibt es genau eine disjunktive Normalform

f(x_{1}, …, x_{n}) = ⋃_{(i_{1},... ,i_{n})} a_{i_{1},... ,i_{n}} ∩ x_{1}^{i_{1}} ∩ … ∩ x_{n}^{i_{n}}

mit i_{j} ∈ {1, −1}, wobei x_{i}^{1} = x_{i} und x_{i}^{−1} = x′_{i} sei.

(2) Zu jeder Booleschen Polynomfunktion f : A^{n} ⟶ A gibt es genau eine konjunktive Normalform

f(x_{1}, …, x_{n}) = ⋂_{(i_{1},... ,i_{n})} a_{i_{1},... ,i_{n}} ∪ x_{1}^{i_{1}} ∪ … ∪ x_{n}^{i_{n}}

mit i_{j} ∈ {1, −1}.

Beweis. Wir beweisen lediglich Teil (1) des Satzes. Zunächst weisen wir die Existenz einer disjunktiven Normalform nach. Wenn eine Polynomfunktion f gegeben ist, so wenden wir eventuell mehrfach die Gleichungen von Satz 7.3 (2) an, um die Bildung des Komplements auf die einzelnen Konstanten oder Variablen zu ziehen. Dann verwenden wir das Distributivgesetz 7.1 (2) i), um den Durchschnitt ∩ nach innen auf die einzelnen Konstanten und Variablen zu ziehen. Wegen der Kommutativität und 7.3 (3) erhalten wir einen Ausdruck wie in der disjunktiven Normalform, jedoch ist es möglich, daß nicht alle Terme a_{i_{1},... ,i_{n}} ∩ x_{1}^{i_{1}} ∩ … ∩ x_{n}^{i_{n}} mit allen Variablen x_{1}, …, x_{n} auftreten. In diesem Falle bekommt man die fehlenden Variablen x_{i}, indem man den entsprechenden Ausdruck mit 1 = x_{i} ∪x′_{i} schneidet und den obigen Prozeß wiederholt. Zuletzt fasse man Ausdrücke mit gleichen Komponenten x_{1}^{i_{1}} ∩ … ∩ x_{n}^{i_{n}} zusammen, indem man die zugehörigen Konstanten a_{i_{1},... ,i_{n}} und b_{i_{1},... ,i_{n}} in A vereinigt. Das ergibt die gewünschte Normalform. Um die Eindeutigkeit der disjunktiven Normalform zu zeigen, wählen wir ein n-Tupel (k_{1}, …, k_{n}) und setzen wir in

f(x_{1}, …, x_{n}) = ⋃ a_{i_{1},... ,i_{n}} ∩ x_{1}^{i_{1}} ∩ … ∩ x_{n}^{i_{n}}

Argumente I_{1}, …, I_{n} ein mit

I_{j} = \begin{cases}1, falls k_{j} = 1, \\ 0, falls k_{j} = −1. \end{cases}

Dann verschwinden alle Terme der disjunktiven Normalform, bis auf den Term zum Index (k_{1}, …, k_{n}). Wir erhalten damit f(I_{1}, …, I_{n}) = a_{k_{1},... ,k_{n}}. Man kann also aus f allein die ”Koeffizienten“ der disjunktiven Normalform erhalten. Diese ist damit eindeutig. Hinweis zur Gewinnung der Koeffizienten a_{i_{1},... ,i_{n}} in den Normalformen aus der gegebenen Polynomfunktion. Es ist durch Einsetzen ersichtlich, daß für

I_{j} = \begin{cases}1, falls i_{j} = 1, \\ 0, falls i_{j} = −1, \end{cases}

in der disjunktiven Normalform gilt a_{i_{1},... ,i_{n}} = f(I_{1}, …, I_{n}). In der konjunktiven Normalform setze man

I_{j} = \begin{cases}0, falls i_{j} = 1, \\ 1, falls i_{j} = −1, \end{cases}

ein und erhält a_{i_{1},... ,i_{n}} = f(I_{1}, …, I_{n}).

Beispiel 7.13. Die disjunktive Normalform von (x_{1} ∪x_{2})∩(x_{1} ∩ x′_{2}) ist 1 ∩ x_{1} ∩ x′_{2}, weil f(0, 0) = f(0, 1) = f(1, 1) = 0 und f(1, 0) = 1 ist. Tatsächlich ist

\begin{matrix}(x_{1} ∪ x_{2}) ∩ (x_{1} ∩ x′_{2}) = (x_{1} ∩ x_{1} ∩ x′_{2}) ∪ (x_{2} ∩ x_{1} ∩ x′_{2} = \\ (x_{1} ∩ x′_{2}) ∪ 0 = x_{1} ∩ x′_{2} = 1 ∩ x_{1} ∩ x′_{2}. \end{matrix}

Boolesche Polynome stellen eine besonders einfache Klasse von Booleschen Funktionen dar. In einem Spezialfall fallen diese beiden Begriffe jedoch sogar zusammen. Wir formulieren hier nur den entsprechenden Satz ohne Beweis.

Satz 7.14. Ist B = {0, 1}, so ist jede Boolesche Funktion in Abb(B^{n}, B) ein Boolesches Polynom.

Bemerkung 7.15. (über Gatter) Eine (technische Realisierung einer) Booleschen Funktion f : B^{n} ⟶ B mit B = {0, 1} heißt ein Gatter.

f(x_{1}, …, x_{n}) = x_{1} ∩ x_{2} ∩ … ∩ x_{n} heißt UND-Gatter,
f(x_{1}, …, x_{n}) = x_{1} ∪ x_{2} ∪ … ∪ x_{n} heißt ODER-Gatter,
f : B ⟶ B mit f(x) = x′  heißt NICHT-Gatter

oder Inverter,

f(x_{1}, …, x_{n}) = (x_{1} ∩ x_{2} ∩ … ∩ x_{n})′ heißt NAND-Gatter,
f(x_{1}, …, x_{n}) = (x_{1} ∪ x_{2} ∪ … ∪ x_{n})′ heißt NOR-Gatter,
f(x_{1}, x_{2}) = (x_{1} ∪ x_{2})′ = x_{1} ↓ x_{2}  heißt Pierce-Gatter,
f(x_{1}, x_{2}) = (x_{1} ∩ x_{2})′ = x_{1}|x_{2}  heißt Sheffer-Gatter.

Die zugehörigen Gatter-Symbole sind:

US Norm:

[figure: And; Or; Not; Sheffer]

Deutsche Norm:

[figure: Und; Oder; Nicht; Sheffer]

Eine Parallelschaltung von Eingängen von Gattern wird als doppelte Anwendung derselben Variablen angesehen, z.B. sind mit (f(x_{1}, x_{2}), g(x_{1}, x_{3})) zwei Eingänge x_{1} der beiden Gatter f und g parallel geschaltet. Eine Serienschaltung von Gattern wird als Einsetzen einer Funktion in eine andere Funktion angesehen. So ist z.B.

(x_{1} ∪ x_{2}) ∩ (x_{1} ∩ x′_{2})

realisierbar durch die folgende Zusammenschaltung von Gattern

[figure]

Da jede Boolesche Funktion in Abb(B^{n}, B) eine Polynomfunktion ist, läßt sie sich durch Gatter darstellen. Die Sheffer-Operation stellt alle Booleschen Funktionen dar, denn sei a \ b = (a ∩ b). Dann gelten

\begin{aligned}x′_{1} & = (x_{1} ∩ x_{1})′ = x_{1}|x_{1}, \\ x_{1} ∩ x_{2} & = ((x_{1} ∩ x_{2})′ ∪ (x_{1} ∩ x_{2})′)′ = (x_{1}|x_{2})|(x_{1}|x_{2}), \\ x_{1} ∪ x_{2} & = ((x_{1} ∩ x_{1})′ ∪ (x_{2} ∩ x_{2})′)′ = (x_{1}|x_{1})|(x_{2}|x_{2}). \end{aligned}

Ebenso lassen sich alle Gatter in eindeutiger Weise mit Hilfe der disjunktiven bzw. konjunktiven Normalform darstellen.