Endliche Mengen und Gleichmächtigkeit/Äquivalenzrelation/Natürliche Anzahl/Textabschnitt

Definition (Gleichmächtigkeit von Mengen)

Zwei Mengen ${}L$ und ${}M$ heißen gleichmächtig, wenn es eine bijektive Abbildung

$\varphi \colon L\longrightarrow M$

gibt.

Definition

Es sei ${}M$ eine Menge. Die Menge ${}{\mathcal {E}}(M)$ der endlichen Teilmengen von ${}M$ wird folgendermaßen festgelegt.

1. ${}\emptyset \in {\mathcal {E}}(M)$,
2. Für jede Teilmenge ${}T\subseteq M$ und jedes ${}x\in M$ gilt: wenn ${}T\in {\mathcal {E}}(M)$ ist, dann ist auch ${}T\cup \{x\}\in {\mathcal {E}}(M)$.
3. Zu ${}{\mathcal {E}}(M)$ gehören nur solche Mengen, die aufgrund von (1) und (2) dazugehören.

Das heißt einfach, dass die leere Menge endlich ist und dass eine endliche Menge, zu der man ein beliebiges Element dazu tut, endlich bleibt. Die zweite Eigenschaft kann man das Induktionsprinzip für endliche Mengen nennen. Die dritte Bedingung besagt, dass eine Menge nur dann endlich ist, wenn sie aus der leeren Menge durch sukzessive Hinzunahme von einzelnen Elementen entsteht. Wenn man die Formulierung in (3) vermeiden möchte, so kann man die Menge der endlichen Mengen definieren als den Durchschnitt von allen Teilmengen der Potenzmengen, die die leere Menge enthalten und die abgeschlossen unter der Hinzunahme von einem Element sind.

Eine Menge ${}M$ heißt unendlich, wenn sie nicht zu den eben definierten endlichen Teilmengen von ${}M$ gehört.

Lemma (Beweisprinzip für endliche Mengen)

Es sei ${}M$ eine Menge und zu jeder endlichen Teilmenge ${}T\subseteq M$ sei eine Aussage ${}A(T)$ gegeben. Die beiden folgenden Bedingungen seien erfüllt.

1. ${}A(\emptyset )$ ist wahr.
2. Für jede endliche Menge ${}T\subseteq M$ und jedes Element ${}x\in M$ gilt: wenn ${}A(T)$ wahr ist, dann ist auch ${}A(T\cup \{x\})$ wahr.

Dann gilt ${}A(T)$ für jede endliche Teilmenge ${}T\subseteq M$.

Beweis

Wir betrachten die Menge

${}U={\left\{T\subseteq M\mid T{\text{ ist endlich und }}A(T){\text{ gilt}}\right\}}\,.$

Nach Voraussetzung enthält diese Menge die leere Menge und sie ist abgeschlossen unter der Hinzunahme von einzelnen Elementen. Also muss es sich aufgrund der Definition um die Menge aller endlichen Teilmengen handeln.

$\Box$

Lemma

Es sei ${}M$ eine Menge und ${}E={\mathcal {E}}(M)$ die Menge der endlichen Teilmengen von ${}M$. Dann definiert die Gleichmächtigkeit eine Äquivalenzrelation auf ${}E$.

Beweis

Siehe Aufgabe 3.1.

$\Box$

Definition

Es sei ${}M$ eine unendliche Menge und ${}E={\mathcal {E}}(M)$ die Menge der endlichen Teilmengen von ${}M$. Dann nennt man die Menge der Äquivalenzklassen zur Gleichmächtigkeit die Anzahlmenge (oder die Menge der natürlichen Zahlen zu ${}M$) von ${}M$. Sie wird mit ${}\mathbb {N} (M)$ bezeichnet.

Lemma

Es sei ${}M$ eine Menge und es seien zwei gleichmächtige Teilmengen ${}T_{1}$ und ${}T_{2}$ gegeben. Es seien ${}x_{1},x_{2}\in M$ mit ${}x_{1}\not \in T_{1}$ und ${}x_{2}\not \in T_{2}$. Dann sind auch die Mengen ${}T_{1}\cup \{x_{1}\}$ und ${}T_{2}\cup \{x_{2}\}$ gleichmächtig.

Beweis

Siehe Aufgabe 3.2.

$\Box$

Definition

Es sei ${}M$ eine unendliche Menge und ${}N=N(M)={\mathcal {E}}(M)/\sim$ sei die Anzahlmenge von ${}M$. Dann nennt man die aufgrund von Fakt wohldefinierte Abbildung

$'\colon N\longrightarrow N,\,[T]\longmapsto [T]',$

mit

$[T]'=[T\cup \{x\}],$

wobei ${}x\in M\setminus T$ beliebig ist, die Nachfolgerabbildung.

Lemma

Es sei ${}M$ eine unendliche Menge und ${}\mathbb {N} (M)={\mathcal {E}}(M)/\sim$ sei die Anzahlmenge von ${}M$ zusammen mit der Nachfolgerabbildung ${}'$ und mit ${}0:=[\emptyset ]$.

Dann ist ${}(\mathbb {N} (M),0,')$ ein Peano-Modell für die natürlichen Zahlen.

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

$\psi \colon S\longrightarrow T$

mit ${}[T]\in U$. Nach Voraussetzung ist auch ${}[T]'\in U$. Es sei ${}y\in M$, ${}y\not \in T$, sodass ${}[T]'=[T\cup \{y\}]$ gilt. Die Bijektion ${}\psi$ kann man fortsetzen zu einer Bijektion

$S\cup \{x\}\longrightarrow T\cup \{y\}.$

Daher ist

${}[S\cup \{x\}]=[T\cup \{y\}]=[T]'\,.$

$\Box$