Mathematische Grundlagen für die Informatik || Zahlenmengen

Zahlenmengen 117

3 Zahlenmengen

Wir haben in den vorigen Kapiteln bereits die aus der Schule und dem tagli-chen Leben bekannten Zahlenmengen in Beispielen verwendet. In diesem Kapi-tel werden wir zunachst die naturlichen Zahlen axiomatisch einfuhren und dannaus ihnen mithilfe von Auivalenzrelationen schrittweise die ganzen Zahlen unddie rationalen Zahlen konstruieren.

3.1 Die Menge der naturlichen Zahlen

Wir werden zunachst den Begriff der Zahlstruktur durch dafur wesentliche Ei-genschaften axiomatisch festlegen und dann die Menge der naturlichen Zahlenals ein Beispiel fur eine solche Zahlstruktur ansehen. Zahlen basiert darauf, zueiner Zahl die nachste zu bestimmen, also zu einer Zahl die Zahl 1 hinzuaddierenzu konnen. Wir werden auf der Basis dieser elementaren Operation arithmetischeVerknupfungen wie die Addition, die Multiplikation und das Potenzieren mithil-fe rekursiver Definitionen einfuhren und die fur diese Rechenarten bekanntenRegeln auflisten. Da die naturlichen Zahlen zum Zahlen verwendet werden, liegtes nahe, diese Menge als Referenzmenge fur die Abzahlbarkeit von beliebigenMengen zu betrachten.

Nach dem Durcharbeiten dieses Kapitels sollten Sie Lernziele

• die axiomatische Einfuhrung der Menge der naturlichen Zahlen verstehen,

• die Rechenregeln fur naturliche Zahlen kennen.

3.1.1 Einfuhrung der Menge der naturlichen Zahlen

Man kann Zahlen, und so sind diese vielleicht auch in der Menschheitsgeschichteentstanden, als Abstraktionen von Mengen mit derselben Anzahl von Elementenbetrachten. Sieben Apfel, sieben Birnen, sieben Ziegen bilden Mengen mit 7 Ele-menten, welches man z.B. durch sieben Kerben in einem Holzstab oder siebenStriche im Sand oder durch die Symbole 7 oder VII notieren kann.

Was braucht man nun ”wirklich“ zum Zahlen? Nun, wir brauchen eine unend-liche Menge, deren Elemente zum Zahlen verwendet werden konnen (Strich-folgen, Zahlensymbole, . . .). Dann brauchen wir eine Zahl, bei der das Zahlenbeginnt, eine ”kleinste“ Zahl, und wir mussen festlegen, dass verschiedene Zah-lensymbole auch verschiedene Anzahlen angeben.

K.-U. Witt, Mathematische Grundlagen für die Informatik, DOI 10.1007/978-3-658-03079-7_3, © Springer Fachmedien Wiesbaden 2013

118 Naturliche Zahlen

Diese grundlegenden Eigenschaften des Zahlens wollen wir mathematisch mit-hilfe einer Zahlstruktur

(S, 0, s)

festlegen. Dabei sei S eine nicht leere Menge, 0 ∈ S ein ausgezeichnetes Ele-ment, welches wir Null nennen, sowie s : S → S eine Funktion, die wir Nach-folgerfunktion nennen. Die Zahlstruktur soll dabei folgende Axiome erfullen:

(P1) Fur alle x ∈ S gilt: s(x) = 0, d.h. 0 kann kein Nachfolger einer Zahl sein.Zahlstruktur

Damit wird 0 quasi als kleinste Zahl festgelegt.

(P2) s ist injektiv, d.h. fur alle x, y ∈ S gilt: Ist x = y, dann ist auchs(x) = s(y), verschiedene Zahlen haben verschiedene Nachfolger. Dasbedeutet allgemeiner, dass verschiedene Zahlen auch verschiedene An-zahlen bedeuten.

(P3) Fur jede Teilmenge M von S gilt: Ist 0 ∈M und folgt daraus, dass x ∈MInduktionsaxiom

ist, auch, dass s(x) ∈ M ist, dann gilt M = S. Dieses ist das sogenannteInduktionsaxiom.

Diese Axiome gehen auf Dedekind19 und Peano20 zuruck. Deswegen wird(S, 0, s) auch Dedekindtripel genannt, und die Axiome P1 - 3 gehoren zu denDedekindtripel

Peano-Axiome Peano-Axiomen zur Definition der Menge der naturlichen Zahlen.

Die konkreten Strukturen im folgenden Beispiel erfullen diese Axiome, sind alsoBeispiele fur Zahlstrukturen.

Beispiel 3.1 a) (S1, 01, s1) mit S1 = {ε, |, ||, |||, . . . , }, 01 = ε, die leere Strich-folge, und s1(x) = x|.b) (S2, 02, s2) mit S2 = {∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}, . . .} mit 02 = ∅und s2(x) = x ∪ {x}. �

Wir wollen zwei Peano-Strukturen (S1, 01, s1) und (S2, 02, s2) strukturgleichIsomorphie

oder isomorph nennen, falls es eine bijektive Abbildung

ϕ : S1 → S2

gibt, fur die

ϕ(s1(x)) = s2(ϕ(x)) fur alle x ∈ S1 (3.1)

gilt. Die Abbildung ϕ ordnet also jedem Element der einen genau ein Elementder anderen Struktur zu, und diese Zuordnung ist vertraglich mit den Nachfolger-funktionen in beiden Strukturen. Das bedeutet, dass, wenn x ∈ S1 dem Elementy ∈ S2 zugeordnet wird, dann werden auch ihre Nachfolger s1(x) ∈ S1 unds2(y) ∈ S2 einander zugeordnet. Sind S1 und S2 isomorph, so schreiben wir:(S1, 01, s1) ∼= (S2, 02, s2).

19 Julius Wilhelm Richard Dedekind (1831 - 1916), deutscher Mathematiker, lieferte unteranderem zur Defintion und Eigenschaften von Zahlenmengen sowie zur Algebra funda-mentale Beitrage.

20 Giuseppe Peano (1858 - 1932), italienischer Mathematiker und Logiker, beschaftigte sichmit axiomatischen Ansatzen zur Beschreibung von Mengen und Strukturen.

Zahlenmengen 119

Beispiel 3.2 Wir zeigen, dass die beiden Zahlstrukturen aus Beispiel 3.1 iso-morph sind. Dazu legen wir die Abbildung ϕ : S1 → S2 wie folgt rekursiv fest:

ϕ(ε) = ∅ϕ(x|) = ϕ(x) ∪ {ϕ(x)}

Wir berechnen mithilfe dieser rekursiven Definition z.B. ϕ(|||) schrittweise:

ϕ(|) = ϕ(ε) ∪ {ϕ(ε)} = ∅ ∪{∅} = {∅}

ϕ(||) = ϕ(|) ∪ {ϕ(|)} = {∅} ∪{{∅}} = {∅, {∅}}

ϕ(|||) = ϕ(||) ∪ {ϕ(||)} = {∅, {∅}} ∪{{∅ , {∅}}} = {∅, {∅}, {∅, {∅}}}

Diese Abbildung ϕ ist bijektiv und sie erfullt die Bedingung (3.1):

ϕ(s1(x)) = ϕ(x|) = ϕ(x) ∪ {ϕ(x)} = s2(ϕ(x))

Es gilt also: (S1, ε, s1) ∼= (S2, ∅, s2). �

Durch Verallgemeinerung der Uberlegungen in obigem Beispiel kann man be-weisen, dass alle Zahlstrukturen isomorph zueinander sind: Zu je zwei Struktu-ren, die die Peano-Axiome erfullen, lasst sich eine bijektive Abbildung finden,die die Bedingung (3.1) erfullt. Der folgende Satz besagt, dass diese Abbildungin jedem Fall die beiden Nullen einander zuordnet.

Satz 3.1 Fur alle Zahlstrukturen (S1, 01, s1) und (S2, 02, s2) gilt

(S1, 01, s1) ∼= (S2, 02, s2)

und fur alle Isomorphismen ϕ zwischen diesen Strukturen gilt

ϕ(01) = 02

�

Ubungsaufgaben

3.1 Beweisen Sie Satz 3.1! �

Gemaß Satz 3.1 sind also alle Zahlstrukturen bis auf die Benennung ihrer Ele-mente identisch. Wir konnen fur den taglichen Gebrauch also irgendeine Zahl-struktur auswahlen. Da die Notation der Elemente der Zahlstrukturen in Beispiel3.1 in Bezug auf ihr Hinschreiben, ihr Lesen oder in Bezug auf das Rechnen


mit ihnen sehr umstandlich ist, stellt sich die Frage nach geeigneten Zahlensym-bolen. Im Verlaufe der Geschichte hat es hier unterschiedliche Entwicklungengegeben, wie z.B. die romischen Zahlen oder die arabischen Zahlen. Die ara-bischen Zahlen haben sich durchgesetzt, weil sie auf einem Stellenwertsystembasieren, woraus sich eine systematische Notation ergibt sowie einfache Verfah-ren zur Durchfuhrung von Rechenoperationen.

Wenn wir nun von der Struktur (S1, ε, s1) im Beispiel 3.1 ausgehen und fur eineDie Menge der

naturlichen

ZahlenFolge von n Strichen das arabische Zahlensymbol fur n und den Nachfolger s(n)von n mit n + 1 notieren, erhalten wir die Menge der uns bekannten naturlichenZahlen

N0 = { 0, 1, 2, 3, . . . }

als weitere Zahlstruktur (N0, 0, s). Da man gelegentlich Aussagen uber allenaturlichen Zahlen ohne die Null machen mochte, fuhren wir N als Symbol furdiese Menge ein:

N = N0 − {0} = { 1, 2, 3, . . . }

3.1.2 Rechnen mit naturlichen Zahlen

Mithilfe der Nachfolgerfunktion s lassen sich nun die elementaren arithmeti-Addition und

Multiplikation

naturlicher

Zahlen

schen Operationen fur naturliche Zahlen, Addition und Multiplikation, rekursivdefinieren (siehe auch Kapitel 4).

(1) Wir fuhren die Addition zweier Zahlen x und y auf die y-fache Addition der1 zu x zuruck: add : N0 × N0 → N0 definiert durch

add(x, 0) = x

add(x, s(y)) = s(add(x, y))

Mit dieser Berechnungsvorschrift ergibt sich z.B.

add(2, 3) = add(2, s(2)) = s(add(2, 2)) = s(add(2, s(1)))

= s(s(add(2, 1))) = s(s(add(2, s(0))))

= s(s(s(add(2, 0)))) = s(s(s(2))) = s(s(3)) = s(4)

= 5

(2) Mithilfe der Addition konnen wir nun die Multiplikation mult : N0 × N0 →N0 definieren:

mult(x, 0) = 0

mult(x, s(y)) = add(mult(x, y), x)

Die Multiplikation von x und y wird hier durch y-fache Addition von x mitsich selbst berechnet.

Zahlenmengen 121

(3) Analog konnen wir nun die Potenzfunktion mithilfe der Multiplikation defi-nieren: exp : N0 × N0 → N0 mit

exp(x, 0) = 1

exp(x, s(y)) = mult(exp(x, y), x)

Die Potenzierung von x mit y wird hier durch y-fache Multiplikation von xmit sich selbst berechnet.

In analoger Art und Weise konnen weitere arithmetische Operationen definiertwerden, die letztendlich immer auf der Addition und damit auf der Addition der1, d.h. auf der Nachfolgerfunktion s – also auf dem Zahlen – basieren. Und zudiesem Zweck, namlich zum Zahlen, haben wir die naturlichen Zahlen ja geradeeingefuhrt.

Ubungsaufgaben

3.2 (1) Berechnen Sie mult(2, 3)!

(2) Berechnen Sie exp(2, 3)! �

Im Folgenden schreiben wir wie ublich x + y anstelle von add(x, y) und x · yoder xy anstelle von mult(x, y) sowie xy fur exp(x, y).

Die naturlichen Zahlen sind abgeschlossen bezuglich der Addition und Multi- Abgeschlossen-

heit von

Addition und

Multiplikation

plikation. Das bedeutet, dass die Summe bzw. das Produkt zweier naturlicherZahlen wieder eine naturliche Zahl ist. Die naturlichen Zahlen sind nicht ab-geschlossen gegenuber Subtraktion und Division, denn die Differenz bzw. derQuotient zweier naturlicher Zahlen muss keine naturliche Zahl sein. Auf Erwei-terungen der Menge der naturlichen Zahlen auf Zahlenmengen, in denen auchdiese Operationen abgeschlossen sind, gehen wir in Kapitel 3.6 und 3.7 ein.

3.1.3 Rechenregeln in N0

Mithilfe vollstandiger Induktion (siehe Kapitel 3.2) und bereits bewiesener Ei-genschaften kann man beweisen, dass fur beliebige Zahlen x, y, z ∈ N0 folgendebekannte Rechenregeln gelten:

(A1) Assoziativgesetz der Addition: (x + y) + z = x + (y + z), d.h. bei der Rechenregeln

Addition von mehr als zwei Zahlen kommt es nicht auf die Reihenfolgeder Ausfuhrung dieser Operation an. Deshalb konnen die Klammern auchweggelassen werden: x + y + z.


(A2) Kommutativgesetz der Addition: x + y = y + x, d.h. das Ergebnis einerAddition ist unabhangig von der Reihenfolge der Operanden.

(A3) Neutrales Element der Addition: x + 0 = 0 + x = x, d.h. die Additionmit 0 verandert den anderen Operanden nicht.

(M1) Assoziativgesetz der Multiplikation: (xy)z = x(yz).

(M2) Kommutativgesetz der Multiplikation: xy = yx.

(M3) Neutrales Element der Multiplikation: x · 1 = 1 · x = x, d.h. die Multi-plikation mit 1 verandert den anderen Operanden nicht.

(D1) Distributivgesetz 1: x(y + z) = xy + xz.

(D2) Distributivgesetz 2: (x + y)z = xz + yz.

In gewissem Rahmen sind auch die Umkehroperationen Subtraktion und Divisi-on zur Addition bzw. zur Multiplikation fur naturliche Zahlen definiert:

• Subtraktion: Gilt x + y = z, dann gilt x = z − y. x heißt dann auch dieDifferenz von z und y. Mithilfe des Kommutativgesetzes (A2) kann man imUbrigen sofort ableiten, dass auch y = z − x gelten muss.

• Division: Gilt xy = z, dann gilt x = z : y. x heißt dann auch der Quotientvon z und y. Anstelle von z : y notieren wir auch z/y oder z

y.

Die Relation≤⊆ N0×N0 definiert durch x ≤ y genau dann, wenn eine Zahl d ∈N0 existiert mit x + d = y legt auf N0 eine totale Ordnung fest (siehe Abschnitt2.1.3). Fur diese Ordnung gelten die beiden folgenden Vertraglichkeitsregeln,auch Monotonieregeln genannt:

