Allgemeine Algebra WS 2004/05

für Informatiker und Wirtschaftsinformatiker

von Prof. Thomas Ihringer

Simon Fuhrmann · Christian M. Meyer Christian Schäck

27. April 2005

Vorbemerkungen: Dieses Skript beschäftigt sich mit strukturellen Grundlagen der Mathematik, nämlich solchen aus den Bereichen

• Kapitel 0: Grundlagen (Mengensprache, Kombinatorik, Beweistechniken)

• Kapitel 1: Diskrete Mathematik (kombinatorischen Strukturen)

• Kapitel 2: Algebra (algebraischen Strukturen)

• Kapitel 3: Logik (logischen Strukturen)

Hierzu können, in der Reihenfolge dieser Kapitel, die folgenden Bücher als ”Basis“ dienen. Aber das Skript enthält alles Wesentliche, und außerdem gibt es viele andere passende Bücher (worüber sich jeder Interessierte selbst informieren möge):

• Christoph Meinel, Martin Mundhenk: Mathematische Grundlagen der Informatik. Teubner, Stuttgart, 2002.

• Thomas Ihringer: Diskrete Mathematik.

Heldermann, Lemgo, 2002

• Thomas Ihringer: Allgemeine Algebra.

Heldermann, Lemgo, 2003

• Uwe Schöning: Logik für Informatiker.

Spektrum, Heidelberg, 2002

Inhaltsverzeichnis

0 Grundlagen 1

0.1 Mengen, Relationen, Abbildungen . . . . . . . . . . . . . . . . . 1 0.1.1 Operationen auf Mengen . . . . . . . . . . . . . . . . . . . 1 0.1.2 Das kartesische Produkt . . . . . . . . . . . . . . . . . . . 1 0.1.3 Relationen . . . . . . . . . . . . . . . . . . . . . . . . . . 2 0.1.4 Äquivalenzrelationen . . . . . . . . . . . . . . . . . . . . . 2 0.1.5 Ordnungsrelationen . . . . . . . . . . . . . . . . . . . . . 2 0.1.6 Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . 4 0.1.7 Injektivität, Surjektivität, Bijektivität . . . . . . . . . . . 5 0.1.8 Russel’sches Paradoxon . . . . . . . . . . . . . . . . . . . 5

0.2 Kombinatorik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 0.2.1 Die Kardinalität von Mengen . . . . . . . . . . . . . . . . 6 0.2.2 Additionsprinzip . . . . . . . . . . . . . . . . . . . . . . . 6 0.2.3 Multiplikationsprinzip . . . . . . . . . . . . . . . . . . . . 7 0.2.4 Gleichheitsprinzip . . . . . . . . . . . . . . . . . . . . . . 7 0.2.5 Prinzip der doppelten Abzählung . . . . . . . . . . . . . . 7 0.2.6 Teilmengen endlicher Mengen . . . . . . . . . . . . . . . . 8 0.2.7 k-Teilmengen endlicher Mengen . . . . . . . . . . . . . . . 8 0.2.8 Die Binomische Formel . . . . . . . . . . . . . . . . . . . 10 0.2.9 Binomialrekursion . . . . . . . . . . . . . . . . . . . . . . 10 0.2.10 Permutationen . . . . . . . . . . . . . . . . . . . . . . . . 12 0.2.11 Multimengen . . . . . . . . . . . . . . . . . . . . . . . . . 12 0.2.12 Zählen von Abbildungen . . . . . . . . . . . . . . . . . . . 13

0.3 Beweismethoden . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 0.3.1 Direkter Beweis . . . . . . . . . . . . . . . . . . . . . . . . 14 0.3.2 Beweis durch Kontraposition . . . . . . . . . . . . . . . . 15 0.3.3 Widerspruchsbeweis . . . . . . . . . . . . . . . . . . . . . 15 0.3.4 Äquivalenzbeweis . . . . . . . . . . . . . . . . . . . . . . . 16 0.3.5 Fallunterscheidung . . . . . . . . . . . . . . . . . . . . . . 16 0.3.6 Vollständige Induktion . . . . . . . . . . . . . . . . . . . . 16

1 Diskrete Mathematik 19

1.1 Graphen: Beispiele und Grundlagen . . . . . . . . . . . . . . . . 19 1.1.1 Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.1.2 Isomorphismen . . . . . . . . . . . . . . . . . . . . . . . . 20 1.1.3 Knotengrad . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.1.4 Kantenzüge . . . . . . . . . . . . . . . . . . . . . . . . . . 22 1.1.5 Zusammenhängende Graphen . . . . . . . . . . . . . . . . 23

1.2 Bäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.2.1 Wälder . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.2.2 Wurzelbäume . . . . . . . . . . . . . . . . . . . . . . . . . 24 1.2.3 Binäre Bäume . . . . . . . . . . . . . . . . . . . . . . . . 25

1.3 Abstände in (ungerichteten, unbewerteten) Graphen . . . . . . . 26 1.3.1 Länge von Kantenzügen . . . . . . . . . . . . . . . . . . . 26 1.3.2 Algorithmus von Moore . . . . . . . . . . . . . . . . . . . 26 1.3.3 Inzidenzmatrizen . . . . . . . . . . . . . . . . . . . . . . . 28 1.3.4 Gerichtete Graphen . . . . . . . . . . . . . . . . . . . . . 29

1.4 Abstände in Netzwerken . . . . . . . . . . . . . . . . . . . . . . . 29 1.4.1 Netzwerke . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.4.2 Der Abstandsbegriff . . . . . . . . . . . . . . . . . . . . . 30 1.4.3 Algorithmus von Dijkstra . . . . . . . . . . . . . . . . . . 30

1.5 Flüsse in Netzwerken . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.5.1 Flussnetzwerke . . . . . . . . . . . . . . . . . . . . . . . . 31 1.5.2 Maximale Flüsse, zunehmende Wege . . . . . . . . . . . . 32 1.5.3 Augmenting Path Theorem . . . . . . . . . . . . . . . . . 33 1.5.4 Minimaler Schnitt . . . . . . . . . . . . . . . . . . . . . . 34 1.5.5 Max-Flow Min-Cut Theorem . . . . . . . . . . . . . . . . 34 1.5.6 Markierungs-Algorithmus (Ford-Fulkerson) . . . . . . . . 35

1.6 Gruppen und Permutationen . . . . . . . . . . . . . . . . . . . . 37 1.6.1 Gruppen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 1.6.2 Links- und Rechtsnebenklassen . . . . . . . . . . . . . . . 38 1.6.3 Satz von Lagrange . . . . . . . . . . . . . . . . . . . . . . 38 1.6.4 Permutationsgruppen . . . . . . . . . . . . . . . . . . . . 39

1.7 Symmetrien von Graphen . . . . . . . . . . . . . . . . . . . . . . 40 1.7.1 Automorphismen . . . . . . . . . . . . . . . . . . . . . . . 41 1.7.2 Automorphismengruppe . . . . . . . . . . . . . . . . . . . 41 1.7.3 Bestimmung der Automorphismengruppe . . . . . . . . . 42

1.8 Die Pólyasche Abzählmethode . . . . . . . . . . . . . . . . . . . . 43 1.8.1 Cauchy-Frabenius-Lemma . . . . . . . . . . . . . . . . . . 44 1.8.2 Färbung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 1.8.3 Permutationstypen . . . . . . . . . . . . . . . . . . . . . . 45 1.8.4 Satz von Pólya . . . . . . . . . . . . . . . . . . . . . . . . 48

2 Algebraische Strukturen 49

2.1 Algebraische Strukturen: Beispiele . . . . . . . . . . . . . . . . . 49 2.1.1 Operationen . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.1.2 Halbgruppen . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.1.3 Monoide . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.1.4 Gruppen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.1.5 Ringe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.1.6 Körper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.1.7 Vektorräume . . . . . . . . . . . . . . . . . . . . . . . . . 54

2.2 Allgemeine Algebren . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.2.1 Ähnlichkeitstyp, allgemeine Algebren . . . . . . . . . . . . 55 2.2.2 Unteralgebren . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.2.3 Hüllensysteme, Hüllenoperatoren, Verbände . . . . . . . . 58 2.2.4 Das direkte Produkt . . . . . . . . . . . . . . . . . . . . . 64 2.2.5 Kongruenzrelation . . . . . . . . . . . . . . . . . . . . . . 65 2.2.6 Homomorphismen . . . . . . . . . . . . . . . . . . . . . . 70

2.3 Der Homomorphiesatz der Allgemeinen Algebra . . . . . . . . . . 71 2.4 Terme und Polynome . . . . . . . . . . . . . . . . . . . . . . . . . 73

2.4.1 Terme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 2.4.2 Termfunktionen . . . . . . . . . . . . . . . . . . . . . . . . 75 2.4.3 Polynome . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

2.5 Gleichungen, freie Algebren, Gleichungstheorie . . . . . . . . . . 76 2.5.1 Gleichungen . . . . . . . . . . . . . . . . . . . . . . . . . . 77 2.5.2 Gleichungstheorien . . . . . . . . . . . . . . . . . . . . . . 77 2.5.3 Frei erzeugte Algebren . . . . . . . . . . . . . . . . . . . . 78

2.5.4 Hauptsätze der Gleichungstheorie . . . . . . . . . . . . . . 79 2.6 Boolesche Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . 80

2.6.1 Atome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 2.6.2 Boolsche Terme . . . . . . . . . . . . . . . . . . . . . . . . 84

3 Logik 87 3.1 Aussagenlogik und boolesche Algebra . . . . . . . . . . . . . . . . 87 3.2 Aussagenlogik: Elementare Grundbegriffe . . . . . . . . . . . . . 88

3.2.1 Syntax der Aussagenlogik . . . . . . . . . . . . . . . . . . 89 3.2.2 Semantik der Aussagenlogik . . . . . . . . . . . . . . . . . 89 3.2.3 Modelle, Gültigkeit, Erfüllbarkeit . . . . . . . . . . . . . . 89

3.3 Prädikatenlogik erster Stufe . . . . . . . . . . . . . . . . . . . . . 90 3.3.1 Syntax der Prädikatenlogik . . . . . . . . . . . . . . . . . 90 3.3.2 Semantik der Prädikatenlogik, 1. Teil . . . . . . . . . . . . 91 3.3.3 Semantik der Prädikatenlogik, 2. Teil . . . . . . . . . . . . 91

Abbildungsverzeichnis 93

Index 94

0 Grundlagen

Dieses Kapitel beschäftigt sich mit der für die moderne Mathematik als Sprachmittel grundlegenden Mengensprache, mit einigen damit verbundenen kombinatorischen Sachverhalten sowie mit elementaren Beweistechniken.

0.1 Mengen, Relationen, Abbildungen

Der Begründer der Mengenlehre war Ende des 19. Jahrhunderts Georg Cantor. Er verwendete folgende recht informelle Definition:

Unter einer Menge verstehen wir jede Zusammenfassung von bestimmten wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens (welche die Elemente der Menge genannt werden) zu einem Ganzen.

Dieser Gedanke war bahnbrechend für die moderne Mathematik, weil er eine einheitliche formale Sprache begründete. Aber er stellte sich als zu ”naiv“ heraus. Dazu später mehr!

0.1.1 Operationen auf Mengen

Zunächst einige elementare Tatsachen über Mengen. Es gibt eine Reihe wichtiger Operationen auf Mengen, mit denen man aus bekannten Mengen (z.B. A und B) neue Mengen erhält. Beispielsweise:

A ∪ B := {x | x ∈ A oder x ∈ B} Vereinigung von A und B
A ∩ B := {x | x ∈ A und x ∈ B} (Durch-)Schnitt von A und B
P(A) := {X | X ⊆ A}  Potenzmenge von A

Man kann Eigenschaften verwenden, um aus bekannten Mengen neue Mengen zu erhalten. Ein Beispiel für ℕ (Menge der natürlichen Zahlen):

ℕ_{g} := {n ∈ ℕ | 2 teilt n}  Menge der geraden natürlichen Zahlen

0.1.2 Das kartesische Produkt

Eine allgemeine Konstruktion für beliebige Mengen A_{1}, …, A_{n} enthält alle n-Tupel (a_{1}, …, a_{n}) mit a_{1} ∈ A_{1}, …, a_{n} ∈ A_{n}:

A_{1} × … × A_{n} := {(a_{1}, …, a_{n}) | a_{i} ∈ A_{i}}

Dies ist das direkte (oder kartesische) Produkt der Mengen A_{i}.

Im Sonderfall A_{1} = ⋯ = A_{n} = A ergibt dies

A^{n} := A × ⋯ × A

die n-te Potenz von A.

0.1.3 Relationen

Jede Teilmenge R ⊆ A_{1} × ⋯ × A_{n} wird eine n-stellige Relation zwischen den Mengen A_{i} genannt. Mathematische Relationen sind überall, sogar im ”wirklichen“ Leben:

Beispiel: Sei

A_{1} := Menge aller Darmstädter Haltestellen, A_{2} := Menge aller Darmstädter Bus- und Bahnlinien, A_{3} := Menge aller möglichen Endstationen, A_{4} := Menge aller möglichen Abfahrtszeiten

(z.B. A_{4} = {0.00, 0.01, 0.02, …, 23.59}).

Die Fahrpläne sämtlicher Haltestellen können (zum Beispiel) in einer Relation R ⊆ A_{1} ×A_{2} ×A_{3} ×A_{4} zusammengefasst werden. Hierzu ein mögliches Element von R (ohne Gewähr!):

Station  Linie Endstation Abfahrtszeit ; (Hofgasse, 8,  Alsbach,  19.02) ∈ R

Bemerkung: Relationen können das Grundmaterial von Datenbanken bilden. In obigem Beispiel sollte es eine Datenbankoperation geben, die zum Beispiel alle Direktverbindungen von Hofgasse nach Eberstadt zwischen 19 und 20 Uhr findet, also etwa die Menge:

{(a_{1}, a_{2}, a_{3}, a_{4}) | a_{1} = Hofgasse, a_{3} = Eberstadt ∨ Alsbach, 19.00 ≤ a_{4} ≤ 20.00}

Besonders wichtig sind binäre (das heißt 2-stellige) Relationen von der Form R ⊆ A^{2}, also binäre Relationen auf einer Menge A. Nachfolgend zwei bedeutende Typen solcher Relationen:

0.1.4 Äquivalenzrelationen

Sei A eine beliebige Menge. Eine Teilmenge R ⊆ A^{2} heißt Äquivalenzrelation auf A, falls folgendes gilt: Für alle a, b, c, ∈ A (wie üblich wird xRy anstelle von (x, y) ∈ R geschrieben)

(Refl) aRa  Reflexivität
(Sym) aRb ⇒ bRa  Symmetrie
(Trans) aRb und bRc ⇒ aRc Transitivität

0.1.5 Ordnungsrelationen

Eine Teilmenge R ⊆ A^{2} heißt Ordnung oder Ordnungsrelation auf A (und das Paar (A, R) eine geordnete Menge), falls für alle a, b, c ∈ A die folgenden Axiome gelten:

(Refl) aRa  Reflexivität
(Anti) aRb und bRa ⇒ a = b Antisymmetrie
(Trans) aRb und bRc ⇒ aRc Transitivität

Beispiel (a): Jede Relation der Form R = {(a, a) | a ∈ A} (genannt Gleichheitsrelation auf A) ist trivialerweise eine Äquivalenzrelation und eine Ordnungsrelation (in der nichts geordnet ist),

Beispiel (b): Äquivalenzrelationen beschreiben oft, dass gewisse Objekte bezüglich bestimmter Eigenschaften gleich sind. Sei zum Beispiel A die Menge aller Informatikstudenten an der TUD, die im Herbst 2005 ihr Vordiplom abschließen. Für a, b ∈ A sei

aRb :⇔ a und b haben die selbe Vordiplomsnote in Mathematik.

Dann ist R eine Äquivalenzrelation auf A.

Beispiel (c): Für x, y ∈ ℤ, sei xRy :⇔ 2 teilt x − y. Dann ist R eine Äquivalenzrelation. Sie hat zwei Äquivalenzklassen (nämlich Teilmengen von ℤ maximaler Größe, die aus paarweise äquivalenten Elementen bestehen):

[0]_{R} := {x ∈ ℤ | xR0} = {…, −4, −2, 0, 2, 4, …} (gerade Zahlen)
[1]_{R} := {x ∈ ℤ | xR1} = {…, −3, −1, 1, 3, 5 …} (ungerade Zahlen)

Ohne formale Definition: Die Äquivalenzklassen jeder Äquivalenzrelation bilden eine Partition der Grundmenge A, das heißt sie sind paarweise disjunkt und ihre Vereinigung ist ganz A.

Beispiel (d): Jetzt eine vielleicht auf den ersten Blick umständlich definierte Ordnungsrelation: Die Schüler einer Klasse haben folgende Noten (andere Fächer werden der Einfachheit halber nicht betrachtet):

Adam Bernd Chris Doris Emma Ferdi
Deutsch  2  3  3  5  4  1
Mathematik  2  2  2  3  4  5

Für alle Schüler x gelte xRx und für je zwei verschiedene Schüler x und y werde definiert:

xRy :⇔ x hat in keinem Fach eine schlechtere Note als y

und in mindestens einem Fach eine bessere Note.

Dann ist R eine Ordnungsrelation. Sie kann durch ein Hasse-Diagramm (auch: Liniendiagramm) dargestellt werden. Eine Linie aufwärts von x nach y heißt: xRy, und kein Element dazwischen.

[figure: d; e; b; c; f; a]

Abbildung 1: Liniendiagramm Beispiel (e): Für jede Menge M ist (P(M), ⊆) eine geordnete Menge: Die Teilmengen von M, geordnet durch Inklusion.

Bemerkung: Für Ordnungsrelationen wird sehr oft ≤ geschrieben, statt R oder anderen Symbolen; ≤ wird ”kleiner gleich“ gelesen.

Die folgende Sorte von Relationen ist sehr wichtig:

0.1.6 Abbildungen

Definition: Eine Abbildung (oder Funktion) ist ein Tripel (A, B, f), bestehend aus einer Menge A (dem Definitionsbereich oder Urbild), eine Menge B (dem Wertebereich) und einer 2-stelligen Relation f ⊆ A × B mit:

(Abb) ∀x ∈ A ˙∃y ∈ B: (x, y) ∈ f

Lies: ”Für jedes x ∈ A existiert genau ein y ∈ B mit…“. Man nennt ∀ einen Allquantor, ∃ einen Existenzquantor, und der Punkt, ˙∃, bedeutet ”genau ein“.

Man nennt f eine Abbildung von A nach B und schreibt dafür kurz f: A ⟶ B. Statt (x, y) ∈ f wird üblicherweise f(x) = y geschrieben, und y heißt das Bild von x, und x das Urbild von y (möglicherweise nicht das einzige). Die Menge aller Bilder von f heißt der Bildbereich von f, kurz f(A) oder auch:

bild(f) := {f(x) | x ∈ A}

Beispiel: Sei A = {1, 2, 3, 4}, B = {a, b, c}, f = {(1, a), (2, a), (3, c), (4, a)}. Das ist eine Abbildung f: A ⟶ B mit bild(f) = {a, c}.

[figure: 1; 2; 3; 4; A; a; b; c; B; Wertetabelle von f:; \begin{matrix}x & 1 & 2 & 3 & 4 \\ f(x) & a & a & c & a \end{matrix}]

Abbildung 2: Pfeildiagramm von f

In der Wertetabelle wird die vollständige Information im Grunde in der unteren Zeile gegeben: Wenn die Reihenfolge 1, 2, 3, 4 der Urbildelemente vorgegeben ist, wird f durch das 4-Tupel (a, a, c, a) beschrieben. In derselben Weise entspricht jede Abbildung f: A ⟶ B einem

A-Tupel (f(x))_{x∈A} ∈ B^{A}

und jedes Tupel in B^{A} entspricht einer Abbildung A in B. Also:

Die Menge aller Abbildungen f: A ⟶ B kann als B^{A} geschrieben werden.

Weitere wichtige, hoffentlich schon vertraute Begriffe:

0.1.7 Injektivität, Surjektivität, Bijektivität

Definition: Eine Abbildung f: A ⟶ B heißt

(i) injektiv, falls ∀x, y ∈ A: f(x) = f(y) ⟹ x = y,
(ii) surjektiv falls ∀y ∈ B∃x ∈ A: f(x) = y,
(iii) bijektiv, falls sie injektiv und surjektiv ist.

Beispiel (a): Die Funktion f: A ⟶ B aus Abbildung 2 ist weder injektiv noch surjektiv.

Beispiel (b): Sei f: ℝ ⟶ ℝ, f(x) := x^{2}. Diese Abbildung ist weder injektiv noch surjektiv. Aber mit abgeändertem Definitions- oder Wertebereich lässt sich das ändern, ohne die Abbildungsvorschrift zu ändern.

Beispielsweise ist die Abbildung g: ℝ ⟶ ℝ_{0}^{+}, g(x) := x^{2} (Einschränkung des Wertebereichs auf die nichtnegativen reellen Zahlen) surjektiv, aber immer noch nicht injektiv. Mit ähnlichen Einschränkungen lassen sich aus f auch injektive, nicht surjektive oder bijektive Abbildungen gewinnen.

[figure: 1; −1; 1; f(x) = x^{2}]

Abbildung 3: Injektivität, Surjektivität, Bijektivität

0.1.8 Russel’sches Paradoxon

Zum Abschluss dieses Abschnitts noch einmal zu Cantors Mengendefinition: Nach Cantor ist sicherlich

A := {X | X ist eine Menge}

eine Menge, nämlich die Menge aller Mengen. Sicherlich sollte es immer möglich sein, mit Hilfe bestimmter Eigenschaften für die Elemente einer vorhandenen Menge, Teilmengen dieser Mengen zu gewinnen. Dem entsprechend sollte, wenn A eine Menge ist, auch die Gesamtheit

B := {X ∈ A | X ∉ X}

die Menge aller Mengen, die sich selbst nicht als Element enthalten, eine Menge sein. Enthält B sich selbst als Element? Es gibt zwei Möglichkeiten, die beide zu einem Widerspruch führen:

Fall 1: B ∈ B Nach Definition folgt sofort B ∉ B Fall 2: B ∉ B Doch das impliziert B ∈ B! ⚡

Dieser Widerspruch wird Russellsches Paradoxon genannt, nach seinem Entdecker, dem Philosophen und Mathematiker Bertrand Russell.

Randbemerkung: Natürlich gibt es solche ”Gesamtheiten“ wie die ”Gesamtheit aller Mengen“. Solche Gesamtheiten werden Klassen genannt. Alle Mengen sind auch Klassen, aber nicht bei allen Klassen handelt es sich um Mengen. Faustregel: Mengen müssen rein mengensprachlich mit Hilfe schon bekannter Mengen definierbar sein.

0.2 Kombinatorik

In der Kombinatorik beschäftigt man sich mit der Bestimmung der Elementzahlen verschiedener (endlicher) Mengen. Dabei werden verschiedenste Zähltechniken verwendet. Ein typisches Zählproblem: Wieviele Elemente hat die Potenzmenge (= Menge aller Teilmengen) einer gegebenen endlichen Menge?

0.2.1 Die Kardinalität von Mengen

Definition: Die Anzahl der Elemente einer Menge A heißt die Kardinalität (oder Mächtigkeit) von A, in Zeichen: |A|. Beispielsweise gilt:

\begin{matrix}|∅| = 0 & |\{1, 2, 3\}| = |\{x, □, 5\}| = 3 \\ |\{1, 2, …, 100\}| = 100 & |\{100, 102, 104, …, 200\}| = 51 \end{matrix}

Für endliche Mengen ist klar, was obige Definition bedeutet. Für unendliche Mengen ist die Situation komplizierter. Die folgenden wichtigen Tatsachen gelten für beliebige Mengen A und B (werden aber hier nicht näher erläutert oder bewiesen):

Satz:

(a) Für zwei Mengen A und B gilt genau dann |A| = |B|, wenn es eine bijektive Abbildung f: A ⟶ B gibt.

(b) Für jede Menge A gilt: |A| < |P(A)|.

Bemerkungen:

(a) Die Menge ℚ der rationalen Zahlen hat scheinbar ”unendlich mal soviele“ Elemente wie die Menge der natrülichen Zahlen. Dennoch gilt (überraschenderweise) |ℚ| = |ℕ|.

(b) Es gilt |ℚ| < |ℝ|, das heißt ℚ ist abzählbar unendlich. (Und es ist unentscheidbar, ob es ”zwischen“ |ℚ| und |ℝ| noch eine weitere Kardinalität gibt.)

Es folgen einige wichtige Abzählprinzipien:

0.2.2 Additionsprinzip

Die Mengen A und B seien disjunkt (das heißt A ∩ B = ∅). Dann gilt:

|A ∪ B| = |A| + |B|

Beispiel: Wenn ein Verein 8 männliche und 13 weibliche Mitglieder hat, dann hat der Verein insgesamt 8 + 13 = 21 Mitglieder.

Das nächste Prinzip benutzt direkte Produkte:

0.2.3 Multiplikationsprinzip

Für beliebige Mengen A und B gilt:

|A × B| = |A| · |B|

Beispiel: Wieviele mögliche Nummernschilder Darmstädter Fahrzeuge sind möglich? Jedes Nummernschild fängt mit DA an, gefolgt von 1-2 Buchstaben (des üblichen 26-elementigen Alphabets), gefolgt von einer höchstens 4-stelligen natürlichen Zahl. Der Buchstaben-Teil hat 26 + 26^{2} Möglichkeiten (Additionsprinzip!), und der Zahlen-Teil hat 9999 Möglichkeiten. Das Multiplikationsprinzip liefert deshalb insgesamt (26 + 26^{2}) · 9999 mögliche Nummernschilder.

Die nächste Regel wurde schon erwähnt. Sie ist zwar sehr wichtig, wird aber dennoch oft verwendet, ohne explizit erwähnt zu werden:

0.2.4 Gleichheitsprinzip

Wenn f: A ⟶ B eine bijektive Abbildung ist, dann gilt:

|A| = |B|

Es folgt ein letztes Prinzip (obwohl es natürlich viele weitere gibt). Es beruht auf der offensichtlichen Tatsache, dass es nicht darauf ankommt, in welcher Reihenfolge man die Elemente einer Menge zählt. Dies wird hier verwendet, um die Elemente einer zweistelligen Relation R ⊆ A × B auf zwei Arten zu zählen. Für jedes a ∈ A und für jedes b ∈ B sei:

r_{1}(a) := |{y ∈ B | (a, y) ∈ R}|
r_{2}(b) := |{x ∈ A | (x, b) ∈ R}|

Es macht keinen Unterschied, ob man die Elemente von R ”A-weise“ oder ”Bweise“ zählt:

0.2.5 Prinzip der doppelten Abzählung

Für jede zweistellige Relation R ⊆ A × B gilt:

∑_{a∈A} r_{1}(a) = ∑_{b∈B} r_{2}(b)

Beide Seiten dieser Gleichung ergeben |R|, die Anzahl der Elemente von R. Viele Mathemetiker betrachten dieses Prinzip als das wichtigste der Kombinatorik. Später werden wichtige Anwendungen betrachtet. Zum Warmwerden folgt hier ein etwas künstliches Beispiel:

\underline{a b c d} ; R : ( \begin{matrix}× & & × \\ & × & × & × \\ × & × & × \end{matrix} ) | \begin{matrix}1 \\ 2 \\ 3 \end{matrix}

Abbildung 4: Kreuztabelle von R Beispiel: Sei A = {1, 2, 3} und B = {a, b, c, d}. Die Relation R ⊆ A × B sei durch obige Kreuztabelle gegeben (ein Kreuz an Stelle ix bedeutet (i, x) ∈ R).

Es gilt:

r_{1}(1) = 2, r_{1}(2) = r_{1}(3) = 3
r_{2}(a) = r_{2}(b) = 2, r_{2}(c) = 3, r_{2}(d) = 1

Tatsächlich gilt (keine Überaschung):

r_{1}(1) + r_{1}(2) + r_{1}(3) = 2 + 2 + 3 = 8
r_{2}(a) + r_{2}(b) + r_{2}(c) + r_{2}(d) = 2 + 2 + 3 + 1 = 8

0.2.6 Teilmengen endlicher Mengen

Jetzt werden die Teilmengen endlicher Mengen gezählt. Der Kürze halber wird jede n-elementige Menge eine n-Menge genannt. Die Menge aller Teilmengen einer Menge N wird mit P(N) bezeichnet (Potenzmenge von N).

Bemerkung: Jede n-Menge N hat genau 2^{n} Teilmengen, das heißt

|P(N)| = 2^{n}

Beweis: Sei oBdA. (ohne Beschränkung der Allgemeinheit) N = {1, 2, …, n}. Jede Teilmenge S ⊆ N ist durch ihre Elemente bestimmt. Für 1 ∈ N gibt es zwei Möglichkeiten: 1 ∈ S oder 1 ∉ S. Und zwei Möglichkeiten für 2 ∈ N: 2 ∈ S oder 2 ∉ S. Ebenso zwei Möglichkeiten für 3 ∈ N. . . . . Zwei Möglichkeiten für n ∈ N. Diese Möglichkeiten werden multipliziert (Multiplikationsprinzip). Zusammen ergeben sich 2 · 2 · 2 · . . . · 2 = 2^{n} Möglichkeiten für Teilmengen von N. □

Aufgabe: Finde einen streng formalen Beweis für obige Bemerkung, der das Gleichheitsprinzip und das Multiplikationsprinzip verwendet.

Beispiel: Sei N = {1, 2, 3}. Es gibt genau 2^{3} = 8 Teilmengen von N:

∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}

0.2.7 k-Teilmengen endlicher Mengen

Jetzt werden die Teilmengen einer n-Menge N in detaillierter Weise betrachtet: Die Menge aller k-Teilmengen (k-elementige Teilmengen) von N wird mit P_{k}(N) bezeichnet. Weiter sei \binom{n}{k} := |P_{k}(N)| (die Mächtigkeit von P_{k}(N)). Man spricht \binom{n}{k} als n über k. Aus Gründen, die später klar werden, nennt man die Zahlen \binom{n}{k} Binomialkoeffizienten.

Beobachtung: Seien n, k ∈ ℕ_{0} (der Menge der natürlichen Zahlen plus 0). Dann gilt:

\begin{matrix}(a) & \binom{n}{0} = \binom{n}{n} = 1, \binom{n}{1} = \binom{n}{n−1} = n \\ (b) & \binom{n}{k} = \binom{n}{n−k} \end{matrix}

Beweis: (a) ist offensichtlich. Für (b) beachte man, dass durch

P_{k}(N) ⟶ P_{n−k}(N), S ↦ N \ S := {x ∈ N | x ∉ S}

eine bijektive Abbildung gegeben ist. Also folgt (b) mit dem Gleichheitsprinzip.

Das Additionsprinzip liefert mit der Bemerkung von Seite 8 sofort:

Folgerung: ∑_{k=0}^{n} \binom{n}{k} = 2^{n} für alle n ∈ ℕ_{0}.

Als nächstes wird eine Formel für \binom{n}{k} entwickelt: Es wird das Prinzip der doppelten Abzählung auf die durch

(x, S) ∈ R :⇔ x ∈ S

definierte Relation R ⊆ N × P_{k}(N) angewandt (wieder mit N = {1, 2, …, n}). Für jedes x ∈ N gilt dann:

r_{1}(x) = |{S ∈ P_{k}(N) | x ∈ S}|
= |P_{k−1}(N \ {x})|
= \binom{n − 1}{k − 1}

Für jedes S ∈ P_{k}(N) gilt offenbar r_{2}(S) = |S| = k.

Also liefert ∑ r_{1}(x) = ∑ r_{2}(S):

\underbrace{n}_{Anzahl Ele- ; mente in N} · \underbrace{\binom{n − 1}{k − 1}}_{r_{1}(x)} = \underbrace{\binom{n}{k}}_{Anzahl Ele- mente in P_{k}(N)} · \underbrace{k}_{r_{2}(S)}

Dies lässt sicht schreiben als

⊛ \binom{n}{k} = \frac{n}{k}\binom{n − 1}{k − 1}

Hiermit lässt sich sofort die gewünschte Formel herleiten:

Satz: Es gilt \binom{n}{k} = \frac{n·(n−1)·...·(n−k+1)}{k·(k−1)·...·1} für alle n, k ∈ ℕ_{0} mit k ≤ n.

Beweis mit einer etwas informell durchgeführten Induktion über n. Bekanntlich gilt \binom{n−k}{0} = 1. Jetzt wird ⊛ der Reihe nach auf \binom{n}{k}, \binom{n−1}{k−1}, \binom{n−2}{k−2}, …, \binom{n−k+1}{1} angewandt:

\binom{n}{k} = \frac{n}{k}\binom{n − 1}{k − 1} = \frac{n}{k} · \frac{n − 1}{k − 1} · \binom{n − 2}{k − 2}
= \frac{n}{k} · \frac{n − 1}{k − 1} · \frac{n − 2}{k − 2} · \binom{n − 3}{k − 3} = …
= \frac{n}{k} · \frac{n − 1}{k − 1} · \frac{n − 2}{k − 2} · . . . · \frac{n − k + 1}{1} · \binom{n − k}{0}
= \frac{n · (n − 1) · (n − 2) · . . . · (n − k + 1)}{k · (k − 1) · (k − 2) · . . . · 1}

wie behauptet. □

Frage: Warum gilt diese Formel auch für k = 0?

Beispiel: Eine Bäckerei bietet 8 verschiedene Brotsorten an. Wieviele Möglichkeiten hat ein Kunde, in dieser Bäckerei 3 Brote zu kaufen, die alle von unterschiedlicher Sorte sind (rein von den Kombinationsmöglichkeiten her)? Antwort: Es gibt genau \binom{8}{3} = \frac{8·7·6}{3·2·1} = 56 Möglichkeiten.

Jetzt folgt die Anwendung der Binomialkoeffizienten, die ihnen den Namen gibt:

0.2.8 Die Binomische Formel

Für alle n ∈ ℕ_{0} und alle x, y ∈ ℂ (komplexe Zahlen) gilt:

(x + y)^{n} = ∑_{k=0}^{n} \binom{n}{k}x^{k}y^{n−k}

Beweis: Die Multiplikation der n Klammern von

(x + y)^{n} = (x + y) · . . . · (x + y)

führt man üblicherweise so durch:

(i) Entscheide in jeder Klammer, ob x oder y genommen werden soll,
(ii) Tue dies auf alle möglichen Arten.

Ein Produkt x^{k}y^{n−k} ergibt sich genau dann, wenn in (i) in genau k Klammern x gewählt wird und in den anderen Klammern y. Da es genau \binom{n}{k} Möglichkeiten gibt, k von n Klammern auszuwählen, ergibt sich genau \binom{n}{k} mal x^{k}y^{n−k}. □

Beispiel:

(x + y)^{3} = \binom{3}{0}x^{0}y^{3} + \binom{3}{1}x^{1}y^{2} + \binom{3}{2}x^{2}y^{1} + \binom{3}{3}x^{3}y^{0}
= y^{3} + 3xy^{2} + 3x^{2}y + x^{3}

