KAPITEL II Natürliche Zahlen

1. Die natürlichen Zahlen

und die vollständige Induktion

Wie am Anfang der Mengenlehre eine axiomatische Einführung stand, so sollen jetzt die natürlichen Zahlen axiomatisch eingeführt werden. Dabei steht der Prozeß des gewöhnlichen Zählens zunächst im Vordergrund. Die heute übliche Begründung der natürlichen Zahlen basiert auf Axiomen, die von Peano 1889 veröffentlicht wurden, die aber auch Dedekind 1888 schon bekannt waren.

Wir werden einige einfache Eigenschaften der natürlichen Zahlen in der folgenden Definition festlegen. Dabei werden wir nebeneinander eine mathematisch präzise Formulierung, die wir in der Sprache der Mengenlehre geben können, und die umgangssprachliche Formulierung der gewünschten Eigenschaften für natürliche Zahlen angeben. Diese Eigenschaften nennt man auch die Peano-Axiome.

Die Existenz einzelner natürlicher Zahlen (z.B. zwei oder drei) ist in den logischen Grundlagen, die wir hier verwenden, enthalten, weil man einzelne Objekte nebeneinander stellen kann und sie damit abzählen kann. Die Existenz der Menge aller natürlichen Zahlen ist dadurch jedoch nicht gegeben. Das ist nämlich eine Menge mit unendlich vielen Elementen. Wir wissen bisher nicht einmal, ob es überhaupt irgendeine Menge mit unendlich vielen Elementen gibt. Daher müssen wir die Existenz der Menge aller natürlichen Zahlen zusätzlich durch ein mengentheoretisches Axiom fordern.

Das Rechnen mit natürlichen Zahlen ist ein wesentlich komplexerer Vorgang. Bevor wir überhaupt die Addition von natürlichen Zahlen einführen können, was erst im Abschnitt 3 geschehen wird, müssen wir starke Hilfsmittel über Rekursion und Induktion bereitstellen.

Definition 1.1. Ein Tripel (ℕ, 1, μ) bestehend aus einer Menge ℕ, einem Element 1 ∈ ℕ und einer Abbildung μ : ℕ ⟶ ℕ, genannt Nachfolgerfunktion, heißt (eine) Menge der natürlichen Zahlen, wenn die folgenden Axiome erfüllt sind: (P1) 1 ∈ ℕ, (”1 ist eine natürliche Zahl“), (P2) μ : ℕ ⟶ ℕ ist eine Abbildung, (”jede natürliche Zahl

besitzt einen eindeutig bestimmten Nachfolger“), (P3) ∀n ∈ ℕ[μ(n) ≠ 1], (”1 ist kein Nachfolger einer natür-

lichen Zahl“), (P4) μ ist injektiv, (”natürliche Zahlen mit gleichen Nachfol-

gern sind gleich“), (P5) (Prinzip der vollständigen Induktion)

∀E ⊂ ℕ[(1 ∈ E ∧ ∀n ∈ E[μ(n) ∈ E]) ⟹ E = ℕ],

(”eine Eigenschaft, die der 1 zukommt und mit einer beliebigen natürlichen Zahl auch ihrem Nachfolger, kommt allen natürlichen Zahlen zu“).

Wir schreiben mit der Nachfolgerfunktion μ und n ∈ ℕ häufig n + 1 := μ(n).

Axiom 6. (Existenz der Menge der natürlichen Zahlen) Es existiert eine Menge der natürlichen Zahlen (ℕ, 1, μ).

Wie wichtig die Forderung nach der Existenz einer Menge der natürlichen Zahlen ist, ersieht man aus dem folgenden Satz. Nur wenn es eine Menge der natürlichen Zahlen gibt, kann es überhaupt auch andere unendliche Mengen geben. Die Menge der natürlichen Zahlen kann man als den kleinsten Prototyp einer unendlichen Menge auffassen. Weiter kann man in jeder unendlichen Menge ein Modell für eine Menge von natürlichen Zahlen finden. Wir erinnern noch einmal an unsere Definition einer unendlichen Menge M (Kap.I. 2.29 und Kap.I.2.31). Es muß zu ihr eine (Selbst-)Abbildung λ : M ⟶ M geben, die injektiv aber nicht surjektiv ist.

Zum Beweis des folgenden Satzes benötigen wir zunächst ein Lemma.

Lemma 1.2. Seien M eine Menge, λ : M ⟶ M eine Abbildung und m ∈ M ein Element. Dann gibt es in M eine kleinste Teilmenge N mit λ(N) ⊂ N und m ∈ N.

Beweis. Wir betrachten die Menge 𝔐 aller Teilmengen A ⊂ M, für die gilt λ(A) ⊂ A und m ∈ A. Diese Menge enthält sicherlich M als Element. Nun bilden wir den Durchschnitt über alle so gefundenen Teilmengen

N := ⋂{A ⊂ M|λ(A) ⊂ A, m ∈ A}.

Offenbar ist dann m ∈ N. Für n ∈ N ist n in allen genannten Teilmengen A enthalten, also auch λ(n). Damit ist auch λ(n) ∈ N. N ist daher die kleinste Teilmenge von M mit m ∈ N und λ(N) ⊂ N. Insbesondere ist diese kleinste Teilmenge N in M mit λ(N) ⊂ N und m ∈ N eindeutig bestimmt.

Man kann sich diese kleinste Teilmenge N in M vorstellen als die Menge der Elemente, die man aus m durch beliebig häufige Anwendung von λ erhält, also die Menge {m, λ(m), λ(λ(m)), … }. Leider ist es recht schwierig, diese Menge formal richtig anzugeben, dashalb haben wir den unanschaulichen, aber mathematisch bequemen Weg der Durchschnittsbildung eingeschlagen. Wir werden diese Mothode bei den algebraischen Strukturen in Kapitel 4 häufig verwenden.

Satz 1.3. Die folgenden Aussagen sind äquivalent:

(1) Es existiert eine Menge der natürlichen Zahlen.

(2) Es existiert eine unendliche Menge.

Beweis. Wenn es eine Menge der natürlichen Zahlen (ℕ, 1, μ) gibt, so ist μ nach (P4) injektiv und nach (P3) nicht surjektiv. Also ist ℕ eine unendliche Menge. Sei umgekehrt M eine unendliche Menge und λ eine injektive und nicht surjektive Abbildung von M in M. Dann gibt es ein Element m ∈ M, das nicht im Bild von λ liegt. Wir betrachten jetzt die kleinste Teilmenge N ⊂ M mit λ(N) ⊂ N und m ∈ N. Sei ν : N ⟶ N die Einschränkung von λ auf die Teilmenge N. Wir zeigen, daß für (N, m, ν) die Peano-Axiome erfüllt sind. Offenbar ist ν als Einschränkung von λ wieder injektiv, und es gilt ∀n ∈ N[ν(n) ≠ m], da m nicht im Bild von λ liegt. Es bleibt nur die Gültigkeit des Prinzips der vollständigen Induktion für (N, m, ν) zu zeigen. Ist E ⊂ N mit m ∈ E und ∀n ∈ E[ν(n) ∈ E], dann gilt für E auch die Bedingung ν(E) ⊂ E bzw. λ(E) ⊂ E. Weil N die kleinste solche Menge ist und E ⊂ N gilt, folgt E = N. Damit ist die Gültigkeit des Prinzips der vollständigen Induktion (P5) bewiesen.

Die Konstruktion einer Menge der natürlichen Zahlen in einer beliebigen unendlichen Menge kann zu recht überraschenden Beispielen führen. Die Abbildung f : ℝ^{+} ∋ x ↦ x^{2} + 1 ∈ ℝ^{+} von den positiven rellen Zahlen in sich ist bekanntlich injektiv und es gilt 1 ∉ f(ℝ^{+}). Eine Menge der natürlichen Zahlen in ℝ^{+} ist dann N = {1, 2, 5, 26, … }.

Aus den vielen wichtigen Eigenschaften, die eine Menge von natürlichen Zahlen besitzt, ist das Zahlenrechnen in ℕ hervorzuheben. Bevor wir aber die einfachsten Rechenoperationen einführen können, müssen wir eines der wichtigsten Beweisprinzipien studieren, den Beweis durch vollständige Induktion. Es gibt dazu viele Varianten. Wir wollen lediglich zwei davon angeben. Sie alle bauen auf dem Peano-Axion (P5) auf. Weiter benötigen wir ein vor allem in der Informatik und mathematischen Logik wichtiges Hilfsmittel, die Definition von Abbildungen durch primitive Rekursion, bevor wir die einfachsten Rechenoperationen in der Menge der natürlichen Zahlen einführen können. Dieses Hilfmittel werden wir im nächsten Paragraphen beprechen.

Satz 1.4. (über den Beweis durch vollständige Induktion): Für jede natürliche Zahl n ∈ ℕ sei eine Aussage 𝔄(n) formuliert. Dafür gelte

Induktionsanfang:  𝔄(1) ist richtig (wahr) und
Induktionsannahme: aus der Richtigkeit von 𝔄(n)
Induktionsschluß:  folgt die Richtigkeit von 𝔄(n + 1).

