2 Mengen-Lehre

Hier legen wir die Basis einer vernünftigen Mengen-Lehre, führen die für uns wichtigsten Begriffe ein und listen die gängisten Gesetzmäβigkeiten auf. Sodann definieren wir die Gröβ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 zurück.

2.1 Grundlagen

Eine Standard-Menge S ist eine Ansammlung einzigartiger Elemente, ohne Kopien. Manchmal jedoch braucht man die Funktionalität des Mehrfach-Vorhandenseins von Elementen; eine solche Struktur nennt man im Englischen multi-set (Kopien erlaubt).1 Dann interessiert man sich auch für die Anzahl des Auftretens der jeweiligen Elemente: diese bezeichnet man als die entsprechende Multiplizität2. Die spezielle Menge mit genau einem Element nennt man englisch-sprachig singleton.

Wir führen nun eine Bezeichnung für die „Mächtigkeit” einer Menge S ein ― deren Kardinal-Zahl, knackiger Kardinalität genannt: |S|. Sie bezeichnet im Endlichen die Anzahl („#”) der Elemente und im Unendlichen deren sogenannte Gröβen-Ordnung. Die kleinste Menge, die leere Menge { } =: ∅, hat selbstverständlich die kleinste Kardinalität:

Eine Menge heiβt abzä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 abzählbar3, wenn es nicht darüber hinaus geht ( |Sc| ≤ |N| ) :

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 gröβ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 kä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) zunächst aussieht ― Beispiel:

Sei E[⊂N] := Menge der geraden9 natürlichen Zahlen; dann gilt folgender Sachverhalt:

Die bijektive Funktion f könnte so aussehen: f : E → N :

Gehen wir auf die beiden Merkmale Injektivität und Surjektivität ein: Verschiedene gerade Zahlen bekommen unterschiedliche natürliche Zahlen injektiv zugeordnet. Es wird kein n vergessen; jede natürliche Zahl wird von einer geraden Zahl als Funktions-Wert surjektiv erreicht. Wir sehen: beide Mengen (echte Teil- und Ober-Menge) sind gleich-„mächtig”10 ― sie haben die gleiche Gröβen-Ordnung.11

Dass der Vergleich der jeweiligen Kardinalitä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 für endliche Mengen folgende Behauptung14:

Folgende weiterführende Tatsache, welche sowohl für endliche als auch für unendliche Mengen gilt, hat fundamentale Bedeutung für unser Ende ( des Kapitels) :

Im Endlichen ist dies leicht einzusehen: Jedes vorhandene Element aus S lässt sich jeweils in ein „singleton” in P(S) stecken, dazu kommt mindestens noch die leere Menge (die kein Element enthält), welche immer Teilmenge jeder beliebigen Menge S (auch sich selbst gegenüber) und damit ein weiteres Element von P(S) ist.

Im Unendlichen bedeutet die „>”-Aussage, dass es eine15 „höhere” Unendlichkeit geben muss als die der Menge (S :=) N der Natürlichen Zahlen. Genau hier liegt die Quelle der Unberechenbarkeit in der Theoretischen Informatik ― die leichter zu verstehen ist, wenn man, wie im laufenden Kapitel, frühzeitig die Basis legt. Im Gegensatz zu nur abzä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 für eine sogenannte „über-abzählbare” Menge: Die nur abzählbar unendlich vielen natü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 mächtig, haben also verschiedene Gröβen-Ordnungen. Dazu später mehr im Abschnitt 2.5 (auf Seite 27).

2.2 Begriffe

Wir beginnen sinnigerweise mit dem bereits angesprochenen Konzept der Teilmenge :

Für deren Kardinalitäten gilt ganz offensichtlich: |A| ≤ |B| .

Da A und B identisch sein kö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 „übergeordnete” Menge: |A| < |B|. Im Unendlichen kann sie gleich-mächtig sein ― siehe Abschnitt 2.1, Seite 14.

Die gegenläufige Beziehung heiβt Obermenge :

Für deren Kardinalitäten gilt ganz offensichtlich: |A| ≥ |B| .

Da A und B identisch sein können, sprechen wir auch von unechter Ober-Menge.

Wenn dieser Spezial-Fall ausgeschlossen ist, handelt es sich um eine echte Obermenge: