Kap. I : Teilbarkeit in ℤ

§ 1. Die geordnete Menge (ℤ, ≤)

Bezeichnungen: ℕ = {1, 2, 3, 4, 5, …} Menge der natürlichen Zahlen ≥ 1
ℕ_{0} := ℕ ∪ {0}
ℤ = {…, −3, −2, −1, 0, 1, 2, 3, 4, …} Menge der ganzen Zahlen

Die grundlegenden Eigenschaften der natürlichen Zahlen sind in den Peano–Axiomen (Giuseppe Peano, 1858–1932) zusammengestellt:

(1.1) Die PEANO–Axiome für die natürlichen Zahlen (1889):

P_{1}) 0 ist eine natürliche Zahl

P_{2}) Jede natürliche Zahl n besitzt eine natürliche Zahl n′ als Nachfolger

P_{3}) 0 ist nicht Nachfolger einer natürlichen Zahl

P_{4}) Haben zwei natürliche Zahlen denselben Nachfolger, so sind siegleich

P_{5}) Induktionsprinzip

Eine Menge T natürlicher Zahlen, die 0 enthält und mit jeder Zahl auch deren Nachfolger, enthält alle natürlichen Zahlen.

Das Induktionsprinzip ist die Grundlage für den Beweis durch vollständige Induktion:

(1.2) Beweis durch vollständige Induktion

A(n) sei eine Aussage in Abhängigkeit von n ∈ IN_{0}. Es gelte

i) A(0) ist richtig,
ii) ∀ n ∈ ℕ_{0} : A(n) wahr ⟹ A(n + 1) wahr.

Dann ist A(n) für alle natürlichen Zahlen n ∈ N_{0} richtig.

\underline{\underline{(1.3) DEF:}} Eine Relation ⪯ auf einer nichtleeren Menge M heißt eine Ordnungsrelation auf M , wenn gilt:

O_{1}) ∀ x ∈ M : x ⪯ x (d.h.⪯ ist reflexiv)
O_{2}) ∀ x, y ∈ M : x ⪯ y und y ⪯ x ⟹ x = y (d.h.⪯ ist antisymmetrisch)
O_{3}) ∀ x, y, z ∈ M : x ⪯ y und y ⪯ z ⟹ x ⪯ z (d.h.⪯ ist transitiv) .

(M, ⪯) heißt dann eine geordnete Menge . Gilt zusätzlich

O_{4}) ∀ x, y ∈ M : x ⪯ y oder y ⪯ x,

so heißt ⪯ eine lineare Ordungsrelation auf M und (M, ⪯) eine linear geordnete Menge .

\underline{\underline{(1.5) DEF:}} (M, ⪯) sei eine geordnete Menge und T ⊆ M eine nichtleere Teilmenge.

a) Ein Element o ∈ M heißt eine obere Schranke von T , wenn gilt: ∀ t ∈ T : t ⪯ o. Besitzt T eine obere Schranke, so heißt T nach oben beschränkt .

b) Ein Element g ∈ M heißt größtes Element von T , wenn gilt:

1) g ∈ T und 2) ∀ t ∈ T : t ⪯ g . Bezeichnung: g = max(T).

c) Ein Element u ∈ M heißt eine untere Schranke von T , wenn gilt: ∀ t ∈ T : u ⪯ t. Besitzt T eine untere Schranke, so heißt T nach unten beschränkt .

b) Ein Element k ∈ M heißt kleinstes Element von T, wenn gilt:

1) k ∈ T und 2) ∀ t ∈ T : k ⪯ t . Bezeichnung: k = min(T).

\underline{\underline{(1.7) SATZ:}} In einer linear geordneten Menge (M, ⪯) besitzt jede nichtleere \underline{endliche} Teilmenge ein kleinstes und ein größtes Element.

\underline{\underline{(1.8) KOROLLAR:}} In (ℤ, ≤) besitzt jede nichtleere \underline{endliche} Teilmenge ein kleinstes und ein größtes Element.

\underline{\underline{(1.9) SATZ:}} Sei T ⊆ ℤ eine nichtleere Teilmenge. Dann gilt:

a) T besitzt genau dann ein größtes Element, wenn T nach oben beschränkt ist.

b) T besitzt genau dann ein kleinstes Element, wenn T nach unten beschränkt ist.

\underline{(1.10) SATZ:}

Wohlordnung von (�_{0}, ≤)

Jede nichtleere Teilmenge von ℕ_{0} besitzt ein kleinstes Element.

\underline{\underline{(1.11) BEM:}} a) Allgemein heißt eine geordnete Menge (M, ⪯) wohlgeordnet , wenn jede nichtleere Teilmenge ein kleinstes Element enthält.

b) Die vorherigen Überlegungen zeigen, daß sich die Wohlordnung von (ℕ_{0}, ≤) aus den Peano– Axiomen herleiten läßt.

Im folgenden soll umgekehrt aus der Wohlordnung von (ℕ_{0}, ≤) das Induktionsprinzip bewiesen werden.

\underline{\underline{(1.12) BEM:}} Mit Hilfe der Wohlordnung von (ℕ_{0}, ≤) läßt sich beweisen: Sei m ∈ ℕ_{0} fest. Für die Teilmenge T ⊆ ℕ_{≥m} := {n | n ∈ ℕ_{0}, n ≥ m} gelte:

a) m ∈ T

b) ∀ t ∈ ℕ_{≥m} : t ∈ T ⟹ t + 1 ∈ T . Dann folgt T = ℕ_{≥m}.

(1.13) Beweis durch vollständige Induktion (1. Variante) A(n) sei eine Aussage in Abhängigkeit von n ∈ IN_{0}. Ferner sei m ∈ ℕ_{0} eine feste Zahl. Es gelte

i) A(m) ist richtig,
ii) ∀ n ∈ ℕ_{0}, n ≥ m : A(n) wahr ⟹ A(n + 1) wahr.

Dann ist A(n) für alle natürlichen Zahlen n ≥ m richtig.

(1.14) Beweis durch vollständige Induktion (2. Variante) A(n) sei eine Aussage in Abhängigkeit von n ∈ IN_{0}. Ferner sei m ∈ ℕ_{0} eine feste Zahl. Es gelte

i) A(m) ist richtig,

ii) Für alle n ∈ ℕ_{0} , n ≥ m folgt aus der Richtigkeit der Aussagen A(m), A(m + 1), A(m + 2), …, A(n) die Richtigkeit von A(n + 1) .

Dann ist A(n) für alle natürlichen Zahlen n ≥ m richtig.