Grundlagen der Diskreten Mathematik und Algebra 1hebisch/skripte/diskmath/diskmath.pdf · Grundlagen der Diskreten Mathematik und Algebra 1 Prof. Udo Hebisch WS 2010/11 Dieses Skript

Grundlagen der Diskreten Mathematik undAlgebra 1

Prof. Udo Hebisch

WS 2010/11

Dieses Skript enthalt nur den “roten Faden”der Vorlesung. Wesentliche Inhalte werden ausschließlich

in der Vorlesung vermittelt. Daher ist diesesSkript nicht zum Selbststudium gedacht, sondern

nur als “Erinnerungsstutze”.

1

INHALTSVERZEICHNIS 2

Inhaltsverzeichnis

1 Aussagen und Mengen 3

1.1 Aussagenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

1.2 Pradikatenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.3 Mengenbildung und Mengenalgebra . . . . . . . . . . . . . . . . . 15

1.4 Relationen und Abbildungen . . . . . . . . . . . . . . . . . . . . . 27

1.4.1 Kartesische Produkte . . . . . . . . . . . . . . . . . . . . . 27

1.4.2 Korrespondenzen und Relationen . . . . . . . . . . . . . . 29

1.4.3 Aquivalenz- und Ordnungsrelationen . . . . . . . . . . . . 34

1.4.4 Abbildungen . . . . . . . . . . . . . . . . . . . . . . . . . . 44

1.4.5 Kardinalzahlen . . . . . . . . . . . . . . . . . . . . . . . . 48

1.4.6 Verknupfungen . . . . . . . . . . . . . . . . . . . . . . . . 53

1.5 Verallgemeinerte mengentheoretische Operationen . . . . . . . . . 56

2 Gruppen, Ringe, Korper 59

2.1 Gruppen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

2.1.1 Elementare Eigenschaften . . . . . . . . . . . . . . . . . . 59

2.1.2 Untergruppen und Homomorphie . . . . . . . . . . . . . . 65

2.1.3 Permutationsgruppen . . . . . . . . . . . . . . . . . . . . . 73

2.2 Ringe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

2.3 Korper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

3 Aufgaben 86

Vorherige Seite Nachste Seite Zuruck Erste Seite Letzte Seite

1 Aussagen und Mengen 3

1 Aussagen und Mengen

Weiterfuhrende Informationen zu den Inhalten dieses Kapitels findet man unter

www.mathecafe.de/logik/

1.1 Aussagenlogik

In diesem Abschnitt werden hauptsachlich fur veranschaulichende BeispieleKenntnisse aus der elementaren Arithmetik vorausgesetzt, also Vertrautheit mitden Rechengesetzen in den naturlichen Zahlen N0, den ganzen Zahlen Z und denrationalen Zahlen Q.

Eine ausfuhrlichere Behandlung dieser Zahlenbereiche und ihrer Rechengesetzefindet man in dem Skript zur Zahlentheorie

www.mathe.tu-freiberg.de/∼hebisch/skripte/zahlenth/zahlenth.pdf

Unter einer “Aussage” versteht man in der Mathematik einen in einer naturli-chen oder formalen Sprache formulierten Satz, fur den eindeutig festgestellt wer-den kann, ob er in einer gewissen “realen Welt” wahr oder falsch ist. TypischeAussagen (aus der “Welt der naturlichen Zahlen”) sind etwa

A: 3 ist eine Primzahl.

B: 9 ist keine Primzahl.

C: 2 teilt 9 (als Formel: 2 | 9).

D: Es gibt unendlich viele Primzahlen.

E: Es gibt unendlich viele Primzahlzwillinge.

Die Wahrheit oder Falschheit von A, B und C kann dabei sehr schnell bestimmtwerden, sobald die in den Aussagen auftretenden Begriffe “Primzahl” und “teilt”geklart sind. Dagegen ist es erheblich schwieriger, die Wahrheit von D festzustel-len, wenn der Begriff “unendlich” prazisiert worden ist, was fur sich genommenschon schwierig genug ist und hier in Definition 1.30 geschieht.

E wird ebenfalls als Aussage betrachtet, obwohl bis heute noch niemand entschei-den konnte, ob dieser Satz wahr oder falsch ist.


http://www.mathecafe.de/logik/index.html

http://www.mathe.tu-freiberg.de/~hebisch/skripte/zahlenth/zahlenth.pdf

1.1 Aussagenlogik 4

Dagegen betrachtet man ublicherweise umgangssprachlich ebenfalls durchaussinnvolle Satze wie “3 ist keine wertvolle Primzahl.” oder “Primzahlen sindschon.” nicht als Aussagen.

Man kann nun “elementare” Aussagen zu komplizierteren zusammensetzen, diedann ebenfalls stets wahr oder falsch sind, z. B. “Wenn 2 die 9 teilt, dann ist9 keine Primzahl” kurz: “wenn C, dann B”, was eine wahre Aussage ist. DieseIdeen werden nun formalisiert.

Definition 1.1 Es sei B = {0,1} die Menge der Booleschen Wahrheitswerte(George Boole, 1815 - 1864). Weiterhin sei V = {A,B,C, . . .} eine Menge von(Aussagen-)Variablen (lat. varius = vielfaltig). Dann werden die aussagenlogi-schen Formeln wie folgt erklart:

(1) Jeder der Wahrheitswerte und jede Variable ist eine aussagenlogische For-mel. Sie werden atomare Formeln oder kurz Atome (grch. atomos = unteilbar)genannt.

(2) Sind p und q aussagenlogische Formeln, dann auch

(¬p), (p ∧ q), (p ∨ q), (p→ q), (p↔ q).

(3) Nur die durch wiederholte Anwendung von (1) und (2) definierten Zeichenket-ten sind aussagenlogische Formeln. Die Gesamtheit aller so definierten Formelnwerde mit F = F(V) bezeichnet

Bemerkung 1.2 a) Da es genau zwei Wahrheitswerte gibt, handelt es sich beider hier betrachteten klassischen Aussagenlogik um eine zweiwertige Logik (grch.logos = Lehre, Aussage). Entsprechend kann man mehrwertige Logiken definie-ren. Man interpretiert den Wahrheitswert 1 als “wahr” und entsprechend 0 als“falsch”. Daher kommen in der Literatur auch andere Bezeichnungen vor: “W”oder “T” oder “true” oder “>” anstelle von 1 und “F” oder “false” oder “⊥”anstelle von 0.

b) Die Menge der Variablen wird als abzahlbar unendlich (in einem spater nochzu prazisierenden Sinn) vorausgesetzt, so daß man immer “genugend” viele Varia-blen zur freien Verfugung hat, aber andererseits sie auch durchnumerieren kann.Man schreibt daher auch oft V = {v0, v1, v2, . . .} oder V = {x0, x1, x2, . . .}. ZurVermeidung von Indizes sind aber die hier und in der Literatur haufig verwende-ten Großbuchstaben bequemer. Jede Variable kann jeweils mit genau einem derWahrheitswerte belegt werden. (Auch dies werden wir spater praziser ausdruckenkonnen, indem wir Variablenbelegungen als Abbildungen val : V → B definieren.)


http://de.wikipedia.org/wiki/George_Boole

1.1 Aussagenlogik 5

c) Die aussagenlogischen Formeln sind rekursiv (lat. recurrere = zurucklaufen)definiert. Jede nicht atomare Formel besitzt einen eindeutigen Aufbau aus kurze-ren Bestandteilen, die selbst wieder Formeln sind. Man kann daher Aussagen ubersamtliche Formeln durch Induktion uber diesen Aufbau beweisen oder Eigenschaf-ten fur Formeln induktiv definieren. Insbesondere kann durch programmierbareVerfahren (Algorithmen) entschieden werden, ob eine vorgelegte Zeichenkette, dieausschließlich aus Variablen, Klammern und Junktoren gebildet wurde, zu F(V)gehort oder nicht.

d) Die Symbole ¬, ∧, ∨, → und ↔ werden logische Junktoren (lat. iungere = ver-binden) genannt und der Reihe nach “nicht”, “und”, “oder”, “wenn..., dann...”sowie “genau dann..., wenn...” gelesen. Ihre exakte Bedeutung wird gleich defi-niert. Man nennt ¬p die Negation (lat. negare = verneinen), p∧q die Konjunktion(lat. coniungere = miteinander verbinden), p ∨ q die Disjunktion (lat. disiungere= trennen, unterscheiden), p → q die Implikation (lat. implicare = einwickeln)oder Subjunktion (lat. subiungere = unterordnen) und p↔ q die Aquivalenz (lat.aequus = gleich, valere = bewerten) der Formeln p und q. In der Literatur werdenauch andere Symbole fur diese Junktoren verwendet, beispielsweise “∼ A” oder“A” fur “¬A”, “&” oder “·” fur “∧”, “+” fur “∨”, “⊃” oder “⇒” fur “→”, “⇔”oder “≡” fur “↔”.

e) Zur Erleichterung der Lesbarkeit und Vermeidung “uberflussiger” Klammernlegt man fest, daß die außeren Klammern stets weggelassen werden durfen undder in d) jeweils weiter links stehende Junktor “starker bindet” als der rechtsstehende. Man schreibt also beispielsweise A∧¬A→ B anstelle von ((A∧(¬A)) →B).

Eine ausfuhrliche Diskussion weiterer moglicher Junktoren und ihre Bezeichnun-gen in der Literatur findet man unter

www.mathecafe.de/logik/booleschefunktionen.html

Aufgabe 1.3 Man versuche, den Begriff “arithmetischer Term”, der in fast je-der Programmiersprache verwendet wird, in ahnlicher Weise wie in Definition 1.1formal zu prazisieren, damit durch ein automatisches Verfahren uberpruft wer-den kann, ob eine vorgelegte Zeichenkette ein korrekter Term ist. Dabei konnenarithmetische Variablen x, y, z, . . . verwendet werden, die jetzt reelle (oder bei-spielsweise auch nur ganzzahlige) Werte annehmen durfen, und bestimmte arith-metische Operatoren wie +,−, ∗, /,max,min. Man nimmt dann diese speziellenSymbole mit einer ganz festen Bedeutung in die Signatur mit auf.

Wie konnte man diese Definition erweitern, wenn auch Vergleiche zwischen Ter-men mit den Vergleichsoperatoren =, 6=, <,≤, >,≥ zugelassen werden sollen?


http://www.mathecafe.de/logik/booleschefunktionen.html

1.1 Aussagenlogik 6

Definition 1.4 Die Verknupfung der Wahrheitswerte von belegten Aussagen-variablen A und B bei Verwendung der jeweiligen Junktoren wird durch diefolgenden Wahrheitswertetafeln festgelegt.

A ¬A0 11 0

A B A ∧B A ∨B A→ B A↔ B0 0 0 0 1 10 1 0 1 1 01 0 0 1 0 01 1 1 1 1 1

Wird also jede Variable mit einem festen Wahrheitswert belegt, dann wird durchRekursion auch jeder aussagenlogischen Formel eindeutig ein Wahrheitswert zu-geordnet.

Beispiel 1.5 In diesem Beispiel beachte man bei der Uberprufung der angege-benen Werte besonders die getroffenen Klammerkonventionen.

A B A ∧ ¬A A ∨ ¬A ¬B → ¬A ¬A ∨B ¬(A→ B)0 0 0 1 1 1 00 1 0 1 1 1 01 0 0 1 0 0 11 1 0 1 1 1 0

Definition 1.6 Zwei aussagenlogische Formeln p und q heißen gleichwertig oder(semantisch) aquivalent, in Zeichen p ≡ q, wenn beide bei jeder Belegung der (inihnen vorkommenden) Variablen denselben Wahrheitswert besitzen.

Eine aussagenlogische Formel p heißt allgemeingultig oder eine Tautologie (grch.tautologia = dasselbe sagend), wenn p ≡ 1 gilt. Dagegen spricht man bei p ≡ 0von einer widerspruchlichen Formel oder einer Kontradiktion (lat. contra = gegen,dicere = sagen, sprechen). Eine nicht widerspruchliche Formel heißt erfullbar.

Aufgabe 1.7 Wie wurde man entsprechend die “Termaquivalenz” fur Terme ausAufgabe 1.3 definieren?

Durch Aufstellen der entsprechenden Wahrheitswertetafeln beweist man den fol-genden Hilfssatz. Diese und weitere Aquivalenzen werden diskutiert auf


1.1 Aussagenlogik 7

www.mathecafe.de/logik/formelaequivalenz.html

Lemma 1.8 Fur aussagenlogische Formeln x gelten die folgenden Aquivalenzen

¬0 ≡ 1,(1)

¬1 ≡ 0,(2)

¬(¬x) ≡ x,(3)

x ∧ ¬x ≡ 0,(4)

x ∨ ¬x ≡ 1,(5)

x↔ ¬x ≡ 0,(6)

0 ∧ x ≡ 0,(7)

1 ∧ x ≡ x,(8)

0 ∨ x ≡ x,(9)

1 ∨ x ≡ 1,(10)

0 → x ≡ 1,(11)

1 → x ≡ x,(12)

x→ 0 ≡ ¬x,(13)

x→ 1 ≡ 1,(14)

x→ x ≡ 1,(15)

x↔ 0 ≡ ¬x,(16)

x↔ 1 ≡ x.(17)

Beweis:

x 0 1 ¬x ¬0 ¬1 ¬(¬x) x ∧ ¬x x ∨ ¬x x↔ ¬x0 0 1 1 1 0 0 0 1 01 0 1 0 1 0 1 0 1 0

x 0 1 ¬x 0 ∧ x 1 ∧ x 0 ∨ x 1 ∨ x 0 → x 1 → x0 0 1 1 0 0 0 1 1 01 0 1 0 0 1 1 1 1 1

x 0 1 ¬x x→ 0 x→ 1 x→ x x↔ 0 x↔ 10 0 1 1 1 1 1 1 01 0 1 0 0 1 1 0 1

�


http://www.mathecafe.de/logik/formelaequivalenz.html

1.1 Aussagenlogik 8

Bemerkung 1.9 Aufgrund der Definition des Junktors ↔ und der Aquivalenz≡ von Formeln gilt p ≡ q genau dann, wenn p↔ q eine Tautologie ist.

Aus (1) und (2) folgt insbesondere, daß die Tautologien gerade die Negationender Widerspruche sind und umgekehrt.

Die Formel (3) beschreibt die “doppelte Verneinung”, welche wieder die ursprung-liche Aussage ergibt.

Die Formel (5) ist auch als “tertium non datur” bekannt: Jede Aussage kann nurwahr oder falsch sein, eine dritte Moglichkeit gibt es nicht. (Dies liegt naturlichan der vorausgesetzten Zweiwertigkeit der Logik!)

Die Formel (11) zeigt, daß aus einem Widerspruch jede beliebige Aussage folgt:“ex contradictione quodlibet” oder kurzer aber nicht ganz korrekt “ex falso quod-libet”.

Die Formel (13) begrundet das Prinzip des Widerspruchsbeweises: Wenn aus einer(als wahr angenommenen) Aussage ein Widerspruch gefolgert werden kann, mußdiese Aussage falsch sein, “tertium non datur”.

Die Formel (15) beschreibt die “Selbstimplikation”, also jede Formel impliziertsich selbst.

Satz 1.10 Fur aussagenlogische Formeln x, y, z gelten die folgenden Aquivalen-zen

x ∧ x ≡ x,(18)

x ∨ x ≡ x,(19)

x ∧ y ≡ y ∧ x,(20)

x ∨ y ≡ y ∨ x,(21)

x↔ y ≡ y ↔ x,(22)

x ∧ (y ∧ z) ≡ (x ∧ y) ∧ z,(23)

x ∨ (y ∨ z) ≡ (x ∨ y) ∨ z,(24)

x↔ (y ↔ z) ≡ (x↔ y) ↔ z,(25)

x ∧ (x ∨ y) ≡ x,(26)

x ∨ (x ∧ y) ≡ x,(27)

x→ (x→ y) ≡ x→ y,(28)

x ∧ (y ∨ z) ≡ (x ∧ y) ∨ (x ∧ z),(29)

x ∨ (y ∧ z) ≡ (x ∨ y) ∧ (x ∨ z),(30)


1.1 Aussagenlogik 9

x→ (y ∧ z) ≡ (x→ y) ∧ (x→ z),(31)

x→ (y ∨ z) ≡ (x→ y) ∨ (x→ z),(32)

x ∧ y → z ≡ (x→ z) ∨ (x→ z),(33)

x ∨ y → z ≡ (x→ z) ∧ (x→ z),(34)

¬(x ∧ y) ≡ ¬x ∨ ¬y,(35)

¬(x ∨ y) ≡ ¬x ∧ ¬y,(36)

¬(x→ y) ≡ x ∧ ¬y,(37)

¬(x↔ y) ≡ ¬x↔ y,(38)

(x ∧ ¬y) ∨ (y ∧ ¬x) ≡ (x ∨ y) ∧ ¬(x ∧ y).(39)

Beweis: Ubungsaufgabe! �

Bemerkung 1.11 Die Aquivalenzen (35) und (36) werden auch De MorganscheRegeln genannt, nach Augustus de Morgan (1806 - 1871).

Folgerung 1.12 Fur aussagenlogische Formeln x, y gelten die folgenden Aqui-valenzen

x↔ y ≡ (x→ y) ∧ (y → x),(40)

x→ y ≡ ¬x ∨ y,(41)

x ∨ y ≡ ¬(¬x ∧ ¬y),(42)

x ∧ y ≡ ¬(¬x ∨ ¬y).(43)

Beweis: (40) ergibt sich aus der folgenden Wahrheitswertetafel:

x y x↔ y x→ y y → x (x→ y) ∧ (y → x)0 0 1 1 1 10 1 0 1 0 01 0 0 0 1 01 1 1 1 1 1

(41) folgt aus (37) mittels (35) und doppelter Verneinung (3).

(42) und (43) folgen aus (36) bzw. (35) ebenfalls durch doppelte Verneinung. �


http://de.wikipedia.org/wiki/Augustus_De_Morgan

1.1 Aussagenlogik 10

Bemerkung 1.13 Diese Folgerung zeigt, daß sich nacheinander ↔, → und ∧aus allen Formeln entfernen lassen, so daß man “eigentlich” nur die Junktoren¬ und ∨ in der Definition 1.1 (2) benotigt. Dasselbe gilt aber auch fur ¬ und∧. Es ist nur eine Frage der Bequemlichkeit, die anderen Junktoren ebenfallszu benutzen. Man bezeichnet die jeweils verwendete Menge von Junktoren, alsoΣ = {¬,∧,∨,→,↔} bzw. Σ = {¬,∧} usw. auch als logische Signatur (lat. signum= Zeichen, Kennzeichen) der gerade betrachteten Logik.

Definition 1.14 Atomare Formeln und deren Negationen heißen Literale. EineDisjunktion p1∨ . . .∨pn, wobei jede Teilformel pi eine Konjunktion von Literalenist, heißt eine disjunktive Normalform oder alternative Normalform. Eine Kon-junktion q1 ∧ . . .∧ qn, wobei jede Teilformel qi eine Disjunktion von Literalen ist,heißt eine konjunktive Normalform.

Ohne Beweis sei der folgende Satz mitgeteilt, der dann naturlich auch verwendetwerden darf.

Satz 1.15 Zu jeder aussagenlogischen Formel gibt es eine aquivalente in disjunk-tiver Normalform und eine aquivalente in konjunktiver Normalform.

Satz 1.16 Fur aussagenlogische Formeln x, y, z gelten die folgenden Tautologien

x → (y → x),(44)

((x→ y) → x) → x,(45)

(x→ (y → z)) → (y → (x→ z)),(46)

(x→ y) ↔ ((¬y) → (¬x)),(47)

(x→ y) → ((y → z) → (x→ z)),(48)

(x→ (y → z)) → ((x→ y) → (x→ z)),(49)

(x→ y) ∧ (x→ z) → (x→ y ∧ z),(50)

(x→ z) ∧ (y → z) → (x ∨ y → z),(51)

(x→ y) ∧ (x→ ¬y) → ¬x,(52)

(x→ y) ∧ (¬x→ y) → y.(53)

Beweis: Einige Formeln lassen sich statt durch Wahrheitswertetafeln auch kurzerdurch Fallunterscheidungen beweisen:

(44): Ist x wahr, dann auch y → x fur jede Formel y und daher (44). Ist x aberfalsch, so gilt diese Implikation wegen “ex falso quodlibet”.


1.2 Pradikatenlogik 11

(45): Ist x wahr, so gilt die Implikation. Ist x falsch, so gilt x → y fur jedes y,womit dann aber (x→ y) → x falsch ist. Daher gilt aber die gesamte Implikation.

Rest: Ubungsaufgabe! �

Bemerkung 1.17 In diesem Satz sind einige Beweismethoden angegeben. (44)beschreibt das Prinzip der “Pramissenbelastung”, (45) ist als “Formel von Peirce”(C. S. Peirce, 1839 - 1914) bekannt, (46) als “Pramissenvertauschung”. (47) stelltden “Beweis durch Kontraposition” dar. (48) beschreibt den sogenannten “Ket-tenschluß”, (49) den “Fregeschen Kettenschluß” (Gottlob Frege, 1848 - 1925).(52) stellt das “Platonische Falschheitskriterium” (Platon, 428/27 - 348/47 v.Chr.) dar, (53) das “Euklidische Wahrheitskriterium” (Euklid, um 360 - um 280v. Chr.)

Bemerkung 1.18 Die Methode der Wahrheitswertetafeln stellt eine universel-le Beweismethode fur aussagenlogische Formeln dar, jedoch steigt der Aufwandexponentiell mit der Anzahl der auftretenden Variablen. Man ist daher an Verfah-ren (Algorithmen) interessiert, die “wesentlich schneller” die Wahrheit, Falschheitoder Erfullbarkeit einer Formel feststellen. Daß die Suche nach derartigen Algo-rithmen nicht nur fur die Aussagenlogik große Bedeutung hat, sondern fur fastalle Bereiche der Mathematik (und ihrer Anwendungen), zeigt die Komplexitats-theorie.

1.2 Pradikatenlogik

Sei E ein Grundbereich von Objekten auch Universum genannt. Dann ist eineVariable x uber E ein Zeichen, fur welches jedes Objekt aus E eingesetzt werdenkann. Eine Aussageform oder Pradikat P uber E ist ein sprachliches Gebildeeiner naturlichen oder formalen Sprache, in dem wenigstens eine Variable uber Eauftritt und aus dem beim Einsetzen von Objekten aus E fur alle Variablen ausP eine Aussage entsteht. Wenn in dem Pradikat P genau die Variablen x1, . . . , xn

auftreten, schreibt man P (x1, . . . , xn), nennt P ein n-stelliges Pradikat und sagt,daß die Variablen x1, . . . , xn in P frei vorkommen.

Eine Aussageform hat noch keinen Wahrheitswert, sondern dieser wird erst fest-gelegt, wenn jede Variable in ihr durch einen Wert aus E ersetzt wird. (Ahnlichhaben die in Aufgabe 1.3 betrachteten arithmetischen Terme erst dann einenWert, wenn jeder Variablen eine (reelle) Zahl zugeordnet wurde. Man beachteauch, daß die im zweiten Teil dieser Aufgabe betrachteten Vergleichsoperatorengerade zweistellige Pradikate sind.)


http://de.wikipedia.org/wiki/Charles_Sanders_Peirce

http://de.wikipedia.org/wiki/Gottlob_Frege

http://de.wikipedia.org/wiki/Platon

http://de.wikipedia.org/wiki/Platon

http://de.wikipedia.org/wiki/Euklid

http://de.wikipedia.org/wiki/Euklid


Sei E = N0 die Gesamtheit aller naturlichen Zahlen.

P (x): x ist eine Primzahl.

T (x, y): x teilt y.

G(x) : T (2, x), also “x ist gerade”.

P (9) ist also die falsche Aussage “9 ist eine Primzahl”, P (3) die wahre Aussage“3 ist eine Primzahl”. Ebenso ist T (2, 9) eine falsche Aussage, aber T (2, x) istnoch keine Aussage.

Definition 1.19 Es sei E eine nichtleere Menge von Objekten und VE ={x0, x1, x2 . . .} eine Menge von (Objekt-)Variablen uber E. Weiterhin sei P ={P,Q,R, . . .} eine Menge von Pradikaten, in denen nur Variablen aus VE auftre-ten. Dann werden die pradikatenlogischen Formeln wie folgt erklart:

(1) Jeder der Wahrheitswerte und jedes Pradikat ist eine pradikatenlogische For-mel. Sie werden atomare Formeln oder kurz Atome genannt.

(2) Sind p und q pradikatenlogische Formeln, dann auch

(¬p), (p ∧ q), (p ∨ q), (p→ q), (p↔ q).

(3) Ist p(x) eine pradikatenlogische Formel, in der die Variable x frei vorkommt,dann sind auch (∀x p(x)) und (∃x p(x)) pradikatenlogische Formeln, in denen dieVariable x nicht mehr frei sondern gebunden ist. Alle anderen in p frei vorkom-menden Variablen bleiben frei.

(4) Nur die durch wiederholte Anwendung von (1) - (3) definierten Zeichenkettensind pradikatenlogische Formeln. Die Gesamtheit aller so definierten Formelnwerde mit FP = FP (VE) bezeichnet

Aufgabe 1.20 Man versuche nun noch einmal eine Formalisierung fur den zwei-ten Teil von Aufgabe 1.3.

Bemerkung 1.21 Man liest ∀x p(x) als “fur alle x (aus E) gilt p(x)” und nenntdiese Formel eine Allaussage. Dagegen liest man die Existenzaussage ∃x p(x) als“es gibt ein x (aus E), fur das p(x) gilt”. Weiterhin heißt ∀ der Allquantor oderGeneralisator und ∃ der Existenzquantor oder Partikularisator.

Man schreibt auch oft knapper: Statt ∀x(x ∈ N → x ≤ 2x) kurz ∀x ∈ N(x ≤ 2x)oder ∀x ∈ N : x ≤ 2x.



Fur manche Zwecke ist es nutzlich, den Existenzquantor noch zu modifizierendurch ∃!x p(x) mit der Lesart “es gibt hochstens ein x (aus E), fur das p(x)gilt” und ∃!!x p(x) fur “es gibt genau ein x (aus E), fur das p(x) gilt”. Mankann aber beide Formeln durch zusammengesetzte Formeln allein mit Hilfe desExistenzquantors ausdrucken:

∃!x p(x) ↔ ((∃x p(x) ∧ ∃y p(y)) → x = y)

∃!!x p(x) ↔ (∃x p(x)) ∧ (∃x p(x) ∧ ∃y p(y) → x = y).

Die exakte Festlegung der formalen Semantik der Quantoren und damit der Wahr-heitswerte von pradikatenlogischen Formeln wurde den Rahmen dieser kurzenEinfuhrung sprengen. Man findet dies aber in dem Skript zur Logischen Pro-grammierung, das unter www.mathecafe.de/logik/ verlinkt ist.

Es werden auch Alternativen zur Pradikatenlogik untersucht (Fuzzylogik, Mo-dallogik, Temporallogik, Kausallogik), in denen neben anderen Wahrheitswertenauch andere Quantoren eingefuhrt werden.

Der folgende Satz kann nur mit Hilfe der oben erwahnten Prazisierungen strengbewiesen werden. Er darf jedoch im weiteren Verlauf dieser und anderer Vorle-sungen angewandt werden.

Satz 1.22 Es sei p(x, y) eine Formel, die von den zwei verschiedenen Variablen xund y abhangt und q(x) eine Formel, die von x abhangt. Dann gelten die folgendenAquivalenzen:

∀x∀y p(x, y) ≡ ∀y∀x p(x, y),(54)

∃x∃y p(x, y) ≡ ∃y∃x p(x, y),(55)

¬∃x q(x) ≡ ∀x¬q(x),(56)

¬∀x q(x) ≡ ∃x¬q(x).(57)

Außerdem gilt die Implikation

∃x∀y p(x, y) → ∀y∃x p(x, y).(58)


http://www.mathecafe.de/logik/index.html


Beispiel 1.23 Uber dem Bereich E = Z der ganzen Zahlen bezeichne p(x, y)die Aussageform x + y = 0. Dann ist ∀y∃x p(x, y), also ∀y∃x x + y = 0 einewahre Aussage, denn man kann zu jeder ganzen Zahl y immer die ebenfalls ganzeZahl x = −y wahlen. Dagegen ist im Bereich E = N0 der naturlichen Zahlen dieseAussage nicht wahr. Dies zeigt also, daß die Wahrheit oder Falschheit einer Formelvon E abhangt. In beiden Bereichen ist aber die Formel ∃x∀y x + y = 0 falsch.Daher gilt die Umkehrung in (58) nicht. In allen diesen Aussagen tritt neben demmathematischen Standardpradikat “=” noch das weitere (Verknupfungs-)Symbol“+” auf, dem hier eine ganz bestimmte Bedeutung unterstellt wird, namlich dieder Addition von (ganzen oder naturlichen) Zahlen, vgl. Aufgabe 1.3.

Beispiel 1.24 Uber dem Bereich E = F aller aussagenlogischen Formeln stelltdie Aquivalenz ≡ gemaß Definition 1.6 ebenfalls ein zweistelliges Pradikat in In-fixnotation dar. Fur Variablen p, q, r aus VE lassen sich dann die Aussagen desfolgenden Lemmas beweisen. Hier werden also Aussagen uber Aussagen formali-siert!

Lemma 1.25 Fur aussagenlogische Formeln p, q, r gelten die folgenden Aussa-gen:

∀p p ≡ p,(59)

∀p∀q p ≡ q → q ≡ p,(60)

∀p∀q∀r p ≡ q ∧ q ≡ r → p ≡ r.(61)

Beweis: (59) ist trivial! (Jede Formel p hat bei jeder Variablenbelegung denselbenWahrheitswert wie sie selbst.)

(60) ist ebenfalls trivial. (Wenn die Formeln p und q bei jeder Variablenbele-gung denselben Wahrheitswert besitzen, dann besitzen auch q und p bei jederVariablenbelegung denselben Wahrheitswert.)

(61): Wenn p ≡ q und q ≡ r wahr sind, dann besitzen sowohl p und q als auch qund r bei jeder Variablenbelegung denselben Wahrheitswert. Dann besitzen aberauch p und r bei jeder Variablenbelegung denselben Wahrheitswert. �

Aufgabe 1.26 Man formalisiere moglichst weitgehend mit Hilfe geeigneterpradikatenlogischer Formeln die Begriffe “Teiler”, “Primzahl” und “großter ge-meinsamer Teiler” innerhalb der ganzen Zahlen Z und der naturlichen Zahlen N0.Es durfen also die Pradikate ganz(x) und nat(x) als gegeben betrachtet werden.


1.3 Mengenbildung und Mengenalgebra 15

1.3 Mengenbildung und Mengenalgebra

Wir gehen zunachst einmal von der Mengendefinition nach Georg Cantor (1845- 1918), dem “Vater der Mengenlehre”, aus:

Unter einer Menge verstehen wir jede Zusammenfassung M von bestimmten wohl-unterschiedenen Objekten m unserer Anschauung oder unseres Denkens (welchedie Elemente von M genannt werden) zu einem Ganzen.

Man notiert diesen Sachverhalt formal durch m ∈ M , gelesen: “m ist Elementvon M” oder “M enthalt m”. Das Symbol ∈ ist ein stilisiertes griechisches ε(“Epsilon”) wegen der Bedeutung “Element” (lat. elementum = Grundstoff).

In einer axiomatischen Mengenlehre (grch. axiomata = als wahr angenommenerGrundsatz) wird diese “naive” Vorstellung nun formal prazisiert. Hier wird einemogliche Prazisierung angegeben, die von Ernst Zermelo (1871 - 1953) und Abra-ham Adolf Fraenkel (1891 - 1965) entwickelt wurde und als “ZFC-Mengenlehre”bezeichnet wird. Dabei steht “C” fur das Auswahlaxiom (”axiom of choice”).

Da eine Menge M nach Cantors Vorschlag genau aus ihren Elementen besteht,fordert man das Extensionalitatsaxiom (lat. extensio = Umfang), d. h. jedeMenge ist durch ihren Umfang bereits eindeutig bestimmt, auf die “inhaltlicheBedeutung” ihrer Elemente kommt es also nicht an:

∀M∀N(∀x(x ∈M ↔ x ∈ N) ↔M = N).

Dies hat weiterhin zur Folge, daß jedes Element einer Menge in dieser Mengenur einmal vorkommt und daß es auf die Reihenfolge der Elemente einer Mengeebenfalls nicht ankommt!

Weiterhin prazisiert man die Idee des “Zusammenfassens” von Elementen zueiner Menge in einem moglichst schwachen Sinn, indem man fordert, daß manmindestens zwei (nicht notwendig verschiedene) Objekte immer zu einer Mengezusammenfassen kann. Man formuliert daher das Paarmengenaxiom:

∀a∀b(∃M(∀x x ∈M ↔ x = a ∨ x = b)).

Nach dem Extensionalitatsaxiom ist M durch a und b jeweils eindeutig bestimmt.Man nennt diese Menge eine Zweiermenge und notiert sie als M = {a, b}, speziellfur a = b als M = {a}, wobei sie dann als Einermenge bezeichnet wird.

Da es bisher nicht gesichert ist, ob es uberhaupt Mengen gibt, fordert man axio-matisch die Existenz von mindestens einer Menge. Man kann sich hierbei prinzi-piell auf eine sehr “kleine” Menge beschranken, in der uberhaupt keine Elementeliegen und fordert daher im Nullmengenaxiom:


http://de.wikipedia.org/wiki/Georg_Cantor

http://de.wikipedia.org/wiki/Georg_Cantor

http://de.wikipedia.org/wiki/Ernst_Zermelo

http://de.wikipedia.org/wiki/Adolf_Abraham_Halevi_Fraenkel

http://de.wikipedia.org/wiki/Adolf_Abraham_Halevi_Fraenkel


∃M∀x¬x ∈M .

Nach dem Extensionalitatsaxiom gibt es genau eine derartige Menge; diese wirdleere Menge genannt und mit ∅ oder {} bezeichnet.

Damit gibt es wenigstens die paarweise verschiedenen Mengen ∅, {∅}, {{∅}},{∅, {∅}} usw.

Nennt man nun eine Menge M Teilmenge einer Menge N , wenn jedes Elementvon M auch ein Element von N ist, und notiert dies als M ⊆ N , so ist jedeMenge Teilmenge von sich selbt, die leere Menge ist Teilmenge jeder Menge, undfur die oben genannten Beispiele gelten beispielsweise {∅} ⊆ {∅, {∅}} usw.

Man mochte aber auch die Elemente, die in verschiedenen Mengen zusammenge-faßt wurden, immer zu einer einzigen Menge zusammenfassen durfen. Wiederumfordert man in dem kleinen Vereinigungsmengenaxiom moglichst vorsichtig,daß dies zumindest fur zwei Mengen stets erlaubt ist:

∀A∀B∃M(x ∈M ↔ x ∈ A ∨ x ∈ B)

Wiederum nach dem Extensionalitatsaxiom ist M durch A und B eindeutig be-stimmt und man schreibt M = A ∪B.

Nun kann man fur jede Menge M den eindeutig bestimmten Nachfolger M+ :=M∪{M} definieren. Es gelten dann immer M ∈M+ und M ⊆M+. Insbesonderehat man dann die “Folge” von paarweise verschiedenen Mengen 0 := ∅, 1 := ∅+ =∅ ∪ {∅} = {∅} = {0}, 2 := (∅+)+ = {∅}+ = {∅} ∪ {{∅}} = {∅, {∅}} = {0, 1} usw.Man mochte nun auch diese “unendlich vielen” Mengen wieder zu einer Mengezusammenfassen konnen und fordert das Unendlichkeitsaxiom:

∃M(∅ ∈M ∧ ∀x(x ∈M → x+ ∈M)).

Hiernach muß M nicht genau aus den Elementen der oben genannten Folge be-stehen, sondern konnte noch mehr Elemente enthalten. Man nennt daher jedeMenge mit dieser Eigenschaft eine Nachfolgermenge. Jetzt kann man die Mengeder naturlichen Zahlen N0 als eindeutig bestimmte Nachfolgermenge definieren,die in jeder Nachfolgermenge enthalten ist. Speziell in der Mengenlehre wird an-stelle von N0 auch das Symbol ω benutzt.

Aufgabe 1.27 Man beweise, daß die naturlichen Zahlen in der angegebenenForm tatsachlich existieren. Dabei darf auch die in Definition 1.32 eingefuhrteDurchschnittsbildung benutzt werden.

Weiterhin zeige man, daß die Peano-Axiome (Guiseppe Peano, 1858 - 1932) erfulltsind:


http://de.wikipedia.org/wiki/Peano


(P1) ∅ ∈ N0.

(P2) n ∈ N0 → n+ ∈ N0.

(P3) ∀n ∈ N0∀m ∈ N0(n+ = m+ → n = m).

(P4) ¬∃n ∈ N0 : 0 = n+.

(P5) ∀N ⊆ N0(N Nachfolgermenge → N = N0).

Daß die oben zitierte Cantorsche Definition, wenn man sie zu naiv ganz wortlichnimmt, schnell zu Widerspruchen (Antinomien) fuhrt, stellte sich bald heraus.Ein besonders bekanntes Beispiel fur eine derartige Antinomie fand BertrandRussell (1872 - 1970) mit der sogenannten Russellschen Menge R wie folgt:

Russell definierte zunachst die Allmenge X, also die “Menge aller Mengen”. Dajede Menge ja ein Objekt unseres Geistes ist, schien diese Mengenbildung nachder Cantorschen Definition moglich. Diese Menge mußte sich dann notwendiger-weise selbst enthalten, also X ∈ X erfullen. Dies sieht zwar ungewohnlich aus,scheint aber noch nicht unmoglich zu sein. Russell bildete nun die Menge R aller“gewohnlichen” Mengen M , die also ¬M ∈M , oder kurz M 6∈M erfullen. Jetztfragte er: “Ist R eine “gewohnliche” Menge, gilt also R 6∈ R, oder nicht?”

Ware R eine gewohnliche Menge, also R 6∈ R, dann musste sie aber Element vonR sein, also R ∈ R erfullen, was nicht sein kann.

Ware aber R eine ungewohnliche Menge, so ware R nicht in R enthalten, alsoR 6∈ R und damit R eine gewohnliche Menge, was ebenfalls nicht sein kann.

Daher ist die Bildung von R und damit auch von X widerspruchlich, man darfalso nicht so “uferlos” Mengen bilden.

Ebenfalls von Russell, der ubrigens 1950 als bisher einziger Mathematiker denLiteraturnobelpreis erhielt, stammt die hubsche Veranschaulichung dieses “Rus-selschen Paradoxons” mit dem Dorfbarbier, der genau die Manner eines Dorfesrasiert, die sich nicht selbst rasieren. (Die Auflosung dieses Paradoxons durch dieAnnahme, daß “der” Dorfbarbier eine emanzipierte Frau ist, war damals wohlnoch undenkbar!)

Russell schlug dann als Ausweg (alternativ zu dem oben begonnenen axiomati-schen) einen stufenweisen Aufbau aller Mengen vor.

Zunachst ging Russell von gegebenen Objekten, sogenannten Urelementen oderUrmengen aus, die er als Mengen 0. Stufe bezeichnete: X0, Y 0, Z0, . . . oder


http://de.wikipedia.org/wiki/Bertrand_Russell

http://de.wikipedia.org/wiki/Bertrand_Russell


x, y, z, . . . in ublicher Schreibweise. Dies sind die Elemente der gewohnlichen Men-gen. (Mit der Bezeichnungsweise “Urmengen” bringt man zum Ausdruck, daß esnur Mengen gibt, keine anderen Objekte!)

Dann ging er zu den gewohnlichen Mengen der 1. Stufe uber: X1, Y 1, Z1, . . . oderX, Y, Z, . . ..

Jetzt folgten Mengensysteme als Mengen der 2. Stufe: X2, Y 2, Z2, . . . oderX,Y, Z, . . .. Ihre Elemente sind gerade die gewohnlichen Mengen oder deren Ele-mente.

So fortfahrend gelangte er zu den Mengen der n. Stufe: Xn, Y n, Zn, . . ..

Da jede Menge M einer Stufe n auf diese Weise nur Elemente einer niedrigerenStufe enthalten kann, ist M ∈M ausgeschlossen und die oben dargestellte Anti-nomie kann nicht mehr auftreten. Es bleibt aber unklar, ob nicht andere Wider-spruche durch zu großzugige Mengenbildung auftreten konnen. Daher schranktman die Bildung von Mengen durch das folgende Mengenbildungsaxiom naherein. Es handelt sich hierbei nicht um ein einzelnes Axiom sondern um ein Axio-menschema, aus dem (je nach Wahl der gleich beschriebenen Aussageform P )unendlich viele verschiedene konkrete Axiome entstehen.

Zunachst bezeichne Mn fur jede Stufe eine Mengenvariable fur Mengen der n.Stufe. Weiterhin sei P (Mn) eine Aussageform uber Mengen n. Stufe, in der alsokeine Mengen hoherer Stufe auftreten durfen. Dann soll gelten:

∃Mn+1∀Mn(Mn ∈Mn+1 ↔ P (Mn)).

Mit dem Extensionalitatsaxiom folgt sogar, daß jede nach dem Mengenbildungs-axiom gebildete Menge eindeutig bestimmt ist:

Satz 1.28 ∃!!Mn+1∀Mn(Mn ∈Mn+1 ↔ P (Mn)).

Beweis: Seien Mn+11 und Mn+1

2 beides Mengen (n + 1). Stufe, die diese Bedin-gung erfullen. Dann ist fur alle Mengen Mn n. Stufe die Aussage Mn ∈ Mn+1

1

gleichwertig zu P (Mn) und die Aussage Mn ∈ Mn+12 gleichwertig zu P (Mn).

Wegen Lemma 1.25 folgt hieraus Mn ∈ Mn+11 ↔ Mn ∈ Mn+1

2 , also nach demExtensionalitatsaxiom die behauptete Gleichheit. �

In der axiomatischen Mengenlehre, in der man keine Stufen betrachtet, formuliertman anstelle des Mengenbildungsaxioms etwas vorsichtiger das Aussonderungs-axiom:

∀N∃M∀x(x ∈M ↔ x ∈ N ∧ P (x, x1, . . . , xn)).



Nach dem Extensionalitatsaxiom ist M als Teilmenge von N eindeutig bestimmtund man schreibt M = {x ∈ N | P (x, x1, . . . , xn)}. Man nennt P (x, x1, . . . , xn)einen definierenden Ausdruck von M .

Beispiel 1.29 In der Russelschen Mengenlehre bezeichne P (x) die Aussageformx = x fur eine Mengenvariable x 0. Stufe. Dann ist E = {x | x = x} dieAllmenge, die alle Urmengen enthalt und ∅ = {x | x 6= x} die leere Menge, diekeine Elemente enthalt. Beides sind Mengen 1. Stufe.

In der axiomatischen Mengenlehre ist die Bildung der Allmenge nur innerhalb ei-ner bereits gegebenen Menge moglich und stimmt dann naturlich mit dieser gege-benen Menge uberein. “Allmengen” im naiven Sinn, die zu Widerspruchen fuhrenkonnen, wenn man zu großzugig mit ihnen umgeht, werden dann als Unmen-gen bezeichnet. Man kann aber Mengen und Unmengen zu sogenannten Klassenzusammenfassen und den widerspruchsfreien Umgang mit ihnen in einer “Klas-senlogik” mathematisch korrekt formulieren. Dies uberschreitet aber den Rahmendieser Vorlesung bei weitem. Die “Russellsche Menge” ist dann ubrigens ebenfallseine Unmenge.

Bei der Bestimmung einer Menge mit Hilfe einer definierenden Eigenschaft sindoft auch andere suggestive Schreibweisen ublich: Statt nN0 := {x | x ∈ N0∧n | x}schreibt man auch nN0 := {x ∈ N0 | n | x} oder nN0 := {nm | m ∈ N0}.

Definition 1.30 Es sei n > 0 eine naturliche Zahl und ai fur i = 1, . . . , n Ele-mente aus E mit ai 6= aj fur alle i 6= j. Man nennt derartige Elemente auchpaarweise verschieden, wobei diese Bedingung fur n = 1 immer erfullt sein soll.Bezeichnet P (x) := x = a1 ∨ x = a2 ∨ . . . ∨ x = an, so schreibt man fur dieMenge M = {x | P (x)} auch M = {a1, . . . , an} und nennt sie eine n-elementigeMenge. Eine Menge M heißt endlich, wenn sie leer ist (0-elementig) oder einen-elementige Menge fur irgend eine naturliche Zahl n > 0. Alle anderen Mengenheißen unendlich. Fur n = 1 ergeben sich nochmals die oben schon definiertenEinermengen, fur n = 2 die Zweiermengen. Man schreibt |M | := n fur jede n-elementige Menge und nennt diese Anzahl ihrer Elemente ihre Machtigkeit oderKardinalitat und |M | eine Kardinalzahl. Fur alle unendlichen Mengen M schreibtman |M | = ∞, wobei dieses Symbol keine konkrete Kardinalzahl darstellt, son-dern nur eine Abkurzung fur die Aussage ¬∃n ∈ N0 : |M | = n ist.

Insbesondere ist also die Menge {1, . . . , n} fur jede naturliche Zahl n endlich.Wir werden spater sehen, daß diese Mengen gewissermaßen die “Prototypen” derendlichen Mengen sind.



Aufgabe 1.31 Zeigen Sie, daß fur die Kardinalitaten beliebiger endlicher Men-gen A und B und dem in Definition 1.32 eingefuhrten Durchschnitt A ∩ B undder Vereinigung A ∪B gilt

|A ∪B| = |A|+ |B| − |A ∩B|.

Versuchen Sie anschließend, eine Verallgemeinerung dieser Formel fur |A1 ∪ . . .∪An| bei endlich vielen endlichen Mengen Ai zu finden.

Ersetzt man in einer Mengendefinition M := {x | P (x)} den definierenden Aus-druck P (x) durch einen dazu gleichwertigen Q(x), so wird wegen des Extensio-nalitatsaxioms durch Q(x) dieselbe Menge M beschrieben. Insbesondere kannman die leere Menge auch durch den Ausdruck Q(x) = 0 und die Allmengedurch R(x) = 1 definieren. Außerdem wird jede Menge M durch den AusdruckM(x) := x ∈M beschrieben. Diese Moglichkeit gestattet es, Verknupfungen vonMengen A ◦B gemaß

(A ◦B)(x) = A(x) ◦B(x)

durch Verknupfungen von Pradikaten durch logische Junktoren ◦ zu definieren,wobei ◦ sogar eine beliebige zweistellige Boolesche Funktion sein kann. Dabeiubertragen sich die Eigenschaften der Junktoren unmittelbar auf die Eigenschaf-ten der mengentheoretischen Verknupfungen. Ublicherweise fuhrt man allerdingsaus historischen Grunden neue Symbole fur die Mengenverknupfungen ein.

Definition 1.32 Fur Mengen A und B Mengen definiert man

den Durchschnitt A ∩B = {x | (A ∧B)(x)} = {x | x ∈ A ∧ x ∈ B},

die Vereinigung A ∪B = {x | (A ∨B)(x)} = {x | x ∈ A ∨ x ∈ B},

das Komplement A = −A = {x | ¬A(x)} = {x | x 6∈ A},

die (mengentheoretische) Differenz A \B = A ∩B = {x | x ∈ A ∧ ¬(x ∈ B)},

die symmetrische Differenz A∆B = {x | x ∈ (A \B) ∪ (B \ A)}.

Zwei Mengen A und B mit A ∩ B = ∅ nennt man disjunkt, und die Elementeeines Mengensystems M heißen paarweise disjunkt, wenn je zwei Elemente A 6= Baus M disjunkt sind.

Bemerkung 1.33 Die Veranschaulichung dieser mengentheoretischen Verknup-fungen geschieht meist durch Venn-Diagramme (John Venn, 1834 - 1923).

Menge A und Komplement −A


http://de.wikipedia.org/wiki/John_venn


E

E

A

−A

A

Durchschnitt A ∩B

E

A B

Vereinigung A ∪B

E

A B

Differenz A \B

E

A B

Symmetrische Differenz A∆B



E

A B

Die Aussagen des folgenden Satzes ergeben sich unmittelbar aus den entsprechen-den Aussagen fur die logischen Junktoren.

Satz 1.34 Fur Mengen A,B,C gelten

A ∩ A = A,(62)

A ∪ A = A,(63)

A ∩B = B ∩ A,(64)

A ∪B = B ∪ A,(65)

(A ∩B) ∩ C = A ∩ (B ∩ C),(66)

(A ∪B) ∪ C = A ∪ (B ∪ C),(67)

A ∩ (A ∪B) = A,(68)

A ∪ (A ∩B) = A,(69)

A ∩ (B ∪ C) = (A ∩B) ∪ (A ∩ C),(70)

A ∪ (B ∩ C) = (A ∪B) ∩ (A ∪ C),(71)

A ∪ ∅ = A,(72)

A ∩ E = A,(73)

A ∩ ∅ = ∅,(74)

A ∪ E = E,(75)

A ∩ A = ∅,(76)

A ∪ A = E,(77)

A = A,(78)

∅ = E,(79)

E = ∅,(80)

A ∩B = A ∪B,(81)

A ∪B = A ∩B.(82)

Beweis: (62) und (63) folgen aus (18) und (19).

(64) und (65) folgen aus (20) und (21).






(72) folgt aus (9) mit (65), (73) aus (8) mit (64).

(74) folgt aus (7), (75) aus (10).

(76) folgt aus (4), (77) aus (5).

(78) folgt aus (3).

(79) folgt aus (1), (80) aus (2).

(81) folgt auch (35), (82) aus (36). �

Bemerkung 1.35 (62) und (63) besagen, daß Durchschnitt bzw. Vereinigungvon Mengen idempotent sind.

(64) und (65) stellen fest, daß beide Operationen auch kommutativ sind.

(66) und (67) beschreiben die Assoziativitat der beiden Operationen.

Die Gleichungen (69) und (68) werden Absorptionsgesetze genannt, die Gleichun-gen (70) und (71) Distributivgesetze.

Schließlich nennt man (76) und (77) die Komplementgesetze.

Gelten ganz allgemein auf einer Menge M fur zwei Operationen ∩ und ∪ dieGesetze (64) - (69), so spricht man von einem Verband. Gelten dazu noch (71)und (70), so heißt der Verband distributiv.

Ist jedem Element dieses distributiven Verbandes dann noch eindeutig ein “Kom-plement” zugeordnet und gibt es zwei ausgezeichnete Elemente (meist mit “o”und “e” bezeichnet), so daß die Komplementgesetze gelten, so spricht man voneiner Booleschen Algebra.

Jede Potenzmenge ist also eine Boolesche Algebra.

Eine ausfuhrlichere Behandlung dieser algebraischen Strukturen findet man indem Skript zur Verbandstheorie

www.mathe.tu-freiberg.de/∼hebisch/skripte/verbtheorie/verb.pdf


http://www.mathe.tu-freiberg.de/~hebisch/skripte/verbtheorie/verb.pdf


Die Assoziativ- und Kommutativgesetze fur Durchschnitt und Vereinigung ge-statten auch die bekannten Schreibweisen fur Durchschnitte und Vereinigungenendlich vieler Mengen A1, . . . , An:⋂n

i=1Ai := (. . . (A1 ∩ A2) ∩ . . . ∩ An−1) ∩ An,⋃ni=1Ai := (. . . (A1 ∪ A2) ∪ . . . ∪ An−1) ∪ An.

Folgerung 1.36 Fur Mengen A,B,C gelten

A \ ∅ = A,(83)

A \ E = ∅,(84)

∅ \ A = ∅,(85)

E \ A = A,(86)

A \ A = ∅,(87)

A \B = A ∪B,(88)

(A ∩B) \ C = (A \ C) ∩ (B \ C),(89)

(A ∪B) \ C = (A \ C) ∪ (B \ C),(90)

A \ (B ∩ C) = (A \B) ∪ (A \ C),(91)

A \ (B ∪ C) = (A \B) ∩ (A \ C),(92)

A \ (B \ C) = (A \B) ∪ (A \ C).(93)

Beweis: Die ersten funf Aussagen sind trivial!

(88): Wegen A \B = A∩B folgt aus (81) A \B = A ∩B = A∪B, wobei in derletzten Gleichheit noch (78) benutzt wurde.

Rest: Ubung! �


A∆B = (A ∪B) \ (A ∩B),(94)

A∆B = B∆A,(95)

(A∆B)∆C = A∆(B∆C),(96)

A∆∅ = A,(97)

A∆A = ∅,(98)

A∆B = A∆B,(99)

A ∩ (B∆C) = (A ∩B)∆(A ∩ C).(100)



Beweis: (94): Es ist nach Definition der symmetrischen und der mengentheore-tischen Differenz A∆B = (A ∩ B) ∪ (B ∩ A). Mit (70) und (71) folgt hierausA∆B = (A ∩B) ∪ (A ∩A) ∪ (B ∩B) ∪ (B ∩A). Wegen A ∩A = B ∩B = ∅ giltalso A∆B = (A ∪ B) ∩ (A ∪ B) = (A ∪ B) ∩ A ∩B, wobei die letzte Gleichheitaus (81) kommt. Mit der Definition der mengentheoretischen Differenz folgt nundie Behauptung.

(95): Nach Definition der symmetrischen Differenz und wegen (65) gilt A∆B =(A \B) ∪ (B \ A) = (B \ A) ∪ (A \B) = B∆A.

(97): Es ist mit der vorhergehenden Folgerung A∆∅ = (A\∅)∪(∅\A) = A∪∅ = A.

(98): Es ist mit der vorhergehenden Folgerung A∆A = (A\A)∪(A\A) = ∅∪∅ = ∅.

Rest: Ubung! �

Definition 1.38 Seien A und B Mengen. Man nennt A eine Teilmenge oderUntermenge von B und B dann eine Obermenge von A, in Zeichen: A ⊆ B, wenn∀x(x ∈ A→ x ∈ B) gilt. Hat man dann noch A 6= B, so heißt A echte Teilmengevon B, in Zeichen: A ⊂ B. Diese Beziehung zwischen zwei Mengen nennt manauch Inklusion (lat. includere = einschließen).

Folgerung 1.39 Fur alle Mengen A,B,C gelten

∅ ⊆ A,(101)

A ⊆ A,(102)

A ⊆ B ∧B ⊆ A → A = B,(103)

A ⊆ B ∧B ⊆ C → A ⊆ C.(104)

Beweis: Da x ∈ ∅ fur alle x falsch ist, gilt x ∈ ∅ → x ∈ A wegen “ex falsoquodlibet”, also ist (101) richtig. (102) und (103) folgen aus (40) und dem Ex-tensionalitatsaxiom, (104) folgt aus (48). �

Beispiel 1.40 Fur jede naturliche Zahl n ∈ N0 ist nZ := {x | ∃z(z ∈ Z ∧ x =n · z)} eine Teilmenge von Z und ebenso ist nN0 = nZ ∩ N0 eine Teilmenge vonN0. Naturlich ist 0Z = {0} und 1Z = Z. Weiterhin gilt n | m ↔ mZ ⊆ nZ,wodurch man die in (102) - (104) enthaltenen Aussagen uber die Inklusion direktin Aussagen uber die Teilbarkeit in den naturlichen Zahlen ubersetzen kann.

Entsprechende Aussagen uber Teilmengen von N0 erhalt man, wenn man dieMengen nN0 = N0 ∩ nZ betrachtet.



Die Aussage (103) wird sehr oft verwendet, um die Gleichheit von zwei Mengenzu zeigen.

Fur unendliche Mengen ist durch die bisherigen Axiome nicht gesichert, daß mansamtliche Teilmengen einer Menge wieder zu einer Menge zusammenfassen darf.Daher fordert man noch das Potenzmengenaxiom:

∀M∃P∀X(X ∈ P ↔ ∀y(y ∈ X → y ∈M)).

Definition 1.41 Fur jede Menge M sei P(M) = {A | A ⊆M} die Potenzmengevon M , also die Menge aller Teilmengen von M .

Beispiel 1.42 Es ist P(∅) = {∅}, P({a}) = {∅, {a}}, P({a, b}) ={∅, {a}, {b}, {a, b}}, P({a, b, c}) = {∅, {a}, {b}, {a, b}, {c}, {a, c}, {b, c}, {a, b, c}}.

Folgerung 1.43 Fur Mengen A und B und ihre Potenzmengen gelten

P(A) ∩ P(B) = P(A ∩B),(105)

P(A) ∪ P(B) ⊆ P(A ∪B).(106)

Beweis: Sei X ⊆ A ∩ B, dann gilt auch X ⊆ A und X ⊆ B. Also liegt jedesX ∈ P(A ∩ B) sowohl in P(A) als auch in P(B). Ist andererseits Y eine Menge,die sowohl in P(A) als auch in P(B) liegt, dann ist Y Teilmenge von A undTeilmenge von B. Also ist jedes y ∈ Y sowohl in A als auch in B enthalten undliegt daher im Durchschnitt A ∩ B. Dies zeigt dann Y ∈ P(A ∩ B). Daher sindbeide Seiten gleich.

Rest: Ubung! �

Um auch Vereinigungen uber unendlich viele Mengen bilden zu konnen fordertman das große Vereinigungsmengenaxiom, woraus naturlich das kleine sofortfolgt:

∀M∃X∀x(x ∈ X ↔ ∃M(M ∈ M ∧ x ∈M)).

Definition 1.44 Es sei M ein Mengensystem. Man definiert

die Vereinigung uber M als⋃

M = {x | ∃X (X ∈ M ∧ x ∈ X)} und

den Durchschnitt uber M 6= ∅ als⋂

M = {x | ∀X (X ∈ M → x ∈ X)}.

Speziell fur Mengensysteme M = {An | n ∈ N0} schreibt man auch⋃

M =⋃∞n=0An bzw.

⋂M =

⋂∞n=0An.


1.4 Relationen und Abbildungen 27

Bemerkung 1.45 Fur Zweiermengen M = {A,B} stimmt⋃

M mit der Vereini-gung A ∪B und

⋂M mit dem Durchschnitt A ∩B uberein.⋃

und⋂

erniedrigen in einer gestuften Mengenlehre die Stufe der Menge um 1.

Fur M = ∅ wurde sich⋂ ∅ = E, die Allmenge, ergeben. Man verzichtet ublicher-

weise in einer nicht gestuften Mengenlehre auf derartige Durchschnittsbildungen,wenn das Mengensystem nicht einer festen Potenzmenge entstammt!

Aufgabe 1.46 Man beweise durch vollstandige Induktion: Ist M eine n-elementige Menge, so ist die Potenzmenge P(M) 2n-elementig, kurz: |P(M)| =2|M |. Man schreibt daher auch 2A oder 2A fur P(A) bei beliebigen Mengen A.

Aufgabe 1.47 Versuchen Sie, den Beweis des Euklid fur die Aussage, daß esnicht nur endlich viele Primzahlen gibt, moglichst weitgehend mit mengentheo-retischen und pradikatenlogischen Mitteln zu formalisieren

Aufgabe 1.48 Man beweise die Moglichkeit der sogenannten Division mit Rest:Zu a, b ∈ Z mit b 6= 0 existieren ein eindeutig bestimmtes q ∈ Z, der Quotient, undein eindeutig bestimmtes r ∈ Z, der Rest mit a = q · b+ r und 0 ≤ r < |b|. (Mankann also a stets durch b 6= 0 eindeutig mit Rest r dividieren.) Sei n > 0 eineganze Zahl, also eine naturliche Zahl n 6= 0. Definiert man fur r = 0, 1, . . . , n− 1die (nichtleeren!) Mengen [r]n = {x ∈ Z | x laßt bei Division durch n den Restr}, dann sind diese Restklassen modulo n nicht leer und paarweise disjunkt undfur das Mengensystem Z/(n) = {[r]n | r = 0, . . . , n− 1} gilt Z =

⋃Z/(n).

1.4 Relationen und Abbildungen

1.4.1 Kartesische Produkte

Die folgende Definition des geordneten Paares und damit des kartesischen Pro-duktes (Rene Descartes, 1596 - 1650) geht auf Kazimierz Kuratowski (1896 -1980) zuruck.

Definition 1.49 Fur beliebige Elemente a und b (aus E) sei das geordnete Paar(a, b) definiert als Zweiermenge (a, b) = {{a}, {a, b}}.

Sind A und B Mengen, dann heißt A × B = {(a, b) | a ∈ A ∧ b ∈ B} daskartesische Produkt oder Kreuzprodukt oder direktes Produkt von A und B.