(O1) sind x, y, z ∈ N0 und ist x ≤ y, dann gilt auch x + z ≤ y + z,Monotonieregeln

(O2) sind x, y, z ∈ N0 und ist x ≤ y, dann gilt auch xz ≤ yz.

Anstelle von x ≤ y schreiben wir auch y ≥ x.

Zur Notation der Summe von mehreren Summanden x1, x2, . . . , xn verwendetSummations-

symbol man oft auch das Summationssymbol∑

:

x1 + x2 + . . . + xn =n∑

i=1

xi

Lauft der Summationsindex i nicht zwischen den Grenzen 1 und n, sondern zwi-schen u und o mit u, o ∈ N0 und u ≤ o, dann notieren wir

xu + xu+1 + . . . + xo =o∑

i=u

xi

u heißt untere und o heißt obere Index- oder Summationsgrenze. Fur den Fallu > o legen wir

∑oi=u xi = 0 fest.

Zahlenmengen 123

Analog wird fur die Multiplikation mehrerer Faktoren xu, xu+1, . . . xo Multiplikations-

symbol

xu · xu+1 · . . . · xo =o∏

i=u

xi

geschrieben. Fur den Fall u > o legen wir∏o

i=u xi = 0 fest.

Sowohl bei der Addition als auch bei der Multiplikation kann die Anzahl derSummanden bzw. die Anzahl der Faktoren unendlich sein, d.h. es kann u = −∞oder o = ∞ oder u = −∞ und o = ∞ sein. Man spricht dann von einerunendlichen Summe bzw. von einem unendlichen Produkt.

Aus den Distributivgesetzen lasst sich das folgende verallgemeinerte Distribu-tivgesetz ableiten: Verallgemeinertes

Distributivgesetz(m∑

i=1

xi

)(n∑

j=1

yj

)= (x1 + x2 + . . . + xm)(y1 + y2 + . . . + yn)

= x1y1 + x1y2 + . . . + x1yn

+ x2y1 + x2y2 + . . . + x2yn

...+ xmy1 + xmy2 + . . . + xmyn

=m∑

i=1

n∑j=1

xiyj

Wegen der Kommutativitat der Addition gilt

m∑i=1

n∑j=1

xiyj =n∑

j=1

m∑i=1

xiyj

3.1.4 Zusammenfassung

Naturliche Zahlen sind ein Beispiel fur eine Zahlstruktur. Zahlstrukturen werdendurch die Peano-Axiome festgelegt: Eine Zahlstruktur enthalt ein kleinstes Ele-ment, mit dem das Zahlen beginnt, und verschiedene Elemente stehen fur ver-schiedene Anzahlen. Aufgrund der rekursiven Struktur der naturlichen Zahlenlassen sich alle arithmetischen Operationen jeweils rekursiv und schrittweise auf-einander aufbauend festlegen, und mithilfe vollstandiger Induktion lassen sichdie bekannten arithmetischen Rechenregeln nachweisen. Die naturlichen Zah-len sind abgeschlossen gegenuber Addition und Multiplikation, d.h. die Additionbzw. die Multiplikation zweier naturlicher Zahlen ist wieder eine naturliche Zahl.Subtraktion und Division hingegen sind nur eingeschrankt moglich, ihr Ergebnismuss keine naturliche Zahl sein.

124 Vollstandige Induktion und verallgemeinertes Rekursionsschema

3.2 Vollstandige Induktion und verallgemeinertes

Rekursionsschema

[Vollstandige Induktion und verallgemeinertes Rekursionsschema]Die Menge der naturlichen Zahlen ist induktiv definiert mithilfe der Peano-Axiome. Das Axiom (P3) gibt eine Methode vor, die Vollstandige Induktion, mitder bewiesen werden kann, dass ein Pradikat auf alle naturlichen Zahlen zutrifft.

In fruheren Kapiteln haben wir Strukturen, wie z.B. die Syntax aussagenlogi-scher Formeln, und Eigenschaften von Strukturen, wie z.B. die Semantik aussa-genlogischer Formeln, rekursiv definiert. Um Aussagen uber solche Strukturenund deren Eigenschaften zu beweisen, bietet es sich deshalb an, solche Beweisenach einem allgemeinen rekursiven Schema durchzufuhren.

Nach dem Durcharbeiten dieses Kapitels sollten SieLernziele

• die Beweismethode der vollstandigen Induktion verstehen und anwendenkonnen,

• das verallgemeinerte Rekursionschema erklaren und anwenden konnen.

3.2.1 Vollstandige Induktion

Vollstandige Induktion ist eine Methode, mit der bewiesen werden kann, dass einPradikat auf die Menge der naturlichen Zahlen zutrifft, d.h. dass ein Pradikat P :N0 → B die Losungsmenge RP = N0 besitzt, d.h. dass P von allen naturlichenZahlen erfullt wird (siehe Abschnitt 2.2.2). Die Menge der naturlichen Zahlenwird in Kapitel 3.1.1 eingefuhrt. Grundlage fur die Vollstandige Induktion istdabei das Axiom P3 (siehe Seite 118).

Ein Beweis mit vollstandiger Induktion erfolgt dementsprechend gemaß folgen-dem Schema:

• Induktionsanfang: Zeige, dass P (0) gilt, d.h. dass 0 ∈ RP gilt.Induktionsanfang

• Induktionsschritt: Zeige: ∀n ∈ N0 : P (n) ⇒ P (n + 1). Dabei heißt P (n)Induktionsschritt

Induktionsannahme Induktionsannahme oder Induktionsvoraussetzung und P (n+1) Induktions-Induktions-

behauptungbehauptung.

Haben wir fur ein Pradikat P : N0 → B Induktionsanfang und Induktionsschrittgezeigt, dann wissen wir, dass P (n) fur alle n ∈ N0 gilt, d.h. dass

RP = {n ∈ N0 | P (n)} = N0

gilt: Das Pradikat P trifft auf alle naturlichen Zahlen zu.

Bemerkung 3.1 Veranschaulichen kann man diese Methode an folgendemProblem: Wann bin ich in der Lage, eine (unendliche) Leiter hinauf zu steigen.Nun, ich werde es schaffen, wenn ich in der Lage bin, die folgenden beiden

Zahlenmengen 125

Schritte zu tun: Ich muss die erste Sprosse besteigen konnen (das entspricht demInduktionsanfang), und wenn ich auf irgendeiner Stufe stehe (das entspricht derInduktionsannahme), dann muss ich auf die nachste Sprosse steigen konnen (da-mit habe ich den Induktionsschritt vollzogen). �

Beispiel 3.3 a) Zeige: ∀n ∈ N0 :∑n

i=0 i = n(n+1)2

. Das Pradikat

P (n) =n∑

i=0

i =n(n + 1)

2(3.2)

behauptet also, dass sich∑n

i=0 i, die Summe der Zahlen von 0 bis n, fur jedenaturliche Zahl n durch den Ausdruck n(n+1)

2berechnen lasst.

Wir beweisen die Behauptung mit vollstandiger Induktion gemaß dem obigenSchema:

Induktionsanfang: Zeige, dass P (0) gilt. Es ist0∑

i=0

i = 0 =0(0 + 1)

2

also gilt P (0).

Induktionsschritt: Zeige unter der Annahme, dass P (n) gilt, auch P (n + 1) gilt.In unserem Fall mussen wir also zeigen, dass

P (n + 1) =n+1∑i=0

i =(n + 1)(n + 2)

2

gilt unter der Vorraussetzung, dass

P (n) =n∑

i=0

i =n(n + 1)

2

gilt.

Die Summe der Zahlen von 0 bis n + 1 ist gleich der Summe der Zahlen von 1bis n plus n + 1, d.h. es ist

n+1∑i=0

i =n∑

i=0

i + (n + 1) (3.3)

Es gilt nun:n+1∑i=0

i =n∑

i=0

i + (n + 1) wegen (3.3)

=n(n + 1)

2+ (n + 1) wegen der Induktionsannahme

=n(n + 1) + 2(n + 1)

2

=(n + 1)(n + 2)

2


Damit haben wir den Induktionsschritt durchgefuhrt.

Insgesamt haben wir also gezeigt, dass unser Pradikat (3.2) fur alle naturlichenZahlen erfullt ist.

b) Sei x ∈ Z mit x = 1, dann gilt, dass xn−1 fur alle n ∈ N0 durch x−1 teilbarist.

Zunachst formulieren wir diese Behauptung als Pradikat:

P (n) = ∀n ∈ N0 :xn − 1

x− 1∈ Z (3.4)

Wir beweisen diese Behauptung durch vollstandige Induktion:

Induktionsanfang: P (0) gilt offensichtlich.

Induktionsschritt: Zeige unter der Annahme, dass P (n) gilt, auch P (n + 1) gilt.In unserem Fall mussen wir also zeigen, dass

xn+1 − 1

x− 1∈ Z (3.5)

gilt unter der Voraussetzung, dass

xn − 1

x− 1∈ Z (3.6)

gilt.

Wir formen (3.5) geeignet um:

xn+1 − 1

x− 1=

x · (xn − 1) + (x− 1)

x− 1= x · x

n − 1

x− 1+ 1

Hieraus folgt mit der Induktionsvoraussetzung (3.6) und der Voraussetzung x ∈Z, dass (3.5) gilt.

Insgesamt haben wir also gezeigt, dass unser Pradikat (3.4) fur alle naturlichenZahlen erfullt ist.

c) In Satz 1.19 auf Seite 74 haben wir bereits mithilfe von Bitvektoren bewiesen,dass, wenn eine Menge M m Elemente hat, die Potenzmenge P(M) von M2m Elemente hat. Jetzt geben wir einen weiteren Beweis mithilfe vollstandigerInduktion an. Dazu formalisieren wir diese Behauptung als Pradikat:

P (m) = ∀m ∈ N0 : |M | = m ⇒ |P(M)| = 2m

Induktionsanfang: Zeige P (0). Sei also m = 0, d.h. M = ∅ und damit P(M) ={ ∅ }, woraus folgt: |P(M)| = 1. Da 20 = 1 ist, gilt also die Behauptung furm = 0.

Induktionsschritt: Zeige, dass |M | = m + 1 ⇒ |P(M)| = 2m+1 gilt, unter derVoraussetzung, dass |P(M)| = 2m gilt fur |M | = m.

Zahlenmengen 127

Sei M = {a1, a2, . . . , am, am+1} sowie M ′ = {b1, b2, . . . , bm}, bi ∈ M , 1 ≤ i ≤m, und {a} = M −M ′. Nach Induktionsvoraussetzung ist |P(M ′)| = 2m.

Sei etwa P(M ′) = {D1, D2, . . . , D2m}. Alle Dj ∈ P(M ′), 1 ≤ j ≤ 2m, sindauch Elemente von P(M). Es fehlen noch die Elemente Dj , zu denen das Ele-ment a hinzugefugt wird: Dj ∪ {a}, 1 ≤ j ≤ 2m. Insgesamt enthalt P(M) also2m + 2m = 2 · 2m = 2m+1 Elemente.

Damit ist der Induktionsschritt gezeigt.

d) Sei x ∈ R, x > −1, x = 0, dann gilt: ∀n ∈ N2 : (1 + x)n > 1 + nx.21

Wir beweisen diese Behauptung mit vollstandiger Induktion:

Induktionsanfang: Zeige P (2). Fur n = 2 gilt

(1 + x)2 = 1 + 2x + x2

> 1 + 2x da x2 > 0

Induktionsschritt: Zeige, dass (1+x)n+1 > 1+(n+1)x gilt, unter Voraussetzung,dass (1 + x)n > 1 + nx gilt, fur x ∈ R, x > −1, x = 0. Es gilt:

(1 + x)n+1 = (1 + x)n(1 + x)

> (1 + nx)(1 + x) nach Induktionsvoraussetzung= 1 + x + nx + nx2

> 1 + nx + x da nx2 > x

= 1 + (n + 1)x

e) Als letztes Beispiel wollen wir das Pradikat

P (n) = ∀n ∈ N7 : 2n2 + 1 < 2n

beweisen.

Induktionsanfang: Zeige P (7). Es gilt 2 · 72 + 1 = 99 und 27 = 128, und damitP (7).

Induktionsschritt: Wir nehmen an, dass P (n) = 2n2 + 1 < 2n gilt, und zeigen,dass dann auch P (n + 1) = 2(n + 1)2 + 1 < 2n+1 gilt.

Es ist

2(n + 1)2 + 1 = 2(n2 + 2n + 1) + 1

= 2n2 + 1 + 4n + 2

< 2n + 4n + 2 wegen der Induktionsannahme< 2n + 2n da 4n + 2 < 2n fur n ≥ 7 (siehe= 2 · 2n = 2n+1 Ubung 3.3 (1))

21 Diese Ungleichung wird als Bernoullische Ungleichung bezeichnet, benannt nach JakobBernoulli (1654 - 1705), einer der Mitglieder der beruhmten schweizerischen Gelehrten-familie Bernoulli (niederlandischer Herkunft), die im 17. und 18. Jahrhundert als Mathe-matiker, Physiker, Mediziner und Theologen hervorragende Beitrage zu diesen Wissen-schaften geliefert haben.


Bemerkung 3.2 Bei den beiden letzten Beispielen ist der Induktionsanfangnicht P (0), sondern P (2) bzw. P (7). Fur kleinere Werte von n gilt die Be-hauptung namlich nicht. Dies ist aber unerheblich und kein prinzipieller Verstoßgegen das Prinzip der Vollstandigen Induktion, denn wir konnen jedes Pradi-kat P (n), fur welches der Induktionsanfang P (c) fur ein c ∈ N0 gilt, trans-formieren in ein aquivalentes Pradikat P ′(n), indem jedes Vorkommen von ndurch n + c ersetzt wird. In Beispiel d) ware die transformierte Behauptung alsoP ′(n) = (1 + x)n+2 > 1 + (n + 2)x, und in Beispiel e) ware die transformierteBehauptung P ′(n) = 2(n + 7)2 + 1 < 2n+7, und beide Behauptungen geltendann fur alle n ∈ N0. �

Ubungsaufgaben

3.3 Beweisen Sie folgende Behauptungen:

(1) ∀n ∈ N, n ≥ 5: 2n + 1 ≤ 2n−1.

(2) ∀n ∈ N:∑n

i=1 2(i− 1) = n2.

(3) Sei q ∈ R, q = 1, dann gilt ∀n ∈ N0:∑n

i=0 qi = 1−qn+1

1−q,

(4) Sei x, y ∈ Z, dann gilt ∀n ∈ N0: xn−yn

x−y∈ Z.

(5) ∀n ∈ N:∑n

i=11

i(i+1)= n

n+1.

(6) ∀n ∈ N:∑2n

i=1(−1)i+1 · i2 =∑2n

i=i i.

(7) ∀n ∈ N:∑n

i=1 i3 = (∑n

i=i i )2

=(

n(n+1)2

)2.

