<<

. 6
( 63 .)



>>

eine “Multiplikation“ eingefuhrt wird. Die Anordnung der ganzen Zahlen spiegelt sich in
¨

[(m, n)]  [(k, l)] : ⇐’ m + l < n + k

wieder. Hierbei sei “ <“ bei den naturlichen Zahlen bekannt.
¨


Bemerkung 1.26
¨
Wenn man mit Aquivalenzklassen neue Objekte unter Verwendung von Reprasentanten ¨
fur die Klassen de¬niert, hat man sich zu vergewissern, daß die De¬nition vom Repra-
¨ ¨
sentanten fur die Klasse unabhangig ist. Dies ist z.B. oben bei der De¬nition der Addition,
¨ ¨
Multiplikation und Kleiner“Beziehung der Fall. Bei der Addition etwa bedeutet dies, nach-
zuweisen, daß [(m, n)]•[(k, l)] = [(m , n )]•[(k , l )] ist, falls [(m, n)] = [(m , n )] , [(k, l)] =
[(k , l )] gilt. Dies sieht man mit Hilfe der Identit¨ten m + n = m + n , k + l = k + l
a
2
sofort ein.

Die oben skizzierte axiomatische Einfuhrung der ganzen Zahlen wird meist in der Analysis
¨
vollst¨ndig abgehandelt. Der Weg von den ganzen Zahlen Z zu den rationalen Q und von
a Z
den rationalen Zahlen Q zu den reellen Zahlen IR kann ¨hnlich vollzogen werden.
a
Wie kommt man aber zum Fundament der Konstruktion, n¨mlich zu den naturlichen
a ¨
Zahlen IN .
Die naturlichen Zahlen hat der liebe Gott gemacht, alles andere ist Menschenwerk.
¨
Kronecker, L. (1823 - 1891)


Kardinalzahlen sind (nach B. Russel, 1872 “ 1970) Klassen von Mengen im Sinne der Relation
“Zwei Mengen X, Y heißen gleich, wenn es eine Bijektion φ : X ’’ Y gibt“. Mit Kardinalzah-
len, wir schreiben dafur “card“, kann man dann die Zahlen 0,1,2,. . . erkl¨ren: 0 = card(…) (…
a
¨
ist der Repr¨sentant fur die Klasse von Mengen M , fur die es eine Bijektion von … auf M
a ¨ ¨
gibt),1 = card({0}), 2 = card({0, 1}), . . . , n = card({0, . . . , n ’ 1}), . . . . Man hat folgende Be-
zeichnung: „µ0 = card(IN ), c = card(IR) .


Ein axiomatisches Fundament basiert auf den Peano-Axiomen (G. Peano (1858 “ 1932)):

Es gibt eine Menge IN , ein Element 1 ∈ IN und eine Abbildung
σ : IN ’’ IN (Nachfolgerabbildung) mit:
(P1) σ ist injektiv.
(P2) 1 ∈ σ(IN ).
/
(P3) Ist M eine Teilmenge von IN mit 1 ∈ M und (m ∈ M =’ σ(m) ∈ M) ,
dann gilt M = IN .

Im Axiom (P3) erkennt man das Prinzip der vollst¨ndigen Induktion wieder.
a
Baumeister: Lineare Algebra I / Stand: August 1996 18



“Seit Euklid tragen alle Mathematiker dasselbe Bild der Mathematik in sich: Sie ruht auf einfa-
chen Axiomen, deren Kombinationen gewissen logischen Regeln folgen und es erlauben, andere
Aussagen zu beweisen. Die Wahrheit breitet sich sozusagen durch Ansteckung aus; sie beginnt bei
Basisaxiomen, die als solche anerkannt sind, und reicht bis zu allem, was mit deren Hilfe bewiesen
werden kann, das heißt also, so glaubte man, bis zur Gesamtheit der Mathematik, die unter Aus-
schluß jeder ¨ußeren Kontingenz auf reiner logischer Notwendigkeit grundet. So ist die Mathematik
a ¨
weder dem Zufall noch der Geschichte unterworfen.
Es war Kurt G¨del vorbehalten, 1930 den Beweis zu fuhren, daß dieses Bild falsch ist. In ei-
o ¨
nem beruhmten Theorem (Unvollst¨ndigkeitssatz), das im Jahr darauf ver¨¬entlicht wurde, zeigt
a o
¨
G¨del, daß es in jedem beliebigem System von Axiomen und Regeln (sofern deren Anzahl endlich
o
ist) moglich ist, eine Ausage uber ganze Zahlen zu formulieren, die innerhalb des betre¬enden
¨ ¨
Systems weder bewiesen noch widerlegt werden kann.“
Aus: Ekeland, I., Zufall, Gluck und Chaos, Hanser-Verlag,1992
¨