http://de.wikipedia.org/wiki/Descartes

http://de.wikipedia.org/wiki/Kuratowski

http://de.wikipedia.org/wiki/Kuratowski


Bemerkung 1.50 Das geordnete Paar (a, b) ist eine Menge 2. Stufe und daskartesische Produkt daher eine Menge 3. Stufe.

Fur a 6= b ist (a, b) eine Zweiermenge, fur den Spezialfall a = b ist (a, a) = {{a}}eine Einermenge.

Man kann geordnete Paare (Mn,Mm) (und damit Kreuzprodukte) auch fur Men-gen Mn,Mm beliebiger, sogar verschiedener, Stufen definieren.

Folgerung 1.51 Fur geordnete Paare gilt (a, b) = (a′, b′) ↔ (a = a′) ∧ (b = b′).

Beweis: Naturlich folgt aus (a = a′)∧(b = b′) sofort die Gleichheit (a, b) = (a′, b′)und es ist nur die umgekehrte Implikation zu zeigen.

Wir unterscheiden zwei Falle: 1. Es ist a = b. Dann ist (a, a) einelementig unddaher auch (a, a) = (a′, b′). Dies ist nur fur a′ = b′ der Fall. Also gilt {{a}} ={{a′}}, woraus zunachst {a} = {a′} und damit auch a = a′ folgt.

2. Es ist a 6= b. Dann ist (a, b) eine Zweiermenge und damit auch (a′, b′). Also giltebenfalls a′ 6= b′. Daher sind {a} und {a′} Einermengen und {a, b} sowie {a′, b′}Zweiermengen. Fur die beiden Elemente der gleichen Zweiermengen {{a}, {a, b}}und {{a′}, {a′, b′}} kann daher nur {a} = {a′} und {a, b} = {a′, b′} gelten. Ausder ersten Gleichung folgt dann schon a = a′ und hieraus {a, b} = {a, b′}. DurchSubtraktion von {a} folgt dann {b} = {b′} und damit b = b′. �

Satz 1.52 Fur Mengen A,B,C,D gelten die folgenden Aussagen

A×B = ∅ ↔ A = ∅ ∨B = ∅,(107)

C 6= ∅ ∧ A× C = B × C → A = B,(108)

(A ∩B)× C = (A× C) ∩ (B × C),(109)

A× (B ∩ C) = (A×B) ∩ (A× C),(110)

(A ∪B)× C = (A× C) ∪ (B × C),(111)

A× (B ∪ C) = (A×B) ∪ (A× C),(112)

(A×B) ∩ (C ×D) = (A ∩ C)× (B ∩D),(113)

(A×B) ∪ (C ×D) ⊆ (A ∪ C)× (B ∪D),(114)

(A \ C)× (B \D) ⊆ (A×B) \ (C ×D).(115)

Sind A und B in einer gemeinsamen Obermenge M enthalten und beziehen sichdie Komplemente auf M bzw. M ×M , so gilt

A×B ⊆ A×B.(116)



Beweis: (107): Ist A = ∅ oder B = ∅, so kann es naturlich kein Element (a, b) ∈A × B geben, denn dann mußte a ∈ A und b ∈ B gelten. Also folgt dannA × B = ∅. Sind andererseits sowohl A als auch B nicht leer, dann gibt eswenigstens ein a ∈ A und ein b ∈ B. Dann liegt aber (a, b) in A × B und dieseMenge ist nicht leer.

(108): Gelte also C 6= ∅ ∧ A × C = B × C und sei x ∈ A. Dann gibt es einc ∈ C und (x, c) ∈ A × C = B × C zeigt x ∈ B. Also gilt A ⊆ B. DurchVertauschung der Rollen von A und B folgt auch die umgekehrte Inklusion unddamit die Gleichheit.

(116) Aus (115) folgt (M \ A) × (M \ B) ⊆ (M ×M) \ (A × B), und dies istgerade die Behauptung.

Rest: Ubung! �

Definition 1.53 Fur naturliche Zahlen n ≥ 3 und Mengen Mi, i = 1, . . . , nsowie Elemente xi ∈Mi seien n-Tupel rekursiv definiert durch

(x1, x2, x3) := ((x1, x2), x3) fur n = 3 und

(x1, x2, . . . , xn) := ((x1, . . . , xn−1), xn) fur n > 3.

Weiterhin sei M1 ×M2 × . . . ×Mn := {(x1, . . . , xn) | x1 ∈ M1 ∧ . . . ∧ xn ∈ Mn}das kartesische Produkt der Mi.

Speziell fur M1 = M2 = . . . = Mn = A schreibt man hierfur An und nennt diesdie n-te Potenz von A mit den Randfallen A2 = A× A, A1 = A und A0 = {∅}.

In der Informatik werden die Elemente (a1, . . . , an) von An auch Listen der Langen genannt und als [a1, . . . , an] notiert. Speziell bezeichnet [ ] dann die leere Listeaus A0. Die Menge A heißt in diesem Zusammenhang auch ein Datentyp. Es istdann A∗ =

⋃∞n=0A

n die Menge aller Listen uber A.

Aufgabe 1.54 Man beweise durch vollstandige Induktion: Ist A eine m-elementige Menge, so ist An eine mn-elementige Menge, kurz: |An| = |A|n furalle endlichen Mengen A und n ∈ N0.

1.4.2 Korrespondenzen und Relationen

Definition 1.55 Es seien A und B Mengen. Eine Teilmenge R ⊆ A × B nenntman auch eine Korrespondenz oder Relation aus A in B und dazu R−1 := {(b, a) |(a, b) ∈ R} ⊆ B × A die inverse Korrespondenz. Weiterhin heißen



D(R) := {x | x ∈ A ∧ ∃y ∈ B : (x, y) ∈ R} der Definitionsbereich und

W (R) := {y | y ∈ B ∧ ∃x ∈ A : (x, y) ∈ R} der Wertebereich von R.

Eine Korrespondenz R ⊆ A×B heißt Korrespondenz

von A in B oder linkstotal, falls D(R) = A gilt,

aus A auf B oder rechtstotal, falls W (R) = B gilt,

von A auf B, falls D(R) = A und W (R) = B gelten.

Schließlich setzt man noch R(x) := {y | (x, y) ∈ R} fur alle x ∈ D(R) und nenntR rechtseindeutig, wenn R(x) einelementig fur alle x ∈ D(R) ist.

Fur Teilmengen A′ ⊆ A und B′ ⊆ B bezeichnet R|A′×B′ := R ∩ (A′ × B′) ={(a′, b′) ∈ A′ ×B′ | (a′, b′) ∈ R} die Einschrankung von R auf A′ ×B′.

Beispiel 1.56 Fur A = {1, 2, 3, 4, 5} und B = {a, b, c, d} sei R ={(1, a), (1, c), (3, b), (4, b)}, also D(R) = {1, 3, 4} und W (R) = {a, b, c}.

1

2

3

4

5

a

b

c

d

AB

R

D(R) W(R)

Dann gilt beispielsweise R(1) = {a, b}, R(3) = R(4) = {b} und R(2) = R(5) = ∅sowie R−1(a) = {1} = R−1(c), R−1(b) = {3, 4} und R−1(d) = ∅.

Bemerkung 1.57 Ist R ⊆ A × B eine beliebige Korrespondenz und setzt manA′ := {x ∈ A | ∃y ∈ B ∧ (x, y) ∈ R} = D(R) sowie B′ := {y ∈ B | ∃x ∈A ∧ (x, y) ∈ R} = W (R), dann ist R′ = R ∩ (A′ × B′) eine Korrespondenz vonA′ auf B′, also eine auf diesen Mengen links- und rechtstotale Korrespondenz.Daher wird oft eine oder sogar beide dieser Eigenschaften allgemein vorausgesetzt,insbesondere bei Abbildungen.



Definition 1.58 Fur eine beliebige Korrespondenz R ⊆ A×B werde die Erwei-terung R ⊆ P(A) × P(B) definiert durch R(X) := {y ∈ B | ∃x ∈ X : (x, y) ∈R} =

⋃{R(x) | x ∈ X}. Daher hat man auch R−1(Y ) := {x ∈ A | ∃y ∈ Y :(x, y) ∈ R} =

⋃{R−1(y) | y ∈ Y }.

Folgerung 1.59 Fur jede Korrespondenz R ⊆ A×B ist R linkstotal und rechts-eindeutig. Es ist stets R(∅) = ∅ und damit auch R−1(∅) = ∅. Weiterhin hat man

R(A) = W (R) und R−1(B) = D(R).

Fur alle X1, X2 ⊆ A und alle Y1, Y2 ⊆ B gelten

R(X1 ∪X2) = R(X1) ∪ R(X2),(117)

R−1(Y1 ∪ Y2) = R−1(Y1) ∪ R−1(Y2),(118)

R(X1 ∩X2) ⊆ R(X1) ∩ R(X2),(119)

R−1(Y1 ∩ Y2) ⊆ R−1(Y1) ∩ R−1(Y2),(120)

R−1(B \ Y1) ⊆ A \ R−1(Y1).(121)

In (119) gilt die Gleichheit, wenn R linkseindeutig ist, in (120) und (121) stehtjeweils die Gleichheit, wenn R rechtseindeutig ist.

Beweis: Man beachte, daß (117) und (118) dieselben Aussagen nur fur die un-terschiedlichen Korrespondenzen R und R−1 sind. Dasselbe gilt bezuglich (119)und (120).

(117): Fur y ∈ B sind jeweils gleichwertig:

y ∈ R(X1 ∪X2),

∃x ∈ (X1 ∪X2) : (x, y) ∈ R,

∃x ∈ X1 : (x, y) ∈ R ∨ ∃x ∈ X2 : (x, y) ∈ R,

y ∈ R(X1) ∨ y ∈ R(X2)

y ∈ R(X1) ∪ R(X2).

Man kann aber auch mit Satz 1.127 (4) schließen:

R(X1 ∪X2) =⋃{R(x) | x ∈ (X1 ∪X2)}

=⋃{R(x) | x ∈ X1 ∨ x ∈ X2}

=⋃

({R(x) | x ∈ X1} ∪ {R(x) | x ∈ X2})=

⋃{R(x) | x ∈ X1} ∪

⋃{R(x) | x ∈ X2})

= R(X1) ∪ R(X2).



Rest: Ubung! �

Definition 1.60 Seien R ⊆ A × B und S ⊆ C × D Korrespondenzen. Dannheißt

R ◦ S := {(x, z) | (x, z) ∈ A×D ∧ ∃y ∈ B ∩ C : (x, y) ∈ R ∧ (y, z) ∈ S}

die Verkettung von R mit S.

Beispiel 1.61 Fur R wie in Beispiel 1.56, C = {b, c, d, e, f}, D = {α, β, γ, δ} seiS = {(b, α), (d, β), (d, γ), (e, α)}.

1

2

3

4

5

a

b

c

d

A

R

B

C

e

f

β

α

δ

γ

S

D

R o S

Dann gilt R ◦ S = {(3, α), (4, α)}.

Satz 1.62 Fur Korrespondenzen R,S, T gelten

(R−1)−1 = R,(122)

(R ◦ S)−1 = S−1 ◦R−1,(123)

(R ◦ S) ◦ T = R ◦ (S ◦ T ).(124)

Beweis: (122) ist trivial.

(123): Fur (d, a) ∈ (R ◦ S)−1 sind jeweils gleichwertig



(a, d) ∈ R ◦ S

∃x ∈ B ∩ C : (a, x) ∈ R ∧ (x, d) ∈ S

∃x ∈ C ∩B : (d, x) ∈ S−1 ∧ (x, a) ∈ R−1

(d, a) ∈ S−1 ◦R−1.

(124): Seien R ⊆ A × B, S ⊆ C × D und T ⊆ E × F . Dann sind fur alle(a, f) ∈ A× F gleichwertig

(a, f) ∈ (R ◦ S) ◦ T ,

∃d ∈ D ∩ E : (a, d) ∈ R ◦ S ∧ (d, f) ∈ T ,

∃d ∈ D ∩ E : ∃b ∈ B ∩ C : (a, b) ∈ R ∧ (b, d) ∈ S ∧ (d, f) ∈ T ,

∃b ∈ B ∩ C : ∃d ∈ D ∩ E : (a, b) ∈ R ∧ (b, d) ∈ S ∧ (d, f) ∈ T ,

∃b ∈ B ∩ C : (a, b) ∈ R ∧ (b, f) ∈ S ◦ T ,

(a, f) ∈ R ◦ (S ◦ T ). �

Definition 1.63 Es sei A eine Menge und n > 0 eine naturliche Zahl. EineTeilmenge % ⊆ An heißt eine n-stellige Relation auf A. Im Fall n = 2 sprichtman auch von binaren Relationen. Die Menge aller binaren Relationen werde mitBA bezeichnet. Binare Relationen % schreibt man oft in Infixnotation, also a%banstelle von (a, b) ∈ %.

Bemerkung 1.64 Relationen sind also Elemente der Potenzmengen P(An).Stets sind ∅, die leere Relation, und An, die Allrelation, Relationen auf An. Zu BA

gehort auch immer die identische Relation oder Identitat ιA = {(a, a) | a ∈ A} aufA. Sie wird auch als idA oder 1A oder ∆A oder schlicht als Gleichheit = notiert.

Folgerung 1.65 Fur binare Relationen %i ∈ BA = P(A×A) auf einer Menge Agelten

(%1 ∪ %2) ◦ %3 = %1 ◦ %3 ∪ %2 ◦ %3,(125)

%1 ◦ (%2 ∪ %3) = %1 ◦ %2 ∪ %1 ◦ %3,(126)

(%1 ∩ %2) ◦ %3 ⊆ %1 ◦ %3 ∩ %2 ◦ %3,(127)

%1 ◦ (%2 ∩ %3) ⊆ %1 ◦ %2 ∩ %1 ◦ %3.(128)



Beweis: (125): Fur (a, b) ∈ A2 sind jeweils gleichwertig:

(a, b) ∈ (%1 ∪ %2) ◦ %3,

∃c ∈ A : (a, c) ∈ %1 ∪ %2 ∧ (c, b) ∈ %3,

∃c ∈ A : ((a, c) ∈ %1 ∨ (a, c) ∈ %2) ∧ (c, b) ∈ %3,

∃c ∈ A : ((a, c) ∈ %1 ∧ (c, b) ∈ %3) ∨ ((a, c) ∈ %2) ∧ (c, b) ∈ %3),

(a, b) ∈ %1 ◦ %3 ∨ (a, b) ∈ %2 ◦ %3,

(a, b) ∈ %1 ◦ %3 ∪ %2 ◦ %3.

Rest: Ubung! �

1.4.3 Aquivalenz- und Ordnungsrelationen

Definition 1.66 Eine binare Relation % ∈ BA heißt

reflexiv :↔ ιA ⊆ %,

irreflexiv :↔ ιA ∩ % = ∅,

symmetrisch :↔ %−1 ⊆ %,

asymmetrisch :↔ %−1 ∩ % = ∅,

antisymmetrisch :↔ %−1 ∩ % ⊆ ιA,

transitiv :↔ % ◦ % ⊆ %,

konnex :↔ % ∪ %−1 ∪ ιA = ωA,

linear :↔ % ∪ %−1 = ωA.

Eine Aquivalenz(relation) ist eine reflexive, symmetrische und transitive Rela-tion, eine partielle Ordnung(srelation) ist eine reflexive, antisymmetrische undtransitive Relation. Eine totale oder lineare Ordnung(srelation) ist eine reflexive,antisymmetrische, transitive und lineare Relation. Mit E(A) werde die Mengealler Aquivalenzrelationen auf A bezeichnet. Fur Aquivalenzrelationen schreibtman statt % oft andere Symbole wie ≡, ∼ oder ∼= und benutzt die Infixnotation.Entsprechend benutzt man fur Ordnungsrelationen oft das Symbol ≤ in Infixno-tation. Ist ≤ partielle Ordnungsrelation auf der Menge A, so nennt man das Paar(A,≤) eine partiell geordnete Menge, im Fall, daß ≤ sogar eine lineare Ordnungist, eine linear oder total geordnete Menge oder eine Kette. Eine Praordnung oderQuasiordnung ist eine reflexive und transitive Relation.



Beispiel 1.67 Die Identitat ιA und die Allrelation ωA liegen stets in E(A). Wegender Reflexivitat gilt fur jede Aquivalenzrelation % auf A bereits ιA ⊆ % ⊆ ωA.

Die Identitat ιA ist ebenso stets eine partielle Ordnung auf A, die in jeder an-deren partiellen Ordnung auf A enthalten ist. Liegen aber in A mindestens zweiverschiedene Elemente a 6= b, so gilt weder (a, b) ∈ ιA noch (b, a) ∈ ιA und daherist dies keine lineare Ordnung. Man schreibt diese partielle Ordnung auf jederMenge ublicherweise als Gleichheit, also a = b anstelle von (a, b) ∈ ιA.

Die Gleichwertigkeit ≡ ist wegen Lemma 1.25 eine Aquivalenz auf der MengeF(V ) aller aussagenlogischen Formeln.

Die Inklusion ⊆ ist wegen Folgerung 1.39 eine partielle Ordnung auf jeder Po-tenzmenge P(M). Enthalt M mehr als ein Element, so ist diese partielle Ordnungnicht linear.

Die Teilbarkeitsrelation | ist eine partielle Ordnungsrelation auf der Menge dernaturlichen Zahlen N0, aber nur eine Quasiordnung auf der Menge der ganzenZahlen Z.

Die ubliche ≤-Relation ist eine lineare Ordnung auf den Mengen N0,Z und Q, alsosind (N0,≤), (Z,≤) und (Q,≤) linear geordnete Mengen.

Bemerkung 1.68 Ist (A,≤) partiell geordnete Menge, so schreibt man auchb ≥ a fur a ≤ b und a < b fur a 6= b mit a ≤ b.

Die hierdurch entstehende binare Relation < auf A ist irreflexiv, asymmetrischund transitiv. Man spricht dann von einer partiellen Ordnung in irreflexiverSchreibweise. Umgekehrt kann man jede derartige Relation < durch Vereinigungmit ιA zu einer partiellen Ordnungsrelation ≤ machen.

Jeder partiellen Ordnung ≤ in reflexiver Schreibweise auf einer Menge A ent-spricht auf diese Weise eindeutig eine partielle Ordnung < in irreflexiver Schreib-weise. Genau dann ist ≤ linear, wenn < konnex ist.

Bemerkung 1.69 Fur (kleine) endliche Mengen A kann man sich partielle Ord-nungen ≤ auf A durch Hasse-Diagramme (Helmut Hasse, 1898 - 1979) veran-schaulichen: Man zeichnet fur jedes Element von A einen Punkt in der Zeichene-bene, wobei man den zu einem Element a ∈ A gehorenden Punkt so anordnet,daß er “oberhalb” von allen Punkten liegt, die zu einem Element x ∈ A gehoren,das x ≤ a erfullt. Anschließend verbindet man zwei verschiedene Punkte genaudann durch eine gerade Linie, wenn fur die zugehorigen Elemente a ≤ b gilt undkein Element x ∈ A \ {a, b} mit a ≤ x und x ≤ b existiert. Fur die kleinen Po-tenzmengen aus Beispiel 1.42 ergeben sich damit die folgenden Diagramme. Imletzten Beispiel ist eine (Teil-)Kette rot hervorgehoben.


http://de.wikipedia.org/wiki/Helmut_Hasse


{a}

{b}{a}

{a,b}

Φ

Φ

Φ

Φ

{a} {b}

{a,b}

{c}

{a,c} {b,c}

{a,b,c}

Φ P({a}) P({a,b})

P({a,b,c})

P( )

Aufgabe 1.70 Man untersuche, welche der in Definition 1.66 genannten Eigen-schaften sich von % auf jede Einschrankung von % auf eine Teilmenge A′ ⊆ Aubertragen, also beispielsweise:

Jede Einschrankung einer (linearen) Ordnungsrelation ist wieder eine (lineare)Ordnungsrelation.

Beispiel 1.71 Es seien (A1,≤1) und (A2,≤2) total geordnete Mengen. Danndefiniert (a1, a2) ≤ (b1, b2) :↔ (a1 <1 b1) ∨ (a1 = b1 ∧ a2 ≤2 b2) eine totaleOrdnung auf A1 × A2, die lexikographische Ordnung.

Man kann diese Konstruktion der lexikographischen Ordnung daher induktiv aufkartesische Produkte A1 × . . .× An mit endlich vielen Faktoren ubertragen.

Definition 1.72 Es sei A eine Menge. Eine Teilmenge Z ⊆ P(A)\{∅} heißt eineZerlegung oder Partition oder disjunkte Uberdeckung von A, wenn die Elementevon Z paarweise disjunkt sind und

⋃Z = A gilt.

Satz 1.73 Es sei A eine Menge, E(A) die Menge aller Aquivalenzrelationen aufA und Z(A) die Menge aller Zerlegungen von A.

a) Fur jede Zerlegung Z ∈ Z(A) wird durch

x%Zy :↔ ∃X ∈ Z ∧ x ∈ X ∧ y ∈ X

fur alle x, y ∈ A eine Aquivalenzrelation %Z definiert.

b) Ist % ∈ E(A) dann ist Z% = {[x]% | x ∈ A} eine Zerlegung von A, wobei [x]% ={y ∈ A | x%y} die von x ∈ A reprasentierte Aquivalenzklasse oder Restklasse ist.

c) Fur alle % ∈ E(A) und Z ∈ Z(A) gelten %Z% = % und Z%Z= Z.



Beweis: a) Sei x ∈ A =⋃

Z. Dann gibt es ein X ∈ Z mit x ∈ X und x ∈ X. Alsoist %Z reflexiv. Gilt x%Zy fur x, y ∈ A, so gibt es ein X ∈ Z mit x, y ∈ X. Danngilt aber auch y%Zx, und %Z ist auch symmetrisch. Gelten nun x%Zy und y%Zz furx, y, z ∈ A, so gibt es X, Y ∈ Z mit x, y ∈ X und y, z ∈ Y . Da die Mengen aus Z

paarweise disjunkt sind, kann dies wegen y ∈ X ∩Y nur fur X = Y gelten. Danngilt aber x, z ∈ X und daher x%Zz. Also ist %Z auch transitiv.

b) Wegen x ∈ [x]% ⊆ A fur alle x ∈ A aufgrund der Reflexivitat von % sinddie Restklassen nichtleere Teilmengen von A und es gilt A =

⋃{[x]% | x ∈ A}.Es bleibt zu zeigen, daß die Restklassen paarweise disjunkt sind. Sei dazu a ∈[x]% ∩ [y]% 6= ∅. Dann ist [x]% = [y]% nachzuweisen. Wegen der Transitivitat undSymmetrie von % ist dies gleichwertig zu x%y. Nun gilt aber x%a und y%a unddaher wiederum wegen der Transitivitat und Symmetrie auch x%y.

c) Siehe Vorlesung! �

Definition 1.74 Die zu einer Aquivalenzrelation % ∈ E(A) gehorende Zerlegungwird auch als A/% = {[x]% | x ∈ A} notiert und Faktormenge von A nach %genannt. Jedes Element x′ ∈ [x]% wird dann ein Reprasentant der Restklasse [x]%genannt. Unter einem Reprasentantensystem von % versteht man eine TeilmengeA′ ⊆ A, so daß fur jede Klasse [x]% ∈ A/% genau ein Reprasentant x′ ∈ [x]% ∩ A′

existiert.

Bemerkung 1.75 Auf der Faktormenge F(V )/ ≡ aller aussagenlogischen For-meln kann man auch die aussagenlogischen Junktoren ¬,∧ und ∨ definie-ren, indem man die Aquivalenzklassen reprasentantenweise verknupft, also etwa[x]∧ [y] := [x∧y]. Dann folgt aus Satz 1.10, daß hierdurch eine Boolesche Algebraentsteht. Die ausgezeichneten Elemente sind hierbei die Klasse [1], die aus allenTautologien besteht, und die Klasse [0], die genau die widerspruchlichen Formelnenthalt.

Beispiel 1.76 Die in Aufgabe 1.48 eingefuhrten Restklassen [r]n modulo n bil-den fur jede naturliche Zahl n > 0 eine Partition von Z. Die zugehorige Aquiva-lenzrelation ≡ modn wird bestimmt durch a ≡ b modn ↔ a− b ∈ nZ fur allea, b ∈ Z und gelesen als “a ist kongruent zu b modulo n”. Die Faktormenge wirdmeist als Z/(n) notiert.

Beispiel 1.77 Auf der Menge Z := N20 wird durch (a, b) ∼ (c, d) :↔ a+d = b+c

fur alle a, b, c, d ∈ N0 eine Aquivalenzrelation definiert. Fur die Aquivalenzklassenschreibt man a− b := [(a, b)]∼ und nennt sie Differenzen der naturlichen Zahlena und b. Auf der Menge Z := Z/ ∼ dieser Aquivalenzklassen kann man durch



(a − b) + (c − d) = (a + c) − (b + d) eine Addition und durch (a − b) · (c −d) := (ac+ bd)− (ad+ bc) eine Multiplikation definieren. Auf diese Weise erhaltman die ganzen Zahlen Z mit den bekannten Rechengesetzen. Die Menge N0 dernaturlichen Zahlen ist in der Form N0 = {a− 0 | a ∈ N0} in Z enthalten.

Beispiel 1.78 Auf der Menge Q = Z × (Z \ {0}) wird durch (a, b) ∼ (c, d) :↔ad = bc fur alle (a, b), (c, d) ∈ Q eine Aquivalenzrelation definiert. Fur die Aqui-valenzklassen schreibt man a

b:= [(a, b)]∼ und nennt sie Quotienten der ganzen

Zahlen a und b 6= 0, wobei a der Zahler und b der Nenner dieses Bruches ist. Aufder Menge Q := Q/ ∼ dieser Aquivalenzklassen kann man durch a

b+ c

d:= ad+bc

bd

eine Addition und durch ab· c

d:= ac

bdeine Multiplikation definieren. Auf diese Wei-

se erhalt man die rationalen Zahlen Q mit den bekannten Rechengesetzen. DieMenge Z der ganzen Zahlen ist in der Form Z = {a

1| a ∈ Z} in Q enthalten.

Bemerkung 1.79 Ein in vielen innermathematischen Anwendungen benotigtesHilfsmittel zum Nachweis der Existenz bestimmter Mengen stellt das Auswahl-axiom dar:

Ist M ein Mengensystem paarweise disjunkter Mengen mit ∅ 6∈ M, dann gibt eseine Auswahlmenge A, so daß fur alleX ∈ M die SchnittmengeX∩A einelementigist. Mit anderen Worten, A “wahlt” aus jeder Menge aus M genau ein Element“aus”.

Offensichtlich ist das Auswahlaxiom gleichwertig damit, daß jede Aquivalenzre-lation auf jeder Menge ein Reprasentantensystem besitzt.

Folgerung 1.80 Es sei % eine Praordnung auf A. Dann ist ∼:= % ∩ %−1 eineAquivalenzrelation auf A und auf der Faktormenge A/ ∼ wird durch

[a]∼ ≤ [b]∼ :↔ a%b(129)

fur alle [a]∼, [b]∼ ∈ A/ ∼ eine partielle Ordnung definiert.

Beweis: Da % reflexiv ist, gilt dasselbe fur %−1 und damit auch fur ∼= % ∩ %−1.Aus a ∼ b folgt a%b und a%−1b und damit b%−1a und b%a, also b ∼ a. Damit ist∼ auch symmetrisch. Aus a ∼ b und b ∼ c folgen a%b, b%c, a%−1b und b%−1c. DieTransitivitat von % ergibt jetzt a%c und a%−1c, also auch a ∼ c. Damit ist ∼ eineAquivalenzrelation.

Zunachst ist zu zeigen, daß die Definition von ≤ reprasentantenunabhangig ist:Seien dazu a, a′, b, b′ ∈ A mit [a]∼ = [a′]∼ und [b]∼ = [b′]∼, also a ∼ a′ und b ∼ b′.



Dann folgen a%a′ und b%b′ sowie a′%a und b′%b. Gilt nun a%b, so gelten a′%a, a%bund b%b′, mit der Transitivitat also auch a′%b′. Daher wird auch [a′]∼ ≤ [b′]∼definiert.

Die Reflexivitat und Transitivitat ubertragen sich sich durch (129) von % unmit-telbar auf ≤.

Gilt nun [a]∼ ≤ [b]∼ und [b]∼ ≤ [a]∼, so folgt a%b und b%a und daher auch a%−1b,also a ∼ b und damit [a]∼ = [b]∼. �

Definition 1.81 Es sei (A,≤) eine partiell geordnete Menge und T ⊆ A. EinElement a ∈ A heißt

obere (untere) Schranke von T , wenn t ≤ a (a ≤ t) fur alle t ∈ T gilt,

maximales (minimales) Element von T , wenn a ∈ T und a ≤ t→ a = t (t ≤ a→a = t) fur jedes t ∈ T gilt,

großtes (kleinstes) Element von T , wenn a ∈ T und t ≤ a (a ≤ t) fur jedes t ∈ Tgilt.

Die Menge T heißt nach oben (nach unten) beschrankt (in A), wenn sie eine obere(untere) Schranke besitzt. Ist beides der Fall, nennt man T beschrankt (in A).

Die partiell geordnete Menge (A,≤) erfullt die Minimalbedingung, wenn jedenichtleere Teilmenge T von A ein minimales Element besitzt.

Eine total geordnete Menge (A,≤) heißt wohlgeordnet, wenn sie die Minimalbe-dingung erfullt.

Folgerung 1.82 a) Jedes großte (kleinste) Element ist eindeutig bestimmt undstets auch maximal (minimal).

b) In einer wohlgeordneten Menge (A,≤) besitzt jede nichtleere Teilmenge T auchein kleinstes Element.

Beweis: a) Sind a, a′ ∈ T großte Elemente von T , so gilt a′ ≤ a, da a großtesElement ist, und ebenso a ≤ a′, da a′ großtes Element ist. Mit der Antisymmetrievon ≤ folgt a = a′, also die Eindeutigkeit. Ist nun a ∈ T großtes Element von T ,dann gilt t ≤ a fur alle t ∈ T und daher ergibt sich aus t ≤ a wiederum mit derAntisymmetrie sofort a = t. Also ist a maximal.

Die Behauptungen uber kleinste und minimale Elemente folgen dual!



