Menge

Nicht-axiomatische Mengenlehre

Richard Dedekind schrieb 1887, dass es sehr häufig vorkommt, „daß verschiedene Dinge a, b, c ... aus irgendeiner Veranlassung unter einem gemeinsamen Gesichtspunkte aufgefaßt, im Geiste zusammengestellt werden, und man sagt dann, daß sie ein System S bilden; man nennt die Dinge a, b, c ...  die Elemente des Systems, sie sind enthalten in S; umgekehrt besteht S aus diesen Elementen. Ein solches System S (oder ein Inbegriff, eine Mannigfaltigkeit, eine Gesamtheit) ist als Gegenstand unseres Denkens ebenfalls ein Ding; es ist vollständig bestimmt, wenn von jedem Ding bestimmt ist, ob es Element von S ist oder nicht.“ (Dedekind: Was sind und was sollen die Zahlen? §1 Systeme von Elementen, Ziffer 2).

1895 formulierte Georg Cantor: „Unter einer ‚Menge‛ verstehen wir jede Zusammenfassung M von bestimmten wohlunterschiedenen Objecten m unserer Anschauung oder unseres Denkens (welche die ‚Elemente‛ von M genannt werden) zu einem Ganzen.“ (Math. Annalen Bd. 46, S. 481). Oder mit den Worten von Felix Hausdorff (1868−1942): „Eine Menge entsteht durch Zusammenfassung von Einzeldingen zu einem Ganzen. Eine Menge ist eine Vielheit, als Einheit gedacht.“ (Hausdorff: Mengenlehre, Walter de Gruyter & Co. 1935³, S. 11).

Während bei Dedekind grundsätzlich irgendwelche Dinge zu einem System zusammengefasst werden können, darf man laut Cantor nur bestimmte Objekte zu einer Menge zusammenfassen. Am 28. Juli 1899 schrieb Cantor demgemäß in einem Brief an Dedekind: „Eine Vielheit kann nämlich so beschaffen sein, daß die Annahme eines ‚Zusammenseins‛ aller ihrer Elemente auf einen Widerspruch führt, so daß es unmöglich ist, die Vielheit als eine Einheit, als ‚ein fertiges Ding‛ aufzufassen. ... Wie man sich leicht überzeugt, ist z.B. der ‚Inbegriff alles Denkbaren‛ eine solche Vielheit.“

Auch die Vielheit aller Mengen, heute „Allklasse“ genannt, ist keine Menge (vgl. den folgenden Abschnitt: Widersprüche!). Um diese Aussage zu verstehen, muss man garnicht wissen, was eine Menge „eigentlich“ ist. Man postuliert vielmehr die Existenz von Mengen und die Gültigkeit formaler Regeln, die im Mengenuniversum gelten sollen und kann dann beweisen, dass die Allklasse diesen Regeln nicht gehorcht (→ Zermelo-Fraenkel’sches Axiomensystem).

In naiver Weise können Mengen auf verschiedene Weise dargestellt werden: eine Menge verschiedenfarbiger Kugeln etwa durch ein Bild,

die Menge aller Primzahlen zwischen 0 und 20 in aufzählender Form,

M₂ = { 2, 3, 5, 7, 11, 13, 17, 19 }

oder die Menge bestimmter Objekte durch deren Eigenschaft:

M₃ = { x ∈∈ M₂ | x < 10 }.

In der Menge M₃ sind all diejenigen Elemente aus M₂ enthalten, die kleiner als 10 sind.

Bezüglich „⊆“ gelten die folgenden Gesetze:

(I)     A ⊆ A   (Reflexivitätsgesetz)
(II)    (A ⊆ B und B ⊆ A) ⇒ A = B   (Identitätsgesetz)
(III)   (A ⊆ B und B ⊆ C) ⇒ A ⊆ C   (Transitivitätsgesetz)

Die Bedeutung der logischen Junktoren nicht, und, oder, wenn...so und genau dann,wenn, die in den vorstehenden Definitionen verwendet worden sind, muss noch erklärt werden. Am übersichtlichsten gelingt dies mit Hilfe der folgenden Verknüpfungstafeln. Hierbei sind "p" und "q" logische Aussagen; das Symbol „⊤“ steht für „wahr“, das Symbol „⊥“ steht für „falsch“. "p ˄ q" bedeutet "p und q"; "p ˅ q" bedeutet "p oder q"; "p → q" bedeutet "wenn p, so q"; "p ↔ q" bedeutet "p genau dann, wenn q" oder "p dann und nur dann, wenn q".

Das logische oder wird also nicht (wie in der Umgangssprache) im ausschließenden Sinne verwendet: "p oder q" ist dann und nur dann falsch, wenn sowohl "p" als auch "q" falsche Aussagen sind. Die Konditionalaussage "wenn p, so q" ist genau dann falsch, wenn "p" wahr, aber "q" falsch ist. Die Aussage "nicht p" ist falsch, wenn "p" wahr ist und wahr, wenn "p" falsch ist.

Folgt aus einer wahren mathematischen Aussage "a" eine andere wahre Aussage "b", dann schreibt man oft abkürzend „a ⇒ b“. Gilt "a ⇒ b und b ⇒ a", so sind die Aussagen "a" und "b" äquivalent und man schreibt „a ⇔ b“. Beispielsweise ist die Aussage

"(p ⇒ q) ⇔ (q ⇒ p)"

wahr, was man sich anhand folgender Verknüpfungstafel klarmacht. Hierbei bedeutet "p" die Negation von "p", also "nicht p", ebenso ist "q" = "nicht q".

Sei nun M eine Menge und A, B und C beliebige Teilmengen von M, das heißt A,B,C ∈∈ ℘(M). Dann sind A∩B, A∪B und A ebenfalls Elemente von ℘(M) (man sagt: ℘(M) ist in Bezug auf die Mengenoperationen „∩“, „∪“ und in Bezug auf die Komplementbildung abgeschlossen) und es gelten die folgenden Gesetze:

Eine Veranschaulichung der Distributibutivgesetze durch Venn-Diagramme findet sich hier.

 
Widersprüche!

Wenn gewisse Objekte x eine gemeinsame Eigenschaft E haben, liegt es nahe, diese Objekte zu einer Menge zusammenzufassen: M_E =_def { x | E trifft zu auf x }. Diesen Vorgang der Mengenbildung nennt man Komprehension. Das sogenannte Komprehensionsprinzip besagt, dass man diese Art der Mengenbildung immer vornehmen kann, und zwar unabhängig sowohl von der Art der betrachteten Objekte als auch von zumindest logisch formulierten Eigenschaften. Der oben vorgestellten, meist „naiv“ genannten Mengenlehre liegt insbesondere dieses Komprehensionsprinzip zugrunde.

Bertrand Russell hatte zu Beginn des vorigen Jahrhunderts die Idee zu der folgenden Komprehension: Man betrachte alle Objekte, die die gemeinsame Eigenschaft besitzen, eine Menge zu sein. Diese Objekte bilden dann eine neue Menge, nämlich die Menge aller Mengen: M = { m | m ist eine Menge }. Aufgrund der Definition von M folgt sofort: M ∈∈ M, das heißt, es gibt (mindestens) eine Menge, die sich selbst als Element enthält. Sei nun die Russel’sche Menge M* definiert durch M* =_def { m | m ist eine Menge und m ∉∉ m }. Mit der Annahme, dass M* ∈∈ M*, folgt sofort aufgrund der Definition von M*: M* ∉∉ M*, ein Widerspruch zur Annahme! Nimmt man umgekehrt an, dass M* ∉∉ M*, so ergibt sich aus der Definition von M*: M* ist keine Menge oder M* ∈∈ M*. Da aber M* als Menge vorausgesetzt war, folgt M* ∈∈ M*. Wieder ein Widerspruch zur Annahme! Insgesamt hat man also das Ergebnis, dass weder M* ∈∈ M* noch M* ∉∉ M* gilt oder aber - je nach Betrachtungsweise - M* ∈∈ M* ⇔ M* ∉∉ M*: ein Resultat, aus dem zwingend folgt, dass M* keine Menge ist. Diese so genannte Russell’sche Antinomie hat zu der Erkenntnis geführt, dass es nicht gestattet sein darf, gemäß des Komprehensionsprinzips in uneingeschränkter Weise Mengen zu bilden! Die Annahme, die der Russell’schen Antinomie (, die - nebenbei bemerkt - unabhängig von Russell auch Zermelo entdeckt hat und möglicherweise Cantor bereits bekannt war) zugrunde liegt, nämlich die Existenz der Menge aller Mengen, ist offenbar falsch. Die Gesamtheit aller Mengen ist keine Menge!

Widersprüche ganz anderer Art ergeben sich bei unterschiedlicher Anordnung der Elemente unendlicher Mengen. Werden beispielsweise alle natürlichen Zahlen (also die Elemente der Menge ℕ) bezüglich „<“ angeordnet, 0 < 1 < 2 < 3 < ...., dann sieht man anschaulich, dass man alle natürlichen Zahlen der Reihe nach abzählen kann. Die Menge ℕ = { 0, 1, 2, ... } ist abzählbar unendlich. Die Menge aller geraden natürlichen Zahlen ℕ_g = { 0, 2, 4, ... } ist, genauso wie die Menge aller ungeraden natürlichen Zahlen ℕ_u = { 1, 3, 5, ... }, ebenfalls abzählbar unendlich. Offensichtlich gilt

ℕ = ℕ_g ∪ ℕ_u = { 0, 2, 4, ..., 1, 3, 5, ... }.

Ist nun ℕ gleichzeitig abzählbar unendlich und doppelt abzählbar unendlich? Es geht noch schlimmer: Sei mit ℕ_p = { p, 2p, 3p, ...} die Menge aller Vielfachen einer Primzahl p definiert, dann ist auch ℕ_p abzählbar unendlich und die Menge

ℕ₃ ∪ ℕ₅ ∪ ℕ₇ ∪ .... = { 3, 6, 9, ..., 5, 10, 15, ... } 

unendlich mal abzählbar unendlich, aber gleichzeitig weniger mächtig als ℕ, da unendlich viele Elemente, nämlich 0, 1, 2, 4, 8, 16, ... fehlen!?

In diesem Zusammenhang passt eine Diskussion über Quadratzahlen zwischen Salviati, Sagredo und Simplicio (Galileo Galilei: Unterredungen und mathematische Demonstrationen 1638, Erster Tag): Salviati erinnert daran, dass eine Quadratzahl aus der Multiplikation einer beliebigen Zahl mit sich selbst entsteht, diejenigen Zahlen, welche mit sich selbst multipliziert werden, Wurzeln genannt werden, und die anderen Zahlen, welche nicht aus zwei gleichen Faktoren bestehen, Nichtquadratzahlen heißen. (Mit „Zahlen“ sind hier die natürlichen Zahlen gemeint.) Das Gespräch verläuft dann so:

   Salv.  ...Wenn ich nun sage, alle Zahlen, Quadrat- und Nichtquadratzahlen zusammen, sind mehr, als die Quadratzahlen allein, so ist das doch eine durchaus richtige Behauptung; nicht?
   Simpl.  Dem kann ich nicht widersprechen.  
   Salv.  Frage ich nun, wieviel Quadratzahlen es giebt, so kann man in Wahrheit antworten, eben soviel als es Wurzeln giebt, denn jedes Quadrat hat eine Wurzel, jede Wurzel hat ihr Quadrat, kein Quadrat hat mehr als eine Wurzel, keine Wurzel mehr als ein Quadrat.
   Simpl.  Vollkommen richtig.
   Salv.  Wenn ich nun aber frage, wieviel Wurzeln giebt es, so kann man nicht leugnen, dass sie eben so zahlreich seien, wie die gesammte Zahlenreihe, denn es giebt keine Zahl, die nicht Wurzel eines Quadrates wäre. Steht dieses fest, so muss man sagen, dass es ebensoviele Quadrate als Wurzeln gäbe, da sie an Zahl ebenso gross als ihre Wurzeln sind, und alle Zahlen sind Wurzeln; und doch sagten wir anfangs, alle Zahlen seien mehr als alle Quadrate, da der grössere Theil derselben Nichtquadrate sind. Und wirklich nimmt die Zahl der Quadrate immer mehr ab, je grösser die Zahlen werden; denn bis 100 giebt es 10 Quadrate, d.h. der 10. Theil ist quadratisch; bis 10000 ist der 100. Theil bloss quadratisch, bis 1000000 nur der 1000. Theil; und bis zu einer unendlich grossen Zahl, wenn wir sie erfassen könnten, müssten wir sagen, giebt es soviel Quadrate, wie alle Zahlen zusammen.
   Sagr.  Was ist denn zu thun, um einen Abschluss zu gewinnen?
   Salv.  Ich sehe keinen andern Ausweg als zu sagen, unendlich ist die Anzahl aller Zahlen, unendlich die der Quadrate, unendlich die der Wurzeln; weder ist die Menge der Quadrate kleiner als die der Zahlen, noch ist die Menge der letzteren grösser; und schliesslich haben die Attribute des Gleichen, des Grösseren und des Kleineren nicht statt bei Unendlichem, sondern sie gelten nur bei endlichen Grössen.

 