Bekanntlich gilt \binom{n}{k} = \frac{n·(n−1)·(n−2)·...·(n−k+1)}{k·(k−1)·(k−2)·...·1}. Man kann die Binomialkoeffizienten aber auch mit folgender Formel berechnen:

0.2.9 Binomialrekursion

Für alle n, k ∈ ℕ gilt

\binom{n}{k} = \binom{n − 1}{k − 1} + \binom{n − 1}{k}

Diese Gleichung kann mit obiger üblicher Formel für die Binomialkoeffizienten leicht nachgerechnet werden. (Ein ganz anderer, begrifflicher Beweis wird in den Übungen vorgestellt!)

Mit Hilfe der Binomialrekursion können die Binomialkoeffizienten rekursiv berechnet werden, das heißt Schritt für Schritt für n = 1, 2, 3, . . .. Auf diese Art ergibt sich das Pascal’sche Dreieck.

[figure: n = 0; k = 0; 1; n = 1; k = 1; 1; 1; n = 2; k = 2; 1; 2; 1; n = 3; k = 3; 1; 3; 3; 1; n = 4; k = 4; 1; 4; 6; 4; 1; n = 5; k = 5; 1; 5; 10; 10; 5; 1; ⋮]

Abbildung 5: Das Pascal’sche Dreieck

Satz: Jede der folgenden Gleichungen kann man in diesem Schema veranschaulichen. Es gibt unzählige weitere Gleichungen für Binomialkoeffizienten, zum Teil von geradezu ”magischer“ Schönheit. Die nachfolgenden Gleichungen verdeutlicht man sich am Besten an dem Pascal’schen Dreieck:

(a) ∑_{k=0}^{n} \binom{n}{k} = 2^{n}  für alle n ∈ ℕ_{0}
(b) ∑_{k=0}^{n}(−1)^{k}\binom{n}{k} = 0  für alle n ∈ ℕ_{0}
(c) ∑_{i=k−1}^{n−1} \binom{i}{k−1} = \binom{n}{k}  für alle n ∈ ℕ_{0}, k ∈ ℕ
(d) ∑_{i=0}^{k} \binom{n−1−k+i}{i} = \binom{n}{k}  für alle n ∈ ℕ, k ∈ ℕ_{0}, n > k
(e) ∑_{i=0}^{k}(−1)^{i}\binom{n+1}{i} = (−1)^{k}\binom{n}{k} für alle n, k ∈ ℕ_{0}
(f) ∑_{i=0}^{k} \binom{n}{i}\binom{m}{k−i} = \binom{n+m}{k}  für alle n, m, k ∈ ℕ_{0}

(Vandermondesche Gleichung)

Beweis:

(a) Das wurde bereits auf Seite 9 gezeigt. Alternative Argumentation: Verwende die Binomische Formel mit x = y = 1.

(b) Binomische Formel mit x = 1, y = −1!

(c) Hier wird (erstmals) eine vollständige Induktion verwendet. Näheres zu diesem Beweisprinzip folgt später in diesem Kapitel! Induktion über n: Induktionsbasis: Die Behauptung gilt für n = 0: Die Summe auf der linken Seite ist leer, ergibt also 0. Die rechte Seite ist \binom{0}{k}, wegen k ≥ 1 ebenfalls 0. Induktionsvoraussetzung: Es werde vorausgesetzt, dass die Behauptung für (irgend ein) n ∈ ℕ_{0} gilt:

(Vor) ∑_{i=k−1}^{n−1} \binom{i}{k−1} = \binom{n}{k}

Indukionsschritt: Jetzt wird die Induktionsvoraussetzung (Vor) verwendet, um die Behauptung für n + 1 zu zeigen. Das funktioniert folgendermaßen:

\begin{aligned}∑_{i=k−1}^{n} \binom{i}{k − 1} & = & ( ∑_{i=k−1}^{n−1} \binom{i}{k − 1}) + \binom{n}{k − 1} \\ & =^{(Vor)} & \binom{n}{k} + \binom{n}{k − 1} = \binom{n + 1}{k} \end{aligned}

(d) Dieser Beweis kann ebenfalls mit Induktion durchgeführt werden. Die restlichen Beweise sind dem interessierten Leser überlassen.

(e) ist sehr trickreich,
(f) bei geeigneter Idee recht einfach.

0.2.10 Permutationen

Bei den Elementen einer Menge kommt es nicht auf die Reihenfolge an (die Elemente sind ”ungeordnet“) und Elemente können nicht doppelt vorkommen. Das kann man auch anders betrachten. Zuerst das geordnete Analogon: Eine k-Permutation einer Menge N ist eine Folge (a_{1}, …, a_{k}) ∈ N^{k} mit a_{i} ≠ a_{j} für i ≠ j, also ein k-Tupel mit k unterschiedlichen Elementen.

Satz: Es gibt genau n · (n − 1) · . . . · (n − k + 1) k-Permutationen in einer gegebenen n-Menge N.

Beweis: Für eine k-Permutation (a_{1}, …, a_{k}) ∈ N^{k} gibt es n Möglichkeiten für a_{1}, n − 1 Möglichkeiten für a_{2}, …, n − k + 1 Möglichkeiten für a_{k}. Insgesamt ergibt das n · (n − 1) · . . . · (n − k + 1) Möglichkeiten. □

0.2.11 Multimengen

In k-Mengen und in k-Permutationen gibt es keine Wiederholungen von Elementen. Jetzt werden Wiederholungen erlaubt. Zuerst eine sehr informelle Definition: Eine k-Multimenge einer Menge N ist eine ”Ansammlung“ {{a_{1}, …, a_{k}}} von k Elementen a_{1}, …, a_{k} ∈ N, wobei Wiederholungen von Elementen vorkommen dürfen. Die Anzahl der k-Multimengen in einer gegebenen n-Menge N wird mit \begin{matrix}( \\ ( & {n \atop k} & ) \\ ) \end{matrix} bezeichnet.

Beispiel: Sei N = {a, b}. Es gibt folgende 3-Mulimengen in N:

{{a, a, a}}, {{a, a, b}}, {{a, b, b}}, {{b, b, b}}

also (mit n = 2, k = 3): \begin{matrix}( \\ ( & {2 \atop 3} & ) \\ ) \end{matrix} = 4.

Satz: Die Anzahl aller k-Multimengen, die in einer gegebenen n-Menge N enthalten sind, beträgt

\begin{matrix}( \\ ( & {n \atop k} & ) \\ ) \end{matrix} = \binom{n + k − 1}{k}

Beweis mit Hilfe eines Beispiels: Es werde die 5-Multimenge

K = {{1, 1, 4, 6, 6}} in N = {1, 2, 3, 4, 5, 6}

betrachtet. Man kann K folgendermaßen mit k = 5 Kreuzen und n − 1 = 5 Strichen kodieren: × × ||| × || × ×. Bedeutung: Erst zwei Einsen, dann null Zweien, dann null Dreien, dann eine Vier, dann null Fünfen, dann zwei Sechsen. In der Kreuz-Strich-Kodierung ist K durch die Positionen der k = 5 Kreuze (Positionen 1, 2, 6, 9, 10) innerhalb der k+n−1 = 10 Zeichen langen Kreuz-Strich-Folge eindeutig bestimmt. Es gibt genau \binom{10}{5} = \binom{k+n−1}{k} Auswahlmöglichkeiten für diese Positionen der Kreuze, also ebensoviele k-Multimengen in {1, …, 6}. □

Es bleibt die Anzahl aller k-Tupel (a_{1}, …, a_{k}) ∈ N^{k} zu bestimmen. Doch das ist einfach (Multiplikationsregel):

Satz: Es gibt genau n^{k} verschiedene k-Tupel in einer gegebenen n-Menge N.

Die Tabelle fasst obige Resultate zusammen:

”Zusammenstellung“ von k

Objekten einer n-Menge  nicht geordnet  geordnet
ohne Wiederholungen  k-Mengen:  k-Permutationen:
\binom{n}{k}  n · (n − 1) · . . . · (n − k + 1)
mit Wiederholungen k-Multimengen: k-Tupel:
\begin{matrix}( \\ ( & {n \atop k} & ) \\ ) \end{matrix} = \binom{n+k−1}{k}  n^{k}

Die folgende Aufgabe gibt einfache Anwendungen:

Aufgabe: Eine Bäckerei bietet 8 Brotsorten an. Wieviele Möglichkeiten (von den Kombinationsmöglichkeiten der Brotsorten) gibt es dort für 5 Studenten

(a) insgesamt 5 Brote zu kaufen (alles verschiedene Sorten),
(b) insgesamt 5 Brote zu kaufen (Sortenwiederholungen möglich),
(c) 5 Brote zu kaufen, für jeden Studenten eins (ohne Wiederholungen),
(d) 5 Brote zu kaufen, für jeden Studenten eins (beliebige Sorten)?

Dieser Abschnitt wird mit dem Zählen von Abbildungen abgeschlossen:

0.2.12 Zählen von Abbildungen

Satz: Sei N eine n-Menge und K eine k-Menge.

(a) Es gibt genau n^{k} Abbildungen K ⟶ N

(b) Es gibt genau n · (n − 1) · . . . · (n − k + 1) injektive Abbildungen K ⟶ N

(c) Es gibt genau S(k, n) surjektive Abbildungen K ⟶ N mit

S(k, n) = ∑_{i=1}^{n}(−1)^{n−i}\binom{n}{i}i^{k}

Beweis

(a) Hierfür muss man alle k-Tupel in N zählen (siehe vorherige Seite)
(b) Das bedeutet, alle k-Permutationen in N zu zählen
(c) Der Beweis ist recht schwierig und wird hier weggelassen  □

Aufgabe: Man ”teste“ Aussage (c) für kleine Werte, zum Beispiel für n = 3, k = 4.

0.3 Beweismethoden

Mathematische Aussagen haben häufig die Form ”wenn p, dann q“, in symbolischer Schreibweise: p → q. Dabei sind dann p und q selbst Aussagen, die wahr (= w) oder falsch (= f) sein können. Die Aussage p → q hat folgende Wahrheitstafel:

\begin{matrix}p & q & p → q \\ w & w & w \\ w & f & f \\ f & w & w \\ f & f & w \end{matrix}

Also muss man sich beim Nachweis der Aussage p → q nur um den Fall kümmern, dass p wahr ist, und muss dann nachweisen, dass auch q wahr ist. Dabei wird p die Hypothese genannt, (und q zum Beispiel die Behauptung).

Ein direkter Beweis von p → q besteht darin, dass man eine Reihe von Aussagen p → p_{1} → p_{2} → … → p_{k} → q nachweist (wobei man alle schon bekannten Tatsachen ”verwenden“, das heißt voraussetzen darf). Andere Stategien bestehen darin, dass man zu p → q logisch äquivalente Aussagen nachweist. Logisch äquivalent zu p → q ist zum Beispiel ¬q → ¬p. Wenn man dies verwendet, muss man aus der Aussagen ¬q die Aussage ¬p herleiten (Kontraposition). Zu p → q ist aber auch die Aussage (p ∧ ¬q) → f äquivalent. Man muss also aus der Gültigkeit von p und von ¬q die Aussage f (falsch) herleiten (Widerspruchsbeweis).

Diese Methoden werden im Folgenden anhand von Beispielen vorgestellt. Außerdem wird das Beweisprinzip der vollständigen Induktion vorgestellt.

0.3.1 Direkter Beweis

Es soll schrittweise die Behauptung

wenn a durch 6 teilbar ist, dann ist a auch durch 3 teilbar

nachgewiesen werden (für a ∈ ℤ). Die Hypothese ist

p : a ist durch 6 teilbar,

und die Behauptung ist

q : a ist durch 3 teilbar.

Für den Nachweis werden mehrere Zwischenschritte verwendet. Nach Definition bedeutet p:

p_{1} : a = 6k für ein k ∈ ℤ.

Wegen 6 = 3 · 2 lässt sich dies schreiben als

p_{2} : a = (3 · 2)k für ein k ∈ ℤ.

Bekanntlich gilt (3 · 2)k = 3(2 · k) (Assoziativität), also

p_{3} : a = 3(2 · k) für ein k ∈ ℤ.

Da mit k auch k′ = 2 · k eine ganze Zahl ist, folgt

p_{4} : a = 3k′ für ein k′ ∈ ℤ.

Letzteres bedeutet, dass a durch 3 teilbar ist. Also ist die Behauptung q jetzt bewiesen. Die Beweisstruktur in diesem Fall war

p → p_{1} → p_{2} → p_{3} → p_{4} → q

Natürlich lassen sich Aussage und Beweis oft viel informeller und knapper formulieren, in diesen Fall zum Beispiel so:

Behauptung: Wenn eine ganze Zahl a durch 6 teilbar ist, dann ist a auch durch 3 teilbar.

Beweis: Ist a durch 6 teilbar, dann gilt a = 6k für ein k ∈ ℤ. Umformung ergibt a = (2 · 3)k = 3(2k) und da mit k ∈ ℤ auch 2k ∈ ℤ gilt, folgt schießlich, dass a durch 3 teilbar ist. □

0.3.2 Beweis durch Kontraposition

Anstelle einer Implikation p → q wird die dazu logisch äquivalente Implikation ¬q → ¬p direkt bewiesen (die Kontraposition von p → q). Ein Beispiel:

Behauptung: Sei a ∈ ℤ. Wenn a^{2} ungerade ist, dann ist a ungerade.

In diesem Beispiel ist p die Aussage ”a^{2} ungerade“ und q die Aussage ”a ungerade“. Jetzt wird aus der Aussage ¬q (”a gerade“) direkt die Aussage ¬p (”a^{2} gerade“) bewiesen:

Beweis der Behauptung: ”a gerade“ bedeutet a = 2k für ein k ∈ ℤ. Dann gilt a^{2} = (2k)^{2} = 4k^{2} = 2(2k^{2}), wobei 2k^{2} ∈ ℤ gilt. Doch das bedeutet ”a^{2} gerade“. □

0.3.3 Widerspruchsbeweis

Anstelle einer Implikation p → q wird die dazu logische äquivalente Implikation (p ∧ ¬q) → f bewiesen (also: p und ¬q können nicht gleichzeitig gelten). Hier ein berühmtes Beispiel:

Behauptung: Es gibt unendlich viele Primzahlen.

Hier handelt es sich um einen degenerierten Widerspruchsbeweis. Die Aussage q sei ”es gibt unendlich viele Primzahlen“ und die Aussage p sei ”wahr“, also p = w. Zu zeigen ist (w ∧ ¬q) → f, also ¬q → f. Dabei bedeutet ¬q ”es gibt nur endlich viele Primzahlen“.

Beweis der Behauptung: Werde angenommen, dass es nur endlich viele Primzahlen z_{1}, …, z_{k} gibt. Dann ist z = z_{1} · . . . · z_{k} + 1 eine ganze Zahl, die aber durch keine der Primzahlen z_{1}, …, z_{k} teilbar ist (denn teilt man z durch z_{i}, bleibt immer Rest 1). Also muss auch z eine Primzahl sein. ⚡ □

Noch zwei Beweisprinzipien, die oben nicht angekündigt waren:

0.3.4 Äquivalenzbeweis

Eine Aussage der Form p ↔ q bedeutet: ”p gilt genau dann, wenn q gilt“. Sie ist logisch äquivalent zu (p → q) ∧ (q → p). Man muss also zwei Beweise führen, nämlich einen für p → q und einen für q → p. Ein Beispiel:

Behauptung: Sei a ∈ ℤ. Dann ist a^{2} genau dann gerade, wenn a gerade ist. Hier werden die Aussagen p (”a^{2} gerade“) und q (”a gerade“) betrachtet:

Beweis der Behauptung: Aus ”a gerade“ folgt ”a^{2} gerade“. Das erhält man mit Kontraposition aus der Behauptung aus Seite 15. Jetzt sei a^{2} gerade. Zu zeigen ist, dass dann auch a gerade ist. Auch das gelingt sehr einfach mit Kontraposition: Sei a ungerade, also von der Form a = 2k + 1, k ∈ ℤ. Dann ist a^{2} = (2k + 1)^{2} = 4k^{2} + 4k + 1 = 2(2k^{2} + 2k) + 1, wobei 2k^{2} + 2k ∈ ℤ gilt. Doch das bedeutet ”a^{2} ungerade“. □

0.3.5 Fallunterscheidung

Jede Aussage p ist logisch äquivalent zur Aussage (q → p)∧(¬q → p), wobei (im Prinzip) q irgendeine Aussage sein kann. Also ist p logisch äquivalent zu: ”Wenn q, dann p und wenn nicht q, dann p“. Natürlich wählt man kein beliebiges q, sondern ein zur Aussage p passendes q. Ein Beispiel:

Behauptung: Sei a ∈ ℤ. Teilt man a^{2} durch 4, so ergibt sich immer Rest 0 oder Rest 1.

Als Aussage p nimmt man hier natürlich die Aussage der Behauptung. Als Aussage q eignet sich ”a gerade“:

Beweis der Behauptung: Mit Fallunterscheidung: Fall 1: Sei a gerade, also von der Form a = 2k, k ∈ ℤ. Dann gilt a^{2} = (2k)^{2} = 4k^{2}, wobei k^{2} ∈ ℤ gilt. Das bedeutet, dass a^{2} durch 4 den Rest 0 ergibt. Fall 2: Sei a ungerade, also von der Form a = 2k + 1, k ∈ ℤ. Dann gilt a^{2} = (2k + 1)^{2} = 4k^{2} + 4k + 1 = 4(k^{2} + k) + 1, wobei k^{2} + k ∈ ℤ gilt. Doch das bedeutet, dass a^{2} durch 4 den Rest 1 ergibt. □

0.3.6 Vollständige Induktion

Damit kann man (bisweilen) unendliche ”Serien“ von Aussagen beweisen, zum Beispiel die Aussagen p(n), n ∈ ℕ_{0}. Diese kann man beweisen, indem man die beiden folgenden Aussagen zeigt:

Induktionsbasis: Es wird p(0) gezeigt.

Induktionsschritt: Es wird gezeigt, dass folgende Aussage gilt:

∀n ∈ ℕ_{0}: p(n) → p(n + 1)

Die letzte Zeile liest man ”für alle n aus ℕ_{0} gilt: die Aussage p(n) impliziert die Aussage p(n + 1)“. Wenn Induktionsbasis und Induktionsschritt nachgewiesen sind, dann weiß man die Gültigkeit aller in folgender Implikationstabelle vorkommenden Aussagen:

p(0) → p(1) → p(2) → p(3) → p(4) → …

Also: Induktionssatz: Gelten die beiden Aussagen p(0) und

∀n ∈ ℕ_{0}: p(n) → p(n + 1)

dann gilt auch die Aussage ∀n ∈ ℕ_{0}: p(n). Das folgende Beispiel kann allerdings auch anders bewiesen werden:

Behauptung: Für alle n ∈ ℕ_{0} gilt:

p(n): ∑_{k=0}^{n} k = \frac{n · (n + 1)}{2}

Beweis mit Induktion über n. Induktionsbasis: Sei n = 0. Dann ergibt die linke Seite p(0) : ∑_{k=0}^{0} k = 0. Die rechte Seite von p(0) ist \frac{0·(0+1)}{2} = 0. Damit ist p(0) gezeigt. Induktionsschritt: Es wird p(n) vorausgesetzt (die sogenannte Induktionsvoraussetzung) und p(n + 1) muss gezeigt werden. Das funktioniert so:

∑_{k=0}^{n+1} k = (∑_{k=0}^{n} k) + n + 1 = \frac{n · (n + 1)}{2} + n + 1

= (n + 1) (\frac{n}{2} + 1) = \frac{(n + 1) · (n + 2)}{2}

Die linke und die rechte Seite dieser Gleichungskette bilden insgesamt die nachzuweisende Gleichung p(n + 1). □

Der obige Induktionssatz läßt sich verallgemeinern: Verallgemeinerter Induktionssatz: Gelten die beiden Aussagen p(0) und ∀n ∈ ℕ_{0}: (p(0) ∧ p(1) ∧ ... ∧ p(n)) → p(n + 1), dann gilt auch die Aussage ∀n ∈ ℕ_{0} : p(n).

Ein sehr simples Beispiel hierfür:

Behauptung: Jede natürliche Zahl n ≥ 2 ist ein Produkt von Primzahlen.

Beweis mit Induktion über n. Induktionsbasis (für n = 2). Die Zahl 2 ist das Produkt von einer Primzahl, nämlich der Zahl 2 selbst.

Induktionsschritt mit Fallunterscheidung: Gelte die Behauptung für alle natürlichen Zahlen zwischen 2 und n (jeweils inklusive). Jetzt wird die Zahl n + 1 behandelt:

Fall 1: Sei n + 1 eine Primzahl. Dann ist n+1 das Produkt einer Primzahl (nämlich sich selbst).

Fall 2: Sei n + 1 keine Primzahl. Dann gilt n + 1 = n_{1} · n_{2} mit 2 ≤ n_{1}, n_{2} < n + 1. Nach Induktionsvoraussetzung gibt es Primzahlen s_{1}, ..., s_{k}, t_{1}, ..., t_{ℓ} mit n_{1} = s_{1} · . . . · s_{k} und n_{2} = t_{1} · . . . · t_{ℓ}, also mit n + 1 = s_{1} · . . . · s_{k} · t_{1} · . . . · t_{ℓ}, womit die Behauptung für n + 1 gezeigt ist. □

Es gibt induktive Definitionen, auch Rekursionen genannt. Oft lassen sich Eigenschaften der so rekursiv definierten Objekte per vollständiger Induktion beweisen.

Ein berühmtes Beispiel: Die Fibonacci-Zahlen f_{0}, f_{1}, f_{2}, ... werden rekursiv definiert durch

f_{0} = 0, f_{1} = 1, f_{n+2} = f_{n+1} + f_{n} für alle n ≥ 0

Die ersten Zahlen dieser Folge sind:

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ f_{n} & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 \end{matrix}

Tatsächlich gilt folgendes Ergebnis (sehr erstaunlich, da eine Folge ganzer Zahlen mittels Wurzeln und Brüchen beschrieben wird):

Behauptung: Für alle Fibonacci-Zahlen f_{n} gilt:

f_{n} = \frac{(\frac{1+\sqrt{5}}{2})^{n} − (\frac{1−\sqrt{5}}{2})^{n}}{\sqrt{5}}

Der Beweis ist eine Übungsaufgabe (aber ohne vollständige Induktion!)

1 Diskrete Mathematik

Die Diskrete Mathematik beschäftigt sich mit endlichen Strukturen, die unter kombinatorischen Gesichtspunkten betrachtet werden können. Vieles in der Diskreten Mathematik ist für moderne Anwendungen, speziell in der Informatik, von größter Bedeutung. Das gilt besonders für Graphen (und speziell Bäume). Es gibt viele interessante Algorithmen für Graphenprobleme, anhand von Graphen kann man die Begriffe Symmetrie und Gruppe einführen, und (Permutations-)Gruppen sind ein wichtiges Hilfsmittel für eine berühmte kombinatorische Abzählmethode, nämlich die Pólya-Methode. Damit endet dieses Kapitel!

1.1 Graphen: Beispiele und Grundlagen

Zuerst ein sehr anschauliches Problem, das gleich auf (mindestens) zwei Arten graphentheoretisch betrachtet werden kann:

Beispiel: Ein Tischtennisturnier mit fünf Teilnehmern und einem Spieltisch. Regeln:

1. Jeder Teilnehmer spielt genau einmal gegen jeden anderen Teilnehmer
2. Kein Teilnehmer spielt in zwei aufeinanderfolgenden Spielen

Aufgabe: Finde einen Spielplan!

Erster Versuch: Die fünf Punkte entsprechen den Teilnehmern, die Linien den Spielen. Das Diagramm gibt keinen Spielplan. Man kann so vorgehen: Das erste Spiel sei oBdA ab. Als zweites Spiel kommen die zu ab ”disjunkten“ Linien cd, cd, de in Frage. Und so weiter!

Zweiter Versuch: Mit einem anderen Graphen, der aber mehr Informationen enthält: die zehn Punkte entsprechen den zehn Spielen, und eine Linie bedeutet, dass die zugehörigen beiden Spiele (=Punkte) hintereinander stattfinden dürfen. Die dicken Linien verbinden dann Spiele zu einem Spielplan!

[figure: a; b; c; d; e; ab; cd; be; ac; de; ce; ae; ad; bd; bc]

Abbildung 6: Turniergraph

1.1.1 Graphen

Definition: Ein Graph ist ein Paar G = (V, E), bestehend aus einer beliebigen Menge V und einer Menge E ⊆ P_{2}(V), das heißt einer Menge zweielementiger Teilmengen von V. Die Elemente von V heißen Ecken (Punkte, Knoten) von G, die Elemente von E Kanten (Linien, Bögen) von G.

Es ist klar, dass man mit Hilfe von Graphen gewisse einfache Zusammenhänge (”Objekte, von denen je zwei entweder miteinander in Beziehung stehen oder nicht“) auf einfache Art darstellen und oft auch mit Diagrammen veranschaulichen kann:

Beispiel: Sei

V = {1, 2, 3, 4, 5}
E = {{1, 2}, {1, 4}, {1, 5}, {2, 3}, {2, 4}, {2, 5}, {3, 4}, {4, 5}}

Dann ist G = (V, E) ein Graph mit |V | = 5 Ecken und |E| = 8 Kanten. Jedes der folgenden drei Diagramme zeigt diesen Graphen:

[figure: 1; 5; 4; 2; 3; 1; 5; 4; 2; 3; 1; 5; 4; 2; 3]

Abbildung 7: Beispiele für Graphen

In der vorliegenden Definition eines Graphen ist folgendes nicht vorgesehen:

[figure: Mehrfachkanten; Multigraphen; Schlingen; Pseudographen; gerichtete Kanten; Gerichtete Graphen; a; 1; ∗; 3, 5; 2; bewertete Kanten; Gewichtete Graphen]

Abbildung 8: Weitere Graphentypen

Sind die Graphen G_{1} und G_{2} identisch? Eindeutig nicht. Aber sie sehen identisch aus:

[figure: 1; 3; 2; 4; G_{1}; a; c; b; d; G_{2}]

Abbildung 9: Graphenisomorphie I

Aber: G_{1} und G_{2} sind identisch bis auf die Tatsache, dass die Ecken unterschiedliche Namen haben.

1.1.2 Isomorphismen

Definition: Zwei Graphen G_{1} = (V_{1}, E_{1}) und G_{2} = (V_{2}, E_{2}) heißen isomorph, falls es eine bijektive Abbildung φ: V_{1} ⟶ V_{2} gibt mit:

∀x, y ∈ V_{1} : {x, y} ∈ E_{1} ⇔ {φ(x), φ(y)} ∈ E_{2}

Dann heißt φ ein Isomorphismus von G_{1} auf G_{2}, und man schreibt auch

G_{1} ≅ G_{2} oder G_{1} ≅^{φ} G_{2}.

Ein Isomorphismus bildet also benachbarte Ecken auf benachbarte Ecken und nicht benachbarte Ecken auf nicht benachbarte Ecken ab. Ein Isomorphismus ist nichts als eine Umbenennung der Ecken. In obigem Beispiel wird ein Isomorphismus φ gegeben durch

\begin{matrix}x & 1 & 2 & 3 & 4 \\ φ(x) & a & b & c & d \end{matrix}

Wie erkennt man in weniger einfachen Fällen, ob zwei Graphen G_{1} und G_{2} isomorph bzw. nicht isomorph sind? Es gibt zwei Möglichkeiten:

Möglichkeit 1: Probiere alle bijektiven Abbildungen φ : V_{1} → V_{2}. Im Fall |V_{1}| = |V_{2}| = n gibt es n! (”n Fakultät“) solche Abbildungen, also für große n (z.B. n = 50) eine für keinen Computer der Welt durchführbare Aufgabe!

Möglichkeit 2: Finde eine (graphentheoretisch formulierbare) Eigenschaft, in der sich G_{1} und G_{2} unterscheiden. Wird auch bei nicht isomorphen Graphen nicht immer gelingen!

Übung: Finde Eigenschaften, die zeigen, dass die folgenden Graphen paarweise nicht isomorph sind:

[figure]

Abbildung 10: Graphenisomorphie II

Für jede Zahl n ∈ ℕ gibt es unendlich viele Graphen mit n Ecken. Aber wie viele ”wirklich verschiedene“, das heißt paarweise nicht isomorphe Graphen mit n Ecken gibt es? Diese Frage ist durchaus kompliziert; es ist keine einheitliche Formel bekannt. Hier sind die ersten Zahlen:

n (Anzahl der Ecken)  1 2 3 4 5 6  7  8 ; Anzahl paarweise nicht isomor- pher Graphen mit n Ecken 1 2 4 11 34 156 1044 12344

Dieser Abschnitt wird mit einigen wichtigen Begriffen abgerundet:

1.1.3 Knotengrad

Definition: Sei G = (V, E) ein Graph. Für jedes v ∈ V sei

deg(v) := |{e ∈ E | v ∈ e}|,

genannt der Grad (engl.: degree) von v.

Beispiel: Der Graph G_{1} (Seite 20, Abbildung: Graphenisomorphie) erfüllt deg(1) = deg(4) = 2, deg(2) = deg(3) = 3.

Das erste der beiden folgenden Resultate ist offensichtlich, das zweite ergibt sich recht einfach mit doppelten Abzählen:

Bemerkung: Ist φ ein Isomorphismus eines Graphen G_{1} auf einen Graphen G_{2}, dann gilt deg(v) = deg(φ(v)) für jede Ecke v von G_{1}.

Handschlag-Lemma: Für jeden endlichen Graphen G = (V, E) gilt:

∑_{v∈V} deg(v) = 2|E|

Eine unmittelbare Folgerung hieraus:

Korollar: Jeder endliche Graph hat eine gerade Anzahl von Ecken ungeraden Grads.

1.1.4 Kantenzüge

Definition: Sei G = (V, E) ein Graph. Eine Folge (v_{0}, v_{1}, …, v_{n}) von Ecken von G heißt ein Kantenzug, falls e_{i} := (v_{i}, v_{i+1}) ∈ E gilt für i = 0, 1, …, n − 1 das heißt falls je zwei aufeinanderfolgende Ecken duch eine Kante verbunden sind. Im Fall v_{0} = v_{n} handelt es sich um einen geschlossenen, sonst um einen offenen Kantenzug. Wenn alle Kanten eines Kantenzugs verschieden sind, spricht man (im offenen Fall) von einem Weg, im geschlossenen Fall von einem Kreis. Kommt außerdem auch jede Ecke nur einmal vor, dann heißt der Weg ein einfacher Weg bzw. der Kreis ein einfacher Kreis (wobei im Fall des Kreises natürlich v_{0} = v_{n} gilt). Die Länge eines Kantenzugs ist die Anzahl seiner Kanten. Der Kantenzug (v_{0}, v_{1}, …, v_{n}) hat also die Länge n.

Randbemerkung: In der Graphentheorie-Literatur herrscht ein großes Bezeichnungschaos, besonders was die eben gegebenen Bezeichnungen betrifft. Beispielsweise werden Wege oft automatisch als ”einfach“ definiert. Man sollte in jedem Buch oder Artikel immer zuerst die grundlegenden Bezeichnungen sorgfältig checken!

Beispiele: In folgendem Graphen G ist

(a, b, d, f)  kein Kantenzug,
(a, c, d, b, c, e) ein Weg der Länge 5, aber kein einfacher Weg,
(a, c, d, b, c, a) ein geschlossener Kantenzug, aber kein Kreis,
(a, c, a)  desgleichen,
(a, c, d, b, a)  ein einfacher Kreis.

Und: es gibt genau 6 verschiedene einfache Wege von a nach d.

[figure: a; b; c; e; d; f; g; G]

Abbildung 11: Zusammenhängende Graphen

1.1.5 Zusammenhängende Graphen

Definition: Ein Graph G = (V, E) heißt zusammenhängend, falls je zwei Ecken x, y ∈ V durch einen Kantenzug verbunden sind. Die Relation R ⊆ V^{2} mit

xRy :⟺ es gibt einen Kantenzug von x nach y

ist eine Äquivalenzrelation auf V. Für jede Äquivalenzklasse W dieser Äquivalenzrelation ist der Untergraph G_{W} := (W, E ∩ P_{2}(W)) seine Zusammenhangskomponente von G.

Definition/Anmerkung: Sei G = (V, E) ein Graph. Jeder Graph G′ = (V′, E′) mit V′ ⊆ V und E′ ⊆ E ist ein Teilgraph von G. Im Fall, dass E′ alle möglichen Kanten enthält, das heißt im Fall E′ = E ∩ P_{2}(V), wird G′ ein Untergraph von G genannt (der von V′ induzierte Untergraph). Die Zusammenhangskomponenten eines Graphen sind also die induzierten Untergraphen auf den Äquivalenzklassen von R. Der obige Graph hat zwei Zusammenhangskomponenten, mit Eckenmengen W_{1} = {a, b, c, d, e} und W_{2} = {f, g}.

1.2 Bäume

Die Graphen dieses Abschnitts spielen gerade in vielen informatischen Anwendungen eine große Rolle.

Definition: Ein Baum ist ein zusammenhängender Graph, der keine Kreise enthält (außer den ”trivialen“ 1-elementigen Kreisen). Hier sind alle Bäume mit 6 Ecken:

[figure]

Abbildung 12: Bäume mit 6 Ecken

Hier eine vielbenutzte Charakterisierung von Bäumen:

Satz: Für einen Graphen G mit n Ecken sind folgende Aussagen äquivalent:

(i) G ist ein Baum,
(ii) G ist zusammenhängend und hat genau n − 1 Kanten.

Beweis: (i) ⇒ (ii): Sei e_{1} ∈ E, e_{1} = {x_{1}, y_{1}}. Entfernt man e_{1} aus G, so ergibt sich der Graph G \ e_{1} := (V, E \ {e_{1}}). Dieser Graph hat eine Zusammenhangskomponente mehr als G, denn x_{1} und y_{1} sind jetzt in verschiedenen Komponenten. Entfernt man jetzt eine weitere Kante e_{2}, so ergibt sich ein Graph G \ e_{1}, e_{2} mit jetzt drei Zusammenhangskomponenten. Setzt man dies schrittweise fort, so erhält man schließlich nach Entfernung von n − 1 Kanten e_{1}, e_{2}, …, e_{n−1} einen Graphen G \ e_{1}, e_{2}, …, e_{n−1} mit 1 + (n − 1) = n Komponenten. Jetzt bildet also jede der n Ecken eine Zusammenhangskomponente für sich selbst, das heißt G \ e_{1}, e_{2}, …, e_{n−1} hat keine Kanten mehr. Es folgt E = {e_{1}, e_{1}, …, e_{n−1}}.

(ii) ⇒ (i): Es ist zu zeigen, dass G keinen nichttrivialen Kreis enthält. Werde im Gegenteil angenommen, es gebe einen solchen Kreis: (v_{0}, v_{1}, …, v_{0}). Es wird ein Widerspruch hergeleitet: Sei e := {v_{0}, v_{1}}. Dann ist offenbar G \ e immer noch zusammenhängend, denn (v_{1}, …, v_{0}) ist ein Kantenzug von v_{1} nach v_{0}. Sei E \ {e} = {e_{1}, …, e_{n−2}}. Dann hat G \ e, e_{1} höchstens zwei Zusammenhangskomponenten, G \ e, e_{1}, e_{2} höchstens drei Zusammenhangskomponenten, …, G \ e, e_{1}, …, e_{n−2} höchstens n − 1 Zusammenhangskomponenten. ⚡ (Denn ein Graph ohne Kanten mit n Ecken hat n Zusammenhangskomponenten!) □

