Kurs:Diskrete Mathematik (Osnabrück 2020)/Vorlesung 1
- 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.
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.
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 .
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.
Wenn eine Menge ist und wenn
und
bijektive Abbildungen sind,
so ist
Die Anzahl einer endlichen Menge ist also wohldefiniert.
Es seien die bijektiven Abbildungen
und
gegeben. Da man bijektive Abbildungen umkehren kann und da die Hintereinanderschaltung von bijektiven Abbildungen nach Aufgabe 3.28 (Mathematik für Anwender (Osnabrück 2023-2024)) (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 . Es seien nun nicht , sodass 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
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.
Es sei eine endliche Menge mit Elementen und eine endliche Menge mit Elementen. Es sei .
Dann gibt es keine injektive Abbildung
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.
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.
Seien und endliche Mengen mit Elementen. Dann sind für eine Abbildung
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. Es 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. Es 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.
Es 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, sodass 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.
Es seien und disjunkte endliche Mengen mit bzw. Elementen.
Dann besitzt ihre Vereinigung gerade Elemente.
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.28 (Mathematik für Anwender (Osnabrück 2023-2024)) (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
sodass die Anzahl von gleich ist.
Es seien und endliche Mengen mit bzw. Elementen.
Dann besitzt die Produktmenge genau Elemente.
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. Es 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, sodass 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
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
- ↑ Der Ausdruck bezeichnet hier den Vorgänger von , die Subtraktion haben wir noch nicht eingeführt.
Kurs:Diskrete Mathematik (Osnabrück 2020) | >> |
---|