Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 1

Ungewöhnliche Zeiten erfordern ungewöhnliche Maßnahmen. Bei all dieser sozialen Distanz sehnt sich der Mensch nach Nähe und Wärme. Deshalb ist uns ein Vorlesungshund zugelaufen. Sie heißt Vorli.

Endliche Mengen

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 [[Abbildung/Hintereinanderschaltung/Injektiv surjektiv bijektiv/Fakt|Kurs:Mathematik für Anwender (Osnabrück 2023-2024)/Abbildung/Hintereinanderschaltung/Injektiv surjektiv bijektiv/Fakt/Faktreferenznummer (Mathematik für Anwender (Osnabrück 2023-2024))  (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$, so dass 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 Lemma 1.2 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 1.4 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 Lemma 1.2 ${}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 1.19 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, so dass nach der Induktionsvoraussetzung hier eine Bijektion vorliegt. Damit ist auch die ursprüngliche Abbildung eine Bijektion.

$\Box$

Endliche Mengen und die Verknüpfungen auf ${}\mathbb {N}$

Wir überlegen uns nun, wie die üblichen Verknüpfungen auf den natürlichen Zahlen, die Addition und die Multiplikation, mit mengentheoretischen Verknüpfungen von endlichen Mengen zusammenhängen. Man kann sich darüber streiten, was man als Definition für diese Verknüpfungen nimmt und was dann eine zu beweisende Aussage ist. Für eine axiomatische Behandlung ist es insgesamt vorteilhaft, diese Verknüpfungen auf die Nachfolgerabbildung zurückzuführen und induktiv zu begründen, siehe dazu den Anhang. Die Summe ${}n+m$ ist in diesem Zugang als der ${}m$-te Nachfolger von ${}n$ definiert, das Produkt ${}n\cdot m$ als die ${}n$-fache Summe von ${}m$ mit sich selbst. Die inhaltliche Bedeutung dieser Verknüpfungen wird in den folgenden Aussagen beschrieben.

Lemma

Es seien ${}M$ und ${}N$ disjunkte endliche Mengen mit ${}m$ bzw. ${}n$ Elementen.

Dann besitzt ihre Vereinigung ${}M\cup N$ gerade ${}m+n$ Elemente.

Beweis

Die Voraussetzung besagt, dass es eine bijektive Abbildung

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

und eine bijektive Abbildung

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

gibt. Die Abbildung

${\{1,\ldots ,n\}}\longrightarrow \{m+1,\ldots ,m+n\},\,i\longmapsto m+i,$

ist nach Aufgabe 1.6 bijektiv, sei ${}\theta$ die Umkehrabbildung. Somit ist nach [[Abbildung/Hintereinanderschaltung/Injektiv surjektiv bijektiv/Fakt|Kurs:Mathematik für Anwender (Osnabrück 2023-2024)/Abbildung/Hintereinanderschaltung/Injektiv surjektiv bijektiv/Fakt/Faktreferenznummer (Mathematik für Anwender (Osnabrück 2023-2024))  (3)]]

$\varphi \circ \theta \colon \{m+1,\ldots ,m+n\}\longrightarrow N$

ebenfalls bijektiv. Wir definieren nun eine Abbildung

$F\colon \{1,\ldots ,m+n\}\longrightarrow M\cup N$

durch

${}F(k)={\begin{cases}\psi (k),{\text{ falls }}k\in \{1,\ldots ,m\}\,,\\\varphi (\theta (k)),{\text{ falls }}k\in \{m+1,\ldots ,m+n\}\,.\end{cases}}\,$

Diese Abbildung ist surjektiv, da jedes Element aus ${}M$ durch den ersten Fall und jedes Element aus ${}N$ durch den zweiten Fall abgedeckt ist. Die Injektivität sieht man so. Wenn

${}k\neq \ell \,$

gegeben sind, und das eine Element zu ${}\{1,\ldots ,m\}$ und das andere zu ${}\{m+1,\ldots ,m+n\}$ gehört, so ist ${}F(k)\in M$ und ${}F(\ell )\in N$ (oder umgekehrt) und sie sind verschieden wegen der Disjunktheit von ${}M$ und ${}N$. Wenn hingegen ${}k$ und ${}\ell$ aus der gleichen Teilmenge des Definitionsbereiches kommen, so ergibt sich die Verschiedenheit von ${}F(k)$ und ${}F(\ell )$ aus der Injektivität von ${}\psi$ bzw. von ${}\varphi \circ \theta$. Insgesamt erhalten wir also eine bijektive Abbildung

$\{1,\ldots ,m+n\}\longrightarrow M\cup N,$

so dass die Anzahl von ${}M\cup N$ gleich ${}m+n$ ist.

$\Box$

Satz

Es seien ${}M$ und ${}N$ endliche Mengen mit ${}m$ bzw. ${}n$ Elementen.

Dann besitzt die Produktmenge ${}M\times N$ genau ${}m\cdot n$ Elemente.

Beweis

Wir führen Induktion über ${}m$, also die Anzahl von ${}M$. Wenn ${}m=0$ ist, so ist ${}M$ leer und damit ist auch die Produktmenge leer, hat also ebenfalls ${}0$ Elemente, was nach Lemma Anhang 1.9  (1) mit dem Produkt übereinstimmt. Dies sichert den Induktionsanfang. Wenn ${}m=1$ ist, so besteht ${}M$ aus genau einem Element, sagen wir ${}x$, und alle Elemente der Produktmenge haben die Form ${}(x,y)$ mit diesem einen ${}x$ und einem beliebigen ${}y\in N$. Somit ist

$N\longrightarrow M\times N,\,y\longmapsto (x,y),$

eine bijektive Abbildung und ${}M\times N$ hat genau so viele Elemente wie ${}N$, nämlich ${}n$. Dies stimmt nach Lemma Anhang 1.9  (2) mit dem Produkt ${}1\cdot n$ überein. Es sei nun die Aussage für alle Mengen ${}M$ mit ${}m$ Elementen (und beliebige endliche Mengen ${}N$) bewiesen und es liege eine ${}(m+1)$-elementige Menge ${}M$ vor. Es sei ${}x\in M$ ein fixiertes Element und wir betrachten die disjunkte Zerlegung

${}M=(M\setminus \{x\})\cup \{x\}\,.$

Die Menge ${}M\setminus \{x\}$ besitzt dann ${}m$ Elemente, so dass wir auf diese Menge die Induktionsvoraussetzung anwenden können. Ferner ist

${}M\times N={\left((M\setminus \{x\})\times N\right)}\cup {\left(\{x\}\times N\right)}\,$

und diese Vereinigung ist disjunkt (die erste Komponente eines Paares ist entweder ${}x$ oder nicht ${}x$). Daher ist nach Lemma 1.6 die Anzahl von ${}M\times N$ gleich der Summe der Anzahlen der beiden Bestandteile, also nach der Induktionsvoraussetzung, dem einelementigen Spezialfall und Lemma Anhang 1.9  (3) gleich

${}m\cdot n+n=(m+1)\cdot n\,.$

$\Box$

Das Distributivgesetz illustriert anhand der Interpretation der Multiplikation als Anzahl einer Produktmenge.

Wir geben noch einen zweiten Beweis für die vorstehende Aussage.

Wir behaupten, dass die Abbildung

$\psi \colon \{1,\ldots ,m\}\times {\{1,\ldots ,n\}}\longrightarrow \{1,2,\ldots ,mn\},\,(i,j)\longmapsto (i-1)n+j,$

bijektiv ist. Zum Beweis der Surjektivität sei ${}z\in \{1,2,\ldots ,mn\}$ vorgegeben. Dieses (ganzzahlige) Intervall kann man in die disjunkten Intervalle

$\{1,\ldots ,n\}\cup \{n+1,\ldots ,2n\}\cup \{2n+1,\ldots ,3n\}\cup \ldots \cup \{(m-1)n+1,\ldots ,mn\}$

unterteilen. Das Element ${}z$ gehört somit zu einem dieser Intervalle, d.h. es gibt ein ${}i$ mit

${}z\in \{(i-1)n+1,\ldots ,in\}\,$

mit ${}i$ zwischen ${}1$ und ${}m$. Dann ist

${}z=(i-1)n+j\,$

mit einem ${}j$ zwischen ${}1$ und ${}n$ und gehört somit zum Bild. Zum Beweis der Injektivität seien

${}(i,j),(k,\ell )\in \{1,\ldots ,m\}\times {\{1,\ldots ,n\}}\,$

gegeben, die auf das gleiche Element abbilden. Es gilt also

${}(i-1)n+j=(k-1)n+\ell \,.$

Da ${}j$ und ${}\ell$ beide zu ${}{\{1,\ldots ,n\}}$ gehören, sind die Summen jeweils maximal gleich ${}in$ bzw. ${}kn$. Daher können die Zahlen nur dann gleich sein, wenn

${}i=k\,$

und dann nach der Abziehregel auch

${}j=\ell \,$

ist.

Fußnoten

Kurs:Diskrete Mathematik (Osnabrück 2020) | >> PDF-Version dieser Vorlesung Arbeitsblatt zur Vorlesung (PDF)