<<

. 4
( 60 .)



>>

ist
Z∼ := {[a] : a ∈ A}
eine Zerlegung von A.

Beweis. Wir mussen die Eigenschaften a)-c) nachprufen. Zunachst ist wegen
¨ ¨ ¨
¨
der Re¬‚exivitat der Aquivalenzrelation a ∈ [a] fur alle a ∈ A. Demzufolge sind
¨ ¨
¨
die Aquivalenzklassen alle nicht leer, was b) ist, und weiter folgt sofort, dass die
¨
Vereinigung aller Aquivalenzklassen gleich A ist, was a) beweist. Es verbleibt der
Beweis von c):
Es sei [a] © [b] = …. Dann exisiert ein Element c in diesem Durchschnitt. Per
De¬nition gelten dann c ∼ a und c ∼ b. Wegen der Symmetrie von ∼ folgt auch
a ∼ c. Zusammen mit c ∼ b und der Transitivitat impliziert das also a ∼ b. Wir
¨
haben also gezeigt:
[a] © [b] = … =’ a ∼ b.
¨
Wir mussen nun noch zeigen, dass zwei ¨quivalente Elemente dieselbe Aquiva-
a
¨
lenzklasse haben. Sie x ein beliebiges Element ∈ [a] , d.h. x ∼ a. Zusammen


16
mit a ∼ b und wieder der Transitivitat folgt x ∼ b, d.h. x ∈ [b] . Damit ist ge-
¨
zeigt, dass [a] ‚ [b] . Auf die genau gleiche Art erhalten wir auch [b] ‚ [a] und
demzufolge [a] = [b] . Wir haben also gezeigt:

a ∼ b =’ [a] = [b] .

Zusammen mit der vorherigen Implikation ergibt sich

[a] © [b] = … =’ [a] = [b] .

Dies ist genau die geforderte Eigenschaft c) fur eine Zerlegung.
¨
Zusammenfassend ergibt sich aus den beiden obigen Lemmata:

¨
Satz 1.3 Sei A eine nichtleere Menge. Aquivalenzrelationen auf A und Zerle-
¨
gungen von A entsprechen sich: Jeder Aquivalenzrelation ∼ wird mit Z∼ eine
¨
Zerlegung zugeordnet und jeder Zerlegung Z wird mit ∼Z eine Aquivalenzrelation
zugeordnet. Diese Zuordnung ist eineindeutig: Die zu ∼Z geh¨rende Zerlegung
o
¨
ist wieder Z und die zu Z∼ geh¨rende Aquivalenzrelation ist wieder ∼ .
o

Beweis. Es bleibt nur noch zu zeigen, dass ausgehend von einer Zerlegung
¨
Z die zu ∼Z geh¨rende Zerlegung wieder Z ist, und ausgehend von einer Aqui-
o
¨
valenzrelation ∼ die zu Z∼ geh¨rende Aquivalenzrelation wieder ∼ ist. Das ist
o
ziemlich o¬ensichtlich, und der formale Beweis sei dem Leser uberlassen.
¨
¨
Ein Element einer Aquivalenzklasse nennt man einen Repr¨sentanten die-
a
¨
ser Aquivalenzklasse. a ∈ A ist nach der obigen Diskussion genau dann ein
¨
Reprasentant der Aquivalenzklasse C wenn [a] = C gilt.
¨

¨
Beispiel 1.7 Wir betrachten die folgende Aquivalenzrelation auf Z : Wir de¬-
¨ ¨
nieren a ∼ b, wenn ein k ∈ Z existiert mit b = a + 6k. (Ubungsaufgabe: Uberzeu-
¨ ¨
gen Sie sich davon, dass das eine Aquivalenzrelation ist). Die Aquivalenzklassen
sind: {0, ±6, ±12, . . .} , {. . . , ’5, 1, 7, 13, . . .} , {. . . , ’4, 2, 8, 14, . . .} etc. Insge-
¨ ¨
samt gibt es o¬enbar 6 verschiedene Aquivalenzklassen. Jede Aquivalenzklasse
enth¨lt genau eine Zahl aus der Menge {0, 1, 2, 3, 4, 5} . Wir k¨nnen daher die
a o
¨ ¨
Menge der Aquivalenzklassen, d.h. die zur Aquivalenzrelation geh¨rende Zerle- o
gung von Z auch einfach mit der Menge {0, 1, 2, 3, 4, 5} identi¬zieren. Die obige
Zerlegung bezeichnet man auch mit Z6 . Z6 enth¨lt 6 Elemente, n¨mlich die obi-
a a
¨
gen Aquivalenzklassen. Wie schon erw¨hnt, k¨nnen wir Z6 mit {0, 1, 2, 3, 4, 5}
a o
identi¬zieren, was aber etwas irrefuhrend ist.
¨
6 spielt in der obigen Diskussion keine besondere Rolle. Man kann statt dessen
auch jede beliebige naturlich Zahl n ≥ 1 nehmen. Die entsprechende Zerlegung
¨
bezeichnet man dann auch als Zn .

