<<

. 3
( 60 .)



>>

Satz 1.2 a) Ist f : A ’ B bijektiv, so gibt es eine Umkehrabbildung f ’1 , die
eindeutig de¬niert ist durch die Festsetzung

f (x) = y ⇐’ f ’1 (y) = x. (1.7)

b) f ’1 erfullt die beiden Gleichungen
¨

f —¦ f ’1 = idB , (1.8)
f ’1 —¦ f = idA .

c) Ist f : A ’ B eine Abbildung und existiert eine Abbildung g : B ’ A mit

f —¦ g = idB , (1.9)
g —¦ f = idA , (1.10)

so ist f bijektiv und g ist die Umkehrabbildung von f.

Beweis. a) hatten wir uns schon vor der Formulierung des Satzes uberlegt.
¨
(1.8) folgt sofort aus (1.7). Wir mussen uns nur den Teil c) noch uberlegen.
¨ ¨
Wir gehen also hier davon aus, dass f nur eine Abbildung ist (keine Vor-
aussetzungen an Injektivit¨t und Surjektivit¨t), fordern aber die Existenz einer
a a
Abbildung g mit den angegebenen Eigenschaften. Wir zeigen zun¨chst, dass f
a
dann surjektiv ist. Dazu betrachten wir ein beliebiges Element y ∈ B. Dies
k¨nnen wir mit g nach A abbilden. Wir setzen x := g(y). Nach (1.9) ist
o

f (x) = f (g(y)) = (f —¦ g) (y) = idB (y) = y.

Wir haben damit nachgewiesen, dass zu jedem y ∈ B ein x ∈ A existiert mit
f (x) = y. Damit ist die Surjektivit¨t bewiesen.
a
Wir kommen nun zur Injektivit¨t. Es seien x und x zwei Elemente von A
a
mit f (x) = f (x ). Nennen wir dieses Element y : y := f (x) = f (x ). Wir wenden
nun (1.10) an:

x = idA (x) = (g —¦ f ) (x) = g (f (x)) = g(y)
= g (f (x )) = (g —¦ f ) (x ) = idA (x ) = x .


12
Damit ist bewiesen, dass aus f (x) = f (x ) die Gleichung x = x folgt. Es ist damit
gezeigt, dass f injektiv ist. Zusammen mit der schon gezeigten Surjektivitat ist ¨
somit bewiesen, dass f bijektiv ist.
Wir mussen nun noch nachweisen, dass g tatsachlich die Umkehrabbildung
¨ ¨
ist. Dies ist aber nun einfach: Ist y = f (x), so ist g(y) = g(f (x)) = (g —¦ f ) (x) =
idA (x) = x. Das ist genau die geforderte Beziehung (1.7) fur die inverse Abbil-
¨
dung.

Bemerkung 1.2 Aus dem obigen Satz folgt sofort, dass die Umkehrabbildung
’1
f ’1 einer bijektiven Abbildung f wieder bijektiv ist und (f ’1 ) = f gilt.

¨
1.3 Relationen, Aquivalenzrelationen
Sind A, B zwei Mengen, so ist die sogenannte Produktmenge A — B die Menge
der geordneten Paare (a, b) von Elementen a ∈ A und b ∈ B. Fur Mengen ¨
A1 , A2 , . . . , An ist die Produktmenge A1 — A2 — . . . — An de¬niert als die Menge
der sogenannten geordneten n-Tupel (a1 , a2 , . . . , an ) von Elementen ai ∈ Ai , 1 ¤
i ¤ n. Es soll hier keine formal ganz pr¨zise De¬nition dieser Menge gegeben
a
werden ” dies wurde eine Axiomatisierung der Mengenlehre voraussetzen, die
¨
wir hier nicht einfuhren m¨chten. Das Wort “geordnet” bedeutet, dass auf die
o
¨
Reihenfolge geachtet wird: Sind a = b, so gilt (a, b) = (b, a) und analog fur die
¨
n-Tupel.
Sind A und B dieselben Mengen, so schreiben wir auch einfach A2 anstelle
von A — A, und analog An fur die Menge der n-Tupel.
¨
Eine Relation R auf einer Menge A ist formal einfach eine Teilmenge R ‚
A — A. Fur a, b ∈ A schreiben wir dann auch aRb anstelle von (a, b) ∈ R. Das ist
¨
im Moment etwas abstrakt. Wir machen gleich einige Beispiele dazu.

Beispiel 1.3 Sie kennen auf R die ubliche Ordnungsrelation a ¤ b. Wir k¨nnen
o
¨
diese Ordnungsrelation auch einfach als Teilmenge von R — R au¬assen. Die
Elemente dieser Teilmenge sind die Elemente (a, b), fur die a ¤ b gilt.
¨

