Diskrete Mathematik/Endliche Mengen/Grundtatsachen/Textabschnitt

In der diskreten Mathematik geht es zu einem Großteil um endliche Mengen, ihre Anzahl, mögliche Strukturen wie Relationen, Ordnungen oder Verknüpfungen auf endlichen Mengen, die kombinatorische Relevanz von endlichen Mengen, etc. Es kann gar nicht so einfach sein, die Anzahl einer endlichen Menge zu bestimmen, insbesondere, wenn die Elemente der Menge verschiedene Möglichkeiten, verschiedene Anordnungen oder verschiedene Lösungen zu einem Problem repräsentieren. Bei einem direkt und naiv gestellten Anzahlproblem ist es oft auch gar nicht unmittelbar klar, welche Menge die richtige Modellierung für das Problem ist. Wenn man beispielsweise Kugeln auf Urnen verteilen möchte, so ist die Anzahl der Möglichkeiten dafür abhängig davon, ob man die Kugeln bzw. die Urnen als unterscheidbar oder als nicht unterscheidbar ansieht, wie man Symmetrien berücksichtigt, was man miteinander identifiziert u.s.w.

Zuerst aber soll es hier um den Anzahlbegriff selbst gehen. Wir können einer Menge eine Anzahl zuordnen, weil wir ihre Elemente abzählen, also mit einer Nummer versehen können. Dies setzt voraus, dass wir das Zählen, also das Nachfolgernehmen in den natürlichen Zahlen, beherrschen, und dass wir eine irgendwie gegebene Menge mit einer Menge der Form ${}\{1,2,3,\ldots ,n\}$ in eine eindeutige Beziehung setzen (nummerieren) können. Für uns gehört die ${}0$ zu den natürlichen Zahlen, der Zählvorgang beginnt aber natürlich mit der ${}1$. Neben den natürlichen Zahlen einschließlich dem Beweisverfahren durch Induktion setzen wir einen naiven Mengenbegriff und den Abbildungsbegriff mit den Konzepten injektiv, surjektiv, bijektiv voraus.

Definition

Eine Menge ${}M$ heißt endlich mit ${}n$ Elementen, wenn es eine Bijektion

$\{1,\ldots ,n\}\longrightarrow M$

gibt.

Die leere Menge besitzt ${}0$ Elemente, dies ist der entscheidende Grund, warum wir die ${}0$ zu den natürlichen Zahlen rechnen. In dieser Vorlesung werden wir „intuitiv klare“ Gesetzmäßigkeiten über endliche Mengen beweisen. Dies legt ein sicheres Fundament für das Folgende und ist eine gute Übung im mathematischen Argumentieren. Man sollte also erstmal davon ausgehen, dass gar nichts klar ist und dass alles mit dem obigen Anzahlbegriff erfasst werden muss. Insbesondere ist noch nicht einmal unmittelbar klar, dass die Anzahl einer endlichen Menge wohldefiniert ist, dass also die Zahl ${}n$ unabhängig von den möglichen Zählreihenfolgen ist. Für den Nachfolger einer natürlichen Zahl ${}\ell$ schreiben wir zunächst kurz ${}\ell '$ statt ${}\ell +1$, da die Addition für die folgenden Überlegungen nicht nötig ist. Die Beziehung  ${}m>n$  zwischen natürlichen Zahlen bedeutet, dass im Abzählprozess der natürlichen Zahlen ${}m$ später als ${}n$ kommt.

Lemma

Es sei  ${}k\neq 0$  eine natürliche Zahl mit dem Vorgänger ${}\ell$, es sei also  ${}k=\ell ^{\prime }$.  Es sei  ${}z\in \{1,\ldots ,k\}$  ein fixiertes Element.

Dann gibt es eine bijektive Abbildung zwischen ${}\{1,\ldots ,\ell \}$ und ${}\{1,\ldots ,k\}\setminus \{z\}$.

Beweis

Wir definieren eine Abbildung

$\varphi \colon \{1,\ldots ,\ell \}\longrightarrow \{1,\ldots ,k\}\setminus \{z\}$

durch

$\varphi (x)={\begin{cases}x\,,{\text{ falls }}x{\text{ in der Durchzählung von }}1{\text{ bis }}k{\text{ vor }}z{\text{ kommt}}\,,\\x^{\prime }\,,{\text{ falls }}x{\text{ gleich }}z{\text{ ist oder in der Durchzählung nach }}z{\text{ kommt}}\,.\end{cases}}\,$