Dann ist 𝔄(n) für alle n ∈ ℕ richtig. (Formal: (𝔄(1) ∧ ∀n ∈ ℕ[𝔄(n) ⟹ 𝔄(n + 1)]) ⟹ ∀n ∈ ℕ[𝔄(n)])

Beweis. Sei E := {n ∈ ℕ|𝔄(n)}. Es gilt 1 ∈ E und ∀n ∈ E[n + 1 ∈ E] wegen der Induktionsvoraussetzungen. Nach (P5) ist E = ℕ, also ∀n ∈ ℕ[𝔄(n)].

Varianten dieses Satzes sind vor allem Induktionsaussagen, die erst von einer vorgegebenen Zahl n_{0} ∈ ℕ an gelten:

𝔄(n_{0}) ∧ ∀n ∈ ℕ[n ≥ n_{0} ∧ 𝔄(n) ⟹ 𝔄(n + 1)])
⟹ ∀n ∈ ℕ[n ≥ n_{0} ⟹ 𝔄(n)].

Diese Aussage werden wir an dieser Stelle nicht beweisen, zumal wir die Ordnung m ≤ n auf den natürlichen Zahlen noch gar nicht kennen. Die Aussage ergibt sich später aber ganz leicht aus dem Beispiel einer Menge von natürlichen Zahlen, die eine Teilmenge T von ℕ ist mit derselben Nachfolgerabbildung, dem Anfangselement n_{0}, und deren Elemente gerade diejenigen n ∈ ℕ sind, für die n_{0} ≤ n gilt, also ({n ∈ ℕ|n_{0} ≤ n}, n_{0}, μ). (vgl. Beispiel 3.8 (2)).

Für den nächsten Satz setzen wir voraus, daß die Ordnung von ℕ schon bekannt ist. Diese Ordnung wird zwar erst in 3.3 eingeführt werden. Der Satz gehört jedoch systematisch in diesen Abschnitt über vollständige Induktion. Er wird zur Herleitung des Ordnungsbegriffes in ℕ auch nicht verwendet.

Satz 1.5. (über die starke vollständige Induktion) Für jede natürliche Zahl n ∈ ℕ sei eine Aussage 𝔄(n) formuliert. Dafür gelte

Induktionsanfang:  𝔄(1),
Induktionsannahme: aus ∀i ≤ n[𝔄(i)], d.h. aus
𝔄(1), …, 𝔄(i), …, 𝔄(n),
Induktionsschluß:  folgt 𝔄(n + 1).

Dann gilt 𝔄(n) für alle n ∈ ℕ.

Beweis. Wir definieren 𝔅(n) :⟺ ∀i ∈ ℕ[i ≤ n ⟹ 𝔄(i)]. Dann gelten 𝔅(1) und ∀n ∈ ℕ[𝔅(n) ⟹ 𝔅(n + 1)]. Also ist ∀n ∈ ℕ[𝔅(n)] und damit auch ∀n ∈ ℕ[𝔄(n)].

2. Primitive Rekursion

Wir wollen eine Abbildung φ : X ⟶ X iterieren, also φ^{2} := φφ, φ^{n+1} := φφ^{n} bilden. Diese zunächst ganz einfach erscheinende Bildung bringt eine grundlegende Schwierigkeit mit sich. Wir wissen nicht, ob φ^{n} für alle n ∈ ℕ mit den gewünschten Eigenschaften definiert ist. Dabei hilft zunächst auch noch nicht das Prinzip der vollständigen Induktion. Deswegen beschränken wir uns zunächst darauf, für ein Element c ∈ X die Elemente φ^{n}(c) ∈ X zu definieren, genau eine Abbildung

α : ℕ ∋ n ↦ φ^{n}(c) ∈ X

zu definieren. Das geschieht in dem folgenden Satz.

Satz 2.1. (über die einfache Rekursion): Sei X eine Menge, c ∈ X ein Element und φ : X ⟶ X eine Abbildung. Dann gibt es genau eine Abbildung α : ℕ ⟶ X mit

(1) α(1) = c,

(2) ∀n ∈ ℕ[α(n + 1) = φ(α(n))], d.h. so daß das Diagramm

[figure: ℕ; ℕ; μ; X; X; φ; α; α; {1}; ι; γ]

kommutiert, wobei γ(1) = c, ι(1) = 1.

Beweis. Quelle und Ziel für die gesuchte Abbildung α stehen fest. Wir suchen den Graphen von α. Dazu betrachten wir die Abbildung (μ × φ) : ℕ × X ∋ (n, x) ↦ (μ(n), φ(x)) ∈ ℕ × X und das Element (1, c) ∈ ℕ × X. Nach Lemma 1.2 sei G die kleinste Teilmenge von ℕ × X mit (μ × φ)(G) ⊂ G und (1, c) ∈ G.

1) Es ist (m, y) ∈ G ⟺ ((m, y) = (1, c) ∨ ∃(n, x) ∈ G[(m, y) = (n+1, φ(x))]. Hierbei gilt ”⟸“ wegen der Definition von G. Die Richtung ”⟹“ erhält man aus der folgenden Argumentation: Angenommen, die Folgerung gilt nicht. Dann gibt es ein (m, y) ∈ G mit (m, y) ≠ (1, c) und ∀(n, x) ∈ G[(m, y) ≠ (n + 1, φ(x))]. Dann gilt (μ × φ)(G \ {(m, y)}) ⊂ G \ {(m, y)} und (1, c) ∈ G\{(m, y)}. Das kann aber nicht sein, weil G die kleinste Menge mit diesen Eigenschaften ist.

2) G ist Graph einer Abbildung von ℕ nach X. Wir zeigen durch vollständige Induktion ∀n ∈ ℕ∃x ∈ X[(n, x) ∈ G]. Sei also 𝔄(n) die Induktionsaussage ∃x ∈ X[(n, x) ∈ G]. Induktionsanfang: 𝔄(1) gilt wegen (1, c) ∈ G.

Induktionsannahme: Gelte 𝔄(n), d.h. ∃x ∈ X[(n, x) ∈ G]. Induktionsschluß: Wegen (n + 1, φ(x)) ∈ G gilt 𝔄(n + 1). Damit folgt die Behauptung. Weiter zeigen wir durch vollständige Induktion: ∀n ∈ ℕ ∀x, y ∈ X[(n, x) ∈ G ∧ (n, y) ∈ G ⟹ x = y]. Sei 𝔄(n) die Induktionsaussage ∀x, y ∈ X[(n, x) ∈ G ∧ (n, y) ∈ G ⟹ x = y]. Induktionsanfang: Sei (1, x) ∈ G und (1, c) ∈ G. Angenommen x ≠ c. Wegen 1) gibt es (n, z) ∈ G[(1, x) = (n + 1, φ(z))], also 1 = n + 1 im Widerspruch zu (P3). Also ist x = c. Daraus folgt 𝔄(1). Induktionsannahme: Gelte 𝔄(n), d.h. ∀x, y ∈ X[(n, x) ∈ G ∧ (n, y) ∈ G ⟹ x = y]. Induktionsschluß: Seien x, y ∈ X gegeben mit (n+1, x) ∈ G und (n + 1, y) ∈ G. Da n durch n + 1 eindeutig festgelegt ist (μ ist injektiv), gibt es (nach 1)) u, v ∈ G mit (n, u) ∈ G, (n, v) ∈ G und φ(u) = x und φ(v) = y, wegen (n+1, φ(u)) = (n+1, x) und (n + 1, φ(v)) = (n + 1, y). Nach Induktionsannahme ist u = v, also x = φ(u) = φ(v) = y. Also ist α := (ℕ, X, G) eine Abbildung.

3) α erfüllt die Bedingungen α(1) = c und ∀n ∈ ℕ[α(n + 1) = φ(α(n))], denn (n, x) ∈ G und (n + 1, φ(x)) ∈ G implizieren α(n) = x und α(n + 1) = φ(x) = φα(n).

4) Es bleibt zu zeigen, daß α eindeutig bestimmt ist. Sei also β : ℕ ⟶ X mit β(1) = c und ∀n ∈ ℕ[β(n+1) = φβ(n)] gegeben. Wir zeigen durch vollständige Induktion ∀n ∈ ℕ[α(n) = β(n)]. Sei 𝔄(n) die Induktionsaussage α(n) = β(n). Induktionsanfang: Es ist α(1) = c = β(1), also gilt 𝔄(1). Induktionsannahme: Sei α(n) = β(n). Induktionsschluß: Dann ist α(n + 1) = φ(α(n)) = φ(β(n)) = β(n + 1). Damit gilt α = β.

In diesem Satz ist das Hilfsmittel der vollständigen Induktion gleich mehrfach angewendet worden. Damit haben wir jetzt aber auch die Möglichkeit, die Funktion φ^{n} für alle n ∈ zu definieren. Wir schreiben einfach φ^{1}(c) = c und φ^{n+1}(c) = φ(φ^{n}(c)). Für festgewähltes c ∈ X gibt es damit eine Abbildung φ()(c) : ℕ ⟶ X gegeben, wobei φ(n)(c) = φ^{n}(c) gelte. Da damit der Wert für jedes c ∈ X eindeutig festgelegt ist, haben wir auch die Abbildungen φ^{n} : X ⟶ X für alle n ∈ ℕ definiert. Häufig braucht man zur rekursiven Definition von Abbildungen etwas kompliziertere Bedingungen an die Rekursion. Der einfachste Fall ist der

Satz 2.2. (über die primitive Rekursion): Sei X eine Menge, c ∈ X ein Element und φ : ℕ × X ⟶ X eine Abbildung. Dann gibt es genau eine Abbildung α : ℕ ⟶ X mit

(1) α(1) = c,

(2) ∀n ∈ ℕ[α(n + 1) = φ(n, α(n))], d.h. so daß das Diagramm

[figure: ℕ; ℕ; μ; ℕ × X; X; φ; (id_{ℕ},α); α; {1}; ι; γ]

kommutiert, wobei γ(1) = (1, c), ι(1) = 1 und (id_{ℕ}, α)(n) := (n, α(n)).

Beweis. Wir wenden 2.1 an auf ℕ × X, (1, c) ∈ ℕ × X und ψ : ℕ × X ⟶ ℕ × X, ψ(n, x) := (n + 1, φ(n, x)). Dann gibt es genau eine Abbildung β : ℕ ⟶ ℕ × X mit β(1) = (1, c) und β(n + 1) = ψ(β(n)) für alle n ∈ N:

[figure: ℕ; ℕ; μ; ℕ × X; ℕ × X.; ψ; β; β; {1}; ι; γ]

Durch β werden eindeutig Abbildungen ρ : ℕ ⟶ ℕ und α : ℕ ⟶ X definiert mit β(n) = (ρ(n), α(n)). Für diese Abbildungen gilt ρ(1) = 1, α(1) = c und (ρ(n + 1), α(n + 1)) = β(n + 1) = ψ(β(n)) = ψ(ρ(n), α(n)) = (ρ(n) + 1, φ(ρ(n), α(n))), also ist ρ(n + 1) = ρ(n) + 1 und α(n + 1) = φ(ρ(n), α(n)). Da die Abbildung ρ aber ρ(1) = 1 und ρ(n + 1) = ρ(n) + 1 = μρ(n) erfüllt und ebenso id_{ℕ}(1) = 1 und id_{ℕ}(n + 1) = μ id_{ℕ}(n) gilt, ist ρ = id_{ℕ} nach 2.1, also ist α(n + 1) = φ(n, α(n)). Ist α′ : ℕ ⟶ X gegeben mit α′(1) = c und α′(n + 1) = φ(n, α′(n)) für alle n ∈ ℕ, so erfüllt β′ : ℕ ⟶ ℕ × X mit β′(n) := (n, α′(n)) die Bedingungen β′(1) = (1, α′(1)) = (1, c) und β′(n + 1) = (n + 1, α′(n + 1)) = (n + 1, φ(n, α′(n))) = ψ(n, α′(n)) = ψ(β′(n)), also ist β = β′ und damit α = α′.

Wir kommen jetzt zu den Grundlagen der natürlichen Zahlen zurück. Wir hatten schon gefordert, daß eine Menge der natürlichen Zahlen existieren soll. Es ist aber zunächst nicht klar, ob es hier verschiedene Wahlmöglichkeiten für diese Menge gibt. Wir werden in Beispiel 3.8 tatsächlich verschiedene Mengen angeben, die die Peano- Axiome erfüllen und damit als Mengen der natürlichen Zahlen in Frage kommen. Damit wäre es möglich, daß späteres Rechnen mit natürlichen Zahlen von der Wahl der Menge abhängt, was natürlich recht unsinnig wäre. Deswegen ist der folgende Satz wichtig.

Satz 2.3. (von der Eindeutigkeit der Menge der natürlichen Zahlen): Seien (ℕ, 1, μ) und (A, a, ν) Mengen der natürlichen Zahlen. Dann gibt es genau eine Abbildung α : ℕ ⟶ A mit α(1) = a und αμ = να, und diese Abbildung ist bijektiv.

Beweis. : Nach 2.1 folgt Existenz und Eindeutigkeit von α : ℕ ⟶ A mit α(1) = a, α(n+1) = ν(α(n)). Ebenso gibt es genau ein β : A ⟶ ℕ, so daß das Diagramm

[figure: A; A; ν; ℕ; ℕ.; μ; β; β; {a}]

3. DIE STRUKTUREN AUF DEN NATÜRLICHEN ZAHLEN 69

kommutiert. Insgesamt haben wir βα(1) = β(a) = 1 = id_{ℕ}(1) und ∀n ∈ ℕ[βα(n + 1) = βνα(n) = μβα(n)] und ∀n ∈ ℕ[id_{ℕ}(n + 1) = μ id_{ℕ}(n)]. Wegen der Eindeutigkeit in 2.1 folgt βα = id_{ℕ}. Analog sieht man αβ = id_{A}.

Bemerkung 2.4. Wir bemerken, daß α die gesamte bisher bekannte ”Struktur“ von ℕ erhält wegen α(1) = a und αμ = να (es ist gleichgültig, ob man erst den Nachfolger in ℕ bildet und dann nach A geht, oder gleich nach A geht und dann dort den Nachfolger bildet). Man kennt den ”Nachfolger“ in A wegen ν = αμα^{−1}. Ebenso kennt man die ”Eins“ in A : α(1) = a. Wir wählen daher eine Menge der natürlichen Zahlen (ℕ, 1, μ) fest aus und bezeichnen sie fortan als die Menge der natürlichen Zahlen. Nach der vorhergehenden Bemerkung ist das keine Einschränkung. In jeder anderen Menge der natürlichen Zahlen könnte die Theorie genauso aufgebaut werden und ergäbe über die bijektive Abbildung α dieselben Resultate (dieselben Primzahlen, dieselbe Primzahlzerlegung etc.).

3. Die Strukturen auf den natürlichen Zahlen

Wir wollen in diesem Abschnitt die üblichen Regeln des Rechnens mit den natürlichen Zahlen entwickeln. Dabei werden wir uns auf die einfache Rekursion stützen und mit ihr zunächst Addition und Multiplikation von natürlichen Zahlen definieren. Mit Hilfe der primitiven Rekursion kann man dann auch das Potenzieren von natürlichen Zahlen einführen.

Definition und Lemma 3.1. (1) Sei m ∈ ℕ. Wir definie-

ren die Abbildung α_{m} : ℕ ⟶ ℕ durch die Bedingungen α_{m}(1) = m + 1,

∀n ∈ ℕ[α_{m}(n + 1) = α_{m}(n) + 1]

(bezüglich m + 1 = μ(m) ∈ ℕ, ρ : ℕ ⟶ ℕ, ρ(n) = μ(n)). Wir kürzen α_{m}(n) =: m + n ab. Die Abbildung ℕ × ℕ ∋ (m, n) ↦ m + n ∈ ℕ heißt Addition.

(2) Sei m ∈ ℕ. Wir definieren die Abbildung μ_{m} : ℕ ⟶ ℕ

durch die Bedingungen μ_{m}(1) = m,

∀n ∈ ℕ[μ_{m}(n + 1) = μ_{m}(n) + m]

(bezüglich m ∈ ℕ, ρ : ℕ ⟶ ℕ, ρ(n) = n+m). Wir kürzen μ_{m}(n) =: m·n ab. Die Abbildung ℕ×ℕ ∋ (m, n) ↦ m·n ∈ ℕ heißt Multiplikation.

(3) Sei m ∈ ℕ. Wir definieren die Abbildung ρ_{m} : ℕ ⟶ ℕ

durch die Bedingungen ρ_{m}(1) = m,

∀n ∈ ℕ[ρ_{m}(n + 1) = ρ_{m}(n) · m]

(bezüglich m ∈ ℕ, ρ(n) = n · m). Wir kürzen ρ_{m}(n) =: m^{n} ab. Die Abbildung ℕ × ℕ ∋ (m, n) ↦ m^{n} ∈ ℕ heißt Potenzieren.

Beweis. In allen drei Fällen existieren die Abbildungen und sind eindeutig bestimmt wegen 2.1 α_{1}(n) = n + 1 und μ(n) = n+1 können tatsächlich indentifiziert werden wegen α_{1}(1) = μ(1) und ∀n ∈ ℕ[α_{1}(μ(n)) = μ(α_{1}(n))] und ∀n ∈ ℕ[μ μ(n) = μ μ(n)], also wegen α_{1} = μ.

Man muß sich die Bedeutung der Rekursionsformeln klar machen, um zu verstehen, daß mit diesen Konstruktionen etwas ganz Alltägliches gemeint ist. Die Rekursionsformel für die Addition ist gegeben durch m + (n + 1) = (m + n) + 1, also einfach durch einen Spezialfall des Assoziativgesetzes für die Addition. Bei der Multiplikation ist die Bedingung m·(n+1) = (m·n)+m, also ein einfacher Fall des Distributivgesetzes. Schließlich fordern wir für das Potenzieren m^{n+1} = m^{n} · m. Daher sind einige einfache Fälle der Rechenregeln für natürliche Zahlen schon in der Definition angelegt. Die anderen Rechenregeln muß man allerdings beweisen.

Satz 3.2. (Rechengesetz für natürliche Zahlen): Für alle m, n, t ∈ ℕ gilt:

(1) m + n = n + m; m · n = n · m;

