dh-Materialien
Mathematische Begriffe
 

Menge

 
Nicht-axiomatische Mengenlehre nach oben

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 ...“ (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. 19353, 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.“

Heute wird der Inbegriff alles Denkbaren „Allklasse“ genannt und es gilt: Die Allklasse 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,

Kugelmenge

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

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

oder die Menge bestimmter Objekte durch deren Eigenschaft:

M3 = { x M2 | x < 10 }.

In der Menge M3 sind all diejenigen Elemente aus M2 enthalten, die kleiner als 10 sind.

Ist x ein Element einer Menge M, so schreibt man „x  M“. Ist x nicht Element einer Menge M, so schreibt man „x  M“. Die Menge { }, die keine Elemente hat, heißt leere Menge.

Seien nun M und N zwei nichtleere Mengen. Wenn x  N aus x  M folgt, so schreibt man „M  N“ („M ist Teilmenge von N“). Kurz geschrieben:

(x M  x N) def  M

Sei M  N. Wenn es ein Objekt x gibt mit x  N und x  M, so ist M eine echte Teilmenge von N und man kann in diesem Fall schreiben: „M  N“.

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)

M  N =def x | x  M und x  N } heißt Durchschnitt von M und N.
M  N =def x | x  M oder x  N } heißt Vereinigung von M und N.

Venn-Diagramme veranschaulichen diese Definitionen:

Vereinigung    Durchschnitt

M und N heißen disjunkt genau dann, wenn M  N = { }.

M\N =def x | x  M und x  N } heißt Differenz von M und N.
Ist N  M, so heißt  M\N  Komplement von N bezüglich M und wird mit „N“ bezeichnet.

Differenz

Sämtliche Teilmengen einer Menge M bilden zusammen die Potenzmenge von M:

(M) =defT | T  M }

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 „T“ steht für „wahr“, das Symbol „F“ steht für „falsch“. "p  q" bedeutet "wenn pso q"; "p  q" bedeutet "p genau dann, wenn q" oder "p dann und nur dann, wenn q".

KonjunktionAlternationKonditionalBi-Konditional

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 pso 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 AB, AB 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:

(i)    Idempotenzgesetze:
        A A = A  und  A A = A
(ii)    Kommutativgesetze:
        A  B = B  A  und   B = B  A