1.2.1 Wälder

Anmerkung: Ein Graph ohne nichttriviale Kreise ist ein Wald. Also sind Bäume gerade die zusammenhängenden Wälder! Das Diagramm zeigt einen Wald mit fünf Zusammenhangskomponenten (= Teilbäumen).

[figure]

Abbildung 13: Wald

1.2.2 Wurzelbäume

In der Informatik werden oft Bäume betrachtet, die noch weitere Eigenschaften oder Zusatzinformationen tragen. Zuerst ein Beispiel hierfür, welches diesen Baum als Grundlage hat:

G

a b

c e

f d

g h i

Grundlage

a

b
c

e

f d g

h
i

root(G) := e [figure] [figure] [figure] [figure]

a

b

c

e

f d

g h

i

root(G) := g

Ecke Kinder
a  −
b  a, c
c  −
d  −
e  d, b, f, g
f  −
g  h
h  i
i  −

Abbildung 14: Wurzelbäume

Es wird eine Ecke als Wurzel von G ausgewählt, genannt root(G). Wählt man in obigem Baum G root(G) := e, dann läßt sich der zugehörige Baum wie in der mittleren Abbildung zeichnen, mit root(G) := g wie in der rechten Abbildung.

Man zeichnet Wurzelbäume üblicherweise von der Wurzel an abwärts (im Unterschied zu Bäumen in der Natur)!

In einem Wurzelbaum hat jede Ecke entweder Kinder, oder sie ist ein Blatt. Die Tabelle in der obigen Abbildung gibt eine Darstellung für den Graphen mit root(G) = e an. Die Blätter sind a, c, d, f, i.

1.2.3 Binäre Bäume

Dies sind Wurzelbäume mit höchstens zwei Kindern pro Ecke, einem linken Kind und einem rechten Kind. Die Abbildung auf Seite 25 zeigt ein Beipsiel als Diagramm und als Tabelle.

Binäre Wurzelbäume werden auch binäre Suchbäume genannt. Sie können zur Suche in linearen Ordnungen verwandt werden.

[figure] [figure] [figure] [figure]

a

b c

d e

f g

h

Ecke linkes Kind rechtes Kind
x  l(x)  r(x)
a  b  c
b  −  d
c  −  e
d  f  g
e  −  −
f  h  −
g  −  −
h  −  −

Abbildung 15: Binärbäume

Beispiel: Sei folgendes (sehr kleines) Telefonbuch gegeben:

Namen Anna Bernd Chris Doris Emil Ferdi Gerd Hans Tel.-Nr. 3715 8102 1519 2424 2426 9132 2001 4567

[figure: {Ferdi \atop 9132}; {Anna \atop 3715}; {Gerd \atop 2001}; {Doris \atop 2424}; {Hans \atop 4567}; {Chris \atop 1519}; {Emil \atop 2426}; {Bernd \atop 8102}]

Abbildung 16: Telefonbuch I

Obiges Diagramm erfüllt folgende Regel: Nach links von einer Ecke mit Namen X kommen nur Namen Y mit Y < X (”vorher im Alphabet“), nach rechts kommen nur Namen Y > X.

Suche nach Chris Nummer: Starte bei Wurzel Ferdi. Chris < Ferdi → nach links zu Anna, Chris > Anna → nach rechts zu Doris, Chris < Doris → nach links zu Chris (Nummer 1519, fertig!)

Dieser binäre Suchbaum hat Tiefe 4 (Tiefe = maximale Weglänge von der Wurzel nach unten). Klar ist: geringere Tiefe ergibt geringere durchschnittliche Suchzeit. Darum ist der folgende binäre Suchbaum für dasselbe Telefonbuch besser (er ist sogar optimal):

[figure: {Ferdi \atop 9132}; {Anna \atop 3715}; {Gerd \atop 2001}; {Doris \atop 2424}; {Hans \atop 4567}; {Chris \atop 1519}; {Emil \atop 2426}; {Bernd \atop 8102}]

Abbildung 17: Telefonbuch II

Dieses Beispiel hat Tiefe 3. Allgemein: In die ”Schichten“ 0, 1, 2, …, k eines Suchbaumes passen offenbar maximal 1 + 2 + 4 + … + 2^{k} = 2^{k+1} − 1 Ecken. Deshalb gilt n ≤ 2^{k+1} − 1, wobei n die Anzahl der Ecken ist. Es folgt n < 2^{k+1}, also:

log_{2}(n) − 1 < Tiefe

1.3 Abstände in (ungerichteten, unbewerteten) Graphen

In diesem Abschnit wird der ”graphentheoretische Abstand“ betrachtet, dabei wird jeder Kante die ”Länge“ 1 zugeordnet.

1.3.1 Länge von Kantenzügen

Definition: Die Länge eines Kantenzugs ist definiert als die Anzahl der Kanten des Kantenzugs (kam schon auf Seite 22 vor). Der Abstand d(a, b) zweier Ecken a und b eines Graphen ist das Minimum der Längen aller Kantenzüge von a nach b. Falls es keinen solchen Kantenzug gibt, wird d(a, b) = ∞ gesetzt.

Beispiel: In folgendem Graphen hat der Kantenzug (a, b, d, f, g, c) die Länge 5. Ein Kantenzug geringster möglicher Länge von a nach c ist (a, b, c), er hat Länge 2. Daher gilt d(a, c) = 2.

[figure: v_{0} = a; b; c; d; e; f; g; G]

Abbildung 18: Kantenzüge

1.3.2 Algorithmus von Moore

Es wird ein Algorithmus vorgestellt (Algorithmus von Moore, 1959), in dem Graphen durch Adjazenzlisten gegeben sind, das heißt für Listen, die zu jeder Ecke die Nachbarecken aufzählen. In obigem Beispiel sind das (bei alphabetischer Anordnung) folgende Listen:

\begin{matrix}A_{a} & A_{b} & A_{c} & A_{d} & A_{e} & A_{f} & A_{g} \\ b, d & a, c, d, f & b, g & a, b, e, f & d, f & b, d, e, g & c, f \end{matrix}

Sei G ein durch seine Adjazenzlisten A_{v} gegebener Graph und sei v_{0} eine Ecke dieses Graphen. Es werden Zahlen d(v) sowie Mengen V (0), V (1), V (2), … berechnet. Der Algorithmus ist in ”Pseudo-Pascal“ geschrieben.

(1) d(v_{0}) ← 0, V (0) ← {v_{0}}, k ← 1,

(2) while V (k − 1) ≠ ∅ do

(3) V (k) ← ∅,

(4) for v ∈ ⋃{A_{u} | u ∈ V (k − 1)} do

(5) if d(v) ist undefiniert then

(6) d(v) ← k, V (k) ← V (k) ∪ {v},

  (7)  end,
  (8)  end,

(9) k ← k + 1

 (10) end.

Was dieser Algorithmus tut, ist möglicherweise auf den ersten Blick nicht gut sichtbar. Aber die Idee ist einfach: Ausgehend von V (0) = {v_{0}} werden sukzessive die Mengen V (1), V (2) berechnet. Dabei besteht V (k) aus den Ecken, die mit Ecken aus V (k−1) benachbart sind, aber nicht in V (0)∪V (1)∪…∪V (k−1) liegen. Mit Induktion sieht man, dass V (k) genau aus den Ecken besteht, die Abstand k von v_{0} haben. Die Laufzeit des Algorithmus ist, in der üblichen pauschalen Weise, schnell bestimmt: Zeile (1) erfordert drei Rechenschritte, und jede andere Zeile nicht mehr als insgesamt (das heißt bei sämtlichen Durchläufen) 2m Rechenschritte, wobei m die Anzahl der Kanten von G bezeichnet. Zu Zeile (4) beachte man, dass die Vereinigungsmenge nicht wirklich berechnet werden muss, es genügt die Elemente der jeweiligen Listen A_{u} der Reihe nach aufrufen. Die Komplexität (= Laufzeit) ist also proportional zu m, in Symbolen: von der Größenordnung O(m) (sprich: ”groß -O von m“). Damit ist insgesamt gezeigt:

Satz: Nach der Durchführung des Algorithmus von Moore gilt für alle Ecken v von G:

d(v, v_{0}) = \{ \begin{matrix}d(v) & falls d(v) definiert ist \\ ∞ & sonst \end{matrix}

Der Algorithmus hat die Komplexität O(m).

Da der Algorithmus ausgehend von Ecke v_{0}, ”in die Breite“ gehend sucht, spricht man auch von breadth first search (BFS).

Für obiges Beispiel ergibt sich: V (0) = {a}, V (1) = {b, d}, V (2) = {c, e, f}, V (3) = {9}, V (4) = ∅.

Dementsprechend: \begin{matrix}v & a & b & c & d & e & f & g \\ d(v) & 0 & 1 & 2 & 1 & 2 & 2 & 3 \end{matrix}

Der Algorithmus liefert auch einen Test, ob der Graph G zusammenhängend ist.

[figure: v_{0} = a; b; c; d; e; f; g; V (0); V (1); V (2); V (3)]

Abbildung 19: Breitensuche

Korollar: Ein endlicher Graph G ist genau dann zusammenhängend, wenn nach Durchführung des Algorithmus von Moore für jede Ecke v die Zahl d(v) definiert ist.

Für die Laufzeit von Algorithmen ist es sehr wichtig, welche Datenstrukturen verwendet werden. Eine Möglichkeit für Graphen ist die Darstellung mit Adjazenzlisten wie auf Seite 27. Es handelt sich dabei um n Listen, wobei alle Listen zusammen 2m Einträge haben (zwei Einträge pro Kante). Dabei ist wie üblich n die Anzahl der Ecken und m die Anzahl der Kanten eines Graphen.

1.3.3 Inzidenzmatrizen

Graphen können auf viele weitere Arten dargestellt werden. Eine davon ist die Darstellung mit Inzidenzmatrizen^{1} . Der Graph G auf Seite 26 hat zum Beispiel die folgende Inzidenzmatrix I(G):

I(G) = ( \begin{matrix}0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 \end{matrix} ) | \begin{matrix}a \\ b \\ c \\ d \\ e \\ f \\ g \end{matrix} ; \overline{a b c d e f g}

Abbildung 20: Inzidenzmatrix von G

Die Inzidenzmatirx I(G) hat an der Stelle (i, j) eine 1, falls {i, j} eine Kante von G ist, und eine 0 sonst. Jedenfalls hat – ganz allgemein – I(G) n^{2} Einträge. Würde man im Algorithmus von Moore eine Inzidenzmatrix statt der Adjazenzlisten verwenden, dann hätte der Algorithmus Komplexität O(n^{2}) statt O(m), was für viele Graphen deutlich mehr ist. Allgemein gilt:

Für die Komplexität von Algorithmen kommt es darauf an, welche Datenstrukturen verwendet werden.

Der Algorithmus von Moore lässt sich übrigens auch für Graphen verwenden, deren Kanten eine Richtung haben.

1In der Literatur allgemein als Adjazenzmatrizen eingeführt.

1.3.4 Gerichtete Graphen

Definition: Ein gerichteter Graph oder auch Digraph (engl.: directed graph) ist ein Paar G = (V, E), wobei V eine Menge ist und E eine Menge von geordneten Paaren (v, w) mit v, w ∈ V und v ≠ w. Man nennt wieder die Elemente von V Ecken und die Elemente von E Kanten von G. Anstelle von (v, w) wird oft kurz vw geschrieben, wobei es im Unterschied zu ungerichteten Graphen auf die Reihenfolge von v und w ankommt.

Viele der Begriffe für ungerichtete Graphen übertragen sich problemlos auf gerichtete Graphen. Beispielsweise heißt eine Folge (v_{0}, v_{1}, …, v_{k}) ein Kantenzug des gerichteten Graphen G, falls (v_{i}, v_{i+1}) eine Kante ist, für alle i. Die Länge dieses Kantenzuges ist k. Entsprechend werden Wege, Kreise und Abstände in gerichteten Graphen definiert. (Dabei wird zur Verdeutlichung oft der Zusatz ”gerichtet“ verwendet, zum Beispiel von ”gerichteten Wegen“ gesprochen.)

In folgendem Digraphen G ist zum Beispiel d(a, c) = 4 der Abstand zwischen a und c. Ein kürzester Weg von a nach c ist (a, d, f, g, c).

[figure: a; b; c; d; e; f; g; G]

Abbildung 21: Wege in ungerichteten Graphen

Aufgabe: Wende den Algorithmus von Moore auf diesen Digraphen an.

1.4 Abstände in Netzwerken

Jetzt wird jeder Kante eines Graphen eine Länge zugeordnet. Typische Beispiele sind Straßennetze mit Entfernungsangaben.

1.4.1 Netzwerke

Definition: Ein Netzwerk ist ein Paar (G, w), bestehend aus einem (gerichteten oder ungerichteten) Graphen G = (V, E) sowie einer Bewertung der Kanten von G mit reellen Zahlen, das heißt einer Funktion w: E ⟶ ℝ. Für jede Kante e ∈ E heißt w(e) die Länge (oder das Gewicht) von e. Für einen Kantenzug K = (v_{0}, v_{1}, …, v_{k}) ist

w(K) := w(v_{0}v_{1}) + w(v_{1}v_{2}) + … + w(v_{k−1}v_{k})

die Länge von K. (Hierbei steht z. B. v_{0}v_{1} als Abkürzung für {v_{0}, v_{1}} bzw. (v_{0}, v_{1}).)

Je nach Anwendung kann es sich bei den Längen bzw. Gewichten auch um Zeitdauern, Kosten, Gewinne und Verluste und vieles andere handeln. Deshalb ist es gerechtfertigt, auch negative Lösungen zuzulassen. Bei der Definition von Abständen würden negative Längen aber Probleme machen:

1.4.2 Der Abstandsbegriff

Definition: Sei (G, w) ein Netzwerk mit nichtnegativen Längen, das heißt mit w(e) ≥ 0 für alle Kanten e. Der Abstand d(a, b) zweier Ecken a, b von G ist definiert als das Minimum der Länge aller Kantenzüge von a nach b. Falls es keinen Kantenzug von a nach b gibt, wird d(a, b) = ∞ gesetzt.

Der folgende Algorithmus von Dijkstra (1959) berechnet die Abstände von einer gegebenen Ecke v_{0} eines Netzwerks. Er kann – wie auch der Algorithmus von Moore im vorigen Abschnitt – für gerichtete und ungerichtete Graphen verwendet werden:

1.4.3 Algorithmus von Dijkstra

Gegeben sei ein Netzerk (G, w) mit G = (V, E) und einer nichtnegativen Längenfunktion w auf E, sowie eine Ecke v_{0} von G. Für jedes v ∈ V wird ein Wert d(v) berechnet:

(1) d(v_{0}) ← 0,

(2) for v ∈ V \ {v_{0}} do

(3) d(v) ← ∞,

  (4) end,

(5) U ← V,

  (6) while U ≠ ∅ do

(7) u ← arg min_{v′∈U}{d(v′)},

(8) for v ∈ {v′ ∈ U | (u, v) ∈ E} do

(9) d(v) ← min{d(v), d(u) + w(u, v)},

 (10)  end,

(11) U ← U \ {u}

 (12) end.

Satz: Nach Durchführung des Algorithmus von Dijkstra gilt d(v) = d(v_{0}, v) für alle v ∈ V. Die Komplexität des Algorithmus ist O(n^{2}).

Beweis: Klar ist, dass (nach Beendigung des Algorithmus) genau dann d(v) = ∞ gilt, wenn v von v_{0} aus nicht erreichbar ist, d. h. im Fall d(v_{0}, v) = ∞. Für alle anderen v ∈ V ist d(v) offenbar die Länge eines Weges von v_{0} nach v, weshalb d(v) ≥ d(v_{0}, v) gilt.

Es bleibt d(v) ≤ d(v_{0}, v) zu zeigen. Dies gelingt mit Induktion über die Ecken von G, und zwar in der Reihenfolge, in der sie aus U entfernt wurden: Zuerst wird v_{0} entfernt und es gilt d(v_{0}) = d(v_{0}, v_{0}) = 0. Jetzt wird d(v) ≤ d(v_{0}, v) für alle vor der Ecke u aus U entfernten Ecken v vorausgesetzt. Zu zeigen ist d(u) ≤ d(v_{0}, u). Werde, im Gegenteil, d(u) > d(v_{0}, u) angenommen und sei (v_{0}, v_{1}, …, v_{k} = u) ein kürzester Weg von v_{0} nach u. Es gibt einen Index i < k, so dass v_{i} vor u aus U entfernt wurde, aber nicht v_{i+1}. Nach Induktionsvoraussetzung gilt d(v_{i}) ≤ d(v_{0}, v_{i}). Es folgt

d(u) > d(v_{0}, u) = d(v_{0}, v_{i}) + w(v_{i}v_{i+1}) + … + w(v_{k−1}u) ≥ d(v_{i}) + w(v_{i}v_{i+1})

Als v_{i} aus U entfernt wurde, galt aber d(v_{i})+w(v_{i}v_{i+1}) = d(v_{i+1}) ≤ d(v_{0}, v_{i+1}), also u ≠ v_{i+1}. Das ist ein Widerspruch, da u vor v_{i+1} aus U entfernt wird!

Für die Abschätzung der Komplexität müsste Zeile (7) eigentlich genauer formuliert werden. Aber es ist klar, dass man bei jedem Durchlauf von (7) mit maximal |U|−1 Vergleichen auskommt. In (9) sind jedesmal maximal |U| Wertzuweisungen nötig. Die Schleife (6) bis (12) wird insgesamt |V | mal durchlaufen. Da immer |U| ≤ |V | gilt, ergibt sich die behauptete Komplexität. □

Beispiel: Für folgendes Netzwerk liefert der Algorithmus von Dijkstra die Abstände von v_{0}. Die Werte d(v) sind in der Reihenfolge aufgelistet, in der die Ecken aus U entfernt werden:

\begin{matrix}v & a & d & f & e & g & c & b \\ d(v) & 0 & 3 & 4 & 6 & 6 & 6 & 11 \end{matrix}

[figure: v_{0} = a; b; c; d; e; f; g; 16; 6; 5; 8; 0; 2; 2; 4; 3; 1; 7; (G, w)]

Abbildung 22: Algorithmus von Dijkstra

Übrigens: Der Algorithmus von Dijkstra kann leicht so abgewandelt werden, dass er nicht nur die Abstände, sondern auch die kürzesten Wege berechnet.

1.5 Flüsse in Netzwerken

Dieser Abschnitt stellt ein Beispiel eines ”Min-Max-Satzes“ vor, nämlich den wohl berühmtesten (”max flow = min cut“, Ford-Fulkerson 1956). Es geht darum, wieviel in einem Netzwerk mit gegebenen Kapazitäten transportiert werden kann. Man denke an ein Stromnetz, ein Wasserleitungssystem, ein Straßennetz oder an Datenübertragungsnetzwerke.

1.5.1 Flussnetzwerke

Definition: Ein Flussnetzwerk (auch: Kapazitätsnetzwerk) besteht aus

• einem Digraphen G = (V, E),

• einer Kapazitätsfunktion c: E ⟶ ℝ_{0}^{+},

• zwei ausgezeichneten Ecken s, t ∈ V (Quelle, Senke).

Ein Fluss in einem solchen Netzwerk ist eine Abbildung f: E ⟶ ℝ_{0}^{+}, so dass folgendes gilt:

(F1) 0 ≤ f(e) ≤ c(e) für alle e ∈ E,
(F2) ∑_{(v,x)∈E^{x∈V}} f(v, x) = ∑_{(y,v)∈E^{y∈V}} f(y, v) für alle v ∈ V, v ≠ s, t.

[figure: s; t; a; b; c; d; e; 5(5); 2(7); 2(4); 2(7); 2(2); 0(4); 0(4); 3(3); 3(4); 1(2); 2(3); 3(3)]

Abbildung 23: Flussnetzwerke

Bedingung (F1) bedeutet, dass der Fluss nirgends negativ ist und immer die Kapazitäten eingehalten werden, (F2) bedeutet, dass in jede Ecke soviel hineinfließt wie herausfließt, allerdings mit Ausnahme der Quelle s und der Senke t.

In diesem Beispiel fließt aus der Quelle s ein Gesamtfluss von f(s, a) + f(s, d) = 5 + 2 = 7, und in die Senke f(a, t) + f(c, t) + f(e, t) = 3 + 2 + 2 = 7. Die Übereinstimmung der Werte ist kein Zufall, denn auf dem Weg von s nach t geht nichts verloren und wird nichts gewonnen.

Bemerkung: Für jede Flussfunktion f eines Flussnetzwerks mit Quelle s und Senke t gilt

∑_{(s,x)∈E^{x∈V}} f(s, x) − ∑_{(y,s)∈E^{y∈V}} f(y, s) = ∑_{(y,t)∈E^{y∈V}} f(y, t) − ∑_{(t,x)∈E^{x∈V}} f(t, x)

Beweis: Die folgende Gleichung gilt, da auf beiden Seiten über alle Kanten e ∈ E summiert wird:

∑_{v∈V} ∑_{(v,x)∈E} f(v, x) = ∑_{v∈V} ∑_{(y,v)∈E} f(y, v)

Hieraus folgt:

0 = ∑_{v∈V} ( ∑_{(v,x)∈E} f(v, x) − ∑_{(y,v)∈E} f(y, v))

= ( ∑_{(s,x)∈E} f(s, x) − ∑_{(y,s)∈E} f(y, s)) + ( ∑_{(t,x)∈E} f(t, x) − ∑_{(y,t)∈E} f(y, t))

wobei die letzte Gleichheit wegen (F2) gilt. □

1.5.2 Maximale Flüsse, zunehmende Wege

Falls es keine Kanten (y, s) und keine Kanten (t, x) gibt, dann schreibt sich die Gleichung der letzten Bemerkung kürzer als:

∑_{x} f(s, x) = ∑_{y} f(y, t)

Die Zahl auf beiden Seiten der Gleichung (oder der Gleichung in der letzten Bemerkung) wird der Wert des Flusses f genannt, in Zeichen: ϕ(f). Es ist immer das Ziel, einen maximalen Fluss zu finden, d. h. einen Fluss f mit maximalem Wert ϕ(f). Jetzt wird gezeigt, wie dies gelingt:

Definition: Ein zunehmender Weg (engl.: augmenting path) bzgl. eines gegebenen Flusses f ist eine Folge (s = v_{0}, v_{1}, …, v_{k} = t), so dass für jedes i ∈ {1, …, k} eine der folgenden beiden Bedingungen gilt:

(v_{i−1}, v_{i}) ∈ E und f(v_{i−1}, v_{i}) < c(v_{i−1}, v_{i}) ”Vorwärtskante“
(v_{i}, v_{i−1} ∈ E und f(v_{i}, v_{i−1}) > 0  ”Rückwüartskante“

[figure: s; t; Vorwärtskante; Rückwärtskante]

Abbildung 24: Zunehmender Weg

1.5.3 Augmenting Path Theorem

Ein Fluss f in einem Flussnetzwerk ist genau dann ein maximaler Fluss, wenn bezüglich f kein zunehmender Weg existiert.

Beweisskizze: ⟹: Beweis mit Kontraposition. Sei W ein zunehmender Weg bezüglich f. Dann kann der Flusswert ϕ(f) entlang W um das Minimum folgender Werte gesteigert werden:

{c(e) − f(w) | e Vorwärtskante in W } ∪ {f(e) | e Rückwärtskante in W }

⟸: Es gebe keinen zunehmenden Weg bezüglich f. Werde definiert: S := {v ∈ V | es gibt einen zunehmenden Weg von s nach v}, T := V \ S Es gilt s ∈ S und, nach Voraussetzung, t ∈ T. Die Kanten zwischen S und T sind ”gesättigt“:

• für jedes (v, w) ∈ E mit v ∈ S, w ∈ T gilt f(v, w) = c(v, w)

• für jedes (w, v) ∈ E mit w ∈ T, v ∈ S gilt f(w, v) = 0.

[figure: f(e) = c(e); f(e) = 0; s; t; S; T]

Abbildung 25: Minimaler Kantenschnitt

Also: die Kanten zwischen S und T bilden einen Engpass, der eine Flusswertvergrößerung verhindert. □

Der Beweis kann mit Hilfe der Flussregeln (F1) und (F2) streng formal geführt werden. Aber das soll hier nicht geschehen, auch für die folgenden Überlegungen nicht: Die Kapazität einer Kantenmenge F ⊆ E ist definiert als

c(F): = ∑_{e∈F} c(e)

Im Fall einer Zerlegung V = S ˙∪ T mit s ∈ S und t ∈ T (wie auf voriger Seite) werden die Kantenmengen E_{S→T} und E_{T →S} folgendermaßen definiert:

E_{S→T}: = {(x, y) ∈ E | x ∈ S, y ∈ T }  (Kanten von S nach T)
E_{T →S}: = {(x, y) ∈ E | x ∈ T, y ∈ S}  (Kanten von T nach S)

Intuitiv sollte – wegen (F1) und (F2) – klar sein, dass folgendes gilt:

Lemma: Sei f ein Fluss und V = S ˙∪ T mit s ∈ S, t ∈ T. Dann gilt

ϕ(f) = ∑_{e∈E_{S→T}} f(e) − ∑_{e∈E_{T →S}} f(e) ≤ c(E_{S→T})

Insbesondere ist für jeden Fluss f der Wert ϕ(f) beschränkt durch die Kapazität c(E_{S→T}) der Kantenmenge E_{S→T}. (Jede solche Kantenmenge wird s und t trennender Schnitt genannt.)

1.5.4 Minimaler Schnitt

Wie in der Beweisskizze des Augmenting Path Theorems angedeutet, existiert im Fall eines maximalen Flusses f ein s und t trennender Schnitt E_{S→T} mit ϕ(f) = c(E_{S→T}).

Dieser Schnitt ist ein minimaler Schnitt, das heißt ein s und t trennender Schnitt von minimaler Kapazität (denn sonst wäre ϕ(f) durch die Kapazität eines anderen Schnitts beschränkt). Deshalb gilt der berühmte Satz von L.R. Ford und D.R. Fulkerson (1956):

1.5.5 Max-Flow Min-Cut Theorem

Satz: In jedem Flussnetzwerk ist der Wert eines maximalen Flusses von Quelle s zur Senke t gleich der Kapazität eines minimalen s und t trennenden Schnitts.

Der Beweis des Augmenting Path Theorems gibt eine Idee für einen Algorithmus zum Auffinden maximaler Flüsse und minimaler Schnitte.

Skizze eines Algorithmus: Sei ein Fluss f von s nach t gegeben (f(e) = 0 für alle e ∈ E ist möglich):

1. Falls es keinen zunehmenden Weg von s nach t gibt, dann STOP. Sonst weiter mit 2.

2. Sei (v_{0}, v_{1}, ⋯, v_{k}) ein zunehmender Weg bzgl. f. Setze

z := min({c(v_{i−1}, v_{i}) − f(v_{i−1}, v_{i}) | (v_{i−1}, v_{i})Vorwärtskante} ∪

{f(v_{i}, v_{i−1}) | (v_{i}, v_{i−1})Rückwärtskante})

Sei

f(v_{i−1}, v_{i}): = f(v_{i−1}, v_{i}) + z für jede Vorwärtskante und

f(v_{i}, v_{i−1}): = f(v_{i}, v_{i−1}) − z für jede Rückwärtskante. Weiter mit (1).

Wie findet man zunehmende Wege? Dies gelingt schrittweise, indem jede Ecke y eines zunehmenden Weges mit drei Werten v(y), r(y), z(y) markiert wird:

v(y) Vorgänger von y im zunehmenden Weg,

r(y) Richtung der Kante von v(y) nach y: r(y) =→ für Vorwärtskante,

r(y) =← für Rückwärtskante,

z(y) möglicher zusätzlicher Flusswert von s nach y.

1.5.6 Markierungs-Algorithmus (Ford-Fulkerson)

Sei ein Flussnetzwerk, bestehend aus einem Digraphen G und einer Kapazitätsfunktion c mit Quelle s und Senke t, gegeben. Sei f ein Fluss auf diesem Netzwerk.

(1) Setze S: = {s}, R: = {s}, z(s): = ∞.

(2) Wähle eine Ecke x ∈ R. Setze R := R \ {x}.

(3) Füge jede Ecke y ∈ V \ S mit (x, y) ∈ E und f(x, y) < c(x, y) zu S und zu R hinzu und setze v(y): = x, r(y): =→, z(y): = min{c(x, y) − f(x, y), z(x)}.

(4) Füge jede Ecke y ∈ V \ S mit (y, x) ∈ E und f(x, y) > 0 zu S und zu R hinzu und setze: v(y): = x, r(y): =←, z(y): = min{f(y, x), z(x)}.

(5) Falls R = ∅, dann STOP. Falls t ∈ S, dann weiter mit (6). Sonst weiter mit (2).

(6) Setze z: = z(t), y: = t.

(7) Falls r(y) =→, setze f(v(y), y): = f(v(y), y) + z. Falls r(y) =←, setze f(y, v(y)): = f(y, v(y)) − z.

(8) Setze y: = v(y). Falls y = s, weiter mit (1). Sonst weiter mit (7).

Die Menge S besteht jeweils aus den Ecken, zu denen von s aus ein zunehmender Weg gefunden wurde, und R besteht aus denjenigen Ecken in S, die noch nicht benutzt wurden, um längere zunehmende Wege zu erhalten. Im Fall R = ∅ gibt es keine weiteren zunehmenden Wege, das heißt der bis dahin gefundene Fluss f ist maximal.

Falls alle Kapazitäten ganzzahlig sind, c(e) ∈ ℤ für alle e ∈ E, dann terminiert der Algorithmus (da alle Flusszuwächse ganzzahlig sind). Also wird der STOP-Befehl in Zeile (5) erreicht. Dasselbe gilt, falls alle Kapazitäten rationale Zahlen sind, c(e) ∈ ℚ.

Satz: Für jedes Flussnetzwerk mit rationalen Kapazitätswerten berechnet der Markierungsalgorithmus einen maximalen Fluss f und eine Eckenmenge S, so dass (mit T: = V \ S) E_{S→T} ein minimaler s und t trennender Schnitt ist.

Bemerkungen

(a) Im Fall von irrationalen Kapazitätswerten kann es vorkommen, dass der Algorithmus unendlich viele Flusszunahmen berechnet, also nie stoppt (und möglicherweise nicht einmal in die Nähe eines maximalen Flusses kommt).

(b) Selbst für ganzzahlige Kapazitäten ist die Komplexität des Markierungsalgorithmus nicht polynomial in n = |V | oder m = |E|, da die Anzahl der Schritte von der Kapazitätsfunktion c abhängen kann. Zeile (2) im Algorithmus ist sehr unklar formuliert. Organisiert man in (2) die Reihenfolge, in der die Ecken ausgewählt werden, wie im Algorithmus von Moore (Seite 27), also nach dem Schema ”breadth first search“, dann wird Komplexität O(nm^{2}) erreicht. Dies wurde 1992 von Edmonds und Karp gezeigt. Mit noch weiter entwickelten Methoden (zum Beispiel von Sleator und Tarjan) kann man sogar Komplexität O(nm log n) eingehalten werden.

Beispiel: Es wird der Markierungsalgorithmus auf den Fluss auf Seite 32 angewandt. Dieser hatte den Flusswert ϕ(f) = 7. Es ergibt sich ein minimaler Schnitt mit S = {s, a, b, d, e} und T = {c, t}. Damit ist der Fluss f maximal mit ϕ(f) = 9.

[figure: Ausgangssituation:; s; t; a; b; c; d; e; 5(5); 2(7); 2(4); 2(7); 2(2); 0(4); 0(4); 3(5); 3(4); 1(2); 2(3); 3(3); ϕ(f) = 7; Erste Flussänderung:; s; t; a; b; c; d; e; 5(5); 2(4); 2(2); 0(4); 0(4); 3(5); 3(4); 3(3); 3(7); 3(3); 0(2); 3(7); \begin{aligned}& v r z \\ s & ∞ \\ a & d → 1 \\ b & a → 1 \\ c & a ← 1 \\ d & s → 5 \\ e & d → 4 \\ t & c → 1 \end{aligned}; ϕ(f) = 8; Zweite Flussänderung:; s; t; a; b; c; d; e; 5(5); 4(7); 1(4); 4(7); 0(2); 1(4); 0(4); 4(5); 4(4); 1(2); 3(3); 3(3); \begin{aligned}& v r z \\ s & ∞ \\ a & e ← 2 \\ b & a → 2 \\ c & b → 1 \\ d & s → 4 \\ e & d → 4 \\ t & c → 1 \end{aligned}; ϕ(f) = 9; Minimaler Schnitt/Maximaler Fluss:; s; t; a; b; c; d; e; 5(5); 4(7); 1(4); 4(7); 0(2); 1(4); 0(4); 4(5); 4(4); 1(2); 3(3); 3(3); \begin{aligned}& v r z \\ s & ∞ \\ a & d → 1 \\ b & a → 1 \\ c \\ d & s → 5 \\ e & d → 4 \\ t \end{aligned}; ϕ(f) = 9]

Abbildung 26: Markierungsalgorithmus

Es gibt unzählige Anwendungen des Markierungsalgorithmus und des darauffolgenden Satzes. Beides kann auf viele Situationen angepasst werden, beispielsweise

• auf Flussnetzwerke mit mehreren Quellen und Senken,

• auf Flussnetzwerke mit zusätzlichen Kapazitätsbeschränkungen in Ecken,

• auf Flussnetzwerke mit Gewinnen und Verlusten in den Ecken,

und auf vieles mehr.

1.6 Gruppen und Permutationen

Im Rest dieses Kapitels werden ”Symmetrien von Graphen“ und das Zählen gewisser Objekte ”bis auf Symmetrie“ behandelt. Die mathematische Betrachtung von Symmetrie führt direkt zum Begriff ”Permutationsgruppe“. Damit wird - nebenbei - der Übergang zum nächsten Kapitel über algebraische Strukturen vorbereitet. Aber zuerst einige gruppentheoretische Grundbegriffe:

1.6.1 Gruppen

Definition: Eine Gruppe ist ein Paar (G, ·), bestehend aus einer nichtleeren Menge G sowie einer zweistelligen Operation · auf G (das heißt eine Abbildung G × G → G, (x, y) ↦ x · y), so dass folgende Regeln erfüllt sind:

(ass) ∀x, y, z ∈ G: (x · y) · z = x · (y · z)  Assoziativität,
(neu) ∃e ∈ G∀x ∈ G: e · x = x = x · e  neutrales Element,
(inv) ∀x ∈ G∃x^{−1} ∈ G: x · x^{−1} = e = x^{−1} · x inverse Elemente.

Gilt außerdem noch

(kom) ∀x, y ∈ G: x · y = y · x Kommutativität,

so spricht man von einer abelschen (oder kommutativen) Gruppe.

Bemerkungen

(a) Anstelle von x · y wird oft auch einfach xy geschrieben.

(b) Man kann leicht zeigen, dass das neutrale Element e einer Gruppe eindeutig bestimmt ist, das heißt es kann nicht zwei verschiedene solche Elemente geben. Regel (inv) bezieht sich auf das (eindeutig bestimmte) neutrale Element e. Für jedes x ∈ G ist das inverse Element x^{−1} ebenfalls eindeutig bestimmt.

(c) In abelschen Gruppen wird oft +, −, 0 anstelle von ·,^{−1} , e geschrieben (additive Schreibweise).

Beispiele

(a) (ℤ, +), (ℚ, +), (ℚ \ {0}, ·) sind abelsche Gruppe. Hingegen sind (ℤ, ·), (ℚ, ·), (ℕ, ·) und (ℕ, +) keine Gruppen. Für jedes n ∈ ℕ ist (ℤ_{n}, +) eine abelsche Gruppe (auf der Grundmenge ℤ_{n} = {0, 1, …, n − 1} wird ”modulo n“ gerechnet).

(b) Die folgende Verknüpfungstafel definiert eine Gruppenoperation auf der Grundmenge G = {e, s, t, u, v, w}:

\begin{matrix}· & e & s & t & u & v & w \\ e & e & s & t & u & v & w \\ s & s & e & w & v & u & t \\ t & t & v & e & w & s & u \\ u & u & w & v & e & t & s \\ v & v & t & u & s & w & e \\ w & w & u & s & t & e & v \end{matrix}

(c) Eine Permutation auf einer Menge A ist eine bijektive Abbildung f: A → A. Die Menge aller Permutationen auf A wird mit S_{A} bezeichnet. (Im Fall |A| = n schreibt man auch S_{n}.) Für zwei Permutationen f, g auf A ist die Verkettung (Komposition, Hintereinanderausführung) f ∘ g definiert durch

(f ∘ g)(x): = f(g(x))

für alle x ∈ A. Für jede Menge A ist (S_{A}, ∘) eine Gruppe (die symmetrische Gruppe auf A).

Definition: Ist (G, ·) eine Gruppe und H eine Teilmenge von G, die mit der auf G erklärten Gruppenoperation selbst eine Gruppe darstellt, dann nennt man H eine Untergruppe von G (in Zeichen: H ⩽ G).

Bemerkungen: Offenbar ist H genau dann eine Untergruppe von G, wenn folgendes gilt:

(1) H ist nicht leer,
(2) für alle a, b ∈ H gilt ab ∈ H,
(3) für alle a ∈ H gilt a^{−1} ∈ H

Man müsste H eigentlich genauer die ”Grundmenge einer Untergruppe“ nennen; die Untergruppe selbst ist das Paar (H, ·), wobei man die Gruppenoperation ”·“ auf H eingeschäntkt betrachten muss.

1.6.2 Links- und Rechtsnebenklassen

Sei H eine Untergruppe von G. Für jedes g ∈ G ist die Linksnebenklasse von g als die Menge gH := {gh | h ∈ H} definiert. (Entsprechend nennt man Hg := {hg | h ∈ H} die Rechtsnebenklasse von g.) Die Menge aller Linksnebenklassen der Untergruppe H wird mit G/H bezeichnet. Für je zwei Elemente g_{1}, g_{2} ∈ G gilt entweder g_{1}H = g_{2}H oder g_{1}H ∩g_{2}H = ∅. Die Linksnebenklassen bilden also eine disjunktive Überdeckung der Menge G. Außerdem sind die Linksnebenklassen alle gleich groß, für alle g ∈ G gilt |gH| = |H|. Eine bijektive Abbildung von H auf gH wird gegeben durch h ⟶ gh. Es folgt:

1.6.3 Satz von Lagrange

Satz: Sei G eine endliche Gruppe und H eine Untergruppe von G. Dann gilt:

|H| | |G|

Die Ordung (das heißt die Anzahl der Elemente) der Untergruppe H teilt also die Ordnung von G.

Die Ordnung eines Elementes a ∈ G ist definiert als die Zahl k mit a^{k} = e. (Wenn eine solche Zahl nicht existiert, dann setzt man ord(a) = ∞.) Für jedes Element a ∈ G ist offenbar ⟨a⟩ := {a^{i} | i ∈ ℤ} die kleinste Untergruppe von G, die a enthält (die von a erzeugte Untergruppe, solche von einem Element erzeugten Untergruppen werden zyklisch genannt). Wenn die Ordnung von a endlich ist, dann hat die Untergruppe ⟨a⟩ genau ord(a) Elemente, nämlich a, a^{2}, …, a^{ord(a)}. Mit dem Satz von Lagrange folgt hieraus Teil (a) des Korollars. Die Teile (b) und (c) sind dann klar:

Korollar: Für jedes Element a einer endlichen Gruppe G gilt

ord(a) | |G|

Für jedes Gruppenelement a einer endlicher Ordnung und jede Zahl k ∈ ℤ gilt

a^{k} = e ⟺ ord(a) | k

Für jedes Element a einer endlichen Gruppe G gilt

a^{|G|} = e

Im Rest des Kapitels richtet sich das Interesse auf Permutationsgruppen:

1.6.4 Permutationsgruppen

Definition: Sei A eine Menge. Jede Untergruppe G der symmetrischen Gruppe S_{A} heißt Permutationsgruppe auf A. (S_{A} ist die Menge aller bijektiven Abbildungen A ⟶ A.) Der Anzahl |A| der Elemente von A wird der Grad der Permutationsgruppe G genannt.

Eine Permutationsgruppe auf A ist also eine nicht leere Menge von Permutationen der Menge A, die gegen Verkettung und Inversenbildung abgeschlossen ist. Klar ist:

Bemerkungen: Für alle n ∈ ℕ gilt |S_{n}| = n!. Für jede Permutationsgruppe G auf A von Grad n (also mit |A| = n) gilt

|G| | n!

Es gibt verschiedene Möglichkeiten, Permutationen darzustellen. Eine Möglichkeit sind Wertetabellen, zum Beispiel:

f = ( \begin{matrix}0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 0 & 5 & 8 & 6 & 1 & 4 & 7 & 3 & 9 & 2 \end{matrix} )

g = ( \begin{matrix}0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ 0 & 1 & 6 & 8 & 5 & 4 & 2 & 9 & 3 & 7 \end{matrix} )

Als Produkt ziffernfremder Zyklen (kurz: Zyklendarstellung) schreibt man f und g als

f = (154)(289)(367), g = (26)(38)(45)(79).

Hierbei steht zum Beispiel (145) für die Permutation, die 1 auf 5, 5 auf 4, 4 auf 1 abbildet. Solche Permutationen heißen Zyklen, und jede Permutation (auf endlicher Grundmenge A) ist ein Produkt von endlichen Zyklen.

Definition: Die Permutationsgruppe G operiere auf A, und es sei a ∈ A. Die Menge

a^{G} := {g(a) | g ∈ G}

heißt Bahn (oder Orbit) von a unter G. Der Stabilisator (oder die Standuntergruppe) von a in G ist

G_{a} := {g ∈ G | g(a) = a}

Allgemeiner definiert man den Stabilisator einer Teilmenge B ⊆ A als

G_{B} := {g ∈ G | ∀b ∈ B : g(b) = b}

Im Fall B = {b_{1}, …, b_{n}} wird statt G_{B} auch G_{b_{1}...b_{n}} geschrieben.

Die Bahn von a besteht also aus den Elementen von A, zu denen man von a aus durch Anwendung von Permutationen aus G gelangen kann. Wenn es nur eine einzige Bahn gibt, das heißt im Fall a^{G} = A, dann nennt man G transitiv. Der Stabilisator von a ist selbst eine Permutationsgruppe, also eine Untergruppe von G. Die nächsten beiden Lemmata sind von größter Bedeutung:

Lemma: Für jede Permutationsgruppe G auf A und jedes a ∈ A gilt:

|G| = |a^{G}| · |G_{a}|

Beweis: Für f, g ∈ G gilt genau dann f(a) = g(a), wenn (g^{−1}f)(a) = a gilt. Dies ist äquivalent zu (g^{−1}f ∈ G_{a}), was auch als f ∈ gG_{a} geschrieben werden kann. Also entspricht jedes Element von a^{G} genau einer Linksnebenklasse gG_{a} von G_{a} in G. Bekanntlich gibt es genau |G|/|G_{a}| solcher Nebenklassen. Es folgt |a^{G}| = |G|/|G_{a}|.

Bei näherer Betrachtung dieses Beweises erhält man, zusätzlich zur Bestimmung der Anzahl der Elemente von G, folgende nähere Beschreibung der Elemente von G:

Lemma: Die Bahn a^{G} bestehe aus genau k verschiedenen Elementen a_{1}, …, a_{k}, und für jedes dieser Elemete sei g_{i} eine Permutation g_{i} ∈ G mit g_{i}(a) = a_{i}. Dann lässt sich jedes g ∈ G in genau einer Weise in der Form g = g_{i}h mit i ∈ {1, …, k} und h ∈ G_{a} darstellen.

Beweis: G ist die disjunktive Vereinigung der Linksnebenklassen g_{1}G_{a}, …, g_{k}G_{a}. □

Im nächsten Abschnitt folgen Anwendungsbeispiele!

1.7 Symmetrien von Graphen

Die Symmetrien dieses Abschnitts sind nichts als die Automorphismen von Graphen:

1.7.1 Automorphismen

Definition: Ein Automorphismus eines Graphen Γ = (V, E) ist eine bijektive Abbildung α: V ⟶ V, so dass für alle x, y ∈ V folgendes gilt:

{x, y} ∈ E ⟺ {α(x), α(y)} ∈ E

Ein Automorphismus von Γ ist also ein Isomorphismus von Γ auf sich selbst.

Anmerkung: Graphen werden jetzt mit Γ bezeichnet, zur Unterscheidung von Gruppen.

Beispiel: Die Permutation f und g von Seite 39 sind Automorphismen des Petersengraphen, wenn man die Ecken so bezeichnet wie in der Skizze.

[figure: 0; 4; 3; 2; 1; 5; 9; 8; 7; 6]

Abbildung 27: Petersengraph

Man kann die Automorphismen als die Symmetrien eines Graphen auffassen. Ist α ein Automorphismus von Γ mit α(x) = y, dann bedeutet das, dass Γ von x aus ”genauso aussieht“ wie von y aus.

1.7.2 Automorphismengruppe

Für jeden Graphen Γ = (V, E) bilden die Automorphismen eine Permutationsgruppe auf V. Diese Gruppe wird die Automorphismengruppe von Γ genannt und mit G(Γ) bezeichnet.

Beispiele

(a) Die Automorphismengruppe des vollständigen Graphen K_{n} (n Ecken, je zwei Ecken durch eine Kante verbunden) ist die volle symmetrische Gruppe S_{n}.

(b) Der n-elementige Kreis C_{n} hat für n ≥ 3 als Automorphismengruppe die Diedergruppe D_{n} (sprich: Di-eder). Diese Gruppe besteht aus 2n Elementen.

(c) Der Graph Γ hat nur die identische Abbildung als Automorphismus.

[figure: K_{4}; G(K_{4}) = S_{4}; C_{4}; G(C_{4}) = D_{4}; Γ; G(Γ) = {id}]

Abbildung 28: Graphenautomorphismen

Mit dem Lemma von Seite 40 ergibt sich unmittelbar das folgende Verfahren:

1.7.3 Bestimmung der Automorphismengruppe

Verfahren zur Bestimmung der Automorphismengruppe eines Graphen: Der Graph sei Γ = (V, E), und die Automorphismengruppe G(Γ) werde kurz mit G bezeichnet.

1. Wähle eine Ecke a ∈ V. Bestimme eine möglichst kleine Menge A = {g_{1}, …, g_{ℓ}} ⊆ G mit a^{G} = {g_{1}(a), …, g_{ℓ}(a)}. Dann gilt g_{i}(a) ≠ g_{j}(a) für i ≠ j, und jedes g ∈ G lässt sich in genau einer Weise in der Form g = g_{i}h mit i ∈ {1, …, ℓ} und h = G_{a} schreiben.

2. Falls die Elemente von G_{a} nicht bekannt sind, kann das Verfahren mit G_{a} anstelle G wiederholt werden: Wähle eine Ecke b ≠ a und bestimme anschließend eine möglichst kleine Menge B = {h_{1}, …, h_{m}} ⊆ G_{a} mit b^{G_{a}} = {h_{1}(b), …, h_{m}(b)}. Jedes g ∈ G lässt sich jetzt genau in einer Weise in der Form g = g_{i}h_{j}k mit i ∈ {1, …, ℓ}, j ∈ {1, …, m}, k ∈ G_{ab} schreiben.

3. Diese Prozedur wird solange wiederholt, bis man schießlich einen Stabilisator erhält, dessen Elemente man kennt. Das ist spätestens der Fall, wenn der Stabilisator nur noch aus der identischen Abbildung besteht.

Bei der Auswahl der Elemente a, b, … kann man mehr oder weniger geschickt sein. Im Allgemeinen ist es günstig, wenn die Bahnen a^{G}, b^{G_{a}}, … groß sind, da das Verfahren dann nach weniger Durchläufen abbricht als bei kleineren Bahnen. Die Mengen A, B, … findet man im wesentlichen durch Probieren.

Beispiel: Es wird der ”Würfelgraph“ Γ behandelt. Klar ist: α_{1} = (abcd)(efgh) und α_{2} = (ae)(bf)(cg)(dh) sind Automorphismen von Γ. Es gilt:

id(a) = a, α_{1}(a) = b, α_{1}^{2}(a) = c, α_{1}^{3}(a) = d,
α_{2}(a) = e, α_{1}α_{2}(a) = f, α_{1}^{2}α_{2}(a) = g, α_{1}^{3}α_{2}(a) = h

[figure: d; c; a; b; h; g; e; f; Γ]

Abbildung 29: Würfelgraph

Das liefert a^{G} = {a, b, c, d, e, f, g, h} = V. Daher kann man

A = {id, α_{1}, α_{1}^{2}, α_{1}^{3}, α_{2}, α_{1}α_{2}, α_{1}^{2}α_{2}, α_{1}^{3}α_{2}}

wählen. Jetzt wird b^{G_{a}} bestimmt. Klar ist b^{G_{a}} ⊆ {b, d, e}, denn da a festbleibt, kann b nur auf zu a benachbarte Ecken abgebildet werden. Mit dem Automorphismus β = (bde)(chf) (”Drehung um die Würfeldiagonale durch a und g“) ergibt sich:

id(b) = b, β(b) = d, β^{2}(b) = e

Daher gilt b^{G_{a}} = {b, d, e}, und es kann

B = {id, β, β^{2}}

gewählt werden. Offenbar gilt G_{a_{b}} = {id, γ} mit γ = (cf)(de). Damit ist G vollständig bestimmt: Jedes g ∈ G lässt sich auf genau eine Weise in folgender Form schreiben:

g = α_{1}^{i}α_{2}^{j}β^{k}γ^{ℓ} mit i ∈ {0, 1, 2, 3}, j, ℓ ∈ {0, 1}, k ∈ {0, 1, 2}

Es folgt insbesondere G = ⟨α_{1}, α_{2}, β, γ⟩, das heißt die Gruppe G wird von den Elementen α_{1}, α_{2}, β, γ erzeugt (wobei es bei dieser Betrachtung nicht darauf ankommt, in welcher Reihenfolge diese Elemente multipliziert werden müssen).

Interessiert man sich nur für die Mächtigkeiten, dann liefert obiges:

|a^{G}| = 8, |b^{G_{a}}| = 3, |G_{a_{b}}| = 2

Das Lemma von Seite 40 liefert:

|G_{a}| = |b^{G_{a}}| · |G_{a_{b}}| = 3 · 2 = 6, also |G| = |a^{G}| · |G_{a}| = 8 · 6 = 48

1.8 Die Pólyasche Abzählmethode

In diesem Abschnitt wird eine gruppentheoretische Methode zur Lösung des folgenden Problems entwickelt (und natürlich zur Lösung vieler anderer Probleme):

Wieviele Perlenketten nur aus weißen und schwarzen Perlen gibt es, die genau drei weiße und drei schwarze Perlen enthalten?

Hierbei komme es nur auf die Farbe der Perlen an und auf die Reihenfolge, in der sie aufeinanderfolgen. Zuerst muss geklärt werden, wann zwei Perlenketten als ”gleich“ betrachtet werden sollen. Sind die Ketten (i) und (ii) wesentlich verschieden? Wenn man die Ketten drehen darf, dann wohl nicht. Auch die Ketten (ii) und (iii) sind gleich, wenn man die Ketten wenden darf. Das Problem ist also: Welches sind die zulässigen Symmetrien?

[figure: (i); (ii); (iii)]

Abbildung 30: Die Pólyasche Abzählmethode

Diese bilden im Ganzen eine Permutationsgruppe. Die in obigen Skizzen auftretenden Symmetrien können in Zyklenschreibweise notiert werden:

τ := (012345)  Drehen der Ketten um eine Perle
σ := (0)(3)(15)(24) Wenden einer Kette

Erlaubt man beides als zulässige Symmetrien, so erhält man insgesamt als Symmetriengruppe die Diedergruppe D_{6}, bestehend aus den Drehungen τ^{i} und den Spiegelungen στ^{i}, i = 0, …, 5. Dieses Beispiel wird unten weiter verfolgt.

Es folgt ein für die Pólya-Theorie grundlegender Satz über Permutationsgruppen. Darin, oder im Beweis, tauchen a^{G} für die Bahn von a unter der Permutationsgruppe G auf, und G_{a} für den Stabilisator von a unter G. Außerdem wird verwendet:

b(G) := |{a^{G} | a ∈ A}|  Anzahl der Bahnen von G
Fix(g) := {a ∈ A | g(a) = a} Menge der Fixpunkte von g ∈ G

Das folgende Resultat ist höchst erstaunlich. Es besagt: Die Anzahl der Bahnen von G ist gleich der durchschnittlichen Anzahl der Fixpunkte in G:

1.8.1 Cauchy-Frabenius-Lemma

Lemma: Für jede Permutationsgruppe G gilt

b(G) = \frac{1}{|G|} ∑_{g∈G} |Fix(g)|

Beweis mit doppelter Abzählung für die Relation I ⊆ A × G mit

aIg :⇔ g(a) = a

Jedes a ∈ A inzidiert mit genau |G_{a}| Elementen von G, und jedes a ∈ A mit genau |Fix(g)| Elementen von A, also

⊛  ∑_{a∈A} |G_{a}| = ∑_{g∈G} |Fix(g)|

Umformung der linken Seite mit dem Lemma von Seite 40 liefert

∑_{a∈A} |G_{a}| = ∑_{a∈A} \frac{|G|}{|a^{G}|} = |G| · ∑_{a∈A} \frac{1}{|a^{G}|}

Zur Auswertung der letzten Summe beachte man: Für eine gegebene Bahn c^{G} und alle a ∈ c^{G} gilt a^{G} = c^{G}. Deshalb:

∑_{a∈c^{G}} \frac{1}{|a^{G}|} = 1,

das heißt jede Bahn a^{G} liefert zur Summe den Beitrag 1. Mit Hilfe von ⊛ ergibt sich jetzt die Behauptung. □

1.8.2 Färbung

Sei weiterhin G eine auf A operierende Permutationsgruppe. Eine Färbung von A mit einer ”Farbmenge“ F ist definiert als eine Abbildung Φ: A ⟶ F. Die Menge aller Färbungen ist dann

Ã := F^{A} (Menge aller Abbildungen A ⟶ F).

Aus jedem g ∈ G wird in natürlicher Weise eine Permutation g̃ auf Ã. Für die ”Bildfärbung“ g̃Φ (Bild von Φ unter g̃) sollte (g̃Φ)(ga) = Φ(a) gelten.

Definition: Aus G wird eine Permutationsgruppe G̃ = {g̃ | g ∈ G} auf der Menge Ã = F^{A} der Färbungen von A gegeben durch

(g̃Φ)(a) := Φ(g^{−1}a)

Wann gelten zwei Färbungen als gleich? Genau dann, wenn sie in derselben Bahn bezüglich G̃ liegen! Also mit den Cauchy-Frabenius-Lemma:

Bemerkung: Die Anzahl der (bezüglich G) wesentlich verschiedenen Färbungen von A ist

b(G̃) = \frac{1}{|G̃|} ∑_{g̃∈G̃} |Fix(g̃)|

Statt g̃ ∈ G̃ kann g ∈ G geschrieben werden, und |G̃| = |G| ist ohnehin klar. Für jedes g ∈ G ist |Fix(g̃)| zu bestimmen: Φ ∈ Fix(g̃) bedeutet g̃Φ = Φ, also (g̃Φ)(a) = Φ(a) für alle a ∈ A. Mit obiger Definition ergibt das

Φ(g^{−1}a) = Φ(a)

Das bedeutet:

Beobachtung: Fix(g̃) besteht aus genau denjenigen Färbungen Φ, die innerhalb jedem Zyklus der Zyklendarstellung von g alle Elemente gleich färben. Also: Gibt es genau f = |F | Farben und hat g genau k Zyklen, dann gilt

|Fix(g̃)| = f^{k}

1.8.3 Permutationstypen

Diese Tatsachen lassen sich am besten ausnutzen, wenn man den Permutationstyp t(g) von g verwenden kann. Bei diesem handelt es sich um einen formalen Ausdruck der Form

t(g) = ∏_{i=1}^{n} z_{i}^{k(i)}

wobei n = |A| die Anzahl der Elemente der Grundmenge ist, und k(i) die Anzahl der Zyklen von g der Länge i angibt. Ist k die Anzahl aller Zyklen von G, dann gilt k = ∑ k(i). Als Beispiel wird die Diedergruppe D_{6} betrachtet (siehe Seite 43). Sie besteht aus folgenden Permutationen:

\begin{matrix}τ^{0} = id = (0)(1)(2)(3)(4)(5), & στ^{0} = σ = (0)(3)(15)(24), \\ τ^{1} = τ = (012345), & στ^{1} = στ = (05)(14)(23), \\ τ^{2} = (024)(135), & στ^{2} = (04)(13)(2)(5), \\ τ^{3} = (03)(14)(25), & στ^{3} = (03)(12)(45), \\ τ^{4} = (042)(153), & στ^{4} = (02)(1)(35)(4), \\ τ^{5} = (054321), & στ^{5} = (01)(25)(34). \end{matrix}

Diese Permutationen werden im Folgenden noch verwendet. Jedenfalls lässt sich die obige Formel |Fix(g̃)| = f^{k} mit den Permutationstypen etwas umständlicher schreiben als:

|Fix(g̃)| = ∏_{i=1}^{n} f^{k(i)}

Zu einer weiteren (später nützlichen) Formalisierung kommt es mit dem Zyklenzeiger ℨ(G) von G (es handelt sich um ein Polynom in z_{1}, …, z_{n}):

ℨ(G) := \frac{1}{|G|} ∑_{g∈G} t(g)

Die Bemerkung von Seite 45 lässt sich damit in kompakter Form schreiben:

Satz: Die Anzahl der (bezüglich G) wesentlich verschiedenen Färbungen von A mit einer f-elementigen Farbenmenge beträgt genau

ℨ(G|f)

(Diese Zahl entsteht auf ℨ(G) durch Einsetzen von z_{i} = f für alle z_{i} und anschließendes Ausrechnen.)

Es wird weiter das Beispiel G = D_{6} betrachtet. Folgende Tabelle (abgeleitet von der Aufstellung aller Permutationen auf voriger Seite) hilft bei der Orientierung:

Permutation  Zyklengestalt  (Permutations-)Typ
τ^{0} = id  (x) (x) (x) (x) (x) (x)  z_{1}^{6}
τ, τ^{5}  (xxxxxx)  z_{6}^{1}
τ^{2}, τ^{4}  (xxx) (xxx)  z_{3}^{2}
τ^{3}, στ, στ^{3}, στ^{5}  (xx) (xx) (xx)  z_{2}^{3}
σ, στ^{2}, στ^{4}  (x) (x) (xx) (xx)  z_{1}^{2}z_{2}^{2}

Also: ℨ(D_{6}) = \frac{1}{12}(z_{1}^{6} + 2z_{6} + 2z_{3}^{2} + 4z_{2}^{3} + 3z_{1}^{2}z_{2}^{2}). Einsetzen von f = 2 für alle z_{i} liefert:

ℨ(D_{6}|2) = \frac{1}{12}(2^{6} + 2 · 2 + 2 · 2^{2} + 4 · 2^{3} + 3 · 2^{2} · 2^{2}) = 13

Deshalb gibt es genau 13 wesentlich verschiedene Eckenfärbungen des regelmäßigen Sechsecks mit zwei gegebenen Farben. Insbesondere: Es gibt genau 13 wesentlich verschiedene Perlenketten mit insgesamt sechs Perlen und zwei Perlensorten (weiß, schwarz).

Das Beispiel ist klein, und man kann die 13 Ketten leicht finden.

Jetzt soll, ebenso systematisch, die Anzahl der Perlenketten mit drei schwarzen und drei weißen Perlen bestimmt werden. (Es wird auch klar werden, wie solche Berechnungen allgemein durchzuführen sind, für beliebige Permutationsgruppen G.) Es muss die Formel aus der Bemerkung von Seite 45 betrachtet werden:

⊛ b(G̃) = \frac{1}{|G̃|} ∑_{g̃∈G̃} |Fix(g̃)|

aber mit G̃ eingeschränkt auf die jetzt noch zulässigen Färbungen (nämlich dreimal schwarz, dreimal weiß). Die Bestimmung von Fix(g̃) gelingt wieder wie auf Seite 45: jeder Zyklus ist einheitlich einzufärben. Beispiel: Sei

g = σ = (0)(3)(15)(24).

Für jede der Mengen {0}, {3}, {1, 5}, {2, 4} muss man sich für schwarz oder weiß entscheiden. Hierfür gibt es (bei insgesamt drei schwarzen Perlen) genau vier Möglichkeiten, nämlich

{0} und {1, 5} schwarz, {0} und {2, 4} schwarz, {3} und {1, 5} schwarz, {3} und {2, 4} schwarz.

Also liefert g = σ den Beitrag 4 zur Summe in ⊛.

Dieses – und alles weitere – kann mit dem Zyklenzeiger ℨ(G) ganz formelmäßig und ganz ohne Nachdenken berechnet werden (aber für den Fortgang der Theorie ist noch ein wenig Denkarbeit erforderlich):

Definition: Das einem Polynom p(z_{1}, …, z_{n}) zugeordnete Polynom entsteht, indem jedes z_{i} durch x_{1}^{i} + x_{2}^{i} ersetzt wird.

Beispiel: Immer noch g = σ = (0)(3)(15)(24): Typ t(σ) = z_{1}^{2}z_{2}^{2}, zugeordnetes Polynom (x_{1}^{1} + x_{2}^{1})^{2}(x_{1}^{2} + x_{2}^{2})^{2}. Jede Klammer korrespondiert mit einer der ”Zyklenmengen“:

\begin{matrix}\{0\} & \{3\} & \{1, 5\} & \{2, 4\} \\ ↓ & ↓ & ↓ & ↓ \\ (x_{1} + x_{2}) & (x_{1} + x_{2}) & (x_{1}^{2} + x_{2}^{2}) & (x_{1}^{2} + x_{2}^{2}) \end{matrix}

Jede Entscheidung ”schwarz oder weiß“ für eine der Zyklenmengen entspricht einer Entscheidung ”x_{1} oder x_{2}“ in der zugehörigen Klammer. Dreimal schwarz, dreimal weiß bedeutet: Ausmultiplizieren, Koeffizient von x_{1}^{3}x_{2}^{3} ist dann |Fix(σ)|. Führt man dies mit dem gesamten Zyklenzeiger ℨ(D_{6}) durch, ergibt sich die erzeugende Funktion (der Färbungen mit zwei Farben) von D_{6}:

ℨ(D_{6}|x_{1}^{i} + x_{2}^{i}) = \frac{1}{12}((x_{1} + x_{2})^{6} + 2(x_{1}^{6} + x_{2}^{6}) + 2(x_{1}^{3} + x_{2}^{3})^{2}
+ 4(x_{1}^{2} + x_{2}^{2})^{3} + 3(x_{1} + x_{2})^{2}(x_{1}^{2} + x_{2}^{2})^{2})
= 1 · x_{1}^{6} + 1 · x_{1}^{5}x_{2} + 3 · x_{1}^{4}x_{2}^{2} + 3 · x_{1}^{3}x_{2}^{3}
+ 3 · x_{1}^{2}x_{2}^{4} + 1 · x_{1}x_{2}^{5} + 1 · x_{2}^{6}

Die Koeffizienten sind (wegen ⊛) tatsächlich die gesuchten Anzahlen. Es ergibt sich folgende Tabelle:

Farbverteilung  Anzahl der Färbungen
schwarz weiß (Koeffizienten der erzeugenden Funktion)
6  0  1
5  1  1
4  2  3
3  3  3
2  4  3
1  5  1
0  6  1
Summe:  13

Obige Argumentation klappt allgemein. Deshalb gilt folgender Satz (wurde 1937 von Pólya gefunden, der sich dafür interessierte, wieviele chemische Verbindungen mit einem vorgegebenen Bauplan es geben kann):

1.8.4 Satz von Pólya

Gegeben sei eine Permutationsgruppe G auf A, |A| = n. Aus dem Zyklenzeiger ℨ(G) entstehe das Polynom ℨ(G | x_{1}^{i}+⋯+x_{f}^{i}), indem für jedes z_{i} der Ausdruck x_{1}^{i} +⋯+x_{f}^{i} substituiert wird (i = 1, …, n). Dieses Polynom ist dann die erzeugende Funktion aller Färbungen mit f Farben: Hierin gibt der Koeffizient von x_{1}^{n(1)} ·. . .·x_{f}^{n(f)} die Anzahl der bezüglich G wesentlich verschiedenen Färbungen von A mit einer f-Farbenmenge F = {F_{1}, …, F_{f}} an, in denen die Farbe F_{i} genau n(i) mal vorkommt.

Anmerkungen:

• Man kann in ℨ(G | x_{1}^{i} + ⋯ + x_{f}^{i}) immer x_{f} = 1 setzen, ohne Information zu verlieren. Im Fall der Diedergruppe D_{6} mit f = 2 Farben ergibt sich (mit x_{1} = x, x_{2} = 1): ℨ(D_{6} | x_{1}^{i} + x_{2}^{i}) = x^{6} + x^{5} + 3x^{4} + 3x^{3} + 3x^{2} + x + 1

• Der Satz von Pólya liefert noch einmal die Anzahl aller Färbungen, indem x_{i} = 1 gesetzt wird für alle i. Es ergibt sich wieder ℨ(G | f) – vergleiche Seite 46.

2 Algebraische Strukturen

Dieses Kapitel beginnt mit einer Auflistung der wichtigsten und gebräuchlichsten algebraischen Strukturen. Dann werden die wichtigsten algebraischen Begriffe, Sprech- und Denkweisen vorgestellt. Der Bogen wird sich von einer einheitlichen Sprache, in der algebraische Strukturen definiert werden können (Grundmenge, Operationen, Ähnlichkeitstyp) über fortgeschrittene Begriffsbildungen (wie Unteralgebren, Homomorphismen, direkten Produkten, Kongruenzrelationen oder gleichungsdefinierten Klassen) bis zu Gleichungstheorien und Gleichungslogik spannen. Zum Abschluss des Kapitels werden dann Verbände und boolesche Algebren betrachtet, womit ein Übergang zum darauf folgenden (und letzten) Kapitel über Logik möglich ist.

2.1 Algebraische Strukturen: Beispiele

In diesem Abschnitt wird eine ganze Reihe der üblichsten algebraischen Strukturtypen mitsamt wichtigen Beispielen vorgestellt.

2.1.1 Operationen

Definition: Sei A eine Menge und n ∈ ℕ_{0}. Dann heißt jede Abbildung

f: A^{n} ⟶ A

eine n-stellige Operation auf A. Solche Abbildungen (Operationen) werden oft in der Form f(x_{1}, …, x_{n}) geschrieben, wobei die Variablen x_{1}, …, x_{n} jeden Wert aus A annehmen können.

Beispiele:

• Die übliche Addition ”+“ auf ℕ ist eine 2-stellige Operation auf ℕ. Anstelle von ”+(x_{1}, x_{2})“ wird, wie üblich, ”x_{1} + x_{2}“ geschrieben (Infix-Schreibweise).

• Definiert man f(x_{1}, x_{2}, x_{3}) := x_{1} + x_{2} + x_{3}, so erhält man eine 3-stellige Operation auf ℕ.

• Eine 1-stellige Operation auf ℕ ist, zum Beispiel, gegeben durch g(x) := x + 1.

• Was ist eine 0-stellige Operation auf einer Menge A? Dabei handelt es sich um Abbildungen A^{0} ⟶ A, wobei A^{0} = {()} gilt: Die Menge entält nur das ”leere Tupel“ (). Solche Operationen hängen nicht von A ab, das Resultat ist ein einziges Element c ∈ A, nämlich f(()) = c. Daher werden 0-stellige Operationen auch Konstanten (in A) genannt. Zum Beispiel 1 ∈ ℕ ist eine Konstante in ℕ.

• 2-stellige Operationen auf kleineren Mengen können oft durch Verknüpfungstafeln dargestellt werden. Beim folgenden Beispiel handelt es sich um die ”Addition modulo 4“ auf der Menge ℤ_{4} = {0, 1, 2, 3}:

+ 0 1 2 3
0 0 1 2 3
1 1 2 3 0
2 2 3 0 1
3 3 0 1 2

2.1.2 Halbgruppen

Definition: Eine Halbgruppe (engl.: semigroup) ist ein Paar (S; ·), bestehend aud aus einer Menge S und einer 2-stelligen Operation · auf S, so dass in S folgende Gleichung erfüllt ist:

(ass) x · (y · z) = (x · y) · z  (Assoziativität)

Bemerkung: Spricht man von ”Gleichung auf A“, so meint man, dass die Gleichung für alle Elemente von A gilt. Im Fall von Gleichung (ass) bedeutet das:

∀x, y, z ∈ A: x · (y · z) = (x · y) · z

Typische Beispiele (Halbgruppe): Abbildungen auf einer Menge: Sei A eine Menge, und sei S die Menge aller Abbildungen f: A ⟶ A. Für je zwei Abbildungen f, g ∈ S werde die Verkettung f ∘ g (”f nach g“) definiert durch

(f ∘ g)(x) := f(g(x)) für alle x ∈ A

Es gilt: Verkettung von Abbildungen ist assoziativ, das heißt (S; ∘) ist eine Halbgruppe.

Beweis: Es ist für alle f, g, h ∈ S zu zeigen, dass

(f ∘ (g ∘ h))(x) = ((f ∘ g) ∘ h)(x) für alle x ∈ A

gilt. Doch dies ist einfach:

(f ∘ (g ∘ h))(x) = f((g ∘ h)(x)) = f(g(h(x))) = (f ∘ g)(h(x)) = ((f ∘ g) ∘ h)(x)

Beispiel: Wörter über einem Alphabet: Sei A eine Menge (die jetzt ein Alphabet genannt wird). Jedes Tupel (a_{1}, a_{2}, …, a_{n}) wird jetzt kürzer als a_{1}a_{2} … a_{n} geschrieben und ein Wort von Länge n über A genannt. Sei A^{∗} die Menge aller Wörter über A (inklusive dem ”leeren Wort“ λ von Länge 0):

A^{∗} := ⋃_{n=0}^{∞} A^{n} (= A^{0} ∪ A^{1} ∪ A^{2} ∪ …)

Die Konkatenation (oder Juxtaposition) von zwei Wörtern a_{1}a_{2} … a_{n} und b_{1}b_{2} … b_{m} ist definiert als

(a_{1}a_{2} … a_{n}) · (b_{1}b_{2} … b_{m}) := a_{1}a_{2} … a_{n}b_{1}b_{2} … b_{m}

offensichtlich gilt: Konkatenation ist assoziativ, das heißt (A^{∗}; ·) ist eine Halbgruppe.

Weitere Beispiele (Halbgruppe)

• (ℕ; +), (ℤ; +), (ℚ; +), (ℝ; +), (ℂ; +) und (ℕ; ·), (ℤ; ·), (ℚ; ·), (ℝ; ·), (ℂ; ·) sind Halbgruppen.

• Matrixmultiplikation ist assoziativ: Bezeichne M(ℝ, n) die Menge aller n × n-Matrizen über ℝ, dann ist (M(ℝ, n); ·) eine Halbgruppe.

• Sei M_{0}(ℝ, n) = {A ∈ M(ℝ, n) | det A = 0}. Dann ist (M_{0}(ℝ, n); ·) eine Halbgruppe.

• Übung: Zeige, dass die Verknüpfungstafel eine Halbgruppenoperation angibt. (Hinweis: Assoziativität muss mit einem geeigneten Argument nachgewiesen werden, nicht indem alle 4^{3} = 64 Möglichkeiten durchprobiert werden.)

2.1.3 Monoide

Definition, Version A: Eine Halbgruppe (M; ·) wird ein Monoid genannt, falls ein neutrales Element existiert, das heißt falls

∃1 ∈ M ∀x ∈ M: x · 1 = x = 1 · x

Bei dieser Regel handelt es sich um keine Gleichung (das heißt um keine zwei Gleichungen), da sie einen Existenzquantor enthält. Doch sie kann in eine Gleichung umgewandelt werden, indem das neutrale Element zu einer nullstelligen Operation gemacht wird:

Definition, Version B: Ein Tripel (M; ·, 1) wird ein Monoid genannt, falls (M; ·) eine Halbgruppe ist und 1 eine nullstellige Operation, die die folgenden Eigenschaften erfüllt:

(neut) x · 1 = x = 1 · x  (neutrales Element)

Typische Beispiele (Monoid): Die Beispiele in ”Typische Beispiele (Halbgruppe)“ sind Monoide:

• Sei wieder S die Menge aller Abbildungen A ⟶ A, und bezeichne id_{A} die identische Abbildung auf A: id_{A}(x) = x für alle x ∈ A.

Dann ist (S; ∘, id_{A}) ein Monoid.

• Sei A^{∗} die Menge aller Wörter über einem Alphabet A. Mit Konkatenation · und dem leeren Wort λ gilt: (A^{∗}; ·, λ) ist ein Monoid.

Im weiteren Lauf dieses Kapitels werden ”Version B“-Typ Definitionen bevorzugt. Im folgenden Abschnitt wird dann, als allgemeiner Begriff, eine (allgemeine) Algebra definiert, als Menge mit Operationen und weiteren Ordungsmerkmalen auf Operationen.

Doch zunächst weitere wichtige Beispiele algebraischer Strukturen. Hierbei wird der Typ einer algebraischen Struktur verwendet, das heißt die Folge der Stelligkeiten der Operationen:

2.1.4 Gruppen

Definition: Eine Algebra (G; ·,^{−1}, 1) von Typ (2, 1, 0) (das heißt mit 2-stel-liger Operation ·, mit 1-stelliger Operation ^{−1}, 0-stelliger Operation 1) heißt Gruppe, falls (G; ·, 1) ein Monoid ist und außerdem folgende Gleichungen gelten:

(inv) x · x^{−1} = 1 = x^{−1} · x  (inverse Elemente)

Typische Beispiele (Gruppe)

• Permutationen: Sei A eine Menge und S_{A} die Menge aller Permutationen auf A (siehe Kapitel 1). Dann ist (S_{A}; ∘,^{−1}, id_{A}) eine Gruppe, genannt die symmetrische Gruppe auf A.

• Symmetrie: Im vorigen Abschnitt wurden Symmetrien geometrischer Figuren als Permutationen gewisser Punktmengen interpretiert. Als Beispiele wurden die Diedergruppen (D_{n}; ∘,^{−1}, id) betrachtet (Symmetriegruppen regelmäßiger n-Ecke).

Weitere Beispiele (Gruppen)

• (ℤ; +, −, 0) ist eine Gruppe mit den üblichen Operationen auf ℤ (insbesondere der 1-stelligen Operation x ↦ −x).

• Für n ∈ ℕ sei ℤ_{n} := {0, 1, …, n − 1}. Dann ist (ℤ_{n}; +, −, 0) eine Gruppe (mit + und − modulo n).

• Sei G(ℝ, n) die Menge aller reellen n × n-Matrizen von Determinante ungleich 0, G(ℝ, n) = {A ∈ M(ℝ, n) | det(A) ≠ 0}. Dann ist (G(ℝ, n); ·,^{−1}, E_{n}) eine Gruppe, genannt die allgemeine lineare Gruppe über ℝ. (Hierbei sei · die übliche Matrizenmultiplikation, A^{−1} die inverse Matrix zu A und E_{n} die n × n-Einheitsmatrix.)

Eine zweistellige Operation x·y auf einer Menge A wird kommutativ genannt, falls folgende Gleichung auf A gilt:

(kom) x · y = y · x  (Kommutativität)

Es ist klar, was man unter einer kommutativen Halbgruppe, einem kommutativen Monoid, einer kommutativen Gruppe versteht. Kommutative Gruppen werden üblicherweise abelsche Gruppen genannt.

2.1.5 Ringe

Definition: Eine Algebra (R; +, −, 0, ·) von Typ (2, 1, 0, 1) heißt ein Ring, falls (R; +, −, 0) eine abelsche Gruppe und (R; ·) eine Halbgruppe ist, so dass die Operationen + und · durch folgende Gleichungen ”verbunden“ sind:

(dist) x · (y + z) = x · y + x · z, (x + y) · z = x · z + y · z (Distributivität)

Ein kommutativer Ring ist ein Ring, in dem die Multiplikation · kommutativ ist. Ein unitärer Ring ist ein Ring mit einer zusätzlichen nullstelligen Operation 1, so dass (R, ·, 1) ein Monoid ist.

Bemerkung: Der Multiplikationspunkt · wird oft weggelassen, das heißt xy statt x · y geschrieben. Deshalb kann das erste Distributivgesetz als x(y + z) = xz + yz geschrieben werden. Die Regel ”Punktrechnung vor Strichrechnung“ versteht sich von selbst.

Typische Beispiele (Ring)

• Ring der ganzen Zahlen: (ℤ; +, −, 0, ·, 1) ist ein kommutativer unitärer Ring. Dasselbe gilt für (ℤ_{n}; +, −, 0, ·, 1) mit Z_{n} = {0, 1, …, n} und allen Operationen modulo n.

• Polynomringe: Mit ℝ[x] werde die Menge der reellen Polynome in der Variablen x bezeichnet:

ℝ[x] = {a_{n}x^{n} + … + a_{1}x + a_{0} | n ∈ ℕ_{0}, a_{n}, …, a_{1}, a_{0} ∈ ℝ}

(Achtung: Hierbei ist x keine Zahl, sondern ein Symbol. Deshalb sind auch die Polynome keine Zahlen, sondern ”formale Ausdrücke“.) Mit den üblichen Operationen ist ℝ[x] ein kommutativer unitärer Ring.

• Matrixringe: Die Menge M(ℝ, n) aller reellen n × n-Matrizen bilden mit der üblichen Matrixaddition und -multiplikation einen unitären Ring, der für n ≥ 2 nicht kommutativ ist.

2.1.6 Körper

Ein Körper ist ein unitärer Ring (K; +, −, 0, ·, 1) mit zusätzlicher einstelliger Operation ^{−1} auf K \{0}, so dass (K \{0}; ·,^{−1}, 1) eine Gruppe ist. Ist die Multiplikationsoperation · kommutativ, so spricht man von einem kommutativen Körper.

Beispiele (Körper): Mit den üblichen Operationen sind die Mengen ℚ, ℝ, ℂ kommutative Körper. Beispielsweise ist ℤ kein Körper, da es keine multiplikativen Inversen gibt (außer für x = 1 und x = −1).

Einige Tatsachen über Körper (ohne Beweise):

• ℤ_{n} ist genau dann ein Körper, wenn n eine Primzahl ist.

• Ein Körper K mit |K| = n Elementen existiert genau dann, wenn n eine Primzahlpotenz ist (das heißt von der Form n = p^{r} mit einer Primzahl p und r ∈ ℕ).

• Für jede Primzahlpotenz q = p^{r} gibt es genau einen Körper mit q Elementen (bis auf Isomorphie).

• Alle endlichen Körper sind kommutativ (nicht leicht zu beweisen!)

• Es ist schwierig, nicht-kommutative Körper zu finden.

2.1.7 Vektorräume

Definition: Sei K ein Körper und sei (V; +, −, 0, K) eine Algebra vom Typ (2, 1, 0, (1)_{k∈K})), mit einer einstelligen Operation x ↦ kx für jedes Körperelement k ∈ K. Dann heißt diese Algebra ein Vektorraum über K, falls (V; +, −, 0) eine abelsche Gruppe ist und für alle k, ℓ ∈ K die folgenden Gleichungen gelten:

(Vekt1) k(x + y) = kx + ky
(Vekt2) (k + ℓ)x = kx + ℓx
(Vekt3) (k(ℓx)) = (kℓ)x
(Vekt4) 1x = x

Einige Tatsachen über Vektorräume (ohne Beweise):

• Eine Basis eines Vektorraums V (über K) ist eine Teilmenge B ⊆ V, so dass jedes v ∈ V auf genau eine Art in der Form

v = k_{1}b_{1} + ⋯ + k_{r}b_{r}

darstellbar ist, mit unterschiedlichen b_{1}, …, b_{r} ∈ B und k_{1}, …, k_{r} ∈ K.

• Falls B eine Basis von V ist, dann nennt man |B| die Dimension von V. Die Dimension ist wohldefiniert: Sind B und C Basen von V, dann gilt |B| = |C|.

• Jeder Vektorraum besitzt eine Basis.

• Ist V ein Vektorraum über K von endlicher Dimension d, dann ist V isomorph zu F^{d}: V ≅ F^{d}

Typische Beispiele für Vektorräume:

• Die reelle Ebene: Sei V := \{\binom{x}{y} | x, y ∈ ℝ\}, wobei hier die Elemente von V als Spaltenvektoren geschrieben sind. Dann ist V mit der üblichen Vektoraddition v + w und Skalarmultiplikation kv ein Vektorraum über ℝ. Dieser Vektorraum ist 2-dimensional, also dim(V) = 2. Er hat B = \{\binom{1}{0} , \binom{0}{1}\} als kanonische Basis: Jedes v = \binom{x}{y} ∈ V kann in

der Form v = x \binom{1}{0} + y \binom{0}{1} geschrieben werden. Entsprechend gibt es die n-dimensionalen reellen Vektorräume ℝ^{n}.

• Polynome von Grad kleiner n: Sei P_{n} die Menge aller reellen Polynome von Grad kleiner n,

P_{n} = {a_{n−1}x^{n−1} + ⋯ + a_{1}x + a_{0} | a_{n−1}, …, a_{1}, a_{0} ∈ ℝ}

Definiert man wie üblich für alle p = a_{n−1}x^{n−1} + ⋯ + a_{1}x + a_{0} und q = b_{n−1}x^{n−1} + ⋯ + b_{1}x + b_{0}:

p + q := (a_{n−1} + b_{n−1})x^{n−1} + ⋯ + (a_{1} + b_{1})x + (a_{0} + b_{0})
rp := (ra_{n−1})x^{n−1} + ⋯ + (ra_{1})x + (ra_{0})

Dann erhält man einen Vektorraum (P_{n}; +, −, 0, ℝ) über ℝ. Die Polynome p_{0}(x) = 1, p_{1}(x) = x, p_{2}(x) = x^{2}, …, p_{n−1}(x) = x^{n−1} bilden eine Basis von P_{n}, deshalb gilt dim(P_{n}) = n. Ein Isomorphismus φ: P_{n} ⟶ ℝ^{n} wird durch folgende ”Umbenennung“ gegeben:

φ(a_{n−1}x^{n−1} + ⋯ + a_{1}x + a_{0}) := ( a_{0} ; a_{1} ; ⋮ ; a_{n−1} )

Alle bisher in diesem Abschnitt vorgestellten Algebren beziehungsweise Klassen von Algebren sind verwandt zueinander: Jeder Vektorraum ”enthält“ einen Körper (und eine Gruppe), jeder Körper ist ein (genauer: ”enthält“ einen) Ring, jeder Ring enthält eine Gruppe (und eine Halbgruppe), jede Gruppe ist ein Monoid, und - schließlich - ist jedes Monoid eine Halbgruppe. Natürlich gibt es viele weitere und auch ganz andere Klassen von Algebren. In diesem Kapitel werden später noch Beispiele vorgestellt, zum Beispiel Verbände und boolesche Algebren.

2.2 Allgemeine Algebren:

Definition und strukturelle Grundbegriffe

Natürlich darf man sich unter einer Algebra zunächst einmal ein Gebilde der Form \underline{A} = (A; F) vorstellen, wobei A eine Menge und F eine Menge endlichstelliger Operationen auf A ist. Alle Algebren sind von dieser Bauart, insbesondere alle Beispiele des vorigen Abschnitts. Will man aber Algebren miteinander in Beziehung setzen (zum Beispiel, weil sie verwandt zueinander sind), empfiehlt sich eine ”detailliertere“ Sprache:

2.2.1 Ähnlichkeitstyp, allgemeine Algebren

Definition: Unter einem (Ähnlichkeits-)Typ versteht man ein geordnetes Paar (F, σ), wobei F eine Menge ist (Menge der Operationssymbole) und σ: F ⟶ ℕ_{0} eine Abbildung, die jedem f ∈ F eine Stelligkeit σ(f) zuordnet. Man nennt f dann ein σ(f)-stelliges Operationssymbol.

Eine allgemeine Algebra (kurz: Algebra) vom Typ (F, σ) ist ein geordnetes Paar \underline{A} = (A; F), bestehend aus einer Menge A und einer Familie

F = (f\underline{A} | f ∈ F)

von Operationen auf A, wobei jedem Operationssymbol f ∈ F eine σ(f)-stellige Operation f\underline{A} auf A zugeordnet wird. Die Menge A heißt Grundmenge von \underline{A} und die Elemente von F heißen die fundamentalen Operationen von \underline{A}.

Beispiel: Als erstes Beispiel für diese Notationen und Sprechweisen wird die Gruppe (ℤ; +, −, 0) betrachtet (siehe Seite 52). Da diese Gruppe im Rahmen aller Gruppen betrachtet werden soll, wird der Typ

(F, σ) mit F = {·,^{−1}, 1}, σ(·) = 2, σ(^{−1}) = 1, σ(1) = 0

gewählt. Die zu betrachtende Gruppe ist \underline{ℤ} = (ℤ; \{+, −, 0\}). Die verwendeten fundamentalen Operationen sind

·\underline{ℤ} = +,  ^{−1}\underline{ℤ} = −,  1\underline{ℤ} = 0

wobei x + y, −x, 0 auf ℤ wie üblich definiert sind. Insbesondere gilt: Keiner hält einen davon ab, gebräuchliche, einfache Symbole für die Operationen zu verwenden, solange keine Missverständnisse drohen, also zum Beispiel ”+“ anstelle von ”·\underline{z}“. Statt (ℤ; \{+, −, 0\}) schreibt man natürlich - unter Einsparung von Klammern - meist (ℤ; +, −, 0).

Aus schon vorhandenen Algebren können auf mehrere Arten ”neue“ Algebren gewonnen werden. Eine Art ist die folgende:

2.2.2 Unteralgebren

Definition: Sei \underline{A} = (A; F) eine Algebra vom Typ (F, σ) und B ⊆ A eine Teilmenge von A, so dass für alle f ∈ F und alle n-Tupel (b_{1}, …, b_{n}) ∈ B^{n} mit n = σ(f) folgendes gilt:

f\underline{A}(b_{1}, …, b_{n}) ∈ B

Die Algebra \underline{B} = (B; (f\underline{B} | f ∈ F)) heißt dann eine Unteralgebra von \underline{A}, wobei f\underline{B} für alle f ∈ F die Einschränkung der Operation f\underline{A} auf die Menge B bedeutet. Für ”\underline{B} ist Unteralgebra von \underline{A}“ schreibt man auch \underline{B} ⩽ \underline{A}. Die Menge aller Grundmengen von Unteralgebren von \underline{A} wird mit Sub(\underline{A}) bezeichnet, Sub(\underline{A}) = \{B | \underline{B} ⩽ \underline{A}\}.

Eine Teilmenge B ⊆ A ist genau dann die Grundmenge einer Unteralgebra von \underline{A} = (A; F), wenn B unter allen fundamentalen Operationen f\underline{A} ∈ F abgeschlossen ist. Man schreibt dann oft \underline{B} = (B; F), ohne zwischen den Operationsfamilien F in \underline{A} und F in \underline{B} zu unterscheiden. Außerdem bezeichnet man sowohl f\underline{A} als auch f\underline{B} einfach mit dem Operationssymbol f.

Am Beispiel der Gruppen lässt sich deutlich machen, dass es bei den Unteralgebren auf den zugrundeliegenden Typ ankommen kann. Betrachtet man Gruppen als Algebren vom Typ (2, 1, 0) (das heißt mit diesen Stelligkeiten für die Operationen) wie auf Seite 51, dann handelt es sich bei den Unteralgebren genau um die Untergruppen. Betrachtet man Gruppen hingegen als Algebren vom Typ (2) (mit der Gruppenmultiplikation als einziger Operation), dann kann es Unteralgebren geben, die keine Untergruppen sind:

Beispiel: Die Algebra (ℤ; +) mit der üblichen Addition hat die Menge ℕ_{0} der nicht negativen ganzen Zahlen als Grundmenge einer Unteralgebra, obwohl ℕ_{0} nicht die Grundmenge einer Unteralgebra von (ℤ; +, −, 0) ist.

Für jede Algebra ist das System der (Grundmengen von) Unteralgebren gegen Durchschnittsbildung abgeschlossen:

Bemerkung: Sei \underline{A} = (A; F) eine Algebra. Dann gilt:

(a) A ∈ Sub(\underline{A})
(b) ⋂ B ∈ Sub(\underline{A}) für jede nichtleere Teilmenge B ⊆ Sub(\underline{A})

Beweis: (a) ist klar. Für den Nachweis von (b) sei B ⊆ Sub(\underline{A}), B ≠ ∅. Es ist zu zeigen, dass ⋂ B unter allen fundamentalen Operationen f von \underline{A} abgeschlossen ist. Sei n = σ(f). Aus b_{1}, …, b_{n} ∈ ⋂ B folgt b_{1}, …, b_{n} ∈ B für alle B ∈ B. Da alle B ∈ B Grundmengen von Unteralgebren sind, gilt f(b_{1}, …, b_{n}) ∈ B für alle B ∈ B Es folgt f(b_{1}, …, b_{n}) ∈ ⋂ B. □

Folgerung: Für jede Algebra \underline{A} = (A; F) und jede Teilmenge X ⊆ A ist

⟨X⟩ := ⋂\{B ∈ Sub(\underline{A}) | B ⊇ X\}

die Grundmenge einer Unteralgebra von \underline{A}, das heißt es gilt ⟨X⟩ ∈ Sub(\underline{A}). Offenbar ist ⟨X⟩ die kleinste X umfassende Grundmenge einer Unteralgebra von \underline{A} (nämlich der von X erzeugten Unteralgebra).

Beispiel: Es wird die Gruppe (ℤ_{6}; +, −, 0) betrachtet. Mit den Elementen von ℤ_{6} = {0, 1, 2, 3, 4, 5} wird modulo 6 gerechnet. Es gilt: ⟨0⟩ = {0}, ⟨1⟩ = ℤ_{6}, ⟨2⟩ = {0, 2, 4}, ⟨3⟩ = {0, 3}, ⟨2, 3⟩ = ℤ_{6}. Übrigens sind das alle Grundmengen von Unteralgebren!

Bemerkung: Sei \underline{A} = (A; F) eine Algebra. Für alle Teilmengen X, Y ⊆ A gilt:

(1) X ⊆ ⟨X⟩  Extensivität
(2) X ⊆ Y ⇒ ⟨X⟩ ⊆ ⟨Y ⟩ Monotonie
(3) ⟨⟨X⟩⟩ = ⟨X⟩  Idempotenz

Der Beweis ergibt sich unmittelbar aus der Definition des Operators ⟨ ⟩. □

Man erhält ⟨X⟩ tatsächlich durch einen Erzeugungsprozess aus X. Dazu werde definiert:

E^{0}(X) := X E(X) := X ∪ {f(a_{1}, ….a_{n}) | f ∈ F, a_{1}, …, a_{n} ∈ X} mit n = σ(f) E^{k+1}(X) := E(E^{k}(X)) für alle k ∈ ℕ_{0}

Satz: Für jede Algebra \underline{A} = (A; F) und jede Teilmenge X ⊆ A gilt:

⟨X⟩ = ⋃_{k=0}^{∞} E^{k}(X)

Beweis: ⊇: Mit Induktion über k wird ⟨X⟩ ⊇ E^{k}(X) gezeigt. k = 0: ⟨X⟩ ⊇ X = E^{0}(X) ist klar. Jetzt werde ⟨X⟩ ⊇ E^{k}(X) vorausgesetzt, um ⟨X⟩ ⊇ E^{k+1}(X) zu zeigen. Sei a ∈ E^{k+1}(X), aber a ∉ E^{k}(X). Dann gibt es a_{1}, …, a_{n} ∈ E^{k}(X) und f ∈ F mit f(a_{1}, …, f_{n}) = a. Wegen E^{k}(X) ⊆ ⟨X⟩, und da ⟨X⟩ die Grundmenge einer Unteralgebra ist, folgt a ∈ ⟨X⟩, insgesamt also E^{k+1}(X) ⊆ ⟨X⟩. Hiermit folgt ⟨X⟩ = ⋃_{k=0}^{∞} E^{k}(X).

⊆: Es muss gezeigt werden, dass ⋃_{k=0}^{∞} E^{k}(X) die Grundmenge einer Unteralgebra ist. Seien also a_{1}, …, a_{n} ∈ ⋃_{k=0}^{∞} E^{k}(X) und f ∈ F (mit σ(f) = n). Dann gibt es für jedes a_{i} ein k(i) ∈ ℕ_{0} mit a_{i} ∈ E^{k(i)}(X). Sei m := max{k(i) | i = 1, …, n}. Es gilt a_{i} ∈ E^{m}(X) für alle i = 1, …, n. Es folgt sofort

f(a_{1}, …, a_{n}) ∈ E^{m+1}(X) ⊆ ⋃_{k=0}^{∞} E^{k}(X)

das heißt die letzte Menge ist abgeschlossen unter allen Operationen f. □

Der letzte Satz und die beiden vorangegangenen Bemerkungen geben Aufschluss über das Verhalten der Mengensysteme Sub(\underline{A}). Dies wird im folgenden Einschub behandelt:

2.2.3 Hüllensysteme, Hüllenoperatoren, Verbände

Alle drei Begriffe der Überschrift spielen bezüglich Unteralgebren eine große Rolle. Zwei dieser Begriffe kamen oben schon vor, der dritte (”Verband“) noch nicht. Diese Begriffe sind aber auch in vielen anderen Zusammenhängen wichtig.

Definition: Sei A eine Menge und M eine Menge von Teilmengen von A, also M ⊆ P(A). Dann nennt man M ein Mengensystem auf A. Ein Mengensystem H ⊆ P(A) heißt Hüllensystem auf A, falls

(1) A ∈ H
(2) ⋂ B ∈ H für jede nicht leere Teilmenge B ⊆ H

Die Elemente H ∈ H werden Hüllen genannt.

Beispiele:

• Für jede Algebra \underline{A} ist Sub(\underline{A}) ein Hüllensystem auf der Grundmenge A.

• Die konvexen Teilmengen von ℝ^{n} bilden ein Hüllensystem.

• Für jede Menge A ist {A} ∪ {E ⊆ A | E endlich} ein Hüllensystem auf A.

• Für jede Menge A ist die Menge Eq(A) aller Äquivalenzrelationen auf A ein Hüllensystem auf A^{2}.

Definition: Sei A eine Menge. Eine Abbildung

C: P(A) ⟶ P(A)

wird Hüllenoperator auf A genannt, falls für alle Teilmengen X, Y ⊆ A folgendes gilt:

(1) X ⊆ C(X)  Extensitivität
(2) X ⊆ Y ⇒ C(X) ⊆ C(Y)  Monotonie
(3) C(C(X)) = C(X)  Idempotenz

Man nennt die Mengen der Form C(X) abgeschlossen und sagt, C(X) ist von X erzeugt.

Klar ist: Für jede Algebra \underline{A} ist der Operator ⟨ ⟩\underline{A} ein Hüllenoperator (siehe Seite 57). Hüllensysteme und Hüllenoperatoren sind in folgendem Sinn im wesentlichen das selbe:

Bemerkung: Sei H ein Hüllensystem auf einer Menge A. Für alle X ⊆ A sei

C_{H}(X) := ⋂{H ∈ H | H ⊇ X}.

Dann ist C_{H} ein Hüllenoperator auf A, und die abgeschlossenen Mengen von C_{H} sind gerade die Hüllen von H.

Sei umgekehrt C ein Hüllenoperator auf A. Dann ist

H_{C} := {C(X) | X ⊆ A}

ein Hüllensystem auf A, und die Hüllen von H_{C} sind gerade die abgeschlossenen Mengen von C.

Allerdings haben Unteralgebren-Hüllenoperatoren und Unteralgebren-Hüllen-systeme noch weitere Eigenschaften:

Definition: Ein Mengensystem M heißt induktiv, falls für jedes nach oben gerichtete Teilsystem G ⊆ M gilt:

⋃ G ∈ M

(Dabei ist G nach oben gerichtet, falls es für alle X, Y ∈ G immer ein Z ∈ G gibt mit X ∪ Y ⊆ Z.) Ein Hüllenoperator C auf A heißt induktiv, falls für alle Teilmengen X ⊆ A folgendes gilt:

C(X) = ⋃ {C(E) | E ⊆ X, E endlich}

Induktivität ist für Mengensysteme und für Hüllensysteme ganz unterschiedlich definiert. Handelt es sich beim Mengensystem aber um ein Hüllensystem, dann stimmen beide Definitionen überein:

Beobachtung: Ein Hüllensystem H ist genau dann induktiv, wenn der zugehörige Hüllenoperator C_{H} induktiv ist.

Beweis: ”⇒“ Sei H ein induktives Hüllensystem auf A und sei X ⊆ A. Offenbar gilt X ⊆ ⋃ {C_{H}(E) | E ⊆ X, E endlich} ⊆ C_{H}(X). Offenbar ist das Teilsystem {C_{H}(E) | E ⊆ X, E endlich} ⊆ H nach oben gerichtet, denn für je zwei endliche Mengen E_{1}, E_{2} ⊆ X gilt C_{H}(E_{1}) ∪ C_{H}(E_{2}) ⊆ C_{H}(E_{1} ∪ E_{2}). Da H als induktiv vorausgesetzt ist, folgt ⋃ {C_{H}(E) | E ⊆ X, E endlich} ∈ H und daher C_{H}(X) = ⋃ {C_{H}(E) | E ⊆ X, E endlich}. Damit ist der Hüllenoperator C_{H} als induktiv nachgewiesen.

”⇐“ Werde nun der Hüllenoperator C_{H} als induktiv vorausgesetzt. Sei das Teilsystem G ⊆ H nach oben gerichtet. Es muss ⋃ G ∈ H gezeigt werden: Für jede endliche Teilmenge E = {e_{1}, …, e_{n}} von ⋃ G gibt es G_{1}, …, G_{n} ∈ G mit e_{1} ∈ G_{1}, …, e_{n} ∈ G_{n}, das heißt mit E ⊆ G_{1}∪…∪G_{n}. Da G nach oben gerichtet ist und G_{1} ∪ … ∪ G_{n} eine endliche Vereinigung ist, gibt es eine Menge G_{E} ∈ G mit G_{1} ∪ … ∪ G_{n} ⊆ G_{E}. Also gilt E ⊆ G_{E} und C_{H}(E) ⊆ C_{H}(G_{E}) = G_{E}. Mit der Induktivität von C_{H} folgt jetzt:

C_{H} (⋃ G) = ⋃ {C_{H}(E) | E ⊆ X, E endlich}
⊆ ⋃ {G_{E} | E ⊆ ⋃ G, E endlich}
⊆ ⋃ G

Wegen der Extensivität von C_{H} folgt C_{H}(⋃ G) = ⋃ G, was gleichbedeutend ist mit ⋃ G ∈ H. □

Satz: (a) Für jede Algebra \underline{A} = (A, F) ist Sub(\underline{A}) ein induktives Hüllensystem, und ⟨ ⟩\underline{A} ist ein induktiver Hüllenoperator.

(b) Umgekehrt gibt es zu jedem induktiven Hüllensystem H auf A eine Algebra \underline{A} = (A, F) mit H = Sub(\underline{A}) und C_{H} = ⟨ ⟩\underline{A}.

Beweis: (a) Sei G ⊆ Sub(\underline{A}) nach oben gerichtet. Es ist ⋃ G ∈ Sub(\underline{A}) nachzuweisen. Sei f ∈ F (n-stellig) und b_{1}, …, b_{n} ∈ ⋃ G. Dann gibt es G_{1}, … G_{n} ∈ G mit b_{1} ∈ G_{1}, …, b_{n} ∈ G_{n}. Da G nach oben gerichtet ist, gibt es ein G ∈ G mit G_{1} ∪ ⋯ ∪ G_{n} ⊆ G, also mit b_{1}, … b_{n} ∈ G. Wegen G ∈ Sub(\underline{A}) folgt f(b_{1}, …, b_{n}) ∈ G. Damit ist ⋃ G ∈ Sub(\underline{A}) gezeigt. Die Induktivität von ⟨ ⟩\underline{A} folgt aus der von Sub(\underline{A}).

(b) Es wird eine Algebra \underline{A} mit C_{H} = ⟨ ⟩\underline{A} definiert. (H = Sub(\underline{A}) ist dann automatisch erfüllt): Für jede endliche Teilmenge E = {e_{1}, … e_{n}} von A und jedes b ∈ C_{H}(E) wird eine n-stellige Operation f_{E,b} auf A definiert:

f_{E,b}(x_{1}, …, x_{n}) := \{ \begin{matrix}b & falls \{x_{1}, …, x_{n}\} = E \\ x_{1} & sonst \end{matrix}

Die Algebra mit diesen Operationen werde \underline{A} genannt. Zu zeigen ist C_{H}(X) = ⟨X⟩\underline{A} für alle X ⊆ A. Sei b ∈ C_{H}(X). Wegen Induktivität von C_{H} folgt die Existenz einer endlichen Menge E = {e_{1}, …, e_{n}} ⊆ X mit b ∈ C_{H}(E). Für die Operation f_{E,b} gilt dann f_{E,b}(e_{1}, …, e_{n}) = b. Es folgt b ∈ ⟨e_{1}, …, e_{n}⟩\underline{A} ⊆ ⟨X⟩\underline{A}, womit C_{H}(X) ⊆ ⟨X⟩\underline{A} gezeigt ist. Für die umgekehrte Inklusion ⟨X⟩\underline{A} ⊆ C_{H}(X) genügt der Nachweis, dass C_{H}(X) eine Unteralgebra von \underline{A} ist. Sei also b_{1}, …, b_{n} ∈ C_{H}(X), und sei f_{E,b} eine der oben definierten Operationen, also mit endlichem E und b ∈ C_{H}(E). Es gibt zwei Fälle: 1) Im Fall {b_{1}, ….b_{n}} = E gilt f_{E,b}(b_{1}, …, b_{n}) = b mit b ∈ C_{H}(b_{1}, …, b_{n}) ⊆ C_{H}(C_{H}(X)) = C_{H}(X). 2) Die einzige andere Möglichkeit ist f_{E,b}(b_{1}, …, b_{n}) = b_{1} (im Fall {b_{1}, …, b_{n}} ≠ E). Daher gilt in beiden Fällen f_{E,b}(b_{1}, …, b_{n}) ∈ C_{H}(X) □