(2) (m + n) + t = m + (n + t); (m · n) · t = m · (n · t);

(3) t + m = t + n ⟹ m = n; t · m = t · n ⟹ m = n; (Kürzungsgesetz)

(4) m · (n + t) = m · n + m · t;

(5) 1 · n = n.

Beweis. Zunächst weisen wir die Rechnengesetze für die Addition nach.

(1) i) Wir wissen schon m + (n + 1) = (m + n) + 1. Durch Induktion nach m beweisen wir zunächst 1 + m = m + 1. Es ist 1 + 1 = 1 + 1. Ist 1 + m = m + 1, so ist auch 1 + (m + 1) = (1+m)+1 = (m+1)+1. Also folgt die Behauptung. Jetzt zeigen wir m + (n + 1) = (m + n) + 1 = (m + 1) + n durch Induktion nach n. Wir brauchen nur die letzte Gleichung zu zeigen. Es ist (m + 1) + 1 = (m + 1) + 1. Ist (m + n) + 1 = (m + 1) + n, so ist (m + (n + 1)) + 1 = ((m + n) + 1) + 1 = ((m + 1) + n) + 1 = (m + 1) + (n + 1), also folgt die Behauptung. Jetzt kommen wir endlich zum Kommutativgesetz der Addition, das wir wieder durch Induktion nach n zeigen. Es ist m + 1 = 1 + m, wie oben gezeigt. Ist m + n = n + m, so folgt m + (n + 1) = (m + n) + 1 = (n + m) + 1 = (n + 1) + m nach dem vorher Gezeigten, und wir sind fertig.

(2) i) Das Assoziativgesetz weisen wir durch Induktion nach t nach. Es ist (m + n) + 1 = m + (n + 1) nach Definition. Gilt (m + n) + t = m + (n + t), so folgt (m + n) + (t + 1) = ((m + n) + t) + 1 = (m + (n + t)) + 1 = m + ((n + t) + 1) = m + (n + (t + 1)).

(3) i) Induktion nach t: Ist 1+m = 1+n, so ist nach (P4) m = n. Folgt aus t+m = t+n für jede Wahl von m und n immer m = n, so folgt (t+1)+m = (t+1)+n ⟹ 1+(t+m) = 1+(t+n) ⟹ t + m = t + n ⟹ m = n. Wir kommen nun zu den Rechengesetzen der Multiplikation. Nach Definition gilt m · 1 = m und m · (n + 1) = (m · n) + m.

(5) Aus der Definition folgt 1·1 = 1. Wenn 1·n = n gilt, so folgt 1 · (n + 1) = (1 · n) + 1 = n + 1.

(1) ii) Wir zeigen zunächst (n+1)·m = n·m+m durch Induktion nach m. Es ist (n + 1) · 1 = n + 1 = n · 1 + 1. Wenn (n + 1) · m = n · m + m gilt, so ist (n + 1) · (m + 1) = (n + 1) · m + (n + 1) = n · m + m + n + 1 = n · m + n + m + 1 = n · (m + 1) + (m + 1). Weiter ist nach (5) 1 · m = m = m · 1. Wenn n · m = m · n gilt, so ist (n + 1) · m = n · m + m = m · n + m = m · (n + 1).

(4) Es ist m · (n + 1) = m · n + m = m · n + m · 1. Wenn m · (n + t) = m · n + m · t gilt, so folgt m · (n + (t + 1)) = m·((n+t)+1) = m·(n+t)+m = m·n+m·t+m = m·n+m·(t+1).

(2) ii) Es ist (m·n)·1 = m·n = m·(n·1). Ist (m·n)·t = m·(n·t), so folgt (m · n) · (t + 1) = (m · n) · t + m · n = m · (n · t) + m · n = m · ((n · t) + n) = m · (n · (t + 1)).

(3) ii) Diesen Beweis stellen wir bis zum Beweis des Satzes 3.5 zurück.

Die natürlichen Zahlen tragen noch eine weitere interessante Struktur. Sie bilden eine total geordnete Menge. Die Eigenschaften dieser Ordnung untersuchen wir im folgenden. Insbesondere wird sich herausstellen, daß diese Ordnung zusätzliche wichtige Eigenschaften hat, sie ist eine Wohlordnung. Zunächst definieren wir diese Ordnung auf ℕ.

Definition und Satz 3.3. Auf ℕ ist eine totale Ordnung gegeben durch m ≤ n :⟺ (m = n ∨ ∃p ∈ ℕ[p + m = n]).

Beweis. Die Reflexivität ist unmittelbar klar. Für den Beweis der Transitivität sei a ≤ b und b ≤ c. Wenn in einem der beiden Fälle Gleichheit gilt, so folgt unmittelbar a ≤ c. Sei also a+s = b und b + t = c. Dann folgt a + s + t = c, also a ≤ c. Sei a ≤ b, b ≤ a und a ≠ b. Dann gilt a + s = b und b + t = a, also a + s + t + 1 = a + 1, nach 3.2 (3) i) also s + t + 1 = 1 im Widerspruch zu (P3). Damit gilt auch die Antisymmetrie. Die Eigenschaft der totalen Ordnung folgt aus der Wohlordnung der natürlichen Zahlen, die wir sogleich zeigen werden.

Definition 3.4. Eine Ordnung auf einer Menge A heißt Wohlordnung, wenn jede nichtleere Teilmenge von A ein kleinstes Element besitzt.

Satz 3.5. (1) ∀m, n, p ∈ ℕ[m ≤ n ⟺ p + m ≤ p + n], (2) ∀m, n, p ∈ ℕ[m ≤ n ⟹ p · m ≤ p · n],

(3) ∀n ∈ ℕ[1 ≤ n],

(4) ∀n ∈ ℕ[n ≠ n + 1],

(5) {m ∈ ℕ|n ≤ m ∧ m ≤ n + 1} = {n, n + 1},

(6) ℕ mit ≤ ist wohlgeordnet.

Beweis. (1) Gelte m ≤ n. Wenn m = n gilt, dann ist nichts zu zeigen. Sei m + t = n. Dann folgt p + m + t = p + n, also p + m ≤ p + n. Sei umgekehrt p + m ≤ p + n. Wenn m ≤ n ist, ist nichts zu zeigen. Wenn jedoch m ≥ n gilt, dann ist nach dem ersten Teil der Aussage p + m ≥ p + n, zusammen mit der anderen Ungleichung erhält man p + m = p + n. Nach dem Kürzungsgesetzt ergibt sich m = n.

(2) Gelte m ≤ n. Dann folgt p · n = p · (m + t) = p · m + p · t, also p · m ≤ p · n.

(3) Es ist 1 ≤ 1. Weiter folgt aus 1 ≤ n und 1 + t = n sofort 1 + t + 1 = n + 1, also 1 ≤ n + 1. Ist jedoch 1 ≤ n und 1 = n, so folgt 1 + 1 = n + 1, also wieder 1 ≤ n + 1.

(4) Sei E = {n ∈ ℕ|n ≠ n + 1}. 1 ∈ E wegen (P3). Sei n ∈ E ⟹ n ≠ n + 1 ⟹ μ(n) ≠ μ(n + 1) ⟹ n + 1 ∈ E ⟹ E = ℕ.

(5) Offenbar erfüllen m = n und m = n + 1 die Bedingungen n ≤ m und m ≤ n+1. Sei jetzt m ≠ n und n ≤ m und m ≤ n+1. Dann ist m = n + t für ein t ∈ ℕ, also n + t ≤ n + 1. Wegen 1 ≤ t gilt auch n + 1 ≤ n + t und damit m = n + t = n + 1. Also sind die beiden angegebenen Mengen gleich.

(6) Sei I ⊂ ℕ, I ≠ ∅. Sei A := {n ∈ ℕ|∀i ∈ I[n ≤ i]}. Wir wollen zeigen, daß A ∩ I ≠ ∅. Wenn nämlich dann r ∈ A ∩ I, dann gilt ∀i ∈ I[r ≤ i], d.h. r ∈ I ist das kleinste Element von I. Wir nehmen jetzt an, daß A ∩ I = ∅. Nach (3) ist 1 ∈ A. Sei n ∈ A und sei i ∈ I. Wegen A ∩ I = ∅ ist n ∉ I, also n ≠ i. Weiter ist n ≤ i, also existiert ein t ∈ ℕ mit n + t = i. Wegen 1 ≤ t ist n + 1 ≤ n + t = i, also ist auch n + 1 ∈ A. Nach Induktionsprinzip ist daher A = ℕ und I ⊂ ℕ = A, ein Widerspruch zu A ∩ I = ∅.

Beweis. von 3.2 (3) ii) Aus 1 · m = 1 · n folgt m = n. Wenn aus t · m = t · n die Gleichung m = n folgt, so schließen wir wie folgt. Sei (t + 1) · m = (t + 1) · n. Wenn m = n, dann sind wir schon fertig. Sonst gilt n ≤ m oder m ≤ n. Bis auf Umbenennung können wir n ≤ m mit n + s = m annehmen. Dann ist t · n + n + 1 = (t + 1) · n + 1 = (t + 1) · m + 1 = (t + 1) · (n + s) + 1 = t · n + n + t · s + 1, nach 3.2 (3) i) also 1 = t · s + 1 im Widerspruch zu (P3). Also kann n + s = m nicht eintreten. Es gilt daher n = m.