(iii)   Assoziativgesetze:
        A  (B  C= (A  B) C  und  A  (B  C= (A B) C   
(iv)   Distributivgesetze:
        A  (B  C= (A ∩ B (A  C)  und  A  (B  C= (A ∪ B (A  C)
(v)    de Morgan’sche Gesetze:
        A B = A  B  und  A  B = A  B 
(vi)   Absorptionsgesetze:
        A  (A  B= A  und  A  (A  B= A
(vii)  Komplementgesetze:
        A A = { } und  A A = M 
(viii) M = { }  und  { } = M
(ix)   B = A  B = A 
(x)    { }  (M

Beweis:
Man überzeugt sich von der Gültigkeit dieser Gesetze auf rein logischem Wege mit Hilfe von Verknüpfungstafeln. Sei mit „a“ die Aussage "xA" bezeichnet, mit ab die Aussage "xund xB", mit avb die Aussage "xoder xB", und so fort. Die beispielsweise zum ersten Distributivgesetz gehörende Verknüpfungstafel sieht wie folgt aus

Tafel

und man erkennt an den gelb unterlegten Spalten, dass xA und (xB oder xC) ⇔ (xA und xBoder (xA und xC),
was gleichbedeutend ist mit A (B  C= (A ∩ B (A  C).

Die Aussage (x) sieht auf den ersten Blick merkwürdig aus. Sie besagt in Worten, dass die leere Menge Teilmenge von jeder Menge M ist, das heißt: wenn x  { }, so x M.
Die Aussage "x  { }" ist jedoch immer falsch, und deswegen ist die gesamte Konditionalaussage wahr (vgl. oben die entsprechende Verknüpfungstafel)!

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

 
Widersprüche! nach oben

Wenn gewisse Objekte x eine gemeinsame Eigenschaft E haben, liegt es nahe, diese Objekte zu einer Menge zusammenzufassen: ME =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 Russelsche 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 Russellschen Antinomie zugrunde liegt (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  { 0, 1, 2, ... } =  = 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  5  7  11  .... = { 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 nach oben

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 Fraenkel (1891 - 1965) und 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.

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.

Alle Aussagen in ZFC können in einer Sprache formuliert werden, deren Zeichen das jeweils Folgende bedeutet:

kleine Buchstaben   Variablen zur Bezeichnung von Mengen
das Zeichen „=   Gleichheitsbeziehung zwischen zwei Mengen
das Zeichen „   Elementbeziehung zwischen zwei Mengen
das Zeichen „˄   Junktor und
das Zeichen „˅   Junktor oder
das Zeichen „   Junktor wenn, so
das Zeichen „   Junktor genau dann, wenn
das Zeichen „¬   Junktor nicht
das Zeichen „∃“   Quantor Es existiert
das Zeichen „∀“   Quantor Für alle
das Zeichen „(“   öffnende Klammer
das Zeichen  „)“   schließende Klammer
das Zeichen  „,“   Trennzeichen

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

Der Ausdruck "∀ab(¬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:

abc (((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. "∃!a" soll "Es existiert genau ein a" bedeuten. "(x  a˄ (y  a)" wird ersetzt 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))". Der Ausdruck "∀a(a  m  φ(a))" bedeutet: "Für alle Mengen, 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: "∀am (φ(a))".

Das Prädikat

φT(a,b) =defe (e  a  e  b),

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

φP(a,b) =defe (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:

φZ(a,b,c) =defe ((e  b  e  a)˄(e  a e  c))

und mit

φN(a) =defe (e  a

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

Dadurch, dass mit φT(a,b), φP(a,b), φZ(a,b,c) bzw. φN(a) bestimmte Mengen formelhaft beschrieben sind, ist nicht ausgesagt, dass derartige Mengen überhaupt existieren!

Es sollen nun die Axiome von ZFC vorgestellt werden:

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

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:

 Existenzaxiom
Es gibt eine Menge.

EXZ   ∃m (= m)

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:

 Extensionalitätsaxiom
Ist a eine Teilmenge von b und b eine Teilmenge von a, so sind a und b einander gleich.

EXT   ∀a,b (∀e (e  a  e  b a = b)

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.

 Paarmengenaxiom
Seien a und b irgendwelche Mengen. Dann gibt es eine Menge, die genau a und b als Elemente enthält.

PMG    ∀a,b ∃c ∀(d  c  (d = a ˅ d = b))

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 1921 vorgeschlagen hat:

Seien x und y zwei beliebige Mengen, dann heißt

(x; y) =def { { x }, { xy } }

geordnetes Paar von x und y.

Die Aussage „g ist ein geordnetes Paar“ soll im Folgenden mit „g:GPR“ abgekürzt werden.

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

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

Beweis:
“: unmittelbar klar.
“: Sei (x; y= (u; v), also { { x }, { x, y } = { { u }, { u, v } }.
Entweder es ist x = y oder es ist x ǂ y.
Im ersten Fall folgt wegen { { x }, { x, x } = { { x }, { x } = { { x } }
{ { x } = { { u }, { u, v } }.
Hieraus folgt sowohl u = v als auch u = x und wegen x = y auch y = v.
Sei nun der zweite Fall, also x ǂ y, angenommen.
Dann ergibt sich wegen der Zweielementigkeit von { x, y }
{ x = { u } und { x, y = { u, v }.
Mit EXT folgt x = u und damit auch y = v.  

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

 Aussonderungsaxiom
Sei m eine Menge und φ(e) ein Prädikat. Dann gibt es eine Menge, die genau diejenigen Elemente e von m enthält, für die φ(e) wahr ist.

AUS   ∀m ∃x ∀(e  x  (e  m ˄ φ(e)))

φ(e) kann außer e noch weitere freie Variablen enthalten, die man Parameter nennt.

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 ],

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:

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

Beweis:
Sei m eine beliebige Menge, dann existiert gemäß AUS die eindeutig bestimmte Menge m* mit

m* =def  { e  m | e  e }.

Dann gilt entweder m*  m* oder m*  m*.
Unter der Annahme, dass m*  m* wahr ist, würde m* ein Element e mit e  e enthalten (nämlich sich selbst). Allerdings besteht m* nach Definition aus all den Mengen, die sich nicht selbst enthalten. Widerspruch zur Annahme! Also folgt m*  m*.
Angenommen nun, es wäre m*  m, dann würde aufgrund der Definition von m* auch m*  m* gelten. Widerspruch! Es gilt also m*  m.  

Die Allklasse ist keine Menge.

Beweis:
Wäre die Allklasse eine Menge, dann wäre gemäß des vorstehenden Beweises *  . Dies ergibt einen Widerspruch, denn umfasst ja nach Definition alle Mengen, darunter also auch *!

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:

Es gibt eine (eindeutig bestimmte) Menge ohne Elemente:

∃!e (e  x).

Beweis:
Sei m eine beliebig gewählte Menge und φE(e,m) =def e  m.
Dann folgt mit AUS:x ∀(e  x  (e  m ˄ e  m)).
Unabhängig von der Wahl von e bzw. m ist die
Aussage "e  m ˄ e  m" immer falsch.
Also hat man: ∃x ∀(e  x).
Mit EXT folgt: ∃!x ∀(e  x),
was äquivalent ist zur behaupteten Aussage.

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

 Potenzmengenaxiom
Zu jeder Menge m gibt es eine Menge, die alle Teilmengen von m enthält.

POT   ∀mpm e (e  m  e  pm)

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

(m) =defe  pme 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  pm | e  m } gesehen werden, andererseits kann man „“ als Operationssymbol betrachten und „(m)“ als Bild unter der Potenzmengenoperation, die eine existierende Menge m auf ihre Potenzmenge abbildet.

Sei φ(x,y) ein zweistelliges Prädikat und es gelte

x ∃!y (φ(x,y))

dann heißt φ(x,y) rechtseindeutig oder auch funktional. Ein funktionales Prädikat φ(x,y) besagt, dass jeder Menge x die eindeutig bestimmte Menge y zugeordnet wird. Man schreibt hierfür y = F(x). F heißt Operator.

Ein funktionales Prädikat φ(x,y) kann unter Umständen außer x und y noch weitere freie Variablen (sogenannte Parameter) enthalten.

Das Potenzmengenprädikat lautet

φP(a,b) =defe (e  b  (∀x (x  e  x  a))).

 Seien a und b zwei beliebige Mengen, dann gilt

PP   x  a ˄ y  b (x; y ((a  b)).

Beweis:
Aus x  a ˄ y  b folgt { x }, { x, y } a  b,
das heißt: { x }, { x, y  (a  b), also:
{ { x }, { x, y }  ((a  b)), was zu zeigen war.

Es gibt ein-elementige Mengen. Präziser: zu jeder Menge m existiert die Einermengem }, das heißt diejenige Menge, die nur m als einziges Element enthält.

Beweis:
Zu jeder Menge m gibt es gemäß POT und EXT die eindeutig bestimmte Potenzmenge (m). Wegen m  m folgt mit AUS die Existenz der Menge { t ∈ (m) | t =m } } =m }.


 Vereinigungsaxiom
Zu jeder Menge m gibt es eine Menge, die alle Elemente der Elemente von m enthält.

VER   ∀m vm a,e (a  m ˄ e  a  e  vm)

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

   m =def  { e  vm | ∃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 ta  t, zu der all die Elemente von t gehören, die a als Element besitzen:

ta =def  { e  t | a  t ˄ a  e }.

Für jedes a gilt entweder ta = t oder ta ǂ t. Sei nun e*  t beliebig gewählt. Dann ist d = { a  e* | ta = 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 ab } = a  b wie oben bereits definiert.

Seien a und b zwei beliebige Mengen. Dann gibt es gemäß PMG und EXT die eindeutig bestimmte Paarmenge { ab } und nach VER und AUS die Menge, die alle Elemente von a und b enthält, und nur diese: ab } = { e  vab | e  a ˅ e ∈ b }. ab } heißt Vereinigung von a und b und man schreibt ab } = 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.

 Ersetzungsaxiom
Sei φ(x,y) ein funktionales Prädikat. Ersetzt man jedes Element x einer Menge durch das durch φ(x,y) eindeutig gegebene y, erhält man wieder eine Menge. Mit φxy =def φ(x,y) gilt

ERS   ∀φxy(∀x,y,z (φxy ˄ φxz y = z)v ∃w ∀x,y (e  v ˄ φxy y  w))

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.

 Unendlichkeitsaxiom
Es existiert eine Menge, die Ø als Element enthält und mit jedem Element e dieser Menge auch e  { e } als Element enthält.

INF   ∃x (Ø  x ˄e (e  x e  { e }  x))  

Eine nach INF existierende Menge 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:

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

(Zermelo’s ursprüngliches 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 oben angegebenen Fassung basiert auf einem Vorschlag von John von Neumann (1903–1957).

 Fundierungsaxiom
Jede nichtleere Menge m enthält ein Element e, so dass e und m disjunkt sind, mit anderen Worten: jede nichtleere Menge ist fundiert.

FND    ∀m (m ǂ Ø ∃e (e  m ˄ e  m = Ø))

Ausführlich geschrieben: ∀m (m ǂ Ø ∃e (e  m ˄ ∄x (x  m ˄ x  e)).

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, deren Elemente alle die Eigenschaft haben, Element des „nächsten“ Elementes von m zu sein: e1  e2  e3 ...  en  e1. 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!

 Auswahlaxiom
Ist a eine Menge von paarweise disjunkten und nichtleeren Mengen, dann gibt es eine Menge, die genau ein Element aus jedem Element von a enthält.

AWL    ∀a (x,y (x,ya xǂØ ˄ yǂØ ˄ (x=y ˅ xy=Ø)) b ∀x (xa  ∃z (bx={z})))

Seien a und b Mengen wie in AWL beschrieben, dann besteht b*, definiert durch b* =def b  a, nur aus den „ausgewählten“ Elementen z. b* heißt Auswahlmenge für a.

 
Relationen und Funktionen nach oben

Dieser Abschnitt dient im Wesentlichen dazu, all diejenigen Begriffe bereitzustellen und zu erläutern, die in den folgenden Abschnitten benötigt werden.

Mit φL(g,u) =defv (g = (uv)) und φR(g,v) =defu (g = (uv)) 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 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

Seien a und b zwei beliebige Mengen, dann heißt die nach AUS existierende Menge

a x b =defe  ((a  b)) | e:GPR ˄ λ(e a ˄ ρ(e b }

das kartesische Produkt von a und b.

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

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

Seien a und b zwei beliebige Mengen und φ(x,y) ein Prädikat. Dann ist die gemäß AUS existierende Menge

r = { (x; y a x bφ(x,y) }

eine Relation zwischen a und b. Ist r a x a, dann wird r eine Relation auf a (manchmal auch Relation in oder über a) genannt. Statt „(x; y r“ wird üblicherweise auch „x r y“ geschrieben.

Ersetzt man gemäß ERS jedes Element (x; y) von r durch die linke Komponente von (x; y), erhält man die nach EXT eindeutig bestimmte Menge

dom(r) =defλ(g) | g  r } =x | ∃y ((x; y r) },

den so genannten Definitionsbereich von r (englisch: domain). Die Menge

rng(r) =defρ(g) | g  r } = { y | ∃x ((x; y r) }

heißt Wertebereich von r (englisch: range).

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 mit AWL keine Aussage darüber möglich ist, wie und auf welchem Weg diese Auswahl zu bewerkstelligen sein könnte.

Ist f eine Relation zwischen a und b und gilt für alle x  a und für alle y, y*  b

(x; y f ˄ (x; y* f y = y*,

so nennt man f eine Funktion.

Die Aussage „f ist eine Funktion“ soll im Folgenden mit „f:FKT“ abgekürzt werden.

Anstatt „f:FKT ˄ dom(f) = a ˄ rng(f) b “ soll abkürzend „fa  b“ geschrieben werden (man sagt: „f ist eine Funktion von a nach b“). b heißt Zielbereich von f. Ist (xy f bzw. x f y, dann schreibt man (wie gewohnt) „y = f(x)“ und nennt y das Bild von x unter f und x Urbild von y unter f.

Sei fa  b. Wenn x ǂ x* f(xǂ f(x*) für alle x, x*  dom(f) gilt, dann nennt man f eine Injektion: fa inj b.  Gilt fa  b und rng(f= b, dann nennt man f eine Surjektion und man sagt, dass f „eine Funktion von a auf b“ ist:  fa sur b. Ist f eine Injektion und eine Surjektion, dann heißt f Bijektionfa bij b.

Aus mengentheoretischer Sicht ist also jede Funktion eine Menge, präziser: eine Teilmenge des kartesischen Produktes zweier Mengen im Gegensatz zur üblichen 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 fa  b folgt f  (a x b). Demzufolge ist die Klasse ab aller Funktionen von a nach b wegen AUS eine Menge:

ab =deff  (a x b) | fa  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 fa inj b. Dann existiert gemäß ERS die Menge f1 =def { (yx) | (xy f }. Wegen der Injektivität von f ist f1 ebenfalls eine Funktion. dom(f1= rng(f). f1 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 fa bij a, so nennt man f eine Permutation von a. Die Bijektion ida mit ida(x= x für alle x  a heißt identische Funktion.

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

Zwei Mengen a und b heißen äquivalent (oder gleichmächtig) genau dann, wenn eine Funktion f existiert, so dass fa bij b. Man schreibt in diesem Fall: „a ∼ b“ und „fa ∼ b“.

Sind f und g Funktionen mit rng(f) dom(g), dann existiert gemäß AUS die Menge { x  dom(fx rng(g) | ρ(x= g(f(πl(x))) }, einfacher formuliert: { (ug(f(u))) | u  dom(f) }.
Also ist die folgende Definition statthaft:

Seien f und g zwei Funktionen mit rng(f) dom(g), dann heißt

gf =def { (ug(f(u))) | u  dom(f) }, falls f,g:FKT ˄ rng(f dom(g); Ø sonst.

Hintereinanderschaltung (oder: Komposition) von f und g.


Sind f und g Funktionen mit dom(g) dom(f) und f(x= g(x) für alle x  dom(g), dann heißt f eine Fortsetzung von g; umgekehrt ist g eine Restriktion von f.

Die Restriktionsoperation wird wie folgt definiert:

f|a=def  f  (a x rng(f)), falls f:FKT ˄ a dom(f); Ø sonst

Sei f:FKT und a dom(f), dann gilt f|a f ˄ f|a:FKT, dom(f|a= a und f|a(x= f(x) für alle x  a.

k mit k nennt man eine Funktionenkette, wenn f g oder g f für alle f,g  k.

Die Aussage „k ist eine Funktionenkette“ wird im Folgenden mit „k:FKK“ abgekürzt.

 Es gilt

FK   ∀k (k:FKK  k:FKT ˄ dom(k= dom(f) | f  k }).

Beweis:
(i) zu zeigen: k:FKT.
k = { g | ∃f (f  k ˄ g ∈ f) }
     = { (x; y) | ∃f (f  k ˄ (x ∈ dom(f˄ y = f(x))) }
     = { (x; y) | ∃f ((f  k ˄ x ∈ dom(f)) ˄ y = f(x)) }
Angenommen, (x; y),(x; y*)  k mit y ǂ y*.
Dann existieren zwei Funktionen f,g  k mit (xy f ˄ (xy* g ˄ f ǂ g.
Wegen k:FKK ist dann entweder f  g oder g  f.
f  g  (x; y),(x; y*)  g Widerspruch, weil g:FKT.
g  f  (x; y),(x; y*)  f Widerspruch, weil f:FKT.
Aus (x; y),(x; y*)  k folgt demnach stets y = y*, also ist k eine Funktion.

(ii) dom(k= { x | ∃f (f  k ˄ (x; y) ∈ f) }.
Sei df =def dom(f) und vf =def {dom(f) | f  k }, dann ist v = { x | ∃df (df  vf ˄ x ∈ df) };
zu zeigen: dom(k= v.

Sei x  dom(k).
Dann existieren f  k und y  ω mit (x; y) ∈ f.
Wegen f  k ist df  vf ˄ x ∈ df, also folgt x  v.

Sei umgekehrt x  v.
Dann existiert ein df mit df  vf ˄ x ∈ df.
Wegen df  vf ist (1) f  k. Wegen x ∈ df gibt es ein y mit (2) (x; y) ∈ f.
Aus (1) ˄ (2) folgt x  dom(k).

Mit EXT folgt dom(k= v.

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

Ist m eine Menge und f: m  m oder f: m x m  m, so nennt man f eine (einstellige bzw. zweistellige) Verknüpfung (auf m bzw. auf m x m) und (m,f) eine algebraische Struktur. Existiert auch eine Relation r auf m, die für die Struktur von m wichtig ist, so erweitert sich das Tupel (m,f) zu (m,f,r). Gibt es darüberhinaus noch ein Element c von m, dem bezüglich f oder r eine besondere Bedeutung zukommt, erhält man das Quadrupel (m,f,r,c).

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

Seien A = (a,f,r,c) und B = (b,g,s,d) algebraische Strukturen. Dann ist ψ genau dann ein Isomorphismus von A auf B (in Zeichen: „ψA ≅ B“),  wenn Folgendes gilt:

ψa bij b
xa (ψ(f(x)) = g(ψ(x))), falls f,g einstellig
x,ya (ψ(f(xy)) = g(ψ(x); ψ(y))), falls f,g zweistellig
x,ya (x r y  ψ(xs ψ(y))
ψ(c= d

Wenn ein Isomorphismus von A auf B existiert, dann sagt man „A und B sind isomorph“:

A  B.

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

Beweis:
Seien x*,y* ∈ b beliebig gewählt.
Dann gibt es x,y ∈ a mit ψ(x= x* ˄ ψ(y= y*.

Falls f und g zweistellige Verknüpfungen sind, gilt
ψ
(f(xy)) = g(x*; y*) wegen ψA ≅ B
und damit hat man ψ1(x*; y*) = f(xy= f(ψ1(x*); ψ1(y*)).
Sind f und g einstellige Verknüpfungen, so folgt
ψ1(x*) = f(x= f(ψ1(x*)) aus ψ(f(x)) = g(x*).

Seien x*,y* ∈ b nun so gewählt, dass xs y*.
xs y*  ψ(xs ψ(y)  x r y  ψ1(x*) r ψ1(y*).

ψ(c= d  ψ1(d= c.

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.

 
Natürliche Zahlen als Mengen nach oben

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 { Ø, { Ø } },..., ns =def n  { n } unter Benutzung der „gewöhnlichen“ natürlichen Zahlen 0, 1, 2, ..., so gilt für beliebiges n und die Nachfolgermenge ns:

ns =01, ..., 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

(I)*   w ǂ Ø
(II)*  ∃s (σ:w w ˄ ∀x,y (x,y  dom(σ) ˄ x ǂ y  σ(xǂ σ(y)))
(III)* ∃! o  w (o  rng(σ))  
(IV)*t (t  w ˄ o  t ˄ ∀x (x  t  σ(x t t = w)

o heißt Nullmenge, σ wird Nachfolgerfunktion genannt. Sind die Axiome (I)* bis (IV)* gültig, dann sagt man kurz: „(w,σ,o) ist eine Peano-Struktur“.

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:

Beweis (erster Teil):
(i) (I)* gilt, denn Ø  ω.

Sei s =defe  ω x ωπr(e= πl(e { πl(e) } }.
s ist gemäß AUS wohldefiniert und
es gilt s:ω ω mit s(x= x  { x },
denn es gilt x  ω x  { x }  ω für alle x  ω
(weil ω eine induktive Menge ist),
und s ist rechtseindeutig:
Aus x = y folgt mit EXTx } = { y }
und somit gilt auch s(x= s(y).

(iii)  Nach Definition von s gilt für alle y  rng(s)
       ∃x ( ω ˄ = x  { x } ),
       woraus folgt, dass y ǂ Ø für alle y  rng(s).
       Also gilt Ø  rng(s), womit (III)* erfüllt ist mit o =  Ø.

(iv)  ω ist die „kleinste“ induktive Menge, präziser:
       jede Teilmenge von ω ist keine induktive Menge,
       das heißt: ∀t (t  ω ˄ Ø  t ˄ ∀x (x  t  s(x t t = ω).
       Dies ist genau die Aussage von (IV)*, wenn w = ω.

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 (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)

Beweis:
Sei φn =def ∀x (x  n  x n).
zu zeigen: φnω, mit anderen Worten: φn trifft für alle n  ω zu.
Induktionsanfang:
Es gilt φn, denn Ø besitzt kein Element und deshalb gibt es nichts nachzuweisen.
Induktionsvoraussetzung:
Es gelte φn=m für ein beliebig gewähltes m  ω.
Induktionsschluss:
Wegen φn=m gilt x m für alle x  m.
s
(m= m  { m }. Sei nun x  s(m).
Dann gilt (1) x  m oder (2) x  { m }.
(1) x m      nach Induktionsvoraussetzung
     
x  s(m)  wegen m s(m).
(2) x = m
      x s(m)  wegen EXT
Es gilt also auch φn=s(m) und damit die behauptete Aussage.

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

Beweis (zweiter Teil):
(ii) Sei s(x= s(y) für x,y  ω angenommen,
     dann ist zu zeigen, dass x = y gilt.
     Aus s(x= s(y) folgt zunächst nach Definition von s
     x  { x } = y  { y }.
     Damit gilt entweder x = y oder x  y ˄ y  x.
     Aus x  y ˄ y  x folgt wegen TM x y ˄ y x.
     Mit EXT folgt x = y und damit (II)*.

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 gezeigt werden, dass die Elemente von ω angeordnet werden können, und zwar mit der -Relation auf ω, definiert durch ω =def { g  ω x ω | λ(g ρ(g) }. "(xy ω" ist gleichbedeutend mit "x ω y"; für "x ω y" soll im Folgenden der Einfachheit halber nur "x  y" geschrieben werden.

 N3
ω ist mit „total geordnet, das heißt, ω 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)

Beweis:
Seien im Folgenden x, y und z Elemente von ω.
(i) Als Folgerung aus FND wurde oben bereits notiert, dass es keine Menge gibt, die sich selbst als Element besitzt. Damit ist die Irreflexivität von ω bereits bewiesen.

(ii) Aus x y ˄ y  z folgt mit TM x  y ˄ y z, also gilt auch x z.

(iii) Sei φn = φ(n=def ∀x (n  x ˅ n = x ˅ x  n).
zu zeigen: φnω, mit anderen Worten: φ(n) trifft für alle n  ω zu.
Induktionsanfang:
zu zeigen: φn: ∀x (Ø  x ˅ Ø = x ˅ x  Ø).
Es genügt zu zeigen, dass ∀x (Ø  x ˅ Ø = x),
denn "x  Ø" ist für alle x eine falsche Aussage.
"∀x (Ø  x ˅ Ø = x)" wird bewiesen durch vollständige Induktion über x:
     "Ø  Ø ˅ Ø = Ø" ist eine wahre Aussage, denn "Ø = Ø" ist wahr.
     Es gelte nun Ø  m ˅ Ø = m für ein beliebig gewähltes m  ω.
     Es folgt sofort Ø  s(m) wegen s(m= m  { m }.
Induktionsvoraussetzung:
Es gelte φn=m für ein beliebig gewähltes m  ω, also:
x (m  x ˅ m = x ˅ x  m).
Induktionsschluss:
zu zeigen: φn=s(m): ∀x (s(m x ˅ s(m) = x ˅ s(m)).
Falls x  m, so gilt wegen s(m= m  { m } auch x  s(m).
Falls m = x, so gilt x m } und somit ebenso x  s(m).
Bleibt noch der Fall "m  x" übrig.
Es gilt

SM    ∀x,mω (m  x  s(m x ˅ s(m) = x),

was durch vollständige Induktion über x bewiesen werden kann:
     Für x = Ø gibt es nichts zu zeigen, denn "m  Ø" ist für alle m falsch.
     Es gelte m  k  s(m k ˅ s(m= k
     für ein beliebiges, aber fest gewähltes k  ω.
     Sei nun m  s(k).
      m  k ˅ m = k,
      (s(m k ˅ s(m) = k) ˅ m = k  (nach Induktionsvoraussetzung)
      (s(m k ˅ s(m) = k) ˅ s(m= s(k)  (s ist rechtseindeutig!)
      (s(m s(k)) ˅ s(m= s(k)  (nach Definition von s).

Man macht sich schnell klar, dass von den Aussagen "x y", "x = y" und "y  x" für zwei beliebig ausgewählte xy ω 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 xy ω 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 idm = 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ω = ω.

Beweis:
Gemäß EXT hat man ω  idω  ω und ω  ω  idω nachzuweisen.

(i)  zu zeigen:ω  idω  ω.
Aus (x; y ω  idω folgt x  y ˅ x = y.
Mit TM ergibt sich x  y, das heißt: (x; y ω.

(ii) zu zeigen: ω  ω  idω 
Die Aussage "(x; y ω  (x; y ω  idω"
ist äquivalent zu "(x; y ω  idω  (x; y ω".
Sei (x; y ω  idω
x  y ˄ x ǂ y
y  x  (wegen der Konnexität von ω)
y  x  (wegen TM)
Angenommen, es gilt (xy ω.
x  y ˄ y  x
x = y. Widerspruch!
Es gilt also (xy ω, was zu zeigen war.

Wegenω  idω = ω wird statt "x  y" für x,y ω meist "x  y" geschrieben.

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

Beweis:
Es gilt x  { x } und damit auch x  x  { x }, was x < s(x) bedeutet.

Es gibt kein e  ω mit e  Ø, also ist Ø bezüglich „<“ das kleinste Element von ω.
Wegen s(Ø) = { Ø } gilt Ø < s(Ø). Ø ist das einzige Element von s(Ø)
und damit das einzige Element, was kleiner ist als s(Ø).

Sei nun m  ω mit m ǂ Ø, aber ansonsten beliebig gewählt.
Angenommen, es gibt ein e ∈ ω mit m < e < s(m).
m < e ist gleichbedeutend mit m  e.
Wegen e  ω existiert ein x  ω mit e = x  { x } und x < e.
Dann ist entweder m  x oder m = x.
Im Fall "m = x" hat man e = m  { m } = s(m). Widerspruch zur Annahme!
Im Fall "m  x" folgt mit SM s(m x ˅ s(m= x.

Mit s(m x ergibt sich s(m< e < s(m).
Hieraus folgt s(m< s(m) (wegen der Transitivität von ω)
und dies ist eine falsche Aussage wegen der Irreflexivität von ω.
Aus s(m= x folgt die falsche Aussage "x < e < x".

Die obige Annahme kann demnach nicht richtig sein, woraus die Behauptung folgt.

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. Die Nachfolgermenge von x soll mit „xs“ bezeichnet werden. xp heißt Vorgängermenge (oder kurz: Vorgänger) von x, wenn s(xp= x.

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

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

Beweis (durch Induktion über n):
Induktionsanfang:
Für n = Ø ist die Behauptung richtig, denn Ø ist das kleinste Element von ω. Induktionsvoraussetzung:
Es gelte m =x  ω | x < m } für ein gewisses m  ω.
Induktionsschluss:
ms = s(m= m  { m } = { x  ω | x < m }  { m }.
mp  m und mpmms sind bezüglich „<“ unmittelbar aufeinanderfolgend.
Also gilt ms =x  ω | x < ms }.

 N6
Mit ω  idω ist ω wohlgeordnet.

Beweis:
Seien x, y, z ω beliebig gewählt.
(i)   zu zeigen: x  y ˄ y  z  x  z   (Transitivität)
ω und idω sind transitiv, also auch ω  idω.

(ii)  zu zeigen: x  y ˄ y  x  x = y   (Identitivität)
Da die Aussagen "x < y" und "y < x" sich gegenseitig ausschließen,
folgt aus x  y ˄ y  x, dass x und y gleich sein müssen.

(iii) zu zeigen: x  x   (Reflexivität)
Die Aussage "x  x" ist wahr, weil x = x immer gilt.

(iv) zu zeigen: Jede nichtleere Teilmenge von ω hat bezüglich “ ein kleinstes Element.
Sei t  ω mit t ǂ Ø.
Im Fall t = ω ist Ø das kleinste Element.
Alle t  ω mit Ø  t haben demnach auch Ø als kleinstes Element.
Für alle t  ω mit Ø  t gilt t ǂ Ø, denn die Durchschnittsmenge t umfasst alle Objekte, die Element von jedem Element von t sind und wegen Ø  t ist Ø  n für alle n  t. t enthält also mindestens Ø als Element. Somit gibt es ein n*  t mit s(n* t (wäre es nicht so, würde die offensichtlich falsche Aussage t = ω folgen). Also hat man t = s(n*= { x  ω | x  n* }. Hieraus ergibt sich s(n* e für alle e  t. Nun ist aber s(n* t, also muss s(n* t gelten, womit s(n*) als kleinstes Element von t gefunden ist.

Der Rekursionssatz für ω besagt, dass Funktionen auf ω rekursiv definiert werden können:

 N7
Sei F ein Operator. Dann gibt es genau eine auf ω definierte Funktion f mit

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

Beweis:
RK kann man unter Verwendung von ERS umformulieren zu folgender Aussage:
RK*   ∀nω (f(Ø) = Ø ˄ f(ns) = F({ (x; f(x) | x  n }).
Hierbei beachte man, dass f|Ø = Ø, weil Ø keine Elemente besitzt.

(i)  zu zeigen: Es gibt höchstens eine Funktion, die RK erfüllt.
Seien f und g zwei Funktionen, die RK* erfüllen.
zu zeigen: f = g, das heißt: f(n) = g(n) für alle n ω.
Zunächst gilt f(Ø) = g(Ø) und hieraus folgt
f({ Ø }) = F({ (Ø; f(Ø)) }) = F({ (Ø; g(Ø)) }) = g({ Ø })
und für beliebiges n ω:
f(ns) = F({ (x; f(x) | x  n }) = F({ (x; g(x) | x  n }) = g(ns).

(ii) zu zeigen: Es gibt eine Funktion f mit den geforderten Eigenschaften.
Hierzu wird definiert: a ist genau dann ein echter Anfang von ω (kurz: „a:EAN“), wenn
a
  ω mit ∀n,ma (m < n ˄ n a  m a).

Sei a die Klasse aller Funktionen f mit dom(f):EAN und f(n= F(f|n) für alle n  dom(f).
Auf jeden Fall ist a nicht leer, denn wegen f(Ø) = F(Ø) ist (Ø; F(Ø))  a.
Mit beliebig gewählten f1,f2 a ist dann entweder dom(f1 dom(f2) oder dom(f2 dom(f1). Ohne Beschränkung der Allgemeinheit sei dom(f1 dom(f2).

Wegen Ø dom(f1) folgt analog zur Argumentation unter (i)
f1
(Ø) = f2(Ø) und darüberhinaus f1(n= f2(n) für alle n dom(f1).
Damit hat man f1  f2, also ist a eine Funktionenkette.
Wegen FK ist auch v =def a eine Funktion und es gilt dom(v= dom(f) | f  a }.
dom(v) ist als Vereinigung echter Anfänge ebenso ein echter Anfang.

zu zeigen: v(n) = F(v|n) für alle n dom(v).
Wenn n dom(v), so existiert f a mit n dom(f).
Sowohl dom(f) als auch dom(v) sind echte Anfänge und es ist f  v,
also gilt f|n = v|n und damit v(n= f(n= F(f|n= F(v|n).
Somit ist v a und zwar mit der Eigenschaft, dass
(*) f  v für alle f a.

Angenommen, dom(vǂ ω. Dann hat ω\dom(v), die Differenz von ω und dom(v), als Teilmenge der wohlgeordneten Menge ω ein kleinstes Element, das mit n* bezeichnet werden soll. Mit dom(v { n* } erhält man gemäß ERS v* = v  { (n*; F(v)) } als Fortsetzung von v. Daraus folgt v*  a und v  v*. Widerspruch zu (*)! Es folgt also dom(v= ω, was noch zu beweisen war.

Aus dem Rekursionssatz für ω 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?):

 N8
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)).

Beweis:
Sei F ein Operator, c eine beliebige Menge und  ω.
Dann ist G, definiert durch

G(x=def F(x(n)), falls x:FKT ˄ dom(x= s(n); c sonst

ebenfalls ein Operator und es existiert nach dem Rekursionssatz für ω genau eine Funktion f auf ω, so dass f(n) = G(f|n) für alle n  ω.
Hieraus folgt mit Ø:FKT ˄ dom(Ø) = Ø ˄ ∄n(Ø = s(n)): f(Ø) = G(Ø) = c.
Wegen f:FKT ˄ s(n) ω hat man f|s(n):FKT ˄ dom(f|s(n)) = s(n).
Damit ergibt sich f(s(n)) = G(f|s(n)= F(f(n)) für alle n  ω.

Sei nun m eine beliebige nichtleere Menge, c  m, hm  m und F speziell gewählt:

F(x=def h(x), falls  m; Ø sonst.

Dann gilt F(x= h(x) für alle x  m und es gibt nach dem Vorstehenden genau eine Funktion f mit

f(Ø) = c ˄ f(s(n)) = F(f(n)) für alle n ω.

Es ist f(Ø) m und mit f(n) m ist wegen F(f(n)) = h(f(n)) = f(ns) auch f(ns) m.
Damit hat man rng(f m und so auch f(s(n)) = F(f(n)) = h(f(n)) für alle n ω.

 N9
Je zwei Peano-Strukturen sind isomorph zueinander.

Beweis:
Sei (w,σ,o) eine Peano-Struktur. Dann ist w gemäß Axiom (I)* nicht leer und es gibt aufgrund des eben bewiesenen speziellen Rekursionssatzes eine eindeutig bestimmte Funktion f, so dass das Folgende gilt:

f: ω  w
f
(Ø) = o
nω (f(s(n)) = σ(f(n)).

f ist dann ein Isomorphismus, wenn gezeigt werden kann, dass f eine Bijektion ist.
zu zeigen: (i) f: ω sur w. und (ii) f: ω inj w.

(i) (w,σ,o) erfüllt als Peano-Struktur das Axiom (IV)*:
t (t  w ˄ o  t ˄ ∀x (x  t  σ(x t t = w).
Es gilt rng(f w und es ist o  rng(f).
Für jedes x  rng(f) existiert ein n  ω mit x = f(n).
Es folgt also σ(x) = σ(f(n)) = f(s(n rng(f)
und damit hat man mit (IV)*: rng(f= w, was zu zeigen war.

(ii) zu zeigen: ∀nω (∀xω (x ǂ n  f(xǂ f(n))).
Induktionsanfang:
Sei n = Ø. f(Ø) = o und o  rng(σ) gemäß Axiom (III)*.
Wenn x ǂ Ø, so hat x eine Vorgängermenge xp, das heißt: x = s(xp).
f(x) = σ(f(xp)), also f(x rng(σ).
Insgesamt folgt demnach f(xǂ f(Ø). 
Induktionsvoraussetzung:
Es gelte ∀xω (x ǂ m  f(xǂ f(m)) für ein beliebig gewähltes m  ω.
Induktionsschluss:
Sei x ǂ s(m).
Falls x = Ø folgt analog zum Induktionsanfang f(Ø) ǂ f(s(m)).
Sei also x ǂ Ø, mit anderen Worten: x = s(xp).
Wegen s(xpǂ s(m) hat man xp ǂ m, weil s:FKT.
Mit der Induktionsvoraussetzung folgt f(xpǂ f(m) und damit
σ(f(m)) ǂ σ(f(xp)) wegen σ: w inj w gemäß (II)*.
f(s(m) = σ(f(m)).
f(x) = f(s(xp)) = σ(f(xp)).
Mit σ(f(xp)) ǂ σ(f(m)) folgt f(xǂ f(s(m), was zu zeigen war.

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.

Wegen (ω,s,Ø) ≅ (,succ,0) kann man nun die vonNeumann’schen Zahlen mit Hilfe der gewöhnlichen natürlichen Zahlen bezeichnen: 0 =def Ø, 1 =def { Ø }, 2 =def { Ø, { Ø } }, ..., ns =def n  { n } und es gilt für beliebiges n  ω und die Nachfolgermenge ns:

ns =01, ..., 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)

Beweis:
Sei n  ω beliebig, aber fest gewählt. Dann gibt es nach dem speziellen Rekursionssatz für ω genau eine Funktion addn mit

addn: ω  ω
addn
(0) = n
nω (addn(s(m)) = s(addn(m))).

Sei + =defx  (ω x ω) x ωρ(x= addλ(λ(x))(ρ(λ(x))) },
einfacher geschrieben: + = { ((nm); k) | k = addn(m) }.
+:FKT, denn +|{n}xω:FKT für alle n  ω
wegen +|{n}xω(nm) = addn(m) für alle n,m  ω.

(i)   n + 1 = addn(s(0)) = s(addn(0)) = s(n).
(ii)  n + 0 = addn(0) = n.
(iii) m + (n + 1) = addm(s(n)) = s(addm(n)) = s(m + n) = (m + n) + 1.

Zu jedem n  ω gibt es neben addn auch genau eine Funktion muln mit

muln: ω  ω
muln
(0) = 0
nω (muln(s(m)) = addn(muln(m))).

Sei · =defx  (ω x ω) x ωρ(x= mulλ(λ(x))(ρ(λ(x))) },
einfacher geschrieben: · = { ((nm); k) | k = muln(m) }.
Analog zu oben gilt ·:FKT.

(iv) n · 0 = muln(0) = 0.
(v)  m · (n + 1) = mulm(s(n)) = addm(mulm(n)) = 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 nach oben

Ü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, und zwar auf eine Weise, wie es Alfred North Whitehead and Bertrand Russell in ihrer Principia Mathematica 1913 erstmalig gemacht haben:

Sei a eine Menge, (a) die Potenzmenge von a und s  (a) eine Teilmenge von (a).
s ist ein induktives System in (a) (kurz formuliert: „s:IND(a)“) genau dann, wenn  

Ø  s ˄ ∀ts ∀xa\t (t  { x }  s).

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.

Eine Menge a ist genau dann endlich (kurz formuliert: „a:EDL“), falls (a) das einzige induktive System in (a) ist.

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.

Beweis:
Sei a eine endliche Menge, b  a und s* ein induktives System in (a  { b }).
Mit s =deft  s* | t  a } folgt s:IND(a).
Weil a endlich ist, gilt s = (a).
Da s nach Definition eine echte Teilmenge von s* ist, folgt (1) (a s*.

Wegen s*:IND(a  { b }) gilt ∀ts* ∀xab }\t (t  { x }  s*).
Insbesondere gilt also (2) ∀t(a) (t  { b }  s*).
Aus (1)˄(2) folgt (a  { b }) = (a { t  { b } | t  (a) }  s*
und weil andererseits s (a  { b }) gilt s= (a  { b }).
Daraus  folgt, dass a  { b } endlich ist.

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

Beweis:
“:
Sei a eine endliche Menge. Dann ist (a) das einzige induktive System in (a) und es gilt a  (a).

“:
Angenommen, a  s, falls s:IND(a).
Sei s* =def { t  (a) | t:EDL }.
Dann ist Ø  s* wegen E1.
Falls t  s* und x  a\t, so folgt t  { x }  s* wegen E2.
Damit ist aber s*:IND(a).
Wegen a  s* (aufgrund der getroffenen Annahme) folgt a:EDL.

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

Beweis:
Sei a:EDL und s =deft  (a) | t:EDL }.
ts ∀xa\t (t  { x }  s) wegen E2 und es ist Ø  s wegen E1.
Dies ist gleichbedeutend mit s:IND(a), also s = (a),
mit anderen Worten: ∀ta (t:EDL).

Sei φ ein Prädikat und m eine endliche Menge. Dann soll im Folgenden mit „φm“ die Aussage „φ(m) trifft zu“ gemeint sein. „φ:EDL“ 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:EDL ˄ φm ˄ b  m  φm{b}) φ:EDL

Beweis:
Sei φ ein Prädikat mit φØ, m eine endliche Menge und b  m.
Es gelte unter diesen Bedingungen φm  φm{b},
das heißt, wenn φ für m zutrifft, so auch für m{b}.

Sei nun a eine beliebig gewählte endliche Menge.
Mit s =def { t  (a) | φt } hat man dann zunächst Ø  s.
Wegen E4 gilt t:EDL für jedes t  s.
Nach Voraussetzung gilt demnach auch φt{b} falls t  s und b  a\t.
Dann gilt mit t  s auch t{b s. Also folgt s:IND(a).
Wegen a:EDL hat man s = (a).
Hieraus folgt a  s weil a  (a). Also gilt φa.
Demnach trifft φ für alle endlichen Mengen zu, denn a war beliebig gewählt.

E6
Alle vonNeumann’schen Zahlen sind endlich. Präziser:

n  ω  n:EDL

Beweis:
Induktionsanfang:
Ø:EDL.
Induktionsvoraussetzung:
Es gelte m:EDL für ein gewisses m  ω.
Induktionsschluss:
s(m= m  { m }.
m  m. Also folgt mit E2 s(m):EDL und damit die Behauptung.

E7
Eine Menge a ist genau dann endlich, wenn ein n  ω existiert mit a ∼ n.

Beweis:
“:
Es gilt Ø: 0 bij Ø, in Worten: die leere Funktion bildet 0 bijektiv auf die leere Menge ab.
Sei nun a eine beliebig gewählte endliche Menge.
Angenommen, es gibt ein n  ω mit a ∼ n.
Dann existiert f mit fn bij a.
Mit XN folgt f = { (xf(x)) | x = 0 .. np }.
Sei nun b eine beliebige Menge mit b  a.
Mit VER hat man f* =def f  { (nb) } und damit f*a{bbij s(n).
Wegen E5 folgt: Für alle endlichen Mengen a gibt es ein n  ω mit a ∼ n.

“:
Sei n  ω und a eine Menge mit a ∼ n.
Also gibt es ein f mit fn bij a, das heißt:
a
 = { ai | i = 0 .. np } mit ai =def f(i) für i  n.
Sei s (a) mit s:IND(a) und sei t  s.
Dann ist a\t = { aj | j < n ˄ aj  t }.
Umnummerierung liefert a\t = { aj | j = 0 .. k } mit einem gewissen k < n.
Sei t0 =def t und tj+1 =def tj  { aj } für j = 0 .. k.
Dann gilt { tj | j = 0 .. k }  s wegen s:IND(a).
Da a = { tj | j = 0 .. k } folgt a:EDL wegen E3.

Sei a endlich. Dann existiert also eine Bijektion fn 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.

Beweis:
Wegen x ∼ y ˄ y ∼ z  x ∼ z ist die zu beweisende Aussage äquivalent zu: 

ZS    ∀n,kω (n ∼ k  n = k).

ZS lässt sich durch Induktion über n beweisen.
Induktionsanfang:
Aus n = Ø ˄ n ∼ k folgt n = Ø = k.
Induktionsvoraussetzung:
Es gelte m ∼ k  m = k für ein beliebig gewähltes m  ω.
Induktionsschluss:
Sei fs(m) ∼ k. Dann ist k ǂ Ø und k = s(kp).
Falls f(mǂ kp, sei π diejenige Permutation von k, die f(mund kp miteinander vertauscht;
falls f(m) = kp, sei π = idk.
Dann folgt πfs(m) ∼ k ˄ (πf)(m) = kp und damit hat man
πf \ { (mkp) }: m ∼ kp.
Mit der Induktionsvoraussetzung folgt m = kp,
also gilt s(m) = s(kp) = k, was zu zeigen war.

Der eben bewiesene Satz ermöglicht die folgende Definiton:

Sei a eine endliche Menge und n  ω mit a ∼ n.
Dann ist n die Mächtigkeit von a (in Zeichen: „|a= n“).

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|.

Beweis:
(i) zunächst zu zeigen: ∀nω ∀t (t  n  |t< n).
Induktionsanfang:
Ø besitzt keine echte Teilmenge.
Also ist für n = Ø nichts nachzuweisen.
Induktionsvoraussetzung:
Es gelte ∀t (t  m  |t< m) für ein gewisses m  ω.
Induktionsschluss:
Sei t eine beliebige echte Teilmenge von s(m).
Dann ist entweder m  t oder m  t.
Aus m  t folgt s(m t im Widerspruch zu t  s(m).
Es gilt also m  t.  
Hieraus folgt mit XN t  m, was t  m bedeutet.
   Wenn t = m, so folgt |t= m < s(m).
   t  m iefert |t< m < s(m) nach Induktionsvoraussetzung.

(ii) Sei nun a:EDL ˄ t  a.
Wegen a:EDL gibt es ein n  ω mit |a= n,
das heißt, es existiert eine Funktion f, so dass fn bij a.
Somit existiert auch f1, so dass f1a bij n.
Ausserdem gilt f1|tt bij x mit x  n wegen t  a.
Mit der unter (i) bewiesenen Aussage folgt |x< n
und hiermit |t< |a| wegen t ∼ x und a ∼ n.

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

Beweis:
Wenn a = Ø ˅ b = Ø, so ist die behauptete Aussage offensichtlich wahr.
Seien also beide Mengen a und b endlich und nicht leer und a  b = Ø.
Dann existieren zwei Funktionen f und g, so dass
fn bij a und gm bij b mit 0 < n und 0 < m.
Gemäss VER hat man die Menge h = f  g,
deren Elemente nach ERS unter Verwendung des folgenden Operators ersetzt werden können:
F((ix)) =def (ix), falls x  a; (i+nx), falls x  b; 0 sonst.
Es ist F(h): n+m bij a  b. Damit folgt die behauptete Aussage.

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

Beweis:
Sei a,b:EDL und x =def a  b und y =def a \ x = a \ b.
Wegen x  a und y  a folgt x,y:EDL und es gilt
(1) a  b = y  b, wobei y  b = Ø und
(2) a = x  y, wobei x  y = Ø.
Aus (1) folgt: (y  b):EDL und |a  b| = |y| + |b|
und aus (2): |a| = |x| + |y| = |a  b| + |y|.
Hieraus folgt die Behauptung.

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

Beweis:
Wenn a = Ø ˅ b = Ø, so ist die behauptete Aussage offensichtlich wahr.
Seien also beide Mengen a und b endlich und nicht leer.
Dann existieren zwei Funktionen f und g, so dass
fn bij a und gm bij b mit 0 < n und 0 < m.
Sei fi =def { (vx f | v = i } für i = 01, ..., np.
Die fi sind gemäß AUS (einelementige) Mengen: fi = { (if(i) }.
Mit ERS gelangt man zu den Mengen { f(i) }; i = 01, ..., np.
Mit bi =def { f(i) } x b gilt |bi| = m für i = 01, ..., np.
Alle diese bi sind paarweise disjunkt, also folgt
|a x b| = |b0  b1 ...  bnp| = n·m, was zu beweisen war.

E13
ω
ist keine endliche Menge.

Beweis:
Angenommen, ω ist endlich.
Dann existiert nach E7 ein n  ω mit ω ∼ n.
n ist gemäß E8 eindeutig bestimmt und es gilt |ω= n.
Nach N5 umfasst n alle x  ω mit  x < n.
Demnach ist n  ω und es gilt |n= n = |ω|.
Dies ist ein Widerspruch zu E9, also ist ω unendlich.

  
Ordinalzahlen nach oben

in Bearbeitung


Kardinalzahlen nach oben

in Bearbeitung

 

 

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

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

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, 1907
Mathematische Annalen 65. Band, S. 261 - 281

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

Wolfgang Rautenberg:
Grundkurs Mengenlehre
Vorlesungsskript 2008

Stefan Geschke:
Einführung in die Mengenlehre
Vorlesungsskript 2010

Chris Preston:
Finite Sets and Counting
arXiv:0809.0105v2 [math.HO] 2010


 Home   Back   Top