Zermelo-Fraenkel’sches Axiomensystem

Ernst Zermelo (1871−1953) hat 1907 mit seinen Untersuchungen über die Grundlagen der Mengenlehre eine axiomatisch begründete Theorie entwickelt, und zwar in der Weise, dass „man die Prinzipien einmal eng genug einschränkt, um alle Widersprüche auszuschließen, gleichzeitig aber auch weit genug ausdehnt, um alles Wertvolle dieser Lehre beizubehalten.“ (Math. Annalen Bd. 65, S. 261). Spätere Ergänzungen von Zermelos Prinzipien durch Abraham Halevi Fraenkel (1891−1965) und Albert Thoralf Skolem (1887−1963) führten schließlich zum Zermelo-Fraenkel’schen Axiomensystem mit Auswahlaxiom (Axiom of Choice), in der mathematischen Literatur abgekürzt mit ZFC.

Fraenkel schreibt zum axiomatischen Aufbau der Mengenlehre (Einleitung in die Mengenlehre, 3. Auflage, S.270):

Die Axiome sind Aussagen, die entweder gewisse Relationen zwischen einer „Menge“ und den „in ihr enthaltenen Elementen“ ausdrücken oder die Existenz bestimmter Mengen fordern oder endlich gestatten, aus der Existenz gewisser Mengen allgemein auf die Existenz gewisser anderer Mengen zu schließen. Danach dürfen der Grundrelation „m ist Element der Menge M“ keine anderen Eigenschaften zugeschrieben werden als die, die in den Axiomen ausgedrückt sind oder sich aus den Axiomen deduktiv ergeben. Ebenso ist unter „Menge“ nicht etwa „jede Zusammenfassung von Elementen“ zu verstehen, sondern es gibt nur Mengen, die auf Grund der Axiome existieren oder herleitbar sind. Schließlich wird das Wort „Element“ überhaupt nicht zur Bezeichnung eines selbständigen Begriffs (etwa der „Menge“ gegenüberstehend) gebraucht, sondern nur als Bestandteil der Grundrelation „Element (einer Menge) sein“; in der Axiomatik tritt also nur eine einzige Kategorie von „Dingen“ oder „Objekten“ auf, nämlich die „Mengen“, womit von vornherein keine bestimmtere Vorstellung als mit dem allgemeinen Ausdruck „Ding“ verbunden zu werden braucht.

In ZFC sind Elemente von Mengen immer ebenfalls Mengen. Das heißt mit anderen Worten: Es existieren in ZFC keine Urelemente (das sind Dinge, die keine Mengen sind, aber Elemente von Mengen sein können). Auf die Frage, was Mengen „eigentlich“ sind, liefert ZFC keine Antwort. Mit ZFC ist es lediglich möglich, Aussagen darüber zu formulieren, dass gewisse mathematische Objekte Mengen sind und welche mengentheoretische Eigenschaften sie haben. Das hört sich sehr schwach an, und dennoch stellt ZFC insbesondere die Basis dafür dar, sowohl die fundamentalen Begriffe der Mathematik mengentheoretisch zu definieren und zu verstehen als auch Grundlagenfragen der Mathematik im Rahmen der Mengenlehre zu diskutieren.

Skolem begann 1929, die Mengenlehre unter Benutzung der Prädikatenlogik zu formalisieren. Alle Aussagen in ZFC können demnach in einer Sprache formuliert werden, deren Zeichen das jeweils Folgende bedeuten soll:

Sinnvolle, aus diesen Zeichen gebildete Ausdrücke heißen (zulässige) mengentheoretische Formeln (kurz: Formeln). Ist eine Variable in einer Formel mindestens einmal weder durch den Existenzquantor „∃“ noch durch den Allquantor „∀“ gebunden, so heißt eine solche Variable freie Variable. Formeln, in denen keine Variable frei vorkommt, heißen mengentheoretische Aussagen (kurz: Aussagen).

Der Ausdruck "∀a∃b(¬c)" ist offensichtlich nicht sinnvoll. In der Formel "∃a (a ∈∈ m)" ist a gebunden und m frei. "∃a ∀m(a ∈∈ m)" ist eine Aussage, die allerdings falsch ist: Es ist nicht so, dass es eine Menge a gibt, die Element von jeder Menge ist.

"∀a,b,c (a = b ˄ b = c ⇀ a = c)" ist eine wahre Aussage und beschreibt die Transitivität bezüglich der Mengengleichheit. Die Aussage lautet ausführlich geschrieben:

∀a∀b∀c (((a = b) ˄ (b = c)) ⇀ (a = c))

Auf die Klammern in Formeln kann man weitgehend verzichten, wenn vereinbart wird, dass die Bindung der Zeichen „=“ und „∈∈“ am stärksten und die der Zeichen „⇀“ und „⇌“ am schwächsten sein soll. Außerdem soll statt "¬(a = b)" in der Regel "a ǂ b", statt "¬(a ∈∈ b)" "a ∉∉ b" und statt "¬(∃a)" "∄a"geschrieben werden. "(x ∈∈ a) ˄ (y ∈∈ a)" wird abgekürzt durch "x,y ∈∈ a".

Kann die Eigenschaft gewisser Mengen durch eine mengentheoretische Formel beschrieben werden, so heißt diese Eigenschaft definit und die zugehörige Formel ist ein Prädikat. Der Ausdruck "∃!m (φ(m))" beispielsweise bedeutet "Es existiert genau eine Menge m, für die das Prädikat φ(m) zutrifft". Er ist logisch äquivalent mit "∃m (∀a (φ(a) ⇌ a = m))" und nebenbei bemerkt ein Beispiel dafür, dass manchmal - wenn es zweckmäßig scheint - in Formeln nicht ausschließlich nur die Zeichen verwendet werden, die oben aufgelistet wurden. Dies ist immer dann erlaubt, solange eine Formel in eine zulässige Formel überführt werden kann.

Der Ausdruck "∀a (a ∈∈ m ⇀ φ(a))" bedeutet: "Für alle Mengen a, die Element von m sind, trifft das Prädikat φ(a) zu". Statt einer Formel der Art "∀a (a ∈∈ m ⇀ φ(a))" soll auch die folgende kürzere Schreibweise verwendet werden: "∀a∈∈m (φ(a))". Das Prädikat

φ_T(a,b) =_def ∀e (e ∈∈ a ⇀ e ∈∈ b)

beschreibt die Teilmengeneigenschaft der Menge a, genauer: φ_T(a,b) drückt aus, dass a eine Teilmenge von b bzw. b eine Obermenge von a ist (abkürzend geschrieben: a ⊆ b). Mit

φ_P(a,b) =_def ∀e (e ∈∈ b ⇌ φ_T(e,a))

wird die Potenzmengeneigenschaft der Menge b definiert. Genauer: Durch φ_P(a,b) wird ausgedrückt, dass b die Potenzmenge von a ist. φ_T und φ_P sind zweistellige Prädikate und beschreiben deswegen die Beziehung zwischen zwei Mengen. Im nächsten Beispiel handelt es sich um ein dreistelliges Prädikat:

∀e ((e ∈∈ b ⇀ e ∈∈ a)˄(e ∈∈ a ⇀ e ∈∈ c))

und mit

φ_N(a) =_def ∀e (e ∉∉ a) 

hat man ein einstelliges Prädikat definiert, mit dem ausgedrückt wird, dass die Menge a keine Elemente hat.

Dadurch, dass etwa mit φ_T(a,b), φ_P(a,b) oder φ_N(a,b) bestimmte Mengen formelhaft beschrieben sind, ist nicht ausgesagt, dass derartige Mengen überhaupt existieren!

Mengen, die eine gewisse definite Eigenschaft besitzen, können in einer Klasse zusammengefasst werden. Um Klassen typographisch von Mengen zu unterscheiden, sollen als Klassennamen nur Großbuchstaben zugelassen und statt geschweifter Klammern eckige Klammern verwendet werden:

𝑲 = [ m | φ(m) ].

Der Ausdruck "m ∈∈ 𝑲" soll "Die Menge m gehört zu 𝑲" bedeuten. Für "∀x (x ∈∈ m ⇀ x ∈∈ 𝑲)" soll kurz "m ⊆ 𝑲" geschrieben werden.

Klassen sind im Allgemeinen keine Mengen. Es wurde im letzten Abschnitt bereits auf logischem Wege gezeigt, dass beispielsweise die Russell-Zermelo-Klasse 𝑹 = [ m | m ∉∉ m ] keine Menge ist; im Rahmen von ZFC wird dies später (→ Z3) bewiesen. In diesem Kapitel werden außer der Allklasse 𝑩 = [ m | m = m ] noch andere Klassen eine Rolle spielen: etwa die Klasse aller Funktionen 𝑭 oder die Klasse aller Ordinalzahlen 𝑶.

Es sollen nun die Axiome von ZFC nacheinander vorgestellt werden:

Existenzaxiom (EXZ),
Extensionalitätsaxiom (EXT),
Paarmengenaxion (PMG),
Aussonderungsaxiom (AUS),
Potenzmengenaxiom (POT),
Vereinigungsaxiom (VER),
Auswahlaxiom (AWL),
Unendlichkeitsaxiom (INF), 
Ersetzungsaxiom (ERS),
Fundierungsaxiom (FND),

Zermelo hat ursprünglich statt EXT und PMG das Axiom der Elementarmengen angegeben, welches insbesondere die Existenz der leeren Menge (von Zermelo Nullmenge genannt) postuliert. In der folgenden Darstellung von ZFC wird stattdessen die Existenz der leeren Menge mit Hilfe von AUS bewiesen. Die Axiome ERS und FND sind dem ursprünglichen Axiomensystem von Zermelo erst später hinzugefügt worden.

Eine Mengenlehre ohne Mengen wäre sinnlos, deswegen lautet das erste Axiom:

Gilt ∀e (e ∈∈ a ⇀ e ∈∈ b) für zwei Mengen a und b, so ist a eine Teilmenge von b, kurz geschrieben: „a ⊆ b“. Die Aussage

 "∀a,b (a = b ⇀ a ⊆ b ˄ b ⊆ a)"

ist demnach offensichtlich wahr. Die Umkehrung dieser Aussage ist nicht selbstverständlich und muss daher axiomatisch festgelegt werden:

Zwei Mengen sind nach dieser Festlegung also immer genau dann gleich, wenn sie in der Gesamtheit aller ihrer Elemente (das heißt, ihrem Umfang nach) übereinstimmen; die Bedeutung oder eine eventuelle Interpretation der Elemente von a bzw. b spielen keine Rolle (extensionale Mengenauffassung).

Wegen ∀e (e ∈∈ a ⇌ e ∈∈ b) ⇌ a = b für alle Mengen a, b könnte man im Prinzip die Gleichheitsbeziehung zwischen zwei Mengen auf die Elementbeziehung zurückführen und so auf das Zeichen „=“ ganz verzichten.

