<<

. 5
( 63 .)



>>

Nachdem nun die obige Aussage bewiesen ist, ist die Behauptung des Satzes schnell ge-
zeigt.
Annahme: Es gibt eine bijektive Abbildungen φ : A ’’ IN n , ψ : A ’’ IN m , n = m .
O.E. sei etwa n > m . Da ψ—¦φ’1 : IN n ’’ IN m bijektiv ist, haben wir einen Widerspruch
zur obigen Aussage.
Baumeister: Lineare Algebra I / Stand: August 1996 13


De¬nition 1.19
Sei X eine Menge.

(a) M heißt endlich, wenn es ein N ∈ IN und eine bijektive Abbildung
ξ : M ’’ {1, . . . , N} gibt. Da nach Satz 1.18 die Zahl N eindeutig bestimmt
ist, ist die Schreibweise #M := N wohlde¬niert.

(b) M heißt abz¨hlbar unendlich, wenn es eine bijektive Abbildung
a
ξ : M ’’ IN gibt. Wir schreiben dann #M = ∞ .

(c) M heißt abzahlbar, wenn M endlich oder abz¨hlbar unendlich ist.
a
¨
2

Die obige De¬nition sagt also, daß wir die Elemente einer (endlichen) Menge M gez¨hlt
a
haben, wenn wir eine Bijektion φ : M ’’ {1, . . . , N} gefunden haben; das Z¨hlergebnis
a
ist #M := N .
Man beachte, daß es Mengen gibt, die nicht abz¨hlbar sind. Ein wichtiges Beispiel ist
a
M := IR . Das Cantorsche Diagonalisierungsverfahren, das ublicherweise in der Analysis
¨
im Zusammenhang mit der Dezimalbruchentwicklung vorgestellt wird, belegt dies.


Satz 1.20

Sei X eine Menge mit #X = N . Dann gilt #P(X) = 2N .
Beweis:
Wir beweisen die Aussage

X Menge mit #X = n =’ #P(X) = 2n