(8) Die Fermat-Zahlen sind fur n ≥ 0 definiert durch An = 22n+1. Zeigen

Sie, dass fur alle n ≥ 1 gilt:∏n−1

i=0 Ai = An − 2.

(9) Gilt ∀n ∈ N0: n2 − n + 41 ∈ P? �

3.2.2 Verallgemeinertes Rekursionsschema

Wir haben schon im Kapitel 1.2 rekursive Definitionen benutzt. So haben wirim Abschnitt 1.2.2 die Syntax der Aussagenlogik definiert, indem wir zunachst– als Rekursionsanfang – atomare Formeln festgelegt haben und anschließend– im Rekursionsschritt – beschrieben, wie aus bereits gegebenen Formeln neuegebildet werden konnen. In der Definition 2.12 auf Seite 103 haben wir die n-fache Komposition einer Relation R mit sich selbst rekursiv definiert: Zunachsthaben wir als Rekursionsanfang R = id festgelegt und im Rekursionsschritt, wieRn aus Rn−1 berechnet wird.

Zahlenmengen 129

Tatsachlich sind rekursive Definition und vollstandige Induktion nicht auf aufnaturlichen Zahlen definierte Funktionen beschrankt. Insbesondere in der Infor-matik sind viele wichtige Datenstrukturen, wie z.B. Listen und Baume, rekur-sive Strukturen, auf denen Operationen wie Einfugen, Loschen und Suchen vonElementen entsprechend als rekursive Prozeduren programmiert werden konnen.Rekursion ist ein allgmeines Problemloseprinzip, welches in vielen Fallen zu

”eleganten“ Losungen fuhrt.

Beweise von Eigenschaften rekursiv definierter Strukturen konne mithilfe des Verallgemeinertes

Rekursionsschemafolgenden verallgemeinerten Induktionsprinzips gefuhrt werden: Sei M eine in-duktiv definierte Menge und P : M → B ein totales Pradikat. Falls gilt:

• Induktionsanfang: Gilt P (x) fur alle explizit angegebenen Elemente von Mund

• Induktionsschritt: gilt ur alle x1, . . . , xk ∈ M und fur jedes daraus nach denDefinitionsregeln von M erzeugbare y ∈M : P (x1), . . . , P (xk) ⇒ P (y),

dann gilt fur alle x ∈ M : P (x). Haben wir fur ein Pradikat P : M → B In-duktionsanfang und Induktionsschritt gezeigt, dann wissen wir, dass P fur alleElemente von M zutrifft.

Beispiel 3.4 Im Abschnitt 1.2.2 haben wir die MengeA der aussagenlogischenFormeln induktiv definiert. Wir beweisen nun das Pradikat P uber dieser Menge,welches besagt, dass in jeder aussagenlogischen Formel, die Anzahl der offnen-den Klammern gleich der Anzahl der schließenden Klammern ist. Wir formali-sieren zunachst dieses Pradikat. Fur eine Formel α ∈ A bezeichne α( die Anzahlder offnenden und α) die Anzahl der schließenden Klammern in α. Unser Pradi-kat lautet damit: P (α) = α( = α). Mit dem verallgemeinerten Induktionsschemazeigen wir nun, dass fur alle α ∈ A gilt P (α).

Induktionsanfang: Die explizit angegebenen Elemente vonA sind die aussagen-logischen Konstanten 0 und 1 sowie die aussagenlogischen Variablen v ∈ V .Diese atomaren Formeln enthalten keine Klammern, d.h. es gilt

0( = 0 = 0)

1( = 0 = 1)

v( = 0 = v), fur alle v ∈ V

Somit gilt P (0) und P (1) sowie P (v) fur alle v ∈ V . Damit ist der Induktions-anfang fur unser Pradikat P gezeigt.

Induktionsschritt: Fur gegebene Formeln α,β ∈ A konnen aufgrund der Defini-tionsregeln von A die Formeln

(1) γ1 = (α ∧ β),

(2) γ2 = (α ∨ β) sowie

(3) γ3 = ¬α

gebildet werden. Nach Induktionsvoraussetzung gelten P (α) und P (β), d.h.α( = α) bzw. β( = β).


Wir zeigen nun, dass auch P (γi), d.h. γi( = γi), fur i = 1, 2, 3, gilt:

Zu (1): Es gilt

γ1( = α( + β( + 1

= α) + β) + 1 wegen Induktionsvoraussetzung= γ1)

Zu (2): Der Beweis fur diesen Fall ist identisch zum Fall (1).

Zu (3): Dieser Fall gilt offensichtlich, denn bei der Negation einer Formel kom-men keine weiteren Klammern hinzu.

Damit ist auch der Induktionsschritt fur alle Falle gezeigt, und damit gilt gemaßdem verallgemeinerten Induktionsprinzip: fur alle α ∈ A: P (α). �

Ubungsaufgaben

3.4 (1) Fur die aussagenlogischen Formeln gilt nicht nur, dass die Anzahl deroffnenden gleich der Anzahl der schließenden Klammern ist, sondern auchdass in jedem Prafix einer Formel die Anzahl der schließenden Klammernnicht großer als die Anzahl der offnenden Klammern ist. Beweisen Siediese Aussage!

(2) Die MengeA der arithmetischen Ausdrucke uber N0 kann induktiv wiefolgt definiert werden:(i) a ∈ N0 ⇒ a ∈ A: Jede naturliche Zahl a ist ein arithmetischer Aus-

druck.(ii) x, y ∈ A ⇒ (x + y), (x · y) ∈ A: Sind x und y arithmetische Aus-

drucke, dann auch (x + y) und (x · y).(iii) Genau die gemaß den Regeln (i) und (ii) bildbaren Ausdrucke gehoren

zu A.Beweisen Sie: In jedem Ausdruck vonA ist die Anzahl von Zahlen aus N0

um 1 hoher als die Anzahl der Operatorsymbole + oder ·. �


Vollstandige Induktion und das verallgemeinerte Rekursionsschema sind Be-weisprinzipien, mit denen Pradikate, die fur die Menge der naturlichen Zahlenerfullt sind, bzw. Pradikate, die fur rekursiv definierte Strukturen erfullt sind, be-wiesen werden konnen. Beide Prinzipien bestehen aus zwei Schritten: Zunachstwird im Induktionsanfang bzeigt, dass die Behauptung fur eine kleinste Zahlbzw. fur alle explizit angegebenen Elemente einer induktiv definierten Menge

Zahlenmengen 131

gelten. Unter der Annahme, dass die Behauptung fur Elemente der Menge gilt,muss dann gezeigt werden, dass die Behauptung auch dann fur alle Elementegilt, die aus denen, fur die die Behauptung angenommen wird, erzeugt werden,ebenfalls gilt.

3.3 Fibonacci-Zahlen

In diesem Kapitel wollen wir die Fibonacci-Folge betrachten. Diese taucht inte-ressanterweise auf die eine oder andere Art bei vielen Phanomenen in Mathema-tik, Informatik und Naturwissenschaften aber auch in Bereichen der Kunst auf.Wir betrachten die Fibonacci-Folge hier nur als weiteres Beispiel einer rekursivdefinierten Funktion, und wir werden nur ein paar wenige ihrer Eigenschaftenbetrachten.

Die Folge wird in der Regel auf das beruhmte ”Kaninchenproblem“ zuruck-gefuhrt. Dieses Problem wird im Liber Abbaci von dem wohl großten europai-schen Mathematiker vor der Renaissance, Leonardo Pisano (Leonardo von Pisa,genannt Leornado Fibonacci, als Abkurzung von Filius Bonaccii, 1170 - 1240)als Ubungsaufgabe gestellt:

Die Vermehrung von Kaninchenpaaren geschehe wie folgt: Am Anfanggebe es kein Paar, nach dem ersten Monat sei ein Paar – durch wenauch immer geschaffen – da. Jedes Kaninchenpaar ist nach dem zweitenMonat seiner Existenz geschlechtsreif, und jedes Kaninchenpaar bringevon da an jeden Monat ein weiteres Paar zur Welt. Frage: Wie vieleKaninchenpaare Fn gibt es nach n Monaten?

Zum Zeitpunkt 0 gibt es kein Paar, also ist F0 = 0. Nach einem Monat gibt esein Paar P1, also ist F1 = 1. Nach zwei Monaten ist dieses Paar geschlechtsreifgeworden, wir nennen es P g

1 , und es ist F2 = 1. Nach drei Monaten hat P g1

ein neues Paar P2 gezeugt, so dass F3 = 2 ist. Nach vier Monaten hat P g1 ein

weiteres Paar P3 gezeugt, und P2 ist geschlechtsreif geworden, was wir mit P g2

notieren. Es ist F4 = 3. Nach funf Monaten haben P g1 und P g

2 je ein Paar, P4 undP5, gezeugt, und P3 ist geschlechtsreif geworden, was wir wieder entsprechendkennzeichnen: P g

3 . Es ist F5 = 5.

Ubungsaufgaben

3.5 Uberlegen Sie selbst in dieser Art weiter! Sie werden herausfinden, dassF6 = 8 und F7 = 13 ist. �

132 Fibonacci-Folge

Gibt es eine Gesetzmaßigkeit, mit der sich Fn fur jedes n ∈ N0 berechnen lasst?Im n-ten Monat gibt es alle Paare, die es auch im vorhergehenden Monat n − 1gegeben hat, sowie so viele Paare, wie es im Monat n − 2 gegeben hat, denndiese sind im Monat n alle geschlechtsreif und bekommen je ein Paar Nach-wuchs. Aus dieser Uberlegung ergibt sich die folgende rekursive Definition furdie Fibonacci-Funktion

F : N0 × N0 → N0

die fur jeden Monat n die Anzahl der Kaninchenpaare Fn angibt:22

F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2, n ≥ 2 (3.7)

Es gilt also z.B.

F2 = F1 + F0 = 1 + 0 = 1F3 = F2 + F1 = 1 + 1 = 2F4 = F3 + F2 = 2 + 1 = 3F5 = F4 + F3 = 3 + 2 = 5F6 = F5 + F4 = 5 + 3 = 8F7 = F6 + F5 = 8 + 5 = 13F8 = F7 + F6 = 13 + 8 = 21F9 = F8 + F7 = 21 + 13 = 34F10 = F9 + F8 = 34 + 21 = 55

Mithilfe analytischer Methoden aus der Theorie der Differenzengleichungen, aufdie wir im Rahmen dieses Buches nicht eingehen, kann man einen geschlossenenAusdruck zur Berechnung von Fn herleiten:

Fn =1√5(φn − φ′n) (3.8)

Dabei istφ = 1

2(1 +

√5) = 1, 6180339 . . .

φ′ = 12(1−

√5) = −0, 6180339 . . .

Es gilt sogar:23

Fn = round

(1√5φn

)Die Anzahl der Kaninchenpaare Fn wachst also exponentiell in der Anzahl derMonate n.

Die Zahl φ stellt den Goldenen Schnitt dar. Ein geometrisches Verhaltnis vonGoldener

Schnitt

22 Es ist ublich bei der Fibonacci-Funktion die eher bei Folgen ubliche Schreibweise Fn

anstelle der Funktionsschreibweise F (n) zu verwenden.23 round ist die bekannte Rundungsfunktion.

Zahlenmengen 133

Großen in Kunst- oder Bauwerken galt von alters her (bei Euklid; in der Renais-sance ”gottliche Proportion“) als asthetisch, falls es durch diese Zahl ausgedrucktwerden konnte.24

Die Fibonacci-Zahlen konnen auch durch fortgesetzte Multiplikation der Matrix(F0 F1

F1 F2

)=

(0 11 1

)

berechnet werden. Dazu erklaren wir zunachst, wie zwei 2× 2-Matrizen mitein-ander multipliziert werden:(

a bc d

)·(

e fg h

)=

(ae + bg af + bhce + dg cf + dh

)(3.9)

Es gilt nun fur alle n ≥ 1(Fn−1 Fn

Fn Fn+1

)=

(F0 F1

F1 F2

)n

=

(0 11 1

)n

Wir beweisen dies durch vollstandige Induktion uber n:

Induktionsanfang: Fur n = 1 gilt:

(F1−1 F1

F1 F1+1

)=

(F0 F1

F1 F2

)1

=

(0 11 1

)

Induktionsschritt: Es gilt

(0 11 1

)n+1

=

(0 11 1

)n

·(

0 11 1

)

=

(Fn−1 Fn

Fn Fn+1

)·(

0 11 1

)wegen Induktionsvoraussetzung

=

(Fn Fn−1 + Fn

Fn+1 Fn + Fn+1

)wegen (3.9)

=

(Fn Fn+1

Fn+1 Fn+

)wegen (3.7)

24 Eine Strecke AB wird durch einen Teilpunkt C gemaß dem Goldenen Schnitt geteilt, fallsgilt |AC|

|CB| = |CB||AB| . Dabei bedeutet |XY | die Lange der Strecke XY . Wenn man |AC| = 1

und |CB| = x setzt, dann wird das Streckenverhaltnis durch 1x = x

1+x , umgeformt durchx2−x−1 = 0 ausgedruckt. Losen wir diese Gleichung auf, dann erhalten wir als Losungenφ und φ′.

134 Ackermannfunktion

Ubungsaufgaben

3.6 Zeigen Sie, dass fur die Folge der Fibonacci-Zahlen folgende Gleichungengelten:

(i) ∀n ∈ N:∑n

i=1 F2i−1 = F2n,

(ii) ∀n ∈ N0:∑n

i=0 F2i = F2n+1 − 1,

(iii)∀n ∈ N: 1 +∑n

i=1 Fi = Fn+2,

(iv) ∀n ∈ N: Fn+1Fn−1 − F 2n = (−1)n.

3.4 Ackermannfunktion

Als weitere Beispiele zu rekursiv definierten Funktionen betrachten wir dieAckermannfunktion und Varianten davon. Die Ackermannfunktion ist vongroßer Bedeutung in der Berechenbarkeitstheorie (siehe Kapitel 4.3). Sie ist eineFunktion, die mit Zahlschleifen nicht berechnet werden kann, weil sie schnel-ler als alle Funktionen wachst, die mit Zahlschleifen berechnet werden konnen.Einen Eindruck dieses Wachstums geben die folgenden Betrachtungen.

Definition 3.1 Die Ackermannfunktion A : N0 × N0 → N0 ist definiert durchAckermann-

funktion

A(x, y) =

⎧⎪⎨⎪⎩

y + 1, x = 0

A(x− 1, 1), x = 0 ∧ y = 0

A(x− 1, A(x, y − 1)), sonst

Ubungsaufgaben

3.7 Berechnen Sie, um einen ersten Eindruck von dieser Funktion zu bekom-men, A(3, 3)! �

Folgerung 3.1 Fur alle n ≥ 0 gilt: a) A(1, n) = n + 2, b) A(2, n) = 2n + 3,

c) A(3, n) = 2n+3 − 3, d) A(4, n) = 22...2︸︷︷︸

n+3 Zweien

−3. �

Zahlenmengen 135

Ubungsaufgaben

3.8 Beweisen Sie Folgerung 3.1! �

Wir definieren nun die Familie {Ai }i≥0 von Funktionen Ai : N0 → N0 rekursivwie folgt:

A0(x) =

⎧⎪⎨⎪⎩

1, x = 0

2, x = 1

x + 2, sonst

An+1(x) = Axn(1) = An(An(. . . An︸︷︷︸

x-mal

(1) . . .))

Und mithilfe dieser Funktionen legen wir die Funktion

ack : N0 → N0

fest:

ack(x) = Ax(x) (3.10)

Gemaß diesen Definitionen gilt z.B.:

ack(0) = A0(0) = 1

ack(1) = A1(1) = A10(1) = 2

ack(2) = A2(2) = A21(1) = A1(A1(1)) = A1(2)

= A20(1) = A0(A0(1)) = A0(2) = 2 + 2 = 4

ack(3) = A3(3) = A32(1) = A2(A2(A2(1))) = A2(A2(2)) = A2(4)

= A41(1) = A1(A1(A1(A1(1)))) = A1(A1(A1(2))) = A1(A1(4))

= A1(A1(4)) = A1(A40(1)) = A1(A0(A0(A0(A0(1)))))

= A1(A0(A0(A0(2)))) = A1(A0(A0(4))) = A1(A0(6))

= A1(8) = . . .

...= 16

Zur Berechnung von ack(4) bestimmen wir zunachst (1) A2(x) und dann (2)A3(x).

Zu (1): Es gilt:

A2(x) = 2x fur alle x ∈ N0 (3.11)

136 Ackermannfunktion

Wir beweisen dies mit vollstandiger Induktion:

Induktionsanfang: Es gilt: A2(0) = A01(1) = 1 = 20. Fur x = 0 stimmt also die

Behauptung.


A2(x + 1) = Ax+11 (1)

= A1(Ax1(1))

= A1(A2(x))

= A1(2x) nach Induktionsvoraussetzung

= A2x

0 (1)

= A0(A0(. . . A0(A0︸︷︷︸2x-mal

(1)) . . .))

= A0(A0(. . . A0︸︷︷︸(2x−1)-mal

(2) . . .))

= 2 + 2 + . . . + 2︸︷︷︸2x-mal

= 2 · 2x = 2x+1

womit der Induktionsschritt vollzogen ist.

Zu (2): Die x-mal iterierte Zweierpotenz ist die Funktion iter 2 : N0 → N0

definiert durch

iter 2(0) = 1

iter 2(n + 1) = 2iter2(n), n ≥ 1

Es gilt also z.B.

iter 2(1) = 2iter2(0) = 21 = 2 = 2 (3.12)

iter 2(2) = 2iter2(1) = 22 = 22 = 4 (3.13)

iter 2(3) = 2iter2(2) = 24 = 222

= 16 (3.14)

iter 2(4) = 2iter2(3) = 216 = 2222

= 65 536 (3.15)

iter 2(5) = 2iter2(4) = 265 536 = 22222

= . . . (3.16)

Man erkennt, dass iter 2(x) die x-mal iterierte 2er-Potenz ist.

Wir beweisen nun mit vollstandiger Induktion, dass gilt

A3(x) = iter 2(x) (3.17)

Induktionsanfang: Es gilt: A3(0) = A02(1) = 1 = iter 2(0). Fur x = 0 stimmt

also die Behauptung.

Zahlenmengen 137


A3(x + 1) = Ax+12 (1)

= A2(Ax2(1))

= A2(A3(x))

= A2(iter 2(x)) nach Induktionsvoraussetzung

= 2iter2(x) wegen (3.11)= iter 2(x + 1) wegen der Definition von iter 2

womit der Induktionsschritt vollzogen ist.

Nun konnen wir ack(4) berechnen:

ack(4) = A4(4)

= A43(1)

= A33(A3(1))

= A33(2) wegen (3.17) und (3.12)

= A23(A3(2))

= A23(4)) wegen (3.17) und (3.13)

= A3(A3(4))

= A3(65536) wegen (3.17) und (3.15)= iter 2(65536)

= 222...2

65536-mal iterierte Zweierpotenz

Man schatzt die Anzahl der Atome im ”bekannten“ Universum auf etwa 2350,im Vergleich zu ack(4) eine sehr kleine Zahl. Die Ackermannfunktion hat einimmenses Wachstumsverhalten. Man kann sogar zeigen, dass die Ackermann-funktion starker wachst als Funktionen, die mit Zahlschleifen berechnet wer-den konnen. Bei Zahlschleifen liegt die Anzahl der Schleifendurchlaufe vorAusfuhrung der Schleife fest, d.h. die Schleifenbedingung kann – im Unterschiedzu Bedingungsschleifen – wahrend der Schleifenausfuhrung nicht verandert wer-den.

3.5 Abzahlbarkeit von Mengen

Die Menge der naturlichen Zahlen ist ja gerade zum Abzahlen geschaffen wor-den. Insofern erscheint es als ”naturlich“ diese Menge als Referenzmenge furabzahlbare Mengen zu wahlen.

138 Abzahlbarkeit

• den Begriff der Abzahlbarkeit und seine grundlegenden Eigenschaften er-klaren konnen,

• die Abzahlbarkeit von Mengen beweisen konnen,

• das Prinzip der Diagonalisierung verstehen und anwenden konnen.

3.5.1 Definitionen und grundlegende Eigenschaften

Wir wollen eine Menge abzahlbar nennen, falls ihre Elemente eindeutig mitnaturlichen Zahlen nummeriert werden konnen.

Definition 3.2 a) Eine Menge M heißt abzahlbar genau dann, wenn sie endlichAbzahlbarkeit

ist oder wenn |M | = |N0| gilt.

b) Ist eine Menge nicht abzahlbar, dann nennen wir sie uberabzahlbar. �Uberabzahlbar-

keitEine unendliche abzahlbare Menge M ist gleichmachtig zur Menge der naturli-chen Zahlen, denn jedem Element aus M kann genau eine naturliche Zahl undjeder naturlichen Zahl kann genau ein Element aus M zugeordnet werden. Istf : M → N0 die Abzahlung mit f(m) = i, dann schreiben wir auch mi. DieElemente aus M besitzen eine eindeutige Nummer, konnen also abgezahlt wer-den: m0, m1, m2, . . .

Folgerung 3.2 A und B seien Mengen.

a) Ist A ⊆ B und ist B abzahlbar, dann ist auch A abzahlbar: Jede Teilmengeeiner abzahlbaren Menge ist abzahlbar.

b) Ist A ⊆ B und ist A uberabzahlbar, dann ist auch B uberabzahlbar: JedeObermenge einer nicht abzahlbaren Menge ist nicht abzahlbar. �

3.5.2 Beispiele und Diagonalisierung

Beispiel 3.5 a) Aus den Beispielen 2.18 (Seite 110) und 2.19 (Seite 114) wis-sen wir, dass das kartesische Produkt Nk

0 fur jedes k ∈ N, die Menge Z derganzen Zahlen und die Menge Q der rationalen Zahlen abzahlbar sind, da siegleichmachtig zur Menge der naturlichen Zahlen sind, bzw. dass die Menge R

der reellen Zahlen, jedes Intervall von reellen Zahlen sowie die PotenzmengeP(N) der naturlichen Zahlen uberabzahlbar sind, da sie machtiger als die Mengeder naturlichen Zahlen sind.

b) Die Menge NN = {ϕ : N → N | ϕ total} der totalen Funktionen der Mengeder naturlichen Zahlen in sich ist uberabzahlbar.

Wir nehmen an, dass NN abzahlbar ist, d.h. es gibt eine bijektive Abbildungf : NN → N, die NN abzahlt. ϕ1, ϕ2, ϕ3 . . . sei die durch f festgelegte Abzahlungvon NN. N ist abzahlbar, und x1, x2, x3 . . . sei eine solche Abzahlung. Mit denbeiden Abzahlungen konnen wir folgende Matrix betrachten:


Zahlenmengen 139

x1 x2 x3 . . . xj . . .ϕ1 ϕ1(x1) ϕ1(x2) ϕ1(x3) . . . ϕ 1(xj) . . .ϕ2 ϕ2(x1) ϕ2(x2) ϕ2(x3) . . . ϕ 2(xj) . . .ϕ3 ϕ3(x1) ϕ3(x2) ϕ3(x3) . . . ϕ 3(xj) . . ....

......

......

......

ϕi ϕi(x1) ϕi(x2) ϕi(x3) . . . ϕ i(xj) . . ....

......

......

......

Da alle Funktionen ϕi total sind, ist diese Tabelle komplett ausgefullt.

Wir definieren mithilfe der Diagonalen dieser Matrix die Funktion ϕD wie folgt: Diagonalisierung

ϕD(xk) = ϕk(xk) + 1 (3.18)

Die Funktion ϕD ist so konstruiert, dass sie sich mindestens fur ein Argument,namlich jeweils fur das entsprechende Element in der Diagonale der Matrix, vonjeder Funktion ϕk unterscheidet. Das fuhrt im Folgenden zu einer widerspruchli-chen Aussage.

Zunachst stellen wir fest, dass ϕD eine totale Funktion ist, d.h. es muss ϕD ∈NN sein. Das bedeutet aber, dass ϕD in der Abzahlung ϕ1, ϕ2, ϕ3, . . . von NN

vorkommen muss. Damit muss es eine Nummer s geben mit ϕD = ϕs. Fur dieseBeziehungen gilt

ϕs(xs) = ϕD(xs) = ϕs(xs) + 1

was offensichtlich einen Widerspruch darstellt. Unsere Annahme muss alsofalsch sein. Damit haben wir bewiesen, dass NN uberabzahlbar ist. �

Das Beweisprinzip, das wir im letzten Beispiel angewendet haben, heißt Diago-nalisierung; es geht auf Cantor zuruck.

Ubungsaufgaben

3.9 Wir wissen bereits, dass die Potenzmenge P(N) der naturlichen Zah-len uberabzahlbar ist, weil wir in Beispiel 2.19 gezeigt haben, dass siegleichmachtig zur Menge R der reellen Zahlen ist. Zeigen Sie mithilfe ei-ner Diagonalisierung, dass P(N) uberabzahlbar ist! �

3.5.3 Abschlusseigenschaften abzahlbarer Mengen

Wir wollen nun die Abschlusseigenschaften der Klasse der abzahlbaren Mengengegenuber den gangigen Mengenverknupfungen betrachten. Dass das kartesische

140 Abzahlbarkeit

1 2 3 4 . . .A1 a11 a12 a13 a14 . . .

↙ ↙ ↙A2 a21 a22 a23 . . .

↙ ↙A3 a31 a32 . . .

↙A4 a41 . . .

...

Abb. 3: Abzahlung von⋃

i∈I Ai

Produkt von endlichen vielen abzahlbaren Mengen abzahlbar ist, folgt unmittel-bar aus der Tatsache, dass das kartesische Produkt Nk

0 fur jedes k ∈ N abzahlbarist.

Satz 3.2 a) Es seien A und B abzahlbare Mengen, dann sind auch (1) A ∩ B,(2) A−B und (3) A ∪B abzahlbar.

b) Es sei I eine unendliche, abzahlbare (Index-) Menge, und die Mengen Ai,i ∈ I , seien ebenfalls abzahlbar, dann ist auch

⋃i∈I Ai abzahlbar.

Beweis a) (1) und (2) folgen unmittelbar aus den Eigenschaften A ∩ B ⊆ Abzw. A−B ⊆ A mithilfe Folgerung 3.2 a). Zu (3) gehen wir von einer Bijektionf : A → N0 und einer Bijektion g : B → N aus. Damit definieren wir h :A ∪B → Z durch

h(x) =

{f(x), x ∈ A

−g(x), x ∈ B − A

h ist somit eine totale, injektive Funktion von A∪B nach Z, womit |A∪B| ≤ |Z|und damit die Azahlbarkeit von A ∪B folgt.

b) Da die Menge I unendlich und abzahlbar ist, konnen wir als Indexmengeauch die Menge N wahlen. Die Mengen Ai sind abzahlbar, so konnen wir ihreElemente entsprechend der entsprechenden Abzahlung wie folgt aufschreiben:ai1, ai2, ai3, . . . etwa realisiert durch die Bijektion ϕi : N → Ai definiert durchϕi(j) = aij . Wir nehmen uns die Matrix 2 von Seite 111 zur Hilfe und tra-gen die Elemente der Mengen Ai gemaß den Funktionswerten ϕi(j) in diesesSchema ein, womit sich die Matrix in Abbildung 3 ergibt. Die Abzahlung in die-ser Tabelle veranschaulicht so die Bijektion ϕ : N →

⋃i∈I Ai definiert durch

ϕ(aij) = c2(i, j). �

Zahlenmengen 141


Die Menge der naturlichen Zahlen ist die Referenzmenge fur die Abzahlbarkeitvon Mengen. Jede Menge, die gleichmachtig zur Menge der naturlichen Zahlen(oder zu einer Teilmenge naturlicher Zahlen) ist, d.h. die bijektiv auf die Mengeder naturlichen Zahlen (bzw. auf eine Teilmenge naturlicher Zahlen) abgebil-det werden kann, ist abzahlbar. Die Elemente einer abzahlbaren Menge konneneineindeutig nummeriert werden. Mithilfe einer Diagonalisierung kann gezeigtwerden, dass eine Menge nicht abzahlbar ist.

3.6 Die Menge der ganzen Zahlen

Die Subtraktion x− y ist in N0 nur dann moglich ist, falls x ≥ y ist. Wir werdennun eine neue Zahlenmenge einfuhren, in der wir sowohl die Menge der naturli-chen Zahlen und das in dieser Menge mogliche Rechnen ”wiederfinden“ werden,in der wir aber auch die Subtraktion ohne Einschrankung durchfuhren konnen.Des Weiteren werden wir die Rechenregeln fur diese neuen Zahlen auflisten.


• verstehen, wie die ganzen Zahlen und das Rechnen mit diesen mithilfe einergeeigneten Aquivalenzrelation auf den naturlichen Zahlen eingefuhrt werdenkonnen,

• die Rechenregeln fur ganze Zahlen kennen und anwenden konnen.

3.6.1 Konstruktion der ganzen Zahlen

Wir werden die Menge der ganzen Zahlen Z mithilfe einer Aquivalenzrelationuber Paaren von naturlichen Zahlen konstruieren.

Die Relation Z ⊆ (N× N)× (N× N) sei definiert durch:

(a, b)Z (c, d) genau dann, wenn a + d = b + c (3.19)

Die Relation Z verwendet nur bekannte Begriffe: naturliche Zahlen bzw. Paarevon naturlichen Zahlen sowie die Addition von naturlichen Zahlen.

Wir zeigen nun, dass Z eine Aquivalenzrelation ist:

Z ist reflexiv: Fur alle (a, b) ∈ N×N gilt a+ b = b+ a, woraus mit (3.19) folgt,dass fur alle (a, b) ∈ N× N gilt: (a, b)Z (a, b).

Z ist symmetrisch: Sei (a, b)Z (c, d), d.h. a + d = b + c. Mit den bekanntenRechenregeln folgt daraus, dass c + b = d + a gilt, und hieraus mit (3.19), dass(c, d)Z (a, b) gilt.

142 Ganze Zahlen

Z ist transititv: Sei (a, b)Z (c, d) und (c, d)Z (e, f), d.h. es ist a+d = b+ c undc + f = d + e. Hieraus folgt, dass (a + d) + (c + f) = (b + c) + (d + e) ist, unddaraus folgt, dass a + f = b + e ist. Mit (3.19) folgt (a, b)Z (e, f).

Wir wollen nun die Aquivalenzklassen von Z bestimmen. Es gilt beispielsweise

[(7, 3)]Z = { (7, 3), (5, 1), (6, 2), (8, 4), . . . }[(2, 2)]Z = { (2, 2), (1, 1), (3, 3), (4, 4), . . . }[(1, 3)]Z = { (2, 4), (3, 5), (4, 6), (5, 7), . . . }

Wir wollen als Reprasentant jeder Aquivalenzklasse das Paar wahlen, welchesKonstruktion

von ZZZ die Zahl 1 mindestens in einer Komponente enthalt. Dann gilt allgemein fura, b ∈ N mit a, b ≥ 2

[(a, 1)]Z = { (c, d) | c = d + (a− 1) } (3.20)[(1, 1)]Z = { (x, x) |x ∈ N } (3.21)[(1, b)]Z = { (c, d) | c + (b− 1) = d } (3.22)

was sich leicht mithilfe von (3.19) nachrechnen lasst. Dabei ist mit a − 1 derVorganger von a und mit b − 1 der Vorganger von b gemeint (da a, b ≥ 2 ist,existieren diese Vorganger).

Auf der Menge der Aquivalenzklassen, die wir mit (N × N)/Z bezeichnen,Rechen-

operationen

fur ganze Zahlenfuhren wir Rechenoperationen, namlich die Addition⊕, die Subtraktion� sowiedie Multiplikation # ein:

[(a, b)]Z ⊕ [(c, d)]Z = [(a + c, b + d)]Z (3.23)[(a, b)]Z � [(c, d)]Z = [(a + d, b + c)]Z (3.24)[(a, b)]Z # [(c, d)]Z = [(ac + bd, bc + ad)]Z (3.25)

Es sei darauf hingewiesen, dass diese Rechenoperationen ausschließlich mit na-turlichen Zahlen und den dafur vollstandig definierten Operationen Addition +und Multiplikation · definiert sind.

Bevor wir die neu definierten Rechenoperationen weiter betrachten, wollen wirzur Vereinfachung den Aquivalenzklassen Namen geben. Da a, b ∈ N mit a, b ≥2 ist, gilt a− 1, b− 1 ∈ N. Damit fuhren wir folgende Bezeichnungen ein:

a− 1 = [(a, 1)]Z

0 = [(1, 1)]Z (3.26)b− 1 = [(1, b)]Z

Es ist also z.B. 4 = [(5, 1)]Z und 2 = [(1, 3)]Z .

Wir wollen nun diese Bezeichner fur die Aquivalenzklassen ganze Zahlen nen-Ganze Zahlen

nen und die Menge der ganzen Zahlen mit Z bezeichnen. Es ist also

Z = { . . . , 3, 2, 1, 0, 1, 2, 3, . . . }

Zahlenmengen 143

Wir haben mithilfe der naturlichen Zahlen, mit den auf diesen vollstandig defi-nierten Operationen + und · und mit der Aquivalenzrelation Z die ZahlenmengeZ mit vollstandig auf ihr definierten Operationen ⊕, � und # geschaffen. Indieser neuen Rechenstruktur wollen wir ein paar Beispiele rechnen:

[(7, 3)]Z ⊕ [(9, 2)]Z = [(16, 5)]Z bzw. 4 ⊕ 7 = 11[(7, 3)]Z � [(9, 2)]Z = [(9, 12)]Z bzw. 4 � 7 = 3[(7, 3)]Z ⊕ [(3, 7)]Z = [(10, 10)]Z bzw. 4 ⊕ 4 = 0[(7, 3)]Z # [(9, 2)]Z = [(69, 41)]Z bzw. 4 # 7 = 28[(7, 3)]Z # [(3, 7)]Z = [(42, 58)]Z bzw. 4 # 4 = 16

Nun, spatestens an diesen Beispielen bemerken wir, dass es sich um die unsbekannten ganzen Zahlen und fur diese definierte Rechenoperationen Addition,Subtraktion und Multiplikation handelt. Wenn wir x anstelle von x, −x anstellevon x notieren und diese Zahlen positive ganze Zahlen bzw. negative ganze Zah-len nennen, und außerdem + fur ⊕, − fur � sowie · fur # schreiben, benutzenwir die uns aus der Schule vertrauten Schreibweisen und Bezeichnungen fur dasRechnen mit ganzen Zahlen.

Wir konnen zudem feststellen, dass die naturlichen Zahlen den positiven Zah- Abgeschlossen-

heit von

Addition,

Multiplikation

und

Subtraktion

len entsprechen und dass wir den Zahlenraum der naturlichen Zahlen um die 0und die negativen ganzen Zahlen erweitert haben. In diesem Zahlenraum ist nun– im Gegensatz zu den naturlichen Zahlen – die Subtraktion uneingeschranktausfuhrbar.

Dass die ganzen Zahlen eine Erweiterung der naturlichen Zahlen darstellen, d.h. ZZZ als

Erweiterung

von NNNdass die positiven ganzen Zahlen mit der auf ihnen definierten Addition undMultiplikation den naturlichen Zahlen mit ihrer Addition und Multiplikation ent-sprechen, also – mathematisch gesprochen – die Strukturgleichheit dieser beidenRechenstrukturen gilt, kann wieder mithilfe eines Isomorphismus beschriebenwerden. Dazu sei

Z+ = { [(a, 1)]Z | a ∈ N, a ≥ 1 }die Menge der positiven ganzen Zahlen einschließlich der Null (dargestellt in derursprunglichen Notation (3.26) als Aquivalenzklassen, um sie von der Notationder naturlichen Zahlen zu unterscheiden). Dann gelten fur die Abbildung

ϕ : Z+ → N0

definiert durch

ϕ([(a, 1)]Z) = a− 1 (3.27)

die Eigenschaften: ϕ ist bijektiv und genugt den Strukturgleichungen

ϕ ([(a, 1)]Z ⊕ [(b, 1)]Z) = ϕ ([(a, 1)]Z) + ϕ ([(b, 1)]Z) (3.28)

sowie

ϕ ([(a, 1)]Z ⊗ [(b, 1)]Z) = ϕ ([(a, 1)]Z) · ϕ ([(b, 1)]Z) (3.29)

144 Ganze Zahlen

Ubungsaufgaben

3.10 Beweisen Sie, dass die oben definierte Abbildung ϕ bijektiv ist und dasssie die Strukturgleichungen (3.28) und (3.29) erfullt! �

Ein Isomorphismus kann als eineindeutige Umbenennung der Elemente einerIsomorphismus

Rechenstruktur mit Elementen einer anderen Rechenstruktur aufgefasst werden,wobei diese Umbenennung mit den Rechenoperationen vertraglich sein muss.Diese Vertraglichkeit wird durch die Strukturgleichungen fur die einzelnen Ope-rationen beschrieben. Bis auf die Benennung der Elemente handelt es sich quasium dieselben Rechenstrukturen.

In unserem Beispiel werden die positiven ganzen Zahlen, d.h. die Aquivalenz-klassen [a, 1]Z von Z mit a ≥ 1 eineindeutig den naturlichen Zahlen a − 1zugeordnet, so dass die Umbenennung der Summe (des Produktes) von zweiganzen Zahlen gleich der Summe (Produkte) der Umbenennungen, d.h. gleichder Summe (dem Produkt) der entsprechenden naturlichen Zahlen, ist.

3.6.2 Rechenregeln in Z

Neben den Regeln A1, A2, A3, M1, M2 und M3 (siehe Abschnitt 3.1.3), die inZ ebenfalls gelten, gilt fur x, y ∈ Z noch:

(A4) Additives Inverses: x + y = 0. Dabei gilt y = −x, und −x heißt die zu xbezuglich der Addition inverse oder die zu x negative Zahl.25Additives

InversesDie Definition der Relation ≤ kann ebenfalls ubernommen werden: ≤⊆ Z × Z

definiert durch x ≤ y genau dann, wenn ∃ d ∈ N0 : x + d = y definiert einetotale Ordnung auf Z.

Fur diese Ordnung gilt ebenfalls die Regel O1, wahrend bei der Regel O2 unter-Monotonieregeln

schieden werden muss, ob der Faktor positiv oder negativ ist:

(O2+) ∀x, y, z ∈ Z mit x ≤ y und z ≥ 1 gilt xz ≤ yz,

(O2−) ∀x, y, z ∈ Z mit x ≤ y und z ≤ −1 gilt xz ≥ yz.

Der Absolutbetrag einer ganzen Zahl ist festgelegt durch die FunktionAbsolutbetrag

| | : Z → N0

25 Formal betrachtet hat das Vorzeichen ”−“ von x eine andere Bedeutung als der Opera-tor ”−“ in einer Subtraktion a − b zweier ganzer Zahlen a und b. Dies haben wir beiEinfuhrung der ganzen Zahlen durch die Notationen x bzw. � auch ganz bewusst unter-schieden. Es gilt allerdings a + (−b) = a − b oder genauer a ⊕ b = a � b, weswegenwir beim Rechnen nicht zwischen dem Operator ”−“ und dem Vorzeichen ”−“ strengunterscheiden mussen.

Zahlenmengen 145

definiert durch