Gemäß EXT ist jedes Element einer Menge m in m nur einmal enthalten.

Aus EXT folgt, dass die nach PMG existierende Paarmenge { a, b } eindeutig bestimmt ist. Die Reihenfolge, in der die Elemente einer Paarmenge notiert werden, ist bedeutungslos.

Das Paarmengenaxiom gestattet es, den Begriff „geordnetes Paar“ mengentheoretisch zu definieren, und zwar so, wie es Kazimierz Kuratowski (1896−1980) 1921 vorgeschlagen hat:

Z1
(x; y) ist nach PMG eine Menge und es gilt

(x = u) ˄ (y = v) ⇌ (x; y) = (u; v).

"(x; y) = (y; x)" ist also dann und nur dann gültig, wenn x = y.

Da es unendlich viele Möglichkeiten gibt, ein Prädikat φ(e) zu formulieren, hat man mit AUS unendlich viele Axiome. AUS nennt man deshalb ein Axiomenschema. Aus EXT folgt, dass die nach AUS zum jeweiligen Prädikat φ(e) existierende Menge x eindeutig bestimmt ist. Man schreibt in der Regel

x = { e ∈∈ m | φ(e) }.

Hierbei ist wesentlich, dass für jedes Element e ∈∈ m nachprüfbar ist, ob φ(e) eine wahre Aussage darstellt oder nicht, wobei hierfür nur die Mengenaxiome, hieraus abgeleitete Aussagen oder allgemeingültige logische Gesetze verwendet werden dürfen.

Bildet man per Komprehension die Gesamtheit von Dingen, die alle eine gemeinsame Eigenschaft haben, so erhält man eine Klasse. Im vorangegangenen Abschnitt wurde bereits deutlich, dass die Klasse aller Mengen

𝑩  = [ m | m = m ],

die so genannte Allklasse, keine Menge ist. Die Allklasse ist also eine echte Klasse. Diese Aussage lässt sich mit Hilfe des Aussonderungsaxioms beweisen, und zwar unter Benutzung des folgenden Satzes:

Z2
Jede Menge m besitzt mindestens eine Teilmenge, welche nicht Element von m ist.

Z3
Die Allklasse ist keine Menge.

Mit dem Aussonderungsaxiom ist sichergestellt, dass neue Mengen nur im Rahmen einer bereits existierenden Menge gebildet werden können.

Erstes Beispiel. Sei m eine Menge und a ⊆ m. Dann heißt

a =_def  { e ∈∈ m | e ∉∉ a }

Komplementärmenge von a bezüglich m (oder kurz: Komplement von a).

Zweites Beispiel. Seien a und b beliebige Mengen, dann kann man durch

a ∩ b =_def  { e ∈∈ b | e ∈∈ a }

den Durchschnitt von a und b definieren.

Sowohl Komplementärmengen als auch Durchschnittsmengen sind aufgrund von AUS Mengen. Eine weitere wichtige Folgerung des Aussonderungsaxioms ist der folgende Satz:

Z4
Es gibt eine (eindeutig bestimmte) Menge ohne Elemente:

∃!x ∄e (e ∈∈ x).

Die hiernach eindeutig existierende Menge x heißt leere Menge und wird mit „Ø“ bezeichnet.

Gemäß AUS lässt sich dann aus p_m eine (nach EXT eindeutige) Menge bilden, die nur die Teilmengen von m enthält:

℘(m) =_def { e ∈∈ p_m | e ⊆ m }.

℘(m) heißt Potenzmenge von m. Da Ø keine Elemente hat, gilt Ø ⊆ m bzw. Ø ∈∈ ℘(m) für jede Menge m.

Zu jeder Menge m gibt es genau eine Potenzmenge ℘(m). Deshalb kann man den Ausdruck „℘(m)“ auf zweierlei Art interpretieren: einerseits kann „℘(m)“ als Bezeichnung der Menge { e ∈∈ p_m | e ⊆ m } gesehen werden, andererseits kann man „℘“ als Operator betrachten und „℘(m)“ als Bild unter der Potenzmengenoperation, die eine existierende Menge m auf ihre Potenzmenge abbildet.

Beispielsweise sieht das Potenzmengenprädikat φ_P(a,b) - ausführlich geschrieben - so aus:

∀e (e ∈∈ b ⇌ (∀x (x ∈∈ e ⇀ x ∈∈ a)))

Z5
Seien a und b zwei beliebige Mengen, dann gilt

x ∈∈ a ˄ y ∈∈ b ⇀ (x; y) ∈∈ ℘(℘(a ∪ b)).

Mit φ_L(g,u) =_def ∃v (g = (u; v)) und φ_R(g,v) =_def ∃u (g = (u; v)) werden zwei funktionale Prädikate definiert. φ_L(g,u) trifft zu, wenn es sich bei g um ein geordnetes Paar und bei u um die linke Komponente von g handelt; φ_R(g,v) trifft zu, wenn es sich bei g um ein geordnetes Paar und bei v um die rechte Komponente von g handelt. Mit φ_L und φ_R lassen sich die Projektionsoperationen λ und ρ und danach das kartesische Produkt zweier Mengen a und b definieren:

λ(g) =_def u, falls φ_L(g,u) zutrifft; Ø sonst
ρ(g) =_def v, falls φ_R(g,v) zutrifft; Ø sonst

Wegen Z5 lässt sich a x b auf einfache (und gewohnte) Weise darstellen:

a x b = { (x; y) | x ∈∈ a ˄ y ∈∈ b }.

Z6
Es gibt ein-elementige Mengen. Präziser: zu jeder Menge m existiert die Einermenge { m }, das heißt diejenige Menge, die nur m als einziges Element enthält. Bei gegebenem m ist { m } eindeutig bestimmt.

Gemäß AUS lässt sich dann aus v_m eine (nach EXT eindeutige) Menge bilden, die alle Elemente der Elemente von m umfasst und nur diese:

⋃m =_def { e ∈∈ v_m | ∃a (a ∈ m ˄ e ∈∈ a) }

⋃m heißt Vereinigungsmenge von m.

Sei nun t eine nichtleere Menge. Dann gibt es nach AUS zu jedem a ∈∈ ⋃t eine bestimmte Teilmenge t_a ⊆ t, zu der all die Elemente von t gehören, die a als Element besitzen:

t_a =_def  { e ∈∈ t | a ∈∈ ⋃t ˄ a ∈∈ e }.

Für jedes a gilt entweder t_a = t oder t_a ǂ t. Sei nun e* ∈∈ t beliebig gewählt. Dann ist d = { a ∈∈ e* | t_a = t } diejenige Teilmenge von e*, welche alle Objekte enthält, die Element von jedem Element von t sind. d heißt Durchschnittsmenge von t und wird mit ∩t bezeichnet. Enthält t nur zwei Elemente, dann schreibt man ∩{ a, b } = a ∩ b wie oben bereits definiert.

Seien a und b zwei beliebige Mengen. Dann gibt es gemäß PMG und EXT die eindeutig bestimmte Paarmenge { a, b } und nach VER und AUS die Menge, die alle Elemente von a und b enthält, und nur diese:

⋃{ a, b } = { e ∈∈ v_{a,b} | e ∈∈ a ˅ e ∈ b }.

⋃{ a, b } heißt Vereinigung von a und b und man schreibt ⋃{ a, b } = a ∪ b.

Die Symbole „∩“ und „∪“ lassen sich als Mengenoperatoren auffassen, mit denen Mengen sinnvoll nur dann verknüpft werden können, wenn sie Elemente der Potenzmenge einer beliebig, aber fest gewählten Menge m sind. Die Rechenregeln bezüglich „∩“ und „∪“ wurden oben bereits behandelt und zeigen, dass „∪“ eine additive und „∩“ eine multiplikative Verknüpfung ist.

Aus dem Vereinigungsaxiom folgt, dass 𝑩’, die Klasse aller Einermengen, keine Menge ist, denn wäre 𝑩’ eine Menge, würde mit VER folgen, dass auch 𝑩 = ⋃𝑩’ eine Menge ist. Widerspruch, denn 𝑩 ist, wie oben gezeigt wurde, eine echte Klasse. Entsprechend folgt auch, dass 𝑩’’, die Klasse aller Zweiermengen, keine Menge ist, und so fort.

Das Auswahlaxiom postuliert zwar die Existenz von Auswahlmengen, bietet aber grundsätzlich keinerlei Möglichkeit, einen Weg anzugeben, wie man diese Mengen bilden könnte. Von daher ist es nicht verwunderlich, dass viele Mathematiker dem nicht-konstruktiven Auswahlaxiom kritisch bis ablehnend gegenüber standen. Andererseits wird das Auswahlaxiom für den Beweis wichtiger mathematischer Gesetzmäßigkeiten gebraucht; es wird zum Beispiel benötigt, um den Wohlordnungssatz zu beweisen.

Zermelo hat die Notwendigkeit des Auswahlaxioms damit begründet, dass das Produkt mehrerer Mengen nur dann verschwinden (das heißt, der leeren Menge gleich sein) soll, wenn einer der Faktoren verschwindet (Math. Annalen Bd. 65, S. 266). Er geht bei der Einführung des Produktes von einer Menge t aus, deren Elemente paarweise disjunkt sind. Dann definiert er 𝔓t als Menge, die all diejenigen Teilmengen der Vereinigungsmenge von t umfasst, welche mit jedem Element von t genau ein Element gemeinsam haben und nennt diese Menge die zu t gehörende Verbindungsmenge (oder: das Produkt der Elemente von t). 𝔓t ist nach VER, AUS sowie Z6 eine wohldefinierte Menge:

𝔓t =_def { u ⊆ ⋃t | ∀m∈∈t ∃z (u ∩ m = { z }) }.

Mit dem Auswahlaxiom folgt nunmehr wie gefordert:

𝔓t = Ø ⇌ Ø ∈∈ t.

Zermelo schreibt weiter: „Die vorstehenden Axiome genügen, wie wir sehen werden, um alle wesentlichen Theoreme der allgemeinen Mengenlehre abzuleiten. Um aber die Existenz ‚unendlicher Mengen‛ zu sichern, bedürfen wir noch des folgenden, seinem wesentlichen Inhalte von Herrn Dedekind herrührenden Axiomes.“ Das ursprüngliche Axiom der Unendlichkeit postuliert die Existenz einer Menge, die Ø als Element enthält und mit jedem Element e dieser Menge auch { e } als Element enthält. Dies führt dann zur von Zermelo so genannten Zahlenreihe Ø, { Ø }, { { Ø } }, ...

Das Unendlichkeitsaxiom in der hier angegebenen Fassung basiert auf einem Vorschlag von John von Neumann (1903−1957):

Eine nach INF existierende Menge m nennt man eine induktive Menge.

Alle induktiven Mengen haben eine gemeinsame Teilmenge. (→ Beweis, gemäß der Argumentation von Zermelo 1907 und unter Benutzung seiner Symbole). Diese Teilmenge, ab jetzt mit ω bezeichnet, besteht aus dem Element Ø und aus denjenigen Elementen, die - ausgehend von Ø - induktiv erzeugt werden:

Ø
{ Ø }
{ Ø, { Ø } }
{ Ø, { Ø }, { Ø, { Ø } } }
...

Abraham Fraenkel wies 1922 in seinem Aufsatz Zu den Grundlagen der Cantor-Zermeloschen Mengenlehre (Mathematische Annalen 86, S. 230−237) darauf hin, dass die Axiome von Zermelo nicht zur Begründung der Mengenlehre ausreichen und gab als Nachweis dieser Aussage unter anderem ein einfaches Beispiel: Es sei Z₀ die Zermelo’sche Zahlenreihe, Z₁ die Potenzmenge von Z₀, Z₂ die Potenzmenge von Z₁, und so fort. Dann lässt sich auf der Grundlage der bisherigen Axiomen nicht die Menge { Z₀, Z₁, ... } und daher auch nicht die Vereinigungsmenge dieser Menge bilden.