¨ ¨
Der Ubergang von einer Menge A und einer darauf de¬nierten Aquivalenzrela-
¨
tion ∼ zur Menge der Aquivalenzklassen ist in der Mathematik ausserordentlich

17
wichtig und wird Ihnen wieder und wieder begegnen. Anschaulich sollte man
¨
sich vorstellen, dass jeweils aquivalente Elemente, die ja dann eine Aquivalenz-
¨
klasse bilden, zu einem “neuen Punkt” zusammengefasst werden. Man “kontra-
¨
hiert” gewissermassen die Aquivalenzklassen zu neuen Elementen. Die Begri¬e
in Anfuhrungszeichen haben jedoch keine mathematische Bedeutung, sondern
¨
dienen (ho¬entlich) nur der Veranschaulichung.
Statt Z∼ schreibt man meist A/ ∼ . Das werden wir auch in Zukunft tun.
Hier noch ein anderes

Beispiel 1.8 G bezeichne die Menge aller Geraden im Raum. Fur g1 , g2 ∈ G
¨
de¬nieren wir g1 ∼ g2 , wenn g1 und g2 parallel sind. G/ ∼ ist die sogenannte
projektive Ebene, die in der Geometrie ausserordentlich wichtig ist.

1.4 Abz¨hlbare Mengen
a
Von Cantor wurde eine Methode entwickelt, mit der man auch unendliche Mengen
“z¨hlen” kann. Fur endliche Mengen A und B ist o¬ensichtlich, dass sie gleich
a ¨
viele Elemente enthalten, wenn es eine bijektive Abbildung von A nach B gibt.
Wir verallgemeinern dies nun wie folgt:

De¬nition 1.7 A und B seien zwei Mengen. Sie heissen gleich m¨chtig, wenn
a
es eine bijektive Abbildung f : A ’ B gibt. B heisst mindestens so m¨chtig
a
wie A, wenn es eine injektive Abbildung f : A ’ B gibt.

De¬nition 1.8 Eine Menge, die gleich m¨chtig wie N ist, heisst abz¨hlbar un-
a a
endlich.

Ist A abzahlbar unendlich, so liefert uns die bijektive Abbildung f : N ’ A
¨
eine Abz¨hlung der Elemente von A : A = {a1 , a2 , a3 , . . .} : Wir setzen einfach
a
ai := f (i). Da f bijektiv ist, sind die Elemente ai alle verschieden, und es sind
auch alle Elemente von A.
Erstaunlich an unendlichen Mengen ist, dass sie echte Teilmengen enthalten,
die gleich machtig wie sie selbst sind. So ist z.B. N naturlich eine echte Teilmenge
¨ ¨
von N0 , aber N0 i ’ i + 1 ∈ N de¬niert eine Bijektion.

Satz 1.4 A und B seien zwei Mengen. Falls injektive Abbildungen f : A ’ B
und g : B ’ A existieren, so existiert auch eine bijektive Abbildung von A nach
B.

Obwohl die Aussage des obigen Satzes intuitiv einleuchtet ” wenn A min-
destens so m¨chtig wie B und B mindestens so m¨chtig wie A ist, dann sind A
a a
und B gleich m¨chtig ” ist der Beweis nicht ganz einfach, und wir lassen ihn
a
hier weg. Beweisen wollen wir hingegen die folgende Aussage uber Produkte von
¨
abz¨hlbar unendlichen Mengen.
a

18
Satz 1.5 A und B seien zwei abz¨hlbar unendliche Mengen. Dann ist auch A—B
a
eine abz¨hlbar unendliche Menge.
a

Beweis. Wir betrachten zun¨chst Abz¨hlungen von A und B, also A =
a a
{a1 , a2 , a3 , . . .} , B = {b1 , b2 , b3 , . . .} . Die Produktmenge hat dann die Elemente
(ai , bj ) , i, j ∈ N. Wir k¨nnen die Elemente dieser Menge von Paaren wie folgt
o
abz¨hlen: (a1 , b1 ) , (a1 , b2 ) , (a2 , b1 ) , (a1 , b3 ) , (a2 , b2 ) , (a3 , b1 ) , (a1 , b4 ) , . . . . Sche-
a
matisch sieht das dann wie folgt aus:

(a1 , b1 ) ’ (a1 , b2 ) (a1 , b3 ) (a1 , b4 ) . . .