|x| ={

x, falls x ≥ 0

−x, falls x < 0

Fur den Absolutbetrag gelten die folgenden Regeln:

(ABS1) Dreiecksungleichung: ∀x, y ∈ Z : |x + y| ≤ |x|+ |y|, Dreiecks-

ungleichung(ABS2) ∀x, y ∈ Z : |x− y| ≤ |x|+ |y|,(ABS3) ∀x, y ∈ Z : ||x| − |y|| ≤| x| − |y|,(ABS4) ∀x, y ∈ Z : |xy| = |x||y|.


Die ganzen Zahlen konnen mithilfe einer Aquivalenzrelation uber Paare vonnaturlichen Zahlen eingefuhrt werden. Die in der Menge der ganzen Zahlen ab-geschlossenen Operationen Addition, Subtraktion und Multiplikation werden alsVerknupfungen der entsprechenden Aquivalenzklassen eingefuhrt. Dabei wer-den diese Operationen – auch die Subtraktion – alleine durch die Addition unddie Multiplikation naturlicher Zahlen definiert. Die Addition und die Multipli-kation auf den positiven ganzen Zahlen stimmt dabei mit der Addition und derMultiplikation der entsprechenden naturlichen Zahlen uberein. Insofern konnendie ganzen Zahlen als Erweiterung der naturlichen Zahlen betrachtet werden, inder nun auch die Subtraktion abgeschlossen ist. Diese Erweiterung kann mithilfedes Isomorphiebegriffs mathematisch beschrieben werden.

3.7 Die Menge der rationalen Zahlen

Wir haben im vorigen Kapitel die Rechenstruktur N erweitert zur RechenstrukturZ, in der auch die Subtraktion uneingeschrankt ausfuhrbar ist. Die beschrankteAusfuhrung der Division bleibt aber weiterhin bestehen: Die Division x : y furzwei Zahlen x ∈ Z und y ∈ Z − {0} ist nur ausfuhrbar, falls es ein z ∈ Z gibtmit x = yz. So existiert etwa der Quotient 4 : 3 in Z nicht, da es keine ganzeZahl z gibt mit 4 = 3z. Das heißt: Nicht alle Gleichungen der Art ax = b mita, b ∈ Z mit a = 0 sind in Z losbar (sondern nur solche, bei denen a ein Teilervon b ist).

In diesem Kapitel werden wir eine neue Zahlenmenge, die Menge Q der ratio-nalen Zahlen, einfuhren, in der wir zum einen solche Gleichungen losen konnenund in der wir zum anderen die Menge der ganzen Zahlen und das in dieser Men-ge mogliche Rechnen erhalten, insofern Z zu Q erweitern. Auch fur Q werdenwir weitere Rechenregeln auflisten.

146 Rationale Zahlen


• verstehen, wie die rationalen Zahlen und das Rechnen mit diesen mithilfe ei-ner geeigneten Aquivalenzrelation auf den ganzen Zahlen eingefuhrt werdenkonnen,

• die Rechenregeln fur rationale Zahlen kennen und anwenden konnen.

3.7.1 Konstruktion der rationalen Zahlen

Analog zur Menge der ganzen Zahlen konstruieren wir die rationalen Zahlenebenfalls mithilfe einer Aquivalenzrelation: Die Relation

Q ⊆ (Z× (Z− {0})× (Z× Z− {0})

sei definiert durch:

(a, b)Q (c, d) genau dann, wenn ad = bc (3.30)

Die Relation Q verwendet nur bekannte Begriffe: ganze Zahlen bzw. Paare vonganzen Zahlen sowie die Multiplikation von ganzen Zahlen.

Der Beweis, dass Q eine Aquivalenzrelation ist, erfolgt analog dem Beweis imvorigen Kapitel, der zeigt, dass die Relation Z eine Aquivalenzrelation ist:

Q ist reflexiv: Fur alle (a, b) ∈ Z×Z−{0} gilt ab = ba, woraus mit (3.30) folgt,dass fur alle (a, b) ∈ Z× Z− {0} gilt: (a, b)Q (a, b).

Q ist symmetrisch: Sei (a, b)Q (c, d), d.h. ad = bc. Mit den bekannten Rechen-regeln folgt daraus, dass cb = da gilt, und hieraus mit (3.30), dass (c, d)Q (a, b)gilt.

Q ist transitiv: Sei (a, b)Q (c, d) und (c, d)Q (e, f), d.h. es ist ad = bc undcf = de. Hieraus folgt, dass adf = bcf = bde ist, und daraus folgt, da d = 0 ist,dass af = be ist. Mit (3.30) folgt (a, b)Q (e, f).

Die Aquivalenzklassen von Q sind fur x, y ∈ Z mit y = 0 gegeben durch:Konstruktion

von QQQ

[(x, y)]Q = { (qx, qy) | q ∈ Z− {0} } (3.31)

Auf der Menge Q = (Z × Z − {0})/Q der Aquivalenzklassen von Q, dieRechenoperatio-

nen fur rationale

Zahlenwir Menge der rationalen Zahlen nennen wollen, fuhren wir Rechenoperationenein:26

• Addition und Subtraktion: [(a, b)]Q ± [(c, d)]Q = [(ad± bc, bd)]Q

• Multiplikation: [(a, b)]Q · [(c, d)]Q = [(ac, bd)]Q

26 Dabei benutzen wir jetzt sofort die ublichen Notationen und nicht erst aus formalenGrunden, wie im vorigen Kapitel bei der Einfuhrung der ganzen Zahlen, neue Symbo-le.

Zahlenmengen 147

• Division: [(a, b)]Q : [(c, d)]Q = [(ad, bc)]Q

Diese (neuen) Rechenoperationen sind ausschließlich mit ganzen Zahlen und dendafur vollstandig definierten Operationen Addition, Subtraktion und Multiplika-tion definiert. Dabei stellen die Aquivalenzklassen [(x, y)]Q mit y = 1 genau dieganzen Zahlen dar. Auch hier kann man mithilfe eines Isomorphismus zeigen,dass die rationalen Zahlen als Erweiterung der ganzen Zahlen betrachtet werdenkonnen.

Fur die neuen Zahlen [(a, b)]Q mit a = 0 gilt wegen (3.31):

[(a, b)]Q · [(b, a)]Q = [(ab, ba)]Q = [(ab · 1, ab · 1)]Q = [(1, 1)]Q

[(b, a)]Q heißt das (multiplikative) Inverse zu [(a, b)]Q.

Weiterhin gilt fur alle Zahlen [(a, b)]Q, [(c, d)]Q ∈ Q mit c = 0:

([(a, b)]Q · [(c, d)]Q) : [(c, d)]Q = [(ac, bd)]Q : [(c, d)]Q

= [(acd, bdc)]Q

= [(cda, cdb)]Q

= [(a, b)]Q

In der Einleitung dieses Kapitels haben wir das Ziel formuliert, die ganzen Zah-len so zu erweitern, dass Gleichungen der Art ax = b fur a = 0 losbar sind. Derfolgende Satz besagt, dass dies in der Menge Q der rationalen Zahlen moglichist.

Satz 3.3 Fur alle Zahlen [(a, b)]Q, [(c, d)]Q ∈ Q mit a = 0 gibt es genau eine Losung von

ax = bax = bax = b in QQQZahl [(x, y)]Q ∈ Q mit [(a, b)]Q · [(x, y)]Q = [(c, d)]Q.

Beweis Wir setzen x = bc und y = ad, dann gilt wegen (3.31):

[(a, b)]Q · [(bc, ad)]Q = [(abc, abd)]Q = [(c, d)]Q

Somit ist die Gleichung [(a, b)]Q · [(x, y)]Q = [(c, d)]Q fur gegebene rationaleZahlen [(a, b)]Q und [(c, d)]Q mit a = 0 losbar.

Wir mussen noch die Eindeutigkeit der Losung x = bc und y = ad zeigen. Wirnehmen an, es gebe eine weitere Losung [(x′, y′)]Q. Es muss dann gelten

[(a, b)]Q · [(x, y)]Q = [(a, b)]Q · [(bc, ad)]Q = [(abc, abd)]Q = [(c, d)]Q

sowie[(a, b)]Q · [(x′, y′)]Q = [(ax′, by′)]Q = [(c, d)]Q

Es folgt, dass[(abc, abd)]Q = [(ax′, by′)]Q

sein muss und damit x′ = bc und y′ = ad, womit die Eindeutigkeit gezeigt ist.�

In der uns vertrauten Notation werden rationale Zahlen nicht als Paare [(a, b)]Q, Bruche

Zahler

Nennersondern als Bruche a

bdargestellt. Dabei heißt a der Zahler und b der Nenner des

Bruches ab.

148 Rationale Zahlen

3.7.2 Rechenregeln in Q

Die Rechenregeln A1 - 4 und M1 - 3 aus Z gelten analog auch in Q. Zudem giltwegen Satz 3.3 die RechenregelMultiplikatives

Inverses(M4) Multiplikatives Inverses: Zu jeder rationalen Zahl x = 0 existiert eine

rationale Zahl y mit xy = 1. Wir nennen x−1 = y das (multiplikative)Inverse von x.

Aus Satz 3.3 folgt zudem fur x = ab

mit a = 0: x−1 = ba.

Fur den Absolutbetrag gilt neben den Regeln ABS1 - 4 noch die Regel

(ABS5) |ab| = |a|

|b| .

Die Relation ≤⊆ Q×Q definiert durch

a

b≤ c

dgenau dann, wenn es

x

ygibt mit x ≥ 0, y ≥ 1 und

a

b+

x

y=

c

d

legt eine totale Ordnung auf Q fest. Fur diese Ordnung gelten die Regeln O1,O2+ und O2−.

Bereits in Beispiel 2.7 b) auf Seite 96 haben wir festgestellt, dass bezuglich die-ser Ordnung die Menge der rationalen Zahlen im Gegensatz zur Menge der gan-Dichtheit von QQQ

zen Zahlen und damit auch im Gegensatz zur Menge der naturlichen Zahlen dichtist, d.h. zwischen zwei verschiedenen rationalen Zahlen a und c mit a ≤ c exi-stiert immer eine von a und c verschiedene rationale Zahl b mit a ≤ b ≤ c. Furgegebene a und c braucht man nur b = a+c

2zu wahlen, denn es gilt:

a =a + a

2≤ a + c

2≤ c + c

2= c (3.32)


Die rationalen Zahlen konnen mithilfe einer Aquivalenzrelation uber Paare vonganzen Zahlen eingefuhrt werden. Die in der Menge der rationalen Zahlen ab-geschlossenen Operationen Addition, Subtraktion, Multiplikation und Divisionwerden als Verknupfungen der entsprechenden Aquivalenzklassen eingefuhrt.Dabei werden diese Operationen – auch die Division – alleine durch Additi-on, Subtraktion und Multiplikation ganzer Zahlen definiert. Addition, Subtrak-tion und Multiplikation auf den rationalen Zahlen mit Nenner 1 stimmen dabeimit Addition, Subtraktion und Multiplikation der entsprechenden ganzen Zah-len uberein. Insofern konnen die rationalen Zahlen als Erweiterung der ganzenZahlen betrachtet werden, in der nun auch die Division abgeschlossen ist. Die-se Erweiterung kann mithilfe des Isomorphiebegriffs mathematisch beschriebenwerden.

Zahlenmengen 149

3.8 Rechenstrukturen

Nachdem wir mit der Einfuhrung der Zahlenmengen N0, Z und Q schrittweiseimmer weitere Rechenmoglichkeiten und Rechenregeln kennen gelernt haben,wollen wir diese nun abstrakt betrachten und strukturieren. Ausgehend von derdurch die Peano-Axiome festgelegten Menge der naturlichen Zahlen haben wirdiese erweitert zu den ganzen Zahlen, um unbeschrankt subtrahieren zu konnen,und dann zu den rationalen Zahlen, um unbeschrankt dividieren zu konnen. Dierationalen Zahlen haben allerdings weitere Einschrankungen. So existiert z.B.in Q keine Losung der Gleichung x2 = 2, denn

√2 ist, wie wir wissen (siehe

Beispiel 1.39 auf Seite 69), keine rationale Zahl. Wir werden sehen, wie man Q

so zu einer Rechenstruktur erweitern kann, in der die Gleichung x2 = 2 losbar istund in der mit dieser Losung dann auch wie mit den rationalen Zahlen gerechnetwerden kann.


• die Rechenstrukturen Gruppe, Ringe und Korper erklaren und Beispieledafur angeben konnen,

• beispielhaft verstehen, wie Korper erweitert werden konnen,

• nachweisen konnen, dass solche Erweiterungen wieder Korper bilden.

3.8.1 Gruppen, Ringe, Korper

Wir bezeichnen im Folgenden die Menge von Objekten, mit denen gerechnetwerden soll, die sogenannte Tragermenge, mit M und die Rechenoperationen Tragermenge

auf dieser Menge allgemein mit ∗, ∗1 und ∗2. Rechenstrukturen (M, ∗) mit einer Einsortige,

zweisortige

RechenstrukturOperation nennen wir einsortig und Rechenstrukturen (M, ∗1, ∗2) mit zwei Ope-rationen zweisortig. Die grundsatzliche Anforderung an eine Rechenstruktur istdie Abgeschlossenheit, d.h. sind a, b ∈ M , dann muss auch a ∗ b ∈ M sein fur Abgeschlossenheit

jede Operation ∗.H = (M, ∗) heißt Halbgruppe genau dann, wenn die Operation ∗ assoziativ auf Halbgruppe

M ist, d.h. wenn fur alle a, b, c ∈M gilt

(a ∗ b) ∗ c = a ∗ (b ∗ c) (3.33)

Beispiele fur Halbgruppen sind (N, +) und (Z, ·).M = (M, ∗) heißt Monoid genau dann, wenn M eine Halbgruppe ist und ein Monoid

Element e ∈M existiert, so dass fur alle a ∈M gilt

a ∗ e = a = e ∗ a (3.34)

e heißt Einselement von M. Man kann zeigen, dass das Einselement eines Mo- Einselement

Neutrales

Elementnoids eindeutig ist. Ein Synonym fur Einselement ist neutrales Element.

150 Rechenstrukturen

Beispiele fur Monoide sind (N0, +) mit dem (additiven) Einselement 0 und (Z, ·)mit dem (multiplikativen) Einselement 1.

G = (M, ∗) heißt Gruppe genau dann, wenn G ein Monoid ist und fur alle a ∈MGruppe

ein b ∈M existiert mit der Eigenschaft

a ∗ b = e = b ∗ a (3.35)

b heißt invers zu a oder Inverses von a. Man kann zeigen, dass das InverseInverses

eindeutig ist. Fur das Inverse von a schreiben wir in der Regel a−1. Es gelten fure und alle a, b ∈M die Eigenschaften:

e−1 = e (3.36)(( a )−1 )−1

= a (3.37)

( a ∗ b )−1 = b−1 ∗ a−1 (3.38)

Ist die Operation ∗ kommutativ, d.h. gilt

a ∗ b = b ∗ a (3.39)

fur alle a, b ∈M , dann heißenH,M bzw. G kommutativ oder auch abelsch.

Beispiele fur kommutative Gruppen sind (Z, +) und (Q∗, ·) mit Q∗ = Q− {0}.

Ubungsaufgaben

3.11 (1) Sei M eine Menge. Zeigen Sie, dass die Rechenstrukturen (P(M),∪)sowie (P(M),∩) komutative Monoide, aber keine Gruppen bilden.

(2) Uberlegen Sie, dass die Menge der bijektiven Funktionen einer Mengein sich selbst mit der Komposition als Verknupfung eine im Allgemeinennicht kommutative Gruppe bildet! �

R = (M, ∗1, ∗2) heißt Ring genau dann, wennRing

• (M, ∗1) eine kommutative Gruppe bildet (deren Einselement bezeichnen wirmit e1),

• (M, ∗2) eine Halbgruppe bildet,

• die (Links- bzw. Rechts-) Distributivgesetze

a ∗2 ( b ∗1 c ) = ( a ∗2 b ) ∗1 ( a ∗2 c )

( a ∗1 b ) ∗2 c = ( a ∗2 c ) ∗1 ( b ∗2 c )(3.40)

fur alle a, b, c ∈M gelten.

Zahlenmengen 151

Ist ∗2 ebenfalls kommutativ, dann heißt R kommutativer Ring. Ist (M, ∗2) einMonoid, dann heißt R Ring mit Einselement (welches wir mit e2 bezeichnen).Bei kommutativen Ringen reicht ein Distributivgesetz aus, weil aus diesem mit-hilfe der Kommutativitat das andere gefolgert werden kann. Kommutativer

Ring

Ring mit

Einselement

Ein Beispiel fur einen kommutativen Ring mit Einselement ist die Menge derganzen Zahlen mit den Operationen Addition und Multiplikation: (Z, +, ·). DasEinselement der Addition ist die 0, das Einselement der Multiplikation ist die1. Da Z ein ”Prototyp“ fur Ringe ist, bezeichnet man auch im Allgemeinen dieOperation ∗1 als Additon und die Operation ∗2 als Multiplikation und notiertdiese mit + bzw. mit ·, und man schreibt im AllgemeinenR = (M, +, ·) anstellevon R = (M, ∗1, ∗2). Dementsprechend nennt man e1 das additive Einselementund e2 das multiplikative Einselement und notiert diese auch im Allgemeinen mit0 bzw. mit 1.

In Abschnitt 2.1.4 haben wir auf Z fur m ∈ N die Aquivalezrelation≡m betrach-tet. Diese partitioniert Z in m Restklassen [ i ]m:

[ i ]m = {x ∈ Z | x = k ·m + i, k ∈ Z} , 0 ≤ i ≤ m− 1 (3.41)

Wahlen wir als Reprasentanten die kleinsten positiven Reste 0, 1, . . . , m− 1 undfassen diese in der Menge

Zm = {0, 1, . . . , m− 1} (3.42)

zusammen und definieren darauf die Addition +m sowie die Multiplikation ·mdurch

[ i ]m +m [ j ]m = [ i + j ]m[ i ]m ·m [ j ]m = [ i · j ]m

(3.43)

so erhalten wir als neue Rechenstruktur (Zm, +m, ·m), den Restklassenring mo-dulo m. Dieser bildet wie Z einen kommutativen Ring mit Einselement. Bei Restklassenring

diesem schreibt man + anstelle von +m und · anstelle von ·m, falls aus demZusammenhang klar ist, dass in Zm gerechnet wird.

SeiR ein Ring. Existiert zu a ∈ R mit a = 0 ein b ∈ R mit b = 0 und a · b = 0,dann heißt a Nullteiler in R. So enthalt Z12 die Nullteiler 2, 3, 4, 6, 9, 10, denn Nullteiler

es gilt z.B. 2 · 6 = 0, 3 · 4 = 0, 4 · 9 = 0 und 6 · 10 = 0 in Z12. Besitzt ein Ringkeine Nullteiler, dann nennen wir ihn nullteilerfrei. Z und Z7 sind Beispiele furnullteilerfreie Ringe.

Einen nullerteilerfreien kommutativen Ring mit Einselement nennt man Inte-gritatsbereich. Z, Z7, Z11 und Z13 sind Beispiele fur Integritatsbereiche, Z4, Z12 Integritats-

bereichunbd Z20 sind keine Integritatsbereiche.

Die bezuglich der Multiplikation invertierbaren Elemente eines Rings mit Eins-element nennt man auch Einheiten. Man kann zeigen, dass a ∈ R eine Einheit Einheit

ist genau dann, wenn a kein Nullteiler von R ist. Die Einheiten eines Rings R


fasst man in der Menge R∗ zusammen. R∗ ist niemals leer, denn es gilt immer1 ∈ R∗. Man kann zeigen, dass R∗ fur jeden Ring R eine Gruppe, die so ge-nannte Einheitengruppe vonR, bildet.

Es gilt z.B.

Z∗ = {1,−1}Z∗

4 = {1, 3}Z∗

7 = {1, 2, 3, 4, 5, 6}Z∗

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

12 = {1, 5, 7, 11}Z∗

20 = {1, 3, 7, 9, 11, 13, 17, 19}

In Integritatsbereichen gilt die Kurzungsregel: Sei I ein Integritatsbereich undKurzungsregel

a, b, c ∈ I mit c = 0 und ac = bc, dann folgt a = b. Denn aus ac = bc folgt(a−b)c = 0. Wegen der Nullteilerfreiheit von I und weil c = 0 ist, muss a−b =0 und damit a = b sein. Wir konnen also in Integritatsbereichen beide Seiteneiner Gleichung durch denselben Faktor (ungleich Null) ”dividieren“, auch wenndieser Faktor nicht invertierbar ist. Liegt z.B. in Z die Gleichung 2a = 2b vor,dann folgt daraus auch in Z, dass a = b ist, obwohl wir nicht durch 2 dividierenkonnnen, denn in Z existiert kein multiplikatives Inverses zur 2.

K = (M, +, ·) bildet einen Korper genau dann, wennKorper

• (M, +, ·) einen kommutativen Ring mit Einselement bildet,

• (M − {0} , ·) eine Gruppe bildet.

Ein kommutativer Ring mit Einselement bildet also einen Korper genau dann,wenn bezuglich der Multiplikation alle Elemente außer der 0 invertierbar sind,wenn also K∗ = K − {0} gilt. Wegen der Kommutativitat braucht man beiKorpern von den beiden Distributivgesetzen (3.40) nur eines fordern.

Die Zahlenmengen Q, R und C sind ”Prototypen“ fur Korper. Man kann zeigen,dass endliche Integritatsbereiche immer Korper sind. Des Weiteren kann manzeigen, dass Zm nullteilerfrei, damit ein Integritatsbereich und damit ein Korperist, genau dann, wenn m eine Primzahl ist. Fur p ∈ P schreibt man anstelle vonZp auch Fp (oder auch GF(p)).

3.8.2 Kopererweiterungen

Fragen wir im Korper Q der rationalen Zahlen nach einer Losung der Gleichungx2 = 2, stellen wir fest, dass dort keine Losung existiert. Es stellt sich die Fra-ge nach der Erweiterung von Q um Elemente, so dass die Gleichung in demerweiterten Korper losbar ist.

Definition 3.3 Sei K ein Korper und α /∈ K. Bildet K(α) = { a + b · α | a, b ∈Erweiterungs-

korper K} ebenfalls einen Korper, dann heißtK(α) Erweiterungskorper vonK oder derum α adjungierte Korper. �

Zahlenmengen 153

Beispiel 3.6 Q(√

2) ist ein Erweiterungskorper von Q. Die neutralen Elementevon Q bleiben erhalten, denn 0 und 1 sind auch neutrale Elemente in R, also auchfur√

2.

Weiterhin gilt:√

2 ·√

2 = 2 ∈ Q. Deshalb kommen zu Q nur die Produkte b√

2und damit die Summen a+b

√2 fur a, b ∈ Q hinzu. Die Tragermenge von Q(

√2)

ist also: { a + b√

2 | a, b ∈ Q }.Es lasst sich leicht nachrechnen, dass Q(

√2) abgeschlossen gegenuber Addition

und Multiplikation ist:

(a + b√

2) + (c + d√

2) = (a + c) + (b + d)√

2 ∈ Q(√

2) (3.44)

sowie

(a + b√

2) · (c + d√

2) = (ac + 2bd) + (ad + bc)√

2 ∈ Q(√

2) (3.45)

Wir mussen noch zeigen, dass zu jedem Element aus dieser Menge sowohl dasadditive als auch das multiplikative Inverse ebenfalls Elemente der Menge sind.Dann wissen wir, dass Q(

√2) einen Korper bildet, da alle anderen Axiome gel-

ten, weil Q und R Korper sind.

Das additive Inverse zu a + b√

2 ist offensichtlich

−(a + b√

2) = (−a) + (−b)√

2 = −a− b√

2 ∈ Q(√

2) (3.46)

Wir zeigen noch die Existenz des multiplikativen Inversen: c+ d√

2 ist invers zua + b

√2 fur a, b ∈ Q mit b = 0, falls (a + b

√2) · (c + d

√2) = 1 ist. Dies ist der

Fall, fallsac + bc

√2 + ad

√2 + 2bd = 1

ist, und dies gilt, falls die Gleichungen

ac + 2bd = 1 (3.47)bc + ad = 0 (3.48)

gelten. Wir losen Gleichung (3.48) nach c auf:

c = −ad

b(3.49)

Wir setzen diesen Term fur c in Gleichung (3.47) ein und erhalten

−a2d

b+ 2bd =

2b2 − a2

bd = 1

woraus

d =b

2b2 − a2(3.50)


folgt. Einsetzen von (3.50) in (3.49) liefert

c = − a

2b2 − a2(3.51)

Aus (3.51) und (3.50) folgt, dass

− a

2b2 − a2+

b

2b2 − a2

√2

das multiplikative Inverse zu a+b√

2 ist. Diese Zahlen existieren fur alle a, b ∈ Q

mit b = 0, denn die Nenner werden genau dann 0, wenn b2 = 2a2 ist, und dieseGleichung ist fur kein a, b ∈ Q mit b = 0 losbar. Es gilt also(

a + b√

2)−1

= − a

2b2 − a2+

b

2b2 − a2

√2 (3.52)

fur alle a, b ∈ Q mit b = 0.

Der Fall b = 0 ist uninteressant, da dann a + b√

2 = a ist, und a = 0 ist alsrationale Zahl invertierbar. �

Ubungsaufgaben

3.12 Verifizieren Sie, dass die obigen Uberlegungen unabhangig von√

2 sind,dass sie also fur alle Korpererweiterungen

Q(√

α) ={a + b

√α | a, b ∈ Q

}mit α ∈ Q und

√α /∈ Q gleichermaßen angewendet werden konnen! �

Wir konnen die Korpererweiterung Q(√

α) auch ohne√

α darstellen, namlichdurch die Rechenstruktur

(Q×Q, +α , ·α)

wobei die Addition + definiert ist durch (siehe (3.44))

(a, b) +α (c, d) = (a + c, b + d)

und die Multiplikation durch (siehe (3.45))

(a, b) ·α (c, d) = (ac + αbd, ad + bc)

Die Abbildung ϕ : Q(√

α) → Q×Q definiert durch

ϕ(a + b√

α) = (a, b)

ist ein Isomorphismus.

Zahlenmengen 155

Ubungsaufgaben

3.13 Beweisen Sie diese Aussage! �

Es lasst sich leicht verifizieren, dass ϕ total, injektiv und surjektiv, also bijektivist. Wir zeigen noch, dass ϕ die Strukturgleichungen bezuglich den Additions-und den Multiplikationsoperationen besitzt:

ϕ((a + b√

α) + (c + d√

α)) = ϕ((a + c) + (b + d)√

α)

= (a + c, b + d)

= (a, b) +α (c, d)

= ϕ(a + b√

α) +α ϕ(c + d√

α)

ϕ((a + b√

α) · (c + d√

α)) = ϕ((ac + αbd) + (ad + bc)√

α)

= (ac + αbd, ad + bc)

= (a, b) ·α (c, d)

= ϕ(a + b√

α) ·α ϕ(c + d√

α)

Aus den obigen Uberlegungen folgt zudem, dass −α(a, b) = (−a,−b) und

(a, b)−1α =

(− a

αb2 − a2,

b

αb2 − a2

)

ist.

Die Strukturen (Q(√

α), +, ·) und (Q × Q, +α , ·α) sind also identisch (bis aufdie Bezeichnung der Elemente). Mithilfe der totalen Injektion φ : Q → Q × Q

definiert durch φ(a) = (a, 0) kann die Struktur (Q(√

α), +, ·) in die Struktur(Q × Q, +α , ·α) eingebettet werden, d.h. (Q × Q, +α , ·α) ist tatsachlich eineErweiterung von (Q(

√α), +, ·).

Ubungsaufgaben

3.14 Verifizieren Sie diese Einbettung anhand der Addition und der Multiplika-tion! �

Nun, es gilt offensichtlich (a, 0)+α (c, 0) = (a+c) sowie (a, 0)·α (c, 0) = (ac, 0).

156 Reelle und komplexe Zahlen


Durch Abstraktion bekannter Rechenregeln fur Zahlenmengen kommt man zualgebraischen Rechenstrukturen wie Halbgruppen, Monoide und Gruppen miteiner Operationen sowie Ringen, Integritatsbereichen und Korpern mit zwei Ver-knupfungen. Selbst Korper wie die Menge der rationalen Zahlen sind nicht ab-geschlossen gegen alle Operationen. So konnen die rationalen Zahlen um irra-tionale Wurzeln erweitert werden, so dass die neue Struktur wieder einen Korperbildet und die alte darin eingebettet ist. Der um die Wurzel erweiterte Korperkann ganzlich ohne die Wurzel (ohne die neue Zahl), alleine durch Paare von ra-tionalen Zahlen mit geeigneter Addition und Multiplikation dargestellt werden.

3.9 Die Mengen der reellen und der komplexen Zahlen

Im vorigen Abschnitt haben wir gesehen, wie die Menge Q der rationalen Zah-len um (einzelne) irrationale Zahlen erweitert werden kann. Diese so erweitertenZahlenmengen bleiben immer noch abzahlbar, denn aus einer Abzahlung fur Q

kann man eine Abzahlung fur Q×Q herleiten. Da die Menge R der reellen Zah-len, die neben den rationalen auch alle irrationalen Zahlen enthalt, uberabzahl-bar ist (siehe Abschnitt 3.5), werden wir bisherige Erweiterungsmethoden (Nauf Z, Z auf Q, Erweiterungen von Q), denen letztendlich immer die Menge dernaturlichen Zahlen zugrunde liegen, nicht mehr anwenden konnen. So benotigtdie Einfuhrung der Menge R der reellen Zahlen Methoden aus der Analysis, dieuber den inhaltlichen Rahmen dieses Buches hinausgehen. Deshalb deuten wirdie Konstruktion der reellen Zahlen nur beispielhaft an. Mithilfe der rationalenZahlen konnen dann die komplexen Zahlen allerdings wieder mit der Erweite-rungsidee des vorigen Abschnitts eingefuhrt werden.

3.9.1 Reelle Zahlen

Eine moglicher Ansatz zur Konstruktion der reeellen Zahlen sind rationale In-Intervall-

schachtelung tervallschachtelungen. Ist 〈 an 〉n∈N0= 〈 a0, a1, a2, . . . 〉 eine monoton wach-

sende Folge rationaler Zahlen, d.h. es ist an+1 ≥ an, und ist 〈 bn 〉n∈N0=

〈 b0, b1, b2, . . . 〉 eine monoton fallende Folge rationaler Zahlen, d.h. es ist bn+1 ≤bn, und ist zudem an ≤ bn und limn→∞(bn − an) = 0, d.h. die Elemente derDifferenzenfolge 〈 bn − an 〉n∈N0

werden mit wachsendem n beliebig klein, dannheißt die Folge In = [ an, bn ] von Intervallen eine Intervallschachtelung.

Zahlenmengen 157

Beispiel 3.7 Offensichtlich ist durch die Folge von Intervallen

In =

[1− 1

n, 1 +

1

n

]

eine solche Intervallschachtelung gegeben. �

Man kann nun zeigen, dass alle Intervalle einer solchen Intervallschachtelunggenau ein gemeinsames Element besitzen. Dieses Element kann eine rationaleZahl sein wie in obigem Beispiel, in dem genau die Zahl 1 in jedem Intervallenthalten ist. Es gibt aber auch Intervallschachtelungen, die in diesem Sinne kei-ne rationale Zahl bestimmen, solche Zahlen werden irrational genannt.

Beispiel 3.8 Wir definieren die Folgen 〈 bn 〉 und 〈 an 〉 durch:

b0 = 2

bn+1 =b2n + 2

2bn

an =2

bn

Man kann zeigen (etwa mithilfe vollstandiger Induktion), dass In = [ an, bn ]eine Intervallschachtelung ist und dass

an ≤√

2 ≤ bn

fur alle n ∈ N0 gilt. Daraus folgt, dass diese Intervallschachtelung genau dieZahl

√2 bestimmt. �

Die Folge 〈 bn 〉 ist eine Anwendung des Heron-Verfahrens,27 mit dem die Qua- Heron-

Verfahrendratwurzel einer Zahl α ∈ Q+ beliebig genau berechnet werden kann: Zur Be-rechnung von

√α bilde man die rekursive Folge

bn+1 =b2n + α

2bn

mit beliebigem Rekursionsanfang b0 = 0 (gunstig ist, b0 = 12(α +1) zu wahlen).

Es gilt dann √α ≤ bn+1 ≤ bn

fur alle n ∈ N0 sowielim

n→∞bn =

√α

Man kann nun eine neue Rechenstruktur einfuhren: Die Menge aller moglichenIntervallschachtelungen bildet die Tragermenge, und fur Intervallschachtelungen

27 Heron von Alexandria (Geburts- und Sterbedatum nicht genau bekann, lebte wohl im 1.Jahrhundert) war ein griechischer Mathematiker und Ingenieur, der fur seine Zeit erstaun-liche Erkenntnisse uber Natur und Technik gewann, Bucher daruber schrieb und Gerateund Maschinen konzipierte und baute. Er hatte bereits erste Ideen zur Automatisierungvon Maschinen und Programmierung von Geraten.


kann man eine Addition und eine Multiplikation einfuhren. Des Weiteren kannman uberlegen, dass Intervallschachtelungen im Hinblick auf die Zahl, die siedarstellen nicht eindeutig sind. So wird z.B. die Zahl 1 auch durch die Intervall-schachtelungen

In(c) =[1− c

n, 1 +

c

n

], c ∈ Q+

definiert. Allerdings kann man eine Aquivalenzrelation uber alle Intervallschach-telungen definieren, bei der sich alle Schachtelungen als untereinander aquiva-lent herausstellen, die dieselbe Zahl bestimmen. Die entsprechenden Aquiva-lenzklassen bilden dann genau die reellen Zahlen.

Die Menge R der reellen Zahlen erfullt alle bisher schon aufgelisteten Rechene-geln A1 - 4, M1 - 4, D1 - 2, ABS1 - 5 sowie O1, O2+ und O2−.

3.9.2 Komplexe Zahlen

In R konnen wir nun Gleichungen der Art x2 = α mit α ≥ 0 losen: Die Losungenx = ±

√α sind reelle Zahlen. Die Gleichungen x2 = −α mit α > 0 besitzen

allerdings keine Losungen in der Menge R, denn es gibt keine reelle Zahl β mitder Eigenschaft β2 = −α. Um Gleichungen dieser Art zu losen, fuhrt man diesogenannte imaginare Zahl i ein, und zwar durch die sie definierende EigenschaftImaginare Zahl

i2 = −1. Mit dieser Zahl und der Menge der reellen Zahlen definieren wir dieMenge der komplexen Zahlen als

C = { a + bi | a, b ∈ R }

Anstelle von a+bi notiert man auch a+ib. Re(z) = a heißt Realteil und Im(z) =Realteil

b heißt Imaginarteil der komplexen Zahl z = a + bi. z = a − bi heißt die zu zImaginarteil

konjugierte komplexe Zahl.Konjugierte

Die obige Gleichung x2 = −α mit α ∈ R und α > 0 besitzt in C die Losungz = i

√α. Es gilt Re(z) = 0 und Im(z) =

√α.

C ist eine Erweiterung von R, d.h. anstelle von C konnten wir auch R(i) schrei-ben (vergleiche Abschnitt 3.8.2). Ebenso konnen wir komplexe Zahlen a+ ib alsPaare (a, b) reeller Zahlen betrachten, dabei sei (a, b) = (a,−b) die Konjugiertezu (a, b). Die Paare (a, 0) entsprechen genau den reellen Zahlen.

Auf diesen Paaren definieren wir eine Addition und eine Multiplikation wieRechenoperationen

fur komplexe

Zahlenfolgt:

(a, b) + (c, d) = (a + c, b + d) (3.53)(a, b) · (c, d) = (ac− bd, bc + ad) (3.54)

Das Rechnen in der neuen Menge C wird also mit den Elementen der bekann-ten Menge R und den dort bekannten Rechenoperationen eingefuhrt. Wir gehenhier also genauso wie in den vorherigen Kapiteln vor, in denen wir mit bekannten

Zahlenmengen 159

Zahlen und darauf definierten Rechenoperationen neue Zahlen und neue Rechen-operationen eingefuhrt haben.

Ubungsaufgaben

3.15 Verifizieren Sie, dass die beiden Definitionen (3.53) und (3.54) auf denPaaren (a, 0) genau der Addition bzw. der Multiplikation reeller Zahlenentspricht! �

Die Rechenstruktur der reellen Zahlen ist also ein Teil der Rechenstruktur derkomplexen Zahlen. Insofern kann C als Erweiterung von R aufgefasst werden.

Die Addition zweier komplexer Zahlen ist also durch die Addition der beidenReal- sowie der beiden Imaginarteile festgelegt. Wir wollen die Definition derMultiplikation verifizieren: Es gilt

(a + bi) · (c + di) = ac + adi + cbi + bdi2 = (ac− bd) + (bc + ad)i

womit Real- und Imaginarteil des Produktes gleich dem Ergebnispaar der Defi-nition (3.54) sind.

Rechnen Sie nun nach, dass die Addition und die Multiplikation komplexer Zah- Rechenregeln

fur CCClen die Rechenregeln A1 - 2, M1 - 2 und D1 - 2 erfullen!

Rechnen Sie auch nach, dass (0, 1) · (0, 1) = (−1, 0) gilt, was der definierendenEigenschaft i2 = −1 der imaginaren Zahl entspricht. Rechnen Sie des Weiterennach, dass

(a, b) · (a, b) = (a2 + b2, 0) (3.55)

gilt sowie dass fur z, z1, z2 ∈ C die folgenden Beziehungen gelten:

z = z (3.56)z1 + z2 = z1 + z2 (3.57)z1 · z2 = z1 · z2 (3.58)(

z1

z2

)=

z1

z2

(3.59)

Ubungsaufgaben

3.16 Uberlegen Sie sich, welche komplexen Zahlen das neutrale Element derAddition bzw. das neutrale Element der Multiplikation sind, und bestim-men Sie das additive Inverse sowie das multiplikative Inverse zu einer kom-plexen Zahl z! �


Nun, das neutrale Element der Addition (x, y) muss die BedingungNeutrale

Elemente(a, b) + (x, y) = (a, b)

erfullen. Aus der Definition (3.53) folgt unmittelbar, dass nur (x, y) = (0, 0)diese Bedingung erfullt. (0, 0) entspricht der 0 in R.

Das neutrale Element (x, y) der Multiplikation muss die Bedingung

(a, b) · (x, y) = (a, b)

erfullen. Ausrechnen gemaß (3.54) ergibt das Gleichungssystem

ax− by = b

bx− ay = a

Fur (a, b) = (0, 0) ergeben sich die Losungen x = 1 und y = 0. (1, 0) ist alsodas neutrale Element der Multiplikation in C; es entspricht der 1 in R.

Fur das additive Inverse (x, y) zur Zahl (a, b) muss gelten: (a, b)+(x, y) = (0, 0).Additives

Inverse Aus (3.53) folgt unmittelbar, dass x = −a und y = −b sein muss. Es gilt also:−(a, b) = (−a,−b).

Nun wollen wir noch das multiplikative Inverse (x, y) zur Zahl (a, b) = (0, 0)Multiplikatives

Inverse bestimmen. Es muss gelten: (a, b) · (x, y) = (1, 0). Wir erhalten das Gleichungs-system

ax− by = 1

bx− ay = 0

Multiplikation der ersten Gleichung mit a und der zweiten Gleichung mitb und anschließende Addition der beiden Gleichungen liefert die Gleichung(a2 + b2)x = a woraus

x =a

a2 + b2

folgt. Durch Einsetzen dieses Wertes in die zweite Gleichung erhalten wir

y =−b

a2 + b2

Wir haben also berechnet, dass

(a, b)−1 =

(a

a2 + b2,−b

a2 + b2

)das multiplikative Inverse von (a, b) = (0, 0) ist.

Ubungsaufgaben

3.17 Rechnen Sie zur Probe nach, dass (a, b) · (a, b)−1 = (1, 0) gilt! �

Zahlenmengen 161

Vergleichbar zum Abschnitt 3.8.2, in dem wir eine Isomorphie zwischen der Er-weiterung Q(

√α) und Q × Q mit jeweils geeignet definierten Additionen und

Multiplikationen festgestellt haben, haben wir mit den obigen Uberlegungen eineIsomorphie zwischen C (= R(i)) und R× R nachgeweisen.

Wir wollen jetzt noch den komplexen Zahlen einen reellen Wert zuweisen. Dabeigehen wir von einer geometrischen Vorstellung aus: Wir betrachten die komple-xen Zahlen (x, y) als Punkte im zweidimensionalen kartesischen Koordinaten-system. Wir ordnen der Zahl z = (x, y) als Betrag |z| den (euklidischen) Ab-stand des Punktes (x, y) vom Ursprung (0, 0) zu. ”Nach Pythagoras“ ergibt sich Betrag |z| einer

komplexen Zahl

|z| =√

x2 + y2 (3.60)

Ubungsaufgaben

3.18 Rechnen Sie nach, dass fur z, z1, z2 ∈ C folgende Beziehungen gelten:(1) |z1 + z2| ≤ |z1|+ |z2|, (2) |z1 · z2| ≤ |z1| · |z2| , (3) |z|2 = z · z. �

Man kann Punkte (x, y) und damit komplexe Zahlen z = x + iy im zweidi-mensionalen Raum auch durch Polarkoordinaten darstellen, namlich durch den Polarkoordinaten

Abstand r = |z| dieses Punktes vom Ursprung (0, 0) und durch den Winkel αzwischen der x-Achse und der Strecke vom Ursprung zum Punkt (x, y). Die Po-larkoordinaten der komplexen Zahl z = x + iy sind also gegeben durch das Paar(r,α ). r heißt – wie schon bekannt – der Betrag, und der Winkel α heißt Argu-ment von z. Da fur jeden Winkel α fur k ≥ 0 die Punkte (r,α + 2kπ) identisch Argument einer

komplexen Zahlsind, schrankt man den Winkel α ein auf das Intervall −π < α ≤ π. Damit istdie Darstellung (r,α ) der Zahl z eindeutig. Dieses Argument α einer komplexenZahl z heißt dann ihr Hauptargument. Hauptargument

einer komplexen

ZahlMithilfe des Hauptargumentes α und der Winkelfunktionen cos und sin konnenwir Real- und Imaginarteil einer komplexen Zahl z = x + iy ausdrucken, dennes gilt

cos α =x

rund sin α =

y

r

und damitRe(z) = x = r · cos α bzw. Im(z) = y = r · sin α

Damit erhalten wir als weitere Darstellung der komplexen Zahl z = x + iy:

z = r(cos α + i sin α)

mitr =√

x2 + y2


und

α =

{+ arccos x

r, y ≥ 0

− arccos xr, y < 0

Wir wollen komplexe Zahlen mithilfe ihrer Polarkoordinatendarstellungen mul-tiplizieren und dividieren. Fur

z1 = r1(cos α1 + i sin α1) und z2 = r2(cos α2 + i sin α2)

gilt mithilfe der Additionsgesetze der Winkelfunktionen:

z1z2 = r1r2(cos α1 cos α2 − sin α1 sin α2 + i (cos α1 sin α2 + sin α1 cos α2))

= r1r2(cos(α1 + α2) + i sin(α1 + α2))

Analog erhalt man fur z2 = 0:z1

z2

=r1

r2

(cos(α1 − α2) + i sin(α1 − α2))

Aus der Formel fur die Multiplikation folgt unmittelbar eine Formel fur die Po-tenzierung einer komplexen Zahl z = r(cos α + i sin α):

zn = rn(cos(nα) + i sin(nα))

Hieraus konnen wir eine Formel fur die n-te Wurzel einer komplexen Zahl zWurzeln

komplexer

Zahlenherleiten. Dazu sei

z = r(cos α + i sin α) und y = ρ(cos β + i sin β)

mit yn = z, d.h. mit

r(cos α + i sin α) = ρn(cos(nβ) + i sin(nβ))

Daraus folgt, dass ρ = n√

r sowie cos α = cos(nβ) und sin α = sin(nβ) seinmussen. Dabei konnen sich die Winkel α und nβ nur um Vielfache von 2π un-terscheiden. Es gilt also

β =α

n+

2kπ

nfur k ∈ Z

Damit ergibt sich insgesamt

n√

z = n√

r

(cos

(α

n+

2kπ

n

)+ i sin

(α

n+

2kπ

n

)), k ∈ Z

Ubungsaufgaben

3.19 Uberlegen Sie, was dies geometrisch bedeutet! Wo befinden sich die n-tenWurzeln in der komplexen Ebene? �

Zahlenmengen 163

Geometrisch bedeutet dies, dass die n-ten Wurzeln einer komplexen Zahl z aufeinem Kreis um den Ursprung mit dem Radius n

√r mit dem Abstand 2π

nliegen.

Es reicht also eine Wurzel zu bestimmen, die anderen ergeben sich durch n − 1Drehungen dieses Punktes um 2π

n.

Die n-ten Wurzeln der komplexen Zahl z = 1 heißen Einheitswurzeln. Sie liegen Einheitswurzeln

auf dem Einheitskreis und haben die Polarkoordinaten (1, cos 2kπn

), k ∈ Z.

3.9.3 Algebraische und transzendente Zahlen

Allgemein gilt der sogenannte Fundamentalsatz der Algebra, den wir ohne Be-weis angeben, da dieser mathematische Kenntnisse verlangt, die nicht innerhalbdieses Buches behandelt werden.

Fundamentalsatz der Algebra Jede Gleichung

anxn + an−1x

n−1 + . . . a1x + a0 = 0

mit ai ∈ C, 0 ≤ i ≤ n, n ≥ 1, besitzt eine Losung in C. �

Definition 3.4 Eine Zahl α ∈ C heißt algebraisch genau dann, wenn sie eine Algebraische

ZahlLosung der Gleichung

anxn + an−1x

n−1 + . . . a1x + a0 = 0 (3.61)

mit ai ∈ Z, 0 ≤ i ≤ n, n ≥ 1, ist. n heißt der Grad der Gleichung.

Es sei Q die Menge der algebraischen Zahlen. �

Folgerung 3.3 a) Es gilt Q ⊂ Q: Jede rationale Zahl ist algebraisch.

b) Alle Quadratwurzeln√