Fraenkel schlug damals vor, Zermelos Axiomensystem durch das von ihm so genannte Ersetzungsaxiom zu ergänzen: „Ist M eine Menge und wird jedes Element von M durch ein ‚Ding des Bereiches ℬ‛ ... ersetzt, so geht M wiederum in eine Menge über.“ und er kommentiert dies (auf S. 231) so:

Für das oben angeführte Beispiel hat man, um die Existenz der Menge { Z₀, Z₁, ... } zu zeigen, auf Grund des soeben formulierten Axioms nur das Element 0 von Z₀ durch Z₀, das Element { 0 } durch Z₁ zu ersetzen usw. Man kann weiter auf die Vereinigungsmenge der so entstehenden Menge das Axiom in analoger Weise anwenden und erlangt, derart weiterschreitend, ersichtlich die erforderliche Freiheit in der Bildung von Mengen.
Für die speziellen Zwecke der Axiomatik der Mengenlehre ist es übrigens ... wünschenswert und möglich, an Stelle des angeführten Axioms ein weniger weitgehendes und schärferes aufzustellen; es gelingt dabei, den Begriff „ersetzen“, der im wesentlichen auf den Funktionsbegriff hinausläuft und einer besonderen Einführung bedürfte, überflüssig zu machen.

Heute wird das Ersetzungsaxiom etwa wie folgt formuliert:

ERS ist genauso wie AUS ein Axiomenschema für unendlich viele Axiome.

Ist v eine Menge, φ_xy funktional und F der zu φ_xy gehörende Operator, dann folgt wegen ERS und AUS, dass 

F(v) =_def { y | ∃x(x ∈∈ v ˄ φ_xy) }

eine Menge ist. F(v) ist nach EXT eindeutig bestimmt und heißt Bild von v unter dem Prädikat φ_xy.

Fraenkel bemerkt in seinem eben zitierten Aufsatz (auf S. 234), dass  das Axiomensystem von Zermelo nebst seiner Ergänzung durch das Ersetzungsaxiom, „die Gesamtheit der Mengen nicht vollständig festlegt“. Im Übrigen beklagt er zwei weitere „Übelstände“: 1. Zwar sind Mengen „nichtmathematischer und überhaupt nichtbegrifflicher Herkunft“ mithilfe der Axiome nicht konstruierbar, allerdings wird die Existenz solcher Mengen durch die Axiome nicht ausgeschlossen. 2. Zermelos Axiome lassen es zu, dass es Mengen mit unerfreulichen Eigenschaften gibt, zum Beispiel zyklische Mengen m, deren Elemente alle die Eigenschaft haben, Element des „nächsten“ Elementes von m zu sein: e₁ ∈∈ e₂ ∈∈ e₃ ... ∈∈ e_n ∈∈ e₁.

Den angegebenen Übelständen kann nach Fraenkel durch ein „... ‚Beschränktheitsaxiom‛ abgeholfen werden, das dem Mengenbegriff oder zweckmäßiger dem Bereich ℬ den geringsten mit den übrigen Axiomen verträglichen Umfang auferlegt“.

Diese Idee von Fraenkel wird realisiert durch das Fundierungsaxiom, welches tatsächlich die charakteristische Struktur des gesamten Mengenuniversums bestimmt (→ vonNeumann’sche Hierarchie) . 

In jeder nichtleeren Menge m gibt es also mindestens ein Element, das kein Element mit m gemeinsam hat; man nennt ein solches Element ∈∈-minimales Element.

Angenommen, es gäbe eine zyklische Menge m. Sei e** ∈∈ m beliebig gewählt, dann gibt es immer ein e* ∈∈ m mit e* ∈∈ e** und  e* ∈∈ (e** ∩ m), das heißt (e** ∩ m) ǂ Ø. So kann man für alle e** ∈∈ m bzw. für alle e* ∈∈ m in beliebiger Reihenfolge argumentieren. Das bedeutet: Aufgrund von FND kann es keine zyklischen Mengen geben.

Es gibt auch keine Mengen, die Element von sich selbst sind: Angenommen, es gäbe eine solche Menge m mit m ∈∈ m. Mit m existiert auch { m } und es gilt m ∈∈ (m ∩ { m }). Widerspruch zu FND!

Die Existenz zweier Mengen a und b mit a ∈∈ b ˄ b ∈∈ a ist ebenfalls ausgeschlossen. Denn gäbe es solche Mengen, würde die gemäß PMG existierende Menge { a, b } zyklisch sein. Widerspruch zu FND!

 
Relationen und Funktionen

Mit der Definition eines geordneten Paares folgt unmittelbar r ⊆ a x a mit a = fld(r). Außerdem gilt fld(r) = dom(r) ∪ rng(r).  Die Klasse aller Relationen auf einer Menge a, nämlich ℘(a x a), ist gemäß POT eine Menge.

Sei a eine Menge von paarweise disjunkten und nichtleeren Mengen, also eine Zerlegung von ⋃a. Diese Zerlegung induziert eine Äquivalenzrelation auf ⋃a und die Elemente von a sind die zugehörigen Äquivalenzklassen. Das Auswahlaxiom besagt, dass sich zu jeder dieser Äquivalenzklassen immer ein Repräsentant auswählen lässt, wobei keine Aussage darüber möglich ist, wie und auf welchem Weg diese Auswahl zu bewerkstelligen sein könnte.

Aus mengentheoretischer Sicht ist also jede Funktion eine Menge, präziser: eine Teilmenge des kartesischen Produktes zweier Mengen im Gegensatz zur Definition einer Funktion als Tripel, bestehend aus Definitionsbereich, Zielbereich und Zuordnungsvorschrift. Da Ø Teilmenge von jeder Menge ist, ist auch Ø eine Funktion (die leere Funktion). Es ist dom(Ø) = Ø, rng(Ø) = Ø und f: Ø → b mit beliebiger Menge b.

Aus f: a → b folgt f ∈∈ ℘(a x b). Demzufolge ist die Klasse ^ab aller Funktionen von a nach b wegen AUS eine Menge:

^ab =_def { f ∈∈ ℘(a x b) | f: a → b }

Ist f eine Funktion und g ⊆ f, dann ist g auch eine Funktion; anders ausgedrückt: 𝑭, die Klasse aller Funktionen, ist bezüglich „⊆“ abgeschlossen.

Sei f: a _inj→ b. Dann existiert gemäß ERS die Menge f⁻¹ =_def { (y; x) | (x; y) ∈∈ f }. Wegen der Injektivität von f ist f⁻¹ ebenfalls eine Funktion. dom(f⁻¹) = rng(f). f⁻¹ heißt Umkehrfunktion von f (oder Inverse von f). Die Umkehrfunktion einer Bijektion von a auf b ist eine Bijektion von b auf a. Gilt f: a _bij→ a, so nennt man f eine Permutation von a. Die Bijektion id_a mit id_a(x) = x für alle x ∈∈ a heißt identische Funktion auf a.

Bijektionen sind insbesondere deswegen wichtig, weil sie es gestatten, Mengen ihrem Umfang nach miteinander zu vergleichen:

Sind f und g Funktionen mit rng(f) ⊆ dom(g), dann existiert gemäß AUS die Menge

{ x ∈∈ dom(f) x rng(g) | ρ(x) = g(f(π_l(x))) },

einfacher formuliert: { (u; g(f(u))) | u ∈∈ dom(f) }. Also ist die folgende Definition statthaft:

Sei f ∈∈ 𝑭 und a ⊆ dom(f), dann gilt f_|a ⊆ f ˄ f_|a ∈∈ 𝑭, dom(f_|a) = a und f_|a(x) = f(x) für alle x ∈∈ a.

R1
Sei m eine nichtleere Menge. Dann gibt es auf ℘(m) eine Auswahlfunktion.

R2
Sei m eine nichtleere Menge. Dann gibt es auf m eine Auswahlfunktion.

R3
Wenn k eine Funktionenkette ist, so ist ⋃k eine Funktion und es gilt

dom(⋃k) = ⋃{ dom(f) | f ∈∈ k }.

Die eben bewiesene Aussage R3 spielt später im Beweis vom Rekursionssatz für ω eine wichtige Rolle.

Man könnte den Begriff „algebraische Struktur“ allgemeiner fassen; dies wäre aber für dieses Kapitel ohne Belang.

R4
Seien A = (a,f,r,c) und B = (b,g,s,d) algebraische Strukturen und ψ: A ≅ B. Wegen der Injektivität von ψ existiert ψ⁻¹ und es gilt ψ⁻¹: b _bij→ a. Darüberhinaus gilt ψ⁻¹: B ≅ A.

Sind zwei Strukturen A und B isomorph, so haben diese also völlig gleiche strukturelle Eigenschaften. Man sagt dann: „A und B sind bis auf Isomorphie gleich“. Gilt ein Satz für Elemente aus a bezüglich f bzw. r, so ist der gleiche Satz für Elemente aus b bezüglich g bzw. s ebenfalls gültig. Das Umgekehrte ist natürlich auch richtig.

 
vonNeumann’sche Zahlen

Auf Grundlage des Unendlichkeitsaxioms können die natürlichen Zahlen als Mengen repräsentiert werden; es sind dies Ø, { Ø }, { Ø, { Ø } }, { Ø, { Ø }, { Ø, { Ø } } }, ..., also die Elemente der Menge ω (vonNeumann’sche Zahlen). Definiert man 0 =_def Ø, 1 =_def { Ø }, 2 =_def { Ø, { Ø } },..., n, s(n) =_def n ∪ { n }, ... unter Benutzung der „gewöhnlichen“ natürlichen Zahlen 0, 1, 2, ..., n, n+1, ... so gilt für beliebiges n und die Nachfolgermenge n+1

n+1 = { 0, 1, ..., n }.

Diese mengentheoretische Definition und Beschreibung der natürlichen Zahlen ist nur dann sinnvoll, wenn der Nachweis gelingt, dass ω dem Axiomensystem von Peano genügt, wenn man zeigen kann, dass die Elemente von ω linear angeordnet werden können und dass ℕ und ω strukturgleich sind.

Die Peano’schen Axiome lauten unter Benutzung der im vorigen Abschnitt definierten Begriffe und Schreibweisen

Es werden nun nacheinander die folgenden Sätze bewiesen:

(ω,s,Ø) ist eine Peano-Struktur mit s(x) = x ∪ { x } für alle x ∈∈ ω.
Die Elemente von ω sind transitive Mengen.
Die Elemente von ω lassen sich linear ordnen.
Für alle n ∈∈ ω ist s(n) das nach n nächstgrößere Element.
Zu jedem n von ω gehören alle Elemente von ω, die kleiner sind als n.
ω ist wohlgeordnet.
Auf ω können Funktionen rekursiv definiert werden.
Es gilt der spezielle Rekursionssatz für ω.
Je zwei Peano-Strukturen sind isomorph zueinander.

 N1
(ω,s,Ø) ist eine Peano-Struktur mit s(x) = x ∪ { x } für alle x ∈∈ ω.

Der Beweis dieses Satzes wird in zwei Teilen geführt:

Im Folgenden soll mit „φ_n=m“ die Aussage „φ_n trifft zu für m“ gemeint sein. „φ_n∈∈ω“ bedeutet demzufolge „φ_n trifft zu für alle n ∈∈ ω“. Sei nun φ_n =_def φ(n) ein Prädikat mit der Eigenschaft

φ_n=Ø ˄ ∀m∈∈ω (m ∈∈ ω ˄ φ_n=m ⇀ φ_n=s(m)).

Dann folgt mit t =_def { n ∈∈ ω | φ_n } und (iv) die Gleichheit von t und ω, und dies bedeutet, dass φ_n für alle n ∈∈ ω zutrifft.

Damit ist (unter wesentlicher Verwendung von INF) der Satz von der vollständigen Induktion über ω (kurz: Induktionssatz für ω) bewiesen:

φ_n=Ø ˄ ∀m∈∈ω (φ_n=m ⇀ φ_n=s(m)) ⇀ φ_n∈∈ω.