Damit ist vollständig geklärt, wie Unteralgebren-Hüllensysteme und Unteralgebren-Hüllenoperatoren aussehen. Jetzt wird noch untersucht, wie die Unteralgebren einer Algebra abstrakt angeordnet sein können. Dies wird in der Sprache der Verbände formuliert. Es handelt sich dabei um algebraische Strukturen, die aber als geordnete Mengen aufgefasst werden können.

Definition: Ein Verband ist eine Algebra (L; ∨, ∧) vom Typ (2, 2), mit den Operationen ∨ (”Verbindung“) und ∧ (”Schnitt“), so dass folgende Gleichungen erfüllt sind:

(komm) x ∨ y = y ∨ x,  x ∧ y = y ∧ x  Kommutativität
(ass)  x ∨ (y ∨ z) = (x ∨ y) ∨ z
x ∧ (y ∧ z) = (x ∧ y) ∧ z  Assoziativität
(abs)  x ∨ (x ∧ y) = x,  x ∧ (x ∨ y) = x Absorption

Man beachte, dass die duale Form jeder dieser Gleichungen (die durch Vertauschen von ∨ und ∧ entsteht) auch zu diesen Gleichungen gehört. Deshalb gilt:

Beobachtung: Leitet man aus diesen Gleichungen eine Aussage ab, dann gilt automatisch auch die dazu duale Aussage.

Zur Illustration eine einfach Anwendung:

Behauptung: In jedem Verband gelten die folgenden Gleichungen:

(idem) x ∨ x = x,  x ∧ x = x Idempotenz

Beweis: Aufgrund obiger Beobachtung genügt es, die erste dieser Gleichungen zu zeigen. Dies gelingt sehr leicht:

x ∨ x =^{(1)} x ∨ (x ∧ (x ∨ y)) =^{(2)} x

wobei für (1) die zweite und für (2) die erste (abs)-Gleichuung verwendet werden kann. □

Beispiel: Der Verband (L; ∨, ∧) wird durch Verknüpfungstafeln dargestellt. Die Gültigkeit der Kommutativgesetze ist offensichtlich (ebenso der Idempotenz). Aber Assoziativität und Absorption sind nicht so offensichtlich:

\begin{matrix}∨ & a & b & c & d & e \\ a & a & b & c & d & e \\ b & b & b & d & d & e \\ c & c & d & c & d & e \\ d & d & d & d & d & e \\ e & e & e & e & e & e \end{matrix}  \begin{matrix}∧ & a & b & c & d & e \\ a & a & a & a & a & a \\ b & a & b & a & b & b \\ c & a & a & c & c & c \\ d & a & b & c & d & d \\ e & a & b & c & d & e \end{matrix}

Man versteht Verbände viel besser, wenn man sie als geordnete Mengen auffassen kann:

Beobachtung: Sei (L; ∨, ∧) ein Verband. Für alle x, y ∈ L sei

x ≤ y :⇔ x ∧ y = x

Dann ist (L; ≤) eine geordnete Menge, genannt eine verbandsgeordnete Menge.

Beweis: Für die Relation ≤ muss Reflexivität, Antisymmetrie und Transitivität gezeigt werden. Reflexivität: wegen (idem) gilt x ∧ x = x für alle x ∈ L, also x ≤ x. Antisymmetrie: Gelte x ≤ y und y ≤ x. Das bedeutet x ∧ y = x und y ∧ x = y. Aber (komm) liefert x ∧ y = y, also x = y. Transitivität: Gelte x ≤ y und y ≤ z. Das bedeutet x ∧ y = x und y ∧ z = y. Es folgt

x ∧ z = (x ∧ y) ∧ z =^{(ass)} x ∧ (y ∧ z) = x ∧ y = x

also x ≤ z. □

Übrigens: Man hätte oben auch

x ≤ y :⇔ x ∨ y = y

definieren können. Wegen x ∧ y = x ⇔ x ∨ y = y hätte sich nichts geändert!

Beispiel: (von Seite 61 fortgesetzt): Alle Informationen über diesen Verband ist in folgendem Diagramm der zugehörigen geordneten Menge (L, ≤) enthalten (viel übersichtlicher als in den Verknüpfungstafeln!).

[figure: a; d = b ∨ c; e; b; c; (L, ≤)]

Abbildung 31: Liniendiagramm des Verbandes (L, ≤)

Natürlich lassen sich die Verbandsoperationen ∨ und ∧ auch umgekehrt aus der Ordnungsrelation ≤ zurückerhalten. Dazu einige Begriffe:

Definition: Sei (A, ≤) eine geordnete Menge, und seien x, y ∈ A. Ein Element b ∈ A heißt eine obere Schranke von x und y, falls b ≥ x und b ≥ y gilt.

Sei B die Menge aller oberen Schranken von x und y. Falls es ein kleinstes Element von B gibt, das heißt ein Element b_{0} ∈ B mit b_{0} ≤ b für alle b ∈ B, dann heißt b_{0} das Supremum (oder die kleinste obere Schranke oder – einfacher – die Verbindung) von x und y, geschrieben als b_{0} = sup(x, y).

Die dualen Begriffe (mit ”≤“ und ”≥“ in vertauschten Rollen) sind: untere Schranke von x und y, die Menge aller unteren Schranken von x und y, größtes Element c_{0} von C (genannt Infimum oder größte untere Schranke oder Schnitt) von x und y, geschrieben als c_{0} = inf(x, y).

Beispiele

• In folgender geordneten Menge (A, ≤) handelt es sich bei den oberen Schranken von d und e um die Elemente von B = {a, b, c}. Diese Menge hat zwei minimale Elemente (nämlich b und c), aber kein kleinstes Element. Also gibt es kein Supremum von d und e. Übrigens existiert auch kein Infimum von d und e.

[figure: d; b; a; e; c; (A, ≤)]

Abbildung 32: Liniendiagramm des Verbandes (A, ≤)

• Im Beispiel von Seite 61 existieren sup(x, y) und inf(x, y) für alle x, y ∈ L, zum Beispiel: sup(b, c) = d, inf(b, c) = a, inf(e, b) = b.

Satz: Sei (L; ∨; ∧) ein Verband. Dann existieren in der zugehörigen verbandsgeordneten Menge (L, ≤) alle Suprema sup(x, y) und alle Infima inf(x, y), und es gilt: sup(x, y) = x ∨ y, inf(x, y) = x ∧ y.

Kurz gesagt: Verbände ”sind“ nichts anderes als geordnete Mengen, in denen alle Suprema und Infima (von je zwei Elementen) existieren.

Beweisplan für obigen Satz (Details seien dem Leser überlassen): Wegen Dualität reicht es, den Sup-Teil zu beweisen. Für alle x, y ∈ L muss gezeigt werden:

1. x ≤ x ∨ y (und – dazu symmetrisch – y ≤ x ∨ y)

2. aus x ≤ z und y ≤ z folgt x ∨ y ≤ z

Für 1. muss x∨(x∨y) = x∨y gezeigt werden. Für 2. muss folgende Implikation nachgewiesen werden: x ∨ z = z, y ∨ z = z ⟹ (x ∨ y) ∨ z = z

Beispiele:

• Mengen: Für jede Menge A ist die geordnete Menge (P(A), ⊆), die Potenzmenge von A mit Mengeninklusion ⊆, ist verbandsgeordnet. Der zugehörige Verband ist (P(A), ∪, ∩).

• Teiler: Mit x | y (”x teilt y“) erhält man eine verbandsgeordnete Menge (ℕ, |). Aufgabe: Was sind die Suprema und die Infima in (ℕ, |)?

• Unteralgebren (bzw. deren Grundmengen): Sei \underline{A} = (A; F) eine Algebra, dann sei (Sub(\underline{A}), ⊆) die geordnete Menge aller Unteralgebren von \underline{A}. Diese ist verbandsgeordnet, für Unteralgebren B, C von \underline{A} gilt: inf(B, C) = B ∩ C, sup(B, C) = ⟨B ∪ C⟩, die von B ∪ C erzeugte Unteralgebra.

Mit dem letzten Beispiel ist geklärt, dass die Unteralgebren einer Algebra einen Verband bilden, aber noch nicht, welche Verbände (abstrakt) als Unteralgebren-Verbände auftreten. Dies wird im Rest dieses Einschubs behandelt (aber ohne alle Beweise).

Definition: Sei (A, ≤) eine geordnete Menge und X ⊆ A eine Teilmenge. Falls eine kleinste obere Schranke sup(X) von X existiert, wird diese auch mit ⋁ X bezeichnet, Supremum von X. Entsprechend wird, falls existent, eine größte untere Schranke inf(X) von X mit ⋀ X bezeichnet, Infimum von X.

Eine verbandsgeordnete Menge (L, ≤) (beziehungsweise der zugehörige Verband (L; ∨; ∧)) heißt vollständiger Verband, falls für jede Teilmenge X ⊆ L das Supremum ⋁ X und das Infimum ⋀ X existiert.

Ist (L, ≤) ein vollständiger Verband, dann heißt ein Element a ∈ L kompakt, falls es zu jeder Menge B ⊆ L mit a ≤ ⋁ B eine endliche Teilmenge B_{0} ⊆ B gibt mit a ≤ ⋁ B_{0}.

Ein algebraischer Verband ist ein vollständiger Verband, in dem jedes Element ein Supremum kompakter Elemente ist.

Beispiele:

• Die geordnete Menge (ℝ, ≤), mit der üblichen Ordnung, ist zwar verbandsgeordnet, aber kein vollständiger Verband: Das Supremum ⋁ X existiert genau dann, wenn X nach oben beschränkt ist. Zum Beispiel existiert das Supremum ⋁ ℝ nicht. In (ℝ, ≤) gibt es keine kompakten Elemente: Sei a ∈ ℝ und ℝ_{<a} := {x ∈ ℝ|x < a}. Dann gilt ⋁ ℝ_{<a} = a, aber für jede endliche Teilmenge E ⊆ ℝ_{<a} gilt ⋁ E = max(E) < a.

• Fügt man zu (ℝ, ≤) ein zusätzliches kleinstes Element −∞ und ein zusätzliches größtes Element +∞ hinzu, erhält man einen vollständigen Verband (ℝ∪{−∞, +∞}, ≤), der aber wiederum keine kompakten Elemente enthält und nicht algebraisch ist.

• Sei H ein Hüllensystem auf A. Dann ist (H, ⊆) ein vollständiger Verband. Für jede Teilmenge X ⊆ H ist ⋀ X := ⋂ X das Infimum von X und ⋁ X := ⋂{H ∈ H | H ⊇ ⋃ X } das Supremum von X (vergleiche die Bemerkung auf Seite 58).

Damit ist klar, dass es sich bei den Unteralgebrenverbänden (Sub(A), ⊆) um vollständige Verbände handelt. Aber außerdem ist schon bekannt, dass Sub(A) für jede Algebra A sogar ein induktives Hüllensystem ist. Dies wirkt sich auf die Verbände (Sub(A), ⊆) wie folgt aus (ohne Beweis):

Bemerkung: Für jede Algebra A ist (Sub(A), ⊆) ein algebraischer Verband. Aber man weiß sogar viel mehr. Der folgende Satz gibt eine vollständige Charakterisierung von Unteralgebrenverbänden (ebenfalls ohne Beweis):

Satz: Ein vollständiger Verband L ist genau dann isomorph zum Unteralgebrenverband einer Algebra, wenn L algebraisch ist.

Zwei algebraische Strukturen werden isomorph genannt, wenn sie ”bis auf eine Umbenennung“ der Elemente der Grundmengen mittels einer bijektiven Abbildung identisch sind. Später in diesem Abschnitt wird das Konzept der ”Isomorphie“ von Algebren systematisch betrachtet!

Es folgt eine zweite Art, nach Unteralgebren, wie man aus gegebenen Algebren erhält.

2.2.4 Das direkte Produkt

Definition: Seien \underline{A} = (A; F\underline{A}) und \underline{B} = (B; F\underline{B}) Algebren des selben Typs (F, σ). Das direkte Produkt \underline{A} × \underline{B} = (A × B; F_{\underline{A}×\underline{B}}) hat die Grundmenge A × B und ist vom selben Typ: für jedes Operationssymbol f ∈ F mit σ(f) = n und für Elemente (a_{1}, b_{1}), …, (a_{n}, b_{n}) ∈ A × B wird definiert:

f_{\underline{A}×\underline{B}}((a_{1}, b_{1}), …, (a_{n}, b_{n})) := (f\underline{A}(a_{1}, …, a_{n}), f\underline{B}(b_{1}, …, b_{n}))

das heißt die Operationen übertragen sich komponentenweise von \underline{A} und \underline{B} auf \underline{A} × \underline{B}. Übrigens werden ganz analog direkte Produkte \underline{A}_{1} × … × \underline{A}_{k} von k Algebren \underline{A}_{1}, …, \underline{A}_{k} oder sogar direkte Produkte ∏_{i∈I} \underline{A}_{i} von – eventuell – unendlich vielen Algebren \underline{A}_{i}, i ∈ I, gebildet.

Beispiele

• Die Halbgruppen \underline{S} = (S; ·) und \underline{T} = (T; ·) seien durch ihre Verknüpfungstafeln gegeben, ebenso das direkte Produkt \underline{S} ×\underline{T} (das ebenfalls eine Halbgruppe ist):

\begin{matrix}· & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{matrix}^{\underline{S} = (S; ·)}  \begin{matrix}· & a & b & c \\ a & a & b & c \\ b & b & c & a \\ c & c & a & b \end{matrix}^{\underline{T} = (T; ·)}  \begin{matrix}· & 0a & 0b & 0c & 1a & 1b & 1c \\ 0a & 0a & 0b & 0c & 0a & 0b & 0c \\ 0b & 0b & 0c & 0a & 0b & 0c & 0a \\ 0c & 0c & 0a & 0b & 0c & 0a & 0b \\ 0a & 0a & 0b & 0c & 1a & 1b & 1c \\ 0b & 0b & 0c & 0a & 1b & 1c & 1a \\ 0c & 0c & 0a & 0b & 1c & 1a & 1b \end{matrix} \underline{S} × \underline{T}_{(Hierbei steht ”xy“ für ”(x, y)“)}

• Seien die Verbände \underline{L}_{1} und \underline{L}_{2} durch ihre Liniendiagramme gegeben. Das direkte Produkt \underline{L}_{1} × \underline{L}_{2} hat dann folgendes Liniendiagramm:

[figure: ^{\underline{L}^{1}}; ^{\underline{L}^{2}}; \underline{L}_{1} × \underline{L}_{2}]

Abbildung 33: Direktes Produkt von Verbänden.

Aufgabe: Schreibe für \underline{L}_{1}, \underline{L}_{2}, \underline{L}_{1} × \underline{L}_{2} die Schnittoperationen ∧ und die Verbindungsoperationen ∨ (als Verknüpfungstafeln).

Als nächstes Konzept zum Erhalt ”neuer“ Algebren aus ”alten“ folgen die Begriffe Kongruenzrelation und Faktoralgebra:

2.2.5 Kongruenzrelation

Definition: Sei \underline{A} = (A; F\underline{A}) eine Algebra vom Typ (F, σ) und sei Θ eine Äquivalenzrelation auf A. Man nennt Θ eine Kongruenzrelation auf A, falls für alle Operationssymbole f ∈ F (mit σ(f) = n) folgendes gilt für alle a_{1}, …, a_{n}, b_{1}, …, b_{n} ∈ A:

(Vert) a_{1}Θb_{1}, …, a_{n}Θb_{n} ⟹ f\underline{A}(a_{1}, …, a_{n})Θf\underline{A}(b_{1}, …, b_{n})

Man nennt unter diesen Umständen die Relation Θ mit der Operation f\underline{A} verträglich. Die Kongruenzrelationen auf A sind also gerade die Äquivalenzrelationen, die mit sämtlichen fundamentalen Operationen f\underline{A} verträglich sind.

Beispiel: Es werde die Halbgruppe von Seite 51 betrachtet, sie werde mit \underline{S} = (S; ·) bezeichnet.

\begin{matrix}· & a & b & c & d \\ a & a & b & c & d \\ b & b & b & c & d \\ c & c & c & c & d \\ d & d & d & d & d \end{matrix}

Es ist übersichtlicher, die Kongruenzrelationen durch ihre Äquivalenzklassen (”Kongruenzklassen“) anzugeben. Die Halbgruppe \underline{S} hat zum Beispiel Kongruenzrelationen Θ_{1} und Θ_{2} mit den folgenden Kongruenzklassen:

Θ_{1} : {a}, {b, c}, {d},
Θ_{2} : {a, b}, {c, d}.

Für jede Algebra \underline{A} wird die Menge der Kongruenzrelationen von \underline{A} mit Con(\underline{A}) bezeichnet. Mit Mengeninklusion ”⊆“ als Ordnung erhält man einen (vollständigen) Verband (Con(\underline{A}), ⊆ ). Das kleinste Element dieses Verbands ist immer Δ_{A} := {(a, a) | a ∈ A} (”Delta-A“, ”Identität“) während das größte Element mit ∇_{A} := {(a, b) | a, b ∈ A} (”Nabla-A“, ”Allrelation“) bezeichnet ist.

Aufgabe: Finde alle Kongruenzrelationen der Halbgruppe \underline{S} oben auf dieser Seite. Zeichne ein Liniendiagramm des Verbands (Con(\underline{S}), ⊆ ). Folgende Tatsachen helfen beim Verständnis sowie beim Lösen obiger Aufgabe:

Die Menge aller Äquivalenzrelationen auf einer Menge A werde mit Eq(A) bezeichnet, sie bildet mit Mengeninklusion ”⊆“ einen Verband (Eq(A), ⊆ ). Das folgende Diagramm zeigt ein Liniendiagramm des Verbands (Eq(A), ⊆ ) für A = {1, 2, 3}:

[figure: 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; 3; 1; 2; Δ_{{1,2,3}}; ∇_{{1,2,3}}; Eq({1, 2, 3})]

Abbildung 34: Liniendiagramm von (Eq(A), ⊆ )

Im Verband Eq(A) (für beliebiges A) gilt, für Θ_{1}, Θ_{2} ∈ Eq(A):

Θ_{1} ∧ Θ_{2} = Θ_{1} ∩ Θ_{2}
Θ_{1} ∨ Θ_{2} = ⋂{ϕ ∈ Eq(A) | ϕ ⊇ Θ_{1} ∪ Θ_{2}}

Das Supremum Θ_{1} ∨ Θ_{2} kann konstruktiv beschrieben werden. Für Θ_{1}, Θ_{2} ∈ Eq(A) sei das Relationenprodukt Θ_{1} ∘ Θ_{2} definiert wie folgt:

Θ_{1} ∘ Θ_{2} := {(x, y) | ∃z ∈ A: x Θ_{1} z Θ_{2} y}

Man beachte, dass das Relationenprodukt assoziativ ist, also keine Klammern gesetzt werden müssen. Es gilt:

Tatsache: Für jede Menge A und alle Θ_{1}, Θ_{2} ∈ Eq(A) gilt

Θ_{1} ∨ Θ_{2} = Θ_{1} ∪ (Θ_{1} ∘ Θ_{2}) ∪ (Θ_{1} ∘ Θ_{2} ∘ Θ_{1}) ∪ (Θ_{1} ∘ Θ_{2} ∘ Θ_{1} ∘ Θ_{2}) ∪ …

das heißt (a, b) ∈ Θ_{1} ∨ Θ_{2} genau dann, wenn es sin n ∈ ℕ und Elemente c_{1}, …, c_{n} ∈ A gibt mit

a = c_{1} Θ_{1} c_{2} Θ_{2} c_{3} Θ_{1} c_{4} … c_{n} = b

Sind jetzt Θ_{1}, Θ_{2} ∈ Con(\underline{A}) für eine Algebra \underline{A}, dann gilt, mit den eben definierten Operationen ∨ und ∧ auf Eq(A):

Θ_{1} ∨ Θ_{2} ∈ Con(\underline{A}), Θ_{1} ∧ Θ_{2} ∈ Con(\underline{A})

Satz: Für jede Algebra \underline{A} ist (Con(\underline{A}), ⊆) ein Unterverband von (Eq(\underline{A}), ⊆). Außerdem gilt immer Δ_{A}, ∇_{A} ∈ Con(\underline{A}).

Beispiele: (a) Hat eine Algebra \underline{A} keine fundamentalen Operationen, F = ∅, so gilt Con(\underline{A}) = Eq(A).

(b) Auf jeder Menge A sind die konstanten Operationen

f_{c}^{(n)}: A^{n} ⟶ A, f(x_{1}, …, x_{n}) = c für alle x_{1}, …, x_{n} ∈ A

mit allen Θ ∈ Eq(A) verträglich. Das selbe gilt für die (einstellige) identische Abbildung id_{A} auf A, aber auch für die Projektionsabbildungen

P_{i}^{(n)}: A^{n} ⟶ A, P_{i}^{(n)}(x_{1}, …, c_{n}) := x; für alle x_{1}, …, x_{n} ∈ A

(c) Wie in obigem Satz festgestellt, sind Δ_{A} und ∇_{A} Kongruenzrelationen für jede Algebra \underline{A}. Im Fall, dass es nur diese Kongruenzrelationen gibt, Con(\underline{A}) = \{Δ_{A}, ∇_{A}\}, nennt man die Algebra einfach. Beispielsweise ist \underline{A} = (A; Op(A)) einfach (mit der Menge Op(A) sämtlicher endlichstelliger Operationen auf A als Menge der fundamentalen Operationen).

Wie stellt man allgemein fest, welches die mit einer Operationenmenge F auf A verträglichen Äquivalenzrelationen, das heißt die Kongruenzrelationen der Algebra \underline{A} = (A; F) sind? Hierbei kann folgendes helfen:

Definition: Sei \underline{A} = (A; F) eine Algebra. Jede Abbildung der Form

f: A ⟶ A, x ↦ f(a_{1}, …, a_{i−1}, x, a_{i+1}, …, a_{n})

mit f ∈ F (n-stellig) und a_{1}, …, a_{i−1}, a_{i+1}, …, a_{n} ∈ A heißt eine Translation von \underline{A}.

Beispiel: Die Algebra \underline{S} = (S; ·) von Seite 65 hat folgende Translationen:

x ↦ a · x mit Wertetabelle \begin{matrix}x & a & b & c & d \\ a · x & a & b & c & d \end{matrix}

x ↦ b · x mit Wertetabelle \begin{matrix}x & a & b & c & d \\ b · x & b & b & c & d \end{matrix}

x ↦ c · x mit Wertetabelle \begin{matrix}x & a & b & c & d \\ c · x & c & c & c & d \end{matrix}

x ↦ d · x mit Wertetabelle \begin{matrix}x & a & b & c & d \\ d · x & d & d & d & d \end{matrix}

Dies sind alle Translationen von \underline{S}. Sie entsprechen den Zeilen (bzw. Spalten) der Verknüpfungstafel.

Mit den Translationen lassen sich sämtliche Kongruenzrelationen einer Algebra \underline{A} bestimmen. Zunächst können sämtliche Hauptkongruenzrelationen Θ(x, y) ∈ Con(\underline{A}), x ≠ y, bestimmt werden. Es handelt sich bei Θ(x, y) um die kleinste das Paar (x, y) enthaltende Kongruenzrelation auf \underline{A}. Es gilt:

Bemerkung: Θ(x, y) ist die transitive, symmetrische Hülle der Menge

T (x, y) := \{(t(x), t(y)) | t Translation von \underline{A}\}

Die Kongruenzrelationen der Form Θ(x, y) können jetzt benutzt werden, um sämtliche Kongruenzrelationen von \underline{A} zu finden:

Bemerkung: Für jede Kongruenzrelation Θ ∈ Con(\underline{A}) gilt

Θ = ⋁{Θ(x, y) | (x, y) ∈ Θ}

das heißt Θ ist ein Supremum von Hauptkongruenzen.

Beispiel: Es wird weiter die Halbgruppe \underline{S} von 65 betrachtet. Mit den Translationen vom letzen Beispiel erhält man zum Beispiel folgende Paare, ausgehend von einem Paar (x, y):

(a, b): (a, b), (b, b), (c, c), (d, d) → Θ(a, b) hat Klassen {a, b}, {c}, {d}.
(a, c): (a, c), (b, c), (c, c), (d, d) → Θ(a, c) hat Klassen {a, b, c}, {d}.
(a, d): (a, d), (b, d), (c, d), (d, d) → Θ(a, d) hat nur Klasse {a, b, c, d}.

Und so weiter! Man erhält alle Hauptkongruenzrelationen, und als Suprema aus diesen dann sämtliche Kongruenzrelationen.

Man kann zueinander äquivalente Elemente bezüglich einer Äquivalenzrelation bekanntlich als ”gleich“ auffassen, jedenfalls aus einem gewissen ”Blickwinkel“. So soll das auch mit zueinander äquivalenten (das heißt kongruenten) Elementen geschehen:

Definition: Sei Θ eine Kongruenzrelation einer Algebra \underline{A} = (A; F\underline{A}). Auf der Menge A/Θ := {[a]Θ | a ∈ A} der Kongruenzklassen von Θ wird die Faktoralgebra \underline{A}/Θ = (A/Θ; F_{\underline{A}/Θ}), indem für jeden n-stelliges Operationssymbol f ∈ F und alle a_{1}, …, a_{n} ∈ A folgendes definiert wird:

f_{\underline{A}/Θ}([a_{1}]Θ, …, [a_{n}]Θ) := [f\underline{A}(a_{1}, …, a_{n})]Θ

Man sagt, dass die Operationen von f_{\underline{A}/Θ} ”repräsentantenweise“ definiert werden, in obiger Definition ist jedes a_{i} ein ”Repräsentant“ der Klasse [a_{i}]Θ. Aber das könnte schiefgehen, die Ergebisse könnten von der Wahl der Repräsentanten abhängen. Glücklicherweise gilt:

Satz: Faktoralgebren \underline{A}/Θ sind wohldefiniert: Ist Θ eine Kongruenzrelation einer Algebra \underline{A}, ist f\underline{A} eine n-stellige, fundamentale Operation von \underline{A}, und gilt [a_{1}]Θ = [b_{1}]Θ, …, [a_{n}]Θ = [b_{n}]Θ, dann gilt auch

f_{\underline{A}/Θ}([a_{1}]Θ, …, [a_{n}]Θ) = f_{\underline{A}/Θ}([b_{1}]Θ, …, [b_{n}]Θ)

Der Beweis ist ganz offensichtlich (und klappt nur, weil Θ eine Kongruenzrelation von \underline{A} ist): Die Vorraussetzung [a_{1}]Θ = [b_{1}]Θ, …, [a_{n}]Θ = [b_{n}]Θ lässt sich schreiben als

a_{1}Θb_{1}, …, a_{n}Θb_{n}

Da Θ eine Kongruenzrelation ist, folgt mit Bedingung (Vert)

f\underline{A}(a_{1}, …, a_{n})Θf\underline{A}(b_{1}, …, b_{n})

das heißt f_{\underline{A}/Θ}([a_{1}]Θ, …, [a_{n}]Θ) = [f\underline{A}(a_{1}, …, a_{n})]Θ = [f\underline{A}(b_{1}, …, b_{n})]Θ = f_{\underline{A}/Θ}([b_{1}]Θ, …, [b_{n}]Θ), wie behauptet. □

Beispiele: (a) Zuerst die Algebra \underline{S} = (S; ·) von Seite 65, mit der Kongruenzrelation Θ_{1} (mit Kongruenzklassen \{a\}, \{b, c\}, \{d\}). Die Faktoralgebra \underline{S}/Θ_{1} hat dann folgende Verknüpfungstafel für ihre wiederum mit · bezeichnete Operation:

\begin{matrix}· & \{a\} & \{b, c\} & \{d\} \\ \{a\} & \{a\} & \{b, c\} & \{d\} \\ \{b, c\} & \{b, c\} & \{b, c\} & \{d\} \\ \{d\} & \{d\} & \{d\} & \{d\} \end{matrix}

(b) Der Klassiker: Werde die Gruppe \underline{ℤ} = (ℤ; +, −, 0) der ganzen Zahlen betrachtet, und sei n ∈ ℕ. Durch

xΘ_{n}y :⇔ n teilt x − y

wird eine zweistellige Relation Θ_{n} auf ℤ definiert. Schon (ganz weit) oben wurde gezeigt, dass Θ_{n} eine Äquivalenzrelation ist. Natürlich ist Θ_{n} sogar eine Kongruenzrelation von \underline{ℤ}: Aus a_{1}Θ_{n}b_{1} und a_{2}Θ_{n}b_{2} folgt

n teilt a_{1} − b_{1} und a_{2} − b_{2}

Deshalb teilt n auch (a_{1} + a_{2}) − (b_{1} + b_{2}) = (a_{1} − b_{1}) + (a_{2} − b_{2}), was (a_{1} + a_{2})Θ_{n}(b_{1} + b_{2}) bedeutet. Außerdem teilt n auch −a_{1} − (−b_{1}) = −(a_{1} − b_{1}), das heißt es folgt (−a_{1})Θ_{n}(−b_{1}). Die Faktoralgebra \underline{ℤ}/Θ_{n} hat die Kongruenzklassen

[0]Θ_{n}, [1]Θ_{n}, …, [n − 1]Θ_{n}

Das Rechnen mit diesen Klassen entspricht dem Rechnen mit modulo n in ℤ_{n} = {0, 1, …, n − 1}.

(c) Noch ein Klassiker: Sei V ein Vektorraum und U ≤ V ein Untervektorraum. Sei Θ_{u} die Äquivalenzrelation mit den Nebenklassen a + U, a ∈ V, als Äquivalenzklassen. Dann ist Θ_{u} eine Kongruenzrelation von V. Und:

Alle Kongruenzrelationen eines Vektorraums V sind von der Form Θ_{u} für einen Untervektorraum U von V.

Zum Abschluss dieses sehr ausführlichen Abschnitts wird eine Möglichkeit vorgeführt, wie man Algebren miteinander ”vergleichen“ kann, nämlich mit Hilfe von Homomorphismen. Eine einfache Version hiervon stellen die Isomorphismen dar, das heißt ”Umbenennungen“ der Elemente von Algebren mittels bijektiver Abbildungen:

Definition: Seien \underline{A} und \underline{B} zwei Algebren des selben Ähnlicheitstyps. Sei φ: A ⟶ B eine bijektive Abbildung der Grundmengen. Man nennt φ einen Isomorphismus von \underline{A} auf \underline{B}, falls für jedes Operationssymbol f ∈ F (von Stelligkeit σ(f) = n) und für alle a_{1}, …, a_{n} ∈ A folgendes gilt:

(Hom) φ(f\underline{A}(a_{1}, …, a_{n})) = f\underline{B}(φ(a_{1}), …, φ(a_{n})) Homomorphie

Die Algebren \underline{A} und \underline{B} werden dann isomorph genannt, in Zeichen \underline{A} ≅ \underline{B}.

Beispiele: (a) Auf Seite 54 wurde ein Isomorphismus zwischen den Vektorräumen P_{n} (reelle Poynome vom Grad kleiner n) und ℝ^{n} angegeben.

(b) Die Gruppe \underline{ℤ}_{6} = (ℤ_{6}; +, −, 0) ist isomorph zum direkten Produkt \underline{ℤ}_{2} × \underline{ℤ}_{3}. Ein Isomorphismus φ: \underline{ℤ}_{6} ⟶ \underline{ℤ}_{2} × \underline{ℤ}_{3} wird gegeben durch:

\begin{matrix}x & 0 & 1 & 2 & 3 & 4 & 5 \\ φ(x) & 00 & 11 & 02 & 10 & 01 & 12 \end{matrix}

(c) Die ersten beiden der folgenden Gruppen sind isomorph; ein Isomorphismus wird gegeben durch φ: {0, 1, 2, 3} ⟶ {a, b, c, d} mit

\begin{matrix}x & 0 & 1 & 2 & 3 \\ φ(x) & a & b & c & d \end{matrix}

Die dritte Gruppe ist nicht isomorph zu den ersten beiden:

+ 0 1 2 3 0 0 1 2 3 1 1 2 3 0 2 2 3 0 1 3 3 0 1 2_{\underline{G}_{1} = (\{0, 1, 2, 3\}; +, −, 0)}  \begin{matrix}· & a & b & c & d \\ a & a & b & c & d \\ b & b & c & d & a \\ c & c & d & a & b \\ d & d & a & b & c \end{matrix}_{\underline{G}_{2} = (\{a, b, c, d\}; ·,^{−1}, a)}  \begin{matrix}∘ & A & B & C & D \\ A & A & B & C & D \\ B & B & A & D & C \\ C & C & D & A & B \\ D & D & C & B & A \end{matrix}_{\underline{G}_{3} = (\{A, B, C, D\}; ∘,^{−1}, A)}

Es ist klar, dass obige Abbildung φ ein Isomorphismus von \underline{G}_{1} auf \underline{G}_{2} ist. Aber wie kann man sehen, dass \underline{G}_{1} und \underline{G}_{3} nicht isomorph sind? Einfache Möglichkeit: \underline{G}_{3} erfüllt die Gleichung x^{2} = 1 (das heißt A∘A = B ∘B = C ∘C = D ∘D = A), während \underline{G}_{1} diese Gleichung nicht erfüllt, zum Beispiel ist 1 + 1 = 2 ≠ 0.

2.2.6 Homomorphismen

Jetzt zur angekündigten Verallgemeinerung:

Definition: Eine Abbildung φ: A ⟶ B zwischen den Grundmengen zweier Algebren \underline{A} und \underline{B} des selben Ähnlichkeitstyps heißt Homomorphismus von \underline{A} nach \underline{B}, wenn die Homomorphiebedingung (Hom) von Seite 70 erfüllt ist.

Bemerkung: Homomorphismen zwischen Algebren A und B müssen nicht injektiv sein, das heißt verschiedene Elemente von A können auf das selbe Ergebnis abgebildet werden. Sie müssen auch nicht surjektiv sein, das heißt es müssen nicht alle Elemente von B als Ergebnisse des Homomorphismus auftreten. (Dies wird schon im ersten der folgenden Beispiele deutlich.)

Beispiele:

• Zwischen den beiden oben definierten Gruppen \underline{G}_{1} und \underline{G}_{3} ist ein Homomorphismus φ: G_{1} ⟶ G_{3} gegeben durch:

\begin{matrix}x & 0 & 1 & 2 & 3 \\ φ(x) & A & B & A & B \end{matrix}

(Dieses Beispiel wird im nächsten Abschnitt näher untersucht. Stichwort: Homomorphiesatz.)

• Sei \underline{ℤ} = (ℤ; +, −, 0) die Gruppe der ganzen Zahlen. Für jedes n ∈ ℕ ist ein Homomorphismus φ_{n}: ℤ ⟶ ℤ (also ein Endomorphismus von \underline{ℤ}) gegeben durch

φ_{n}(x) := n + x

Aufgabe: Zeige, dass alle Endomorphismen von \underline{ℤ} von dieser Form sind.

• Sei (A^{∗}; ·, λ) das Wortmonoid über dem Alphabet A = {a, b} (siehe Seite 50) und sei (ℕ_{0}^{2}; +, (0, 0)) das Monoid mit komponentenweiser Addition:

(x_{1}, x_{2}) + (y_{1}, y_{2}) := (x_{1} + y_{1}, x_{2} + y_{2})

(es handelt sich also um das direkte Produkt \underline{ℕ_{0}}^{2} = \underline{ℕ_{0}} × \underline{ℕ_{0}} des Monoids \underline{ℕ_{0}} = (ℕ_{0}; +, 0) mit sich selbst.) Ein Homomorphismus φ: A^{∗} ⟶ ℕ_{0}^{2} wird gegeben durch

φ(a_{1}a_{2} ⋯ a_{k}) = (i, j)

wobei i die Anzahl der a’s und j die Anzahl der b’s in a_{1}a_{2} ⋯ a_{k} sei.

Beispielsweise gilt φ(λ) = (0, 0) und φ(abbabaaa) = (5, 3)

2.3 Der Homomorphiesatz der Allgemeinen Algebra

Zu jedem Homomorphismus zwischen zwei Algebren gehört in natürlicher Weise eine Unteralgebra und eine Kongruenzrelation:

Bemerkung: Sei φ: A ⟶ B ein Homomorphismus der Algebra \underline{A} in die Algebra \underline{B}. Dann gilt φ(A) ∈ Sub(\underline{B}), das heißt φ(A) ist die Grundmenge einer Unteralgebra \underline{φ(A)} ⩽ \underline{B}) (”Bild von A unter φ“). Außerdem ist

Kern(φ) := {(a_{1}, a_{2}) ∈ A^{2} | φ(a_{1}) = φ(a_{2})}

eine Kongruenzrelation auf \underline{A} (”Kern von φ“), das heißt es gilt Kern(φ) ∈ Con(\underline{A}).

Beweis: Für φ(A) ∈ Sub(\underline{B}) muss gezeigt werden, dass φ(A) abgeschlossen ist gegen die Operationen f\underline{B} von \underline{B}. Sei f\underline{B} n-stellig und seien a_{1}, …, a_{n} ∈ A gegeben. Für φ(a_{1}), …, φ(a_{n}) ∈ φ(A) gilt dann:

f\underline{B}(φ(a_{1}), …, φ(a_{n})) =^{(Hom)} φ(f\underline{A}(a_{1}, …, a_{n})) ∈ φ(A)