b) Sei T 6= ∅ Teilmenge von A. Dann existiert wegen der Minimalbedingungein minimales Element a ∈ T . Fur alle t ∈ T gilt wegen der Linearitat derOrdnungsrelation aber t ≤ a oder a ≤ t. Wegen der Minimalitat von a ist dahernur a ≤ t moglich. Also ist a kleinstes Element von T . �

Beispiel 1.83 Betrachtet man fur eine n-elementige Menge M mit n > 1 dieMenge A = P(M)\{∅,M} mit der Inklusion ⊆ als partieller Ordnungsrelation, soist (A,⊆) eine partiell geordnete Menge, in der die n Einermengen {m} minimaleund die n−1-elementigen Mengen M \{m} fur jedes m ∈M maximale Elementesind.

Jede endliche Teilmenge T der ganzen Zahlen Z besitzt in der total geordne-ten Menge (Z,≤) ein großtes und ein kleinstes Element, ist also insbesonderebeschrankt. Dagegen besitzt die unendliche Teilmenge N0 zwar ein kleinstes Ele-ment 0 aber keine obere Schranke.

Die total geordnete Menge (N0,≤) erfullt die Minimalbedingung, ist also wohlge-ordnet.

Ist M = {a1, . . . , an}, so definiert ai ≤ aj :↔ i ≤ j eine totale Ordnung auf Mund wegen der Endlichkeit besitzt jede nichtleere Teilmenge von M naturlich einkleinstes Element. Also ist (M,≤) wohlgeordnet.

Die leere Menge ∅ besitzt als einzige binare Relation die leere Relation ∅ = ∅× ∅und diese ist eine totale Ordnungsrelation auf ∅. Offensichtlich ist sie auch eineWohlordnung. Dagegen ist die leere Menge nicht beschrankt, da keine Schrankenexistieren!

Definition 1.84 Es sei (A,≤) eine partiell geordnete Menge und T ⊆ A. EinElement a ∈ A heißt obere Grenze oder Supremum von T , wenn es obere Schrankevon T ist und fur alle oberen Schranken s ∈ A von T bereits a ≤ s gilt, wenn alsoa kleinstes Element in der Menge der oberen Schranken von T ist. Man schreibtdann a = supA T . Dual wird eine untere Grenze oder Infimum von T definiertund als infA T notiert.

Existieren in (A,≤) fur jede Zweiermenge T = {a, b} sowohl ein Supremum alsauch ein Infimum, so nennt man (A,≤) einen Verband. Man schreibt dann aucha∧b := inf{a, b} und a∨b := sup{a, b}. Existieren Supremum und Infimum sogarfur jede Teilmenge von A, so spricht man von einem vollstandigen Verband.

Beispiel 1.85 Durch das folgende Hasse-Diagramm wird auf der Menge A ={0, a, b, c, d, 1} eine partielle Ordnung definiert.



0

1

c

a b

d

Die Teilmenge T1 = {a, b, c, d} besitzt die maximalen Elemente c und d, also keingroßtes Element, und die minimalen Elemente a und b, also auch kein kleinstesElement. Die Menge T2 = {a, b} besitzt die oberen Schranken c, d und 1, aberkein Supremum, jedoch ist die einzige untere Schranke 0 naturlich Infimum vonT2. Es handelt sich also nicht um einen Verband.

Bemerkung 1.86 Man beachte, daß sich die Eindeutigkeit von Supremum bzw.Infimum im Falle ihrer Existenz aus Folgerung 1.82 ergeben.

Die Menge N0 bildet mit der Teilbarkeitsrelation | eine partiell geordnete Menge(N0, |), in der fur eine beliebige Teilmenge A das Infimum durch den großtengemeinsamen Teiler ggT (A) aller a ∈ A und das Supremum durch das kleinstegemeinsame Vielfache kgV (A) aller a ∈ A gegeben ist. Speziell ist ggT (N0) = 1und kgV (N0) = 0. Schrankt man die Teilbarkeitsrelation auf die Menge T (n)aller Teiler einer festen Zahl n ein, so bildet (T (n), |) ebenfalls einen endlichenund daher vollstandigen Verband. Fur (T (36), |) erhalt man das folgende Hasse-Diagramm. In ihm ist die Kette {3, 6, 18, 36} rot hervorgehoben.

1

2 3

9

36

12 18

4 6

Beim zweiten Beispiel, dem Teilerverband (T (30), |), ergibt sich dasselbe Bild wiebei der Potenzmenge (P({a, b, c}),⊆) in Bemerkung 1.69, beide halbgeordnetenMengen sind “irgendwie gleich”. Wir werden dies spater im Begriff der “Isomor-phie” prazisieren.



32

10 156

5

30

1

Folgerung 1.87 Ist M ⊆ P(A) ein beliebiges Teilsystem einer Potenzmenge, sogelten sup M =

⋃M und inf M =

⋂M in der partiell geordneten Menge (P(A),⊆).

Insbesondere hat man inf ∅ = A = sup P(A) und inf P(A) = ∅ = sup ∅ fur diebeiden extremen Falle M = ∅ und M = P(A). Die partiell geordnete Menge(P(A),⊆) ist daher ein vollstandiger Verband.

Beweis: Es werden die Behauptungen uber die Suprema gezeigt, die Behauptun-gen uber die Infima folgen dann dual.

Sei zunachst M = ∅ und B ⊆ A beliebig. Dann gilt C ⊆ B fur jedes C ∈ M, daes kein derartiges C gibt. Also ist B obere Schranke von M. Die kleinste obereSchranke ist daher das kleinste Element von P(A), also ∅. Daher gilt ∅ = sup M =sup ∅ und dies ist naturlich das Infimum von P(A).

Sei nun M 6= ∅ und V :=⋃

M ⊆ A. Ist dann M ∈ M eine beliebige Menge ausdiesem Mengensystem, so gilt x ∈ V fur alle x ∈ M , also M ⊆ V . Damit istV obere Schranke von M. Sei nun S eine beliebige obere Schranke von M undx ∈ V . Dann gibt es wenigstens ein M ∈ M mit x ∈ M . Wegen M ⊆ S folgtx ∈ S, also insgesamt V ⊆ S, und damit ist V kleinste obere Schranke, alsosup M = V =

⋃M. �

Beispiel 1.88 In der wohlgeordneten Menge (N0,≤) besitzt zwar jede nichtleereTeilmenge ein kleinstes Element und daher ein Infimum, aber kein Supremum,wenn sie nicht endlich ist und daher nicht nach oben beschrankt. Man kann diesen“Mangel” aber beheben, indem man ein neues Element ∞ 6∈ N0 hinzugibt unddie Wohlordnung ≤ von N0 auf N∞0 := N0 ∪ {∞} erweitert gemaß n <∞ fur allen ∈ N0. Dann besitzt in der ebenfalls wohlgeordneten Menge (N∞0 ,≤) sogar jedeTeilmenge T ein Infimum und ein Supremum, also ist (N∞0 ,≤) ein vollstandigerVerband.

Auf der linear geordneten Menge (Z,≤) reicht es dagegen nicht, ein großtes Ele-ment ∞ zu adjungieren (lat. adiungere = anbinden), um einen vollstandigenVerband zu erhalten. Hier gibt es auch nach unten unbeschrankte Mengen. Man



fugt also zwei Elemente +∞ und −∞ hinzu und erweitert die Ordnung von Zauf Z±∞ := Z ∪ {+∞,−∞} durch −∞ < x < +∞ fur alle x ∈ Z. Dann ist auch(Z±∞,≤) ein vollstandiger Verband.

Auf die gleiche Weise kann man auch die linear geordnete Menge der reellenZahlen (R,≤) zu einem vollstandigen Verband (R±∞,≤) erweitern, was allerdingserheblich aufwendiger zu beweisen ist.

Warum funktioniert diese Konstruktion nicht bei den rationalen Zahlen Q?

Folgerung 1.89 a) Es sei E ⊆ E(A) ⊆ P(A×A) eine Menge von Aquivalenzre-lationen auf A. Dann ist auch

⋂E eine Aquivalenzrelation auf A.

b) Ist % ∈ BA eine beliebige binare Relation auf A, dann existiert eine kleinsteAquivalenzrelation %∗ auf A mit % ⊆ %∗.

c) Fur %, σ ∈ E(A) ist % ◦ σ genau dann ebenfalls eine Aquivalenzrelation, wenn% ◦ σ = σ ◦ % gilt.

Beweis: a) Fur E = ∅ ist⋂

E = ωA nach Folgerung 1.87 und dies ist eineAquivalenzrelation auf A. Sei nun E 6= ∅ und σ :=

⋂E. Fur jedes % ∈ E gilt dann

ιA ⊆ %, also auch ιA ⊆ σ. Also ist σ reflexiv. Fur (a, b) ∈ σ gilt (a, b) ∈ % unddamit wegen der Symmetrie auch (b, a) ∈ %. Also gilt (b, a) ∈ σ und σ ist auchsymmetrisch. Sind schließlich (a, b), (b, c) ∈ σ so folgt wiederum (a, b), (b, c) ∈ %und wegen der Transitivitat (a, c) ∈ %. Dies zeigt auch (a, c) ∈ σ und σ isttransitiv.

b) Stets ist die Allrelation ωA eine Aquivalenzrelation auf A mit % ⊆ ωA. Da-her liefert %∗ :=

⋂E = inf E fur E = {σ ∈ E(A) | % ⊆ σ} 6= ∅ die gesuchte

Aquivalenzrelation.

c) Ubung! �

Die folgenden Satze, die fur gewisse Grundlagenfragen der Mathematik sehr wich-tig sind, konnen im Rahmen einer axiomatisch aufgebauten Mengenlehre mit teil-weise erheblichem Aufwand bewiesen werden. In dieser Einfuhrung seien sie ohneBeweis zitiert.

Satz 1.90 Lemma von Zorn (Max August Zorn, 1906 - 1993) Besitzt in derpartiell geordneten Menge (A,≤) jede Kette eine obere Schranke, dann gibt es einmaximales Element in A.


http://de.wikipedia.org/wiki/Max_August_Zorn


Satz 1.91 Wohlordnungssatz Jede Menge kann wohlgeordnet werden.

Es kann sogar allgemeiner gezeigt werden:

Theorem 1.92 Es sind aquivalent:

(1) Auswahlaxiom

(2) Wohlordnungssatz

(3) Lemma von Zorn

1.4.4 Abbildungen

Definition 1.93 Sind A undB Mengen, dann versteht man unter einer partiellenAbbildung f aus A in B eine rechtseindeutige Relation f ⊆ A × B. Ist f nochlinkstotal, so spricht man einfach von einer Abbildung. Man schreibt f : D(f) →B fur partielle Abbildungen und f : A → B fur Abbildungen. Das zu x ∈ D(f)eindeutig bestimmte y ∈ B mit (x, y) ∈ f wird auch in der Form y = f(x)notiert. Man nennt den Wertebereich W (f) = f(A) bei Abbildungen auch dasBild von f und schreibt Imf (lat. imago = Bild). Fur Teilmengen Y ⊆ B nennt

man f−1(Y ) auch das Urbild von Y .

Eine rechtstotale Abbildung f : A → B heißt surjektiv oder eine Surjektion(franz. sur = auf), eine linkseindeutige Abbildung heißt eineindeutig, injektivoder Injektion (lat. inicere = hineinwerfen). Eine Abbildung, die sowohl surjektivals auch injektiv ist, nennt man bijektiv (lat. bis = zweimal) oder eine Bijektionzwischen A und B.

Beispiel 1.94 Die identische Relation ιA ist auf jeder Menge A eine bijektiveAbbildung ιA : A→ A. Sie wird daher auch identische Abbildung auf A genannt.

Fur jede Teilmenge A ⊆ B ist inA = {(a, a) | a ∈ A} ⊆ A × B eine injektiveAbbildung. Sie wird die naturliche Injektion oder Einbettung von A in B genannt.

Ist M = M1 × . . .×Mn 6= ∅ ein kartesisches Produkt, dann wird fur i = 1, . . . , ndurch πi(x1, . . . , xi, . . . , xn) := xi eine surjektive Abbildung πi : M → Mi defi-niert, die Projektion auf die i-te Komponente von M . Man nennt eine TeilmengeA ⊆ M auch ein subdirektes Produkt der Mengen Mi, wenn πi(A) = Mi furi = 1, . . . , n gilt.



Aufgabe 1.95 Abbildungen, die Teilmengen der Zahlenbereiche N0, Z, Q, R oderC (komplexe Zahlen) aufeinander abbilden, werden im allgemeinen Funktionengenannt, beispielsweise in der Zahlentheorie, der Analysis oder der Funktionen-theorie. Untersuchen Sie die auf Ihrem Taschenrechner (oder in Ihrer Lieblings-Programmiersprache) realisierten Funktionen hinsichtlich der in Definition 1.93eingefuhrten Begriffe. Welches sind bei bijektiven Funktionen die Umkehrfunk-tionen? Woher kennt der Rechner eigentlich die jeweiligen Funktionswerte mitderartiger Genauigkeit?

Folgerung 1.96 a) Fur jede Abbildung f : A → B ist die Einschrankungf |A×f(A): A→ f(A) surjektiv.

b) Ist f : A→ B injektiv, dann ist auch die Einschrankung f |A′ := f |A′×B: A′ →B fur jede Teilmenge A′ ⊆ A injektiv.

c) Fur Abbildungen f : A → B und g : B → C ist auch f ◦ g : A → C eineAbbildung.

d) Ist f : A → B bijektiv, dann ist auch f−1 : B → A eine bijektive Abbildung.Sie wird die Umkehrabbildung von f genannt.

e) Ist f : A → B eine Abbildung, dann ist kerf := {(x, y) ∈ A2 | f(x) = f(y)}eine Aquivalenzrelation auf A.

f) Fur Abbildungen f, g : A→ B gilt f = g ↔ ∀x ∈ A : f(x) = g(x).

Beweis: a) und b) sind trivial.

c) Fur jedes x ∈ A gibt es genau ein y ∈ B mit y = f(x) und fur jedes y ∈ Bgibt es genau ein z ∈ C mit z = g(y) = g(f(x)). Also gibt es zu jedem x ∈ Agenau ein z ∈ C mit (x, z) ∈ f ◦ g. Damit ist f ◦ g linkstotal und rechtseindeutig,also eine Abbildung. Wie hier schon geschehen, schreibt man meist z = g(f(x))fur z = (f ◦ g)(x).

d) Ist f : A → B bijektiv, so ist sie links- und rechtstotal sowie links- undrechtseindeutig. Damit ist dann f−1 als Relation rechts- und linkstotal sowierechts- und linkseindeutig, also der Reihe nach: uberall definiert, surjektiv, eineAbbildung und injektiv, d. h. ebenfalls eine Bijektion.

e) Dies folgt aus der Tatsache, daß die Gleichheit “=” eine Aquivalenzrelationauf f(A) ist!

f) Gilt f = {(x, f(x)) | x ∈ A} = g = {(x, g(x)) | x ∈ A}, so folgt aus der jewei-ligen Rechtseindeutigkeit sofort f(x) = g(x) fur alle x ∈ A. Hat man umgekehrt



diese Gleichheiten, so folgt wiederum aus der Rechtseindeutigkeit von f und gals Abbildungen die Gleichheit f = g als Relationen. �

Folgerung 1.97 Fur alle Abbildungen f : A → B und g : B → C gelten diefolgenden Aussagen.

a) Es ist f genau dann injektiv, wenn f(x) = f(x′) → x = x′ fur alle x, x′ ∈ Agilt.

b) Sind f und g beide injektiv (surjektiv, bijektiv), so ist auch f ◦ g injektiv(surjektiv, bijektiv).

c) Ist f ◦ g injektiv, dann ist f injektiv.

d) Ist f ◦ g surjektiv, dann ist auch g surjektiv.

e) Ist f ◦ g bijektiv, dann ist f injektiv und g surjektiv.

f) Genau dann ist f bijektiv, wenn f ◦ f−1 = ιA und f−1 ◦ f = ιB gelten.

Beweis: a) Ist f : A → B eine injektive Abbildung und gilt f(x) = f(x′) =y ∈ B fur x, x′ ∈ A, so gelten (x, y) ∈ f und (x′, y) ∈ f , woraus wegen derLinkseindeutigkeit sofort x = x′ folgt. Liegen umgekehrt die Paare (x, y) und(x′, y) in f ⊆ A × B, so gilt, da f Abbildung ist, f(x) = y = f(x′). Damit folgtaus der vorausgesetzten Implikation dann x = x′, also die Linkseindeutigkeit.

b) Sind f und g injektiv, so folgt aus (f ◦g)(x) = g(f(x)) = g(f(x′)) = (f ◦g)(x′)wegen der Injektivitat von g aus a) zunachst f(x) = f(x′) und hieraus wegen derInjektivitat von f dann ebenso mit a) x = x′. Also ist auch f ◦ g injektiv.

Sind f und g surjektiv, so gelten f(A) = B und g(B) = C, also (f ◦ g)(A) =g(f(A)) = g(B) = C, und damit die Surjektivitat dieser Verkettung.

Hieraus ergibt sich unmittelbar die Behauptung fur die Bijektivitat.

c) Ist f ◦ g injektiv und gilt f(x) = f(x′), so folgt (f ◦ g)(x) = g(f(x)) =g(f(x′)) = (f ◦ g)(x′), und damit aus der Injektivitat auch x = x′. Mit a) folgtdie Behauptung.

d) Ist f ◦g surjektiv und c ∈ C, so gibt es ein x ∈ A mit c = (f ◦g)(x) = g(f(x)).Dann erfullt y := f(x) ∈ B aber auch g(y) = c, d. h. g ist rechtstotal, alsosurjektiv.

e) Dies folgt unmittelbar aus c) und d).



f) Ist f bijektiv, dann nach Folgerung 1.96 d) auch f−1. Zu x ∈ A gibt es eineindeutig bestimmtes y ∈ B mit (x, y) ∈ f , also (y, x) ∈ f−1, und zu diesem yist x = f−1(y) eindeutig bestimmt, da f−1 Abbildung ist. Es folgt (f ◦ f−1)(x) =f−1(f(x)) = f−1(y) = x, also f ◦ f−1 = ιA. Vertauscht man nun die Rollen vonf und f−1 (beides sind bijektive Abbildungen!) erhalt man f−1 ◦ f = ιB.

Gelten umgekehrt die beiden Gleichungen. Zunachst ist f−1 als Relation rechts-eindeutig, denn aus (y, x), (y, x′) ∈ f−1 folgt (x, y), (x′, y) ∈ f und daher (x, x′) ∈f ◦ f−1 = ιA, also x = x′. Dann ist f−1 aber auch linkstotal, denn fur y ∈ B gilt(y, y) ∈ ιB = f−1 ◦ f . Daher existiert ein x ∈ A mit (y, x) ∈ f−1 (und (x, y) ∈ f).Insgesamt ist f−1 : B → A ebenso eine Abbildung wie f : A → B. Aus derInjektivitat von ιA = f ◦ f−1 folgt nun mit c) die Injektivitat von f und aus derSurjektivitat von ιB = f−1 ◦ f die Surjektivitat von f . �

Lemma 1.98 Sei A eine Menge und % ∈ E(A) eine Aquivalenzrelation auf A.Dann ist die Abbildung ν : A→ A/% gemaß ν(x) := [x]% fur alle x ∈ A surjektivund es ist kerν = %. Weiterhin ist ν injektiv und damit bijektiv genau dann, wenn% = ιA gilt.

Beweis: Zu [x]% ∈ A/% ist x ∈ A ein Reprasentant dieser Klasse, der von ν aufdiese Klasse abgebildet wird. Also ist ν surjektiv. Es ist (x, x′) ∈ kerν gleichwertigzu ν(x) = ν(x′) nach Definition von kerν, und daher zu [x]% = [x′]%. Da %Aquivalenzrelation ist, ist dies wiederum gleichwertig zu (x, x′) ∈ %. Dies zeigtkerν = %. Es ist % = ιA genau dann, wenn jede Klasse [x]% aus genau einemElement besteht, also gleich {x} ist. Dies ist aber gleichwertig damit, daß ν(x) ={x} fur alle x ∈ A gilt. Dies zeigt dann die Injektivitat von ν. Ist andererseits νnicht injektiv, so gibt es x 6= x′ in A mit ν(x) = [x]% = ν(x′) und damit (x, x′) ∈ %also ist dann % 6= ιA. �

Man nennt die Abbildung ν : A → A/% auch die naturliche Abbildung oderkanonische Projektion von A auf A/%.

Satz 1.99 Erster Abbildungssatz Es sei f : A → B eine Abbildung, ν :A → A/kerf die kanonische Projektion und inf(A) die Injektion von f(A) ⊆ Bin B. Dann existiert genau eine bijektive Abbildung ϕ : A/kerf → f(A) mitf = ν ◦ ϕ ◦ inf(A).

Beweis: Definiere ϕ : A/kerf → f(A) durch ϕ([x]kerf ) := f(x) fur alle[x]kerf ∈ A/kerf . Dann ist zunachst die Reprasentantenunabhangigkeit oderWohldefiniertheit zu zeigen: Fur alle x, x′ ∈ A mit [x]kerf = [x′]kerf muß bereits



f(x) = f(x′) gelten. Aus [x]kerf = [x′]kerf folgt aber (x, x′) ∈ kerf nach Defini-tion dieser Aquivalenzklassen. Daher gilt auch f(x) = f(x′) nach Definition derRelation kerf .

Es ist ϕ surjektiv, denn zu y ∈ f(A) gibt es ein x ∈ A mit f(x) = y und dahergilt fur die Klasse [x]kerf ∈ A/kerf bereits ϕ([x]kerf ) = y.

Es ist ϕ auch injektiv und damit bijektiv, denn aus ϕ([x]kerf ) = ϕ([x′]kerf ) folgtf(x) = f(x′) und damit (x, x′) ∈ kerf , also auch [x]kerf = [x′]kerf .

Es ist f = ν ◦ ϕ ◦ inf(A), denn fur alle x ∈ A gilt f(x) = inf(A)(f(x)) =inf(A)(ϕ([x]kerf )) = inf(A)(ϕ(ν(x))) = ν ◦ ϕ ◦ inf(A)(x), und wegen Folge-rung 1.96 d) gilt die Gleichheit der Abbildungen.

Schließlich ist ϕ eindeutig bestimmt, denn ist auch ϕ′ : A/kerf → f(A) mitf = ν ◦ ϕ′ ◦ inf(A), so folgt aus inf(A)(ϕ(ν(x)) = inf(A)(ϕ

′(ν(x)) fur alle x ∈ Azunachst ϕ(ν(x)) = ϕ′(ν(x)) aus der Injektivitat von inf(A). Da ν surjektiv ist,folgt ϕ([x]kerf ) = ϕ′([x]kerf ) fur alle [x]kerf ∈ A/kerf , also ϕ = ϕ′ wiederumwegen Folgerung 1.96 d). �

Definition 1.100 Fur Mengen A und B bezeichne AB := {f | f : B → A},also die Menge aller Abbildungen von B in A. Speziell fur B = {1, . . . , n}, alsof : {1, . . . , n} → A schreibt man ai := f(i) fur i = 1, . . . , n und notiert f kurz alsn-Tupel f = (a1, . . . , an) ∈ An anstelle von f = {(1, a1), . . . , (n, an)} ⊆ B × A.Fur B = N0 erhalt man analog die (unendlichen) Folgen (ai)i∈N0 . Ist B = I einebeliebige nichtleere Menge, die in diesem Zusammenhang Indexmenge genanntwird, so spricht man von f auch als einer indizierten Familie und notiert diesein der Form (ai)i∈I oder (ai | i ∈ I). Ist hierbei A = P(M), so nennt man (Ai)i∈I

eine Mengenfamilie der Mengen Ai ⊆M .

Bemerkung 1.101 Mengenfamilien stellen also eine Verallgemeinerung der “un-geordneten” Mengensysteme dar, indem sie es ermoglichen, uber den jeweiligenIndex “gezielt” einzelne Elemente des Mengensystems anzusprechen und es auchgestattet ist, daß ein- und dieselbe Menge mehrfach in der Familie vorkommt,was bei Mengensystemen wegen des Extensionalitatsaxioms nicht der Fall ist.

1.4.5 Kardinalzahlen

Definition 1.102 Zwei Mengen A und B heißen gleichmachtig, in Zeichen: A ∼B, wenn es eine Bijektion f : A→ B gibt.



Man nennt eine Menge A abzahlbar unendlich, wenn A ∼ N0 gilt. Eine endlicheoder abzahlbar unendliche Menge heißt abzahlbar. Eine nicht abzahlbare Mengewird uberabzahlbar genannt.

Man schreibt ℵ0 := |N0| = |N | (“Aleph Null” ist die “Machtigkeit” von N0; Alephist der erste Buchstabe des hebraischen Alphabets) fur jede abzahlbar unendlicheMenge N . Durch |M | > ℵ0 kurzt man dann die Aussage “M ist uberabzahlbar”ab. Unter einer Kardinalzahl versteht man die Machtigkeit einer Menge, alsodie Anzahl ihrer Elemente. Ist die Menge unendlich, so spricht man von einertransfiniten Kardinalzahl.


A ∼ A,(130)

A ∼ B → B ∼ A,(131)

A ∼ B ∧B ∼ C → A ∼ C.(132)

Die Ahnlichkeit ∼ ist also auf jedem Mengensystem M eine Aquivalenzrelation.

Beweis: (130) gilt wegen Beispiel 1.94, (131) wegen Folgerung 1.96 d), (132)wegen Folgerung 1.97. �

Beispiel 1.104 a) Es ist N ∼ N0, da die Nachfolgerfunktion f : N0 → Ngemaßf(n) = n+ 1 fur alle n ∈ N0 bijektiv ist. Es ist namlich f−1(n) = n− 1 furalle n ∈ N die Umkehrabbildung.

Hieraus folgt durch geeignete Einschrankung von f sofort: {0, . . . , n − 1} ∼{1, . . . , n} und daher {0, . . . , n− 1} ∼ {a1, . . . , an} fur jede n-elementige Menge.Die Kardinalzahl einer endlichen Menge ist also stets eine naturliche Zahl.

Weiterhin folgt (E ∪ N0) ∼ N0 fur jede endliche Menge E. Die Vereinigung einerendlichen und einer abzahlbar unendlichen Menge ist stets abzahlbar unendlich.

b) Es ist Z ∼ N0, da die Abbildung f : N0 → Z gemaß f(n) = n2

fur gerades nund f(n) = −n+1

2fur ungerades n bijektiv ist.

Hieraus ergibt sich weiter (N ∪N0) ∼ N0 fur jede abzahlbar unendliche Menge Nund daher: Endliche Vereinigungen abzahlbar unendlicher Mengen sind abzahlbarunendlich.

c) Erstes Cantorsches Diagonalverfahren: Es ist N × N ∼ N, da die Abbildung

f : N× N → N gemaß f(n,m) = n(n+1)2

+ (m+1)(m+2)2

+ nm− 1 bijektiv ist.



Hieraus folgt Q+ ∼ N und daraus dann Q ∼ N0 oder allgemein: Die abzahlbareVereinigung abzahlbarer Mengen ist abzahlbar.

Bemerkung 1.105 Man kann auch fur unendliche oder transfinite Kardinal-zahlen wie ℵ0 Summen und Produkte definieren und dann die eben bewiesenenAussagen durch Gleichungen ausdrucken. Wir werden diese aber in dieser Vorle-sung nicht weiter benutzen. Fur alle n ∈ N0 gelten:

n+ ℵ0 = ℵ0,

ℵ0 + ℵ0 = ℵ0,

0 · ℵ0 = 0,

n · ℵ0 = ℵ0 (n 6= 0),

ℵ0 · ℵ0 = ℵ0.

Beispiel 1.106 Ist M ∼ N0 eine abzahlbar unendliche Menge und f : N0 → Meine Bijektion, dann wird analog wie im Beispiel 1.83 fur endliche Mengen durchf(i) ≤ f(j) :↔ i ≤ j eine Wohlordnung auf M definiert. Dies beweist denWohlordnungssatz zumindest fur abzahlbare Mengen.

Satz 1.107 Jede Teilmenge einer abzahlbaren Menge ist abzahlbar.

Beweis: Sei M ⊆ N und N abzahlbar. Fur endliches N oder endliches M istdie Behauptung offensichtlich. Es bleibt der Fall N ∼ N0 und M unendlich zubetrachten. Dann gibt es eine Bijektion f : N0 → N , also N = {ai = f(i) | i ∈ N0}mit paarweise verschiedenen ai. Wegen M ⊆ N und M unendlich existiert eineTeilfolge (aik)k∈N0 mit M = {aik | k ∈ N0} und naturlich sind auch diese aik

paarweise verschieden. Daher ist g : N0 → M mit g(k) = aik eine Bijektion undfolglich M ∼ N0, also M abzahlbar. �

Satz 1.108 Satz von Cantor Fur jede Menge A gilt A 6∼ P(A). Insbesondereist P(N0) uberabzahlbar.

Beweis: Ware f : A → P(A) eine (sogar nur) surjektive Abbildung, dann gabees zu X := {x ∈ A | x /∈ f(x)} ein x0 ∈ A mit f(x0) = X. Der Fall x0 ∈ Xfuhrt zu x0 6∈ f(x0) = X, also einem Widerspruch. Aber auch der Fall x0 6∈ X,der zu x0 ∈ f(x0) = X fuhrt, liefert einen Widerspruch. Nach dem PlatonischenFalschheitskriterium (52) kann es daher kein derartiges x0 ∈ A geben, also kann fnicht surjektiv und daher auch nicht bijektiv sein. In P(N0) liegen die abzahlbar



unendlich vielen paarweise verschiedenen Einermengen {n} fur n ∈ N0, daherkann P(N0) nicht endlich sein. Nach dem ersten Teil des Satzes ist P(N0) aberauch nicht abzahlbar unendlich. �

Wir zeigen nun noch, daß die reellen Zahlen R, also die Menge aller Dezimalzahlen,uberabzahlbar ist. Wegen N0 ⊆ R kann sie naturlich nicht endlich sein.

Lemma 1.109 a) Es gibt eine bijektive Abbildung f : (−1, 1) → R, also(−1, 1) ∼ R fur dieses offene Intervall.

b) Fur jedes nichtleere offene Intervall (a, b) ⊆ R ist b − a 6= 0 und daher g :(a, b) → (0, 1) mit g(x) = 1

b−a(x− a) eine Bijektion. Also gilt (0, 1) ∼ R.

Beweis: a) Vorlesung!

b) Es ist g−1 : (0, 1) → (a, b) gemaß g−1(x) = (b − a)(x + ab−a

) offensichtlich dieUmkehrabbildung. Also gilt speziell (0, 1) ∼ (−1, 1). Mit a) und der Transitivitatvon ∼ folgt hieraus die letzte Behauptung. �

Satz 1.110 Zweites Cantorsches Diagonalverfahren Das offene Einheits-intervall (0, 1) und damit auch R ist uberabzahlbar.

Beweis: Jedes x ∈ (0, 1) werde durch einen nicht abbrechenden Dezimalbruchx = 0.x0x1x2x3 . . . dargestellt, wobei fur abbrechende Dezimalbruche immer dieeindeutig bestimmte alternative Darstellung mit Periode 9 gewahlt werde. Wegenx 6= 1 gibt es aber stets mindestens eine Stelle xi 6= 9. Angenommen, es gabe eineBijektion f : N0 → (0, 1). Dann kann man alle Dezimalbruche aus (0, 1) auflistendurch

f(0) = x0 = 0.x00x01x02 . . . ,

f(1) = x1 = 0.x10x11x12 . . . ,

f(2) = x2 = 0.x20x21x22 . . . ,...

Definiere nun die Zahl y = 0.y0y1y2 . . . durch folgende Vorschrift. Es sei yi = 1,falls xii ∈ {0, 2, . . . , 9}, und yi = 2, falls xii = 1 gilt. Dann ist y ∈ (0, 1) undy 6= xi fur jedes i ∈ N0, also f nicht surjektiv. Es kann daher keine derartigeBijektion geben. Dies zeigt (0, 1) 6∼ N0 und daher wegen der Transitivitat von ∼und dem vorhergehenden Lemma R 6∼ N0. �



Bemerkung 1.111 Man definiert nun eine neue Kardinalzahl c := |R| und nenntdiese die Machtigkeit des Kontinuums.

Es gilt dann ℵ0 < c und die sogenannte Kontinuumshypothese (CH) lautet:

Es gibt keine Kardinalzahl zwischen ℵ0 und c.

Es ist eines der fundamentalsten Ergebnisse der neueren Mathematik, daß dieKontinuumshypothese aus der axiomatischen Mengenlehre heraus weder wider-legbar ist (von Kurt Godel (1906 - 1978) 1938 gezeigt) noch beweisbar (von PaulCohen (1934 - 2007) 1963 gezeigt). Man kann also die bisher vorgestellte axioma-tische Mengenlehre auf zwei vollig verschiedene Arten erweitern, einmal indemman die Kontinuumshypothese als neues Axiom hinzunimmt, einmal indem manihre Negation hinzunimmt. Je nachdem existieren dann ganz unterschiedlicheunendliche Mengen.

Mit Hilfe der Gleichmachtigkeit ∼ von Mengen definierte Richard Dedekind (1831- 1916) die Endlichkeit einer Menge, ohne auf die naturlichen Zahlen zuruckzugrei-fen, wie folgt: Eine Menge M ist (Dedekind-)endlich, wenn ¬∃X : X ⊂M ∧X ∼M), wenn sie also keine zu ihr gleichmachtige echte Teilmenge besitzt.

Alfred Tarski (1902 - 1983) schlug dagegen die folgende Definition vor, die eben-falls keine naturlichen Zahlen benotigt: M ist (Tarski-)endlich, wenn (P(M),⊆)die Minimalbedingung erfullt.

Bertrand Russell wiederum orientierte sich mehr an der Definition der naturlichenZahlen als Nachfolgermenge, indem er definierte:M ist (Russell-)endlich, wennMin jedem Mengensystem enthalten ist, das die leere Menge und mit jeder Mengeauch deren Vereinigung mit einer beliebigen Einermenge enthalt.

Ohne Beweis sei hier nur angegeben:

Satz 1.112 Fur jede Menge M sind gleichwertig:

(1) M ist endlich.

(2) M ist Dedekind-endlich.

(3) M ist Tarski-endlich.

(4) M ist Russell-endlich.


http://de.wikipedia.org/wiki/Kurt_G%C3%B6del

http://de.wikipedia.org/wiki/Paul_Cohen_(Mathematiker)

http://de.wikipedia.org/wiki/Paul_Cohen_(Mathematiker)

http://de.wikipedia.org/wiki/Richard_Dedekind

http://de.wikipedia.org/wiki/Richard_Dedekind

http://de.wikipedia.org/wiki/Alfred_Tarski


Damit hat man dann auch alternative Charakterisierungen unendlicher Mengen,etwa mit Dedekind: Jede unendliche Menge besitzt eine echte Teilmenge, die zuihr gleichmachtig ist.

Aufgabe 1.113 Man beweise: Jede unendliche Menge enthalt eine abzahlbarunendliche echte Teilmenge.

1.4.6 Verknupfungen

Eine ausfuhrlichere Behandlung der hier nur kurz eingefuhrten algebraischenStrukturen erfolgt in der Algebra-Vorlesung:

www.mathe.tu-freiberg.de/∼hebisch/skripte/algebra/gruppen.pdf

Definition 1.114 Es sei n ∈ N0 und A eine Menge. Eine n-stellige Verknupfungoder (algebraische) Operation (lat. operare = verrichten, arbeiten) in A ist danneine Abbildung f : An → A.

Bemerkung 1.115 a) Eine nullstellige Operation in A 6= ∅ ist ein Element ausA, denn ist f : {∅} → A eine Abbildung, so ist diese eindeutig bestimmt alsf = {(∅, a)} fur ein a ∈ A. Konkrete Beispiele sind ∅ undM in jeder PotenzmengeA = P(M) oder 0 und 1 in den Zahlbereichen N0, Z und Q oder 0 und 1 in derMenge der Wahrheitswerte.

b) Einstellige Operationen sind also nichts weiter als beliebige Abbildungenf : A → A. Man nennt solche Abbildungen auch Transformationen der MengeA, beispielsweise bei den Transformationen der Zustandsmenge eines Automatenoder bei geometrischen Transformationen. Konkrete Beispiele sind die Komple-mentbildung f(B) = B fur B ⊆M in jeder Potenzmenge A = P(M), die Negati-on f(p) = ¬p in der Menge der aussagenlogischen Formeln, das Entgegengesetztef(a) = −a in den Zahlbereichen N0,Z und Q oder das Inverse f(a) = a−1 in derMenge Q \ {0}.

c) Binare Operationen f : A2 → A treten (ahnlich wie binare Relationen) inder Mathematik am haufigsten auf. Sie werden ebenfalls meistens in der Infixno-tation geschrieben, also z. B. a ∗ b anstelle von f(a, b). Konkrete Beispiele sindDurchschnitt ∩, Vereinigung ∪, Differenz \ und symmetrische Differenz ∆ injeder Potenzmenge, die Junktoren ∧,∨,→ und ↔ in der Menge der aussagen-logischen Formeln und die arithmetischen Operationen Summe + (lat. summus= das Oberste, Hochste) und Produkt · (lat. producere = hervorbringen) in denZahlbereichen.


http://www.mathe.tu-freiberg.de/~hebisch/skripte/algebra/gruppen.pdf


Definition 1.116 Eine binare Operation ∗ in einer Menge A 6= ∅ heißt

assoziativ (lat. associare = verbinden), wenn (a ∗ b) ∗ c = a ∗ (b ∗ c),

kommutativ (lat. commutare = vertauschen), wenn a ∗ b = b ∗ a,

idempotent, (lat. idem = selbst, potens = machtig), wenn a ∗ a = a

jeweils fur alle a, b, c ∈ A gilt. Die Menge A wird Tragermenge der Operati-on ∗ genannt und das Paar (A, ∗) ein Gruppoid. Unter der Ordnung von (A, ∗)versteht man dann die Kardinalzahl |A|. Ist die Operation ∗ assoziativ, so nenntman (A, ∗) eine Halbgruppe. Eine kommutative und idempotente Halbgruppe wirdHalbverband genannt.

Aufgabe 1.117 Welche Tasten Ihres Taschenrechners realisieren nullstellige,einstellige oder zweistellige Operationen? Welche zweistelligen Operationen da-von sind assoziativ, kommutativ, idempotent, welche nicht?

Beispiel 1.118 Fur jeden Verband (A,≤) bildet sowohl die Supremumsbildunga∨ b = sup{a, b} als auch die Infimumsbildung a∧ b = inf{a, b} eine binare Ope-ration, die assoziativ, kommutativ und idempotent ist. Daher sind dann (A,∨)und (A,∧) Halbverbande. Dies begrundet auch die Bezeichnung.

Beispiel 1.119 Fur (kleine) endliche Mengen A kann man binare Operationenauf A auch durch Cayley-Tafeln (Arthur Cayley, 1821 - 1895) definieren. Mannotiert in einer Tabelle, deren Kopfzeile und erste Spalte jeweils die Elemente vonA in einer festen linearen Ordnung enthalt, in der Zeile mit dem ersten Elementai ∈ A und in der Spalte zu dem Element aj ∈ A das Verknupfungsergebnisai ∗ aj ∈ A. Dann kan man beispielsweise die Kommutativitat der durch dieseTafel definierten Operation ∗ an der Symmetrie zur Hauptdiagonalen erkennen.Solche Tafeln eignen sich auch dazu, binare Operationen auf einem Rechner zuspeichern, ihre Gesetzmaßigkeiten zu uberprufen und mit ihnen zu rechnen.

Die Menge B = {0,1} kann durch 0 < 1 linear geordnet werden. Auf dieser Mengeexistieren dann stets das Supremum a∨ b und das Infimum a∧ b fur alle a, b ∈ B.Es handelt sich also um einen Verband. Die entsprechenden Cayley-Tafeln sinddann

∨ 0 10 0 11 1 1

und∧ 0 10 0 01 0 1


http://de.wikipedia.org/wiki/Arthur_Cayley


und dies sind genau die Ergebnisse der logischen Junktoren ∨ und ∧, wenn mansie auf die wahre Aussage 1 und die falsche Aussage 0 gemaß (7) - (10) anwendet.

Man kann ubrigens 0 und 1 auch mit den naturlichen Zahlen 0 und 1 identifizie-ren. Dann wird die oben angegebene Ordnung gerade die gewohnliche Ordnungfur diese Zahlen und ∧ und ∨ werden Minimum min und Maximum max furnaturliche Zahlen.

Beispiel 1.120 Fur jede Menge A ist die Menge TA := AA aller Abbildungenvon A in sich mit der Verkettung ◦ wegen (124) eine Halbgruppe (TA, ◦), dieTransformationshalbgruppe auf A. Insbesondere ist jede bijektive Abbildung f :A → A in TA enthalten. Diese Abbildungen werden auch Permutationen von Agenannt.

Aufgabe 1.121 Man beweise: Fur jede n-elementige Menge A gibt es genaun! := 1 · 2 · · ·n, gelesen: “n Fakultat”, Permutationen auf A.

Beispiel 1.122 Fur eine beliebige Menge A sei A+ :=⋃∞

n=1An :=

⋃{An | n ∈N}. Durch

(x1, . . . , xn) · (y1, . . . , ym) := (x1, . . . , xn, y1, . . . , ym) ∈ An+m ⊆ A+(133)

fur alle (x1, . . . , xn), (y1, . . . , ym) ∈ A+ wird dann eine assoziative binare Opera-tion auf A+ definiert, die Konkatenation genannt wird. Die Halbgruppe (A+, ·)heißt dann die freie Halbgruppe uber A. Man schreibt kurz x1 . . . xn anstelle von(x1, . . . , xn) und nennt dieses Element von An ⊆ A+ ein Wort der Lange n uberA. Speziell in der Informatik spricht man in diesem Zusammenhang auch vondem Alphabet A 6= ∅, nennt die Worte x1 . . . xn auch Strings uber A und dieElemente von A, also die Worte der Lange 1, Buchstaben, Zeichen oder Symbole.Unter einer formalen Sprache versteht man eine beliebige Teilmenge von A+.

Bemerkung 1.123 Es ist ∅+ = ∅ und A+ unendlich fur A 6= ∅. Fur einelemen-tige Mengen A = {a} gilt A+ = {an | n ∈ N}, also ist A+ abzahlbar unendlichund die freie Halbgruppe (A+, ·) ist kommutativ. Enthalt dagegen A mindestenszwei verschiedene Elemente a 6= b, so ist wegen ab 6= ba die freie Halbgruppe(A+, ·) niemals kommutativ. Bei abzahlbarem Alphabet A bleibt A+ aber immerabzahlbar, da An fur jedes n ∈ N abzahlbar ist und die abzahlbare Vereinigungabzahlbarer Mengen ebenfalls.

Fur jedes Alphabet A 6= ∅ gibt es also uberabzahlbar viele formale Sprachen, vondenen man mit endlichen Texten aber nur abzahlbar viele beschreiben kann.


1.5 Verallgemeinerte mengentheoretische Operationen 56

Konkrete Beispiele sind samtliche Programmiersprachen, aber auch die Mengealler aussagenlogischen Formeln uber dem Alphabet A = V ∪B∪{¬,∧,∨,→,↔}oder aller pradikatenlogischen Formeln uber dem Alphabet A = VE ∪ P ∪ B ∪{¬,∧,∨,→,↔,∀,∃}. Dasselbe gilt fur die Menge der in Aufgabe 1.3 betrachtetenarithmetischen Terme.

Aufgabe 1.124 Man versuche fur ein endliches Alphabet, etwa A = {a, b}, aufA+ eine lexikographische Ordnung zu definieren und damit A+ wohlzuordnen.

Eine ausfuhrliche Darstellung von Beschreibungsmechanismen fur formale Spra-chen findet man in dem Skript zur Automatentheorie

www.mathe.tu-freiberg.de/∼hebisch/skripte/formsprach/formsprach.pdf

1.5 Verallgemeinerte mengentheoretische Operationen

Definition 1.125 Ist (Ai)i∈I eine indizierte Mengenfamilie uber einer Menge M ,so definiert man⋃

i∈I Ai :=⋃{Ai | i ∈ I} und

⋂i∈I Ai :=

⋂{Ai | i ∈ I}.

Bemerkung 1.126 Durchschnitt und Vereinigung uber Mengenfamilien werdenalso uber Durchschnitt und Vereinigung von Mengensystemen definiert. Daherkommt es auf die Reihenfolge der Elemente dieser Mengenfamilie ebensowenigan, wie darauf, ob einzelne Mengen Ai mehrfach in der Familie auftreten. Insbe-sondere sind diese Operationen kommutativ, genauer: Es gilt

⋃i∈I Ai =

⋃i∈I Aπ(i)

und⋂

i∈I Ai =⋂

i∈I Aπ(i) fur jede Permutation π : I → I.

Außerdem ist⋃

i∈I Ai das Supremum von {Ai | i ∈ I} in (P(M),⊆), also diekleinste Menge, die alle Ai als Teilmengen umfaßt, und entsprechend

⋂i∈I Ai das

Infimum, also die großte Menge, die in allen Ai als Teilmenge enthalten ist.

Diese Definition verallgemeinert die schon weiter oben eingefuhrten Bezeichnun-gen

⋃ni=1Ai bzw.

⋃∞i=1Ai fur die Vereinigung und analog fur den Durchschnitt.

Satz 1.127 Es seien (Ai)i∈I und (Bi)i∈I Mengenfamilien uber derselben MengeM und C ⊆M . Dann gelten

(1) ∀j ∈ I :⋂

i∈I Ai ⊆ Aj ⊆⋃

i∈I Ai.


http://www.mathe.tu-freiberg.de/~hebisch/skripte/formsprach/formsprach.pdf


(2)⋂

i∈I Ai =⋃

i∈I Ai.

(3)⋃

i∈I Ai =⋂

i∈I Ai.

(4)⋃

i∈I(Ai ∪Bi) =⋃

i∈I Ai ∪⋃

i∈I Bi.

(5)⋂

i∈I(Ai ∩Bi) =⋂

i∈I Ai ∩⋂

i∈I Bi.

(6)⋂

i∈I Ai ∪⋂

i∈I Bi ⊆⋂

i∈I(Ai ∪Bi).

(7)⋃

i∈I(Ai ∩Bi) ⊆⋃

i∈I Ai ∩⋃

i∈I Bi.

(8) C ∩ ⋃i∈I Ai =

⋃i∈I(C ∩ Ai).

(9) C ∪ ⋂i∈I Ai =

⋂i∈I(C ∪ Ai).

Ist I =⋃

k∈K Ik eine Partition von I, dann gelten die verallgemeinerten Assozia-tivgesetze

(10)⋂

i∈I Ai =⋂

k∈K

⋂i∈Ik

Ai.

(11)⋃

i∈I Ai =⋃

k∈K

⋃i∈Ik

Ai.

Beweis: Naturlich kann man jede Gleichung bzw. Inklusion elementweise uber-prufen. Oft ist es allerdings einfacher, weniger formal sondern mehr inhaltlich zuargumentieren. Dazu bezeichne VA :=

⋃i∈I Ai =

⋃{Ai | i ∈ I} die Vereinigungdieser Mengenfamilie und DA :=

⋂i∈I Ai =

⋂{Ai | i ∈ I} ihren Durchschnitt.Nach Folgerung 1.87 sind dies gerade sup und inf dieser Mengenfamilie in derpartiell geordneten Menge (P(M),⊆). Analog seien VB, DB, VA∩B, DA∩B usw.fur die anderen beteiligten Mengenfamilien definiert.

(1) Dies folgt nun unmittelbar aus der Definition von Infimum und Supremumgemaß Definition 1.84.

Die restlichen Aussagen (2) - (11) sind jeweils paarweise dual zueinander. Daherreicht es, immer nur eine pro Paar zu beweisen, also etwa (2), (4), (6), (8) und(10).

(2) Es ist x ∈ ⋂i∈I Ai gleichwertig zu ¬∀i ∈ I : x ∈ Ai. Nach (57) ist dies

gleichwertig zu ∃i ∈ I : ¬(x ∈ Ai), also zu x ∈ ⋃i∈I Ai.

(4) Aus Ai ⊆ VA ⊆ VA ∪ VB und Bi ⊆ VB ⊆ VA ∪ VB folgt nach Definition derVereinigung Ai ∪ Bi ⊆ VA ∪ VB fur alle i ∈ I und daher nach Definition desSupremums auch VA∪B ⊆ VA ∪ VB. Umgekehrt folgt Ai ⊆ Ai ∪ Bi ⊆ VA∪B unddaher nach der Definition des Supremums VA ⊆ VA∪B. Analog folgt VB ⊆ VA∪B.



Nach der Definition der Vereinigung ergibt sich daher auch die andere InklusionVA ∪ VB ⊆ VA∪B.

(6) Wegen DA ⊆ Ai ⊆ Ai ∪ Bi fur alle i ∈ I folgt DA ⊆ DA∪B nach Definitiondes Infimums. Analog erhalt man DB ⊆ DA∪B. Nach Definition der Vereinigungzeigt dies bereits DA ∪DB ⊆ DA∪B. Daß die umgekehrte Inklusion nicht immergilt, kann man noch durch ein geeignetes Gegenbeispiel zeigen.

(8) Aus (7) folgt mit C = Bi fur alle i ∈ I und der Kommutativitat des Durch-schnitts (64) bereits VC∩A ⊆ C ∩ VA. Umgekehrt folgt fur jedes x ∈ C ∩ VA auchx ∈ C∧x ∈ Ai fur ein i ∈ I und damit x ∈ C∩Ai. Dies impliziert aber x ∈ VC∩A,also auch die umgekehrte Inklusion.

(10) Es sind jeweils gleichwertig

x ∈ ⋂i∈I Ai,

∀i ∈ I : x ∈ Ai,

∀k ∈ K∀i ∈ Ik : x ∈ Ai,

x ∈ ⋃k∈K(

⋃i∈Ik

Ai). �

Satz 1.128 Es sei (Ai,j | (i, j) ∈ I×J) eine durch die Indexmenge I×J doppeltindizierte Mengenfamilie. Dann gilt⋃

i∈I

⋂j∈J Ai,j ⊆

⋂j∈J

⋃i∈I Ai,j.

Beweis: Es ist x ∈ ⋃i∈I

⋂j∈J Ai,j gleichwertig zu

∃i ∈ I∀j ∈ J : x ∈ Ai,j.

Nach der Vertauschungsregel fur Quantoren (58) folgt hieraus

∀j ∈ J∃i ∈ I : x ∈ Ai,j

und dies ist gleichwertig zu x ∈ ⋂j∈J

⋃i∈I Ai,j. �


2 Gruppen, Ringe, Korper 59

2 Gruppen, Ringe, Korper

Weiterfuhrende Informationen zu den Inhalten dieses Kapitels findet man unter

www.mathecafe.de/algebra/

2.1 Gruppen

2.1.1 Elementare Eigenschaften

Definition 2.1 Es sei (G, ·) ein Gruppoid. Ein Element e ∈ G heißt linksneutraloder ein Linkseinselement, wenn e · a = a fur alle a ∈ G gilt. Dual spricht manvon einem rechtsneutralen oder Rechtseinselement, wenn a · e = a fur alle a ∈ Gerfullt ist, und e heißt ein neutrales Element oder Einselement, wenn beides gilt.

Dagegen heißt ein Element a ∈ G linksabsorbierend (rechtsabsorbierend, absor-bierend), wenn a · b = a (b · a = a, beides) fur alle b ∈ G gilt.

Eine Halbgruppe (G, ·) mit einem Einselement e wird auch Monoid genannt. Mannotiert dies oft als (G, ·, e).

Beispiel 2.2 Auf jeder nichtleeren Menge G kann man durch a · b := a fur allea, b ∈ G eine Multiplikation definieren, die wegen a · (b · c) = a = a · b = (a · b) · cersichtlich assoziativ ist. Daher ist (G, ·) eine Halbgruppe, die sogenannte Links-zerohalbgruppe auf G. Hierin ist jedes a ∈ G linksabsorbierend und rechtsneutral.

Dual dazu wird die Rechtszerohalbgruppe auf G durch a · b := b fur alle a, b ∈ Gdefiniert.

Fur |G| = 1 erhalt man dasselbe (kommutative) Monoid. Es wird auch das trivialeMonoid genannt. Fur |G| > 1 sind diese Halbgruppen naturlich nicht kommutativund wegen der nachsten Folgerung keine Monoide.

Folgerung 2.3 Ein Einselement e ∈ G (absorbierendes Element a ∈ G) ist,wenn es existiert, eindeutig bestimmt.

Beweis: Man kann sogar etwas mehr zeigen: Ist e ∈ G Linkseinselement und e′ ∈G Rechtseinselement, so folgt bereits e′ = e · e′ = e. Ist a ∈ G linksabsorbierendund a′ ∈ G rechtsabsorbierend, so folgt bereits a = a · a′ = a′. �


http://www.mathecafe.de/algebra/

2.1 Gruppen 60

Beispiel 2.4 a) (N0, ·, 1), (Z, ·, 1) und (Q, ·, 1) sind kommutative Monoide.

b) (N,+, 0), (Z,+, 0) und (Q,+, 0) sind additiv geschriebene kommutative Mo-noide. Wie in diesen Fallen wird ein Einselement in einem additiv geschriebenenGruppoid oft Nullelement genannt.

c) Jede Potenzmenge (P(M),∩,M) ist ein kommutatives und idempotentes Mo-noid. Ebenso ist (P(M),∪, ∅) ein derartiges Monoid.

d) In jeder Transformationshalbgruppe (TA, ◦) ist die identische Abbildung ιA einEinselement, also (TA, ◦, ιA) ein Monoid, das (volle) Transformationsmonoid aufA. Die fur jedes a ∈ A definierte konstante Abbildung ca : A → A mit ca(x) = afur alle x ∈ A ist stets rechtsabsorbierend wegen (f ◦ ca)(x) = ca(f(x)) = a =ca(x) fur jedes f ∈ TA und Folgerung 1.96 f). Existieren also mindestens zweiverschiedene Elemente a 6= b in A, so ist wegen ca ◦ cb = cb 6= ca = cb ◦ ca diesesMonoid nicht kommutativ.

e) Ist (G, ·) ein beliebiges Gruppoid, so kann man ein Element e 6∈ G als Eins-element zu (G, ·) adjungieren, indem man die Multiplikation von G auf G ∪ {e}fortsetzt durch e · x = x · e = x fur alle x ∈ G ∪ {e}, also insbesondere e · e = e.Dann ist (G ∪ {e}, ·, e) ein Gruppoid mit dem Einselement e. Dieses ist genaudann idempotent, kommutativ bzw. assoziativ, wenn (G, ·) die jeweilige Eigen-schaft hat.

Fuhrt man diese Adjunktion eines Einselementes speziell fur eine freie Halbgruppe(A+, ·) durch, so schreibt man fur das Einselement meistens ε oder λ und nenntes das leere Wort oder den leeren String mit der Lange 0. (Naturlich darf ε bzw.λ noch nicht in A vorkommen!) Man identifiziert dann A0 mit {ε} und schreibtmit A∗ :=

⋃∞n=0A

n kurz (A∗, ·, ε) fur dieses freie Monoid uber dem Alphabet A.

Definition 2.5 Ein Element a ∈ G eines Gruppoids (G, ·) heißt linkskurzbar(rechtskurzbar) in (G, ·), wenn a · x = a · y → x = y (x · a = y · a → x = y)fur alle x, y ∈ G gilt. Sind beide Implikationen erfullt, so nennt man a kurzbar.Das Gruppoid (G, ·) heißt kurzbar, linkskurzbar, rechtskurzbar, wenn jedes a ∈ Gdiese Eigenschaft hat.

Beispiel 2.6 a) Jedes Linkseinselement ist linkskurzbar, jedes Rechtseinsele-ment rechtskurzbar. Daher ist jede Linkszerohalbgruppe rechtskurzbar und jedeRechtszerohalbgruppe linkskurzbar.

b) (N0,+, 0) ist ein kurzbares Monoid und dasselbe gilt fur (N, ·, 1). Dagegen ist0 nicht kurzbar in (N0, ·).


2.1 Gruppen 61

c) Jedes freie Monoid ist kurzbar.

d) Definiert man in einem Gruppoid (G, ·) fur jedes a ∈ G die Linkstranslationλa : G → G durch λa(x) := a · x und dual die Rechtstranslation %a : G → Gdurch %a(x) := x · a jeweils fur alle x ∈ G, so sind dies Transformationen von G.Offensichtlich ist λa genau dann injektiv, wenn a linkskurzbar ist, und dual %a

genau dann injektiv, wenn a rechtskurzbar ist. Weiterhin ist (G, ·) genau dannkommutativ, wenn λa = %a fur alle a ∈ G gilt. In diesem Fall nennt man dieseAbbildungen einfach Translationen. Bei Cayley-Tafeln von endlichen Gruppoidenstehen in der Zeile mit dem Index a gerade die Werte von λa und in der Spaltemit dem Index a die Werte von %a.

Definition 2.7 Es sei (G, ·, e) ein Monoid und a ∈ G. Ein Element a′ ∈ G mita′ ·a = e heißt Linksinverses zu a (mit a ·a′ = e heißt Rechtsinverses zu a), und esheißt ein Inverses zu a, wenn es beide Bedingungen erfullt. In diesem Fall nenntman a invertierbar. Die Menge aller invertierbaren Elemente von (G, ·, e) werdemit G∗ bezeichnet.

Folgerung 2.8 Es sei (G, ·, e) ein Monoid.

a) Ein linksinvertierbares (rechtsinvertierbares, invertierbares) Element a ∈ G istlinskurzbar (rechtskurzbar, kurzbar).

b) Ein Inverses zu einem Element a ∈ G∗ ist stets eindeutig bestimmt und wirdim folgenden mit a−1 bezeichnet.

c) Es ist e ∈ G∗ 6= ∅ und e−1 = e.

d) Fur a ∈ G∗ gilt a−1 ∈ G∗ und (a−1)−1 = a.

e) Fur a, b ∈ G∗ gilt a · b ∈ G∗ und (a · b)−1 = b−1 · a−1.

Beweis: a) Aus a · x = a · y folgt a′ · (a · x) = a′ · (a · y) und daraus mit derAssoziativitat dann x = e · x = (a′ · a) · x = (a′ · a) · y = e · y = y. Dual folgt dieBehauptung bezuglich der Rechtskurzbarkeit und damit dann die bezuglich derKurzbarkeit.

b) Ist a′ ∈ G Linksinverses zu a ∈ G und a′′ ∈ G Rechtsinverses, so gilt aufgrundder Assoziativitat a′ = a′ · e = a′ · (a · a′′) = (a′ · a) · a′′ = e · a′′ = a′′.

c) folgt aus e · e = e, d) folgt aus a−1 · a = e = a · a−1.

e) Wiederum mit der Assoziativitat folgt (a · b) · (b−1 · a−1) = a · e · a−1 = e und(b−1 · a−1) · (a · b) = b−1 · e · b = e. �


2.1 Gruppen 62

Beispiel 2.9 In dem vollen Transformationsmonoid (TA, ◦, ιA) besteht T ∗A genau

aus den Permutationen, also den bijektiven Abbildungen f : A → A. (Manvergleiche noch einmal Folgerung 2.8 d) und e) mit den Aussagen von Satz 1.62.)

Satz 2.10 Fur jede Halbgruppe (G, ·) sind gleichwertig:

a) Fur alle a, b ∈ G existieren (eindeutig bestimmte) x, y ∈ G mit a · x = b undy · a = b.

b) Es gibt ein Linkseinselement e` ∈ G und zu jedem a ∈ G existiert ein a′ ∈ Gmit a′ · a = e`.

c) Es gibt ein Einselement e ∈ G und zu jedem a ∈ G existiert ein Inversesa′ ∈ G, d. h. (G, ·, e) ist Monoid mit G∗ = G.

Beweis: Vorlesung! �

Definition 2.11 Eine Gruppe ist eine Halbgruppe (G, ·), welche die Bedingun-gen aus Satz 2.10 erfullt. Eine kommutative Gruppe wird auch abelsche Gruppegenannt (Niels Henrik Abel, 1802 - 1829).

In einer additiv geschriebenen Gruppe (G,+) notiert man das neutrale Elementauch als 0 und das Inverse zu a ∈ G als −a.

Eine additiv geschriebene abelsche Gruppe (G,+) nennt man auch einen Modul(lat. modus = Maß, Maßstab) und darin a − b := a + (−b) die Differenz (lat.differre = sich unterscheiden) von a und b aus G.