Beispiel 1.4 Betrachten Sie die Menge G der Geraden im dreidimensionalen
Raum. Wir k¨nnen die Relation R der “Parallelit¨t” de¬nieren: Zwei Geraden
o a
g1 und g2 stehen in dieser Relation, wenn sie parallel sind. Formaler ausgedruckt:
¨
(g1 , g2 ) ∈ R ⇐’ g1 und g2 sind parallel.

De¬nition 1.4 R sei eine Relation auf A.
a) R heisst symmetrisch, wenn

(a, b) ∈ R ⇐’ (b, a) ∈ R

gilt.


13
b) R heisst transitiv, wenn

(a, b) ∈ R und (b, c) ∈ R =’ (a, c) ∈ R

gilt.
c) R heisst re¬‚exiv, wenn (a, a) ∈ R fur alle a ∈ A gilt.
¨

Beispiel 1.5 Die zweiteinfachste Relation auf A ist die “Gleichheit”: (a, b) ∈ R
gilt genau dann, wenn a = b ist. O¬ensichtlich ist diese Relation symmetrisch,
transitiv und re¬‚exiv. Noch trivialer ist R = A — A. In diesem Fall stehen zwei
beliebige Elemente von A in der Relation R.

Beispiel 1.6 Etwas weniger trivial ist das Beispiel 1.3 von oben. Die Ordnungs-
relation ¤ auf R ist transitiv, denn aus a ¤ b, b ¤ c folgt a ¤ c, und re¬‚exiv. Sie
ist aber nicht symmetrisch, denn es gilt zwar 1 ¤ 2, aber nicht 2 ¤ 1.

De¬nition 1.5 a) Eine re¬‚exive und transitive Relation R auf einer Menge A
heisst eine Ordnungsrelation auf A, wenn zus¨tzlich die folgende Eigenschaft
a
gilt:
(a, b) ∈ R und (b, a) ∈ R =’ a = b.
b) Eine Ordnungsrelation heisst Totalordnung, wenn je zwei beliebige Ele-
mente von A vergleichbar sind, d.h. wenn fur beliebige Elemente a, b ∈ A (a, b) ∈
¨
R oder (b, a) ∈ R ist.
c) Eine re¬‚exive, symmetrische und transitive Relation auf A heisst eine
¨
Aquivalenzrelation.

¨
Ublicherweise schreibt man Ordnungsrelationen als ¤ oder oder ¨hnlich.
a
¨
Man schreibt dann auch a ¤ b anstelle von (a, b) ∈¤ . Aquivalenzrelationen
schreibt man ublicherweise als ∼, also a ∼ b fur zwei Elemente, die in dieser
¨ ¨
Relation stehen.
Es gibt viele Beispiele von Ordnungsrelationen, die keine Totalordnungen sind.
Die Gleichheitsrelation ist naturlich immer auch eine Ordnungsrelation. Es ist
¨
jedoch keine Totalordnung, ausser wenn A nur ein Element enthalt. Hier noch
¨
2
ein weniger triviales Beispiel. Wir betrachten A = R , die Menge der reellen
Paare. Dann de¬nieren wir (a1 , a2 ) (b1 , b2 ) wenn a2 = b2 und a1 ¤ b1 gelten.
ist eine Ordnungsrelation aber keine Totalordnung, denn z.B. (1, 2) und (3, 4)
sind nicht vergleichbar.
Ein anderes Beispiel, das Sie schon kennen, tritt in folgender Situation auf.
Wir betrachten eine beliebige Menge M. P(M ) sei die Potenzmenge von M,
d.h. die Menge aller Teilmengen von M. Ein Element von P(M ) ist also nichts
anderes als eine Teilmenge von M. Auf P(M ) betrachten wir die ubliche Inklusi-
¨
onsrelation: Zwei Elemente B, C ∈ P(M ) (d.h. zwei Teilmengen von M ) stehen
in der Relation ‚, wenn B eine Teilmenge von C ist, also B ‚ C im ublichen ¨

14
Sinn. ‚ ist ebenfalls eine Ordnungsrelation, aber keine Totalordnung (falls M
mehr als ein Element enthalt).
¨
Soviel im Moment zu Ordnungsrelationen, die uns noch sehr oft begegnen
werden.
¨
Nun zu den Aquivalenzrelationen. Ein Beispiel ist wieder die Gleichheitsre-
¨
lation. Die Ordnungsrelation ¤ auf R ist jedoch keine Aquivalenzrelation, denn
sie ist nicht symmetrisch. Noch ein anderes Beispiel. Wir betrachten die Menge
aller Geraden in einer Ebene. Wir de¬nieren fur zwei Geraden g1 und g2 : g1 ∼ g2
¨
¨
wenn g1 und g2 parallel sind. Dies ist o¬ensichtlich eine Aquivalenzrelation.
¨
Aquivalenzrelationen stehen in engster Beziehung zu sogenannten Zerlegun-
gen. Eine Zerlegung einer Menge A ist eine Aufteilung der Menge in nicht leere
Teilmengen von A, die sich gegenseitig “nicht uberlappen”. Hier eine ganz for-
¨
male De¬nition:

De¬nition 1.6 A sei eine nicht leere Menge. Eine Zerlegung Z von A ist eine
Familie von Teilmengen Ci ‚ A mit
a) i Ci = A.
b) Ci = … fur alle i.
¨
c) Ci © Cj = … fur i = j.
¨

Zwei Mengen mit der Eigenschaft c) (“nicht uberlappend”, “haben leeren
¨
Schnitt”) heissen ubrigens disjunkt. Der Index i in der obigen De¬nition durch-
¨
l¨uft irgendeine “Indexmenge” I, die endlich oder unendlich sein kann. Ein tri-
a
viales Beispiel ist die “Zerlegung” in eine einzige Teilmenge, die dann naturlich
¨
A selbst sein muss. In diesem Fall gibt es nur ein C1 . Nach dem ublichen Sprach-
¨
verst¨ndnis w¨re das naturlich keine Zerlegung; die obigen Bedingungen sind
a a ¨
jedoch erfullt, auch c), denn da es gar keine zwei verschiedenen Indizes i, j gibt,
¨
ist das automatisch richtig. (“Alle vieraugigen, wiederkauenden Amerikaner be-
¨ ¨
sitzen einen roten Ferrari” ist eine mathematisch korrekte Aussage).
Die Formulierung der De¬nition mit indizierten Mengen ist eigentlich uber-
¨
¬‚ussig. Formal “schoner” ist die De¬nition von Z als Teilmenge der Potenzmenge
¨ ¨
P(A) mit den entsprechend formulierten Aussagen a)-c). Diese lauten dann

Z = A.
a)
b) C = … fur alle C ∈ Z.
¨
c) C © D = … fur C = D, C, D ∈ Z.
¨

Zur Erinnerung Z = {x ∈ A : ∃C ∈ Z mit x ∈ Z} . Das ist vielleicht im
Moment etwas abstrakt.
Hier ein Beispiel einer Zerlegung: Wir zerlegen N in die unendlich vielen
Teilmengen: {1} , {2, 3} ,{4, 5, 6}, {7, 8, 9, 10} , etc. Die Zerlegung ist dann

Z = {{1} , {2, 3} , {4, 5, 6}, {7, 8, 9, 10} , . . .} .

15
¨
Es stellt sich nun heraus, dass Aquivalenzrelationen eigentlich nichts anderes
als Zerlegungen sind. Zunachst ist es sehr einfach, einer Zerlegung Z von A
¨
¨
eine Aquivalenzrelation auf A zuzuordnen. Wir bezeichnen diese mit ∼Z : Fur ¨
Elemente a, b ∈ A de¬nieren wir a ∼Z b, wenn a und b in derselben Menge der
Zerlegung sind:
a ∼Z b ⇐’ ∃C ∈ Z mit a, b ∈ C.

¨
Lemma 1.1 Ist Z eine Zerlegung, so ist ∼Z eine Aquivalenzrelation.

Beweis. Zun¨chst die Re¬‚exivit¨t: Da Z eine Zerlegung ist, existiert zu
a a
jedem a ∈ A eine Menge C der Zerlegung mit a ∈ C. Demzufolge gilt a ∼Z a.
Die Symmetrie von ∼Z ist klar aus der De¬nition.
Nun zur Transitivit¨t. Seien a ∼Z b, b ∼Z c. So wie die Relation de¬niert ist,
a
existieren C ∈ Z mit a, b ∈ C und C ∈ Z mit b, c ∈ C . Das Element b liegt also
in C und C . Demzufolge ist C © C = …. Aus der Eigenschaft c) einer Zerlegung
folgt also C = C . Daraus folgt a ∼Z c.
¨
Wir gehen nun umgekehrt vor und konstruieren zu einer beliebigen Aquiva-
¨
lenzrelation ∼ auf A eine Zerlegung. Dies geht uber die sogenannten Aquiva-
¨
¨
lenzklassen. Ist a ∈ A, so de¬nieren wir die Aquivalenzklasse [a] ‚ A von a
¨
(bezuglich der Aquivalenzrelation ∼) durch
¨

[a] := {b ∈ A : b ∼ a} .
¨
Die Aquivalenzklassen sind also Teilmengen von A.

¨
Lemma 1.2 Sei A eine nichtleere Menge und ∼ eine Aquivalenzrelation. Dann

<<

. 3
( 60 .)



>>