Für den Nachweis von Kern(φ) ∈ Con(\underline{A}) muss gezeigt werden, dass Kern(φ) eine Äquivalenzrelation auf A ist (was aber offensichtlich ist) und dass für Kern(φ) die Verträglichkeitsbediungung (Vert) von Seite 65 gilt. Sei also f\underline{A} eine nstellige fundamentale Operation von \underline{A} und für a_{1}, …, a_{n}, b_{1}, …, b_{n} ∈ A gelte

a_{1}Kern(φ)b_{1}, …, a_{n}Kern(φ)b_{n},

das heißt φ(a_{1}) = φ(b_{1}), …, φ(a_{n}) = φ(b_{n}). Dann gilt

φ(f\underline{A}(a_{1}, …, a_{n})) =^{(Hom)} f\underline{B}(φ(a_{1}), …, φ(a_{n}))
= f\underline{B}(φ(b_{1}), …, φ(b_{n}))
=^{(Hom)} φ(f\underline{A}(b_{1}, …, b_{n}))

also f\underline{A}(a_{1}, …, a_{n})Kern(φ)f\underline{A}(b_{1}, …, b_{n}). □

Als Beispiel wird der Homomorphismus φ: \underline{G}_{1} ⟶ \underline{G}_{3} von Seite 70. Tatsächlich gilt φ(G_{1}) = \{A, B\} ∈ Sub(\underline{G}_{3}). Die Kongruenzrelation Kern(φ) hat diese Kongruenzklassen {0, 2} und {1, 3}.

Jetzt zum ”Kern“ dieses Abschnitts. Dazu zuerst:

Beobachtungen: Sei \underline{C} eine Unteralgebra der Algebra \underline{B}. Dann ist die Abbildung

i: C ⟶ B, x ↦ x  (Inklusionsabbildung)

ein Homomorphismus \underline{C} ⟶ \underline{B}.

Sei Θ eine Kongruenzrelation der Algebra \underline{A}. Dann ist die Abbildung

π: A ⟶ A/Θ, x ↦ [x]Θ  (Faktorabbildung)

ein Homomorphismus \underline{A} ⟶ \underline{A}/Θ.

Der Beweis hierfür ist einfach, er sei dem Leser überlassen.

Jetzt werde wieder die Ausgangssituation betrachtet, also ein Homomorphismus φ: \underline{A} ⟶ \underline{B}. In den obigen Beobachtungen sei \underline{C} = \underline{φ(A)} (die Bildalgebra) und Θ = Kern(φ) (der Kern von φ), mit den zugehörigen Homomorphismen i: φ(A) ⟶ B und π: A ⟶ A/Kern(φ).

Beobachtung: Für den Homomorphismus φ: \underline{A} ⟶ \underline{B} werde die Abbildung

φ′: A/Kern(φ) ⟶ φ(A), [x]Kern(φ) ↦ φ(x)

definiert. Dann ist φ′ wohldefiniert. Außerdem ist φ′ ein Isomorphismus von \underline{A}/Kern(φ) in \underline{φ(A)}.

Beweis: Die Abbildung φ′ ist tatsächlich wohldefiniert: Sie geht tatsächlich von A/Kern(φ) in φ(A). Außerdem folgt aus [x]Kern(φ) = [y]Kern(φ) sofort φ(x) = φ(y). Es handelt sich bei φ′ um einen Homomorphismus (eigentlich klar, wie sollte es anders sein; dennoch – ein letztes Mal – ein derartig ”schrecklicher“ Beweis): Sei also f ein n-stellliges Operatorsymbol und seien a_{1}, …, a_{n} ∈ A. Dann gilt

φ′(f_{\underline{A}/Kern(φ)}([a_{1}]Kern(φ), …, [a_{n}]Kern(φ)))
= φ′([f\underline{A}(a_{1}, …, a_{n})]Kern(φ))
= φ(f\underline{A}(a_{1}, …, a_{n}))
= f\underline{B}(φ(a_{1}), …, φ(a_{n}))
= f\underline{φ(A)}(φ(a_{1}), …, φ(a_{n}))
= f\underline{φ(A)}(φ′([a_{1}]Kern(φ)), …, φ′([a_{n}]Kern(φ)))

Es bleibt zu zeigen, dass φ′ ein Isomorphismus, das heißt auch bijektiv ist: φ′ ist nach Definition offensichtlich surjektiv. Für die Injektivität werde jetzt φ′([x]Kern(φ)) = φ′([y]Kern(φ)) vorausgesetzt. Das bedeutet φ(x) = φ(y), also xKern(φ)y, also [x]Kern(φ) = [y]Kern(φ). □

Damit ist insgesamt folgendes bewiesen (Bezeichnungen wie oben):

Homomorphiesatz: Sei φ: \underline{A} ⟶ \underline{B} ein Homomorphismus. Dann kann φ in ein Produkt φ = i ∘ φ′ ∘ π aus einem surjektiven Homomorphismus π (Faktorabbildung), einem Isomorphismus φ′ und einem injektiven Homomorphismus i (Inklusionsabbildung) zerlegt werden. In anderen Worten, das folgende Diagramm kommutiert:

[figure: \underline{A}/Kern(φ); \underline{A}; \underline{φ(A)}; \underline{B}; φ; φ′; π; i]

Abbildung 35: Homomorphiesatz

Quintessenz: ”Arbeitsteilung“, π macht alles gleich, was unter φ gleich wird, φ(A) enthält alles, was unter φ herauskommt. Kann φ′ nur noch ein Isomorphismus sein!

Zurück zum Beispiel φ: \underline{G}_{1} ⟶ \underline{G}_{3}. Es ist sinnvoll, sich die Zusammenhänge auch an den Verknüpfungstafeln von \underline{G}_{1} und \underline{G}_{3} auf Seite 70 klar zu machen.

2.4 Terme und Polynome

Jetzt werden die aus den fundamentalen Operationen einer Algebra ”zusammengesetzten“ Operationen untersucht. Dies wird für die Untersuchung von Gleichungen wichtig sein.

[figure: 2; 3; 0; 1; A; B; C; D; φ; \underline{G}_{1}; \underline{G}_{3}; A; B; C; D; φ′; [0]Kern(φ); [1]Kern(φ); φ(\underline{G}_{1}); \underline{G}_{1}/Kern(φ); \underline{G}_{3}]

Abbildung 36: Homomorphiesatz (Beispiel)

2.4.1 Terme

Definition: Sei (F, σ) ein Ähnlichkeitstyp von Algebren, und X eine Menge, deren Elemente Variablen genannt werden, mit X ∩ F = ∅. Mit folgender Rekursionsvorschrift wird die Menge T (X) der Terme vom Typ (F, σ) über X definiert:

(1) Für alle Variablen x ∈ X liegt das 1-Tupel (x) in T (X),

(2) für alle f ∈ F (mit σ(f) = n) und alle t_{1}, …, t_{n} ∈ T (X) gilt (f, t_{1}, …, t_{n}) ∈ T (X).

(3) Es gibt nur die mit den Regel (1) und (2) gebildeten Terme.

Die Termalgebra \underline{T} (X) vom Typ (F, σ) über der Variablenmenge X ist definiert als die Algebra mit Grundmenge T (X) und den für jedes f ∈ F (n-stellig) folgendermaßen definierten Operationen f_{\underline{T} (X)}:

f_{\underline{T} (X)}(t_{1}, …, t_{n}) = (f, t_{1}, …, t_{n})

Bemerkungen:

• Für t ∈ T (X) schreibt man oft auch t(x_{1}, …, x_{n}), um anzudeuten, dass die in t enthaltenen Variablen alle zur Menge {x_{1}, …, x_{n}} gehören. Man nennt den Term t(x_{1}, …, x_{n}) n-stellig.

• Für jeden gegebenen Ähnlichkeitstyp (F, σ) besteht T (X) genau aus den ”sinnvoll gebildeten Ausdrücken“, die mit den Elementen von X ∪ F gebildet werden können. Sei zum Beispiel F = {+} mit σ(+) = 2, und sei X = {x, y, z}. Dann sind (beispielsweise) folgende Ausdrücke Terme über X:

(x), (y), (z), (+, x, y), (+, x, x), (+, (+, x, y), z)

(Diese schreibt man oft in der einfacheren Form x, y, z, x + y, x + x, (x + y) + z.) Die folgenden Ausdrücke sind hingegen keine Terme:

(x, y, +), (+, x), (+, x, y, z)

Unmittelbar aus obiger Definition folgt:

Bemerkung: Jede Termalgebra \underline{T} (X) wird von der Variablenmenge X erzeugt, das heißt es gilt T (X) = ⟨X⟩.

Es folgt eine wesentliche Eigenschaft der Algebra \underline{T} (X):

Satz: (”Einsetzungs-Homomorphismus“) Sei \underline{T} (X) die Termalgebra vom Typ (F, σ) über X. Für jede Algebra \underline{A} vom Typ (F, σ) und jede Abbildung φ: X ⟶ A gibt es dann genau einen Homomorphismus φ̄: \underline{T} (X) ⟶ \underline{A}, der φ fortsetzt, das heißt mit φ̄|_{x} = φ.

Beweis: Sei \underline{A} vom Typ (F, σ) und φ: X ⟶ A gegeben. Dann muss offenbar φ̄(x) = φ(x) für alle x ∈ X gelten und außerdem

φ̄(f, t_{1}, …, t_{n}) = f\underline{A}(φ̄(t_{1}), …, φ̄(t_{n}))

für jeden Term der Form (f, t_{1}, …, t_{n}). Damit ist φ̄ auf ganz T (X) definiert. Wegen f_{\underline{T} (X)}(t_{1}, …, t_{n}) = (f, t_{1}, …, t_{n}) ist φ automatisch ein Homomorphismus.

□

2.4.2 Termfunktionen

Definition: Sei t ein Term von Typ (F, σ) über X = \{x_{1}, …, x_{n}\} und \underline{A} eine Algebra desselben Typs. Für a_{1}, …, a_{n} ∈ A sei φ_{a_{1},...,a_{n}} der nach obigem Satz eindeutig bestimmte Homomorphismus mit x_{i} ↦ a_{i} für i = 1, …, n. Dann entsteht eine n-stellige Operation t\underline{A}: A^{n} ⟶ A durch:

t\underline{A}(a_{1}, …, a_{n}) := φ_{a_{1},...,a_{n}}(t)

Die derart gebildeten Operationen t\underline{A} heißen Termfunktionen auf \underline{A}. Die Menge aller Termfunktionen auf \underline{A} wird mit T (\underline{A}) bezeichnet.

Also: Termfunktionen entstehen aus Termen, indem man für diese Variablen Elemente einsetzt und dann das Ergebnis ”ausrechnet“.

Die Termfunktionen einer Algebra sind genau die Operationen, die man durch Superposition (”ineinander einsetzen“) aus den fundamentalen Operationen der Algebra sowie den Projektionsabbildungen p_{i}^{n}(x_{1}, …, x_{n}) = x_{i} erhält.

Die Termfunktionen liefern für jede Algebra unmittelbar den Unteralgebren-Hüllenoperator (der Beweis ist offensichtlich):

Tatsache: Für jede Algebra A und jede Teilmenge C ⊆ A gilt:

⟨C⟩ = {t_{A}(c_{1}, …, c_{n}) | n ∈ ℕ_{0}, t ∈ T (x_{1}, …, x_{n}), c_{1}, …, c_{n} ∈ C)}

Termfunktionen verhalten sich bezüglich den Homomorphismen einer Algebra wie fundamentale Operationen (auch ziemlich offensichtlich, aber trotzdem mit Beweis):

Satz: Die Algebren \underline{A} und \underline{B} und der n-stellige Term t seien alle vom gleichen Typ. Für jeden Homomorphismus φ: \underline{A} ⟶ \underline{B} und alle a_{1}, …, a_{n} ∈ A gilt dann:

φ(t\underline{A}(a_{1}, …, a_{n})) = t\underline{B}(φ(a_{1}), …, φ(a_{n}))

Beweis mit Induktion über den Aufbau der Terme (”algebraischer Induktion“): Sei t ∈ T (x_{1}, …, x_{n}). Im Fall t = x_{i} gilt die Behauptung offensichtlich. Nun sei t = (f, t^{1}, …, t^{m}), mit m-stelligem f ∈ F und Termen t^{1}, … t^{m} ∈ T (x_{1}, …, x_{n}). Werde angenommen, dass die Behauptung für t^{1}, …, t^{m} schon gezeigt sei. Dann gilt:

φ(t\underline{A}(a_{1}, …, a_{n}))
= φ(f\underline{A}(t1 ; \underline{A}(a_{1}, …, a_{n}), …, tm ; \underline{A}(a_{1}, …, a_{n})))
= f\underline{B}(φ(t1 ; \underline{A}(a_{1}, …, a_{n})), …, φ(tm ; \underline{A}(a_{1}, …, a_{n})))
= f\underline{B}(t1 ; \underline{B}(φ(a_{1}), …, φ(a_{n})), …, tm ; \underline{B}(φ(a_{1}), …, φ(a_{n})))
= t\underline{B}(φ(a_{1}), …, φ(a_{n}))
□

2.4.3 Polynome

Definition: Sei \underline{A} eine Algebra. Aus einem Term t ∈ T (X) entsteht ein Polynom, indem für einige Variablen von t Elemente von A eingesetzt werden. Die Menge all solcher Polynome werde mit P_{A}(X) bezeichnet. Indem man für die verbliebenen Variablen eines Polynoms p(x_{1}, …, x_{n}) beliebige Elemente a_{1}, …, a_{n} ∈ A einsetzt und dann auswertet, erhält man eine Polynomfunktion p_{A}(x_{1}, …, x_{n}) auf A. Die Menge aller Polynomfunktionen auf A werde mit P (A) bezeichnet.

Diese Definition war nicht sehr formal, darum zum besseren Verständnis ein Beispiel:

Beispiel: Sei \underline{A} = (A; +) eine Algebra des Typs F = \{+\} mit σ(+) = 2 und sei b, c ∈ A. Dann sind (zum Beispiel) die folgenden Ausdrücke Polynome von A (aus denen dann jeweils Polynomfunktionen gewonnen werden können):

x + y (alle Terme sind Polynome!), b + z,

(b + y) + z, (b + y) + c, ((x + b) + c) + (z + b)

So wie die Termfunktionen die Unteralgebren einer Algebra erhalten (siehe Tatsache auf Seite 75), so erhalten die Polynomfunktionen die Kongruenzrelationen einer Algebra (ohne Beweis):

Tatsache: Die Polynomfunktionen einer Algebra \underline{A} sind mit allen Kongruenzrelationen von A verträglich, das heißt für n ∈ ℕ_{0}, p ∈ P_{A}(x_{1}, …, x_{n}), Θ ∈ Con(\underline{A}) folgt aus a_{i}Θb_{i}, i = 1, …, n, immer:

P\underline{A}(a_{1}, …, a_{n})ΘP\underline{A}(b_{1}, …, b_{n})

2.5 Gleichungen, freie Algebren, Gleichungstheorie

In diesem Abschnitt wird vieles nur ”angerissen“, aber trotzdem einige Grundbegriffe vorgestellt. Im darauffolgenden Abschnitt über boolesche Algebren wird einiges verwendet werden. Auf diese Weise wird auch das folgende Kapitel über Logik vorbereitet.

2.5.1 Gleichungen

Definition: Sei T (X) die Menge aller Terme vom Typ (F, σ) über der Variablenmenge X. Dann heißt jedes Paar (s, t) ∈ T (X) × T (X) eine Gleichung über X. Anstelle von (s, t) schriebt man oft:

s ≈ t oder s(x_{1}, … x_{n}) ≈ t(x_{1}, …, x_{n})

(letzteres um anzudeuten, dass die in s und t vorkommenden Variablen in der Menge \{x_{1}, …, x_{n}\} enthalten sind). Eine Algebra \underline{A} vom Typ (F, σ) erfüllt die Gleichung s(x_{1}, … x_{n}) ≈ t(x_{1}, …, x_{n}) (oder diese Gleichung gilt in \underline{A}), falls

s\underline{A}(a_{1}, …, a_{n}) = t\underline{A}(a_{1}, …, a_{n})

gilt für jede Belegung a_{1}, …, a_{n} ∈ A. In diesem Fall schreibt man

\underline{A} ⊧ s(x_{1}, … x_{n}) ≈ t(x_{1}, …, x_{n}) oder \underline{A} ⊧ s ≈ t

Beispielsweise ist eine Algebra \underline{A} = (A; ·) mit einer zweistelligen Operation · genau dann kommutativ, falls:

\underline{A} ⊧ x · y ≈ y · x

2.5.2 Gleichungstheorien

Definition: Für jedes Gleichungssystem (Gleichungsmenge) Σ ⊆ T (X) × T (X) über der Variablenmenge X sei

M(Σ) := \{\underline{A} | \underline{A} ⊧ s ≈ t für alle (s, t) ∈ Σ\}

die Klasse aller Modelle von Σ.

Für jede Klasse K von Algebren sei

G_{X}(K) := \{(s, t) ∈ T (X) × T (X) | \underline{A} ⊧ s ≈ t für alle \underline{A} ∈ K\}

die Menge aller in allen Algebren von K gültigen Gleichungen über der Variablenmenge X.

Die Klassen von Algebren der Form K = M(Σ) heißen gleichungsdefiniert. Jede Menge von Gleichungen der Form Σ = G_{X}(K) wird eine Gleichungstheorie über X genannt.

Beispiele und Bemerkungen:

• Da Gruppen mit Hilfe von Gleichungen definiert sind, ist die Klasse aller Gruppen eine gleichungsdefinierte Klasse. Das selbe gilt für viele andere schon behandelte Klassen von Algebren!

• Beispielsweise bilden alle Gleichungen (über einer gegebener Variablenmenge X), die in allen Gruppen gelten, eine Gleichungstheorie. Es gibt beliebig viele andere Beispiele. In vielen Fällen ist es ein großes (oft sogar prinzipiell unlösbares!) Problem festzustellen, ob eine vorgegebene Gleichung zu einer gegebenen Gleichungstheorie gehört oder nicht.

• Am bequemsten ist es, immer die abzählbar-unendliche Variablenmenge X = {x_{1}, x_{2}, x_{3}, …} zu verwenden. Jedenfalls enthält jede Gleichung nur endlich viele Variablen, also können alle Gleichungen in dieser Variablenmenge X formuliert werden!

Satz: Sei K eine Klasse von Algebren eines gegebenen Typs (F, σ) und sei \underline{T} (X) die Termalgebra dieses Typs über der Variablenmenge X. Dann gilt:

G_{X}(K) = ⋂\{Kern(φ) | φ: \underline{T} (X) ⟶ \underline{A}, \underline{A} ∈ K\}

Insbesondere ist G_{X}(K) immer eine Kongruenzrelation von \underline{T} (X).

Der Beweis dieses Satzes ist recht leicht, wird hier aber nicht geführt. Das selbe gilt für den folgenden Satz, der den entsprechenden Satz für Termalgebren von Seite 75 verallgemeinert. In diesem Satz wird anstelle einer jeden Variablen x ∈ X die Kongruenzklasse x̄ := [x]G_{X}(K) verwendet und dem entsprechend X̄ = {x̄ | x ∈ X} anstelle von X.

Satz (”Einsetzungs-Homomorphismus“ verallgemeinert): Für jede Algebra \underline{A} ∈ K und jede Abbildung φ: X̄ ⟶ A gibt es genau einen Homomorphismus φ̄: \underline{T} (X)/G_{X}(K) ⟶ \underline{A}, der φ fortsetzt, das heißt mit φ̄|X̄ = φ.

Wann liegt die Algebra \underline{T} (X)/G_{X}(K) selbst in der Klasse K? Jedenfalls dann, wenn K unter der Bildung homomorpher Bilder von Unteralgebren und direkter Produkte abgeschlossen ist, das heißt falls H(K) ⊆ K, S(K) ⊆ K und P(K) ⊆ K gilt. Dies lässt sich übrigens knapper schreiben als HSP(K) ⊆ K (wobei es auf die Reihenfolge von H, S und P sehr wohl ankommt).

2.5.3 Frei erzeugte Algebren

Feststellung: Für jede HSP-abgeschlossene Klasse K gilt:

\underline{T} (X)/G_{X}(K) ∈ K

Bemerkungen: In diesem Fall nennt man \underline{T} (X)/G_{X}(K) die von X frei erzeugte Algebra in K und bezeichnet sie kürzer mit

\underline{F}_{K}(X)

Also ist \underline{F}_{K}(X) die ”allgemeinste“ Algebra mit Erzeugendenmenge X (eigentlich mit Erzeugendenmenge X̄).

Beispiele: Sei A die Klasse aller abelschen (kommutativen) Gruppen. Ganz offenbar ist A HSP-abgeschlossen. Als Operationssymbole werden, wie bei Gruppen üblich, · und ^{−1} und 1 verwendet:

• Einelementige Variablenmenge X = {x}: Aus jeder Kongruenzklasse

[t(x)]G_{X}(K)

wird ein Repräsentant verwendet, in diesem Fall naheliegenderweise die Elemente x^{k}, k ∈ ℤ. Unter Begehung kleiner ”Ungenauigkeiten“ gilt also:

\underline{F}_{A}(\{x\}) = (\{x^{k} | k ∈ ℤ\}; ·,^{−1}, 1)

Als Beispiel eine Anwendung des Einsetzungs-Homomorphismus: Es gibt genau einen Homomorphismus

φ: \underline{F}_{A}(\{x\}) ⟶ \underline{ℤ}_{6} = (ℤ_{6}; +, −, 0) mit φ(x) = 3

nämlich mit φ(x^{k}) = 0 für k gerade und φ(x^{k}) = 3 für k ungerade.

Übrigens: \underline{F}_{A}(\{x\}) ist isomorph zu \underline{ℤ} = (ℤ; +, −, 0), ein Isomorphismus ist gegeben durch x^{k} ⟶ k.

• Als Übung: Stelle analog Überlegungen für die freie 2-erzeugte abelsche Gruppe \underline{F}_{A}(\{x, y\}) an!

2.5.4 Hauptsätze der Gleichungstheorie

Es folgen wiederum ohne Beweis, die zwei Hauptsätze der Gleichungstheorie. Beide wurden in den 30er Jahren von G. Birkhoff gefunden, der in dieser Zeit viele wesentliche Grundlagen der Allgemeinen Algebra entwickelt hat.

Erster Hauptsatz der Gleichungstheorie Birkhoff, 1935: Eine Klasse K von Algebren eines gegebenen Typs ist genau dann gleichungsdefiniert, wenn sie HSP-abgeschlossen ist, das heißt wenn HSP(K) ⊆ K gilt.

Es sei eine kleine Anwendung dieses Satzes angegeben. Frage: Könnte man Körper (ausschließlich mit Hilfe von Gleichungen definieren, bei Verwendung eines geeigneten Ähnlichkeitstyps, das heißt geeigneter Operationen? Antwort: Nein, denn direkte Produkte von Körpern sind keine Körper!

Es folgt eine Charakterisierung der Gleichungstheorien, das heißt derjenigen Gleichungsmengen Σ, die von der Form Σ = G_{X}(K) sind. Für jede Gleichungstheorie G_{X}(K) gelten offenbar folgende Regeln (anstelle von (s, t) wird suggestiver s ≈ t geschrieben):

(G1) Für alle s ∈ T (X) gilt s ≈ s ∈ G_{X}(K),
(G2) aus s ≈ t ∈ G_{X}(K) folgt t ≈ s ∈ G_{X}(K),
(G3) aus s ≈ t ∈ G_{X}(K) und t ≈ u ∈ G_{X}(K) folgt s ≈ u ∈ G_{X}(K),

(G4) aus f ∈ F (n-stellig) und s_{i} ≈ t_{i} ∈ G_{X}(K) für i = 1, …, n folgt

f(s_{1}, …, s_{n}) ≈ f(t_{1}, …, t_{n}) ∈ G_{X}(K), (G5) aus s(x_{1}, …, x_{n}) ≈ t(x_{1}, …, x_{n}) ∈ G_{X}(K) und u_{1}, …, u_{n} ∈ T (X)

folgt s(u_{1}, …, u_{n}) ≈ t(u_{1}, …, u_{n}) ∈ G_{X}(K).

Die Regeln (G1)-(G3) sagen aus, dass G_{X}(K) eine Äquivalenzrelation auf T (X) ist und (G4) besagt, dass G_{X}(K) sogar eine Kongruenzrelation von \underline{T} (X) ist (was oben schon festgestellt wurde). Regel (G5) lässt sich (gleichwertig) anders formulieren:

(G5’) Ist φ: \underline{T} (X) ⟶ \underline{T} (X) ein Homomorphismus und gilt s ≈ t ∈ G_{X}(K), dann gilt auch φ(s) ≈ φ(t) ∈ G_{X}(K).

Also ist G_{X}(K) mit allen Endomorphismen von \underline{T} (X) verträglich. Kongruenzrelationen mit dieser Eigenschaft nennt man voll-invariant. Also:

G_{X}(K) ist eine voll-invariante Kongruenzrelation von \underline{T} (X).

Es gilt aber noch mehr:

Zweiter Hauptsatz der Gleichungstheorie Birkhoff, 1935: Ein Gleichungssystem Σ ⊆ T (X) × T (X) ist genau dann eine Gleichungstheorie, wenn Σ eine voll-invariante Kongruenzrelation von \underline{T} (X) ist.

Eine wesentliche Folgerung dieses Satzes soll noch diskutiert werden. Sei Σ ⊆ T (X) × T (X) ein Gleichungsmenge. Frage: Welche Gleichungen folgen aus Σ?

Antwort A: Es folgen alle Gleichungen, die sich ausgehend von Σ, durch – eventuell mehrfache – Anwendung der Regeln (G1)-(G5) erhalten lassen. Folgt auf diese Art eine Gleichung s ≈ t aus Σ, so schreibt man dafür auch:

Σ ⊢ s ≈ t

Antwort B: Es folgen genau die Gleichungen s ≈ t aus Σ, die in allen Algebren gelten, in denen alle Gleichungen aus Σ gelten, das heißt aus Σ folgen genau die Gleichungen in G_{X}(M(Σ)). Bei dieser Art Folgerung schreibt man:

Σ ⊧ s ≈ t

Offenbar enthält Antwort B die ”stärkere“ Folgerungsart, es gilt immer

Σ ⊢ s ≈ b ⇒ Σ ⊧ s ≈ t.

Aber tatsächlich sind beide Folgerungsarten gleichwertig:

Vollständigkeitssatz der Gleichungslogik:

⊢ = ⊧

2.6 Boolesche Algebra

Dieser letzte Abschnitt des Algebra-Kapitels behandelt ein Thema, das vor allem deshalb interessant ist, weil es einerseits algebraische und andererseits ordnungsund verbandstheoretische Aspekte miteinander verbindet und weil es in der Aussagelogik unmittelbar anwendbar ist.

Definition: Eine Algebra \underline{B} = (B; +, ·,′ , 0, 1) vom Typ (2, 2, 1, 0, 0) wird boolesche Algebra genannt, falls

(verb)  (B; +, ·) ein Verband ist

und die folgenden Gleichungen gelten:

(dist)  x · (y + z) = x · y + x · z  Distributivität
(komp) x · x′ = 0, x + x′ = 1  Komplemente
(null)  x · 0 = 0, x + 0 = x  Nullelement
(eins)  x · 1 = x, x + 1 = 1  Einselement

Bemerkungen:

• In der zum Verband (B; +, ·) gehörigen geordneten Menge (B, ≤) ist 0 das kleinste Elemente und 1 das größte Element.

• In obiger Definition befinden sich ”zu viele“ Gleichungen. Zum Beispiel können die ersten Gleichungen in (null) und (eins) aus den anderen Gleichungen hergeleitet werden. Natürlich gilt das selbe auch für die zweiten Gleichungen in (null) und (eins). Von den drei Verbandsgleichungen wird nur (komm) und (abs) benötigt, während (ass) aus den anderen Gleichungen hergeleitet werden kann. Dies sind drei Übungsaufgaben.

Natürlich gelten in jeder booleschen Algebra noch weitere Gleichungen und Eigenschaften, zum Beispiel diese:

Bemerkung: In jeder booleschen Algebra \underline{B} gelten für alle x, y, z ∈ B:

(a) x + (y · z) = (x + y) · (x + z)  duale Distributivität
(b) x · y = 0, x + y = 1 ⇒ y = x′ Komplementeindeutigkeit
(c) (x + y)′ = x′ · y′, (x · y)′ = x′ + y′ de Morgan’sche Gesetze
(d) x′′ = x, 0′ = 1, 1′ = 0

Beweis: (a) Die Verbandsgleichungen und (dist) liefern:

(x + y)(x + z) = (x + y)x + (x + y)z = xx + yx + xz + yz = x + yz

(b) Es gilt x(x′ + y) = xx′ + xy = 0 + 0 = 0. Dies und y ≤ x′ + y ergeben:

x′ + y = 1(x′ + y) = (x + y)(x′ + y) = x(x′ + y) + y(x′ + y) = 0 + y = y

Ganz ähnlich ergibt sich

x′ + y = 1(x′ + y) = (x + x′)(x′ + y) = x(x′ + y) + x′(x′ + y) = 0 + x′ = x′

also insgesamt y = x′.

(c) Es wird x′y′(x + y) = 0 und x′y′ + (x + y) = 1 gezeigt. Die behauptete Gleichung x′y′ = (x + y)′ folgt dann mit (b). Verwendet wird die Distributivität und duale Distributivität:

x′y′(x + y) = x′y′x + x′y′y = y′0 + x′0 = 0 + 0 = 0

x′y′ + (x + y) = (x′ + (x + y))(y′ + (x + y)) = (1 + y)(1 + x) = 1 · 1 = 1

Die zweite Gleichung in (c) kann ”dual“ bewiesen werden (indem im eben geführten Beweis + und · vertauscht werden).

(d) x und x′′ = (x′)′ sind beides Komplemente von x′, woraus mit (b) sofort x = x′′ folgt. Mit (null) erhält man 1 · 0 = 0, 1 + 0 = 1 und wiederum mit (b) folgt 0 = 1′. Analog ergibt sich 1 = 0′ □

Beispiele:

• Folgende Operationen liefern eine 2-elementige boolesche Algebra \underline{B}_{2} := (\{0, 1\}; +, ·,′ , 0, 1):

+ 0 1 0 0 1 1 1 1  \begin{matrix}· & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{matrix}  \begin{matrix}x & 0 & 1 \\ x′ & 1 & 0 \end{matrix}

[figure: 0; x; x′; 1]

Abbildung 37: Liniendiagramm einer 8-elementigen boolesche Algebra)

• Das Liniendiagramm zeigt eine boolesche Algebra mit acht Elementen.

• Für jede Menge A erhält man eine boolesche Algebra durch

(P(A); ∪, ∩, , ∅, A)

(die Potenzmengenalgebra auf A). Die Operationen sind mengentheoretische Vereinigung und Schnitt, und die Komplementierung \overline{X} = A \ X.

2.6.1 Atome

Die Potenzmengenalgebren sind ”typische“ boolesche Algebren. Es wird gezeigt, dass jede endliche boolesche Algebra isomorph ist zu einer solchen. Hierfür wird benötigt:

Definition: Sei \underline{B} eine boolesche Algebra. Ein Element a ∈ B heißt ein Atom von \underline{B}, falls a ein oberer Nachbar des kleinsten Elements 0 von B ist (das heißt falls a > 0 gilt, es aber kein Element b gibt mit 0 < b < a). Die Menge aller Atome von \underline{B} wird mit At(\underline{B}) bezeichnet.

Lemma: In jeder endlichen booleschen Algebra \underline{B} ist jedes Element b ∈ B eindeutig durch die Elemente unterhalb von b bestimmt. Genauer: Sei \{a ∈ At(\underline{B}) | a ≤ b\} = \{a_{1}, …, a_{k}\} (mit k verschiedenen Elementen). Dann gilt:

b = a_{1} + ⋯ + a_{k}

[figure: 1; 0; b; c; c′; x; unter b; unter c′; \underline{B}]

Abbildung 38: Atome

Beweis: Sei c := a_{1}+⋯+a_{k}. Es soll c = b gezeigt werden. Wegen a_{1}, …, a_{k} ≤ b gilt c ≤ b: Werde jetzt c < b angenommen. Offenbar gilt:

bc′ + c = bc′ + bc = b(c + c′) = b · 1 = b

Es folgt bc′ > 0. In jeder endlichen booleschen Algebra hat jedes Element ungleich 0 ein Atom unter sich (Beweis hierfür?). Also gibt es ein Atom x ≤ bc′ Dann gibt es aber x ≤ c′ und x ≤ b, wobei letzteres auch x ≤ c impliziert. Daher gilt x ≤ cc′ = 0, ein Widerspruch! Also muss c = b gelten. □

Mit diesem Lemma folgt der angekündigte Sachverhalt:

Satz: Sei \underline{B} eine endliche boolesche Algebra. Dann wird ein Isomorphismus von \underline{B} auf die Potenzmengenalgebra auf der Menge At(\underline{B}) der Atome von \underline{B} gegeben durch

φ(b) := \{a ∈ At(\underline{B}) | a ≤ b\}

Beweis: Folgendes muss gezeigt werden:

(1) φ ist injektiv,

(2) φ ist surjektiv,

(3) φ(x + y) = φ(x) ∪ φ(y) für alle x, y ∈ B,

(4) φ(xy) = φ(x) ∩ φ(y) für alle x, y ∈ B,

(5) φ(x′) = \overline{φ(x)} für alle x ∈ B.

Eigentlich müsste noch φ(0) = ∅ und φ(1) = At(\underline{B}) gezeigt werden, aber dies folgt schon aus obigem (beziehungsweise ist sowieso klar).

(1) folgt unmittelbar aus dem Lemma, denn aus φ(b) = φ(c) ergibt sich

b = ∑ φ(b) = ∑ φ(c) = c

(wobei zum Beispiel φ(b) die mit + gebildete Summe aller Elemente von φ(b) bezeichnet).

(2) Für jede Teilmenge A ⊆ At(\underline{B}) muss ein b ∈ B gefunden werden mit φ(b) = A. Sei A = {a_{1}, …, a_{k}} und werde b := ∑ A gesetzt. Klar ist φ(b) ⊇ A und es muss φ(b) = A gezeigt werden. Werde im Gegensatz hierzu angenommen, es gäbe ein Element a ∈ φ(b) \ A. Dann ergibt sich:

a = ab = a(a_{1} + … + a_{k}) = aa_{1} + … + aa_{k} = 0 + … + 0 = 0 ⚡

(3) Gelte φ(x) = C, φ(y) = D. Dann gilt x = ∑ D (Lemma!) und

x + y = ∑ C + ∑ D = ∑(C ∪ D) = ∑(φ(x) ∪ φ(y)).

Wie im Beweis von (2) folgt hieraus φ(x + y) = φ(x) ∪ φ(y).

(4) Gelte wieder φ(x) = C, φ(y) = D. Dann besteht C ∩ D genau aus den Atomen unter x und unter y, das heißt unter xy. Nach Definition von φ gilt φ(xy) = C ∩ D (= φ(x) ∩ φ(y)).