Bemerkung 3.6. Die letzte Aussage des Satzes ist ein wichtiges mathematisches Beweismittel, das man auch die ”Jagd nach dem kleinsten Verbrecher“ nennt. Wenn man eine Aussage 𝔄(n) für alle n ∈ ℕ beweisen will und eine vollständige Induktion kompliziert wird, so hilft häufig die folgende Argumentation. Man nimmt an, daß es Elemente r ∈ ℕ gibt, für die die Aussage 𝔄(n) falsch ist. Dann gibt es nach Teil (4) des Satzes auch ein kleinstes solches n_{0} ∈ ℕ, für das 𝔄(n_{0}) falsch ist. Das Element n_{0} nennt man oft auch den kleinsten ”Verbrecher“. Man zeigt dann, daß diese Bedingung zu einem Widerspruch führt. Es gibt also keine Elemente n ∈ ℕ, für die die Aussage falsch ist. Sie ist daher für alle n ∈ ℕ richtig.

Der Begriff der Wohlordnung hat eine weitere ungemein wichtige Bedeutung in der Mengenlehre. Es gibt nämlich ein weiteres Axiom der Mengenlehre über die Wohlordnung. Für viele Anwendungen sind die dazu äquivalenten (und damit auch als Axiome der Mengenlehre verwendbaren) Aussagen ebenso wichtig. Wir können sie hier nur für spätere Anwendungen formulieren, aber ihre Äquivalenz nicht beweisen.

Axiom 7. Jede Menge kann wohlgeordnet werden, d.h. auf jeder Menge gibt es eine Wohlordnung.

Satz 3.7. Unter den übrigen Axiomen der Mengenlehre sind äquivalent:

(1) (Wohlordnungsaxiom) Jede Menge kann wohlgeordnet werden.

(2) (Zornsches Lemma) Besitzt in einer geordneten Menge A jede total geordnete Teilmenge eine obere Schranke, so besitzt A ein maximales Element.

(3) (Auswahlaxiom) Zu jeder Menge M ≠ ∅ gibt es eine Abbildung f : P(M) ⟶ M mit der Eigenschaft

∀U ∈ P(M) \ {∅}[f(U) ∈ U].

”Es gibt eine Abbildung f, die aus jeder nichtleeren Teilmenge U von M eines ihrer Elemente, nämlich f(U), auswählt.“

Bevor wir weitere Eigenschaften der natürlichen Zahlen studieren, wollen wir einige Beispiele für Mengen der natürlichen Zahlen anführen und erinnern dazu nochmals an den Satz 2.3.

Beispiele 3.8. (1) Ein durch Axiom 6 gegebenes Tripel

(ℕ, 1, μ) ist eine Menge der natürlichen Zahlen.

(2) Sei n_{0} ∈ ℕ eine natürliche Zahl. Dann ist die Menge N := {n ∈ ℕ|n_{0} ≤ n} zusammen mit n_{0} und der Einschränkung μ|_{N} von μ als μ|_{N} : N ⟶ N eine Menge der natürlichen Zahlen.

(3) ℕ_{0} := ℕ ∪ {0} zusammen mit 0 und μ′ mit

μ′(n) = \begin{cases}μ(n), & für n ∈ ℕ, \\ 1, & für n = 0, \end{cases}

ist eine Menge der natürlichen Zahlen.

(4) ℕ_{0} × ℕ_{0} zusammen mit (0, 0) und ν : ℕ_{0} × ℕ_{0} ⟶ ℕ_{0} × ℕ_{0} mit

ν(m, n) := \begin{cases}(m + 1, n − 1), & falls n > 0, \\ (0, m + 1), & falls n = 0, \end{cases}

ist eine Menge der natürlichen Zahlen.

Das letzte Beispiel ist etwas komplizierter und zeigt, daß es häufig nicht sofort ersichtlich ist, ob man ein Modell für eine Menge der natürlichen Zahlen vor sich hat. Dabei gibt es einen einfachen Trick, neue Modelle zu konstruieren. Dazu gehen wir noch einmal auf 2.3 zurück. Wenn man zwei Mengen der natürlichen Zahlen (ℕ, 1, μ) und (A, a, ν) hat, dann gibt es eine bijektive Abbildung α : ℕ ⟶ A, die die gegebenen Strukturen erhält. Hat man nun nur eine Menge A und eine bijektive Abbildung α : ℕ ⟶ A, so kann man auf A eine Struktur einer Menge von natürlichen Zahlen immer einführen. Man definiert die ”Eins“ in A durch α(1) und die Nachfolgerabbildung ν : A ⟶ A durch ν := αμα^{−1}. Dann kann man leicht nachprüfen, daß (A, a, ν) eine Menge der natürlichen Zahlen ist. So ist auch unser Beispiel (4) entstanden. Der Leser mag versuchen, die bijektive Abbildung α : ℕ ⟶ ℕ_{0} × ℕ_{0} zu finden.

Man nennt eine Menge A abzählbar unendlich, wenn es eine bijektive Abbildung α : ℕ ⟶ A gibt. Die Abbildung wird dann auch eine Abzählung von A genannt. Offenbar kann man jede abzählbar unendliche Menge mit der Struktur einer Menge der natürlichen Zahlen versehen. Abzählbar unendliche Mengen sind ℤ, ℤ × ℤ, ℚ, ℚ × ℚ × ℚ, ℚ^{n} und viele andere mehr. Die jeweils induzierte Struktur einer Menge der natürlichen Zahlen auf den genannten Mengen hängt selbstverständlich von der gewählten Abzählung ab. Selbst auf ℕ mit 1 ∈ ℕ kann man verschiedene Nachfolgerfunktionen μ_{i} : ℕ ⟶ ℕ angeben, mit denen (ℕ, 1, μ_{i}) eine Menge der natürlichen Zahlen wird. Man kann also sehr exotische Beispiele für Mengen der natürlichen Zahlen finden. Beispiele für unendliche Mengen, die nicht abzählbar sind, sind ℝ, ℂ und Abb(ℝ, ℝ) = ℝ^{ℝ}, die Menge der reellen Funktionen. Diese Überlegungen führen jetzt aber schon in das Gebiet der Kardinalzahlen, die wir nicht weiter betrachten wollen.

Eine der wichtigen Rechenregeln in den natürlichen Zahlen ist die Division mit Rest, die in der Zahlentheorie eine grundlegende Bedeutung hat. Wir beweisen sie hier vor allem, um in der Folgerung eine Aussage über die Darstellung des größten gemeinsamen Teilers zweier Zahlen zu erhalten. Der dort angegebene Algorithmus ist Grundlage vieler zahlentheoretischer Programmpakete auf Computern.

Wir geben die Division mit Rest gleich für die Menge der ganzen Zahlen an, weil sie in dieser Menge ihre volle Nützlichkeit entwickelt. Man kann auch leicht die Division mit Rest für natürliche Zahlen formulieren und beweisen. Wie man formal die Menge der ganzen Zahlen ℤ einführt, werden wir erst im 5. Abschnitt dieses Kapitels diskutieren.

Satz 3.9. (Division mit Rest) Es gilt

∀x ∈ ℤ, n ∈ ℕ∃q ∈ ℤ, r ∈ ℕ_{0}[x = qn + r ∧ r ≤ n − 1],

und in dieser Darstellung sind q und r durch x und n eindeutig bestimmt.

Beweis. Sei M := {x − pn|p ∈ ℤ ∧ 0 ≤ x − pn}. Dann gilt M ⊂ ℕ_{0} und M ≠ ∅. Denn für x ≥ 0 ist x ∈ M und für x < 0 ist x − xn = x(1 − n) = (−x)(n − 1) ≥ 0, also x − xn ∈ M. Da ℕ und damit auch ℕ_{0} wohlgeordnet sind, existiert ein kleinstes Element r ∈ M mit x − qn = r oder x = qn + r. Wenn r ≥ n, dann ist r − n ≥ 0 und x − qn − n = x − (q + 1)n = r − n, also r − n ∈ M im Widerspruch dazu, daß r minimal in M gewählt ist. Damit ist r ≤ n − 1. Um nun die Eindeutigkeit von q und r zu zeigen, gelte auch x = qn+r = q′n+r′ mit r′ ≤ n−1, r′ ∈ ℕ_{0} und q′ ∈ ℤ. Ohne Einschränkung der Allgemeinheit kann r ≤ r′ angenommen werden. Dann ist 0 ≤ r′ − r = qn − q′n = (q − q′)n. Damit ist auch q−q′ ≥ 0. Wäre nun q−q′ ≥ 1, so wäre (q−q′)n ≥ n im Widerspruch zu (q−q′)n = r′−r ≤ n−1. Daher muß q = q′ und dann auch r = x − qn = x − q′n = r′ gelten.

Folgerung 3.10. Seien m, n ∈ ℤ nicht beide 0, und sei t ∈ ℕ größter gemeinsamer Teiler von m und n. Dann gibt es a, b ∈ ℤ mit am + bn = t.