φ_n=Ø heißt Induktionsanfang,
(m ∈∈ ω ˄ φ_n=m) Induktionsvoraussetzung und
(m ∈∈ ω ˄ φ_n=m ⇀ φ_n=s(m)) Induktionsschluss.

Bevor der oben mit (i), (iii) und (iv) begonnene Beweis fortgeführt wird, soll zuvor erst noch die folgende wichtige Aussage bewiesen werden:

 N2
Alle Elemente von ω sind transitive Mengen, das heißt:

   TM    ∀n,x (n ∈∈ ω ˄ x ∈∈ n ⇀ x ⊆ n)

Im Beweis von N1 fehlt noch der Nachweis, dass s:ω → ω mit s(x) = x ∪ { x } eine Injektion ist:

Hiermit ist bewiesen, dass (ω,s,Ø) eine Peano-Struktur ist: die Trägermenge ω genügt den Axiomen (I)* bis (IV)*, s ist die Nachfolgerfunktion auf ω und Ø repräsentiert die Nullmenge.

Als Nächstes soll (mit N3 und N4) gezeigt werden, dass die Elemente von ω angeordnet werden können, und zwar mit der ∈∈-Relation auf ω, definiert durch

∈∈_ω =_def { g ∈∈ ω x ω | λ(g) ∈∈ ρ(g) }.

"(x; y) ∈∈ ∈∈_ω" ist gleichbedeutend mit "x ∈∈_ω y"; für "x ∈∈_ω y" soll im Folgenden der Einfachheit halber nur "x ∈∈ y" geschrieben werden.

 N3
Es gilt für alle x,m ∈∈ ω

m ∈∈ x ⇀ s(m) ∈∈ x ˅ s(m) = x.

 N4
ω ist mit „∈∈“ linear geordnet: ∈∈_ω ist irreflexiv, transitiv und konnex:

∄x (x ∈∈ x)  (Irreflexivität)
∀x,y,z (x ∈∈ y ˄ y  ∈∈ z ⇀ x ∈∈ z)  (Transitivität)
∀x,y (x ∈∈ y ˅ x = y ˅ y ∈∈ x)  (Konnexität)

Man macht sich schnell klar, dass von den Aussagen "x ∈∈ y", "x = y" und "y ∈∈ x" für zwei beliebig ausgewählte x, y ∈∈ ω stets nur genau eine Aussage richtig sein kann: Sowohl "x ∈∈ y ˄ x = y" als auch "y ∈∈ x ˄ x = y" können nie gelten, da ∈∈_ω irreflexiv ist. Aus demselben Grund ist auch "x ∈∈ y ˄ y ∈∈ x" immer eine falsche Aussage, denn mit x ∈∈ y ˄ y ∈∈ x würde wegen der Transitivität von ∈∈_ω die falsche Aussage "x ∈∈ x" folgen.

Für x, y ∈∈ ω schreibt man üblicherweise "x < y" statt "x ∈∈ y". Es ist also entweder x < y oder y < x oder x = y, das heißt: je zwei Elemente von ω sind vergleichbar. Da alle Elemente von ω transitive Mengen sind, folgt aus x < y stets x ⊂ y.

Definiert man die Identitätsrelation auf einer Menge m durch

id_m =_def { g ∈∈ m x m | λ(g) = ρ(g) }

und die Teilmengenrelation auf einer Menge m durch

⊆_m =_def { g ∈∈ m x m | λ(g) ⊆ ρ(g) },

dann gilt

∈∈_ω ∪ id_ω = ⊆_ω.

Wegen ∈∈_ω ∪ id_ω = ⊆_ω wird statt „x ⊆ y“  für x,y ∈∈ ω meist „x ≤ y“ geschrieben.

 N5
Sei x ∈∈ ω beliebig gewählt. Dann gilt x < s(x) und es existiert kein e ∈∈ ω mit x < e < s(x).

Die Nachfolgerfunktion trägt also ihren Namen zu Recht: Ist x ∈∈ ω, so folgt s(x) auf x bezüglich „<“ unmittelbar. s(x) heißt Nachfolgermenge (oder kurz: Nachfolger) von x. x_p heißt Vorgängermenge (oder kurz: Vorgänger) von x, wenn s(x_p) = x.

 N6
Jedes Element n von ω umfasst alle diejenigen Elemente von ω, die kleiner sind als n:

n = { x ∈∈ ω | x < n }  für alle n ∈∈ ω.

 N7
Mit ∈∈_ω ∪ id_ω ist ω wohlgeordnet.

Der nächste Satz besagt, dass Funktionen auf ω rekursiv definiert werden können:

 N8 (Rekursionssatz für ω)
Sei F ein Operator. Dann gibt es genau eine auf ω definierte Funktion f mit

RK    ∀n∈∈ω (f(n) = F(f_|n)).

 N9 (Einfacher Rekursionssatz für ω)
Sei F ein Operator und c eine beliebige Menge. Dann gibt es genau eine auf ω definierte Funktion f mit

f(Ø) = c
∀n∈∈ω (f(s(n)) = F(f(n))).

Aus  N9 folgt der Spezielle Rekursionssatz für ω, dessen Aussage dem Satz der Definition durch Induktion von Richard Dedekind entspricht (Nummer 126 in: Was sind und was sollen die Zahlen?):

 N10 (Spezieller Rekursionssatz für ω)
Sei m eine nichtleere Menge, c ∈∈ m und h: m → m. Dann gibt es genau eine Funktion f mit