durch vollst¨ndige Induktion nach n .
a
n=1: Hier ist X = {x} und daher P(X) = {…, {x}}, #P(X) = 2 .
(Wir h¨tten auch mit n = 0 beginnen k¨nnen. Hier ist X = … und daher P(X) =
a o
{…}, #P(X) = 1 = 20 .)
n+1: Es ist etwa X = {a1, . . . , an+1 } . Setze X := {a1, . . . , an } . Die Induktionsannahme
besagt #P(X ) = 2n .
Sei nun A eine Teilmenge von X . Ist an+1 ∈ A, dann ist A = {an+1 }∪A mit A ∈ P(X ) .
Ist an+1 ∈ A, dann ist A ∈ P(X ) . Dies zeigt #P(X) = 2n + 2n = 2n+1 .
/


De¬nition 1.21
Sei f : X ’’ Y eine Abbildung und sei A ‚ X. Dann heißt

x ’’ f(x) ∈ Y
f|A : A

die Einschrankung von f auf A.
2
¨
Baumeister: Lineare Algebra I / Stand: August 1996 14


1.4 Relationen
Das Gleichheitszeichen “ =“ verwenden wir in einer Menge unter der stillschweigenden
Annahme der folgenden Regeln:

x = x ; x = y =’ y = x ; x = y, y = z =’ x = z .

Dies nehmen wir zum Anlaß fur
¨
De¬nition 1.22
Sei X eine Menge. Eine Teilmenge R ‚ X — X heißt Aquivalenzrelation auf X,
¨
falls gilt:

(i) (x, x) ∈ R fur alle x ∈ X (Re¬‚exivitat)
¨ ¨
(ii) (x, y) ∈ R =’ (y, x) ∈ R (Symmetrie)

(iii) (x, y), (y, z) ∈ R =’ (x, z) ∈ R (Transitivitat)
¨

2
Liegt mit R auf X eine Aquivalenzrelation vor, so schreiben fur (x, y) ∈ R
¨ ¨
R
x ∼ y oder kurz x ∼ y .
¨
Die Bedeutung einer Aquivalenzrelation liegt darin, daß man damit die Menge X in
Klassen einteilen kann, eine Einteilung, die eventuell grober ist, als die Aufteilung in
¨
einelementige Mengen, und die bezuglich eines “Merkmales“ doch noch aussagekraftig
¨ ¨
ist. Die Klasseneinteilung geschieht durch
R
[x] := {y ∈ X|y ∼ x} , x ∈ X ,

und
X/ R := {[x]|x ∈ X} .
¨
Die Objekte [x] heißen Aquivalenzklassen, x heißt Repr¨sentant der Klasse [x] . Man
a
R
beachte, daß jedes y ∈ X mit y ∼ x als Repr¨sentant fur [x] Verwendung ¬nden kann.
a ¨
Das folgende Lemma zeigt, daß X durch “ ∼ “ in disjunkte Klassen zerlegt wird.


Lemma 1.23
¨
Sei X eine Menge und sei R eine Aquivalenzrelation auf X. Dann gilt:

(a) Fur jedes x ∈ X gibt es [y] ∈ X/ R mit x ∈ [y] .
¨
(b) Es ist x ∼ y genau dann, wenn [x] = [y] gilt.
¨
(c) Zwei Aquivalenzklassen besitzen genau dann nichtleeren Durchschnitt, wenn
sie gleich sind.
Beweis:
Baumeister: Lineare Algebra I / Stand: August 1996 15


Zu (a). Klar: x ∈ [x] fur alle x ∈ X wegen der Re¬‚exivit¨t von “∼“.
a
¨
Zu (b). Sei x ∼ y . Sei u ∈ [x]. Dann ist u ∼ x und aus der Symmetrie und der Transitivit¨t a
folgt u ∼ y, d.h. u ∈ [y]. Also ist [x] ‚ [y] gezeigt. Die Aussage [y] ‚ [x] folgt v¨llig analog.
o
Ist [x] = [y] dann ist x ∼ y, da wir x ∈ [y] = [x] haben.
Zu (c). Unter Beachtung der Transitivit¨t, der Symmetrie von “∼“ und (b) folgt
a

z ∈ [x] © [y] ⇐’ z ∼ x, z ∼ y ⇐’ x ∼ y ⇐’ [x] = [y]

was zu beweisen war.


De¬nition 1.24
Sei X eine Menge. Eine Teilmenge O ‚ X — X heißt Halbordnung von X, falls
gilt:

(i) F¨r alle x ∈ X gilt (x, x) ∈ O.
u

(ii) (x, y) ∈ O , (y, x) ∈ O =’ y = x .

(iii) (x, y), (y, z) ∈ O =’ (x, z) ∈ O .

Ist zusatzlich noch
¨

(iv) F¨r alle x, y ∈ X gilt (x, y) ∈ O oder (y, x) ∈ O
u

erfullt, dann heißt O eine Ordnung von X.
¨
2
O
Meist schreibt man bei Vorliegen einer Halbordnung O statt (x, y) ∈ O auch x ∼ y oder
kurz x ¤ y .
O¬enbar haben wir das Ungleichungszeichen “ ¤ “ zum Anlaß fur obige De¬nition 1.24
¨
genommen. Die ubliche “Kleiner“Gleich“Beziehung“ in Z und Q ist eine Ordnung.
Z
¨


Beispiel 1.25
Ist X eine Menge, dann ist in P(X) eine Halbordnung O de¬niert durch

(A, B) ∈ O : ⇐’ A ¤ B : ⇐’ A ‚ B .

2
Beachte, daß nur in trivialen F¨llen eine Ordnung vorliegt.
a


1.5 Zahlen
Die reellen Zahlen bezeichneten wir mit IR . Sie umfassen die rationalen Zahlen und wir
kommen von den rationalen Zahlen zu den reellen Zahlen, indem wir auch Dezimalzahlen
zulassen, die keine echten Bruche darstellen. In der Analysis wird diese Konstruktion
¨
genauer studiert. Jedenfalls stehen auch hier wieder die Rechenarten
Baumeister: Lineare Algebra I / Stand: August 1996 16


“Addition, Subtraktion, Multiplikation, Division“
wie in Q zur Verfugung. Im Kapitel uber Vektorr¨ume werden wir dies zum Anlaß nehmen,
a
¨ ¨
die Existenz solcher “Verknupfungen“ von Zahlen axiomatisch einzufuhren.
¨ ¨
Daruberhinaus haben wir sogar eine Anordnung in Q, ja sogar in IR, d.h. fur alle x, y ∈ IR
¨ ¨
gilt genau eine der folgenden Alternativen (siehe De¬nition 3.26):

x = y oder x < y oder x > y .

Damit ist dann der Betrag |x| einer Zahl x ∈ IR erkl¨rt:
a
±
x , falls x > 0

|x| := ’x , falls x < 0


0 , falls x = 0

Hierbei ist ’x das Negative von x.

Ausgehend von IR k¨nnen wir auch IRn de¬nieren. Zwischen IR 1 und IR besteht dann ein
o
zu vernachl¨ssigender formaler Unterschied.
a
Wir werden IR 2 als Modell zur Beschreibung der anschaulichen Ebene und IR3 als Modell
zur Beschreibung des anschaulichen Raumes kennenlernen.

Skizzieren wollen wir nun den Konstruktionsweg von den naturlichen Zahlen zu den ganzen
¨
¨
Zahlen. Wir sehen dabei die Nutzlichkeit des Begri¬s der Aquivalenzrelation.
¨
Auf IN — IN l¨ßt sich eine Aquivalenzrelation durch
¨
a

R := {((m, n), (k, l)) ∈ IN 2 — IN 2 |m + l = n + k}
¨
einfuhren. Man best¨tigt leicht, daß in der Tat eine Aquivalenzrelation vorliegt.
a
¨
Die Zuordnung eines Paares (m, n) zu einer Klasse [(k, l)] geschieht unter dem Gesichts-
punkt, daß die Di¬erenz m’n gleich der Di¬erenz k’l ist. Dies liefert den Zusammenhang
zur Menge der ganzen Zahlen Z , wenn wir sie schon als bekannt voraussetzen. Dazu
Z
de¬nieren wir
J : (IN — IN )/ R [(m, n)] ’’ m ’ n ∈ Z . Z
Dies ist eine bijektive Abbildung, wie man leicht bestatigt. Wir haben
¨

0 = J([(n, n)] , 1 = J([(n + 1, n)] , ’1 = J([(n, n + 1)]) (n ∈ IN beliebig) .

Daran erkennen wir den Weg, ausgehend von der Kenntnis der naturlichen Zahlen, die
¨
ganzen Zahlen zu konstruieren:

Man fuhrt Z als Menge der Aquivalenzklassen (IN — IN )/R ein.
¨
Z
¨

Vervollstandigt wird dieser Schritt durch die Beobachtung, daß durch
¨

[(m, n)] • [(k, l)] := [(m + k, n + l)]

eine “Addition“ und durch

[(k, l)] := [(m · k + n · l, m · l + n · k)]
[(m, n)]
Baumeister: Lineare Algebra I / Stand: August 1996 17


<<

. 5
( 63 .)



>>