Endliche Mengen/Einführung mit 1...n/Textabschnitt

Aus Wikiversity
Zur Navigation springen Zur Suche springen


Definition  

Eine Menge heißt endlich mit Elementen, wenn es eine Bijektion

gibt.

Die natürliche Zahl ist dabei nach Aufgabe eindeutig bestimmt und heißt die Anzahl (oder die Kardinalität) der Menge. Sie wird mit oder mit bezeichnet. Die bijektive Abbildung

kann man eine Nummerierung der Menge nennen. Eine Menge besitzt also Elemente, wenn man sie mit den natürlichen Zahlen von bis durchnummerieren kann. Zwei endliche Mengen und , für die es eine Bijektion

gibt, besitzen die gleiche Anzahl. Dies beruht einfach darauf, dass diese Bijektion verknüpft mit der bijektiven Nummerierung wieder eine Bijektion ist. Eine Menge, die nicht endlich ist, für die es also keine Bijektion mit für kein gibt, heißt unendlich.



Lemma  

Es sei eine endliche Menge mit Elementen und eine endliche Menge mit Elementen. Es sei .

Dann gibt es keine injektive Abbildung

Beweis  

 Wir nehmen an, dass es eine injektive Abbildung

gibt. Es sei das Bild von unter der Abbildung . Dann ergibt sich eine Bijektion

da sich die Injektivität überträgt und da eine Abbildung immer surjektiv auf ihr Bild ist. Daher haben und gleich viele Elemente. Nach Aufgabe ist die Anzahl einer Teilmenge stets kleiner oder gleich der Anzahl der Menge. Also ist im Widerspruch zur Voraussetzung.


TooManyPigeons.jpg

Die vorstehende Aussage heißt Schubfachprinzip (oder Taubenschlagprinzip). Es besagt, dass wenn man Tauben auf Plätze verteilt mit , dass dann in mindestens einem Platz mindestens zwei Tauben landen.



Lemma  

Seien und endliche Mengen mit Elementen. Dann sind für eine Abbildung

die Begriffe injektiv, surjektiv und bijektiv äquivalent.

Beweis  

Wir führen Induktion über die Anzahl der beiden Mengen und . Bei gibt es nur die leere Abbildung (von der leeren Menge in die leere Menge), und diese erfüllt alle drei Eigenschaften. Sei nun und die Aussage für alle endlichen Mengen mit einer Anzahl bewiesen. Es muss lediglich die Äquivalenz von injektiv und surjektiv gezeigt werden. Sei zunächst injektiv. Wir wählen ein Element und setzen . Wir setzen

Beide Mengen haben nach Fakt Elemente, und somit kann man darauf die Induktionsvoraussetzung anwenden. Es sei

Diese Abbildung ist wohldefiniert, da wegen der Injektivität nur das Element auf abgebildet wird, alle anderen Elemente aus werden auf andere Elemente abgebildet, d.h. sie landen in . Die Injektivität von überträgt sich auf die Teilmenge . Nach der Induktionsvoraussetzung ist also surjektiv. Damit ist aber insgesamt surjektiv, da einerseits im Bild liegt (mit als Urbild) und da andererseits jedes Element zu gehört und damit ein Urbild in besitzt.

Sei nun surjektiv. Sei beliebig und . Wir betrachten die Einschränkung

Diese Abbildung kann nicht surjektiv sein. Andernfalls würde sich nämlich der Widerspruch (hier geht auch Aufgabe ein)

ergeben. Daher muss im Bild von fehlen, und das heißt, dass eine surjektive Abbildung

vorliegt. Beide Mengen besitzen Elemente, so dass nach der Induktionsvoraussetzung hier eine Bijektion vorliegt. Damit ist auch die ursprüngliche Abbildung eine Bijektion.