(5) Gelte φ(x) = C, φ(x′) = D. Aus x + x′ = 1 folgt, C ∪ D = At(\underline{B}), und aus xx′ = 0 folgt C ∩ D = ∅. Doch das impliziert

D = At(B) \ C = \overline{C} = \overline{φ(x)}
□

Alle endlichen booleschen Algebren sind, nach dem eben Bewiesenen, isomorph zu Potenzmengenalgebren, also sehr einfach strukturiert. Im Gegensatz dazu können unendliche boolesche Algebren ”unendlich kompliziert“ sein!

Die ”praktische“ Bedeutung der 2-elementigen booleschen Algebra

\underline{B}_{2} = (\{0, 1\}; +, ·,′ , 0, 1)

(zum Beispiel für die Konstruktion elektronischer Schaltkreise) liegt sehr stark in den Termoperationen:

2.6.2 Boolsche Terme

Definition: Die Terme in der Sprache (also dem Typ boolescher Algebren) werden auch boolesche Terme genannt.

Beispiele über der Variabenmenge {x_{1}, x_{2}, x_{3}} sind unter anderen:

x_{2} + 1, (x_{2}, x′_{3})′′′, x_{1}x′_{2} + x_{3}, ((x_{1}x′_{2} + x_{3})′x_{1} + x′_{2})

Bekanntlich werden alle Terme, über Algebren des entsprechenden Typs, zu Termfunktionen der Algebra. Die Termfuktionen boolescher Algebren werden oft boolesche Funktionen genannt. Obwohl die 2-elementige boolesche Algebra \underline{B}_{2} äußerst simpel ist, bringt sie interessante praktische und theoretische Sachverhalte. Darum werden hier zuerst boolesche Funktionen über \underline{B}_{2} betrachtet:

Beispiel: Der boolesche Term t(x_{1}, x_{2}, x_{3}) = ((x_{1}x′_{2} +x_{3})′x_{1} +x′_{2})′ liefert eine 3-stellige boolesche Funktion t_{\underline{B}_{2}}(x_{1}, x_{2}, x_{3}) auf \{0, 1\}, mit

t_{\underline{B}_{2}}(0, 0, 0) = 0, t_{\underline{B}_{2}}(0, 0, 1) = 0, t_{\underline{B}_{2}}(0, 1, 0) = 1, t_{\underline{B}_{2}}(0, 1, 1) = 1, usw.

Boolsche Funktionen auf t_{\underline{B}_{2}} liefern alle Operationen auf \{0, 1\}.

Satz: Jede Operation auf {0, 1} ist eine boolesche Funktion.

Anstelle eines Beweises folgt ein Beispiel, aus dem sich der allgemeine Beweis aber ablesen lässt. Es wird gezeigt, dass folgende 3-stellige Operation f(x_{1}, x_{2}, x_{3}) auf {0, 1} eine boolesche Funktion ist:

\begin{matrix}x_{1} & x_{2} & x_{4} & f(x_{1}, x_{2}, x_{3}) \\ 0 & 0 & 0 & 1 → x′_{1}x′_{2}x′_{3} \\ 0 & 0 & 1 & 1 → x′_{1}x′_{2}x_{3} \\ 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 → x_{1}x′_{2}x′_{3} \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 → x_{1}x_{2}x′_{3} \\ 1 & 1 & 1 & 1 → x_{1}x_{2}x_{3} \end{matrix}

Die Produkte rechts in obiger Tabelle werden zu einem booleschen Term summiert:

t(x_{1}, x_{2}, x_{3}) = x′_{1}x′_{2}x′_{3} + x′_{1}x′_{2}x_{3} + x_{1}x′_{2}x′_{3} + x_{1}x_{2}x′_{3} + x_{1}x_{2}x_{3}

Tatsächlich gilt t_{B_{2}}(x_{1}, x_{2}, x_{3}) = f(x_{1}, x_{2}, x_{3}) für alle x_{1}, x_{2}, x_{3} ∈ {0, 1}. Dies könnte man leicht nachrechnen. Es soll hier aber systematisch erklärt werden:

Offenbar gilt t_{B_{2}}(x_{1}, x_{2}, x_{3}) = 1 für x_{1}, x_{2}, x_{3} ∈ {0, 1} genau dann, wenn x_{1}y_{2}y_{3} = 1 gilt für einen der Summanden y_{1}y_{2}y_{3} von t (wobei y_{i} = x_{i} oder y_{i} = x′_{1} gelten kann, für i ∈ {1, 2, 3}). Aber y_{1}y_{2}y_{3} = 1 gilt genau für y_{1} = y_{2} = y_{3} = 1. Betrachtet man, zum Beispiel, den dritten Summanden x_{1}x′_{2}x′_{3}, der die zugehörige Zeile der Wertetabelle darstellt:

1  0  0  1 →  x_{1}  · x_{2} · x_{3}
eins null null \underline{eins}  kein Strich  Strich  Strich
Das Produkt y_{1}y_{2}y_{3} = x_{1}y′_{2}x′_{3} bewirkt t_{\underline{B}_{2}}(1, 0, 0) = 1

Indem man diese Methode anwendet, erhält man immer boolesche Terme in der ”vollständige Summe-von-Produkten“ Form:

• die Bedeutung von ”Summe-von-Produkten“ ist klar,

• ”vollständig“ bedeutet, dass in jedem der Produkte jede der Variablen x_{i} genau einmal vorkommt, entweder als y_{i} = x_{i} oder als y_{i} = x′_{i}.

Der Satz von Seite 84 kann auch so formuliert werden:

Folgerung: Die Operationen +, ·, ′ auf {0, 1} bilden eine vollständige Menge von Operationen, das heißt mit Hilfe von +, ·, ′ können sämtliche Operationen auf {0, 1} ”zusammengebaut“ werden.

Dabei kann entweder + oder · sogar weggelassen werden:

Beobachtung:

(a) Die Menge {·,′ } ist eine vollständige Menge von Operationen auf {0, 1}.

(b) Die Menge {+,′ } ist eine vollständige Menge von Operationen auf {0, 1}.

Beweis: (a) Es genügt zu zeigen, dass + aus · und ′ gebildet werden kann. Doch dies ist einfach, denn bekanntlch gelten folgende Gleichungen:

x + y = (x + y)′′ = (x′ · y′)

(b) Der selbe Beweis mit + und · vertauscht. □

Aber es reicht sogar eine einzige Operation (ohne Beweis):

Beobachtung: Die zweistellige Operation ↑ auf {0, 1} sei definiert durch:

x ↑ y := x′ + y′ Sheffer-Strich

Dann ist {↑} eine vollständige Menge von Operationen auf {0, 1}.

Jeder boolesche Term kann mit Hilfe der definierenden Gleichungen für boolesche Algebren in eine Standardform gebracht werden, nämlich in die disjunkte Normalform (DNF). Es folgt ein Beispiel. Da man nach jeder Umformung einen anderen Term erhält, wird – wie bei Gleichungen – ≡ statt = geschrieben:

t(x_{1}, x_{2}, x_{3}) = ((x_{1}x′_{2} + x_{3})′x_{1} + x′_{2})′
≡ ((x_{1}x′_{2} + x_{3})′x_{1})′x_{2}
≡ ((x_{1}x′_{2} + x_{3}) + x′_{1})x_{2}
≡ (x_{1}x′_{2} + x_{3})x_{2} + x′_{1}x_{2}
≡ x_{1}x′_{2}x_{2} + x_{3}x_{2} + x′_{1}x_{2}
≡ x_{2}x_{3} + x′_{1}x_{2}
≡ (x_{1} + x′_{1})x_{2}x_{3} + x′_{1}x_{2}(x_{3} + x′_{3})
≡ x_{1}x_{2}x_{3} + x′_{1}x_{2}x_{3} + x′_{1}x_{2}x_{3} + x′_{1}x_{2}x′_{3}

Das selbe kann mit jedem booleschen Term gemacht werden:

Feststellung: Zu jedem booleschen Term gibt es eine disjunkte Normalform, die bis auf die Reihenfolge der Summanden und bis auf die Reihenfolge der Faktoren in jedem Summand eindeutig bestimmt ist.

Als nächstes wird folgende Frage beantwortet: Welches sind die Gleichungen, die in jeder booleschen Algebra gelten? Dies kann auf verblüffend einfache Weise beantwortet werden:

Satz: Für beliebige boolesche Terme s(x_{1}, …, x_{n}) und t(x_{1}, …, x_{n}) sind folgende Aussagen äquivalent:

(i) Die Gleichung s(x_{1}, …, x_{n}) ≡ t(x_{1}, …, x_{n}) gilt in allen booleschen Algebren,

(ii) Die Gleichung s(x_{1}, …, x_{n}) ≡ t(x_{1}, …, x_{n}) gilt in der 2-elementigen booleschen Algebra \underline{B}_{2},

(iii) s(x_{1}, … x_{n}) und t(x_{1}, …, x_{n}) haben dieselbe disjunkte Normalform.

Beweis: (i) ⇒ (ii) ist offensichtlich. (ii) ⇒ (iii): Die Gültigkeit von s ≡ t in \underline{B}_{2} bedeutet s_{\underline{B}_{2}} = t_{\underline{B}_{2}} für die zugehörigen booleschen Funktionen. Aber das ist nur möglich, falls s und t die selbe disjunkte Normalform haben. (iii) ⇒ (i): Sei d die disjunkte Normalform von s und t. Dann gelten in allen booleschen Algebren die Gleichungen s ≡ d und t ≡ d woraus sofort die Gültigkeit von s ≡ t folgt.

3 Logik

Die boolesche Algebra, besonders die sehr einfache 2-elementige boolesche Algebra, spielt eine fundamentale Rolle in der Logik. Da diese Vorlesung ihrem Ende entgegen geht, wird die Logik hier nur sehr knapp und Oberflächlich behandelt.

Jetzt folgt ein einführender Abschnitt mit aussagenlogischen Beispielen, dann ein Abschnitt zur Systematik der Aussagenlogik, und schließlich ein Abschnitt, in dem die Prädikatenlogik in Form eines Beispiels vorgestellt wird.

3.1 Aussagenlogik und boolesche Algebra

In der Mitte des 19. Jahrhunderts entwickelte der britische Mathematiker G. Boole ein Kalkül für die ”Gesetze des Denkens“ und schuf damit gleichermaßen die später nach ihm benannte boolesche Algebra wie auch die Aussagenlogik. Diese beschäftigt sich nicht mit inhaltlichen Aspekten irgend welcher Aussagen, sondern nur mit den Konsequenzen, die es hat, wenn eine Aussage ”wahr“ oder ”falsch“ ist: Konsequenzen für andere Aussaugen, die auch ”wahr“ oder ”falsch“ sein können!

Es gibt folgende aussagenlogische Gundoperationen, mit denen aus vorhandenen Aussaugen (zum Beispiel A oder B) neue Aussagen zusammengesetzt werden können:

A ∨ B ”A oder B“ wahr genau dann, wenn mindestens eine der Aussa-

gen A und B war ist,

A ∧ B ”A und B“ wahr genau dann, wenn A und B beide wahr sind,
¬A  ”nicht A“  wahr genau dann, wenn A falsch ist.

Setzt man 1 für ”wahr“ und 0 für ”falsch“, so ergeben sich folgende Wahrheitswerttabellen:

\begin{matrix}A & B & A ∨ B & A ∧ B \\ 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 \end{matrix}  \begin{matrix}A & ¬A \\ 0 & 1 \\ 1 & 0 \end{matrix}

Mit den Wahrheitswerten von Aussagen wird also wie in der 2-elementigen booleschen Algebra gerechnet, wobei aber in der Regel ∨, ∧, ¬ verwendet wird anstelle von +, ·, ′. Es werden noch weitere, zusammengesetzte Operationen verwendet, zum Beispiel:

A → B ”wenn A dann B“ wahr genau dann, wenn A falsch oder B wahr ist.

Die Aussage A → B kann als Abkürzung für ¬A ∨ B aufgefaßt werden (denn beide Aussagen haben die selben Warheitswerte).

Beispiel: Mit den Aussagen

A: die Katze schreit, B: der Mond scheint

hat A → B den Wahrheitswert 1, außer A ist ”wahr“ und B ist ”falsch“. Man beachte: Auf einen ”inneren“ Zusammenhang zwischen A und B kommt es nicht an!

Genau genommen werden häufig keine Aussagen betrachtet, sondern Aussageformen, das heißt boolesche Terme (aber üblicherweise mit ∨, ∧, ¬ geschrieben). Erst indem man für die Variablen Aussagen einsetzt, wird aus der Aussageform selbst eine Aussage. Und eine Wahrheitswerttabelle kann nie für eine konkrete Aussage, sondern nur für eine Aussageform aufgestellt wrden. es handelt sich um die Wertetabelle der zugehörigen booleschen Funktion.

Es werden folgende Bezeichnungen verwendet: zwei Aussageformen s und t heissen äquivalent, in Zeichen s ≡ t, falls f_{\underline{B}_{2}} = t_{\underline{B}_{2}} gilt. (das heißt falls wi dieselben Wahrheitswerrabellen haben). Oft sucht man zu einer Aussageform eine äquivalente Aussageform, die einfacher aufgebaut ist:

Beispiel: Im Reisebüro schildert ein Kunde seine Wünsche für eine Urlaubsreise: ”Wenn der Urlaubsort am Meer liegt, dann dürfen keine Berge in der Nähe sein. An einem Urlaubsort ohne Meer und ohne Berge muss sich ein Schwimmbad befinden. Und wenn es dort kein Meer und kein Schwimmbad gibt, dann geht es nicht ohne Berge!“. Zuerst ist der Angestellte des Reisebüros verwirrt. Doch dann gelingt es ihm, die Aussagen des Kunden zu vereinfachen. Aus erstes ordnet er den Eigenschaften des Urlaubsortes Variablen zu:

am Meer – x, mit Bergen – y, Schwimmbad – z

Die Urlaubswünsche des Kunden ergeben folgende Aussageform, die anschließend umgeformt wird:

(x → ¬y) ∧ ((¬x ∧ ¬y) → z) ∧ ((¬x ∧ ¬z) → y)
≡ (x ∨ ¬y) ∧ ((¬x ∧ ¬y) ∨ z) ∧ ((¬x ∧ ¬z) ∨ y)
≡ ¬(x ∨ y) ∧ (x ∨ y ∨ z)

Jetzt weiß der Angestellte: der Kunde möchte mindestens eine der Eigenschaften ”Meer“, ”Berge“ oder ”Schwimmbad“, aber nicht ”Meer“ und ”Berge“ gemeinsam.

3.2 Aussagenlogik: Elementare Grundbegriffe

Jetzt wird die Aussagenlogik etwas systematischer angegangen. Die Basis bildet aber immer noch die 2-elementige boolesche Algebra.

3.2.1 Syntax der Aussagenlogik

Definition: Die atomen Formen sind A_{1}, A_{2}, A_{3}, . . .. (Es können natürlich auch andere Großbuchstaben wie A, B, C verwendet werden, weil dies das Schreiben vereinfacht.) Alle Ausdrücke, die durch – eventuell wiederholte – Anwendung folgender Schritte erhalten werden können, heißen Formeln:

(1) Alle atomaren Formeln sind Formeln

(2) Sind F und G Formeln, dann sind auch (F ∨ G) und (F ∧ G) Formeln

(3) Ist F eine Formel, dann ist auch ¬F eine Formel

3.2.2 Semantik der Aussagenlogik

Definition: Die Elemente 0 und 1 heißen Wahrheitswerte. Sei D die Menge atomarer Formeln. Eine Belegung von D ist eine Abbildung α: D ⟶ {0, 1}. Jede soche Abbildung kann auf natürliche Weise zu einer Abbildung α̂: E ⟶ {0, 1} fortgesetzt werden, wobei E die Menge aller mit D gebildeten Formeln sei:

(1) Für jede atomare Formel A ∈ D sei α̂(A) := α(A)

(2) α̂(F ∨ G) := \{ \begin{matrix}1 & falls α̂(F) = 1 oder α̂(G) = 1, \\ 0 & sonst \end{matrix}

(3) α̂(F ∧ G) := \{ \begin{matrix}1 & falls α̂(F) = 1 und α̂(G) = 1, \\ 0 & sonst \end{matrix}

(4) α̂(¬F) := \{ \begin{matrix}1 & falls α̂(F) = 0 \\ 0 & falls α̂(F) = 1 \end{matrix}

Klar ist: Jede Formel F kann als boolesche Funktion aufgefasst werden, und α̂(F) ist ein Wert in der Wahrheitswerttabelle von F. Übrigens wird für α̂(F) im Allgemeinen einfacher α(F) geschrieben.

3.2.3 Modelle, Gültigkeit, Erfüllbarkeit

Definition: Sei F eine Formel und α eine Belegung. Falls α für alle in F vorkommenden atomaren Formeln definiert ist (also falls α(F) definiert ist), dann heißt α zu F passend.

Falls α zu F passend ist und α(F) = 1 gilt, so wird α ⊧ F geschrieben. Man sagt dann: ”F gilt unter α“ oder ”α ist ein Modell für F“. Ist \underline{F} eine Menge von Formeln, dann ist α ein Modell für \underline{F} (oder F gilt unter α), falls α ⊧ \underline{F} gilt, das heißt A ⊧ F für alle F ∈ \underline{F}.

Eine Formel F (bzw. Formelmenge F) heißt erfüllbar, falls α ⊧ F (bzw. α ⊧ \underline{F}) gilt für mindestens eine Belegung α. Andernfalls heißt F (bzw. \underline{F}) unerfüllbar.

Eine Formel F heißt gültig (oder Tautologie), falls jede zu F passende Belegung ein Modell für F ist. Man schreibt ⊧ F, falls F eine Tautologie ist, und #F sonst.

Zum Abschluss dieses Abschnitts eine einfache Aussage:

Satz: Eine Formel F ist genau dann eine Tautologie, wenn ¬F unerfüllbar ist.

Beweis: Offensichtlich sind folgende Aussagen äquivalent:

• F ist eine Tautologie

• jede zu F passende Belegung ist ein Modell für F

• jede zu F, damit auch zu ¬F passende Belegung ist kein Modell für F

• ¬F besitzt kein Modell

• ¬F ist unerfüllbar □

3.3 Prädikatenlogik erster Stufe

Ein wohlbekannter prädikatenlogischer Ausdruck aus der Analysis ist folgender:

∀ε > 0 ∃n_{0} ∈ ℕ ∀n ≥ n_{0} : |f(n) − f(n_{0})| < ε

Dieser Ausdruck hat als Bestandteile: die Quantoren ∀ und ∃, die Funktionen (= Operationen) | · |, f, − sowie die Relationen >, ≥, <.

Zuerst wird der syntaktische Sprachrahmen abgesteckt:

3.3.1 Syntax der Prädikatenlogik

Definition: Es werden die Variablen x_{1}, x_{2}, x_{3}, … verwendet (manchmal auch …, x, y, z), die Prädikatssymbole P_{i}^{k} und die Funktionssymbole f_{i}^{k} (manchmal auch P, Q, R bzw. f, g, h), wobei i nur der Unterscheidung dient (Unterscheidungsindex) und k die Stelligkeit angibt. Was die mit den Funktionssymbolen f_{i}^{k} und den Variablen x_{j} gebildeten Terme sind, ist aus Abschnitt 2.4 klar. Man erhält die Formeln der Prädikatenlogik durch – eventuell mehrfache – Anwendung folgender Regeln:

(1) Für jedes k-stellige Prädikatssymbol P und beliebige Terme t_{1}, …, t_{k} ist P (t_{1}, …, t_{k}) eine Formel

(2) Für jede Formel F ist ¬F eine Formel

(3) Sind F und G Formeln, dann sind auch (F ∨ G) und (F ∧ G) Formeln

(4) Für jede Variable x und jeder Formel F sind auch ∃xF und ∀xF Formeln

Die Formeln in (1) heißen atomare Formeln. Eine Formel F heißt Teilformel einer Formel G, falls F in G vorkommt. Eine Variable x kann in einer Formel gebunden vorkommen (das heißt in der Form ∀xG oder ∃xG) oder frei, das heißt ohne Quantor. Eine Variable kann innerhalb derselben Formel sowohl gebunden als auch frei vorkommen. Eine Formel ohne freie Variablen wird geschlossen (oder eine Aussage) genannt.

Beispiel für eine Formel:

F := (∃x_{1}P_{5}^{2}(x_{1}, f_{2}^{1}(x_{2})) ∨ ¬∀x_{2}P_{4}^{2}(x_{2}, f_{7}^{2}(f_{4}^{0}, f_{5}^{1}(x_{3}))))

In F ist x_{1} überall gebunden, x_{2} ist beim ersten Auftreten frei und sonst gebunden, und x_{3} kommt nur frei vor.

3.3.2 Semantik der Prädikatenlogik, 1. Teil

Eine Struktur ist ein Paar A = (U_{A}, I_{A}), wobei U_{A} eine nicht leere Menge ist (die Grundmenge oder das Universum von A) und I_{A} eine Abbildung, die

• jedem k-stelligen Prädikatssymbol P (welches im Definitionsbereich von I_{A} liegt) ein k-stelliges Prädikat (= Relation) P^{A} auf U_{A} zuordnet,

• jedem k-stelligen Funktionssymbol f (im Definitionsbereich von I_{A}) eine k-stellige Funktion f^{A} auf U_{A} zuordnet,

• jeder Variablen x (im Definitionsbereich von I_{A}) ein Element x^{A} von U_{A} zuordnet.

Eine Struktur A = (U_{A}, I_{A}) heißt zu einer Formel F passend, falls I_{A} für alle in F vorkommenden Prädikatssymbole, Funktionssymbole und freien Variablen definiert ist.

Beispiel: Sei die Formel F := ∀xP (x, f(x)) ∧ Q(g(a, z)) gegeben. Hierin ist P ein zweistelliges und Q ein einstelliges Prädikatssymbol, f ein einstelliges, g ein zweistelliges und a ein nullstelliges Funktionssymbol, sowie x eine gebundene und z eine freie Variable. Eine zu F passende Struktur A = (U_{A}, I_{A}) mit:

U_{A} := ℕ,  P^{A} := {(m, n) ∈ U_{A}^{2} | m < n},  Q^{A} := {n ∈ ℕ | n prim
f^{A}(n) := n + 1,  g^{A}(m, n) := m + n,  a^{A} := 2, z^{A} := 3

In dieser Struktur ”gilt“ F offensichtlich (muss aber erst noch definiert werden). Es gibt aber – ziemlich offensichtlich – zu F passende Strukturen, in denen F nicht gilt.

3.3.3 Semantik der Prädikatenlogik, 2. Teil

Sei F eine zur Struktur A passende Formel. Zuerst wird für jeden aus den Variablen und Funktionssymbolen von F gebildeten Term t der Wert A(t) definiert (induktiv, das heißt über den Aufbau der Terme):

(1) Im Fall t = x (für eine Variable x) sei A(t) := x^{A}.

(2) Im Fall t = f(t_{1}, …, t_{n}) mit einem k-stelligen Funktionssymbol f und Termen t_{1}, …, t_{k} sei A(t) := f^{A}(A(t_{1}), …, A(t_{k})).

Jetzt werden – wieder induktiv – für alle Formeln F die (Wahrheits-)Werte A(F) definiert:

(3) Für F = P (t_{1}, …, t_{k}) mit k-stelligem Prädikatssymbol P und Termen t_{1}, …, t_{k} sei

A(F) := 1 falls (A(t_{1}), …, A(t_{k})) ∈ P^{A}, A(F) := 0 sonst

(4) Für F = ¬G sei

A(F) := 1 falls A(G) = 0, A(F) := 0 sonst

(5) Für F = (G ∨ H) sei

A(F) := 1 falls A(G) = 1 oder A(H) = 1, A(F) := 0 sonst (6) Für F = (G ∧ H) sei

A(F) := 1 falls A(G) = 1 und A(H) = 1, A(F) := 0 sonst

(7) Für F = ∀xG sei

A(F) := 1 falls A_{[x/d]}(G) = 1 für alle d ∈ U_{A}, A(F) := 0 sonst

(8) Für F = ∃xG sei

A(F) := 1 falls A_{[x/d]}(G) = 1 für ein d ∈ U_{A}, A(F) := 0 sonst

Anmerkung zu 7/8: ”A_{[x/d]}“ bedeutet, dass x = d gesetzt wird, unabhängig vom Wert x^{A} (und davon, ob x^{A} definiert ist). Fall A(F) = 1 gilt, wird wieder A ⊧ F geschrieben (”F gilt in A“ oder ”A ist ein Modell für F“). Wenn jede (zu F passende) Struktur ein Modell für F ist, heißt F (allgemein-)gültig: ⊧ F, andernfalls: #F. Falls es mindestens ein Modell für F gibt, heißt F erfüllbar, sonst unerfüllbar.

Schlussbemerkung: (a) Prädikatenlogik ”enthält“ die Aussagenlogik: Man nimmt nur 0-stellige Prädikatssymbole (und keine Terme, Variablen und Quantoren).

(b) Die hier angedeutete ”Prädikatenlogik erster Stufe“ erlaubt keine Quantifizierung über Prädikats- und Funktionssymbole, dies ist in der ”Prädikatenlogik zweiter Stufe“ erlaubt!

Ende!

Abbildungsverzeichnis

1 Liniendiagramm . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 2 Pfeildiagramm von f . . . . . . . . . . . . . . . . . . . . . . . . . 4 3 Injektivität, Surjektivität, Bijektivität . . . . . . . . . . . . . . . 5 4 Kreuztabelle von R . . . . . . . . . . . . . . . . . . . . . . . . . . 7 5 Das Pascal’sche Dreieck . . . . . . . . . . . . . . . . . . . . . . . 11 6 Turniergraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 7 Beispiele für Graphen . . . . . . . . . . . . . . . . . . . . . . . . 20 8 Weitere Graphentypen . . . . . . . . . . . . . . . . . . . . . . . . 20 9 Graphenisomorphie I . . . . . . . . . . . . . . . . . . . . . . . . . 20 10 Graphenisomorphie II . . . . . . . . . . . . . . . . . . . . . . . . 21 11 Zusammenhängende Graphen . . . . . . . . . . . . . . . . . . . . 23 12 Bäume mit 6 Ecken . . . . . . . . . . . . . . . . . . . . . . . . . . 23 13 Wald . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 14 Wurzelbäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 15 Binärbäume . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 16 Telefonbuch I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 17 Telefonbuch II . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 18 Kantenzüge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 19 Breitensuche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 20 Inzidenzmatrix von G . . . . . . . . . . . . . . . . . . . . . . . . 28 21 Wege in ungerichteten Graphen . . . . . . . . . . . . . . . . . . . 29 22 Algorithmus von Dijkstra . . . . . . . . . . . . . . . . . . . . . . 31 23 Flussnetzwerke . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 24 Zunehmender Weg . . . . . . . . . . . . . . . . . . . . . . . . . . 33 25 Minimaler Kantenschnitt . . . . . . . . . . . . . . . . . . . . . . 33 26 Markierungsalgorithmus . . . . . . . . . . . . . . . . . . . . . . . 36 27 Petersengraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 28 Graphenautomorphismen . . . . . . . . . . . . . . . . . . . . . . 41 29 Würfelgraph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 30 Die Pólyasche Abzählmethode . . . . . . . . . . . . . . . . . . . . 43 31 Liniendiagramm des Verbandes (L, ≤) . . . . . . . . . . . . . . . 62 32 Liniendiagramm des Verbandes (A, ≤) . . . . . . . . . . . . . . . 62 33 Direktes Produkt von Verbänden. . . . . . . . . . . . . . . . . . . 65 34 Liniendiagramm von (Eq(A), ⊆ ) . . . . . . . . . . . . . . . . . . 66 35 Homomorphiesatz . . . . . . . . . . . . . . . . . . . . . . . . . . 73 36 Homomorphiesatz (Beispiel) . . . . . . . . . . . . . . . . . . . . . 74 37 Liniendiagramm einer 8-elementigen boolesche Algebra) . . . . . 82 38 Atome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

Index

Ähnlichkeitstyp, 55 Äquivalenzbeweis, 16 Äquivalenzklasse, 3, 23 Äquivalenzrelation, 23 Äquivalenzrelation, Klassen, 3 Äquivalenzrelation, Parition, 3 Äquivalenzrelationen, 2

Abbildung, 4 Abelsche Gruppe, 37 Abzählprinzipien, 6 Abzählprinzipien, doppelte, 7 Additionsprinzip, 6 Adjazenzlisten, 27 Algebra, 55 Algebra, boolesche, 80 Algebra, frei erzeugte, 78 Algebraische Strukturen, 49 Algebren, Unteralgebra, 56 Algorithmus, Dijkstra, 30 Algorithmus, Ford-Fulkerson, 35 Algorithmus, Markierungs-, 35 Algorithmus, Moore, 27 Allgemeine Algebra, 55 Allquantor, 4 Alphabet, 50 Atom, 82 Augmenting Path Theorem, 34 Aussagen, 14 Automorphismengruppe, 41 Automorphismus, 41

Bögen, 19 Bücher, I Bahn, 39 Basis, 54 Basis, kanonische, 54 Baum, 23 Baum, binärer, 25 Baum, Tiefe, 25 Baum, Wurzel-, 24 Behauptung, 14 Beweis, Äquivalenz, 16 Beweis, direkter, 14 Beweis, Fallunterscheidung, 16 Beweis, Induktion, 16 Beweis, Kontraposition, 15 Beweis, Widerspruch, 15 Beweismethoden, 14 BFS, breadth first search, 27 Bijektivität, 5 Bild, 4 Binärer Baum, 25 Binomialkoeffizienten, 8 Binomialrekursion, 10 Blatt, 25 Boolesche Algebra, 80 Boolsche Terme, 84

Das Cauchy-Frabenius-Lemma, 44 Definitionsbereich, 4 Diedergruppe, 43 Digraph, 29 Dijkstra, 30 Dimension, 54 Direkter Beweis, 14 Direktes Produkt, 1 Diskrete Mathematik, 19 Doppelte Abzählung, 7

Ecken, 19

Erzeugende Funktion, 47 Erzeugungsprozess, 57 Existenzquantor, 4

Fallunterscheidung, 16 Fibbonacci-Zahlen, 18 Fluss, 31 Fluss, maximaler, 32 Ford-Fulkerson, 35 Frei erzeugte Algebra, 78 Funktion, 4

gerichteter Graph, 29 Gleichheitsprinzip, 7 Gleichheitsrelation, 2 Gleichungen, 77 Gleichungslogik, Vollständigkeit, 80 Gleichungssystem, 77 Gleichungstheorie, 77 Gleichungstheorie, Hauptsätze, 79 Grad einer Permutationsgruppe, 39 Grad von Knoten, 21 Graph, 19 Graph, gerichtet, 29 Graph, zusammenhängend, 23 Graphenisomorphie, 20 Grundmenge, 55 Gruppe, 37 Gruppe, abelsche, 37 Gruppe, kommutative, 37

Hüllen, 58 Hüllenoperator, 58 Hüllensystem, 58 Hasse-Diagramm, 3 Hauptsätze Gleichungstheorie, 79 Homomorphiesatz, 73 Homomorphismus, Algebren, 70 Hypothese, 14

Induktionsbasis, 16 Induktionssatz, 17 Induktionsschritt, 16 Induktive Definition, 18 Induktives Mengensystem, 59 Infix-Schreibweise, 49 Injektivität, 5 Inzidenzmatrix, 28 Isomorphismus, 20 Isomorphismus, Algebren, 70

kanonische Basis, 54 Kanten, 19 Kantenzug, 22, 26 Kardinalität, 6 Kartesisches Produkt, 1 Knoten, 19 Knotengrad, 21 Kommutative Gruppe, 37 Kongruenzrelation, 65 Kontraposition, 15 Kreis, 22

Länge eines Kantenzugs, 26 Lagrange, 38 Linien, 19 Liniendiagramm, 3 Linksnebenklasse, 38 Literatur, I

Markierungsalgorithmus, 35 Max-Flow Min-Cut Theorem, 34 maximaler Fluss, 32 Menge, Ordnung, 38 Mengen, Kardinalität, 6 Mengen, Potenz, 1 Mengen, Produkt, 1 Mengen, Schnitt, 1 Mengen, verbandsgeordnete, 61 Mengen, Vereinigung, 1 Mengenlehre, 1 Mengensystem, 58 Mengensystem, induktiv, 59 Minimaler Schnitt, 34 Modell, 77 Moore, 27 Multimengen, 12 Multiplikationsprinzip, 7

Nachbar, 82 Netzwerk, 29 Netzwerk, Fluss, 31

Operation, 49 Operationen, 55 Orbit, 39 Ordnungsrelation, 2, 3 Ordung einer Menge, 38

Pólyasche Abzählmethode, 43 Parition, 3 Pascal’sches Dreieck, 10 Permutation, 12 Permutationsgruppe, 43 Permutationsgruppe, Grad, 39 Permutationstyp, 45 Petersengraph, 41 Pfeildiagramm, 4 Polynom, 76 Polynomfunktion, 76 Potenzmenge, 1, 8 Potenzmengenalgebra, 82 Produkt, direktes, 1 Produkt, kartesisches, 1 Produktmenge, 1 Projektionsabbildung, 75 Punkte, 19

Quelle, 31

Rechtsnebenklasse, 38 Rekursion, 10, 18 Relationen, 2 Relationen, Äquivalenz-, 2 Relationen, binäre, 2 Relationen, Gleichheits-, 2 Relationen, Kongruenz-, 65 Relationen, Ordnungs-, 2 Ring, 52 Ring, kommutativer, 52 Ring, unitärer, 52 Russel’sches Paradoxon, 5

Satz von Pólya, 48 Schnitt, minimaler, 34 Schnitt, trennender, 34 Schnittmenge, 1 Senke, 31 Skalarmultiplikation, 54 Spaltenvektoren, 54 Stabilisator, 39 Standuntergruppe, 39 Stelligkeit, 55 Strukturen, algebraische, 49 Superposition, 75 Surjektivität, 5 Symmetriengruppe, 43

Teilgraph, 23 Teilmengen, 8 Term, 74 Termalgebra, 74 Terme, boolesche, 84 Termfunktion, 75 Tiefe von Bäumen, 25 Trennender Schnitt, 34 Tupel, 1 Typ, 55

Unteralgebra, 56 Untergraph, 23 Untergruppe, 38 Untergruppe, zyklische, 38 Urbild, 4

Vandermondesche Gleichung, 11 Variable, 74 Vektorraum, 54 Verband, 60 Verband, geordneter, 61 Verbandsgeordnete Menge, 61 Vereinigunsmenge, 1 Verkettung, 50 Voll-invariant, 79 Vollständige Induktion, 11, 16 Vollständiger Graph, 41 Vollständigkeitssatz, 80 Vorbemerkungen, I

Wahrheitstafel, 14

Wald, 24 Weg, 22 Wertebereich, 4 Wertetabelle, 4 Widerspruchsbeweis, 15 Wurzelbaum, 24

zunehmender Weg, 33

Zusammenhängender Graph, 23 Zyklenzeiger, 47 Zyklische Untergruppe, 38