(a2 , b1 ) (a2 , b2 ) (a2 , b3 ) (a2 , b4 ) . . .

(a3 , b1 ) (a3 , b2 ) (a3 , b3 ) (a3 , b4 ) . . .

(a4 , b1 ) (a4 , b2 ) (a4 , b3 ) (a4 , b4 ) . . .
. . . . ...
. . . .
. . . .
Wir de¬nieren also eine bijektive Abbildung f : N ’ A — B durch f (1) =
(a1 , b1 ) , f (2) = (a1 , b2 ) , f (3) = (a2 , b1 ) usw. Es ist klar, dass das eine bijektive
Abbildung de¬niert, denn jedes Element von A — B kommt in der Au¬‚istung
genau einmal vor.
Der obige Satz liefert die erstaunliche Tatsache, dass fur zwei abz¨hlbar un- a
¨
endliche Mengen A und B eine Bijektion von A nach A — B existiert. Ist n¨mlich a
g : N ’ A eine bijektive Abbildung, so ist mit dem oben konstruierten f, die
Abbildung f —¦ g ’1 eine bijektive Abbildung A ’ A — B. Man k¨nnte vielleicht o
auf die Idee kommen, dass alle unendlichen Mengen gleich m¨chtig sind. Dem ist
a
aber nicht so, wie der folgende Satz zeigt.

Satz 1.6 Fur jede Menge A ist P (A) nicht gleich m¨chtig wie A.
a
¨

Beweis. Wir nehmen an, dass A und P (A) gleich m¨chtig sind und fuhren
a ¨
das zu einem Widerspruch. f sei also eine bijektive Abbildung A ’ P (A) . Fur
¨
jedes a ∈ A ist dann f (a) eine Teilmenge von A. Wir bilden die folgende Menge

B := {a ∈ A : a ∈ f (a)} .
/

Da B eine Teilmenge von A ist, und wir voraussetzen, dass f bijektiv, also ins-
besondere surjektiv ist, existiert ein b ∈ A mit B = f (b). Wir fragen uns nun: Ist
b ∈ B ? W¨re b ∈ B = f (b), so folgt aus der De¬nition von B, dass b ∈ B ist.
a /
Das ist also nicht m¨glich. W¨re aber b ∈ B, so folgt wieder aus der De¬nition
o a /
von B, dass b ∈ B gilt. Das ist also auch nicht m¨glich. Somit bleibt nur noch
o
die M¨glichkeit, dass es eine derartige Abbildung gar nicht gibt.
o
Aus dem obigen Satz folgt insbesondere, dass die Menge der Teilmengen von N
nicht abz¨hlbar unendlich ist. Man nennt eine derartige Menge uberabz¨hlbar.
a a
¨

19
Man kann beweisen, dass es eine bijektive Abbildung von P (N) ’ R gibt. R ist
also auch uberabzahlbar. Im Gegensatz dazu ist die Menge der rationalen Zahlen
¨ ¨
abzahlbar:
¨

Satz 1.7 Q ist abz¨hlbar unendlich.
a

Beweis. Wir betrachten zun¨chst Q+ := {x ∈ Q : x > 0} . Eine Zahl q ist
a
+
genau dann in Q , wenn es Zahlen m, n ∈ N gibt mit q = m/n. Durch Kurzen ¨
von gemeinsamen Faktoren in Z¨hler und Nenner k¨nnen wir erreichen, dass diese
a o
+
Darstellung eindeutig ist: Zu jeder Zahl q ∈ Q existiert genau ein Zahlenpaar
(m, n) ∈ N — N mit g.g.T. (m, n) = 1 und q = m/n. Dies de¬niert also eine
injektive Abbildung Q+ ’ N — N. Setzen wir das mit der bijektiven Abbildung
N — N ’ N zusammen, die es nach Satz 1.6 gibt, so erhalten wir eine injektive
Abbildung Q+ ’ N. Andererseits existiert eine injektive Abbildung N ’ Q+ :
Jede naturliche Zahl ist ja auch eine rationale Zahl. Zusammen mit Satz 1.4 folgt
¨
dann, dass N und Q+ gleich m¨chtig sind.
a
+
Dass Q und Q gleich m¨chtig sind, ist nun sehr einfach zu sehen: Es sei
a
q1 , q2 , q3 , . . . ein Abz¨hlung der Elemente von Q+ . Dann ist 0, q1 , ’q1 , q2 , ’q2 , . . .
a
eine Abz¨hlung der Elemente von Q.
a

1.5 Vollst¨ndige Induktion
a
Die Menge der naturlichen Zahlen N hat eine wichtige Eigenschaft: Sie ist un-
¨

<<

. 4
( 60 .)



>>