Menge/Endliche Teilmengen/Rekursiv/Erfüllt Peanoaxiome/Fakt/Beweis

Beweis

Zunächst ist ${}0=[\emptyset ]$ nicht Nachfolger einer Anzahlklasse ${}[T]$ . Denn andernfalls gebe es eine Teilmenge ${}T\subseteq M$ und ein Element ${}x\in M$ , ${}x\not \in T$ und eine Bijektion

T\cup \{x\}\longrightarrow \emptyset .

Eine solche Abbildung kann es aber nicht geben, da es keinen möglichen Wert für ${}x$ gibt.

Um zu zeigen, dass die Nachfolgerabbildung injektiv ist, seien Anzahlklassen ${}[T_{1}]$ und ${}[T_{2}]$ gegeben mit

{}[T_{1}]'=[T_{2}]'\,.

D.h. es gibt Elemente ${}x_{1},x_{2}\in M$ mit ${}x_{1}\not \in T_{1}$ und ${}x_{2}\not \in T_{2}$ und eine Bijektion

\varphi \colon T_{1}\cup \{x_{1}\}\longrightarrow T_{2}\cup \{x_{2}\}.

Es sei ${}\varphi (x_{1})=y$ . Bei ${}y\in T_{2}$ kann man eine Bijektion

\psi \colon T_{2}\cup \{x_{2}\}\longrightarrow T_{2}\cup \{x_{2}\}

konstruieren, die ${}y$ und ${}x_{2}$ vertauscht. Dann ist ${}\psi \circ \varphi$ eine Bijektion der beiden Mengen, die ${}x_{1}$ auf ${}x_{2}$ schickt. Wir können also von vornherein annehmen, dass ${}\varphi (x_{1})=x_{2}$ ist. Dann stiftet ${}\varphi$ eingeschränkt auf ${}T_{1}$ eine Bijektion zwischen ${}T_{1}$ und ${}T_{2}$ , sodass ${}[T_{1}]=[T_{2}]$ ist.

Zum Nachweis der Induktionseigenschaft sei ${}U\subseteq \mathbb {N} _{M}$ eine Teilmenge, die ${}0=[\emptyset ]$ und mit jeder Anzahl ${}[T]$ auch die Nachfolgeranzahl ${}[T]'$ enthält. Wir müssen zeigen, dass für jede endliche Menge ${}S\subset M$ die zugehörige Anzahlklasse ${}[S]$ zu ${}U$ gehört. Dies beweisen wir über den induktiven Aufbau der endlichen Mengen. Wenn ${}S=\emptyset$ ist, so ist ${}S\in U$ nach Voraussetzung. Es sei die Aussage nun schon für eine Menge ${}S$ bewiesen und sei ${}x\in M$ , ${}x\not \in S$ mit der Erweiterungsmenge ${}S\cup \{x\}$ . Dann gibt es eine Bijektion