Bemerkung 2.12 Die Bedingung a) aus Satz 2.10 besagt (fur ein beliebigesGruppoid) gerade, daß samtliche Links- und Rechtstranslationen surjektiv sind.Fur invertierbare Elemente sind diese Abbildungen wegen der Kurzbarkeit nachFolgerung 2.8 a) daher bereits Permutationen, woraus sich dann schon die Ein-deutigkeit in a) ergibt.

Fur beliebige Gruppoide sind die drei Bedingungen aus Satz 2.10 nicht mehrgleichwertig. Man nennt Gruppoide, die a) einschließlich der Eindeutigkeiterfullen, Quasigruppen. Solche Quasigruppen werden in der Codierungstheoriezur Konstruktion von fehlererkennenden Codes benutzt.

Wegen Satz 2.10 a) beschreibt die Cayley-Tafel einer endlichen Halbgruppe ge-nau dann eine Gruppe, wenn jedes Element in jeder Zeile und in jeder Spalte(genau einmal) auftritt. Tafeln mit dieser Eigenschaft (auch ohne daß die Asso-ziativitat erfullt ist), werden auch Lateinische Quadrate genannt. Sie werden inder Kombinatorik untersucht.


http://de.wikipedia.org/wiki/Niels_Henrik_Abel

2.1 Gruppen 63

Beispiel 2.13 Ist (G, ·, e) ein Monoid, so ist (G∗, ·, e) wegen Folgerung 2.8 ei-ne Gruppe, die Einheitengruppe von (G, ·, e). Insbesondere bilden in dem vollenTransformationsmonoid (TA, ◦, ιA) die Permutationen diese Einheitengruppe. Siewird auch die volle Permutationsgruppe oder Symmetrische Gruppe auf A genanntund mit S(A) oder Sym(A) oder SA bezeichnet.

Beispiel 2.14 a) (Z,+, 0), (Q,+, 0), (R,+, 0) sind Moduln.

b) (Q \ {0}, ·, 1) und (R \ {0}, ·, 1) sind abelsche Gruppen.

c) Wegen Folgerung 1.37 ist (P(M),∆, ∅) fur jede Menge M eine abelsche Grup-pe. Fur eine Zweiermenge M := {a, b} seien die Elemente von P(M) wie folgtbezeichnet: 0 := ∅, 1 := {a}, 2 := {b} und 3 := M . Dann erhalt man fur dieseGruppe die folgende Cayley-Tafel.

∆ 0 1 2 30 0 1 2 31 1 0 3 22 2 3 0 13 3 2 1 0

Diese Gruppe der Ordnung 4 wird Kleinsche Vierergruppe (Felix Klein, 1849 -1925) genannt und ublicherweise mit V4 bezeichnet.

Fur eine Einermenge M := {a} erhalt man mit den Abkurzungen 0 := ∅ und1 := M entsprechend die Cayley-Tafel

∆ 0 10 0 11 1 0

Diese beschreibt die Addition modulo 2 (ohne Ubertrag), also die Addition vonBits, welche eine grundlegende arithmetische Operation in allen Rechnern dar-stellt.

Offensichtlich ist sie als “Teil” in der Kleinschen Vierergruppe enthalten, ahnlichwie die Gruppe der ganzen Zahlen (Z,+) in der Gruppe der rationalen Zahlen(Q,+) enthalten ist.


http://de.wikipedia.org/wiki/Felix_Klein

http://de.wikipedia.org/wiki/Felix_Klein

2.1 Gruppen 64

Beispiel 2.15 Fur n ∈ N seien P1, . . . , Pn gleichmaßig auf dem Einheitskreisangeordnete Punkte, also fur n ≥ 3 die Eckpunkte eines regelmaßigen n-Ecks.Zur Vereinfachung der Schreibweise bezeichnen wir die Punkte nur noch durchihre Indizes, wie im Bild fur n = 4, und schreiben M := {1, . . . , n} fur die Mengedieser Punkte.

P1

P3

P1

P2

13

P1P2

2

4

Mit r sei die Drehung um den Mittelpunkt des Einheitskreises um den Drehwinkelϕ = 2π/n in positiver Richtung bezeichnet. Dann permutiert r die Menge M inder folgenden Weise: r(1) = 2, r(2) = 3, . . . , r(n− 1) = n, r(n) = 1.

Weiterhin sei rk fur k ∈ N0 die k-fache Verkettung dieser Drehung mit sich selbst,also r0 := ιM , r1 := r, r2 := r ◦ r, rk+1 := rk ◦ r. Wegen rn = ιM (Dre-hung um 2π) gilt rk = rk+n und daher rk ◦ rn−k = ιM = rn−k ◦ rk. Also hatman (rk)−1 = rn−k. Daher ist die Verkettung eine assoziative Verknupfung aufder Menge Cn = {r0, r1, . . . , rn−1}, r0 ist Einselement und jedes Element ausCn besitzt in Cn ein Inverses. Es ist also (Cn, ◦, r0, −1) eine Gruppe, die Dreh-gruppe des regelmaßigen n-Ecks. Sie wird auch zyklische Gruppe der Ordnung ngenannt und ist stets kommutativ. Derartige Gruppen werden u. a. in der Kri-stallographie und Chemie benutzt, um Symmetrieeigenschaften von Kristallenund Molekulen zu beschreiben. (Schreibt man die Komponenten xi eines beliebi-gen n-Tupels (x1, x2, . . . , xn) ∈ An fur einen Datentyp A an die Eckpunkte desn-Ecks, dann bewirkt diese Drehung eine Abbildung shift : An → An gemaßshift(x1, x2, . . . , xn) := (xr(1), . . . , xr(n)) = (x2, . . . , xn, x1), also gerade einen zy-klischen Linksshift der n-Tupel.)

In der folgenden Cayley-Tafel dieser Gruppe fur n = 4 werden die Elemente rk

einfach durch ihre Exponenten k dargestellt.


2.1 Gruppen 65

◦ 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 3 0 1 2

Man erhalt dieselbe Cayley-Tafel, wenn man die Verknupfung ⊕ auf Zn ={0, 1, . . . , n − 1} ⊆ Z als Addition modulo n definiert: Fur x, y ∈ Zn istx⊕ y := x+ y ∈ Z, wenn bereits x+ y < n gilt, sonst ist x⊕ y := x+ y − n.

Dagegen ist die Cayley-Tafel der Kleinschen Vierergruppe hiervon “wesentlichverschieden”, denn dort ist jedes Element sein eigenes Inverses, was in den zy-klischen Gruppen Cn fur n ≥ 3 nicht der Fall ist. Wir werden die “wesentlicheGleichheit” (nicht nur) von Gruppen spater im Begriff der “Isomorphie” prazi-sieren.

2.1.2 Untergruppen und Homomorphie

Lemma 2.16 Es sei f : Gn → G eine n-stellige Operation auf einer nichtleerenTragermenge G, ∅ 6= U ⊆ G und f |U := f ∩ Un × U die Einschrankung von fauf Un+1. Genau dann ist f |U : Un → U eine n-stellige Operation auf U , wennf(Un) ⊆ U gilt.

Beweis: Ist f |U eine n-stellige Operation auf U , so gilt f |U (u1, . . . , un) ∈ U furalle (u1, . . . , un) ∈ Un, also f(u1, . . . , un) ∈ U , d. h. f(Un) ⊆ U . Umgekehrt istf | U als Einschrankung einer Abbildung selbst eine partielle Abbildung auf Un.Es bleibt zu zeigen, daß f |U linkstotal ist. Zu beliebigem (u1, . . . , un) ∈ Un istaber (u1, . . . , un, f(u1, . . . , un)) ∈ Un+1 und damit (u1, . . . , un, f(u1, . . . , un)) ∈f |U . Also ist f |U linkstotal. �

Definition 2.17 Es sei (G, ·) ein Gruppoid. Unter einem Untergruppoid (einerUnterhalbgruppe, einer Untergruppe) (U, ·) von (G, ·) versteht man eine nichtleereTeilmenge U von G, die zusammen mit der Einschrankung · |U selbst ein Grup-poid (eine Halbgruppe, eine Gruppe) (U, · |U) ist.

Mit Sub(G) ⊆ P(G) werde die Menge aller Untergruppoide eines Gruppoids (Un-terhalbgruppen einer Halbgruppe, Untergruppen einer Gruppe) (G, ·) bezeichnet.

Satz 2.18 Genau dann ist (U, ·) fur ∅ 6= U ⊆ G Untergruppoid des Gruppoids(G, ·), wenn

U · U := {u · v | u, v ∈ U} ⊆ U(134)


2.1 Gruppen 66

gilt. Ist hierbei (G, ·) eine Halbgruppe, so auch (U, ·).

Genau dann ist (U, ·,−1 ) fur ∅ 6= U ⊆ G Untergruppe einer Gruppe (G, ·,−1 ),wenn neben (134) noch

U−1 := {u−1 ∈ G | u ∈ U} ⊆ U(135)

gilt. Gemeinsam sind (134) und (135) gleichwertig zu

U · U−1 := {u · v−1 | u, v ∈ U} ⊆ U.(136)

Das Einselement von G ist dann auch das Einselement von U .

Beweis: Der erste Teil folgt unmittelbar aus Lemma 2.16. Ersichtlich gilt dieAssoziativitat fur alle a, b, c ∈ U ⊆ G. Bis auf die Behauptung uber die Einsele-mente folgt auch der Rest aus Lemma 2.16. Zu u ∈ U 6= ∅ liegt u−1 ∈ G nach(135) bereits in U . Dann folgt aber mit (134) auch e = uu−1 ∈ U . �

Beispiel 2.19 a) In jeder Gruppe (G, ·,−1 , e) sind {e} und G Untergruppen, dietrivialen Untergruppen.

b) (N0,+) ist Unterhalbgruppe von (Z,+), (Z,+) ist Untergruppe von (Q,+),(Q+ := {q ∈ Q | q > 0},+) ist Unterhalbgruppe von (Q,+)

c) ({−1, 1}, ·) ist Untergruppe von (Q \ {0}, ·), (Q+, ·) ist Untergruppe von (Q \{0}, ·).

Aufgabe 2.20 Bestimmen Sie alle Untergruppen von (Z,+). Hinweis: Die Divi-sion mit Rest ist hilfreich.

Lemma 2.21 Ist (Ui)i∈I eine Familie von Untergruppoiden eines Gruppoids(Unterhalbgruppen einer Halbgruppe) (G, ·), so ist D =

⋂Ui entweder leer oder

ein Untergruppoid (eine Unterhalbgruppe) von (G, ·). Sind hierbei alle Ui Un-tergruppen einer Gruppe (G, ·), so ist D eine Untergruppe von (G, ·). Also istSub(G) in diesem Fall ein vollstandiger Verband.

Ist ∅ 6= A ⊆ G in einem Gruppoid (einer Halbgruppe, Gruppe) (G, ·), dannexistiert ein kleinstes Untergruppoid (eine kleinste Unterhalbgruppe, eine kleinsteUntergruppe) (D, ·) von (G, ·) mit A ⊆ D.


2.1 Gruppen 67


Definition 2.22 Man nennt (D, ·) aus dem zweiten Teil von Lemma 2.21 dasvon A erzeugte Gruppoid bzw. die von A erzeugte Halbgruppe (Gruppe) undschreibt hierfur < A > und nennt A ein Erzeugendensystem von < A >. EineHalbgruppe (Gruppe) (G, ·) heißt zyklisch oder monogen, wenn es ein a ∈ G mit< a >:=< {a} >= G gibt.

Fur ein Element a ∈ G einer Gruppe (G, ·) nennt man o(a) = | < a > |, alsodie Ordnung der von a erzeugten Untergruppe von (G, ·), die Ordnung von a.(Nach dem weiter unten bewiesenen Satz von Lagrange ist sie stets ein Teiler derOrdnung |G| von (G, ·).)

Beispiel 2.23 a) Die Halbgruppe (N,+) wird von {1} erzeugt, ist also eine un-endliche zyklische Halbgruppe.

b) Die Gruppe (Z,+) wird ebenfalls von {1} erzeugt, ist also eine unendlichezyklische Gruppe. Jedes Element a 6= 0 hat unendliche Ordnung und 0 hat dieOrdnung 1.

c) Die Drehgruppe Cn wird von der Drehung r um den Winkel ϕ = 2π/n erzeugt,ist also endliche zyklische Gruppe der Ordnung n. Fur n = 4 ist o(r) = 4 undo(r2) = 2.

d) Sei (G, ·) eine Gruppe und a ∈ G. Fur die Untergruppe < a >= {an | n ∈ Z}gibt es die beiden folgenden Moglichkeiten:

1. Alle Potenzen an sind paarweise verschieden. Dann gilt | < a > | = ∞, also ist< a > eine unendliche zyklische Gruppe.

2. Es gibt n 6= m in Z mit an = am, wobei m < n angenommen werden darf.Dann folgt an−m = e, also ak = e fur ein k ≥ 1. Dann gibt es ein minimales k ∈ Ndieser Art. Daher gilt < a >= {a0, a1, . . . , ak−1} mit paarweise verschiedenen ai,also | < a > | = k. Dann ist < a > eine zyklische Gruppe der Ordnung k = o(a).

Satz 2.24 Es sei (U, ·) Untergruppe einer Gruppe (G, ·). Definiert man fur allex, y ∈ G

x ∼r y :↔ xy−1 ∈ U und x ∼` y :↔ x−1y ∈ U,(137)

dann sind ∼r und ∼` Aquivalenzrelationen auf G, die fur alle x, y ∈ G

x ∼r y ↔ x−1 ∼` y−1(138)


2.1 Gruppen 68

erfullen. Die zugehorigen Aquivalenzklassen sind fur alle x ∈ G

[x]∼r = Ux = {ux | u ∈ U} und [x]∼`= xU = {xu | u ∈ U}.(139)

Fur jedes x ∈ G ist die Rechtstranslation %x : U → Ux eine Bijektion. Also gilt|U | = |Ux| und ebenso |U | = |xU |. Bezeichnet G/∼r = {Ux | x ∈ G} bzw. G/∼`

= {xU | x ∈ G} die Menge der jeweiligen Aquivalenzklassen, dann wird durchϕ(Ux) = x−1U ∈ G/∼` fur alle Ux ∈ G/∼r eine Bijektion ϕ : G/∼r → G/∼`

definiert. Also gilt |G/∼r | = |G/∼` |.

Beweis: Zeige mit Hilfe von Satz 2.18, daß ∼r eine Aquivalenzrelation ist. Dannfolgt dual dasselbe fur ∼`. Wegen xx−1 = e ∈ U ist ∼r reflexiv. Mit xy−1 ∈ Uliegt wegen (135) aber auch yx−1 = (xy−1)−1 in U , also ist ∼r symmetrisch. Ausxy−1 ∈ U und yz−1 ∈ U folgt wegen (134) auch xy−1yz−1 = xz−1 ∈ U und damitdie Transitivitat von ∼r.

Weiterhin gilt x−1 ∼` y−1 ↔ (x−1)−1y−1 = xy−1 ∈ U ↔ x ∼r y. Damit ist auch

(138) gezeigt.

Es ist y ∼r x gleichwertig zu yx−1 = u fur ein u ∈ U , also zu y = ux ∈ Ux. Dieszeigt die richtige Beschreibung der Aquivalenzklassen von ∼r und die Behauptungfur ∼` folgt dual.

Die Injektivitat der Rechtstranslationen %x folgt aus der Rechtskurzbarkeit vonx in der Gruppe (G, ·), die Surjektivitat ist klar.

Da ϕ ebenfalls surjektiv ist, denn offensichtlich wird die Nebenklasse Ux−1 aufeine gegebene Nebenklasse xU abgebildet, bleibt die Injektivitat zu zeigen. Ausϕ(Ux) = ϕ(Uy) folgt aber x−1U = y−1U , also x−1 ∼` y

−1. Dies fuhrt wegen (138)aber zu x ∼r y und damit zu Ux = Uy. �

Definition 2.25 Die Aquivalenzklassen [x]∼r bzw. [x]∼`in Satz 2.24 heißen

Rechts- bzw. Linksnebenklassen von (U, ·) in (G, ·). Die Anzahl |G/∼r | = |G/∼` |heißt Index von (U, ·) in (G, ·), in Zeichen: |G : U |.

Folgerung 2.26 Satz von Lagrange (Joseph Louis Lagrange, 1736 - 1813)Fur jede Untergruppe (U, ·) einer Gruppe (G, ·) gilt

|G| = |G : U | · |U |.(140)


http://de.wikipedia.org/wiki/Joseph_louis_Lagrange

2.1 Gruppen 69

Beweis: Sei zunachst |G| = ∞. Ist dann auch U eine unendliche Untergruppe vonG, so steht auch auf der rechten Seite∞. Ist dagegen U eine endliche Untergruppe,so muß es unendlich viele Nebenklassen geben, da alle gleichmachtig zu U sindund damit die Vereinigung endlich vieler endlicher Klassen nicht die unendlicheTragermengeG ergeben konnte. Also sind wiederum beide Seiten von (140) gleich.

Sei nun |G| endlich. Dann kann man die Elemente von G abzahlen, indem man diedisjunkten |G : U | Nebenklassen abzahlt, die aber alle |U | Elemente enthalten.Hieraus folgt sofort (140). �

Definition 2.27 Es sei (G, ·) ein Gruppoid. Eine Aquivalenzrelation ≡ aus E(G)heißt linksinvariant, linkskompatibel oder eine Linkskongruenz, wenn

a ≡ b→ c · a ≡ c · b(141)

fur alle a, b, c ∈ G gilt. Dual heißt ≡ eine Rechtskongruenz, wenn

a ≡ b→ a · c ≡ b · c(142)

fur alle a, b, c ∈ G gilt. Sind beide Implikationen stets erfullt, so nennt man ≡eine Kongruenz(relation) auf (G, ·).

Lemma 2.28 Es sei ≡ eine Aquivalenzrelation auf dem Gruppoid (G, ·).

a) Genau dann ist ≡ Kongruenzrelation auf (G, ·), wenn

a ≡ b ∧ c ≡ d→ a · c ≡ b · d(143)

fur alle a, b, c, d ∈ G erfullt ist.

b) Ist ≡ Kongruenzrelation auf (G, ·) und G/ ≡ die Faktormenge, dann wirddurch

[a]≡ · [b]≡ := [a · b]≡(144)

fur alle [a]≡, [b]≡ ∈ G/ ≡ eine binare Operation auf G/ ≡ definiert, so daß(G/ ≡, ·) ein Gruppoid, das Faktorgruppoid von (G, ·) nach ≡, ist. Mit (G, ·) istauch (G/ ≡, ·) assoziativ (kommutativ, idempotent, ein Monoid, eine Gruppe).


2.1 Gruppen 70


Satz 2.29 Fur jede Untergruppe (U, ·) einer Gruppe (G, ·) sind aquivalent:

a) ∼r ist Kongruenzrelation auf (G, ·).

b) ∼` ist Kongruenzrelation auf (G, ·).

c) ∼r und ∼` stimmen uberein.

d) Fur alle x ∈ G gilt

Ux = xU.(145)

In diesem Fall schreibt man G/U fur diese Gruppe anstelle von G/∼r = G/∼` .


Definition 2.30 Eine Untergruppe (U, ·) einer Gruppe (G, ·), die (145) fur allex ∈ G erfullt, nennt man einen Normalteiler von (G, ·) und (G/U, ·) heißt danndie Faktorgruppe von (G, ·) nach (U, ·).

Satz 2.31 Es sei (N, ·) ein Normalteiler einer Gruppe (G, ·) und κ Kongruenzauf (G, ·).

a) Es ist κN := {(x, y) ∈ G2 | xy−1 ∈ N} eine Kongruenz auf (G, ·).

b) Es ist Nκ := [e]κ fur das Einselement e ∈ G ein Normalteiler von (G, ·).

c) Es gelten N = NκNund κ = κNκ.

Beweis: Vorlesung!

Beispiel 2.32 Wie in jeder abelschen Gruppe ist in dem Modul (Z,+) jede Un-tergruppe bereits Normalteiler. Nach Aufgabe 2.20 sind dies gerade die Untergrup-pen (nZ,+) fur n ∈ N0. Die zu dem Normalteiler nZ gehorende KongruenzrelationκnZ ist dann gerade gegeben durch a κnZ b ↔ a − b ∈ nZ, also nichts anderes alsa ≡ b modulo n. Man schreibt fur Z/nZ auch wie schon getan Z/(n) und erhaltals Faktorgruppen dieRestklassengruppen (Z/(n),+) modulo n. Schreibt man nunnoch fur die Restklasse [m]n ∈ Z/(n) einfach wieder m, so erhalt man fur n = 4die Cayley-Tafel aus Beispiel 2.15 und fur n = 2 die zweite Tafel aus Beispiel 2.14.


2.1 Gruppen 71

Definition 2.33 Es seien (G, ·) und (G′,�) Gruppoide. Ein Homomorphismusvon (G, ·) in (G′,�) ist eine Abbildung ϕ : G→ G′, die

ϕ(a · b) = ϕ(a)� ϕ(b)(146)

fur alle a, b ∈ G erfullt. Ein injektiver Homomorphismus wird auch Monomor-phismus oder Einbettung genannt, ein surjektiver Homomorphismus ein Epimor-phismus und ein bijektiver Homomorphismus auch Isomorphismus.

Fur G = G′ nennt man Homomorphismen auch Endomorphismen und bijektiveEndomorphismen heißen Automorphismen. Schließlich bezeichne Hom(G,G′) dieMenge aller Homomorphismen von G in G′, End(G) die Menge aller Endomor-phismen und Aut(G) die Menge aller Automorphismen von (G, ·).

Zwei Gruppoide (Halbgruppen, Gruppen) heißen isomorph, in Zeichen G ∼= G′,wenn es einen Isomorphismus ϕ : G→ G′ gibt.

Aufgabe 2.34 Durch welche Funktionstasten sind auf Ihrem TaschenrechnerGruppenhomomorphismen realisiert?

Lemma 2.35 Es seien (G, ·) und (G′,�) Gruppoide und ϕ : G→ G′ ein Homo-morphismus.

a) Stets ist das Bild Imϕ = ϕ(G) Untergruppoid von (G′,�). Mit (G, ·) ist auch(ϕ(G),�) Halbgruppe.

b) Besitzt (G, ·) ein Einselement e, so ist ϕ(e) Einselement von (ϕ(G),�). Mit(G, ·, e) ist daher auch (ϕ(G),�, ϕ(e)) Monoid.

c) Ist (G, ·, e) Monoid und a−1 das Inverse von a ∈ G, so ist ϕ(a−1) = ϕ(a)−1

das Inverse von ϕ(a) in ϕ(G).

d) Es ist ϕ(U) ∈ Sub(G′) fur alle U ∈ Sub(G), falls G und G′ beides Gruppoide(Halbgruppen, Gruppen) sind.

e) Es ist ϕ−1(U ′) ∈ Sub(G) fur alle U ′ ∈ Sub(G′), falls G und G′ beides Grup-poide (Halbgruppen, Gruppen) sind.



2.1 Gruppen 72

Lemma 2.36 a) Es ist ιG ∈ Aut(G) ⊆ End(G), also beide Mengen nicht leer.

b) Sind ϕ : G→ G′ und ψ : G′ → G′′ Homomorphismen, dann auch ϕ ◦ ψ : G→G′′. Also ist (End(G), ◦, ιG) ein Monoid.

c) Ist ϕ : G → G′ ein Isomorphismus, dann auch ϕ−1 : G′ → G. Also ist(Aut(G), ◦, ιG) gerade die Gruppe der Einheiten von (End(G), ◦, ιG).

d) Die Isomorphie ∼= ist eine Aquivalenzrelation auf jeder nichtleeren Menge vonGruppoiden (Halbgruppen, Gruppen).


Satz 2.37 Homomorphiesatz fur Gruppen Es seien (G, ·) und (G′, ·) Grup-pen und ϕ : G→ G′ ein Homomorphismus. Dann gelten:

a) Ist e′ ∈ G′ das Einselement von (G′, ·), dann ist der Kern Ker(ϕ) = ϕ−1(e′) ={x ∈ G | ϕ(x) = e′} von ϕ ein Normalteiler von (G, ·).

b) Die zu Ker(ϕ) gemaß Satz 2.31 a) gehorende Kongruenz ist gerade kerϕ gemaßFolgerung 1.96 e).

c) Die Faktorgruppe (G/Ker(ϕ), ·) ist isomorph zu (ϕ(G), ·) vermoge des Isomor-phismus ψ([x]) = ϕ(x) fur alle [x] ∈ G/Ker(ϕ).

d) Mit dem kanonischen Epimorphismus νKerϕ : (G, ·) → (G/Ker(ϕ), ·) und derInjektion inϕ(G) : ϕ(G) → G′ gilt νKer(ϕ) ◦ ψ ◦ inϕ(G) = ϕ. Die Abbildung ψ istdadurch eindeutig bestimmt.

Beweis: a) Da ϕ(G) Untergruppe von (G′, ·) ist, liegt das Einselement e′ von G′

bereits in ϕ(G) und stimmt dort mit dem Einselement ϕ(e) uberein. Insbesonderegilt e ∈ Ker(ϕ). Sind nun x, y ∈ Ker(ϕ) so gilt ϕ(xy−1) = ϕ(x)ϕ(y−1) =e′ϕ(y)−1 = (e′)−1 = e′, d. h. U = Ker(ϕ) ist Untergruppe von (G, ·). Sei jetzta ∈ G beliebig. Dann folgt fur jedes u ∈ U wegen ϕ(aua−1) = ϕ(a)ϕ(u)ϕ(a−1) =ϕ(a)e′ϕ(a)−1 = e′ bereits aua−1 ∈ U . Also gilt aUa−1 ⊆ U und damit aU ⊆ Ua.Dual folgt Ua ⊆ aU , d. h. U = Ker(ϕ) ist Normalteiler.

b) Es ist xκKer(ϕ)y genau dann, wenn e′ = ϕ(xy−1) = ϕ(x) ·ϕ(y)−1 ist, also genaudann, wenn ϕ(x) = ϕ(y) gilt.

c) Definiere ψ : G/Ker(ϕ) → ϕ(X) wie angegeben gemaß ψ([x]) = ϕ(x) furalle [x] ∈ G/Ker(ϕ). Dann ist ψ wohldefiniert, denn [x] = [y] ist gleichwertig zuxy−1 ∈ Ker(ϕ), also zu xy−1 = k fur ein k ∈ Ker(ϕ), also zu x = ky fur ein


2.1 Gruppen 73

k ∈ Ker(ϕ). Hieraus folgt aber ϕ(x) = ϕ(ky) = ϕ(k)ϕ(y) = ϕ(y). Ersichtlichist ψ surjektiv. Die Injektivitat folgt aus ψ([x]) = ψ([y]) → ϕ(x) = ϕ(y) →ϕ(xy−1) = ϕ(x)ϕ(y)−1 = e′ → xy−1 ∈ ker(ϕ) → [x] = [y]. Schließlich ist ψ einHomomorphismus wegen ψ([x][y]) = ψ([xy]) = ϕ(xy) = ϕ(x)ϕ(y) = ψ([x])ψ([y]).

d) Es ist νKer(ϕ) ◦ψ(x) = ψ([x]) = ϕ(x) fur alle x ∈ G. Daher gilt νKer(ϕ) ◦ψ = ϕ.Aus νKer(ϕ) ◦ ψ1 = ϕ = νKer(ϕ) ◦ ψ2 folgt aber bereits ψ1([x]) = ψ2([x]) fur alle[x] ∈ G/Ker(ϕ), also ψ1 = ψ2. �

Satz 2.38 Satz von Cayley Jede Gruppe ist zu einer Untergruppe einer Sym-metrischen Gruppe isomorph.

Beweis: Sei (G, ·) eine beliebige Gruppe. Fur jedes x ∈ G ist jede Rechtstransla-tion %x : G→ G bijektiv und liegt damit in der Symmetrischen Gruppe (SG, ◦).Definiere ϕ : G→ SG durch ϕ(x) = %x fur alle x ∈ G. Dann ist ϕ injektiv, dennϕ(x) = ϕ(x′) bedeutet die Gleichheit %x = %x′ der beiden Rechtstranslationen,also insbesondere die Gleichheit %x(e) = %x′(e) fur das Einselement e von (G, ·),was naturlich x = x′ liefert. Außerdem gilt fur beliebige Elemente x, x′ ∈ G undalle y ∈ G auch

%xx′(y) = y(xx′) = (yx)x′ = (%x ◦ %x′)(y),

woraus ϕ(xx′) = %xx′ = %x ◦ %′x = ϕ(x) ◦ ϕ(x′) folgt. Daher ist ϕ sogar einHomomorphismus und damit (G, ·) isomorph zu der Untergruppe ϕ(G) von SG.�

2.1.3 Permutationsgruppen

Definition 2.39 Unter einer Permutationsgruppe versteht man eine beliebigeUntergruppe einer Symmetrischen Gruppe S(A) auf einer Menge A, also einElement von Sub(S(A)).

Lemma 2.40 Es seien A 6= ∅ 6= B Mengen. Aus A ∼ B folgt S(A) ∼= S(B).Existiert eine injektive Abbildung f : A → B, dann ist S(A) isomorph zu einerUntergruppe von S(B).

Beweis: Sei f : A→ B eine Bijektion. Fur jede Permutation π ∈ S(A) ist dannπ′ := f−1 ◦ π ◦ f eine Permutation von B und die Abbildung ϕ : S(A) → S(B)gemaß ϕ(π) := π′ ist ein Isomorphismus.

Rest: Ubung! �


2.1 Gruppen 74

Definition 2.41 Es sei a ∈ A 6= ∅ und π ∈ S(A). Gilt a = π(a) so heißt aFixpunkt von π, andernfalls mobil bei π.

Permutationen π1, π2 ∈ S(A) heißen (elemente)fremd, wenn fur alle a ∈ A gilt: aist Fixpunkt von π1, wenn a mobil bei π2 ist.

Lemma 2.42 Sind π1, π2 ∈ A fremd, so gilt π1 ◦ π2 = π2 ◦ π1.

Beweis: Mit Kontraposition ist die Voraussetzung gleichwertig dazu, daß fur allea ∈ A gilt: a ist Fixpunkt von π2, wenn a mobil bei π1 ist. Unterscheide nun dreiFalle:

1. π1(a) = a = π2(a): Dann gilt offensichtlich (π1 ◦ π2)(a) = a = (π2 ◦ π1)(a).

2. π1(a) 6= a: Dann folgt aber π2(a) = a und π1(π1(a)) 6= π1(a) und daherauch π2(π1(a)) = π1(a). Nun hat man (π1 ◦ π2)(a) = π2(π1(a)) = π1(a)) und(π2 ◦ π1)(a) = π1(π2(a)) = π1(a), also ebenfalls (π1 ◦ π2)(a) = (π2 ◦ π1)(a).

3. π2(a) 6= a: Dieser Fall entsteht aus dem 2. Fall durch Vertauschung der Rollenvon π1 und π2.

Damit gilt in jedem Fall (π1 ◦ π2)(a) = (π2 ◦ π1)(a). �

Lemma 2.43 Es sei U ∈ Sub(S(A)) eine Permutationsgruppe. Die RelationτU ∈ A2 sei definiert durch

a τU b :↔ ∃π ∈ U : π(a) = b.(147)

Dann ist τU Aquivalenzrelation auf A.

Beweis: Wegen ιA ∈ U ist τU reflexiv, wegen (135) ist τU symmetrisch, wegen(134) transitiv. �

Definition 2.44 Die Elemente der Faktormenge A/τU heißen Transitivitatsge-biete von U . Im Fall τU = ωA = A× A nennt man U transitiv.

Definition 2.45 Es sei a ∈ A und π ∈ S(A). Dann heißt O(π, a) := {πn(a) |n ∈ Z} der Orbit oder die Bahn von a bezuglich π.


2.1 Gruppen 75

Bemerkung 2.46 Die Bahnen sind die Transitivitatsgebiete der von π erzeugtenzyklischen Untergruppe < π > von S(A).

Es sind zwei Falle moglich: 1. Alle πn(a) sind paarweise verschieden. Dann ist dieBahn (abzahlbar) unendlich.

2. Es gibt n 6= m aus Z mit πn(a) = πm(a). Dies ist offensichtlich gleichwertigdamit, daß ein minimales k ∈ N mit a = πk(a) existiert. In diesem Fall ist dieBahn endlich und k = |O(π, a)| ihre Lange.

Zur Untersuchung von endlichen Permutationsgruppen kann man die endlicheMenge A immer durch eine der Mengen Mn := {1, . . . , n} fur n ∈ N ersetzen. Manschreibt dann kurz Sn oder Sn fur S({1, . . . , n}) und notiert eine Permutationπ ∈ Sn in der Form

π =(

1 2 . . . nπ(1) π(2) . . . π(n)

).

Man beachte, daß stets Sn ⊆ Sn+1 gilt.

Beispiel 2.47 Fur die identischen Abbildung π =(

1 . . . n1 . . . n

)∈ Sn schreibt

man abkurzend immer π = (1). Dann gilt S1 = {(1)} und diese SymmetrischeGruppe ist offensichtlich kommutativ.

Unter einer Transposition versteht man eine Permutation π ∈ Sn, die genauzwei Elemente i 6= j aus Mn gemaß π(i) = j und π(j) = i vertauscht undalle anderen k ∈ Mn \ {i, j} gemaß π(k) = k fix laßt. Man schreibt dann kurzπ = (i j) = (j i), wobei man meistens i < j wahlt. Es ist dann stets π2 = (1),also jede Transposition zu sich selbst invers. Fur n = 2 liegt in S2 neben (1) nochgenau die Transposition (1 2), und daher ist auch S2 kommutativ.

In S3 liegen neben (1) und den Transpositionen (1 2), (1 3) und (2 3) noch derenProdukte, z. B. π := (1 2)◦(1 3). Wegen π(1) = 2, π(2) = 3 und π(3) = 1 bewirktπ also eine zyklische Vertauschung dieser drei Elemente, was man auch kurz als(1 2 3) notiert. Entsprechend gilt dann (1 3 2) = (1 3) ◦ (1 2) und diese beidenProdukte sind verschieden. Also ist S3 und damit jede Symmetrische Gruppe Sn

mit n ≥ 3 nicht kommutativ.

Definition 2.48 Eine Permutation π ∈ Sn heißt ein Zyklus oder eine zyklischeVertauschung der Lange `, wenn es paarweise verschiedene Zahlen i1, . . . , i` ∈Mn

mit π(ik) = ik+1 fur k = 1, . . . , ` − 1 und π(i`) = i1 gibt. Man schreibt dannπ = (i1 i2 . . . i`).