Dies ist eine wohldefinierte Abbildung, da die Bilder echt unterhalb von ${}z$ oder echt oberhalb von ${}z$ liegen, niemals aber gleich ${}z$ sind, und da maximal der Nachfolger von ${}\ell$, also ${}k$ erreicht wird.

Die Abbildung ist injektiv: Wenn ${}x$ und ${}y$ beide unterhalb von ${}z$ liegen, so werden beide Elemente auf sich selbst abgebildet. Wenn beide oberhalb von ${}z$ liegen, so werden beide auf ihren Nachfolger abgebildet, und das Nachfolgernehmen ist injektiv (dies ist die Eigenschaft, dass der Vorgänger eindeutig bestimmt ist). Wenn ${}x$ unterhalb von ${}z$ und ${}y$ oberhalb von ${}z$ (oder umgekehrt) liegt, so ist erst recht ${}y^{\prime }$ oberhalb von ${}z$ und somit von ${}x$ verschieden.

Die Abbildung ist auch surjektiv. Die Zahlen echt unterhalb von ${}z$ werden durch sich selbst erreicht und die Zahlen ${}u$ echt oberhalb von ${}z$ (und unterhalb von ${}k$ einschließlich ${}k$) kann man als

${}u=v^{\prime }\,$

mit ${}v$ oberhalb von ${}z$ (einschließlich ${}z$) und echt unterhalb von ${}k$, also maximal gleich ${}\ell$ schreiben. Insgesamt ist ${}\varphi$ also eine Bijektion.

$\Box$

Lemma

Wenn ${}M$ eine Menge ist und wenn

$\varphi \colon {\{1,\ldots ,n\}}\longrightarrow M$

und

$\psi \colon \{1,\ldots ,k\}\longrightarrow M$

bijektive Abbildungen sind,

so ist

${}n=k\,.$

Die Anzahl einer endlichen Menge ist also wohldefiniert.

Beweis

Es seien die bijektiven Abbildungen

$\varphi \colon {\{1,\ldots ,n\}}\longrightarrow M$

und

$\psi \colon \{1,\ldots ,k\}\longrightarrow M$

gegeben. Da man bijektive Abbildungen umkehren kann und da die Hintereinanderschaltung von bijektiven Abbildungen nach Fakt  (3) wieder bijektiv ist, ist auch

$\psi ^{-1}\circ \varphi \colon {\{1,\ldots ,n\}}\longrightarrow \{1,\ldots ,k\}$

bijektiv. Wir müssen also nur die endlichen Standardmengen ${}{\{1,\ldots ,n\}}$ untereinander vergleichen. Wir müssen also zeigen, dass wenn eine bijektive Abbildung

$\theta \colon {\{1,\ldots ,n\}}\longrightarrow \{1,\ldots ,k\}$

vorliegt, dass dann

${}n=k\,$

ist. Dies zeigen wir durch Induktion nach ${}n$. Wenn  ${}n=0$  ist, so ist die Menge links leer und somit muss auch die rechte Menge leer sein, also ist dann auch  ${}k=0$.  Es seien nun ${}n,k$ nicht ${}0$, sodass sie also jeweils einen Vorgänger haben. Es sei ${}m$ der Vorgänger von ${}n$ und ${}\ell$ der Vorgänger von ${}k$. Diese Zahlen sind eindeutig bestimmt, da die Nachfolgerabbildung injektiv ist. Wir setzen

${}z=\theta (n)\in \{1,\ldots ,k\}\,.$

Dann gibt es nach der Herausnahme von ${}n$ bzw. ${}z$ eine bijektive Abbildung

$\{1,\ldots ,m\}={\{1,\ldots ,n\}}\setminus \{n\}\longrightarrow \{1,\ldots ,k\}\setminus \{z\}.$

Nach Fakt gibt es eine bijektive Abbildung zwischen ${}\{1,\ldots ,\ell \}$ und ${}\{1,\ldots ,k\}\setminus \{z\}$. Somit gibt es dann auch insgesamt eine bijektive Abbildung zwischen ${}\{1,\ldots ,m\}$ und ${}\{1,\ldots ,\ell \}$. Nach Induktionsvoraussetzung ist  ${}m=\ell$,  also auch

${}n=m'=\ell '=k\,.$

$\Box$

Eine wilde Menge von Punkten. Über eine gute Nummerierung dieser Menge kann man sich streiten, aber nicht über die Anzahl.

Die natürliche Zahl ${}n$ heißt die Anzahl (oder die Kardinalität) der Menge. Sie wird mit ${}{\#\left(M\right)}$ oder mit ${}\vert {M}\vert$ bezeichnet. Die bijektive Abbildung

$\{1,\ldots ,n\}\longrightarrow M$

nennt man eine Nummerierung der Menge ${}M$. Eine Menge besitzt also ${}n$ Elemente, wenn man sie mit den natürlichen Zahlen von ${}1$ bis ${}n$ durchnummerieren kann. Die Mengen ${}{\{1,\ldots ,n\}}$ dienen also als Standardmenge oder Referenzmenge für endliche Mengen. Für jede endliche Menge gibt es nach Definition zwar eine bijektive Abbildung zu einer solchen Standardmenge, es gibt aber keine optimale oder kanonische bijektive Abbildung zu einer Standardmenge. Zumeist ist die Wahl einer Nummerierung willkürlich, man denke etwa an eine wilde Punktmenge in der Ebene. Insgesamt empfiehlt es sich daher, weitgehend mit beliebigen Mengen zu arbeiten und natürliche Identifizierungen zwischen Mengen zu erkennen, und die Anzahlen durch Rechnungen statt durch Nummerierungen zu bestimmen.

Zwei endliche Mengen ${}M$ und ${}N$, für die es eine Bijektion

$M\longrightarrow N$

gibt, besitzen die gleiche Anzahl. Dies beruht einfach darauf, dass diese Bijektion verknüpft mit der bijektiven Nummerierung wieder eine Bijektion ist. Man spricht vom Bijektivitätsprinzip. Wenn man sich für die Anzahl einer Menge ${}M$ interessiert, und weiß, dass diese in eine Bijektion zu einer anderen Menge ${}N$ gebracht werden kann, so kann man genau so gut die Anzahl von ${}N$ bestimmen. Eine Menge, die nicht endlich ist, für die es also keine Bijektion mit ${}\{1,\ldots ,n\}$ für irgendein ${}n$ gibt, heißt unendlich.

Lemma

Es sei ${}M$ eine endliche Menge mit ${}m$ Elementen und ${}N$ eine endliche Menge mit ${}n$ Elementen. Es sei  ${}m>n$. 

Dann gibt es keine injektive Abbildung

$M\longrightarrow N.$

Beweis

 Wir nehmen an, dass es eine injektive Abbildung

$\varphi \colon M\longrightarrow N$

gibt. Es sei  ${}T=\varphi (M)\subseteq N$  das Bild von ${}M$ unter der Abbildung ${}\varphi$. Dann ergibt sich eine Bijektion

${\tilde {\varphi }}\colon M\longrightarrow T,$

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

$\Box$

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

Lemma

Seien ${}M$ und ${}N$ endliche Mengen mit ${}n$ Elementen. Dann sind für eine Abbildung

$F\colon M\longrightarrow N$

die Begriffe injektiv, surjektiv und bijektiv äquivalent.

Beweis

Wir führen Induktion über die Anzahl ${}n$ der beiden Mengen ${}M$ und ${}N$. Bei  ${}n=0$  gibt es nur die leere Abbildung (von der leeren Menge in die leere Menge), und diese erfüllt alle drei Eigenschaften. Es sei nun  ${}n\geq 1$  und die Aussage für alle endlichen Mengen ${}M$ mit einer Anzahl ${}<n$ bewiesen. Es muss lediglich die Äquivalenz von injektiv und surjektiv gezeigt werden. Es sei zunächst ${}F$ injektiv. Wir wählen ein Element  ${}x\in M$  und setzen  ${}y=F(x)$.  Wir setzen

$M'=M\setminus \{x\}{\text{ und }}N'=N\setminus \{y\}.$

Beide Mengen haben nach Fakt ${}n-1$ Elemente, und somit kann man darauf die Induktionsvoraussetzung anwenden. Es sei

$F'\colon M'\longrightarrow N',\,x\longmapsto F(x).$

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

Es sei nun ${}F$ surjektiv. Sei  ${}x\in M$  beliebig und  ${}y=F(x)$.  Wir betrachten die Einschränkung

$F'\colon M'=M\setminus \{x\}\longrightarrow N.$

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

${}n={\#\left(M\right)}>{\#\left(M\setminus \{x\}\right)}\geq {\#\left(F(M\setminus \{x\})\right)}={\#\left(N\right)}=n\,$

ergeben. Daher muss ${}y$ im Bild von ${}F'$ fehlen, und das heißt, dass eine surjektive Abbildung

$M\setminus \{x\}\longrightarrow N\setminus \{y\}$

vorliegt. Beide Mengen besitzen ${}n-1$ Elemente, sodass nach der Induktionsvoraussetzung hier eine Bijektion vorliegt. Damit ist auch die ursprüngliche Abbildung eine Bijektion.

$\Box$