Natürliche Zahlen/Ordnung mengentheoretisch aus Peanoaxiomen/Textabschnitt

Definition

Es sei ${}(N,0,')$ ein Peanomodell für die natürlichen Zahlen. Dann heißt eine Teilmenge ${}T\subseteq N$ induktiv abgeschlossen, wenn für jedes ${}n\in T$ auch der Nachfolger ${}n'\in T$ ist.

Definition

Es sei ${}(N,0,')$ ein Peanomodell für die natürlichen Zahlen und ${}n\in \mathbb {N}$. Dann setzen wir

$N_{\geq n}=\bigcap _{M\subseteq N,\,n\in M{\text{ und }}M{\text{ ist }}{\text{induktiv abgeschlossen}}}M$

Wegen ${}n\in N$ und da ${}N$ selbst induktiv abgeschlossen ist, ist die Familie, über die der Durchschnitt genommen wird, nicht leer.

Lemma

Es sei ${}(N,0,')$ ein Peanomodell für die natürlichen Zahlen und ${}n\in \mathbb {N}$.

Dann ist

$N_{\geq n}$

induktiv abgeschlossen und enthält ${}n$.

Beweis

Das Element ${}n$ gehört zum Durchschnitt, da ein Durchschnitt über Menge genommen wird, die alle jeweils ${}n$ enthalten. Um zu zeigen, dass ${}N_{\geq n}$ induktiv abgeschlossen ist, sei ${}x\in N_{\geq n}$ ein beliebiges Element. Dann gehört ${}x$ zu jeder induktiv geordneten Menge ${}T$, die ${}n$ enthält. Dazu gehört dann auch der Nachfolger ${}x'$. Da dies für jedes solche ${}T$ gilt, gehört ${}x'$ auch zum Durchschnitt, also ${}x'\in N_{\geq n}$.

$\Box$

Man kann also ${}N_{\geq n}$ sehen als die kleinste induktiv abgeschlossene Teilmenge, die ${}n$ enthält.

Definition

Es sei ${}(N,0,')$ ein Peanomodell für die natürlichen Zahlen und ${}k,n\in N$. Dann setzt man

$k\geq n,{\text{ wenn }}k\in N_{\geq n}{\text{ gilt}}.$

Lemma

Es sei ${}(N,0,')$ ein Peanomodell für die natürlichen Zahlen und ${}k,n\in N$.

Dann ist

$k\geq n{\text{ genau dann, wenn }}N_{\geq k}\subseteq N_{\geq n}.$

Beweis

Es sei zunächst ${}k\geq n$, also ${}k\in N_{\geq n}$ nach Definition. Es sei ${}x\in N_{\geq k}$, d.h. ${}x$ gehört zu jeder induktiv abgeschlossenen Teilmenge, die ${}k$ enthält. Nach Voraussetzung und aufgrund von Fakt ist dann insbesondere ${}x\in N_{\geq n}$, was die Inklusion beweist. Die andere Richtung folgt direkt aus ${}k\in N_{\geq k}\subseteq N_{\geq n}$.

$\Box$

Lemma

Es sei ${}(N,0,')$ ein Peanomodell für die natürlichen Zahlen.

Dann ist

$N_{\geq k}=N_{\geq k'}\cup \{k\}{\text{ und }}k\not \in N_{\geq k'}.$

Beweis

Für die Inklusion ${}\supseteq$ ist einerseits ${}k\in N_{\geq k}$. Da ${}N_{\geq k}$ induktiv abgeschlossen ist, gilt auch ${}k'\in N_{\geq k}$ und damit nach Fakt auch ${}N_{\geq k'}\subseteq N_{\geq k}$. Für die andere Inklusion zeigen wir, dass ${}T=N_{\geq k'}\cup \{k\}$ induktiv abgeschlossen ist. Es sei dazu ${}x\in T$. Bei ${}x=k$ ist ${}x'=k'\in N_{\geq k'}\subseteq T$. Andernfalls ist ${}x\in N_{\geq k'}$ und da diese Menge induktiv abgeschlossen ist, folgt ${}x'\in N_{\geq k'}\subseteq T$. Damit ist die rechte Seite induktiv abgeschlossen und enthält ${}k$, also kommt sie im Durchschnitt, der ${}N_{\geq k}$ ergibt, vor, also gilt auch die andere Inklusion.

$\Box$

Lemma

Es sei ${}(N,0,')$ ein Peanomodell für die natürlichen Zahlen und ${}n\in \mathbb {N}$.

Dann ergibt die Einschränkung der Nachfolgeabbildung eine Bijektion

$N_{\geq n}\longrightarrow N_{\geq n'},\,x\longmapsto x'.$

Beweis

Zunächst landet die Abbildung in der angegebenen Menge. Es sei hierzu ${}x\in N_{\geq n}$. Dann ist nach Fakt ${}x=n$ oder ${}x\in N_{\geq n'}$. Im ersten Fall ist ${}x'=n'\in N_{\geq n'}$, im zweiten Fall folgt diese Zugehörigkeit aus der induktiven Abgeschlossenheit von ${}N_{\geq n'}$.

Die Abbildung ist injektiv, da sie eine Einschränkung der aufgrund der Peanoaxiome injektiven Nachfolgerabbildung ist. Es sei ${}B$ das Bild der Abbildung. Es ist ${}n'\in B$. Ferner ist ${}B$ induktiv abgeschlossen. Für ein Element ${}y\in B$ gibt es ja ein ${}x\in N_{\geq n}$ mit ${}y=x'$. Dann gehört aber ${}y'=(x')'$ ebenfalls zu ${}B$, da ${}x'\in N_{\geq n}$ ist. Daher muss ${}N_{\geq n'}\subseteq B$ gelten und die Abbildung muss surjektiv sein.

$\Box$

Korollar

Es sei ${}(N,0,')$ ein Peanomodell für die natürlichen Zahlen und ${}n,k\in N$.

Dann ist

$n\geq k{\text{ genau dann, wenn }}n'\geq k'.$

Beweis

Dies folgt aus der in Fakt bewiesenen Bijektion

$N_{\geq k}\longrightarrow N_{\geq k'},\,x\longmapsto x'.$

$\Box$

Lemma

Es sei ${}(N,0,')$ ein Peanomodell für die natürlichen Zahlen.

Dann gilt ${}n\not \in N_{\geq n'}$ für alle ${}n\in N$.

Beweis

Wir beweisen die Aussage durch Induktion nach ${}n$. Sei ${}n=0$. Wir behaupten, dass ${}N\setminus \{0\}$ eine induktiv abgeschlossene Menge ist, die ${}0'$ enthält. Letzteres folgt sofort aus ${}0'\neq 0$. Sei ${}x\neq 0$. Dann ist insbesondere auch ${}x'\neq 0$, da ${}0$ gemäß den Peanoaxiomen kein Nachfolger ist. Also ist ${}N\setminus \{0\}$ induktiv abgeschlossen. Es sei nun ${}n\notin N_{\geq n'}$ bereits bewiesen und betrachten wir ${}n'$. Aufgrund von Fakt haben wir eine bijektive Abbildung

$\varphi \colon N_{\geq n'}\longrightarrow N_{\geq (n')'},\,x\longmapsto x'.$

Wäre ${}n'\in N_{\geq (n')'}$, so müsste auch dessen (einziges) Urbild, also ${}n$, zu ${}N_{\geq n'}$ gehören, was aber aufgrund der Induktionsvoraussetzung ausgeschlossen ist.

$\Box$

Lemma

Es sei ${}(N,0,')$ ein Peanomodell für die natürlichen Zahlen.

Dann ist die in Definition festgelegte Relation ${}\geq$ eine totale Ordnung.

Beweis

Die Reflexivität und die Transitivität folgen aus der Charakterisierung in Fakt und aus den entsprechenden Eigenschaften der Inklusion.

Die Antisymmetrie beweisen wir durch Induktion über ${}n$, wobei die zu beweisende Aussage die Form ${}A(n)=$ für jedes ${}k\in N$ mit ${}k\geq n$ und ${}n\geq k$ gilt ${}n=k$. Es sei ${}n=0$. Bei ${}k\neq 0$ ist ${}k\in N\setminus \{k\}$, und diese Menge haben wir im Beweis zu Fakt als induktiv abgeschlossen nachgewiesen. Daher ist ${}0\not \in N_{\geq k}$. Es sei nun angenommen, dass ${}A(n)$ schon bewiesen ist und betrachten wir ${}n'$. Es sei ${}k$ gegeben mit ${}k\geq n'$ und ${}n'\geq k$. Bei ${}k=0$ erhalten wir aus der ersten Bedingung einen Widerspruch, da ${}0\not \in N_{\geq n'}$ gilt. Also ist ${}k=\ell '$. Aufgrund von Fakt gilt dann ${}\ell \geq n$ und ${}n\geq \ell$. Die Induktionsvoraussetzung impliziert dann ${}n=\ell$ und damit ${}n'=\ell '=k$.

Wir beweisen nun, ebenfalls durch Induktion nach ${}n$, dass eine totale Ordnung vorliegt, wobei wir die Aussage ${}A(n)=$ für alle ${}k$ ist ${}k\geq n$ oder ${}n\geq k$ zugrunde legen. Bei ${}n=0$ erhalten wir wegen ${}k\in N_{\geq 0}=N$ sofort ${}k\geq 0$. Es sei also die Aussage für ${}n$ schon bewiesen und betrachten wir ${}n'$. Es sei ${}k$ gegeben. Bei ${}k=0$ ist ${}k\leq n'$. Andernfalls ist ${}k=\ell '$ und dann gilt nach Induktionsvoraussetzung ${}\ell \geq n$ oder ${}\ell \leq n$, was die Vergleichbarkeit von ${}k$ mit ${}n'$ impliziert.

$\Box$