<<

. 5
( 60 .)



>>

ter der naturlichen Ordnungsrelation ¤, wie man sagt, wohlgeordnet. Eine
¨
Ordnungsrelation ¤ auf einer Menge A heisst eine Wohlordnung, wenn jede
nichtleere Teilmenge B von A ein kleinstes Element hat, d.h. es existiert ein
Element b ∈ B mit c ≥ b fur alle c ∈ B. Dass N wohlgeordnet ist, ist o¬en-
¨
sichtlich: Ist B ‚ N nicht leer, so gibt es eine Element b ∈ B. Dann ist die
Menge {1, 2, . . . , b} eine endliche Menge und wir ¬nden unter diesen Elementen
sicher ein kleinstes Element, das in B liegt. Es sollte bemerkt werden, dass dieser
Beweis formal nicht ganz pr¨zise ist. Ein formal wirklich ganz genauer Beweis
a
wurde eine bessere Axiomatisierung der Mengenlehre erfordern, die wir hier nicht
¨
geben k¨nnen. Unter Verwendung dieser Wohlordnungseigenschaft kann jedoch
o
die folgende wichtige Eigenschaft bewiesen werden:

Satz 1.8 Sei A eine Teilmenge von N mit den folgenden Eigenschaften:
a) 1 ∈ A
b) Fur jedes a ∈ A ist auch a + 1 ∈ A
¨
Dann gilt A = N.

Beweis. Wir fuhren die Annahme, dass A = N ist zu einem Widerspruch.
¨
Aus A = N folgt n¨mlich, dass Ac nicht leer ist. Demzufolge hat Ac ein kleinstes
a
Element, nennen wir es b. Es gilt b = 1, denn 1 ist nach a) in A und demzufolge


20
nicht in Ac . Da b = 1 ist, ist b ’ 1 ∈ N. b ’ 1 kann jedoch nicht in Ac sein, da b
das kleinste Element von Ac war. Demzufolge ist b ’ 1 ∈ A. Nach der Eigenschaft
b) ist dann b = (b ’ 1) + 1 ∈ A im Widerspruch zu b ∈ Ac .
Der obige Satz fuhrt zu einem ausserst wichtigen Beweisverfahren, der voll-
¨ ¨
st¨ndigen Induktion.
a

Satz 1.9 Gegeben sei fur jede naturliche Zahl n ∈ N eine Aussage E(n), die
¨ ¨
entweder wahr oder falsch sein kann. Falls
a) E(1) gilt (Induktionsverankerung)
b) E(n) =’ E(n + 1) fur alle n ∈ N (Induktionsschluss)
¨
Dann gilt E(n) fur alle n ∈ N.
¨

Beweis. Sei A := {n ∈ N : E(n) gilt} . Nach a) folgt 1 ∈ A und nach b) folgt,
dass mit jeder Zahl n ∈ A auch n + 1 ∈ A ist. Nach dem vorangegangenen Satz
folgt, dass A = N ist. Demzufolge gilt E(n) fur alle n ∈ N.
¨
Wir geben ein Beispiel:

Satz 1.10 Fur jede naturliche Zahl n gilt
¨ ¨
n
n(n + 1)(2n + 1)
j2 = .
6
j=1


Beweis. Wir fuhren den Beweis mit vollst¨ndiger Induktion.
a
¨
Induktionsverankerung: Die Aussage gilt fur n = 1. Dies ist o¬ensichtlich.
¨
Induktionsschluss: Wir nehmen an, die Aussage gelte fur n (Induktionsvor-
¨
aussetzung). Wir zeigen nun, dass sie dann auch fur n + 1 gilt:
¨
n+1 n
2
j 2 + (n + 1)2
j=
j=1 j=1
n(n + 1)(2n + 1)
+ (n + 1)2 (nach Induktionsvoraussetzung)
=
6
n(2n + 1) (n + 2) (2n + 3)
= (n + 1) + n + 1 = (n + 1)
6 6
(n + 1) ((n + 1) + 1) (2 (n + 1) + 1)
= .
6