Beweis. Sei t kleinstes Element in der Menge M := {am + bn|a, b ∈ ℤ ∧ am + bn > 0}. Da die Menge offenbar nicht leer ist und in ℕ liegt, existiert t, und es ist t = a_{0}m + b_{0}n. Die Division mit Rest ergibt m = qt + r mit 0 ≤ r < t. Wegen r = m − qt = m − qa_{0}m − qb_{0}n = (1 − qa_{0})m − qb_{0}n ist r ∈ M oder r = 0. Weil t in M minimal ist und r < t gilt, muß r = 0 gelten. Also ist m = qt. Ebenso erhält man n = pt. Also ist t ein gemeinsamer Teiler von m und n. Ist d ∈ ℕ ein weiterer gemeinsamer Teiler von m und n, so gilt xd = m und yd = n, also t = a_{0}xd + b_{0}yd = (a_{0}x + b_{0}y)d. Damit ist d ein Teiler von t und t größter gemeinsamer Teiler von m und n.

Bemerkung 3.11. Einen Algorithmus zur Bestimmung von t, a_{0} und b_{0} aus m und n ≠ 0 erhält man so:

1. Schritt: man führe eine Division mit Rest aus: m = q·n+r und 0 ≤ r < n. Das kann man z.B. mit den in Computersprachen vorhandenen Operationen q = div(m, n) und r = mod(m, n) durchführen.

2. Schritt: man iteriere den 1. Schritt, indem man m durch n, n durch r ersetzt, bis r = 0 eintritt.

m_{0} := m, n_{0} := n,  m_{0} = q_{0}n_{0} + r_{0}, 0 ≤ r_{0} < n_{0},
m_{1} := n_{0}, n_{1} := r_{0}, m_{1} = q_{1}n_{1} + r_{1}, 0 ≤ r_{1} < r_{0},
⋮  ⋮  ⋮  ⋮
m_{k} := n_{k−1}, n_{k} := r_{k−1}, m_{k} = q_{k}n_{k}.

Dann ist n_{k} der größte gemeinsame Teiler von m und n, denn n_{k} = r_{k−1} teilt m_{k} = n_{k−1} und wegen m_{k−1} = q_{k−1}n_{k−1} + r_{k−1} auch m_{k−1}. Nach endlich vielen Schritten ist dann n_{k} ein Teiler von m und n. Weiter ist r_{0} = m − q_{0}n und r_{1} = m_{1} − q_{1}n_{1} = n − q_{1}(m − q_{0}n) = −q_{1}m + (1 + q_{0})n. Ist r_{i} = a_{i}m + b_{i}n und r_{i+1} = a_{i+1}m + b_{i+1}n, so ist r_{i+2} = m_{i+2} − q_{i+2}n_{i+2} = r_{i} − q_{i+2}r_{i+1} = a_{i}m + b_{i}n − q_{i+2}(a_{i+1}m + b_{i+1}n) = (a_{i} − q_{i+2}a_{i+1})m + (b_{i} − q_{i+2}b_{i+1})n. Also sind alle Reste, insbesondere aber r_{k−1} von der Form r_{k−1} = am + bn. Also ist jeder gemeinsame Teiler von m und n auch Teiler von r_{k−1}, d.h. r_{k−1} ist größter gemeinsamer Teiler. Die obige Berechnung der Faktoren a und b durch den Übergang

(\begin{matrix}a_{i} & a_{i+1} \\ b_{i} & b_{i+1} \end{matrix}) ↦ (\begin{matrix}a_{i+1} & a_{i} − q_{i+2}a_{i+1} \\ b_{i+1} & b_{i} − q_{i+2}b_{i+1} \end{matrix})

in jedem Schritt des Algorithmus ergibt mit dem Anfangswert

(\begin{matrix}1 & 0 \\ 0 & 1 \end{matrix}) die gewünschte Darstellung ggT(m, n) = am + bn. Der

Anfangswert ist dadurch zu erklären, daß man den gegebenen Algorithmus eventuell durch Umbenennung mit m > n durchführt (der Fall m = n ist trivial) und ihn noch um eine Zeile nach oben hin erweitert, nämlich

m_{−1} := n, n_{−1} := m, m_{−1} = 0 · n_{−1} + r_{−1}, 0 ≤ r_{−1} < n_{−1}.

Damit hat man r_{−2} := n_{−1} = m = 1 · m + 0 · n und r_{−1} = n = 0 · m + 1 · n. Dann kann man die iterative Anwendung der Division mit Rest in jedem Schritt begleiten von der angegebenen Umschreibung der Paare (a_{i}, b_{i}) und (a_{i+1}, b_{i+1}). Wenn der Algorithmus dann abbricht, hat man insbesondere die Koeffizienten der Darstellung r_{k−1} = am + bn erhalten.

4. Anzahlaussagen

Nachdem in Kapitel I in Definition 2.29 eine abstrakte Definition von endlichen Mengen ohne Rückgriff auf natürliche Zahlen gegeben wurde und jetzt die natürlichen Zahlen mit vielen ihrer Eigenschaften auch zur Verfügung stehen, können wir auch die viel anschaulichere Beschreibung endlicher Mengen geben, nämlich mit Hilfe der endlichen durch eine natürliche Zahl festgelegten Anzahl der Elemente in einer Menge. Wir werden danach in diesem Abschnitt für eine Reihe von Mengen die Anzahl ihrer Elemente genau bestimmen.

Satz 4.1. Die Menge {1, …, n} := {i ∈ ℕ|1 ≤ i ≤ n} ist endlich.

Beweis. Sei α : {1, …, n} ⟶ {1, …, n} injektiv. Es ist nach Kapitel I 2.30 zu zeigen, daß α surjektiv ist. Wir beweisen das durch vollständige Induktion nach n. Die Behauptung ist klar für n = 1. Sei α : {1, …, n + 1} ⟶ {1, …, n + 1} eine injektive Abbildung und α′ : {1, …, n} ⟶ {1, …, n + 1} die Einschränkung von α.

1. Fall: Bi(α′) ⊆ {1, …, n}. Dann ist α′ injektiv und nach Induktionsannahme damit auch surjektiv, also bijektiv. Da α injektiv ist, ist α(n + 1) ∉ {1, …, n} , also α(n + 1) = n + 1. Damit ist α surjektiv.

2. Fall: Wenn Bi(α′) ⊄ {1, …, n}, dann gibt es genau ein i mit α′(i) = n + 1 = α(i). Da α injektiv ist, gibt es auch ein j ∈ {1, …, n} mit α(n + 1) = j. Sei nun β : {1, …, n} ⟶ {1, …, n} definiert durch

β(m) = \begin{cases}α(m), & m ≠ i, \\ j, & m = i. \end{cases}

α injektiv ⟹ β surjektiv ⟹ alle Zahlen {1, …, n+1}\{j, n+ 1} kommen in Bi(α) vor, aber auch n + 1 und j, also ist α surjektiv.

Satz 4.2. Seien m, n natürliche Zahlen.

(1) Es gibt dann und nur dann eine injektive Abbildung α : {1, …, m} ⟶ {1, …, n}, wenn m ≤ n gilt.

(2) Es gibt dann und nur dann eine surjektive Abbildung α : {1, …, m} ⟶ {1, …, n}, wenn m ≥ n gilt.

(3) Es gibt dann und nur dann eine bijektive Abbildung α : {1, …, m} ⟶ {1, …, n}, wenn m = n gilt.

Beweis. (1) Wenn m ≤ n, dann ist die Inklusionsabbildung eine injektive Abbildung. Wenn m > n ist, dann ist die Komposi-

tion {1, …, m}⟶^{α}{1, …, n} ↪ {1, …, m} ebenfalls injektiv,

also nach 4.1 surjektiv, aber m ist nicht nur im Bild dieser Abbildung wegen m > n. Widerspruch. Damit ist m ≤ n.

(2) Sei m ≥ n. Dann ist

α(i) = \begin{cases}i & 1 ≤ i ≤ n \\ 1 & n < i ≤ m \end{cases}

eine surjektive Abbildung α : {1, …, m} ⟶ {1, …, n}. Sei α surjektiv. Sei β : {1, …, n} ⟶ {1, …, m}, g(i) = kleinstes j : α(j) = i. Damit ist β eine Abbildung und injektiv. ⟹ (nach Teil (1)) n ≤ m.

(3) Wenn n = m ist, dann ist die identische Abbildung eine bijektive Abbildung. Wenn α : {1, …, m} ⟶ {1, …, n} bijektiv ist, dann ist m ≤ n nach Teil 1 und m ≥ n nach Teil 2, also m = n.

Jetzt haben wir die Hilfsmittel zur Verfügung, um zu zeigen, daß die Endlichkeit einer Menge damit zusammenfällt, daß sie mit den natürlichen Zahlen bis zu einer bestimmten Zahl n abgezählt werden kann. Der Beweis des folgenden Satzes wird auch ergeben, daß die Anzahl der Elemente einer endlichen Menge von der Wahl der Abzählung, d.h. von der Reihenfolge, wie die Elemente abgezählt werden, unabhängig ist. Die zunächst so selbstverständlich erscheinende Tatsache, daß jede Abzählung einer endlichen Menge zu derselben Anzahl von Elementen führt, hat einen recht komplizierten Beweis, den wir auch als Beweis (mit einem Stern) markiert haben, der in der Vorlesung ausgelassen werden kann.