α fur α ∈ Q+ sind algebraisch.

c) Q ist abzahlbar.

Beweis a) Jede rationale Zahl pq, p ∈ Z, q ∈ N ist Losung der Gleichung

qx − p = 0, damit gilt Q ⊆ Q. Die echte Teilmengenbeziehung Q ⊂ Q folgtmithilfe von b).

b) Jede Quadratwurzel√

α ist Losung der Gleichung x2 − α = 0.

c) Die Gleichungen der Art (3.61) vom Grad n werden eindeutig bestimmt durchdie Koeffizientenfolge a0, . . . , an, ai ∈ Z, 0 ≤ i ≤ n, n ≥ 1. Die Menge allerGleichungen vom Grad n entspricht also der Menge ×n

i=0 Zi. Diese Menge ist,wie wir wissen, abzahlbar. Alle moglichen Gleichungen entsprechen der Menge

∞⋃n=1

×ni=0 Zi

welche eine abzahlbare Vereinigung von abzahlbaren Mengen ist, die somitebenfalls abzahlbar ist. Jede Gleichung von Grad n hat hochstens n Losungen.Insgesamt ergibt sich damit die Behauptung. �


Die Menge der T = C−Q der komplexen, nicht algebraischen Zahlen nennt mantranszendent. Da C uberabzahlbar und Q abzahlbar ist, muss T uberabzahlbarsein. Bekannte Beispiele fur transzendente Zahlen sind die Kreiszahl π und dieTranszendente