K. G¨del (1906 “ 1978) wurde in Brunn geboren. 1930 bewies er den Unabh¨ngigkeitssatz “ ein
o a
¨
alternativer Beweis seines Unvollst¨ndigkeitssatzes wurde sp¨ter von G. Chaitin unter Verwendung
a a
von Begri¬en aus der Komplexit¨tstheorie erbracht “ und 1938 zeigte er, daß das Auswahlaxiom
a
durch die anderen ZF“Axiome nicht widerlegt werden kann. P. Cohen fugte 1963 hinzu, daß es
¨
durch die anderen Axiome auch nicht bewiesen werden kann. Diese Entdeckungen Godels markieren
¨
das Ende des “Determinismus“ in der Mathematik, ebenso wie W. Heisenbergs Unsch¨rferelation
a
(1927 formuliert; W. H. 1901 “ 1976) den Determinismus in der Physik beendete. G¨del starb in
o
Princeton an selbstverschuldetem Verhungern.


Uber die als “Kontinuumshypothese“ bezeichnete Aussage, daß es keine echt zwischen „µ0 und
¨
c liegende Kardinalzahl gibt, hat K. G¨del einen atemberaubenden Satz bewiesen, der ungef¨hr
o a
folgendes besagt (A bezeichne das starke Ausswahlaxiom, C die Kontinuumshypothese): Wenn die
Mathematik ohne die Annahme von A und C widerspruchsfrei ist, so bleibt sie es auch, wenn man
diese Annahme hinzunimmt. Es werden unserer Mathematik also durch die Annahme von A und
C keine neuen Fehler hinzugef ugt.
¨

Rufen wir uns noch die Teilbarkeit in den ganzen Zahlen in Erinnerung.


De¬nition 1.27
Seien a, b ∈ Z . Wir sagen a teilt b oder a ist ein Teiler von b, falls es k ∈ Z gibt
Z Z
mit a · k = b ; wir schreiben dann a|b .
2

Sei m ∈ IN . Wir verwenden m nun als Aquivalenzmodul, denn damit k¨nnen wir
¨ o
¨
folgende Aquivalenzrelation auf Z erkl¨ren:
Z a

a ∼ b : ⇐’ m|(b ’ a) : ⇐’ ∃l ∈ Z (b = a + lm) .
Z

Dies ergibt eine Zerlegung von Z in Aquivalenzklassen: Ist a ∈ Z , so entscheidet der
¨
Z Z
¨
Rest bei der Teilung von a durch m, welcher Aquivalenzklasse a zugeordnet wird. Da nur
¨
m verschiedene Reste auftreten konnen, liefert dies eine Zerlegung von Z in m Aquiva-
Z
¨
lenzklassen. Wir haben also

Z m := Z / ∼ = {[0], . . . , [m ’ 1]} .
Z Z
Baumeister: Lineare Algebra I / Stand: August 1996 19


Interessanterweise kann man in Z m sogar wieder addieren (Operation •) und multipli-
Z
zieren (Operation ):
[k] • [l] := [k + l] , [k] [l] := [k · l] , k, l ∈ Z .
Z

Beachte, daß hier wieder nachgepruft werden muß, daß
¨
[k] • [l] , [k] [l]
vom Repr¨sentanten k fur [k] und l fur [l] nicht abh¨ngen.
a a
¨ ¨
Die Rolle der Null wird von der Klasse [0] und die Rolle der Eins wird von der Klasse [1]
ubernommen. Man stellt aber fest, daß eine Eigenschaft, die bei Z keine Entsprechung
Z
¨
hat, hier eintritt: Die Multiplikation von Klassen, die von Null verschieden sind, k¨nnen
o
die Nullklasse ergeben; siehe folgende Additions“ und Multiplikationstafel fur m = 6 :
¨