2.1 Gruppen 76

Lemma 2.49 a) Jeder Zyklus der Lange ` > 1 kann gemaß (i1 i2 . . . i`) =(i1 i2) ◦ (i1 i3) ◦ . . . ◦ (i1 i`) als Produkt von ` − 1 Transpositionen geschriebenwerden. Fur n > 1 kann auch (1) = (1 2) ◦ (1 2) als Produkt von Transpositionengeschrieben werden.

b) Sind π1 und π2 elementefremde Zyklen aus Sn, so gilt π1 ◦ π2 = π2 ◦ π1.

c) Jede Permutation aus Sn kann als Produkt elementefremder Zyklen geschriebenwerden. Diese Darstellung ist bis auf die Reihenfolge der Zyklen eindeutig.

Beweis: Ubung! �

Definition 2.50 Es seien π ∈ Sn fur n ≥ 2 und 1 ≤ i < j ≤ n. Dann heißt(i, j) eine Inversion von π, wenn π(j) < π(i) gilt, und π heißt gerade (ungerade),wenn die Anzahl der Inversionen von π gerade (ungerade) ist. Man definiert dasSignum von π als sgn(π) := +1, falls π gerade ist, und sgn(π) := −1 sonst. DieMenge aller geraden Permutationen in Sn wird als An oder An notiert.

Beispiel 2.51 Die identische Abbildung (1) ist eine gerade Permutation.

Jede Transposition ist ungerade, denn

(i j) =(

1 2 . . . i− 1 i i+ 1 . . . j − 1 j j + 1 . . . n1 2 . . . i− 1 j i+ 1 . . . j − 1 i j + 1 . . . n

)

besitzt genau die Inversionen (j, i + 1), (j, i + 2), . . . , (j, j − 1), (j, i) und (i +1, i), (i+ 2, i), . . . , (j − 1, i), also eine ungerade Anzahl.

In S3 gelten noch sgn((1 2 3)) = sgn((1 3 2)) = −1. Es ist also |A2| = |S2|/2 und|A3| = |S3|/2.

Satz 2.52 Fur alle π1, π2 ∈ Sn gilt sgn(π1 ◦ π2) = sgn(π1) · sgn(π2), d. h. sgn :Sn → {−1,+1} ist ein Homomorphismus von (Sn, ◦) in die Gruppe ({−1,+1}, ·).Insbesondere gilt sgn((i1 . . . i`)) = (−1)`−1.

Eine Permutation ist genau dann gerade, wenn sie als Produkt einer geradenAnzahl von Transpositionen darstellbar ist.

(An, ◦) ist Normalteiler von (Sn, ◦) mit |An| = |Sn|/2.



2.2 Ringe 77

2.2 Ringe

Definition 2.53 Unter einem Ring (R,+, ·) versteht man eine nichtleere Trager-menge R zusammen mit zwei binaren Operationen, einer Addition + und einerMultiplikation ·, so daß folgendes gilt:

(1) (R,+) ist ein Modul mit dem Nullelement 0.

(2) (R, ·) ist ein Gruppoid.

(3) Es gelten die Distributivgesetze a ·(b+c) = a ·b+a ·c und (b+c) ·a = b ·a+c ·afur alle a, b, c ∈ R.

Ein Ring heißt kommutativ (idempotent, Ring mit Einselement), wenn das Grup-poid (R, ·) die jeweilige Eigenschaft hat.

Handelt es sich bei (R, ·) um eine Halbgruppe, so spricht man auch von einemassoziativen Ring.

Assoziative und idempotente Ringe mit Einselement werden auch Boolesche Rin-ge genannt.

Bemerkung 2.54 Die Distributivgesetze besagen gerade, daß die Links- undRechtstranslationen von (R, ·) bereits Endomorphismen des Moduls (R,+) sind.Man beachte, daß die rechten Seiten der Distributivgesetze nur definiert sind,wenn man die ubliche Prioritatsregel “Punktrechnung vor Strichrechnung” an-wendet.

Folgerung 2.55 Fur alle Elemente a, b, c ∈ R eines Ringes (R,+, ·) gelten:

(1) 0 · a = 0 = a · 0, das Nullelement ist also absorbierend.

(2) (−a) · b = −(a · b) = a · (−b) und (−a) · (−b) = a · b, die ublichen Vorzeichen-regeln.

(3) a · (b− c) = a · b− a · c.

(4) (b− c) · a = b · a− c · a.

Beweis: (1) Es gilt 0 · a+ 0 · a = (0 + 0) · a = 0 · a = 0 · a+ 0 und durch Kurzenvon 0 · a in dem Modul (R,+) folgt 0 · a = 0. Dual ergibt sich 0 = a · 0.


2.2 Ringe 78

(2) Wegen der Distributivgesetze und (1) gilt a·b+(−a)·b = (a+(−a))·b = 0·b = 0und daher (−a) · b = −(a · b) im Modul (R,+). Dual folgt die zweite Gleichung.Hieraus ergibt sich dann (−a) · (−b) = −(a · (−b)) = −(−[a · b]) = a · b.

(3) Nach Definition der Differenz gilt wegen der Distributivgesetze a · (b − c) =a · (b+ (−c)) = a · b+ a · (−c) = a · b+ (−(a · c)) = a · b− a · c.

(4) ist dual zu (3). �

Definition 2.56 Es sei (R,+, ·) ein Ring. Elemente a, b ∈ R \ {0} mit a · b = 0heißen Nullteiler in R. (R,+, ·) heißt nullteilerfrei, wenn a · b = 0 → a = 0∨ b = 0fur alle a, b ∈ R gilt.

Unter einem Integritatsbereich (R,+, ·) versteht man einen assoziativen, kommu-tativen und nullteilerfreien Ring mit Einselement 1 6= 0.

Ein Schiefkorper ist ein assoziativer Ring mit Einselement 1 6= 0, fur den R∗ =R \ {0} gilt, fur den also (R \ {0}, ·) Gruppe ist.

Ein kommutativer Schiefkorper wird Korper genannt.

Beispiel 2.57 a) Der Nullring ({0},+, ·) mit den Operationen 0 + 0 = 0 = 0 · 0ist ein kommutativer, nullteilerfreier Boolescher Ring, der aber wegen 1 = 0 keinIntegritatsbereich ist.

b) Fur jeden Modul (R,+) mit dem Nullelement 0 wird durch a · b := 0 eineassoziative und kommutative Multiplikation auf R definiert, so daß (R,+, ·) einRing ist. Er wird der Zeroring auf (R,+) genannt. Fur |R| > 1 sind alle von 0verschiedenen Elemente Nullteiler.

c) Die ganzen Zahlen (Z,+, ·) sind ein Integritatsbereich, der kein Korper ist.

d) Die rationalen Zahlen (Q,+, ·), die reellen Zahlen (R,+, ·) und die komplexenZahlen (C,+, ·) sind Korper.

e) Wegen Folgerung 1.37 ist fur jede MengeM 6= ∅ die Potenzmenge (P(M),∆,∩)ein Boolescher Ring mit dem Einselement M , der fur |M | ≥ 2 Nullteiler besitzt.Dann gilt namlich fur a 6= b aus M sowohl {a} 6= ∅ 6= {b} als auch {a}∩{b} = ∅.Fur M = {a} dagegen erhalt man einen Korper, dessen Cayley-Tafeln mit denAbkurzungen 0 := ∅ und 1 := M wie folgt aussehen.

+ 0 10 0 11 1 0

· 0 10 0 01 0 1


2.2 Ringe 79

Dieser zweielementige Korper beschreibt die Addition und Multiplikation modulo2, welche die Grundlage der Arithmetik in jedem Digitalrechner sind.

f) Es sei (G,+) ein Modul. Fur ϕ, ψ ∈ End(G) sei eine Addition gemaß(ϕ + ψ)(g) = ϕ(g) + ψ(g) fur alle g ∈ G definiert. Dann ist (End(G),+, ◦)ein assoziativer Ring mit Einselement ιG, der Endomorphismenring von (G,+).

Bemerkung 2.58 Jeder endliche Integritatsbereich ist bereits ein Korper.

Es gilt der Satz von Wedderburn (Joseph Wedderburn, 1882 - 1948): Jeder end-liche Schiefkorper ist bereits ein Korper.

Die Hamiltonschen Quaternionen (William Rowan Hamilton, 1805 - 1865) bildeneinen nicht-kommutativen Schiefkorper.

Definition 2.59 Ein Unterring (U,+, ·) eines Ringes (R,+, ·) ist eine Teilmenge∅ 6= U ⊆ R, so daß (U,+) Untermodul von (R,+) und (U, ·) Untergruppoid von(R, ·) ist. Die Menge aller Unterringe von (R,+, ·) werde mit Sub(R) bezeichnet.

Lemma 2.60 Ist (Ui)i∈I eine Familie von Unterringen eines Ringes (R,+, ·), soist D :=

⋂Ui ∈ Sub(R). Daher existiert fur jede Teilmenge A ⊆ R auch der

kleinste Unterring von (R,+, ·), der A umfaßt.

Beweis: Ubung! �

Definition 2.61 Es sei (R,+, ·) ein Ring mit Einselement e 6= 0. Dann heißtχ(R) := o(e), falls diese Ordnung von e im Modul (R,+) endlich ist, und χ(R) :=0 sonst, die Charakteristik von (R,+, ·).

Lemma 2.62 Fur einen Integritatsbereich (R,+, ·) ist χ(R) = 0 oder χ(R) = peine Primzahl.

Beweis: Sei χ(R) = n = m · k mit 1 ≤ m, k ≤ n. Dann ist me :=∑m

i=1 e 6= 0und ke =

∑ki=1 e 6= 0 wegen der Minimalitat von n als Ordnung von e in (R,+).

Andererseits ist 0 = ne = me · ke und damit (R,+, ·) nicht nullteilerfrei. �


http://de.wikipedia.org/wiki/Joseph_Wedderburn

http://de.wikipedia.org/wiki/William_Rowan_Hamilton

2.2 Ringe 80

Definition 2.63 Eine Kongruenz(relation) eines Ringes (R,+, ·) ist eine Aqui-valenzrelation κ ∈ E(R), die sowohl Kongruenz des Moduls (R,+) als auch Kon-gruenz des Gruppoids (R, ·) ist, d. h. es muß

aκb→ (a+ c)κ (b+ c) ∧ a · c κ b · c ∧ c · a κ c · b(148)

fur alle a, b, c ∈ R gelten.

Lemma 2.64 Ist κ Kongruenzrelation des Ringes (R,+, ·), dann werden durch

[a]κ + [b]κ := [a+ b]κ,(149)

[a]κ · [b]κ := [a · b]κ(150)

binare Operationen auf der Faktormenge R/κ definiert, so daß (R/κ,+, ·) eben-falls ein Ring ist, der Restklassenring von (R,+, ·) nach κ. Mit (R,+, ·) ist auch(R/κ,+, ·) assoziativ, kommutativ oder Ring mit Einselement.


Beispiel 2.65 Die Kongruenz modulo n, also a ≡ b ↔ a − b ∈ nZ ist fur jedesn ∈ N0 eine Kongruenz auf dem Ring (Z,+, ·) der ganzen Zahlen.

Daher ist der Restklassenring modulo n ein assoziativer und kommutativer Ring(Z/(n),+, ·) mit Einselement [1]n. Wie das Beispiel n = 4 zeigt, muß dies nichtimmer ein Integritatsbereich sein, denn dann gilt [2]4 · [2]4 = [4]4 = [0]4.

Definition 2.66 Es seien (R,+, ·) und (R′,⊕,�) Ringe. Eine Abbildung ϕ :R→ R′ heißt ein (Ring-)Homomorphismus, wenn

ϕ(a+ b) = ϕ(a)⊕ ϕ(b)(151)

ϕ(a · b) = ϕ(a)� ϕ(b)(152)

jeweils fur alle a, b ∈ R gelten, wenn also ϕ sowohl ein Modul-Homomorphismusvon (R,+) in (R′,⊕) als auch ein Gruppoid-Homomorphismus von (R, ·) in(R′,�) ist. Sind (R,+, ·) und (R′,⊕,�) beides Ringe mit Einselement, so mußnoch

ϕ(e) = e′(153)


2.2 Ringe 81

fur die Einselemente gelten. Unter dem Kern des Ringhomomorphismus verstehtman dann den Kern Ker(ϕ) = {a ∈ R | ϕ(a) = 0} des Modulhomomorphismus.Die Bezeichnungen Epimorphismus, Monomorphismus, Isomorphismus, Endo-morphismus und Automorphismus sind dann wie bei Gruppoid-Homomorphismendefiniert und werden gegebenenfalls mit dem Zusatz “Ring-” versehen.

Bemerkung 2.67 Ist (R′,⊕,�) Integritatsbereich und ϕ nicht die konstanteNullabbildung, so folgt (153) bereits aus (151) und (152). Dann existiert namlichein a 6= 0 aus R mit ϕ(a) 6= 0′ und damit e′ ·ϕ(a) = ϕ(a) = ϕ(e · a) = ϕ(e) ·ϕ(a).Die Rechtskurzbarkeit von ϕ(a) 6= 0′ in (R′,⊕,�) liefert dann die Behauptung.

Definition 2.68 Es sei (R,+, ·) ein Ring. Eine Teilmenge ∅ 6= I ⊆ R heißt einIdeal von (R,+, ·), wenn fur alle a, b ∈ I und r ∈ R gilt

a− b ∈ I, d. h. (I,+) ist Untermodul (also Normalteiler) von (R,+),

r · a ∈ I und a · r ∈ I.

Insbesondere ist also I ∈ Sub(R).

Lemma 2.69 Fur jeden Ringhomomorphismus ϕ : R→ R′ ist Ker(ϕ) ein Idealvon (R,+, ·).

Beweis: Da ϕ : R→ R′ insbesondere ein Modulhomomorphismus ist, ist Ker(ϕ)Normalteiler von (R,+). Aus a ∈ Ker(ϕ), also ϕ(a) = 0 folgt ϕ(r · a) = ϕ(r) ·ϕ(a) = 0, also r · a ∈ Ker(ϕ) und dual auch a · r ∈ Ker(ϕ). �

Satz 2.70 Es sei (I,+, ·) Ideal von (R,+, ·) und κ eine Kongruenz auf (R,+, ·).Dann gelten die folgenden Aussagen:

a) Die durch a κI b ↔ a − b ∈ I fur alle a, b ∈ R definierte Relation ist eineKongruenz auf (R,+, ·).

b) Die Kongruenzklasse I := [0]κ ist ein Ideal von (R,+, ·).

c) Es gilt κ = κIκ und I = IκI.



2.2 Ringe 82

Bemerkung 2.71 Ist I Ideal eines Ringes (R,+, ·), so schreibt man R/I fur denRestklassenring (R/κI ,+, ·).

Es gilt der Homomorphiesatz fur Ringe: Jedes homomorphe Bild (ϕ(R),+, ·) einesRinges (R,+, ·) ist isomorph zum Restklassenring (R/Ker(ϕ),+, ·).

Definition 2.72 Es sei (R,+, ·) ein assoziativer Ring mit Einselement. Ein Po-lynom uber (R,+, ·) in der Unbestimmten x ist dann eine endliche Summe derForm

f(x) = a0 + a1x+ a2x2 + . . .+ anx

n =n∑

i=0

aixi

mit Koeffizienten ai ∈ R. Außer beim Nullpolynom f(x) = 0 existiert immer einKoeffizient an 6= 0 mit dem hochsten Index n. Diesen nennt man den Leitkoeffizi-enten und n den Grad des Polynoms f(x), in Zeichen grad(f(x)) = n. Die Mengealler Polynome in der Unbestimmten x mit Koeffizienten aus R werde als R[x]notiert.

Seien f(x) =∑n

i=0 aixi, g(x) =

∑mj=1 bjx

j ∈ R[x]. Dann wird ihre Summe durch

(f + g)(x) =max(n,m)∑

k=0

(ak + bk)xk

definiert, wobei ak := 0 fur k > n und bk := 0 fur k > m gesetzt werde. Dagegenwird ihr Produkt durch

(f · g)(x) :=n+m∑k=0

ckxk mit ck =

∑k=i+j

ai · bj

festgelegt.

Satz 2.73 Es ist (R[x],+, ·) ebenfalls ein assoziativer Ring mit Einselement.Genau dann ist (R[x],+, ·) kommutativ (nullteilerfrei), wenn dies fur (R,+, ·)gilt.


Bemerkung 2.74 Da R[x] ebenfalls assoziativer Ring mit Einselement ist, exi-stiert dann auch R[x, y] := (R[x])[y] in der Unbestimmten y, also ein Polynom-ring in zwei Unbestimmten x, y. So fortfahrend gelangt man zum PolynomringR[x1, . . . , xn] in endlich vielen Unbestimmten x1, . . . , xn uber R. Rechnungen indiesen Polynomringen bilden die Grundlage fur jedes Computeralgebra-System.Als Koeffizientenbereich wird dabei der Korper K = Q der rationalen Zahlenoder ein endlicher Korper K benutzt.


2.3 Korper 83

Aufgabe 2.75 Zeigen Sie, daß in jedem Polynomring (K[x],+, ·) uber einemKorper (K,+, ·) die Division mit Rest wie folgt moglich ist. Zu f [x], g(x) ∈ K[x]mit g(x) 6= 0 existieren eindeutig bestimmte Polynome q(x), r(x) ∈ K[x] mitf(x) = q(x)g(x) + r(x) und r(x) = 0 oder grad(r(x)) < grad(g(x)).

2.3 Korper

Definition 2.76 Es sei (K,+, ·) ein Korper. Unter einem Teilkorper oder Un-terkorper (U,+, ·) versteht man eine Teilmenge U ⊆ K mit |U | ≥ 2 unda, b ∈ U → a − b ∈ U sowie a, b ∈ U , b 6= 0 → a · b−1 ∈ U . Man nennt dann(K,+, ·) auch einen Oberkorper von (U,+, ·) und spricht von einer Korpererwei-terung [K : U ], gelesen:“K uber U”.

Bemerkung 2.77 Wegen U 6= ∅ existiert ein a ∈ U und damit gilt 0 = a−a ∈ Ufur das Nullelement von K. Wegen |U | ≥ 2 gibt es aber auch ein a 6= 0 in U unddamit gilt e = a · a−1 ∈ U fur das Einselement e ∈ K.

Außerdem ist dann (U,+, ·) ebenfalls ein Korper.

Satz 2.78 Sei (K,+, ·) ein Schiefkorper, (R,+, ·) ein Ring und ϕ : K → R einRinghomomorphismus. Dann gilt entweder ϕ(K) = {0} oder ϕ ist injektiv, also(ϕ(K),+, ·) isomorph zu (K,+, ·).

Beweis: Ist ϕ nicht injektiv, so gibt es a 6= b aus K mit ϕ(a) = ϕ(b), alsoa− b 6= 0 und ϕ(a− b) = 0. Dann gilt aber c = c · (a− b)−1 · (a− b) fur alle c ∈ Kund daher ϕ(c) = ϕ(c · (a− b)−1) · ϕ(a− b) = 0, also ϕ(K) = {0}. �

Bemerkung 2.79 Da ein Korper nur diese beiden trivialen homomorphen Bilderbesitzt, hat er auch nur die beiden Kongruenzen ιK und ωK und die beiden Ideale{0} und K.

Aufgabe 2.80 Es seien a, b ∈ Z und d = ggT (a, b) ihr großter gemeinsamerTeiler. Zeigen Sie mit Hilfe des Euklidischen Algorithmus: Es gibt x, y ∈ Z mitd = x · a+ y · b. Der ggT (a, b) laßt sich also nicht nur immer berechnen, sondernauch aus a und b “linear kombinieren”.


2.3 Korper 84

Beispiel 2.81 Der Restklassenring (Z/(n),+, ·) ist genau dann ein Korper, wennn eine Primzahl ist. Ist namlich n = a · b zerlegbar mit 1 < a, b < n, so gilt[a]n 6= [0]n 6= [b]n, aber [a]n · [b]n = [n]n = [0]n, d. h. (Z/(n),+, ·) besitzt Nullteilerund kann daher kein Korper sein. Ist andererseits n eine Primzahl und [a]n 6= [0]naus Z/(n) mit einem Reprasentanten 1 ≤ a ≤ n − 1, so gilt ggT (a, n) = 1 undmit dem Euklidischen Algorithmus kann man Zahlen x, y ∈ Z bestimmen mit1 = x · a+ y ·n. Dann gilt [1]n = [x]n[a]n + [y]n[n]n = [x]n[a]n, d. h. [x]n 6= [0]n istInverses zu [a]n in der kommutativen Halbgruppe (Z/(n), ·). Daher ist (Z/(n),+, ·)ein Korper.

Beispiel 2.82 Wie Beispiel 2.81 zeigt, sind in (Z/(n),+, ·) genau die Elemente[a]n invertierbar, fur die ggT (a, n) = 1 ist, fur die a also teilerfremd zu n ist.Man bezeichnet die Gruppe (Z/(n)∗, ·) dieser Einheiten von (Z/(n), ·) als primeRestklassengruppe modulo n und nennt ihre Ordnung ϕ(n) := |Z/(n)∗| den Wertder Eulerschen ϕ-Funktion (Leonhard Euler, 1707 - 1783) an der Stelle n ≥ 2.Man setzt noch ϕ(1) := 1. Es ist also ϕ(n) die Anzahl der zu n teilerfremdenZahlen a ∈ Z mit 1 ≤ a ≤ n. Insbesondere ist ϕ(p) = p − 1 fur jede Primzahl pund ϕ(pr) = pr−1(p− 1) fur jede Primzahlpotenz.

Wie bei Gruppen und Ringen kann man zeigen:

Lemma 2.83 Ist (Ui)i∈I eine Familie von Unterkorpern eines Korpers (K,+, ·),dann ist D =

⋂Ui ebenfalls ein Unterkorper von (K,+, ·). Daher ist Sub(K)

ein vollstandiger Verband. Man nennt P = infSub(K), also den Durchschnittaller Unterkorper von (K,+, ·), den Primkorper von (K,+, ·). Er hat wie alleUnterkorper von (K,+, ·) dieselbe Charakteristik. Im Fall χ(K) = 0 ist (P,+, ·)isomorph zu (Q,+, ·), im Fall χ(K) = p ist er isomorph zu (Z/(p),+, ·).


Bemerkung 2.84 Fur n ∈ N gibt es genau dann einen (endlichen) Korper mit nElementen, wenn n = pr fur eine Primzahl p und einen Exponenten r ∈ N gilt. Einderartiger Korper ist bis auf Isomorphie eindeutig bestimmt und wird mit GF (pr)oder Fpr bezeichnet und Galois-Feld oder Galois-Korper genannt (Evariste Galois,1811 - 1832). Es ist immer Z/(p) Primkorper von GF (pr) und beide haben dieCharakteristik p.

In der Informatik, speziell der Codierungstheorie, werden insbesondere die Galois-Felder GF (2r) fur bestimmte Exponenten r benotigt, etwa r = 8, r = 64, r = 256etc.

Beispielsweise ist GF (22) auf der Menge {0, 1, a, b} durch die folgenden Cayley-Tafeln gegeben


http://de.wikipedia.org/wiki/Leonhard_Euler

http://de.wikipedia.org/wiki/Evariste_Galois

http://de.wikipedia.org/wiki/Evariste_Galois

2.3 Korper 85

+ 0 1 a b0 0 1 a b1 1 0 b aa a b 0 1b b a 1 0

· 0 1 a b0 0 0 0 01 0 1 a ba 0 a b 1b 0 b 1 a

Beispiel 2.85 Es sei k ∈ N keine Quadratzahl. Wie im Fall k = 2 kann manzeigen, daß

√2 6∈ Q gilt. Es gibt nun einen kleinsten Unterkorper (D,+, ·)

von (R,+, ·), der A := Q ∪ {√k} enthalt, namlich den Durchschnitt uber

alle Unterkorper (U,+, ·) von (R,+, ·) mit A ⊆ U . Man kann zeigen, daßD = Q(

√k) := Q + Q

√k := {a + b

√k | a, b ∈ Q} gilt. Jeder dieser quadrati-

schen Zahlkorper hat (Q,+, ·) als Primkorper und damit die Charakteristik 0. Esist jeweils Z(

√k) := Z + Z

√k ein Untering von Q(

√k) und damit ein Integritats-

bereich. Weiterhin ist jedes Element aus Q(√k) ein Quotient von zwei Elementen

aus Z(√k).

Ersetzt man in allen diesen Uberlegungen k durch −k, dann erhalt man Un-terkorper Q + Q

√−k und Unterringe Z + Z

√−k von (C,+, ·). Hier kann man

auch k = −1 wahlen und erhalt so speziell den Ring der ganzen GaußschenZahlen Z + Zi (Carl Friedrich Gauß, 1777 - 1855).


http://de.wikipedia.org/wiki/Carl_Friedrich_Gauss

3 Aufgaben 86

3 Aufgaben

Aufgabe 3.1 Zeigen Sie, daß die folgenden Implikationen Tautologien sind.

a) A ∧B → A,

b) A→ A ∨B,

c) ¬A→ (A→ B),

d) A ∧ (A→ B) → B,

e) (A ∨B) ∧ (¬A ∨B) → B,

f) ¬(A→ B) → (B → A),

g) (A→ B) ∧ (B → C) → (A→ C).

Aufgabe 3.2 Ist (((¬A) → B) → (A → (¬B))) eine Tautologie? (Beweis oderGegenbeispiel.)

Aufgabe 3.3 Geben Sie eine disjunktive Normalform der Formel (((¬A) →B) → (A→ (¬B))) aus Aufgabe 3.2 an.

Aufgabe 3.4 Geben Sie eine konjunktive Normalform der Formel (((¬A) →B) → (A→ (¬B))) aus Aufgabe 3.2 an.

Aufgabe 3.5 Zeigen Sie, daß (((¬A) → B) → (((¬A) → (¬B)) → A)) eineTautologie ist.

Aufgabe 3.6 Zeigen Sie, daß (A → B) ∧ (¬(B → C) → ¬A) → (A → C) eineTautologie ist.

Aufgabe 3.7 Beweisen Sie die folgenden drei Aquivalenzen:

a) (¬x ∧ ¬y) → ¬z ≡ z → (x ∨ y),

b) (¬x ∨ y) → z ≡ (x ∧ ¬y) ∨ z,

c) ¬x→ (y ∨ z) ≡ ¬y → (¬z → x).


3 Aufgaben 87

Aufgabe 3.8 Zeigen Sie, daß sich auch die Junktoren ∨ und ∧ allein durch ¬und → ausdrucken lassen, daß also auch die Menge {¬,→} funktional vollstandigist.

Aufgabe 3.9 Der logische Junktor ↓ (Peirce-Pfeil) laßt sich definieren gemaßA ↓ B :≡ ¬A ∧ ¬B fur alle Aussagen A,B. Beweisen Sie die Aquivalenzen

a) ¬A ≡ A ↓ A,

b) A ∧B ≡ (A ↓ A) ↓ (B ↓ B).

Also ist auch {↓} eine funktional vollstandige Menge von Junktoren. Geben Siejeweils eine Darstellung von ∨ und von → durch ↓ an.

Aufgabe 3.10 Der logische Junktor | (Sheffer-Strich) laßt sich definieren durchA | B :≡ ¬(A∧B) (“NAND”) fur alle Aussagen A,B. Beweisen Sie die folgendenAquivalenzen:

a) ¬A ≡ A | A,

b) A ∨B ≡ (A | A) | (B | B).

Also ist auch {|} eine funktional vollstandige Menge von Junktoren. Geben Siejeweils eine Darstellung von ∧ und von → durch | an.

Aufgabe 3.11 Zeigen Sie, daß die Menge F{¬,∨}({A}) aller aussagenlogischenFormeln, die mit nur einer Variablen A und ausschließlich mit den Junktoren ¬und ∨ gebildet werden konnen, abzahlbar unendlich ist. Zeigen Sie dann, daßes eine Menge A ⊆ F{¬,∨}({A}) von vier Formeln dieser Art gibt, so daß jedeFormel aus F{¬,∨}({A}) zu genau einer Formel aus A gleichwertig ist.

Zusatz: Wie andert sich die Situation, wenn man statt einer Variablen A endlichviele A1, . . . , An nimmt? Was passiert, wenn man abzahlbar viele Variablen Ai

fur i ∈ N0 zulaßt?

Aufgabe 3.12 Der Teilerverband (T (n), ggT, kgV ) einer naturlichen Zahl n > 1ist im allgemeinen keine Boolesche Algebra (T (n), ggT, kgV,′ ), wie das Beispieln = 4 mit T (n) = {1, 2, 4} zeigt. Fur Primzahlen n = p ist aber T (p) = {1, p}naturlich die zweielementige Boolesche Algebra. Geben Sie Beispiele fur (unend-lich viele) zusammengestzte Zahlen n an, fur die der Teilerverband eine BoolescheAlgebra ist.


3 Aufgaben 88

Aufgabe 3.13 Das Universum einer (sehr armen!) Mengenlehre bestehe nur ausder leeren Menge ∅ und den beiden Einermengen {∅} und {{∅}}. Zeigen Sie daßin dieser Mengenlehre das Nullmengenaxiom, das Extensionalitatsaxiom und dasAussonderungsaxiom erfullt sind. Sind auch das Paarmengenaxiom bzw. das klei-ne Vereinigungsmengenaxiom erfullt? Wie sieht es mit dem großen Vereinigungs-mengenaxiom aus?

Aufgabe 3.14 Das Universum einer (noch armeren) Mengenlehre bestehe nuraus den beiden Mengen ∅ und {∅}. In dieser Mengenlehre gelten das Nullmen-genaxiom, das Extensionalitatsaxiom, das kleine und das große Vereinigungs-mengenaxiom und das Aussonderungsaxiom. Das Potenzmengenaxiom und dasPaarmengenaxiom gelten aber nicht.

Aufgabe 3.15 Die paarweise verschiedenen Mengen Xn seien fur n ∈ N0 wiefolgt definiert. Es sei X0 := ∅ und Xn+1 := {Xn} sonst. Zeigen Sie zunachstdurch vollstandige Induktion nach n, daß Xn 6= Xn+1+k fur alle k ∈ N0 gilt.

Als Mengen in einem Universum der Mengenlehre werden nun diejenigen Teilmen-gen von {X0, X1, X2, . . .} betrachtet, in denen nur endlich vieleXn mit ungerademIndex n vorkommen. Insbesondere liegen alle Xn selbst in diesem Universum.Zeigen Sie, daß in dieser Mengenlehre das Nullmengenaxiom, das Extensiona-litatsaxiom, das Aussonderungsaxiom und das kleine Vereinigungsmengenaxiomgelten, aber nicht das große Vereinigungsmengenaxiom.

Aufgabe 3.16 Es seien F ⊆ A×B und G ⊆ B ×A Korrespondenzen zwischenMengen A und B und es gelten F ◦ G = ιA und G ◦ F = ιB. Dann sind F undG jeweils links- und rechtstotal sowie links- und rechtseindeutig, also zueinanderinverse Abbildungen.

Losung 3.17 (zu Aufgabe 3.1) a) Ist A wahr, so ist auch die Implikation wahr.Ist A falsch, dann auch A∧B, wodurch aber die behauptete Implikation ebenfallswahr ist.

b) Ist A falsch, dann ist die Implikation wahr. Ist A wahr, dann auch A∨B, unddamit auch die gesamte Implikation.

c) Ist A wahr, so ist ¬A falsch und daher die Implikation richtig. Ist A aberfalsch, so ist die Konklusion A→ B immer richtig, also die gesamte Implikationebenfalls.

d) Ist B wahr, dann ist die Implikation wahr. Sei daher B falsch. Ist dann nochA falsch, dann auch A ∧ (A → B) und damit die Pramisse, wodurch aber die


3 Aufgaben 89

Implikation wahr wird. Ist dagegen A wahr, dann ist A → B falsch und damitwiederum die Pramisse. Also ist die Implikation auch in diesem letzten Fall wahr.

e) Aufgrund des Distributivgesetzes ist die Pramisse gleichwertig zu (A∧¬A)∨Balso zu 0∨B ≡ B. Daher ist die gesamte Implikation gleichwertig zur TautologieB → B und damit ebenfalls immer wahr. (Man beachte, daß die Formel nur eineUmformulierung des Euklidischen Wahrheitskriteriums ist.)

f) Ist B falsch, so ist die Konklusion B → A wahr und daher auch die gesamteImplikation. Ist B wahr, dann auch A → B. Also ist die Pramisse falsch undfolglich die Implikation wahr.

g) Wenn A falsch ist, ist die Konklusion A → C wahr und daher ebenso dieImplikation. Sei also A wahr. Ist dann B falsch, so auch A → B und damit diegesamte Pramisse, wodurch die Implikation wiederum wahr ist. Seien also sowohlA als auch B wahr. Im Fall, daß dann C falsch ist, ist auch B → C falsch, also diegesamte Pramisse, wodurch auch jetzt die Implikation wahr wird. Ist schließlichauch noch C wahr, dann gilt naturlich die Implikation.

Losung 3.18 (zu Aufgabe 3.2) Die Wahrheitswertetabelle fur diese Implikationergibt

A B ¬A ¬B ¬A→ B A→ ¬B (¬A→ B) → (A→ ¬B)0 0 1 1 0 1 10 1 1 0 1 1 11 0 0 1 1 1 11 1 0 0 1 0 0

Man sieht also, daß die Aussage keine Tautologie ist und genau dann falsch wird,wenn beide Aussagen A und B richtig sind.

Beispielsweise erhalt man fur die Aussagen A: “ 2 ist eine gerade Zahl” und B: “ 2ist Primzahl”, die beide wahr sind, ¬A→ B als wahre Aussage (“ex falso quodli-bet”), aber A→ ¬B als falsche Aussage. Daher ist auch die gesamte Implikation(¬A→ B) → (A→ ¬B) falsch, also die Formel tatsachlich keine Tautologie.

Losung 3.19 (zu Aufgabe 3.3) Aus den Zeilen der Wahrheitswertetabelle derFormel, die den Wahrheitswert 1 ergeben, kann man ablesen, daß die Formelgenau dann wahr ist, wenn eine der drei Kombinationen der Wahrheitswerte vonA und B vorliegt, die in den ersten drei Zeilen beschrieben werden, also genaudann, wenn ¬A ∧ ¬B oder ¬A ∧ B oder A ∧ ¬B gilt. Also wird die Formel


3 Aufgaben 90

genau dann wahr, wenn (¬A∧¬B)∨ (¬A∧B)∨ (A∧¬B) gilt. Damit ist schoneine disjunktive Normalform gefunden. Diese ist aber keineswegs eindeutig. Ausden ersten beiden Zeilen kann man namlich auch ablesen, daß die Formel dannwahr ist, wenn A falsch ist, unabhangig von dem Wahrheitswert von B. Also isteine weitere (kurzere!) disjunktive Normalform durch ¬A ∨ (A ∧ ¬B) gegeben.Es geht aber noch besser. Nutzt man das Distributivgesetz aus, so ergibt sich alsgleichwertige Formel (¬A∨A)∧(¬A∨¬B), was sich mit “tertium non datur” undder Neutralitat von 1 gegenuber ∧ vereinfachen laßt zu ¬A∨¬B. Dies ist nun einekurzeste disjunktive Normalform und zugleich auch eine ebensolche konjunktiveNormalform!

Dies hatte man aber auch einfacher erkennen konnen. Aus der Wahrheitswerte-tabelle sieht man ja, daß die Formel genau dann falsch ist, wenn A und B wahrsind. Daher ist sie gleichwertig zu ¬(A∧B), was nach den De Morgenschen Regelnsofort zur Normalform ¬A ∨ ¬B fuhrt.

Losung 3.20 (zu Aufgabe 3.4) Aus den Zeilen der Wahrheitswertetabelle derFormel, die den Wahrheitswert 0 ergeben, kann man ablesen, daß die Formelgenau dann falsch ist, wenn die Kombination der Wahrheitswerte von A und Bvorliegt, die in der letzten Zeile beschrieben ist. Daher ist die Formel genau dannwahr, wenn diese Kombination nicht vorliegt, also wenn ¬(A∧B) gilt. Nach denDe Morganschen Regel ist sie daher gleichwertig zu ¬A ∨ ¬B, was schon einekonjunktive Normalform ist.

Losung 3.21 (zu Aufgabe 3.5) Die gesamte Implikation ist jedenfalls dann wahr,wenn ihre Pramisse falsch ist, also wenn (¬A) → B falsch ist. Außerdem ist siedann wahr, wenn die Pramisse ihrer Konklusion, also ¬A → ¬B, falsch ist. Esbleibt also nur noch der Fall, daß (¬A) → B und ¬A→ ¬B beides wahre Aussa-gen sind. Dann ergibt das Platonische Falschheitskriterium jedoch die Wahrheitvon ¬(¬A), also von A. Dann ist aber die Konklusion der Implikation wahr, alsodie gesamte Implikation. In jedem Fall ist daher die Implikation wahr.

Losung 3.22 (zu Aufgabe 3.6)

Es ist ¬(B → C) → ¬A wegen der Kontraposition gleichwertig zu A→ (B → C).Also ist die Pramisse gleichwertig zu (A → B) ∧ (A → (B → C). Hieraus folgtaber A → (B ∧ (B → C)). Wegen Aufgabe 3.1 d) folgt aus B ∧ (B → C)) aberC und daher ergibt sich aus der Pramisse mit Aufgabe 3.1 g) schließlich A→ C.

Losung 3.23 (zu Aufgabe 3.7) a) Kontraposition besagt, daß die rechte Seitegleichwertig ist zu ¬(x ∨ y) → ¬z. Die Pramissse dieser Implikation ist aber


3 Aufgaben 91

wegen der De Morganschen Regel gleichwertig zu ¬x∧¬y. Setzt man dies ein, soentsteht genau die linke Seite der behaupteten Aquivalenz.

b) Die linke Seite ist gleichwertig zu ¬(¬x∨y)∨z durch Auflosung der Implikation.Nach der De Morganschen Regel und der doppelten Verneinung ist dies aber danngleichwertig zu (x ∧ ¬y) ∨ z.

c) Die linke Seite ist gleichwertig zu (y ∨ z) ∨ x, wobei die Implikation aufgelostund die doppelte Verneinung verwendet wurde. Ebenso erhalt man fur die rechteSeite durch zweimalige Auflosung der Implikation und mit jeweils einer doppeltenVerneinung zuerst (¬z → x)∨y und dann (x∨z)∨y. Wegen der Kommutativitatund Assoziativitat von ∨ folgt (x ∨ z) ∨ y ≡ y ∨ (z ∨ x) ≡ (y ∨ z) ∨ x und damitdie Behauptung.

Losung 3.24 (zu Aufgabe 3.8)

Wegen der doppelten Verneinung x ≡ ¬(¬x) gilt x ∨ y ≡ ¬(¬x) ∨ y fur alleAussagen x, y. Aus x → y ≡ ¬x ∨ y folgt daher ¬x → y ≡ x ∨ y, also dieDarstellung von ∨ durch ¬ und →.

Aus der De Morganschen Regel folgt x ∧ y ≡ ¬(¬x ∨ ¬y). Wegen des erstenTeils dieser Aufgabe kann man aber die rechte Seite mit ¬ und → ausdrucken:¬(¬x ∨ ¬y) ≡ ¬(x → ¬y), wobei wiederum die doppelte Verneinung verwendetwurde.

Losung 3.25 (zu Aufgabe 3.9) a) Dies folgt unmittelbar aus der Definition we-gen der Idempotenz von ∧.

b) Wegen A ∧ B ≡ ¬(¬A) ∧ ¬(¬B) ≡ (¬A) ↓ (¬B) aufgrund der doppeltenVerneinung und der Definition von ↓, folgt die Behauptung durch Anwendungvon a).

Wegen A ∨ B ≡ ¬(¬A ∧ ¬B) ≡ ¬((A ↓ A) ∧ (B ↓ B)) ≡ ¬((A ↓ A) ↓ (A ↓ A) ↓(B ↓ B) ↓ (B ↓ B)) nach a) und b) ist A∨B dann nach a) gleichwertig zu ((A ↓A) ↓ (A ↓ A) ↓ (B ↓ B) ↓ (B ↓ B)) ↓ ((A ↓ A) ↓ (A ↓ A) ↓ (B ↓ B) ↓ (B ↓ B)).

Wegen A → B ≡ ¬(A ∧ ¬B) ≡ ¬(A ∧ (B ↓ B)) ≡ ¬((A ↓ A) ↓ ((B ↓ B) ↓ (B ↓B))) ist A→ B schließlich gleichwertig zu

((A ↓ A) ↓ ((B ↓ B) ↓ (B ↓ B))) ↓ ((A ↓ A) ↓ ((B ↓ B) ↓ (B ↓ B))).

Losung 3.26 (zu Aufgabe 3.10) Die Beweise verlaufen ganz analog wie die inder Losung von Aufgabe 3.9.


3 Aufgaben 92

Losung 3.27 (zu Aufgabe 3.11) Jede derartige Formel ist ein Wort uber demendlichen Alphabet X = {0,1, A,¬,∨, (, )}, also ein Element der freien Halb-gruppe X+. Diese ist aber abzahlbar unendlich. Also gibt es hochstens abzahl-bar unendlich viele derartige Formeln. Dies andert sich auch nicht, wenn manstatt A endlich viele Variable A1, . . . , An in X aufnimmt. Andererseits existie-ren bereits mit einer Variablen A unendlich viele derartige Formeln: A, (A ∨A),((A ∨ A) ∨ A), . . .

Die vier Formeln in der Menge A = {0,1, A,¬A} sind offensichtlich untereinan-der paarweise nicht gleichwertig. Wendet man den Junktor ¬ auf eine von ihnenan, so entsteht wieder eine Formel, die zu genau einer Formel aus A gleichwertigist. Verknupft man zwei von ihnen mit dem Junktor ∨ so entsteht ebenfalls eineFormel, die zu genau einer Formel aus A gleichwertig ist. Die Behauptung folgtjetzt durch Induktion uber den Aufbau der Formeln aus F{¬,∨}({A}) mit Hil-fe der Transitivitat der Gleichwertigkeit. (Die gleichen Uberlegungen kann mannaturlich mit jedem der Junktoren ∧, → und ↔ anstelle von ∨ machen.)

Bei endlich vielen Variablen A1, . . . , An besteht die Menge A aus allen Disjunk-tionen Li1 ∨ . . .∨Lik wobei die Liν Literale zu paarweise verschiedenen Aiν sind.Also bleibt A endlich. Bei abzahlbar unendlich vielen Variablen bleibt die Mengealler Formeln abzahlbar, aber nun wird auch A abzahlbar unendlich.

Losung 3.28 (zu Aufgabe 3.12) Ist n = p1 . . . pk mit paarweise verschiedenenPrimzahlen pi zusammengesetzt, dann ist fur jeden Teiler d von n der eindeutigbestimmte Co-Teiler d′ mit n = d ·d′ das Komplement, denn es gilt ggT (d, d′) = 1und kgV (d, d′) = d · d′ = n.

Losung 3.29 (zu Aufgabe 3.13) Wegen {∅} ∪ {{∅}} = {∅, {∅}} existiert wederdie Vereinigungsmenge von {∅} und {{∅}} in diesem Universum noch die Paar-menge von ∅ und {∅}. Die betreffenden beiden Axiome sind also nicht erfullt.Naturlich gilt aber das Nullmengenaxiom und das Extensionalitatsaxiom, denndiese drei Mengen sind paarweise verschieden: Die beiden Einermengen sind nichtleer und {{∅}} ist wegen {∅} 6= ∅ nicht in {∅} enthalten. Die einzigen echteTeilmengen, die man aus diesen Mengen aussondern kann, sind die leere Mengeund {∅}, die ja beide zum Universum gehoren. Daher gilt auch das Aussonde-rungsaxiom. Wegen

⋃ ∅ = ∅, ⋃ {∅} = {∅} und⋃ {{∅}} = {{∅}} ist das große

Vereinigungsmengenaxiom jedoch erfullt.

Losung 3.30 (zu Aufgabe 3.14) Offensichtlich gelten das Nullmengenaxiom unddas Extensionalitatsaxiom. Die einzige echte Teilmenge, die ausgesondert werdenkann, ist die leere Menge aus {∅}. Also gilt auch das Aussonderungsaxiom. Bei


3 Aufgaben 93

Vereinigungen konnen nur ∅ und {∅} entstehen, also gelten auch beide Vereini-gungsmengenaxiome. Da {∅, {∅}} aber nicht zum Universum gehort, gilt wederdas Paarmengenaxiom noch das Potenzmengenaxiom.

Losung 3.31 (zu Aufgabe 3.15) Fur n = 0 gilt X0 = ∅ 6= Xk+1 = {Xk}. Geltealso Xn 6= Xn+1+k fur alle k und ein n ∈ N0. Aus Xn+1 = Xn+1+1+k wurde aber{Xn} = {Xn+1+k} und damit wegen der Gleichheit dieser Einermengen schonXn = Xn+1+k folgen. Also muß auch Xn+1 6= Xn+1+1+k gelten.

Daher gelten das Nullmengenaxiom und das Extensionalitatsaxiom. Mit X und Yist aber auch X∪Y und jede Teilmenge von X eine Menge des Universums. Dahergelten auch das kleine Vereinigungsmengenaxiom und das Aussonderungsaxiom.Die Menge X := {X2, X4, . . .} liegt ebenfalls in dem Universum, da uberhauptkeine Xn mit ungeradem Index in X vorkommen. Aber

⋃X = {X1, X3, . . .}

besteht aus unendlich vielen Xn mit ungeradem Index, ist also keine Menge desUniversums.

Losung 3.32 (zu Aufgabe 3.16) Fur jedes x ∈ A gilt (x, x) ∈ ιA = F ◦ G.Also existiert dazu ein y ∈ B mit (x, y) ∈ F und (y, x) ∈ G. Dies zeigt, daß Flinkstotal und G rechtstotal ist. Dual folgt aus der Gleichung G ◦ F = ιB, daß Glinkstotal und F rechtstotal ist. Sind (x, y), (x′, y) ∈ F , so gibt es, da G linkstotalist, ein z ∈ A mit (y, z) ∈ G. Es folgt (x, z) ∈ F ◦G = ιA, also x = z, und ebensox′ = z. Also ist F linkseindeutig. Dual folgt aus G◦F = ιB, daß G linkseindeutigist. Sind (x, y), (x, y′) ∈ F , so gibt es, wiederum da G linkstotal ist, z, z′ ∈ Amit (y, z), (y′, z′) ∈ G und daher (x, z), (x, z′) ∈ F ◦ G = ιA, was x = z = z′

impliziert. Also hat man (y, x), (y′, x) ∈ G, und aus der Linkseindeutigkeit vonG folgt y = y′. Daher ist F auch rechtseindeutig. Dual folgt schließlich, daß auchG rechtseindeutig ist. Daher sind sowohl F als auch G bijektive AbbildungenF : A→ B und G : B → A.

Fur (x, y) ∈ F gibt es genau ein z ∈ A mit (y, z) ∈ G und wegen (x, z) ∈ F ◦G =ιA folgt z = x. Dies zeigt F−1 ⊆ G, und dual folgt G−1 ⊆ F . Hieraus folgtschließlich G = (G−1)−1 ⊆ F−1 und daher F−1 = G.


Index

n-Fakultat, 55n-Tupel, 29n-te Potenz, 29Aquivalenz, 5Aquivalenzrelation, 34

Abbildung, 44bijektive, 44eineindeutige, 44identische, 44injektive, 44konstante, 60partielle, 44surjektive, 44

Absorptionsgesetze, 23Addition

modulo 2, 79Adjunktion einer Eins, 60Aleph Null, 48Allmenge, 19Allrelation, 33Alphabet, 55Assoziativitat, 23Atom, 4, 12Aussage, 3Aussageform, 11Aussagenvariable, 4Aussonderungsaxiom, 18Auswahlaxiom, 38, 44Automorphismengruppe, 72Automorphismus, 71

Bahn, 74Bijektion, 44Bild, 44Boolesche Algebra, 23Boolescher Ring, 77, 78Buchstabe, 55

Cayley-Tafel, 54, 61–64, 70, 78, 84

De Morgansche Gesetze, 9Definitionsbereich, 30Diagonalverfahren

Zweites, 51Erstes, 49

Differenz, 62mengentheoretische, 20symmetrische, 20

Disjunktion, 5Distributivgesetze, 77Distributivitat, 23Division mit Rest, 27doppelte Negation, 8Durchschnitt, 20

Einbettung, 44Einermenge, 15Einheitsintervall, 51Einschrankung, 30Einselement, 59Element

absorbierendes, 59großtes, 39invertierbares, 61kurzbares, 60kleinstes, 39linksabsorbierendes, 59linkskurzbares, 60linksneutrales, 59maximales, 39minimales, 39neutrales, 59Ordnung von einem, 67rechtsabsorbierendes, 59rechtskurzbares, 60rechtsneutrales, 59

Endomorphismus, 71Epimorphismus, 71Erzeugendensystem, 67Euklidischer Algorithmus, 83

94

INDEX 95

Euklidisches Wahrheitskriterium, 11ex falso quodlibet, 8Extensionalitatsaxiom, 15

Faktorgruppe, 70Faktorgruppoid, 69Faktormenge, 37Familie, 48Fixpunkt, 74Folge

unendliche, 48Formel

aquivalente, 6allgemeingultige, 6aussagenlogische, 4erfullbare, 6gleichwertige, 6pradikatenlogische, 12von Peirce, 11widerspruchliche, 6

Funktion, 45

Galois-Feld, 84Galois-Korper, 84geordnetes Paar, 27gleichmachtig, 48Grad, 82Grenze

obere, 40untere, 40

Gruppe, 62abelsche, 62symmetrische, 63zyklische, 64, 67

Gruppoid, 54

Halbgruppe, 54freie, 55monogene, 67zyklische, 67

Halbverband, 54Hasse-Diagramm, 35Homomorphismus, 71

Idempotenz, 23Identitat, 33Implikation, 5Index, 68Indexmenge, 48Infimum, 40Injektion, 44Inklusion, 25Integritatsbereich, 78Inverses, 61Inversion, 76Isomorphismus, 71

Junktor, 5

Korper, 78Korpererweiterung, 83kurzbar, 60Kardinalitat, 19Kardinalzahl, 19, 49, 54

transfinite, 49, 50kartesisches Produkt, 27Kette, 34Kettenschluß, 11Klasse, 19Kleinsche Vierergruppe, 63Koeffizient, 82Kommutativitat, 23Komplement, 20Komplementgesetze, 23Kongruenzrelation, 69Konjunktion, 5Konkatenation, 55Kontinuumshypothese, 51Kontradiktion, 6Kontraposition, 11Korrespondenz, 29, 44

inverse, 29linkstotale, 30rechtseindeutige, 30rechtstotale, 30

Kreuzprodukt, 27

Lateinische Quadrate, 62


INDEX 96

Leitkoeffizient, 82Linkseinselement, 59Linksinverses, 61linkskurzbar, 60Linkskongruenz, 69Linksnebenklassen, 68linkstotal, 30Linkstranslation, 61Liste, 29Literal, 10

Machtigkeit, 19, 48Menge

uberabzahlbare, 48abzahlbar unendliche, 48abzahlbare, 48beschrankte, 39Dedekind-endliche, 52endliche, 19leere, 16linear geordnete, 34nach oben beschrankte, 39nach unten beschrankte, 39partiell geordnete, 34Russell-endliche, 52Russellsche, 17Tarski-endliche, 52total geordnete, 34unendliche, 19wohlgeordnet, 39

Mengendisjunkte, 20paarweise disjunkte, 20

Mengenbildungsaxiom, 18Mengenfamilie, 48Mengensystem, 18Minimalbedingung, 39Modul, 62Monoid, 59Monomorphismus, 71Multiplikation

modulo 2, 79

Nachfolgerfunktion, 49

Nachfolgermenge, 16naturliche Injektion, 44Negation, 5

doppelte, 8Normalform

disjunktive, 10konjunktive, 10

Normalteiler, 70Nullelement, 60Nullmengenaxiom, 15Nullpolynom, 82Nullring, 78Nullteiler, 78nullteilerfrei, 78

obere Grenze, 40obere Schranke, 39Oberkorper, 83Obermenge, 25Operation

algebraische, 53arithmetische, 53binare, 53einstellige, 53nullstellige, 53

Orbit, 74Ordnung

eines Gruppoids, 54lexikographische, 36partielle, 34totale, 34

Ordnungsrelation, 34

Paargeordnetes, 27

Paarmengenaxiom, 15Partition, 36Permutation, 55

gerade, 76ungerade, 76

Permutationsgruppe, 73transitive, 74

Platonisches Falschheitskriterium, 11


INDEX 97

Polynom, 82Potenzmenge, 26, 60, 78Potenzmengenaxiom, 26Pramissenbelastung, 11Pramissenvertauschung, 11Praordnung, 34Primkorper, 84Produkt

direktes, 27kartesisches, 27subdirektes, 44

Produkt von Polynomen, 82Projektion, 44

kanonische, 47

quadratischer Zahlkorper, 85Quasigruppe, 62Quasiordnung, 34

rechtseindeutig, 30Rechtseinselement, 59Rechtsinverses, 61rechtskurzbar, 60Rechtskongruenz, 69Rechtsnebenklassen, 68rechtstotal, 30Rechtstranslation, 61Relation, 29

n-stellige, 33antisymmetrische, 34asymmetrische, 34binare, 33identische, 33irreflexive, 34konnexe, 34leere, 33lineare, 34linkseindeutige, 29linksinvariante, 69linkskompatible, 69linkstotale, 29rechtseindeutige, 29rechtskompatible, 69

rechtstotale, 29reflexive, 34symmetrische, 34transitive, 34

Reprasentant, 37Reprasentantensystem, 37Reprasentantenunabhangigkeit, 47Restklassen modulo n, 27Restklassengruppe

prime, 84Restklassengruppen modulo n, 70Restklassenring, 80

modulo n, 80Ring, 77

assoziativer, 77Boolescher, 77idempotenter, 77kommutativer, 77mit Einselement, 77

Ringhomomorphismus, 80Russelsche Antinomie, 17

Satz von Cantor, 50Satz von Lagrange, 68Satz von Wedderburn, 79Schiefkorper, 78, 79Schranke

obere, 39untere, 39

Selbstimplikation, 8Signatur

logische, 10Signum, 76Sprache

formale, 55String, 55Subjunktion, 5Summe von Polynomen, 82Supremum, 40Surjektion, 44Symbol, 55

Tautologie, 6


INDEX 98

Teilkorper, 83Teilmenge, 25

echte, 25Term, 5tertium non datur, 8Tragermenge, 54Transformation, 53Transformationshalbgruppe, 55Transformationsmonoid, 60Transitivitatsgebiet, 74Translation, 61translation, 68Transposition, 75

Umkehrabbildung, 45Unbestimmte, 82Unendlichkeitsaxiom, 16Universum, 11Unmenge, 19untere Grenze, 40untere Schranke, 39Untergruppe, 65

triviale, 66Untergruppoid, 65Unterhalbgruppe, 65

erzeugte, 67Unterkorper, 83Untermenge, 25Urbild, 44Urelement, 17Urmenge, 17

Variable, 11arithmetische, 5aussagenlogische, 4frei vorkommende, 11gebundene, 12

Verband, 23, 40, 54distributiver, 23

Vereinigung, 20Vereinigungsmengenaxiom

großes, 26kleines, 16

Vergleichsoperator, 5Verkettung, 32Verknupfung, 53Vorzeichenregeln, 77

WahrheitswertBoolescher, 4

Wahrheitswertetafel, 6Wertebereich, 30Widerspruch, 6Widerspruchsbeweis, 8Wohldefiniertheit, 47Wohlordnung, 39, 40, 43, 50Wohlordnungssatz, 43Wort, 55

leeres, 60

Zahlenganze, 38ganze Gaußsche, 85naturliche, 16rationale, 38, 43reelle, 43, 50

Zeichen, 55Zerlegung, 36Zornsches Lemma, 43, 44Zweiermenge, 15zyklische Vertauschung, 75Zyklus, 75


Documents

Grundlagen der Diskreten Mathematik und Algebra 1hebisch/skripte/diskmath/diskmath.pdf · Grundlagen der Diskreten Mathematik und Algebra 1 Prof. Udo Hebisch WS 2010/11 Dieses Skript