Satz 4.3. Eine Menge A ≠ ∅ ist genau dann endlich, wenn es ein m ∈ ℕ und eine bijektive Abbildung β : {1, …, m} ⟶ A gibt. m ist durch A eindeutig bestimmt und wird Anzahl der Elemente von A genannt.

Beweis^{∗}. Die eine Richtung des Beweises ist recht einfach. Sei β : {1, …, m} ⟶ A eine bijektive Abbildung. Sei γ : A ⟶ A injektiv. Dann ist auch β^{−1}γβ : {1, …, m} ⟶ {1, …, m} injektiv, also auch surjektiv. Damit wird dann auch γ = ββ^{−1}γββ^{−1} surjektiv, also ist A endlich. Die andere Richtung des Beweises ist die eigentlich wichtige Aussage des Satzes. Wir erläutern zunächst die Idee dieses längeren Beweises. Wir wollen die vorgegebene Menge so abzählen wie wir es uns naiv vorstellen. Dazu benötigen wir eine Abzählabbildung von ℕ in A. Wir hoffen, daß wir nicht alle natürlichen Zahlen benötigen, aber ob das geht, werden wir erst später feststellen können. Eine Abbildung ℕ ⟶ A kann mit einfacher Rekursion definiert werden. Der Anfang ist leicht: wir wählen irgendein Element von A, das wir als erstes abzählen. Die Fortsetzung der Abzählung ist komplizierter. Wenn wir schon n Elemente aus A abgezählt haben, dann müssen wir das nächste abzuzählende Element angeben. Es darf nicht unter den schon abgezählten Elementen vorkommen. Deshalb genügt es für die einfache Rekursion nicht, lediglich das letzte abgezählte Element zu kennen, man muß die Teilmenge U aller bisher abgezählten Elemente kennen. Dann kann man daraus das nächste abzuzählende Element festlegen, indem man ein Element aus dem Komplement von U in A wählt. Es kommt also eine Variante des Auswahlaxioms mit ins Spiel, weil wir zu jeder Teilmenge U ein Element außerhalb wählen müssen. Diese formulieren wir zunächst. Sei also A ≠ ∅ endlich. Wir benutzen eine Auswahlabbildung f : P(A)\{∅} ⟶ A (vgl. 3.7) mit f(U) ∈ U für alle Teilmengen U ≠ ∅ von A. Weiter sei g : P(A) \ {A} ⟶ A die Abbildung g(U) := f(A\U). Dann gilt g(U) ∉ U für alle Teilmengen U ≠ A von A. Sei X := {(a, U)|a ∈ U, U ∈ P(A)} ⊂ A × P(A). Wir definieren eine Abbildung φ : X ⟶ X durch

φ(a, U) := \begin{cases}(g(U), U ∪ \{g(U)\}) & für U ≠ A, \\ (a, A) & für U = A. \end{cases}

Weiter legen wir ein Element a_{1} ∈ A und damit ein Element (a_{1}, U_{1}) ∈ X mit U_{1} := {a_{1}} fest. Nach Satz 2.1 gibt es genau eine Abbildung, d.h. eine Folge, α : ℕ ⟶ X mit α(1) = (a_{1}, U_{1}) und α(r + 1) = φ(α(r)). Wir schreiben (a_{r}, U_{r}) := α(r) und erhalten so (a_{r+1}, U_{r+1}) = φ(a_{r}, U_{r}), also

a_{r+1} = \begin{cases}g(U_{r}), & wenn U_{r} ≠ A, \\ a_{r}, & wenn U_{r} = A, \end{cases}

U_{r+1} = \begin{cases}U_{r} ∪ \{a_{r+1}\}, & wenn U_{r} ≠ A, \\ A, & wenn U_{r} = A. \end{cases}

Wir können uns U_{r} als die Menge {a_{1}, …, a_{r}} = {a_{i}|1 ≤ i ≤ r} vorstellen, jedoch ist nicht klar, daß U_{r} tatsächlich diese Form hat. Im Falle U_{r} ≠ A ist nun a_{r+1} = g(U_{r}) ∉ U_{r}, also U_{r} ⫋ U_{r+1}. Im Falle U_{r} = A ist U_{r} ⊂ U_{r+1}. Sei r < s und U_{r} ≠ A. Dann ist U_{r} ⫋ U_{r+1}. Ist U_{r} ⫋ U_{r+t}, so ist dann U_{r+t} ⊂ U_{r+t+1}, also auch U_{r} ⫋ U_{r+t+1}. Damit ist mit vollständiger Induktion U_{r} ⫋ U_{r+t} für alle t ∈ ℕ, insbesondere also U_{r} ⫋ U_{s}. Sei r < s und U_{r} ≠ A. Wir zeigen jetzt, daß dann a_{r} ≠ a_{s} gilt. Für s = r + 1 haben wir a_{s} = a_{r+1} ∉ U_{r} und wegen a_{r} ∈ U_{r} gilt a_{s} ≠ a_{r}. Ist s = r + t und a_{r+t} ≠ a_{r}, so gibt es zwei Fälle. Ist U_{s} = A, so ist a_{r+t+1} = a_{s+1} = a_{s} ≠ a_{r}. Ist U_{s} ≠ A, so ist a_{r+t+1} = a_{s+1} ∉ U_{s}, also auch a_{r+t+1} ∉ U_{r} und damit a_{r+t+1} ≠ a_{r}. Die Behauptung a_{r} ≠ a_{r+t} gilt also für alle t ∈ ℕ. Wir betrachten die Menge B := {a_{i}|i ∈ ℕ} ⊂ A. Wenn für alle r ≠ s gilt a_{r} ≠ a_{s}, dann ist die Abbildung ℕ ∋ i ↦ a_{i} ∈ B bijektiv. Wir können damit die Abbildung B ∋ a_{i} ↦ a_{i+1} ∈ B konstruieren, die injektiv ist, aber nicht surjektiv. B ist als Teilmenge von A aber ebenfalls endlich, ein Widerspruch. Daher gibt es r < s mit a_{r} = a_{s}. Nach der vorhergehenden Überlegung ist dann U_{r} = A. Sei m ∈ ℕ die kleinste solche Zahl, d.h. die kleinste Zahl in {s ∈ ℕ|U_{s} = A}. Wir zeigen jetzt, daß die Abbildung β : {1, …, m} ⟶ A mit β(i) = a_{i} bijektiv ist. Für alle r < m ist U_{i} ≠ A und daher sind alle a_{r} für r ∈ {1, …, m} paarweise verschieden, d.h. β ist injektiv. Sei nun a ∈ A und a ∉ Bi(β). Dann ist a ≠ a_{1} und daher a ∉ U_{1}. Ist a ∉ U_{r}, so ist a ∉ U_{r} ∪ {β(r + 1)} = U_{r} ∪ {a_{r+1}} = U_{r+1}, also ist a ∉ U_{n} für alle n ∈ ℕ. Das ist ein Widerspruch wegen U_{m} = A. Daher ist β auch surjektiv. Die Eindeutigkeit von m folgt nun unmittelbar aus Satz 4.2.

Folgerung 4.4. (1) (Dirichletsches Schubfächerprinzip): Wenn man n Objekte auf m Schubfächer verteilt und n > m ist, dann gibt es mindestens ein Schubfach, das mehrere Objekte enthält.

(2) Wenn man n Objekte auf m Schubfächer verteilt und n < m ist, dann gibt es mindestens ein leeres Schubfach.

Beweis. (1) α : {1, …, n} ⟶ {1, …, m} und n > m impliziert, daß α nicht injektiv ist. Also existiert ein Schubfach j und Objekte i_{1}, i_{2} mit α(i_{1}) = α(i_{2}) = j.

(2) α : {1, …, n} ⟶ {1, …, m} und n < m impliziert, daß α nicht surjektiv ist. Also existiert ein Schubfach j mit α^{−1}(j) = ∅.

Definition 4.5. Wir bezeichnen mit ℕ_{0} ∋ n ↦ n! ∈ ℕ die eindeutig bestimmte Abbildung mit 0! := 1, 1! = 1 und (n + 1)! = n! · (n + 1). (2.2)

Satz 4.6. Es gibt n! verschiedene bijektive Abbildungen

α : {1, …, n} ⟶ {1, …, n}.

Diese Abbildungen heißen Permutationen.