Dieser Beweis hat naturlich den Nachteil, dass man nicht sieht, wie die Formel
¨
zustande kommt.
Prinzip der rekursiven Konstruktion
Es kommt oft vor, dass man eine Funktion, eine Zahl oder eine Menge, die
noch von n ∈ N abh¨ngt, quasi per Induktion nach n, oder wie man sagt, rekursiv
a


21
konstruiert. Ein einfaches Beispiel ist die Fakultat n!, die rekursiv durch die
¨
beiden Vorschriften:

1! := 1
(n + 1)! := (n + 1) · n!

festgelegt wird. Es ist dann klar, dass n! fur jedes n auf diese Weise de¬niert ist.
¨
Man konstruiert also zun¨chst das erste Element und beschreibt dann, wie man
a
das (n + 1)-te aus dem n-ten gewinnt. Wir wollen das nicht genau durchforma-
lisieren; wir werden noch sehr viele Beispiele dazu kennen lernen. Hier noch ein
einfaches:
Nehmen wir an, Sie k¨nnen z¨hlen aber noch nicht rechnen (addieren und
o a
multiplizieren). Sie wissen also nur, wie man zu jeder Zahl n den Nachfolger dieser
Zahl gewinnt, den wir mit φ(n) bezeichnen. Nun de¬nieren wir die Addition: Wir
konstruieren fur m, n ∈ N die Zahl m + n rekursiv nach n :
¨

m + 1 := φ (m)
m + (n + 1) := φ (m + n) .

Wenn Sie also zahlen konnen und das Prinzip der rekursiven Konstruktion ken-
¨ ¨
nen, so konnen Sie auch addieren. Nun zur Multiplikation m·n, ebenfalls rekursiv
¨
nach n ” wir setzen hier voraus, dass die Addition schon bekannt ist:

m · 1 := m
m · (n + 1) := m · n + m.




22
2 Algebraische Grundstrukturen:
Gruppen, Ringe, K¨rper
o
2.1 Zweistellige Verknupfungen, Gruppen
¨
Wir betrachten eine nicht leere Menge A. Eine Abbildung A — A ’ A nennt
man eine zweistellige Verknupfung. Statt wie sonst ublich mit f, g, φ oder
¨
¨
¨hnlichen Buchstaben, bezeichnet man eine derartige Abbildung meist mit +, ·
a
oder —. Im Moment nehmen wir —. Wir schreiben dann auch a — b anstelle von
— (a, b) . Das Paar (a, b) ∈ A—A wird also unter der Verknupfung auf das Element
¨
a — b ∈ A abgebildet. Sie kennen schon viele derartige Verknufpungen, z.B. die
¨
Addition auf N, die Multiplikation auf N oder auf R etc.

De¬nition 2.1 — sei eine zweistellige Verknupfung auf der Menge A.
¨
a) — heisst assoziativ, wenn fur alle Element a, b, c ∈ A die Gleichung
¨

(a — b) — c = a — (b — c)

gilt.
b) — heisst kommutativ, wenn fur alle a, b ∈ A
¨

a—b=b—a

gilt.
c) Ein Element e ∈ A heisst Neutralelement, wenn fur jedes a ∈ A
¨

a—e=a=e—a

gilt.

Bemerkung 2.1 Ein Neutralelement ist, falls es existiert, eindeutig.

Beweis. Es seien e und e zwei Neutralelemente. Dann folgt aus der De¬ni-
tion
e=e —e=e.

Es sei eine zweistellige assoziative Verknupfung — auf der Menge A gegeben.
¨
Es ist dann ziemlich klar, dass man nach Belieben “umklammern” kann. Z.B. ist
dann fur Elemente a1 , a2 , . . . , an ∈ A ein Produkt a1 — a2 — . . . — an ∈ A eindeutig
¨
de¬niert. Eigentlich hat man nur festgelegt, wie man je zwei Elemente verknupft, ¨
sodass man dieses Element durch sukzessive Multiplikation gewinnen muss. Wir
machen das nun ganz formal und de¬nieren a1 — a2 — . . . — an rekursiv wie folgt:
Fur n = 1 ist das einfach a1 . Rekursiv setzen wir
¨

a1 — a2 — . . . — an — an+1 := (a1 — a2 — . . . — an ) — an+1 .