f: ω → m
f(Ø) = c
∀n∈∈ω (f(s(n)) = h(f(n)).

 N11
Je zwei Peano-Strukturen sind isomorph zueinander.

Es ist bemerkenswert, dass für den vorstehenden Beweis alle Peano’schen Axiome benötigt werden. Außerdem ist hervorzuheben, dass die Tatsache, dass (ω,≤) eine Wohlordnung ist, bewiesen werden kann, ohne zuvor eine innere Verknüpfung auf ω definiert zu haben! Plakativ ausgedrückt: Man kann mit den Elementen von ω zählen ohne rechnen zu müssen. Das ist in ℕ anders.

N11 besagt, dass die den Peano’schen Axiomen genügende Struktur bis auf Isomorphie eindeutig bestimmt ist. Das Peano’sche Axiomensystem ist also monomorph (oder kategorisch).

Wegen (ω,s,Ø) ≅ (ℕ,succ,0) ist es nunmehr sinnvoll, die vonNeumann’schen Zahlen mit Hilfe der gewöhnlichen natürlichen Zahlen zu bezeichnen: 0 =_def Ø, 1 =_def { Ø }, 2 =_def { Ø, { Ø } }, ..., s(n) =_def n ∪ { n } und es gilt für beliebiges n ∈∈ ω und die Nachfolgermenge s(n) :

s(n) = { 0, 1, ..., n }.

Unter Benutzung dieser Bezeichnungen lässt sich auf ω eine Addition und eine Multiplikation definieren. Diese beiden zweistelligen Verknüpfungen haben die folgenden Eigenschaften:

(i)  s(n) =  n + 1
(ii)  n + 0 = n
(iii)  m + (n + 1) = (m + n) + 1
(iv)  n · 0 = 0
(v)  m · (n + 1) = m + (m · n)

Die bekannten Rechengesetze bezüglich „+“ und „·“, wie Kommutativ-, Assoziativ- und Dissoziativgesetze erschließt man sich durch Induktionsbeweise: vgl. Addieren und Multiplizieren natürlicher Zahlen.

 
Endliche Mengen

Üblicherweise nennt man eine Menge genau dann endlich, wenn man die Elemente dieser Menge mit Hilfe der natürlichen Zahlen abzählen kann. Es ist jedoch durchaus möglich, den Begriff „endliche Menge“ ohne Verwendung der natürlichen Zahlen zu definieren:

Es folgt unmittelbar, dass ℘(a):IND(a) für alle a gilt. Das heißt, es existiert immer mindestens ein induktives System in ℘(a), nämlich ℘(a) selbst.

Diese auf den ersten Blick möglicherweise irritierende Definition versteht man besser, wenn man sich deren anschauliche Bedeutung klarmacht. Man stelle sich einen Haufen mit beliebig vielen Objekten vor, wobei man zunächst nicht weiß, ob es sich hierbei um endlich viele Objekte handelt oder nicht. Nun nehme man sukzessiv Objekte aus dem Haufen heraus, in jedem Schritt jeweils ein Objekt. Endet dieser Wegnehme-Prozess irgendwann damit, dass der Haufen einmal gänzlich weg ist, weiß man: der Haufen bestand aus endlich vielen Objekten. Sei nun beispielsweise a = { u, v } (eine augenscheinlich endliche Menge :). Dann sind { Ø, { u }, { u, v } } und { Ø, { v }, { u, v } } Teilmengen von ℘(a) und repräsentieren die zwei kompletten und möglichen Wegnehme-Prozesse bei einem gegebenen Haufen mit zwei Objekten. Jedes Element von ℘(a) schließlich repräsentiert einen Zustand des (endlichen) Haufens während eines der möglichen Wegnehme-Prozesse. Und: für jeden dieser möglichen Zustände gibt es ein entsprechendes Element in ℘(a).

Aus der obigen Definition folgt sofort ein zwar trivialer, aber nichtsdestoweniger wichtiger Satz:

E1
Die leere Menge ist endlich.

Der nächste Satz ist grundlegend für viele Beweise von Aussagen über endliche Mengen.

E2
Sei a eine endliche Menge und b ∉∉ a. Dann ist auch a ∪ { b } endlich.

E3
a ist genau dann endlich, wenn jedes induktive System in ℘(a) a enthält.

E4
Sei a eine endliche Menge und t ⊂ a eine echte Teilmenge von a. Dann ist auch t endlich.

Sei φ ein Prädikat und m eine endliche Menge. Dann soll im Folgenden mit „φ_m“ die Aussage „φ(m) trifft zu“ gemeint sein. „φ_E“ bedeutet „φ trifft zu für alle Mengen, die endlich sind“.

E5
Sei φ ein Prädikat, das eine gewisse Eigenschaft endlicher Mengen beschreibt. Wenn die leere Menge diese Eigenschaft besitzt und ferner für eine beliebige endliche Menge m neben φ_m auch φ_m∪{b} für alle b ∉∉ m gilt, so besitzt jede endliche Menge diese Eigenschaft:

φ_Ø ˄ ∀m∈∈𝑬 ∀b∉∉m (φ_m ⇀ φ_m∪{b}) ⇀ φ_E

E6
Alle vonNeumann’schen Zahlen sind endlich:

n ∈∈ ω ⇀ n ∈∈ 𝑬

E7
Eine Menge a ist genau dann endlich, wenn ein n ∈∈ ω existiert, so dass n und a gleichmächtig sind. Kurz geschrieben:

  a ∈∈ 𝑬 ⇌ ∃n (n ∈∈ ω ˄ a ∼ n).

Sei a endlich. Dann existiert also eine Bijektion f: n _bij→ a mit n ∈∈ ω. Eine solche Bijektion heißt Abzählung von a der Länge n.

E8
Sei a eine endliche Menge. Dann haben alle Abzählungen von a dieselbe Länge.

Der eben bewiesene Satz ermöglicht die folgende Definiton:

Demnach sind endliche Mengen genau dann äquivalent, wenn sie die gleiche Mächtigkeit haben.
Für n ∈∈ ω gilt |n| = n.

E9
Sei a eine endliche Menge und t ⊂ a eine echte Teilmenge von a. Dann gilt |t| < |a|.

E10
Seien a und b endlich und disjunkt, also a ∩ b = Ø.
Dann ist auch a ∪ b endlich und es gilt |a ∪ b| = |a| + |b|.

E11
Für zwei endliche Mengen a und b gilt |a| + |b| = |a ∪ b| + |a ∩ b|.

E12
Für zwei endliche Mengen a und b gilt a x b ∈∈ 𝑬 und |a x b| = |a|·|b|.

E13
ω ist keine endliche Menge.

 
Fundierte Strukturen und Wohlordnungen

Es gilt der Induktionssatz für fundierte Strukturen:

W1 (Induktionssatz für fundierte Strukturen)
Wenn (m,r) eine fundierte Struktur ist, so gilt

∀a (∀x∈∈m (r[x]⊆a ⇀ x∈∈a) ⇀ m ⊆ a).

Sei (m,r) eine fundierte Struktur und φ ein einstelliges Prädikat. Dann folgt mit a = { x ∈∈ m | φ(x) } aus W1, dass

∀b∈∈m (∀x (x r b ⇀ φ(x)) ⇀ φ(b)) ⇀ ∀b∈∈m (φ(b)).

Mit dem Fundierungsaxiom (FND) folgt, dass (m,∈∈_m) eine fundierte Struktur ist. FND garantiert also, gegebenenfalls induktiv über ∈∈_m beweisen zu können, dass alle Elemente einer gegebenen Menge eine gewisse Eigenschaft haben.

Ein Anfangsabschnitt einer Wohlordnung ist immer wohlgeordnet.

W2
(m,r) und (m*,r*) seien Wohlordnungen. Sind f und g Isomorphismen von (m,r) auf Anfangsabschnitte von (m*,r*), so gilt f = g.

Es folgt sofort, dass, wenn es zwischen zwei Wohlordnungen einen Isomorphismus geben sollte, dieser eindeutig bestimmt ist. Ferner folgt aus W2

W3
Es gibt keinen Isomorphismus von einer Wohlordnung auf einen ihrer echten Anfangsabschnitte.

W4 (Vergleichbarkeitssatz für Wohlordnungen)
(m,r) und (m*,r*) seien Wohlordnungen. Dann ist (m,r) isomorph zu einem Anfangsabschnitt von (m*,r*) oder es ist (m*,r*) isomorph zu einem Anfangsabschnitt von (m,r).

Falls r ǂ ∈∈_m, kann es durchaus vorkommen, dass r[x] = r[y] für x,y ∈∈ m mit x ǂ y.

W5
Zwei Anfänge einer fundierten Struktur stimmen auf dem Durchschnitt ihrer Definitionsbereiche überein.

Es soll nun das Rekursionstheorem für fundierte Strukturen bewiesen werden:

W6 (Rekursionstheorem für fundierte Strukturen)
Sei F ein zweistelliger Operator und (m,r) eine fundierte Struktur. Dann existiert genau eine auf m definierte Funktion f, für die Folgendes gilt:

∀x (x ∈∈ m ⇀ f(x) = F(x, f_|r[x]) ).

 
Ordinalzahlen

Im vorletzten Abschnitt wurde gezeigt, dass man die Elemente jeder endlichen Menge mit Hilfe der natürlichen Zahlen bzw. der vonNeumann’schen Zahlen abzählen kann, anders ausgedrückt: man kann die Elemente einer endlichen Menge m nummerieren: erstes, zweites, drittes Element von m, und so fort. In diesem Abschnitt wird gezeigt, dass es auch möglich ist, die Elemente unendlicher Mengen zu nummerieren, und zwar mit Hilfe der sogenannten Ordinalzahlen.

Gemäß des Vorschlags von Wolfgang Rautenberg (1936−2011) kann eine Ordinalzahl wie folgt definiert werden:

Zur Erinnerung:

Da alle Elemente von ω transitive Mengen sind (N2) und jedes Element von ω nur Elemente von ω umfasst (N6), folgt sofort, dass alle n ∈∈ ω und ω selbst Ordinalzahlen sind. Die vonNeumann’schen Zahlen sind die einzigen endlichen Ordinalzahlen; ω ist die erste transfinite Ordinalzahl.

O1
Jedes Element einer Ordinalzahl ist ebenfalls eine Ordinalzahl.

O2
𝑶 ist eine echte Klasse.

O3
Sei α eine Ordinalzahl. Dann ist s(α), definiert durch s(α) =_def α ∪ { α }, auch eine Ordinalzahl.

Wegen O3 lässt sich die Zählreihe 0, 1, 2, ..., ω über ω hinaus fortsetzen. Die Nachfolgermenge von ω ist nach Definition s(ω) = ω ∪ { ω }; danach folgt ω ∪ { ω } ∪ { ω ∪ { ω } }, u.s.w. Diese hier banal klingende Aussage war zu Cantors Lebzeiten sensationell und geradezu ungeheuerlich. Er schreibt 1883 in seinen Grundlagen einer allgemeinen Mannigfaltigkeitslehre im §1:

Die Abhängigkeit, in welche ich mich von dieser Ausdehnung des Zahlbegriffs versetzt sehe, ist eine so große, daß es mir ohne letztere kaum möglich sein würde, zwanglos den kleinsten Schritt weiter vorwärts in der Mengenlehre auszuführen; möge in diesem Umstande eine Rechtfertigung oder, wenn nötig, eine Entschuldigung dafür gefunden werden, daß ich scheinbar fremdartige Ideen in meine Betrachtungen einführe. Denn es handelt sich um eine Erweiterung resp. Fortsetzung der realen ganzen Zahlenreihe über das Unendliche hinaus; so gewagt dies auch scheinen möchte, kann ich dennoch nicht nur die Hoffnung, sondern die feste Überzeugung aussprechen, daß diese Erweiterung mit der Zeit als eine durchaus einfache, angemessene, natürliche wird angesehen werden müssen. Dabei verhehle ich mir keineswegs, daß ich mit diesem Unternehmen in einen gewissen Gegensatz zu weitverbreiteten Anschauungen über das mathematische Unendliche und zu häufig vertretenen Ansichten über das Wesen der Zahlgröße mich stelle.

Also können wir bis jetzt wie folgt zählen:

0, 1, 2, ..., ω, ω+1, ω+2, ...

O4
𝑶 ist mit „∈∈“ partiell geordnet.

Man schreibt gewöhnlich „β < α“ statt „β ∈∈ α“. Für "β < α ˅ β = α" schreibt man „β ≤ α“.

O5
Sei m eine nichtleere Menge von Ordinalzahlen. Dann sind ∩m und ⋃m auch Ordinalzahlen.

Sei φ ein einstelliges Prädikat. Es soll nun bewiesen werden, dass φ auf alle Ordinalzahlen zutrifft, wenn man zeigen kann, dass φ auf eine beliebige Ordinalzahl α zutrifft unter der Voraussetzung, dass φ auf all diejenigen Ordinalzahlen zutrifft, die kleiner als α sind:

O6 (Satz von der transfiniten Induktion für 𝑶)
Sei φ ein einstelliges Prädikat und α ∈∈ 𝑶, dann gilt:

∀α (∀β<α (φ(β) ⇀ φ(α)) ⇀ ∀α (φ(α)).

Aus dem Induktionssatz für 𝑶 folgt der Satz von der kleinsten Ordinalzahl:

O7 (Satz von der kleinsten Ordinalzahl)
Jede nichtleere Menge m von Ordinalzahlen besitzt ein kleinstes Element. Formal geschrieben:

∃α∈∈m (∀β (β < α ⇀ β ∉∉ m)).

O8
𝑶 ist mit „<“ linear geordnet.

Von den Aussagen "α < β", "β < α" und "α = β" für zwei beliebig ausgewählte Ordinalzahlen kann stets nur genau eine Aussage richtig sein: Sowohl "α < β ˄ α = β" als auch "β < α ˄ α = β" können nie gelten wegen der Irreflexivität bezüglich „<“. Aus demselben Grund ist auch "α < β ˄ β < α immer eine falsche Aussage, denn mit α < β ˄ β < α würde wegen der Transitivität von „<“ die falsche Aussage "α ∈∈ α" folgen.

Aus O7 und O8 folgt sofort

O9
𝑶 ist wohlgeordnet.

Mit 𝑶 ist auch jede nichtleere Menge von Ordinalzahlen wohlgeordnet.

O10
Sei α eine beliebig gewählte Ordinalzahl. Dann gilt α < s(α) und es existiert keine Ordinalzahl ξ mit α < ξ < s(α).

ω ist die kleinste Limeszahl.

 O11
Jede Ordinalzahl α umfasst alle diejenigen Elemente von α, die kleiner sind als α:

α ∈∈ 𝑶 ⇀ α = { ξ ∈∈ s(α) | ξ < α }.

O11 besagt insbesondere, dass jede Ordinalzahl α ǂ Ø als nichtleere Menge von Ordinalzahlen wohlgeordnet ist.

O12
Sind zwei Wohlordnungen (α,∈∈_α) und (β,∈∈_β) isomorph zueinander, so gilt α = β.

Aus dem Rekursionstheorem für fundierte Strukturen folgt der Rekursionssatz für 𝑶, eine Verallgemeinerung vom Rekursionssatz für ω:

O13 (Rekursionssatz für 𝑶)
Sei F ein einstelliger Operator. Dann existiert für jede Ordinalzahl μ genau eine auf μ definierte Funktion f, für die Folgendes gilt:

∀ξ (ξ < μ ⇀ f(ξ) = F(f_|ξ) ).

O14
Für alle Ordinalzahlen gilt

α < β ⇌ α ⊂ β.

Aus O14 folgt sofort, dass auch

α ≤ β ⇌ α ⊆ β

gilt.

O15
Sei m eine nichtleere Menge von Ordinalzahlen. Dann ist ∩m das kleinste Element von m.

O16
Sei m eine nichtleere Menge von Ordinalzahlen. Dann ist m nach oben beschränkt und ⋃m das Supremum von m in 𝑶.

Mit O16 und O3 ist bewiesen, dass es zu jeder Menge α von Ordinalzahlen stets eine noch größere gibt: s(sup α) ist größer als jedes Element von α und größer als α.

Man mag sich an dieser Stelle erinnern, wie Cantor 1883 eine wohlgeordnete Menge charakterisiert hat. Er schreibt in seinen Grundlagen einer allgemeinen Mannigfaltigkeitslehre im §2:

Unter einer wohlgeordneten Menge ist jede wohldefinierte Menge zu verstehen, bei welcher die Elemente durch eine bestimmt vorgegebene Sukzession mit einander verbunden sind, welcher gemäß es ein erstes Element der Menge gibt und sowohl auf jedes einzelne Element (falls es nicht das letzte in der Sukzession ist) ein bestimmtes anderes folgt, wie auch zu jeder beliebigen endlichen oder unendlichen Menge von Elementen ein bestimmtes Element gehört, welches das ihnen allen nächst folgende Element in der Sukzession ist (es sei denn, dass es ein ihnen allen in der Sukzession folgendes überhaupt nicht gibt).

Ein echter Anfang μ von 𝑶, also eine Menge mit β < α ˄ α ∈∈ μ ⇀ β ∈∈ μ für alle α,β ∈∈ μ, ist als Teil von 𝑶 auch wohlgeordnet und lässt sich stets fortsetzen, das heißt: es gibt bei gegebenem μ immer eine nächste Ordinalzahl ν. Hat μ ein Maximum τ, dann gilt ν = s(τ) (ν ist dann eine Nachfolgerzahl), andernfalls setzt man ν = sup μ (dann ist ν eine Limeszahl).

O17
Sei φ ein einstelliges Prädikat. Gilt (i) φ(0), (ii) φ(α) ⇀ φ(s(α)) für alle Ordinalzahlen α und (iii) ∀β (β < λ ⇀ φ(β)) ⇀ φ(λ) für alle Limeszahlen λ, so gilt φ(α) für alle Ordinalzahlen α.

Mal angenommen, man hätte für irgendeine Menge ein geeignetes Verfahren gefunden, um die Elemente dieser Menge unter Verwendung der Ordinalzahlen wiederholungsfrei abzuzählen: m₀, m₁, m₂, m₃, ... Dann ist aufgrund des eben Gesagten nicht zu erwarten, dass diese Abzählung irgendwann einmal abbrechen könnte, etwa weil zum Weiterzählen nicht genügend viele Ordinalzahlen zur Verfügung stehen. Dieser Erwartung entsprechend gilt der nach Friedrich Moritz Hartogs (1874−1943) benannte Satz von Hartogs:

O18 (Satz von Hartogs)
Für alle Mengen m gibt es eine Ordinalzahl ξ, für die keine Injektion von ξ nach m existiert; als Formel geschrieben:

∀m ∃ξ (∄f ( f: ξ _inj→ m )).

O19
Sei w eine Wohlordnung. Dann gibt es genau eine Ordinalzahl ξ mit (ξ,∈∈_ξ) ≅ w.

O20
Eine Menge m ist genau dann zu einer Ordinalzahl gleichmächtig, wenn es eine Relation r gibt, so dass (m,r) eine Wohlordnung ist.

O20 ist der letzte der Bausteine, die nötig sind, um den von Cantor 1883 formulierten und von Zermelo 1904 erstmalig bewiesenen Wohlordnungssatz zu beweisen:

O21 (Wohlordnungssatz)
Für jede Menge m gibt es eine Relation r auf m, so dass m mit r wohlgeordnet ist.

Es folgt die möglicherweise sehr irritierende Tatsache, dass zum Beispiel auch ℝ, die Menge der reellen Zahlen, wohlgeordnet werden kann! Der Beweis des Wohlordnungssatzes liefert allerdings keinerlei Informationen darüber, mit welcher Relation ℝ wohlgeordnet werden bzw. auf welche Weise man eine solche Relation konstruieren könnte.

 
Die vonNeumann’sche Hierarchie

In Übereinstimmung mit der Definition eines Anfangs einer fundierten Struktur wird Folgendes festgelegt:

H1
Sei F ein einstelliger Operator. Dann gibt es einen Operator G mit

(*) G(m) = F(G_|m), falls m ∈∈ 𝑶; Ø sonst

und dieser ist mit (*) eindeutig festgelegt.

Sei der Operator F_V definiert durch

dann hat man mit H1 den eindeutig bestimmten Operator V mit

unter Beachtung der Tatsache, dass eine Ordinalzahl entweder gleich 0 oder eine Nachfolgerzahl oder eine Limeszahl ist.

Üblicherweise werden die Argumente von V als Indizes geschrieben, und zwar wie folgt:

Auf genau die gleiche Art wird weiter unten der Aleph-Operator ℵ definiert.

H2
V_μ ist eine transitive Menge für jede Ordinalzahl μ.

H3
Für beliebige Ordinalzahlen α und β gilt

(*)  β < α ⇀ V_β ∈∈ V_α
(**) β ≤ α ⇀ V_β ⊆ V_α

Sei nun

𝑽 =_def [ x | ∃α∈∈𝑶 ( x ∈∈ V_α) ]

die Klasse all derjenigen Mengen, die Element einer vonNeumann’schen Stufe V_α sind und m eine zu 𝑽 gehörende Menge. Dann gibt es eine Ordinalzahl μ mit m ∈∈ V_μ und gemäß AUS die Menge v_m =_def { β < s(μ) | m ∈∈ V_β }. v_m ist wegen μ ∈∈ v_m nicht leer, also besitzt nach O7 v_m ein kleinstes Element, etwa σ_m. Aufgrund der Definition des Operators V muss σ_m zwangsläufig eine Nachfolgerzahl sein, das heißt, es gilt σ_m = s(ρ_m) mit ρ_m als Vorgänger von σ_m. Somit ist ρ_m eindeutig bestimmt. Da für m lediglich die Zugehörigkeit zu 𝑽 vorausgesetzt wurde, gibt es ein derartiges ρ_m für alle m ∈∈ 𝑽, so dass die folgende Definition sinnvoll ist:

H4
Für alle Ordinalzahlen α gilt α ∈∈ 𝑽 und

rg(α) = α.

H5
Für alle x,y ∈∈ 𝑽 gilt

x ∈∈ y ⇀ rg(x) < rg(y).

H6
Es gilt

x ∈∈ 𝑽 ⇌ x ⊆ 𝑽.

Die Klasse 𝑽 ist nach den vorstehenden Ergebnissen kumulativ-hierarchisch aufgebaut. Es beginnt mit der leeren Menge und gemäß H3 umfasst dann jedes V_s(μ) alle vorherigen V_β:

V₀ = Ø
V₁ = { Ø }
V₂ = { Ø, { Ø } }
V₃ = { Ø, { Ø }, { { Ø } }, { Ø, { Ø } } }
u.s.f.

Jede zu 𝑽 gehörende nichtleere Menge m erscheint hierbei erstmalig als Teilmenge der rg(m)-ten Stufe, um dann den jeweils darauffolgenden Stufen als Element anzugehören. Umgekehrt umfasst jede Stufe V_s(μ) alle Mengen m mit rg(m) ≤ μ; insbesondere ist μ ∈∈ V_s(μ) für alle μ ∈∈ 𝑶. So gilt zum Beispiel für die Elemente von V₃:

rg({ Ø, { Ø } }) = rg(2) = 2,
 rg({ { Ø } }) = 2,
 rg({ Ø }) = rg(1) = 1,
 rg(Ø) = rg(0) =  0.

Die Anzahl N(μ) der Elemente in den vonNeumann’schen Stufen V_μ wächst mit zunehmendem μ stark an und wird sehr schnell unvorstellbar groß:

H7
Zu jeder Menge m gibt es eine transitive Obermenge und darüberhinaus eine kleinste transitive Obermenge. (Die somit eindeutig bestimmte kleinste transitive Obermenge von m heißt transitive Hülle von m.)

H8
Sei φ(m) ein einstelliges Prädikat. Wenn es eine Menge m gibt, auf die dieses Prädikat zutrifft, dann gilt

∃m (φ(m) ˄ ∀x (x ∈∈ m ⇀ ¬φ(x)))

H9
Zu jeder Menge m gibt es ein μ, so dass m ∈∈ V_μ, mit anderen Worten:

𝑩 = 𝑽.

 
Mächtigkeiten

Cantor beginnt seinen Beitrag zur Mannigfaltigkeitslehre 1878 mit den Worten „Wenn zwei wohldefinirte Mannigfaltigkeiten M und N sich eindeutig und vollständig, Element für Element, einander zuordnen lassen (was, wenn es auf eine Art möglich ist, immer auch noch auf viele andere Weisen geschehen kann), so möge für das folgende die Ausdrucksweise gestattet sein, dass diese Mannigfaltigkeiten gleiche Mächtigkeit haben, oder auch, dass sie äquivalent sind.“ In heutiger Sprache bedeutet das: Für zwei Mengen a und b gilt a ∼ b genau dann, wenn eine Funktion f existiert, so dass f: a _bij→ b (a und b heißen dann äquivalent oder gleichmächtig).

Gemäß dieser Definition ist das Prädikat ∼ offensichtlich reflexiv, symmetrisch und transitiv. ∼ hat also formal die gleichen Eigenschaften wie eine Äquivalenzrelation.

Aus der Definition von ≼ folgt wegen id_a: a _inj→ b sofort, dass

 a ⊆ b ⇀ a ≼ b.

Aufgrund von O14 bedeutet dies für Ordinalzahlen α und β:

α ≤ β ⇀ α ≼ β.

Die Implikationen a ⊂ b ⇀ a ≺ b bzw. α < β ⇀ α ≺ β sind im Allgemeinen nicht gültig! Man betrachte zum Beispiel eine Ordinalzahl α mit ω ≤ α. Dann gilt α < s(α) wegen O11, aber es ist α ∼ s(α), denn s ∪ id_|α\ω ∪ { (α; 0) } ist eine Bijektion von s(α) auf α.

Seien α und β voneinander verschiedene Ordinalzahlen. Gibt es dann eine Injektion von α nach β, so folgt, dass α eine Teilmenge von β sein muss, das heißt:

α ≺ β ⇀ α < β.

Hieraus folgt zusammen mit E9

∀m,n∈∈ω (m ≺ n ⇌ m < n).

M1
Wenn a ∼ a* und b ∼ b* gilt, so folgt

(i) a ≼ b ⇌ a* ≼ b*
(ii) a ≺ b ⇌ a* ≺ b*.

M2
Für alle Mengen a, b und c gilt

(i)  a ≼ a
(ii)  a ≼ b ˄ b ≼ c ⇀ a ≼ c
(iii)  a ≼ b ˅ b ≼ a.

M3
Ist a eine Teilmenge von b und b höchstens so mächtig wie a, dann sind a und b äquivalent:

a ⊆ b ˄ b ≼ a ⇀ a ∼ b.

M4 (Äquivalenzsatz)
Für alle Mengen a und b gilt

a ≼ b ˄ b ≼ a ⇀ a ∼ b.

Die Beweise von M3 und M4 orientieren sich an der Argumentation von Ebbinghaus (Einführung in die Mengenlehre, Kapitel IX, Satz 1.4(iii). Die zugrunde liegende Beweisidee geht zurück auf Zermelo, der den Äquivalenzsatz 1907 bewies (Untersuchungen über die Grundlagen der Mengenlehre. I., Nr. 25 und Nr. 27). In der Fußnote zu den Nrn. 25 und 27 schrieb Zermelo, dass der von ihm gegebene Beweis „im Gegensatz zu den älteren Beweisen von E. Schröder und F. Bernstein, sowie zu dem letzten Beweise von J. König ... jede Bezugnahme auf geordnete Reihen vom Typus ω oder das Prinzip der vollständigen Induktion“ vermeidet. Das Gleiche gilt für die Beweise von M3 und M4. (Der von Cantor 1883 formulierte Äquivalenzsatz wurde zuerst von Dedekind bewiesen: der Satz mit vollständigem Beweis wurde erst nach seinem Tod in seinem Tagebuch von 1887 gefunden.)

M5 (Satz von Cantor)
Die Potenzmenge einer Menge m ist stets mächtiger als m:

∀m (m ≺ ℘(m)).

M6
Zu jeder Ordinalzahl α gibt es eine Ordinalzahl, die mächtiger ist als α:

 ∀α∈∈𝑶 ∃β∈∈𝑶 (α ≺ β).

Mit M6 und O7 folgt die Existenz und die Eindeutigkeit der kleinsten Ordinalzahl κ, welche mächtiger ist als eine beliebig vorgegebene Ordinalzahl α:

 κ = min { β∈∈𝑶 | α ≺ β }.

Daher kann nun der Aleph-Operator ℵ definiert werden, und zwar auf die gleiche Art, in welcher oben der Operator V definiert wurde:

Jede endliche Menge ist äquivalent zu einer der vonNeumann’schen Zahlen 0, 1, 2, ... (→ Mächtigkeit endlicher Mengen). Es wird sich herausstellen, dass jede unendliche Menge zu einem der Alephs ℵ₀, ℵ₁, ℵ₂, ... äquivalent ist.

Aufgrund der Definition von ℵ sind alle Alephs Ordinalzahlen und es ist ℵ_α ≺ ℵ_s(α), also gilt auch ℵ_α < ℵ_s(α). Für jedes β mit ℵ_α ≤ β < ℵ_s(α) folgt β ∼ ℵ_α, denn mit β < ℵ_s(α) hat man β ≼ ℵ_s(α) und da β ∼ ℵ_s(α) wegen der Definition von ℵ_s(α) ausgeschlossen ist, ergibt sich β ≺ ℵ_s(α). Alle Ordinalzahlen, die zu einer Zahlklasse

 Z_α =_def [ β∈∈𝑶 | ℵ_α ≤ β < ℵ_s(α) ]

gehören, sind also einander äquivalent. ℵ_α ist die kleinste Ordinalzahl in Z_α und heißt deswegen Anfangszahl von Z_α. Desweiteren nennt man ω erste Zahlklasse, Z₀ zweite Zahlklasse, Z₁ dritte Zahlklasse, usf.

M7
Alle Alephs sind Limeszahlen:

 ∀α∈∈𝑶 (ℵ_α ∈∈ 𝑳).

M8
Für α,β ∈∈ 𝑶 gilt

(*)  α < β ⇀ ℵ_α ≺ ℵ_β.

M9
Für α,β ∈∈ 𝑶 sind die folgenden Aussagen äquivalent:

(i) α < β
(ii) ℵ_α ≺ ℵ_β.
(iii) ℵ_α < ℵ_β.

Aufgrund von M9 und der Definition von ℵ_λ ist ℵ ein normaler Operator.

M10
Sei ℱ ein normaler Operator und m eine nichtleere Menge von Ordinalzahlen. Dann gilt

ℱ (⋃m) = ⋃{ ℱ (α) | α ∈∈ m }.

M11
Sei ℱ ein normaler Operator. Dann gilt für alle α ∈∈ 𝑶:

(*) α ≤ ℱ (α),
(**) ∃β∈∈𝑶 (α ≤ β ˄ ℱ (β) = β).

M12
Sei ℱ ein normaler Operator und α eine Ordinalzahl mit ℱ (0) ≤ α. Dann existiert ein größtes β mit ℱ (β) ≤ α.

M13
Zu jeder Ordinalzahl α mit ω ≤ α gibt es genau ein β mit α ∼ ℵ_β und ℵ_β ≤ α.

𝑲, die Klasse der Kardinalzahlen, besteht also aus den vonNeumann’schen Zahlen und allen Alephs.

M14
Zu jeder Menge m existiert eine eindeutig bestimmte Kardinalzahl mit m ∼ κ:

∀m ∃!κ∈∈𝑲 (m ∼ κ ).

Auf Grundlage von M14 kann nunmehr die Mächtigkeit einer Menge definiert werden:

Jede endliche Menge ist abzählbar; ω ist abzählbar unendlich; ℘(ω) ist nach dem Satz von Cantor überabzählbar. ℵ₁ ist die kleinste überabzählbare Ordinalzahl.

Für alle Kardinalzahlen κ gilt

|κ| = κ.

Ferner gilt für alle Mengen a und b

a ∼ b ⇌ |a| = |b| 
a ≼ b ⇌ |a| ≤ |b| 
a ≺ b ⇌ |a| < |b|.

Im Kapitel Zahlen wird detailliert beschrieben, wie nacheinander ℕ zu ℤ, ℤ zu ℚ und ℚ zu ℝ erweitert werden kann. Die Gesamtheit aller ganzen Zahlen, die Gesamtheit aller rationalen Zahlen und die Gesamtheit aller reellen Zahlen können auf der Grundlage von ω unter Verwendung der mengentheoretischen Definition des kartesischen Produkts und unter Beachtung des Auswahlaxioms auch durch Mengen im Sinne von ZFC repräsentiert werden. Denn bezeichnet man die zu einer Äquivalenzrelation r auf einer Menge v gehörende Quotientenmenge wie üblich mit „v/r“, dann kann

ℤ = ℕxℕ/r alias ℤ = ωxω/r mit
(n; m) r (n*; m*) ⇌ m + n* = n + m*
für (n; m) (n*; m*) ∈∈ ℕxℕ;

ℚ = ℤx(ℤ\{ 0 })/s mit
(a; b) s (a*; b*) ⇌ a · b* = b · a*
für (a; b),(a*; b*) ∈∈ ℤx(ℤ\{ 0 });

ℝ = f_C/t mit
(x_n) t (y_n) ⇌ (x_n − y_n) ist eine Nullfolge
für (x_n),(y_n) ∈∈ f_C

gesetzt werden, wobei f_C die Menge aller rationalen Cauchyfolgen darstellt. Es ist möglich, auf ℤ, ℚ bzw. ℝ jeweils eine additive Verknüpfung „+“ als auch eine multiplikative Verknüpfung „·“ so zu definieren, dass ℕ in ℤ, ℤ in ℚ, sowie ℚ in ℝ eingebettet werden können. Es existieren also Monomorphismen von ℕ nach ℤ, ℤ nach ℚ bzw. ℚ nach ℝ, mit anderen Worten: es gilt ℕ ∼ ℕ' ⊆ ℤ, ℤ ∼ ℤ' ⊆ ℚ, ℚ ∼ ℚ' ⊆ ℝ und damit ℕ ≼ ℤ, ℤ ≼ ℚ und ℚ ≼ ℝ.

Sei die Funktion f von ℚ nach ℕ (ab jetzt verlaufen die Argumentationen außerhalb von ZFC!) wie folgt definiert:

 g (±z/n) =_def 2^s·p^z·qⁿ

für teilerfremde natürliche Zahlen z und n mit n ǂ 0.  Es  soll s = 1 im Fall „+z/n“ und s = 0 im Fall „−z/n“ gelten; p und q sind Primzahlen mit p ǂ q und p,q ǂ 2. Dann ist f injektiv, also gilt ℚ ≼ ℕ. Zusammen mit ℕ ≼ ℚ folgt hieraus nach dem Äquivalenzsatz |ℕ| = |ℚ| und damit

|ℕ| = |ℤ| = |ℚ| = ω.

M15
Es gilt

|ℕxℕ| = |ℕ|.

Sei n ∈∈ ℕ beliebig gewählt. Dann gilt für alle Felder (i; j) der n-ten Diagonale im obigen Gitterdiagramm i+j = n. Damit hat man p(i; j) = p(0; n)+ i. Wegen

p(0; n) = n∑j = 0j = n(n+1)/2

folgt

p(i; j) = (i+j)(i+j+1)/2 + i.

Mit M15 hat man beispielsweise auch |ℤxℤ| = |ℤ| und |ℚxℚ| = |ℚ|, denn die Elemente jeder abzählbaren Menge a lassen sich mit Hilfe der natürlichen Zahlen nummerieren: a₀, a₁, a₂, ... Man beweist dann |axa| = |a| auf die gleiche Weise wie M15. Statt i wird a_i und statt j wird a_j genommen und man setzt z₀ = a₀ sowie z₁ = a₁.

Welche Aussagen sind nun möglich im Hinblick auf die Menge der reellen Zahlen? Auf jeden Fall gilt ℵ₀ < |ℝ| bzw. ℕ ≺ ℝ, denn ℝ ist überabzählbar.

M16
Sei (u, v) ein offenes Intervall in ℝ, dann gilt

|(u, v)| = |ℝ|.

M17
Es gilt

|ℝxℝ| = |ℝ|.

M18
Sei m eine Menge. Dann ist die Potenzmenge von m äquivalent zur Menge aller Funktionen von m nach { 0, 1 }.

℘(m) ∼ ^m{ 0, 1 }.

M19
Sei ℘_∞(ℕ) die Menge aller unendlichen Teilmengen von ℕ. Dann gilt

℘_∞(ℕ) ∼ ℘(ℕ).

M20
Es gilt

ℝ ∼ ℘(ℕ).

1877 stellte sich Cantor die Frage (Ein Beitrag zur Mannigfaltigkeitslehre, §8), „wie sich die verschiedenen Theile einer stetigen geraden Linie, d. h. die verschiedenen in ihr denkbaren unendlichen Mannigfaltigkeiten von Punkten hinsichtlich ihrer Mächtigkeiten verhalten“ und er schreibt weiter:

Entkleiden wir dieses Problem seines geometrischen Gewandes und verstehen ... unter einer linearen Mannigfaltigkeit reeller Zahlen jeden denkbaren Inbegriff unendlich vieler, von einander verschiedener reeller Zahlen, so fragt es sich in wie viel und in welche Klassen die linearen Mannigfaltigkeiten zerfallen, wenn Mannigfaltigkeiten von gleicher Mächtigkeit in eine und dieselbe Klasse, Mannigfaltigkeiten von verschiedener Mächtigkeit in verschiedene Klassen gebracht werden.  Durch ein Inductionsverfahren, auf dessen Darstellung wir hier nicht näher eingehen, wird der Satz nahe gebracht, dass die Anzahl der nach diesem Eintheilungsprincip sich ergebenden Klassen linearer Mannigfaltigkeiten eine endliche und zwar, dass sie gleich zwei ist.
Darnach würden die linearen Mannigfaltigkeiten aus zwei Klassen bestehen, von denen die erste alle Mannigfaltigkeiten in sich fasst, welche sich auf die Form: functio ips. ν (wo ν alle positiven ganzen Zahlen durchläuft) bringen lassen; während die zweite Klasse alle diejenigen Mannigfaltigkeiten in sich aufnimmt, welche auf die Form: functio ips. x (wo x alle reellen Werthe ≥0 und ≤1 aufnehmen kann) zurückführbar sind.

Cantor vermutete also, dass für alle unendlichen Mengen x mit x ⊆ ℝ

entweder x ∼ ω oder x ∼ ℝ

folgt, mit anderen Worten:

(CH)   |ℝ| = ℵ₁.

Cantor hat über viele Jahre vergeblich versucht, seine Kontinuumshypothese zu beweisen. Er musste an dieser Aufgabe scheitern, denn Kurt Gödel konnte 1938 zeigen, dass die Kontinuumshypothese nicht widerlegbar ist; Paul Cohen hat 1963 nachgewiesen, dass die Kontinuumshypothese nicht beweisbar ist. Die Kontinuumshypothese ist also eine von ZFC unabhängige Aussage. Falls ZFC widerspruchsfrei sein sollte (was nach dem Zweiten Unvollständigkeitssatz von Gödel grundsätzlich nicht beweisbar ist), dann ist sowohl ZFC mit (CH), als auch ZFC mit ¬(CH) widerspruchsfrei. Es ist demnach innerhalb von ZFC nicht entscheidbar, ob |ℝ| = ℵ₁ oder aber ℵ₁ < |ℝ| gilt: ZFC ist eine unvollständige Theorie (was sich nach dem Ersten Unvollständigkeitssatz von Gödel prinzipiell nicht vermeiden lässt).

 
Symbole und Abkürzungen

Literatur- und Quellenangaben:

Galileo Galilei:
Unterredungen und mathematische Demonstrationen über zwei neue Wissenszweige, die Mechanik und die Fallgesetze betreffend, Erster bis Sechster Tag Arcetri, 6. März 1638
Wissenschaftliche Buchgesellschaft 1973

Georg Cantor:
Ein Beitrag zur Mannigfaltigkeitslehre, 1877
Journal für die reine und angewandte Mathematik 84. Band, S. 242−258

Richard Dedekind:
Was sind und was sollen die Zahlen?
Friedrich Vieweg Verlag, 1887

Georg Cantor:
Grundlagen einer allgemeinen Mannigfaltigkeitslehre. Ein mathematisch-philosophischer Versuch in der Lehre des Unendlichen.
Teubner Verlag, Leipzig,1883

Georg Cantor:
Beiträge zur Begründung der transfiniten Mengenlehre, 1895
Mathematische Annalen 46. Band, S. 481–493

Ernst Zermelo:
Untersuchungen über die Grundlagen der Mengenlehre. I, 1908
Mathematische Annalen 65. Band, S. 261–281

Kazimierz Kuratowski:
Sur la notion de l’ordre dans la théorie des ensembles, 1921
Fundamenta Mathematicae Volume 2, S. 161–171

A. Fraenkel:
Zu den Grundlagen der Cantor-Zermeloschen Mengenlehre, 1922
Mathematische Annalen 86. Band, S. 230−237

A. Fraenkel:
Axiomatische Begründung der transfiniten Kardinalzahlen. I., 1922
Mathematische Zeitschrift 13, S. 153−188

A. Fraenkel:
Einleitung in die Mengenlehre, 1928
Die Grundlehren der mathematischen Wissenschaften, Band IX

John von Neumann:
Über die Definition durch transfinite Induktion und verwandte Fragen der allgemeinen Mengenlehre, 1928
Mathematische Annalen 99. Band, S. 373–391

Heinz-Dieter Ebbinghaus:
Einführung in die Mengenlehre
Spektrum Akademischer Verlag, 4. Auflage 2003

Wolfgang Rautenberg:
Grundkurs Mengenlehre
Vorlesungsskript 2008

Oliver Deiser:
Einführung in die Mengenlehre
www.aleph1.info 2018

Chris Preston:
Finite Sets and Counting
https://arxiv.org/abs/0809.0105v2 2010