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

Aus Wikiversity
Zur Navigation springen Zur Suche springen
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 in eine eindeutige Beziehung setzen (nummerieren) können. Für uns gehört die zu den natürlichen Zahlen, der Zählvorgang beginnt aber natürlich mit der . 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.

Appelbijektion1.png

Definition  

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

gibt.

Die leere Menge besitzt Elemente, dies ist der entscheidende Grund, warum wir die 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 unabhängig von den möglichen Zählreihenfolgen ist. Für den Nachfolger einer natürlichen Zahl schreiben wir zunächst kurz statt , da die Addition für die folgenden Überlegungen nicht nötig ist. Die Beziehung zwischen natürlichen Zahlen bedeutet, dass im Abzählprozess der natürlichen Zahlen später als kommt.



Lemma  

Es sei eine natürliche Zahl mit dem Vorgänger , es sei also . Es sei ein fixiertes Element.

Dann gibt es eine bijektive Abbildung zwischen und .

Beweis  

Wir definieren eine Abbildung

durch

Dies ist eine wohldefinierte Abbildung, da die Bilder echt unterhalb von oder echt oberhalb von liegen, niemals aber gleich sind, und da maximal der Nachfolger von , also erreicht wird.

Die Abbildung ist injektiv: Wenn und beide unterhalb von liegen, so werden beide Elemente auf sich selbst abgebildet. Wenn beide oberhalb von 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 unterhalb von und oberhalb von (oder umgekehrt) liegt, so ist erst recht oberhalb von und somit von verschieden.

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

mit oberhalb von (einschließlich ) und echt unterhalb von , also maximal gleich schreiben. Insgesamt ist also eine Bijektion.


VerschiedeneNummerierungen.png



Lemma  

Wenn eine Menge ist und wenn

und

bijektive Abbildungen sind,

so ist

Die Anzahl einer endlichen Menge ist also wohldefiniert.

Beweis  

Seien die bijektiven Abbildungen

und

gegeben. Da man bijektive Abbildungen umkehren kann und da die Hintereinanderschaltung von bijektiven Abbildungen nach Aufgabe 3.27 (Mathematik für Anwender (Osnabrück 2019-2020))  (3) wieder bijektiv ist, ist auch

bijektiv. Wir müssen also nur die endlichen Standardmengen untereinander vergleichen. Wir müssen also zeigen, dass wenn eine bijektive Abbildung

vorliegt, dass dann

ist. Dies zeigen wir durch Induktion nach . Wenn ist, so ist die Menge links leer und somit muss auch die rechte Menge leer sein, also ist dann auch . Seien nun nicht , so dass sie also jeweils einen Vorgänger haben. Es sei der Vorgänger von und der Vorgänger von . Diese Zahlen sind eindeutig bestimmt, da die Nachfolgerabbildung injektiv ist. Wir setzen

Dann gibt es nach der Herausnahme von bzw. eine bijektive Abbildung

Nach Lemma 1.2 gibt es eine bijektive Abbildung zwischen und . Somit gibt es dann auch insgesamt eine bijektive Abbildung zwischen und . Nach Induktionsvoraussetzung ist , also auch


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

Die natürliche Zahl heißt die Anzahl (oder die Kardinalität) der Menge. Sie wird mit oder mit bezeichnet. Die bijektive Abbildung

nennt man eine Nummerierung der Menge . Eine Menge besitzt also Elemente, wenn man sie mit den natürlichen Zahlen von bis durchnummerieren kann. Die Mengen 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 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. Man spricht vom Bijektivitätsprinzip. Wenn man sich für die Anzahl einer Menge interessiert, und weiß, dass diese in eine Bijektion zu einer anderen Menge gebracht werden kann, so kann man genau so gut die Anzahl von bestimmen. Eine Menge, die nicht endlich ist, für die es also keine Bijektion mit für irgendein 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 1.4 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 Lemma 1.2 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 1.19 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.




Endliche Mengen und die Verknüpfungen auf

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 ist in diesem Zugang als der -te Nachfolger von definiert, das Produkt als die -fache Summe von mit sich selbst. Die inhaltliche Bedeutung dieser Verknüpfungen wird in den folgenden Aussagen beschrieben.



Lemma  

Es seien und disjunkte endliche Mengen mit bzw. Elementen.

Dann besitzt ihre Vereinigung gerade Elemente.

Beweis  

Die Voraussetzung besagt, dass es eine bijektive Abbildung

und eine bijektive Abbildung

gibt. Die Abbildung

ist nach Aufgabe 1.6 bijektiv, sei die Umkehrabbildung. Somit ist nach Aufgabe 3.27 (Mathematik für Anwender (Osnabrück 2019-2020))  (3)

ebenfalls bijektiv. Wir definieren nun eine Abbildung

durch

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

gegeben sind, und das eine Element zu und das andere zu gehört, so ist und (oder umgekehrt) und sie sind verschieden wegen der Disjunktheit von und . Wenn hingegen und aus der gleichen Teilmenge des Definitionsbereiches kommen, so ergibt sich die Verschiedenheit von und aus der Injektivität von bzw. von . Insgesamt erhalten wir also eine bijektive Abbildung

so dass die Anzahl von gleich ist.


Aples.svg



Satz  

Es seien und endliche Mengen mit bzw. Elementen.

Dann besitzt die Produktmenge genau Elemente.

Beweis  

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

eine bijektive Abbildung und hat genau so viele Elemente wie , nämlich . Dies stimmt nach Lemma Anhang 1.9  (2) mit dem Produkt überein. Sei nun die Aussage für alle Mengen mit Elementen (und beliebige endliche Mengen ) bewiesen und es liege eine -elementige Menge vor. Es sei ein fixiertes Element und wir betrachten die disjunkte Zerlegung

Die Menge besitzt dann Elemente, so dass wir auf diese Menge die Induktionsvoraussetzung anwenden können. Ferner ist

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


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[1]

bijektiv ist. Zum Beweis der Surjektivität sei vorgegeben. Dieses (ganzzahlige) Intervall kann man in die disjunkten Intervalle

unterteilen. Das Element gehört somit zu einem dieser Intervalle, d.h. es gibt ein mit

mit zwischen und . Dann ist

mit einem zwischen und und gehört somit zum Bild. Zum Beweis der Injektivität seien

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

Da und beide zu gehören, sind die Summen jeweils maximal gleich bzw. . Daher können die Zahlen nur dann gleich sein, wenn

und dann nach der Abziehregel auch

ist.




Fußnoten
  1. Der Ausdruck bezeichnet hier den Vorgänger von , die Subtraktion haben wir noch nicht eingeführt.


Kurs:Diskrete Mathematik (Osnabrück 2020) | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)