• [0] [1] [2] [3] [4] [5] [0] [1] [2] [3] [4] [5]
[0] [0] [1] [2] [3] [4] [5] [0] [0] [0] [0] [0] [0] [0]
[1] [1] [2] [3] [4] [5] [0] [1] [0] [1] [2] [3] [4] [5]
[2] [2] [3] [4] [5] [0] [1] [2] [0] [2] [4] [0] [2] [4]
[3] [3] [4] [5] [0] [1] [2] [3] [0] [3] [0] [3] [0] [3]
[4] [4] [5] [0] [1] [2] [3] [4] [0] [4] [2] [0] [4] [2]
[5] [5] [0] [1] [2] [3] [4] [5] [0] [5] [4] [3] [2] [1]

Man beachte, daß in der obigen Multiplikationstafel auch “Quadratwurzeln“ zu ¬nden
sind:
[3] = [3] [3] , [4] = [4] [4] .
Die damit zusammenh¨ngenden Fragen sind Teil der Ringtheorie, die in der Algebra
a
behandelt wird.

¨
Das Rechnen in Kongruenzen ist nichts anderes als das Rechnen in Aquivalenklassen wie
oben angedeutet. Mit der Kongruenz
a ≡ b (mod m)
¨
drucken wir aus, daß a, b zur selben Aquivalenzklasse bezuglich des Moduls m gehoren.
¨ ¨ ¨
Als Illustration:

Beispiel 1.28
Betrachte das Kongruenzsystem
7x ≡ 1 (mod 4) , 2x ≡ 1 (mod 3) .
7x ≡ 1 (mod 4) ist gleichbedeutend mit x ≡ 3 (mod 4), d.h. x = 3 + 4z , z ∈ Z .
Z
Einsetzen in die Kongruenz 2x ≡ 1 (mod 3) ergibt die Kongruenz

2(3 + 4z) ≡ 1 (mod 3) oder 8z ≡ 1 (mod 3) ,
Baumeister: Lineare Algebra I / Stand: August 1996 20


und schließlich
z ≡ 2 (mod 3) oder z = 2 + 3l , l ∈ Z .
Z
Ruckubersetzung ergibt
¨¨
x ≡ 11 (mod 12) .
2

De¬nition 1.29
Eine Zahl p ∈ IN , p = 1, heißt Primzahl genau dann, wenn gilt:

m|p =’ m = 1 oder m = p .
2

Seit Euklid weiß man, daß es unendlich viele Primzahlen gibt.


De¬nition 1.30
Seien m, n ∈ IN 0, aber nicht beide 0.
d ∈ IN heißt großter gemeinsamer Teiler von m, n, abgekurzt ggT(m,n), genau
¨ ¨
dann wenn gilt:

• d teilt m und n ;

• teilt q ∈ IN sowohl n als auch m, so teilt q auch d.
2

Bekanntlich gibt es zu jedem m ∈ IN \{1} Primzahlen p1 , . . . , pl (nicht notwendig alle
verschieden) mit
m = p1 · · · pl
(Primfaktorzerlegung von m). Nun ist klar, daß zu je zwei Zahlen m, n ∈ IN 0 mit m+n = 0
stets ein gr¨ßter gemeinsamer Teiler
o

d = ggT (m, n)

existiert. Aus der De¬nition 1.30 liest man ab, daß fur zwei gr¨ßte gemeinsame Teiler
o
¨
d, d von m, n ofenbar d|d , d |d, also d = d gilt. Diesen eindeutig bestimmten gr¨ßten
o
gemeinsamen Teiler kann man durch Teilung mit Rest berechnen. Das resultierende Re-
chenschema ist der Euklidische Algorithmus.
Zur Formulierung sind die sogenannten Gaußklammern nutzlich. Fur eine reelle Zahl r
¨ ¨
seien de¬niert:
’’
| r’ := gr¨ßte ganze Zahl z mit z ¤ r , | r | := kleinste ganze Zahl z mit z ≥ r .
| o

Baumeister: Lineare Algebra I / Stand: August 1996 21


Euklidischer Algorithmus:

m, n ∈ IN 0 . O.E. m > n ≥ 0 .
EIN
SCHRITT 1 f0 := m, f1 := n .
SCHRITT 2 Ist f1 = 0 , gehe zu AUS .

SCHRITT 3 f := f0 ’ | f0 ’ 1 .
¯ |f
’f
1
¯

<<

. 6
( 63 .)



>>