Zahlen Euler-Zahl e = limn→∞(1 + 1n)n.


Die Menge R der reellen Zahlen lasst sich mithilfe von Intervallschachtelungenkonstruieren. Die Erweiterung der reellen Zahlen um die imaginare Zahli als Losung der Gleichung x2 = −1 fuhrt zur Menge der reellen ZahlenC = { a + bi | a, b ∈ R }. Eine komplexe Zahl z = a + bi lasst sich alsPunkt (a, b) im zweidimensionalen kartesischen Raum R × R interpretieren.Daraus ergibt sich eine weitere Darstellung komplexer Zahlen, die fur vieleAnwendungen von Bedeutung ist: die Darstellung in Polarkoordinaten (r,α ).Denn es ist z = r(cos α + i sin α) mit r = |z| =

√a2 + b2 der Abstand des

Punktes (a, b) vom Ursprung (0, 0), und α ist der Winkel zwischen der x-Achseund der Strecke vom Ursprung zum Punkt (a, b).

Die Menge Q der algebraischen Zahlen ist die Menge der Losungen vonGleichungen n-ten Grades mit ganzzahligen Koeffizienten. Diese Mengeist abzahlbar. Die Menge der nicht algebraischen Zahlen, die Menge dertranszendenten Zahlen T, ist uberabzahlbar.

Documents

Mathematische Grundlagen für die Informatik || Zahlenmengen