23
Damit haben wir fur beliebiges n ∈ N und beliebige Elemente a1 , a2 , . . . , an ∈ A
¨
das Element a1 — a2 — . . . — an ∈ A de¬niert. Diese De¬ninition hangt zunachst
¨ ¨
nicht von der Assoziativitat ab und konnte mit einer beliebigen zweistelligen
¨ ¨
Verknupfung so gemacht werden. Nun zeigen wir, dass man dann beliebig um-
¨
klammern kann:

Satz 2.1 Fur n ∈ N, a1 , a2 , . . . , an ∈ A und 1 ¤ k ¤ n ’ 1 gilt
¨

(a1 — a2 — . . . — ak ) — (ak+1 . . . — an ) = a1 — a2 — . . . — an (2.1)

Beweis. Wir de¬nieren die Aussage E (n) , n ∈ N wie folgt: Fur beliebige¨
Elemente a1 , a2 , . . . , an ∈ A und jedes k ∈ N mit 1 ¤ k ¤ n ’ 1 gilt (2.1).
Wir zeigen nun, dass E (n) fur alle n ∈ N gilt, was die Aussage des Satzes
¨
beweist. Der Beweis erfolgt mit Induktion nach n.
Induktionsverankerung: Fur n = 1 ist die Aussage trivialerweise richtig, denn
¨
es gibt gar keine Zahl k mit 1 ¤ k ¤ n ’ 1.
Induktionsschluss: Wir zeigen E (n) =’ E (n + 1) .
Seien also a1 , a2 , . . . , an+1 ∈ A und 1 ¤ k ¤ n. Ist k = n, so ist (2.1) einfach
die Gleichung

a1 — a2 — . . . — an — an+1 = (a1 — a2 — . . . — an ) — an+1 ,

die durch die rekursive De¬nition abgedeckt ist. Ist 1 ¤ k ¤ n ’ 1 so schliessen
wir wie folgt:

(a1 — a2 — . . . — ak ) — (ak+1 — . . . — an+1 ) = (a1 — . . . — ak ) — ((ak+1 — . . . — an ) — an+1 )
= ((a1 — . . . — ak ) — (ak+1 — . . . — an )) — an+1
= (a1 — . . . — an ) — an+1
= a1 — . . . — an+1 .

Die erste und vierte Gleichung gilt nach der rekursiven De¬nition, die zweite
wegen der Assoziativit¨t und die dritte folgt aus der Induktionsvoraussetzung.
a
Damit ist E (n + 1) gezeigt.

De¬nition 2.2 Eine Menge A, versehen mit einer zweistelligen Operation —, die
assoziativ ist und ein Neutralelement besitzt, nennt man eine Halbgruppe. Eine
Halbgruppe heisst abelsch, wenn die Operation zus¨tzlich kommutativ ist.
a
Eine Halbgruppe heisst Gruppe, wenn sie zus¨tzlich die folgende Eigenschaft
a
hat: Zu jedem Element a ∈ A existiert ein Element b ∈ A mit

a — b = b — a = e. (2.2)

Man nennt ein b ∈ A mit dieser Eigenschaft ein zu a inverses Element.


24
Wir schreiben dann (A, —) fur die Halbgruppe bzw. die Gruppe. Fur abelsche
¨ ¨
Halbgruppen und Gruppen bezeichnet man die Verknupfung ublicherweise mit +.
¨ ¨
Oft verwendet man auch einfach (je nach Situation) · als Verknupfungszeichen.
¨

Lemma 2.1 Sei (A, —) eine Halbgruppe und sei a ∈ A. Existiert ein b ∈ A mit
(2.2), so ist dieses Element eindeutig.

Beweis. b, b seien zwei derartige Elemente. Dann gilt

b = b — e = b — (a — b ) = (b — a) — b = e — b = b .


Nach dem Lemma k¨nnen wir also von dem Inversen eines Elementes einer
o
Halbgruppe sprechen. Eine Gruppe ist also eine Halbgruppe in der jedes Element
ein Inverses hat. Man bezeichnet dieses Inverse von a ublicherweise als a’1 , oder
¨

<<

. 5
( 60 .)



>>