Beweis. (durch vollständige Induktion) Wir beweisen allgemeiner: Sind A, B Mengen mit je n Elementen, dann gibt es genau n! Bijektionen von A nach B. Ist n = 1, so ist das klar. Sei die Behauptung für Mengen mit n Elementen richtig. Seien A = {a_{1} …, a_{n+1}} und B = {b_{1}, …, b_{n+1} Mengen mit n + 1 Elementen. Wir definieren A_{i} := A\{a_{i}}, B_{i} := B\{b_{i}}. Sei α : A ⟶ B eine Bijektion mit α(a_{n+1}) = b_{i}. Dann ist α′ : A_{n} ⟶ B_{i} wieder bijektiv mit α′(a_{j}) = α(a_{j}). Umgekehrt kann jede Bijektion α′ : A_{n} ⟶ B_{i} zu einer Bijektion α : A ⟶ B fortgesetzt

werden durch α(a_{j}) = \begin{cases}α′(a_{j}) & j ≤ n \\ b_{i} & j = n + 1 \end{cases}. Nach Induktionsan-

nahme gibt es n! bijektive α′ : A_{n} ⟶ B_{i}, also auch n! bijektive Abbildungen α : A ⟶ B mit α(a_{n}) = b_{i}. Es gibt n + 1 Möglichkeiten für die Wahl von b_{i}, also insgesamt n! · (n + 1) = (n + 1)! bijektive Abbildungen α · A ⟶ B.

Satz 4.7. Seien A = {a_{1}, …, a_{m}} und B = {b_{1}, …, b_{n}} endliche Mengen mit m bzw. n Elementen. Dann gibt es n^{m} Abbildungen von A nach B.

Beweis. Durch Induktion nach m: Für m = 1 gibt es offenbar n = n^{1} Abbildungen α(a_{1}) = b_{i}. Sei die Behauptung für m und alle n ∈ ℕ wahr und sei A = {a_{1}, …, a_{m+1}}. Dann läßt sich jede Abbildung α′ : {a_{1}, …, a_{m}} ⟶ {b_{1}, …, b_{n}} fortsetzen zu einer Abbildung α : A ⟶ B durch die Festsetzung α(a_{(}m + 1) := b_{i} (und α(a_{j}) = α′(a_{j}) für 1 ≤ J ≤ m) und jede Abbildung α : A ⟶ B kommt auf diese Weise vor. Also gibt es n^{m} · n = n^{m+1} Abbildungen von A nach B.

Definition und Lemma 4.8. Sei B ⊂ A eine Teilmenge. Die charakteristische Funktion χ_{B} von B ist die Abbildung χ_{B} :

A ⟶ {0, 1} mit

χ_{B}(a) = \begin{cases}0 & a ∉ B \\ 1 & a ∈ B. \end{cases}

Dann ist P(A) ∋ B ↦ χ_{B} ∈ Abb(A, {0, 1}) = {0, 1}^{A} eine bijektive Abbildung.

Beweis. Die Umkehrabbildung ist α ↦ B := {a ∈ A|α(a) = 1} = α^{−1}(1).

Folgerung 4.9. Sei A eine endliche Menge mit n Elementen. Dann besitzt A genau 2^{n} Teilmengen, d.h. die Potenzmenge P(A) besitzt genau 2^{n} Elemente.

Beweis. P(A) und {1, 2}^{A} haben gleich viele, also 2^{n} Elemente.

Definition 4.10. Der Binomialkoeffizient \binom{n}{r} ist die Anzahl

der r-elementigen Teilmengen einer Menge A mit n Elementen

für 0 ≤ r ≤ n. Wir definieren für r > 0: \binom{n}{−r} := 0, und für

m > n: \binom{n}{m} := 0.

Beachte: \binom{n}{0} = \binom{n}{n} = 1.

Folgerung 4.11. ∑_{r=0}^{n} \binom{n}{r} = 2^{n}.

Beweis. Durch Abzählen der r-elementigen Teilmengen für alle r.

Satz 4.12. Für alle n ∈ ℕ_{0} und 0 ≤ r ≤ n gilt

\binom{n}{r − 1} + \binom{n}{r} = \binom{n + 1}{r}.

Beweis. Bezeichne |B| die Anzahl der Elemente von B. Sei A eine Menge mit n + 1 Elementen und sei a ∈ A, A′ := A \ {a}. Dann ist

\binom{n+1}{r} = |\{U ⊂ A||U| = r\}|

= |{U ⊂ A|a ∈ U ∧ |U| = r} ˙∪{U ⊂ A|a ∉ U ∧ |U| = r}|

= |{U ⊂ A|∃V ⊂ A′[U = V ˙∪{a} ∧ |V | = r − 1]} ˙∪

{U ⊂ A′||U| = r}|

= |{V ⊂ A′||V | = r − 1} ˙∪{U ⊂ A′||U| = r}|

= \binom{n}{r−1} + \binom{n}{r}.

Folgerung 4.13. (Pascalsches Dreieck für Binomialkoeffizienten): Man erhält das Pascalsche Dreieck, indem man die beiden Seiten des Dreiecks mit Einsen besetzt und das Innere dadurch ausfüllt, daß man je zwei nebeneinander stehende Zahlen addiert und darunter zwischen ihnen notiert:

\binom{0}{0}  1
\binom{1}{r}  1 1
\binom{2}{r}  1 2 1  \binom{n}{r − 1} + \binom{n}{r}
\binom{3}{r}  1 3 3 1  \binom{n + 1}{r}
\binom{4}{r}  1 4 6 4 1

Jeder Eintrag dieses Dreiecks in der n-ten Zeile an der r-ten

Stelle enthält dann den Wert \binom{n}{r}.

Satz 4.14. Für 0 ≤ r ≤ n gilt \binom{n}{r} = \frac{n!}{r!(n − r)!}

Beweis. Durch vollständige Induktion nach n beweisen wir

𝔄(n) :⟺ ∀r ∈ ℕ[0 ≤ r ≤ n ⟹ \binom{n}{r} = \frac{n!}{r!(n − r)!}].

Induktionsanfang: Es ist \binom{1}{0} = 1 = \frac{1!}{0! · 1!} und \binom{1}{1} = 1 = \frac{1!}{1! · 0!}.

Induktionsannahme: Sei 𝔄(n) wahr. Induktionsschluß:

\begin{matrix}\binom{n + 1}{r} = \binom{n}{r − 1} + \binom{n}{r} = \frac{n!}{(r − 1)!(n − r + 1)!} + \frac{n!}{r!(n − r)!} \\ = \frac{n! · r + n!(n + 1 − r)}{r!(n + 1 − r)!} = \frac{(n + 1)!}{r!((n + 1) − r)!} \end{matrix}

für 1 ≤ r ≤ n.

Für r = 0 ist \binom{n + 1}{0} = 1 = \frac{(n + 1)!}{0!(n + 1)!} und für r = n + 1 ist

\binom{n + 1}{n + 1} = 1 = \frac{(n + 1)!}{(n + 1)!0!}.

Satz 4.15. (Die binomische Formel) Für alle a, b ∈ ℝ und n ∈ ℕ gilt

(a + b)^{n} = ∑_{r=0}^{n} \binom{n}{r}a^{r}b^{n−r}.

Beweis. Beim Ausmultiplizieren kommt a^{r} so oft vor, wie

man r Faktoren aus n Faktoren auswählen kann, also \binom{n}{r} mal.

Die restlichen n − r Faktoren ergeben b^{n−r}.

5. Ein kurzer Aufbau des Zahlensystems

In diesem kurzen Abschnitt wollen wir andeuten, wie man nun mit den für die natürlichen Zahlen gewonnenen Eigenschaften das weitere Zahlsystem entwickelt werden kann. Wir geben lediglich die Konstruktionen der Mengen der ganzen Zahlen, der rationalen Zahlen, der reellen Zahlen und der komplexen Zahlen an, ohne jeweils die Rechengesetze herzuleiten. Lediglich für die komplexen Zahlen definieren wir die Addition und die Multiplikation.

Definition 5.1. Die Menge der ganzen Zahlen ℤ wird wie folgt definiert. Auf ℕ × ℕ bildet man eine Äquivalenzrelation ∼ durch

(a, b) ∼ (c, d) :⟺ a + d = b + c.

Die Menge der Äquivalenzklassen ℕ × ℕ/ ∼ ist dann ℤ. Man fasse die Klasse \overline{(a, b)} als a − b auf.

Definition 5.2. Die Menge der rationalen Zahlen ℚ wird wie folgt definiert. Auf ℤ × (ℤ \ {0}) bildet man eine Äquivalenzrelation ∼ durch

(a, b) ∼ (c, d) :⟺ ad = cb.

Dann definiert man ℚ := ℤ × (ℤ \ \{0\})/ ∼ und kürzt \overline{(a, b)} durch \frac{a}{b} ab.

Definition 5.3. Die Menge der reellen Zahlen ℝ wird wie folgt definiert. Eine Teilmenge a ⊂ ℚ heißt Dedekindscher Schnitt, wenn

(1) a ≠ ∅ ∧ a ≠ ℚ,

(2) ∀x ∈ a∀y ∈ ℚ[x ≤ y ⟹ y ∈ a],

(3) a enthält kein kleinstes Element (bzgl. der Ordnung von

ℚ). Die Menge ℝ der reellen Zahlen ist die Menge der Dedekindschen Schnitte. Eine reelle Zahl ist also ein Dedekindscher Schnitt.

Nach Einführung der Ordnung in der Mange der reellen Zahlen und der Identifizierung der rationalen Zahlen mit speziellen reellen Zahlen stellt sich dann heraus, daß der zugehörige Dedekindsche Schnitt für eine reelle Zahl r aus allen rationalen Zahlen x mit r < x besteht.

Definition 5.4. Die Menge der komplexen Zahlen ℂ ist ℝ × ℝ mit den Rechenoperationen (a, b) + (c, d) = (a + c, b + d) und (a, b) · (c, d) = (ac − bd, ad + bc). Es ist i := (0, 1).