E-Book, Deutsch, 147 Seiten
Reihe: De Gruyter Studium
Hower Diskrete Mathematik
2. erweiterte und verbesserte Auflage 2021
ISBN: 978-3-11-069567-0
Verlag: De Gruyter
Format: EPUB
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
Grundlage der Informatik
E-Book, Deutsch, 147 Seiten
Reihe: De Gruyter Studium
ISBN: 978-3-11-069567-0
Verlag: De Gruyter
Format: EPUB
Kopierschutz: Adobe DRM (»Systemvoraussetzungen)
Zielgruppe
Studenten der Informatik (Hochschulen und Universitäten). / Students of informatics.
Autoren/Hrsg.
Fachgebiete
Weitere Infos & Material
2 Mengen-Lehre
Hier legen wir die Basis einer vernu¨nftigen Mengen-Lehre, fu¨hren die fu¨r uns wichtigsten Begriffe ein und listen die ga¨ngisten Gesetzma¨ßigkeiten auf. Sodann definieren wir die Gro¨ßen-Ordnung einer Menge und beleuchten Gemeinsamkeiten von und Unterschiede zwischen endlichen und unendlichen Mengen. Die am Ende des Kapitels diskutierte Unendlichkeit bereitet die Unberechenbarkeit in der Theoretischen Informatik vor. Letztlich schrecken wir auch nicht vor der Verallgemeinerten Kontinuums-Hypothese zuru¨ck.
2.1 Grundlagen
Eine Standard-Menge S ist eine Ansammlung einzigartiger Elemente, ohne Kopien. Manchmal jedoch braucht man die Funktionalita¨t des Mehrfach-Vorhandenseins von Elementen; eine solche Struktur nennt man im Englischen multi-set (Kopien erlaubt).1 Dann interessiert man sich auch fu¨r die Anzahl des Auftretens der jeweiligen Elemente: diese bezeichnet man als die entsprechende Multiplizita¨t2. Die spezielle Menge mit genau einem Element nennt man englisch-sprachig singleton.
Wir fu¨hren nun eine Bezeichnung fu¨r die „Ma¨chtigkeit” einer Menge S ein ? deren Kardinal-Zahl, knackiger Kardinalita¨t genannt: |S|. Sie bezeichnet im Endlichen die Anzahl („#”) der Elemente und im Unendlichen deren sogenannte Gro¨ßen-Ordnung. Die kleinste Menge, die leere Menge { } =: Ø, hat selbstversta¨ndlich die kleinste Kardinalita¨t:
Eine Menge heißt abza¨hlbar unendlich, wenn es eine Bijektion mit N gibt. (Am Ende dieses Abschnittes sehen wir, dass dies nur die erste Stufe der Unendlichkeit darstellt.) Eine Menge Sc ist abza¨hlbar3, wenn es nicht daru¨ber hinaus geht ( |Sc| = |N| ) :
| • | 0 | = | |Sc| | = | i[?N] | < | |N| | : | Sc endlich | ; |
| • | 0 | = | i[?N] | < | |Sc| | = | |N| | : | Sc unendlich | . |
Kommen wir nun zu etwas ganz Fundamentalem im Bereich Mengen und Funktionen :
Im Endlichen ist es klar: Wenn die Anzahl der Elemente in den Mengen verschieden ist, hat nicht jedes Element aus der gro¨ßeren Menge eine/n exklusive/n Partner/in in der kleineren;4 es gibt keine Bijektion. Hat aber jede Menge die gleiche Elemente-Anzahl, so ka¨me auf jedes Element ein Partner5-Element; es gibt eine Bijektion, mindestens6 1.
Im Unendlichen geht’s wilder zu: Hier schafft man in bestimmten Konstellationen eine Bijektion, selbst wenn eine Menge auf den ersten naiven Blick weniger Elemente zu haben scheint als die andere, wie dies ja bei einer echten (hier unendlich großen) Teilmenge7 (ihrer Obermenge8) zuna¨chst aussieht ? Beispiel:
Sei E[?N] := Menge der geraden9 natu¨rlichen Zahlen; dann gilt folgender Sachverhalt:
Die bijektive Funktion f ko¨nnte so aussehen: f : E ? N :
Gehen wir auf die beiden Merkmale Injektivita¨t und Surjektivita¨t ein: Verschiedene gerade Zahlen bekommen unterschiedliche natu¨rliche Zahlen injektiv zugeordnet. Es wird kein n vergessen; jede natu¨rliche Zahl wird von einer geraden Zahl als Funktions-Wert surjektiv erreicht. Wir sehen: beide Mengen (echte Teil- und Ober-Menge) sind gleich-„ma¨chtig”10 ? sie haben die gleiche Gro¨ßen-Ordnung.11
Dass der Vergleich der jeweiligen Kardinalita¨t zweier unendlich großer Mengen auch ganz anders ausgehen kann, zeigt folgender Passus:
Eine ganz wichtige Menge ist die Menge aller Teilmengen12 einer (Grund-)Menge S ? „power set”13 P(S) := {s| s ? S} ? in manchen Werken mit 2S bezeichnet, u. a. aus folgendem Grund: Gegeben |S|; dann gilt fu¨r endliche Mengen folgende Behauptung14:
Folgende weiterfu¨hrende Tatsache, welche sowohl fu¨r endliche als auch fu¨r unendliche Mengen gilt, hat fundamentale Bedeutung fu¨r unser Ende ( des Kapitels) :
Im Endlichen ist dies leicht einzusehen: Jedes vorhandene Element aus S la¨sst sich jeweils in ein „singleton” in P(S) stecken, dazu kommt mindestens noch die leere Menge (die kein Element entha¨lt), welche immer Teilmenge jeder beliebigen Menge S (auch sich selbst gegenu¨ber) und damit ein weiteres Element von P(S) ist.
Im Unendlichen bedeutet die „>”-Aussage, dass es eine15 „ho¨here” Unendlichkeit geben muss als die der Menge (S :=) N der Natu¨rlichen Zahlen. Genau hier liegt die Quelle der Unberechenbarkeit in der Theoretischen Informatik ? die leichter zu verstehen ist, wenn man, wie im laufenden Kapitel, fru¨hzeitig die Basis legt. Im Gegensatz zu nur abza¨hlbar unendlich großen Mengen (wie N und die eben definierte Menge E), welche bijektiv aufeinander abbildbar sind, ist die angedeutete ? unendlich große ? „power set” P(N) ein Beispiel fu¨r eine sogenannte „u¨ber-abza¨hlbare” Menge: Die nur abza¨hlbar unendlich vielen natu¨rlichen Zahlen reichen nicht aus, um jedem Element aus der Menge aller Teilmengen von N ein Element aus N bijektiv zuzuordnen; diese beiden Mengen sind unterschiedlich ma¨chtig, haben also verschiedene Gro¨ßen-Ordnungen. Dazu spa¨ter mehr im Abschnitt 2.5 (auf Seite 27).
2.2 Begriffe
Wir beginnen sinnigerweise mit dem bereits angesprochenen Konzept der Teilmenge :
Fu¨r deren Kardinalita¨ten gilt ganz offensichtlich: |A| = |B| .
Da A und B identisch sein ko¨nnen, sprechen wir auch von unechter Teil-Menge.
Wenn dieser Spezial-Fall ausgeschlossen ist, nennt man die Mengen-Inklusion echt :
Im Endlichen hat die echte Teilmenge weniger Elemente als die „u¨bergeordnete” Menge: |A| < |B|. Im Unendlichen kann sie gleich-ma¨chtig sein ? siehe Abschnitt 2.1, Seite 14.
Die gegenla¨ufige Beziehung heißt Obermenge :
Fu¨r deren Kardinalita¨ten gilt ganz offensichtlich: |A| = |B| .
Da A und B identisch sein ko¨nnen, sprechen wir auch von unechter Ober-Menge.
Wenn dieser Spezial-Fall ausgeschlossen ist, handelt es sich um eine echte Obermenge:
