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

Aus Wikiversity


Definition (Gleichmächtigkeit von Mengen)  

Zwei Mengen und heißen gleichmächtig, wenn es eine bijektive Abbildung

gibt.


Definition  

Es sei eine Menge. Die Menge der endlichen Teilmengen von wird folgendermaßen festgelegt.

  1. ,
  2. Für jede Teilmenge und jedes gilt: wenn ist, dann ist auch .
  3. Zu 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 heißt unendlich, wenn sie nicht zu den eben definierten endlichen Teilmengen von gehört.



Lemma (Beweisprinzip für endliche Mengen)  

Es sei eine Menge und zu jeder endlichen Teilmenge sei eine Aussage gegeben. Die beiden folgenden Bedingungen seien erfüllt.

  1. ist wahr.
  2. Für jede endliche Menge und jedes Element gilt: wenn wahr ist, dann ist auch wahr.

Dann gilt für jede endliche Teilmenge .

Beweis  

Wir betrachten die Menge

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.



Lemma

Es sei eine Menge und die Menge der endlichen Teilmengen von . Dann definiert die Gleichmächtigkeit eine Äquivalenzrelation auf .

Beweis

Siehe Aufgabe 3.1.



Definition  

Es sei eine unendliche Menge und die Menge der endlichen Teilmengen von . Dann nennt man die Menge der Äquivalenzklassen zur Gleichmächtigkeit die Anzahlmenge (oder die Menge der natürlichen Zahlen zu ) von . Sie wird mit bezeichnet.



Lemma

Es sei eine Menge und es seien zwei gleichmächtige Teilmengen und gegeben. Es seien mit und . Dann sind auch die Mengen und gleichmächtig.

Beweis

Siehe Aufgabe 3.2.



Definition  

Es sei eine unendliche Menge und sei die Anzahlmenge von . Dann nennt man die aufgrund von Fakt wohldefinierte Abbildung

mit
wobei beliebig ist, die Nachfolgerabbildung.



Lemma  

Es sei eine unendliche Menge und sei die Anzahlmenge von zusammen mit der Nachfolgerabbildung und mit .

Dann ist ein Peano-Modell für die natürlichen Zahlen.

Beweis  

Zunächst ist nicht Nachfolger einer Anzahlklasse . Denn andernfalls gebe es eine Teilmenge und ein Element , und eine Bijektion

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

Um zu zeigen, dass die Nachfolgerabbildung injektiv ist, seien Anzahlklassen und gegeben mit

D.h. es gibt Elemente mit und und eine Bijektion

Es sei . Bei kann man eine Bijektion

konstruieren, die und vertauscht. Dann ist eine Bijektion der beiden Mengen, die auf schickt. Wir können also von vornherein annehmen, dass ist. Dann stiftet eingeschränkt auf eine Bijektion zwischen und , so dass ist.

Zum Nachweis der Induktionseigenschaft sei eine Teilmenge, die und mit jeder Anzahl auch die Nachfolgeranzahl enthält. Wir müssen zeigen, dass für jede endliche Menge die zugehörige Anzahlklasse zu gehört. Dies beweisen wir über den induktiven Aufbau der endlichen Mengen. Wenn ist, so ist nach Voraussetzung. Es sei die Aussage nun schon für eine Menge bewiesen und sei , mit der Erweiterungsmenge . Dann gibt es eine Bijektion

mit . Nach Voraussetzung ist auch . Es sei , , so dass gilt. Die Bijektion kann man fortsetzen zu einer Bijektion

Daher ist