MengenlehreSkriptum zur Vorlesung (WS 2000/01)

Klaus Gloede

L i t e r a t u r :

A. Zur Einführung und zum Gebrauch neben der Vorlesung:

Ebbinghaus, D.: Einführung in die Mengenlehre, BI 1994

Friedrichsdorf, U.-Prestel, A.: Mengenlehre für den Mathematiker, vieweg studium 1985

Oberschelp, A.: Allgemeine Mengenlehre, BI 1994

B. Weiterführende Literatur

Jech, T,J.: Lectures in Set Theory, Springer LNM 217 1971

Jech, T.J.: Set Theory, Academic Press New York 1978, Springer 1997

Lévy, A.: Basic Set Theory, Springer 1979

Mendelson, E.: Introduction to Mathematical Logic, van Nostrand 1964

Rubin, J.E. Set Theory for the Mathematician, Holden-Day 1967

Shoenfield, J.R.: Mathematical Logic, Addison-Wesley 1967

Takeuti, G.-Zaring, W.M.: Introduction to Axiomatic Set Theory,

Axiomatic Set Theory, Springer 1971/73

C. Monographien mit besonderen Schwerpunkten

Drake, F.R.: Set Theory. An Introduction to large Cardinals, NHPC Amsterdam 1974

Kanamori, A.: The Higher Infinite, Springer 1997

Kunen, K.: Set Theory. An Introduction to Independence Proofs, NHPC Amsterdam 1983

Kuratowski-Mostowski: Set Theory, NHPC Amsterdam/PWN 1968

D. Alternative Axiomensysteme der Mengenlehre

Aczel, P.: Lectures on Nonwellfounded sets, CSLI Lecture Notes No 9 1987

Bernays, P.: Axiomatic Set Theory, NHPC Amsterdam 1958

Chuaqui, R.: Axiomatic Set Theory, Impredicative Theory of Classes, NHPC Amsterdam 81

Forster, T.E.: Set Theory with a Universal Set, Oxford Univ.Press 1992

Potter, M.D.: Sets. An Introduction, Clarendon Press - Qxford Univ. Press 1990

(deutsche Übersetzung: Mengentheorie, Spektrum-Verlag 1994)

Quine, W.V.O.: Set Theory and its Logic, Harward 1963 (deutsche Übers. bei vieweg 1973)

Rubin, J.E.: Set Theory for the Mathematician, Holden-Day 1967

Schmidt, J.: Mengenlehre I, BI Mannheim1966

Vopenka, P. - Hajek, P.: The Theory of Semisets, NHPC Amsterdam 1972

1

E. Von historischem und allgemeinem Interesse

Bolzano, B.: Paradoxien des Unendlichen, Leipzig 1851 (Neudruck bei F. Meiner 1955)

Cantor, G.: Gesammelte Abhandlungen, Hildesheim 1962

Dauben, J.W.: Georg Cantor. His mathematics and Philosophy of the Infinite, Princeton

paperbacks, Univ. Press, Princeton, NJ.

Felgner, U. (Herausgeber): Mengenlehre, Darmstadt 1979

Fraenkel, A.: Einleitung in die Mengenlehre, Springer-Verlag 1919

Fraenkel, A.: Abstract Set Theory, NHPC Amsterdam 1953

Fraenkel, A.-Bar Hillel, Y. -Lévy, A.: Foundations of Set Theory, NHPC Amsterdam 1973

Gödel, K.: Collected Works I,II, (ed. Feferman) Oxford 1986/87

Hallett, M.: Cantorian set theory and limitation of size, Oxford Univ. Press 1984

Hausdorff, F.: Grundzüge der Mengenlehre, Berlin 1914 (Chelsea, New York 1965)

Hausdorff, F.: Set Theory, Chelsea, New York 1962 (Übersetzung der Ausgabe von 1937)

Lavine, S.: Understanding the infinite, Harvard Univ. Press 1994

Meschkowski, H.: Probleme des Unendlichen. Werk und Leben Georg Cantors, Vieweg 1967

Meschkowski, H.: Hundert Jahre Mengenlehre, dtv Wiss. Reihe Bd. 4142 1973

Moore, G.H.: Zermelo´s Axiom of Choice, Springer 1982

Purkert, W.-Ilgauds, H.J.: Georg Cantor 1845-1918, Birkhäuser 1987

Spalt, D. (Herausgeber): Rechnen mit dem Unendlichen, Birkhäuser 1990

F. Sonstige

Devlin, K.: The Joy of Sets, Springer 1993 (2. Auflage)

Henle, J.M.: On Outline of Set Theory, Springer 1986

Jech, T.J.: The Axiom of Choice, Springer 1997

Klaua, D.: Mengenlehre, de Gruyter Berlin 1979

Krivine, J.L.: Théorie axiomatique des ensembles, Paris 1966

Rubin, H. - Rubin, J.E.: Equivalents of the Axiom of Choice, NHPC Amsterdam 1963

(Band II: 1985)

Shoenfield, J.R.: Mathematical Logic, Addison Wesley 1967

Zeitschriften über Mathematische Logik:

Annals of Pure and Applied Logic

Archive of Mathematical Logic

Fundamenta Mathematicae (FM)

Journal of Symbolic Logic (JSL)

Mathematical Logic Quarterly (früher: Zeitschrift f. math. Logik und Grundl. der Math.)

Notre Dame Journal of Formal Logic (NDJFL)

2

Übersicht über die ZERMELO-FRAENKELsche Mengenlehre (ZF)

Sprache von ZF:

a, b, c, . . . x, y, z , . . . Variable für Mengen

¬ (nicht), ∨ (oder), ∧ (und), → (wenn ... dann), ↔ (genau dann ... wenn),

∀ (für alle), ∃ (es gibt) logische Symbole

a = b (Gleichheit), a ∈ b (Elementbeziehung) Grundprädikate

Axiome von ZF:

Extensionalitätsaxiom: (Ext) ∀x (x ∈ a ↔ x ∈ b ) → a = b

Nullmengenaxiom : (Null) ∃y ∀x ( x ∉ y )

Paarmengenaxiom: (Paar) ∃y ∀x ( x ∈ y ↔ x = a ∨ x = b )

Summenaxiom: (Sum) ∃y ∀z (z ∈ y ↔ ∃x ∈ a z ∈ x )

Potenzmengenaxiom: (Po t ) ∃y ∀z (z ∈ y ↔ z ⊆ a )

Ersetzungsschema : (ErsS) ∀x∀y∀z (ϕ(x,y) ∧ ϕ(x,z) → y = z ) → → ∃u∀y (y ∈ u ↔ ∃x ∈ a ϕ(x,y))

Unendlichkeitsaxiom: ( U n ) ∃x ( Ø ∈ x ∧ ∀y(y ∈ x → y+1 ∈ x)

Fundierungsaxiom: (Fund) a ≠ Ø → ∃x ∈ a x ∩ a = Ø

Unter Benutzung von Klassentermen (Ausdrücken der Form {x|ϕ (x)}, bezeichnet mit

Großbuchstaben A, B, . . .) und der Definition

Mg(A): ↔ ∃x ( x = A ) A ist Menge

lassen sich die obigen Axiome auch wie folgt ausdrücken (mit den üblichen Definitionen):

Extensionalitätsaxiom : ( E x t ) ∀x (x ∈ a ↔ x ∈ b ) → a = b

Nullmengenaxiom : (Null) Mg(Ø)

Paarmengenaxiom: (Paar) Mg({a,b}

Summenaxiom: (Sum) Mg( ∪ a)

Potenzmengenaxiom: (Po t ) Mg(P(a) )

Ersetzungsschema : (ErsS) Fkt(F) → Mg(F[a])

Unendlichkeitsaxiom: (Un) Mg(N )

Fundierungsaxiom: (Fund) a ≠ Ø → ∃x ∈ a x ∩ a = Ø

Fügt man noch das

Auswahlaxiom: (AC) ∀x∈a x≠Ø → ∃f (Fkt(f) ∧ ∀x∈a f(x)∈x )

hinzu, so erhält man die Theorie ZFC.

3

§1 Mengen und Klassen

Teil A Die ZERMELO-FRAENKELsche Mengenlehre (ZF)

Kap. I : Die Axiome von ZF (ohne Unendlichkeitsaxiom)

§1 RUSSELsche Antinomie, Mengen und Klassen

1.1 Die Antinomien: In seinem Hauptwerk

Cantor, G.: Beiträge zu Begründung der transfiniten Mengenlehre, Math.Ann. 46 (1895),

481-512, 49 (1897), 207-246 (s. Ges. Abh. S.282)

gab CANTOR seine berühmte Definition einer Menge:

Unter einer "Menge" verstehen wir jede Zusammenfassung M von bestimmten

wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens (welche die

"Elemente" von M genannt werden) zu einem Ganzen.

Man kann diese "Definition" in folgendem Sinne zu präzisieren versuchen:

Zu jeder Eigenschaft E(x) existiert die Menge M aller Objekte x mit der

Eigenschaft E(x): M = {x: E(x) }.

ZERMELOs Erklärung des Begriffes Eigenschaft als definite Eigenschaft wurde von FRAENKEL

und SKOLEM dahingehend präzisiert, daß Eigenschaften als Ausdrücke einer bestimmten

formalen Sprache festzulegen sind. Diese Sprache, LZF, besitzt folgende Symbole:

• logische Zeichen: ¬ (nicht), ∨ (oder), ∧ (und), → (wenn ... dann), ↔ (genau dann ... wenn), ∀ (für alle), ∃ (es gibt)

• Variable: a, b, c, . . . x, y, z, . . . (für Mengen)

• Prädikate: = (Gleichheit), ∈ (Element-Beziehung)

• Hilfssymbole: (, )

Aus diesen Symbolen werden wie üblich (s. §2) Formeln aufgebaut und mit kleinen

griechischen Buchstaben: ϕ, ψ, . . . bezeichnet. Die CANTORsche Definition kann nun als

Forderung präzisiert werden:

1.2 Komprehensionsaxiom: ∃y ∀x ( x ∈ y ↔ ϕ(x) )

wobei ϕ(x) eine beliebige Formel ist, in welcher y nicht vorkommt.

Dieses Axiom (eigentlich ein Axiomenschema, da es aus unendlich vielen Axiomen besteht) ist

nun aber widerspruchsvoll:

4

§1 Mengen und Klassen

1.3 RUSSELLsche Antinomie (1903):

Wählt man für ϕ(x) die Formel x ∉ x, so liefert das Komprehensionsaxiom die Existenz einer

Menge r mit∀x ( x ∈ r ↔ r ∉ r ) , insbesondere gilt für x = r:

r ∈ r ↔ r ∉ r , Widerspruch!

Ähnliche Widersprüche erhält man, wenn man für ϕ(x) die Formel

"x = x" (Antinomie der "Menge aller Mengen" von CANTOR)

"x ist Kardinalzahl" (Antinomie von CANTOR (um 1899, publiziert erst 1932))

"x ist Ordinalzahl" (Antinomie von CANTOR (1895) und BURALI-FORTI (1897))

wählt, wobei man noch einige Schritte in der Anwendung der Theorie durchführen muß, um

zum Widerspruch zu gelangen, während die Antinomie von RUSSELL (die um die gleiche Zeit

auch bereits ZERMELO bekannt war) sehr elementar - und daher besonders beeindruckend -

ist.

1.4 Auswege

a) RUSSELLsche Typentheorie: Das Komprehensionsaxiom wird eingeschränkt. Zur Vermeidung

eines circulus vitiosus darf bei der Definition der Menge y durch die Eigenschaft ϕ(x) nicht auf

einen Bereich Bezug genommen werden, dem dieses y selbst angehört. Man nimmt eine

Stufeneinteilung vor: x0, x1, . . und vereinbart, daß xn ∈ xm nur erlaubt ist, wenn m = n+1.

Das Komprehensionsaxiom hat dann die Form

∃yn+1 ∀xn ( xn ∈ yn+1 ↔ ϕ(xn) ).

Da die Bildung von rn ∉ rn nicht mehr erlaubt ist, ist die RUSSELLsche Antinomie nicht mehr

formulierbar. Dieses prädikative Komprehensionsaxiom schränkt die Mengenbildung jedoch

stark ein; die Idee eines stufenweisen Aufbaus der Mengenlehre werden wir jedoch auch in der

ZF-Mengenlehre wieder finden (von NEUMANNsche Hierarchie). Vgl. hierzu auch das System

NF von QUINE (s. QUINE 1963/73, FORSTER 1992) sowie von SCOTT (s. POTTER).

b) ZERMELOsches Aussonderungsaxiom: Das Komprehensionsaxiom wird eingeschränkt auf die

Bildung von Teilmengen einer bereits gegebenen Menge a:

Aussonderungsaxiom : (AusS) ∃y ∀x ( x ∈ y ↔ x ∈ a ∧ ϕ(x, . . .) )

Um dieses Axiom anwenden zu können, müssen wir die Menge a , aus welcher mittels der

Eigenschaft ϕ eine Teilmenge ausgesondert wird, bereits haben - weitere Axiome sind

erforderlich! Versucht man erneut, die RUSSELLsche Antinomie abzuleiten, so erhält man die

Existenz einer Menge r mit

5

§1 Mengen und Klassen

r ∈ r ↔ r ∈ a ∧ r ∉ r, also

• es gibt keine "Menge aller Mengen" (für a eingesetzt, erhielte man den RUSSELLschen

Widerspruch),

• es gibt eine "leere" Menge (setze für ϕ(x) ein: x ≠ x und für a irgendeine Menge).

c) Unterscheidung zwischen Mengen und Klassen (von NEUMANN, GÖDEL, BERNAYS): Man

läßt eine (mehr oder weniger beschränkte) Komprehension von Mengen zu, das Ergebnis ist

dann aber nicht notwendig wieder eine Menge, sondern zunächst eine Klasse {x|ϕ(x)}. So kann

man für die Formeln von 1.3 bilden:

die RUSSELLsche Klasse R = {x| x ∉ x },

die Klasse aller Mengen V = {x| x = x },

die Klasse aller Ordinalzahlen On = {x| x ist Ordinalzahl},

die Klasse aller Kardinalzahlen, u.s.w.

Das Auftreten von Antinomien wird nun dadurch vermieden, daß diese Klassen keine Mengen

sind - die Frage, ob etwa R ∈ R oder R ∉ R , wird gar nicht erst zugelassen, bzw. erst unter

der Annahme sinnvoll, daß

(+) die Klasse R eine Menge r

ist. Die RUSSELLsche Klasse führt jetzt nur zum Widerspruch mit der Annahme (+), mithin

ergibt sich als Ergebnis, daß R keine Menge ist! Ebenso lassen die anderen Antinomien in der

jetzigen Formulierung die Folgerung zu, daß bestimmte Klassen keine Mengen sind.

Andererseits gibt es andere "harmlose" Klassen, von denen man problemlos annehmen kann,

daß sie Mengen sind, z.B.

{x| x ≠ x } (leere Klasse)

{x| x = a } (Einermenge {a}),

{x| x ∈ a } (die Menge a als Klasse aller Elemente von a), u.s.w.

Die verschiedenen Axiomensysteme der Mengenlehre unterscheiden sich weniger in dem jeweils

zugelassenen Bereich von Mengen als in dem Status, den sie den Klassen einräumen:

• ohne Klassen:

das Axiomensystem ZF von ZERMELO-FRAENKEL in der (engeren) ZF-Sprache

• mit eliminierbaren Klassen ("virtuelle Klassen" (QUINE)):

das Axiomensystem ZF von ZERMELO-FRAENKEL in der erweiterten ZF-Sprache

(welches wir hier zugrunde legen werden)

• mit freien Klassenvariablen:

das Axiomensystem von BERNAYS 1958

• mit freien und gebundenen Klassenvariablen, aber nur prädikativen Klassen:

das Axiomensystem NBG (von NEUMANN-GÖDEL-BERNAYS), hier hat das

Komprehensionsaxiom die Form

∃Y ∀x ( x ∈ Y ↔ ϕ(x, . . ,A, . . ) )

wobei jetzt A, B, . . , X,Y, . . Klassen bezeichnen (x,y, . . weiterhin Mengen) und ϕ(x, . .) eine

Eigenschaft von Mengen ist (möglicherweise mit Klassen als Parametern - prädikative Form).

6

§1 Mengen und Klassen

• Klassen, ernst genommen (imprädikativ):

das Axiomensystem QM von QUINE-MORSE mit dem Komprehensionsaxiom wie oben, aber

jetzt werden auch Formeln zugelassen, die Quantifikationen über Klassen enthalten; in diesem

System lassen sich mehr Aussagen über Mengen beweisen als in NBG! (CHUAQUI 1981, RUBIN

1967, SCHMIDT 1966)

• neben Klassen und Mengen auch noch Halbmengen:

die alternative Mengenlehre von VOPENKA (VOPENKA-HAJEK 1972).

Neben der Entscheidung, welchen existentiellen Wert man den Klassen einräumen soll, bleibt

als Hauptproblem die Frage: welche Mengen existieren - bzw.: welche Eigenschaften definieren

Mengen - oder (wenn wir ein allgemeines Komprehensionsprinzip für Klassen zugrunde

legen): welche Klassen führen zu Mengen?

Im folgenden werden wir der Entwicklung der Mengenlehre nach ZERMELO folgen, aber dabei -

wie jetzt allgemein üblich und zweckmäßig - die Vorteile einer erweiterten Sprache nutzen, in

welcher auch über (spezielle) Klassen gesprochen werden kann. Grundlegend werden dabei

folgende Vorstellungen sein:

• Es gibt Mengen und Klassen ; ihre Gleichheit wird durch das Extensionali tätsprinzip

bestimmt: Mengen bzw. Klassen sind identisch, wenn sie vom selben Umfang sind, d.h. dieselben

Elemente enthalten.

• Elemente von Klassen und Mengen sind wieder Mengen; echte Klassen ("Unmengen" wie die

RUSSELLsche Klasse) sind dagegen niemals Elemente - weder von Mengen noch von anderen

Klassen.

• Komprehensionsprinzip: Jeder Eigenschaft E(x) von Mengen x entspricht die

Klasse {x| E(x)} aller Mengen x mit der Eigenschaft E(x),

• insbesondere ist jede Menge a eine Klasse (nämlich: a = {x| x∈a } ),

• umgekehrt ist aber nicht jede Klasse eine Menge, sondern nur diejenigen Klassen, die nicht

"zu groß" sind, sind Mengen ("limitation of size").

Klassen sind somit nach dem Komprehensionsprinzip (nahezu) unbeschränkt bildbar,

Mengen existieren (als spezielle Klassen) nur nach Maßgabe einzelner Axiome.

(Und als unerfüllbare Hoffnung bleibt: Widersprüche werden vermieden!)

Literatur:

Cantor, G.: Beiträge zu Begründung der transfiniten Mengenlehre, Math.Ann. 46 (1895),

481-512, 49 (1897), 207-246

Fraenkel, A.- Bar Hillel, Y. - Lévy, A.: Foundations of Set Theory, NHPC Amsterdam 1973,

Chapter I (zum Antinomienproblem)

Fraenkel, A.A.: Zu den Grundlagen der Cantor-Zermeloschen Mengenlehre, Math Ann 86

(1922), 230-237 (in: Felgner 1979)

Skolem, T.: Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre, Kongress

Helsingfors 1922, s. Selected Works in Logic oder Felgner 1979.

7

§2 Extensionalität und Aussonderung

§2 Extensionalität und Aussonderung

2.1 Sprachliche Festlegungen: Wir benutzen

• a, b, c, . . . . , x, y, z, . . . (als Variable) für Mengen,

• a = b, a ∈ b (als Grundprädikate) für die Gleichheit und die Elementbeziehung

• ¬ , ∨ , ∧ , → , ↔ , ∀ , ∃ , als logische Symbole (wie oben unter 1.1)

• ( , ), { , } Klammern als Hilfssymbole bzw. für Klassenterme

Aus diesen Symbolen bilden wir die Formeln der ZF-Sprache (im engeren bzw. erweiterten

Sinne):

2.2 Definition

Formeln sind Zeichenreihen, die nach folgenden (rekursiven) Gesetzen gebildet werden:

(F1) Sind a, b Mengenvariable, so sind

a = b und a ∈ b Formeln (Grundformeln, atomare Formeln).

(F2) Sind ϕ und ψ Formeln, so auch (¬ ϕ), (ϕ ∨ ψ), (ϕ ∧ ψ), (ϕ → ψ) und (ϕ ↔ ψ) .(F3) Ist ϕ(a) eine Formel, in welcher die Variable x nicht vorkommt, so sind auch

∀x ϕ(x) und ∃x ϕ(x) Formeln.

(F4) Ist ϕ(a) eine Formel, in welcher die Variable x nicht vorkommt, so ist auch

a ∈ {x| ϕ(x) } eine Formel.

(F5) Das sind alle Formeln.

Von Formeln der ZF-Sprache im engeren Sinne sprechen wir, wenn bei der Bildung dieser

Formeln die Bedingung (F4) nicht benutzt wurde, ansonsten von Formeln der erweiterten ZF-

Sprache (siehe aber auch unter 2.5).

2.3 Bemerkungen und Ergänzungen

a) Klammern werden weggelassen, wenn dadurch die eindeutige Lesbarkeit nicht verloren geht.

b) Wir benutzen beschränkte Quantoren ∀x ∈ a, ∃x ∈ a als Akürzungen:

∀x ∈ a ϕ steht für ∀x(x ∈ a → ϕ ) , ∃x ∈ a ϕ steht für ∃x(x ∈ a ∧ ϕ )

Für viele Untersuchungen spielen Fragen der Komplexität von Eigenschaften eine wichtige

Rolle; dabei gelten beschränkte Quantoren als "einfacher" als unbeschränkte Quantoren. Wir

werden daher im folgenden - soweit möglich - beschränkte Quantoren verwenden.

2.4 Unser erstes Axiom (für die erweiterte ZF-Sprache) ist das folgende

CHURCHsche Schema (CS): a ∈ {x | ϕ(x, . . . ) } ↔ ϕ(a, . . . ).

Es erlaubt, Klassenterme, d.h. Ausdrücke der Form {x | ϕ(x, . . . ) }, wieder zu eliminieren,

und damit gilt:

8

§2 Extensionalität und Aussonderung

2.5 Metatheorem (Elimination von Klassentermen)

Zu jeder Formel ϕ der erweiterten Sprache existiert eine Formel ψ der engeren Sprache

(mit denselben freien Variablen), so daß unter Benutzung von (CS) gilt: ϕ ↔ ψ .(Beweis bei A. LEVY: Basic Set Theory, Appendix X. Beachte, daß der Beweis konstruktiv ist.)

Die erweiterte ZF-Sprache ist somit eigentlich nicht ausdrucksstärker, aber gelegentlich doch

bequemer zu benutzen, vor allem weil man für jede Eigenschaft ϕ die Klasse {x | ϕ(x, . . ) }

bilden kann, während man zur Bildung einer entsprechenden Menge erst nachprüfen muß, ob

die Axiome dies zulassen. Schließlich noch ein weiterer Schritt: Um nicht immer über die

Klassenterme {x | ϕ(x, . . ) } durch Angabe von Formeln sprechen zu müssen, werden wir

Variable A, B, . . . für Klassenterme benutzen! Eine Aussage der Form

(für alle B :) es gibt ein A mit . . . . A . . . . B . . . .

wird somit als Versprechen zu lesen sein, für jeden Klassenterm B einen Klassenterm A

konkret (d.h. durch eine Formel) anzugeben, der die gewünschte Eigenschaft besitzt;

ebenso wird eine universelle Aussage der Form

für alle A: . . . . A . . . .

bedeuten, daß sie für alle (konkret definierbaren) Klassenterme A gilt.

Beachte, daß Aussagen der Form ∃A .... bzw. ∀A .... formal nicht zulässig sind! Äußerlich

treten also die Variablen A, B,... wie freie Klassenvariable im System von BERNAYS 1958 auf,

tatsächlich sind es aber nur (Meta-)Variable für Klassenterme. Wie in 2.3 b) werden wir

auch abgekürzt ∀x∈A ϕ für ∀x(x∈A → ϕ) und ∃x∈A ϕ für ∃x(x ∈ A ∧ ϕ) schreiben,

aber diese Quantoren i.a. nicht als beschränkte Quantoren ansehen (warum nicht?).

2.6 Extensionalitätsprinzip

a) Für Mengen fordern wir, daß Mengen mit denselben Elementen (umfangsgleiche Mengen)

gleich sind:

Extensionalitätsaxiom : (Ext) ∀x (x ∈ a ↔ x ∈ b ) → a = b .

Aus logischen Axiomen über die Gleichheit folgt die Umkehrung, es gilt dann also:∀x (x ∈ a ↔ x ∈ b ) ↔ a = b (extensional)

Somit könnte man im Prinzip auf die Gleichheit als logisches Grundsymbol verzichten und sie

mittels der Elementbeziehung definieren. - Denkbar wäre auch eine Definition durch∀x (a ∈ x ↔ b ∈ x ) ↔ a = b (intensional, LEIBNIZ-Gleichheit),

diese Äquivalenz wird später einfach beweisbar sein (mit Existenz der Einer-Menge).

Aus dem Extensionalitätsaxiom folgt, daß es höchstens eine Menge gibt, die keine Elemente

enthält (die leere Menge), es gibt also keine Urelemente (für eine alternative Mengenlehre ,

die Urelemente zulassen soll, muß man also das Extensionalitätsaxiom abändern).

9

§2 Extensionalität und Aussonderung

b) Für Klassen bzw. Klassen und Mengen untereinander definieren wir die Gleichheit als

Umfangsgleichheit:

A = B : ↔ ∀x (x ∈ A ↔ x ∈ B ) ,

A = b : ↔ ∀x (x ∈ A ↔ x ∈ b ) ,

a = B : ↔ ∀x (x ∈ a ↔ x ∈ B ) , also a = B ↔ B = a ,

und in ähnlicher (und natürlicher) Weise definieren wir:

A ∈ B : ↔ ∃y ( y = A ∧ y ∈ B ) ,

A ∈ b : ↔ ∃y ( y = A ∧ y ∈ b ) ,

und somit sind die Grundprädikate = und ∈ für sowohl Mengen wie auch Klassen definiert.

Mg(A): ↔ ∃x ( x = A ) "A ist eine Menge", somit gilt

Mg(A) ↔ A ∈ V , wobei

V : = {x| x = x } (Klasse aller Mengen, Allklasse, Universum).

Klassen, die keine Mengen sind, nennt man auch echte Klassen.

Aus diesen Definitionen erhalten wir:

2.7 Lemma

( i ) Jede Menge ist eine Klasse: a = {x| x ∈ a } ,

( i i ) Gilt eine Eigenschaft für alle Klassen, so auch für alle Mengen:

Falls ϕ(A,B, . . . ), so auch ϕ(a,b, . . . ).

2.8 Das Aussonderungsschema ist die folgende Menge von Axiomen:

(AusS) ∃y ∀x ( x ∈ y ↔ x ∈ a ∧ ϕ(x, . . . ) ).

Unter Benutzung von Klassenvariablen und einfachen Definitionen (s.§3) erhalten wir:

2.9 Satz

Das Aussonderungsaxiom ist äquvalent zu den folgenden Aussagen:

( i ) ∃y ∀x ( x ∈ y ↔ x ∈ a ∧ x ∈ A)

( i i ) ∃y ( y = a ∩ A )

( i i i ) a ∩ A ∈ V bzw. Mg(a ∩ A)

( i v ) A ⊆ a → Mg(A) (Abschätzungssatz).

2.10 Korollar

Aus dem Aussonderungsaxiom folgt:

( i ) a ∩ b, a − b und Ø = {x| x≠x } (leere Klasse) sind Mengen,

( i i ) V = {x| x = x } (Allklasse, Universum) ist keine Menge, also eine echte Klasse.

10

§3 BOOLEsche Klassenalgebra

§3 BOOLEsche Klassenalgebra

In diesem Paragraphen werden wir die BOOLEschen Operationen auf den Klassen (die in engem

Zusammenhang mit der Aussagenlogik stehen) untersuchen; spezifische mengentheoretische

Axiome werden dazu nicht benötigt (abgesehen vom gelegentlichen Gebrauch des

Extensionalitätsaxioms).

3.1 Definition

Ø := {x| x≠x } leere Klasse: ∀x (x ∉ Ø)

V := {x| x=x } Universum: ∀x (x ∈ V)

A ⊆ B : ↔ ∀x( x ∈ A → x ∈ B) Inklusion, insbesondere

a ⊆ b : ↔ ∀x ∈ a ( x ∈ b ) (beschränkte Quantoren!)

A ⊂ B : ↔ A ⊆ B ∧ A ≠ B echte Inklusion

3.2 Lemma

Die Inklusion ⊆ ist eine teilweise (partielle) Ordnung mit Ø als kleinstem, V als größtem

Element:

(i) A ⊆ A ( re f l ex i v )

A ⊆ B ∧ B ⊆ C → A ⊆ C ( t rans i t i v ) ,

A ⊆ B ∧ B ⊆ A → A = B (antisymmetrisch)

( i i ) Ø ⊆ A ⊆ V .

Ferner gilt: A ⊂ B ↔ A ⊆ B ∧ ¬ B ⊆ A ↔ A ⊆ B ∧ ∃x (x ∈ B ∧ x ∉ A).

Dabei gilt die Antisymmetrie von ⊆ im Falle von Mengen gerade aufgrund des

Extensionalitätsaxioms, das sich mit beschränkten Quantoren schreiben läßt als∀x ∈ a ( x ∈ b ) ∧ ∀x ∈ b ( x ∈ a ) → a = b,

während diese Eigenschaft für Klassen aufgrund der Definition von A = B gilt.

3.3 Definition (BOOLEsche Operationen)

A ∩ B : = {x| x ∈ A ∧ x ∈ B} Durchschnitt

A ∪ B : = {x| x ∈ A ∨ x ∈ B} Vereinigung

A − B : = {x| x ∈ A ∧ x ∉ B} (relatives) Komplement

− B : = {x| x ∉ B} Komplement

3.4 Satz

Es gelten die Gesetze einer BOOLEschen Algebra:

( 1 ) A ∩ B = B ∩ A Kommutativgesetze

A ∪ B = B ∪ A

( 2 ) A ∩ (B ∩ C) = (A ∩ B) ∩ C Assoziativgesetze

A ∪ (B ∪ C) = (A ∪ B) ∪ C( 3 ) A ∩ A = A , A ∪ A = A Idempotenzgesetze

11

§3 BOOLEsche Klassenalgebra

( 4 ) A ∩ (B ∪ C) = (A ∩ B) ∪ ( A ∩ C) Distributivgesetze

A ∪ (B ∩ C) = (A ∪ B) ∩ ( A ∪ C)

( 5 ) A ∩ Ø = Ø , A ∪ V = V Größtes und kleinstes Element

A ∪ Ø = A , A ∩ V = A bzw. neutrale Elemente

( 6 ) A ∪ − A = V , A ∩ − A = Ø Komplementgesetze

− − A = A

− Ø = V, −V = Ø

( 7 ) − (A ∩ B) = − A ∪ − B de MORGANsche Gesetze

− (A ∪ B) = − A ∩ − B

( 8 ) A ⊆ B ↔ A ∪ B = B ↔ A ∩ B = A Umformungen ↔ A ∩ − B = Ø ↔ − B ⊆ −A

( 9 ) A ⊆ A ∪ B , B ⊆ A ∪ B Supremum

A ⊆ C ∧ B ⊆ C → A ∪ B ⊆ C A ∩ B ⊆ A , A ∩ B ⊆ B Infimum

C ⊆ A ∧ C ⊆ B → C ⊆ A ∩ B

( 1 0 ) A ⊆ B → A ∪ C ⊆ B ∪ C ∧ A ∩ C ⊆ B ∩ C Monotonie

Die Beweise dieser (oder ähnlicher) Aussagen sind elementar, wenn auch gelegentlich

langwierig (insbesondere im Falle mehrerer Variabler). Prinzipiell kann man nach folgenden

Methoden vorgehen:

1. Rückführung mittels der Def. 3.3 auf entsprechende aussagenlogische Aussagen, die man dann

inhaltlich (d.h. gemäß der Bedeutung der aussagenlogischen Operationen) oder etwa mit Hilfe

der Wahrheitstafeln behandelt,

2. (Algebraisch-axiomatisch) Versuche, die zu beweisende Aussage aus den Axiomen der

BOOLEschen Algebra (dazu reichen die Aussagen (1) - (7)) abzuleiten,

3. (Geometrisch-anschaulich) VENNsche Diagramme

4. Kombinationen dieser Methoden, außerdem etwa Beweis von X = Y durch einzelnen Nachweis

von

a) X ⊆ Y und b) Y ⊆ X,

möglicherweise jeweils mit geeigneten Fallunterscheidungen.

Übung:

1) A ∪ B = (A ∩ B) ∪ ( A − B) ∪ (B − A).

2) A ∆ (B ∆ C) = (A ∆ B) ∆ C, wobei

A ∆ B : = (A ∪ B) − (A ∩ B) (symmetrische Differenz von A und B).

12

§4 Relationen und Funktionen

§4 Elementare Axiome (Paar, Summe); Relationen und Funktionen

Zur Darstellung der BOOLEschen Klassenalgebra haben wir noch keine mengentheoretischen

Axiome benötigt; zum Aufbau des Relationen- und Funktionenkalküls benutzen wir (geordnete)

Paare von Mengen, um mehrstellige Relationen auf einstellige, d.h. auf Klassen,

zurückzuführen - Funktionen werden dann als spezielle Relationen eingeführt.

4.1 Definition

{a,b} : = {x| x = a ∨ x = b} ungeordnetes Paar von a und b,

{a} := {x| x = a } = {a,a} Einerklasse von a

4.2 Paarmengenaxiom: (Paar) ∃y ∀x ( x ∈ y ↔ x = a ∨ x = b )

bzw. Mg({a,b}) .

Nach dem Paarmengenaxiom ist also insbesondere für jede Menge a die Einerklasse {a} von a

eine Menge, die Einermenge von a (unit set ). Somit kann man die folgenden Mengen bilden:

{a,b}, {a}, {a,{a,b}}, {{a,c},{e, {a,e}}}, {{a,{a,b}}, {{a,c}, {e, {a,e}}} }, u.s.w.

Setzen wir etwa das

4.3 Nullmengenaxiom : (Null) ∃y ∀x ( x ∉ y ),

bzw. Mg(Ø)

voraus (das offensichtlich aus dem Aussonderungsaxiom folgt, welches wir in diesem Para-

graphen aber nicht allgemein benötigen werden), so kann man etwa folgende Mengen bilden:

Ø , {Ø}, {Ø,{Ø}} , . . . , die später für die Zahlen O, 1, 2, . . stehen werden und untereinander

verschieden sind, denn es ist

Ø ∈ {Ø} , aber Ø ∉ Ø , somit Ø ≠ {Ø} , ebenso {Ø,{Ø}} ≠ Ø, {Ø} . Tatsächlich gibt es

aufgrund der bisherigen Axiome bereits unendlich viele Mengen, z.B.

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

aber die Existenz einer Menge mit mehr als zwei Elementen ist damit noch nicht nachweisbar!

4.4 Lemma

( i ) c ∈ {a,b} ↔ c = a ∨ c = b

( i i ) {a,b} = {b,a} (ungeordnet)

( i i i ) c ∈ {a} ↔ c = a

( i v ) {a} = {b} → a = b

( v ) {a,b} = {c} → a = b = c

( v i ) {a,b} = {a,c} → b = c

Beweis : (i) und (iii) ergeben sich direkt aus der jeweiligen Definition mittels (CS), (ii)

folgt aus (i) und der Kommutativität von "oder".

13

§4 Relationen und Funktionen

(iv): Aus a ∈ {a} = {b} folgt a ∈ {b}, nach (iii) also a = b.

(Somit gilt sogar: {a} ⊆ {b} → a = b.)

(v) beweist man ähnlich: Es sind a,b ∈ {a,b} = {c} , also wieder nach (iii): a = c und b = c.

(Auch hier könnte man die Vor. abschwächen zu {a,b} ⊆ {c}.)

(vi): Es ist zweckmäßig, die Fälle a = c (dann kann man (v) anwenden) und a ≠ c zu

unterscheiden: Es ist c ∈ {a,c} = {a,b} , also c = a oder c = b. Falls a ≠ c, muß also c = b gelten.

4.5 Bemerkung : Unter der Voraussetzung, daß zu jeder Menge a die Einermenge {a}

existiert, gilt also (indem man für x die Menge {a} setzt):

∀x (a ∈ x → b ∈ x ) → a = b , insbesondere also

∀x (a ∈ x ↔ b ∈ x ) ↔ a = b (intensionale Charakterisierung der Gleichheit).

4.6 Definition (WIENER 1914, KURATOWSKI 1921)

(a,b):= {{a}, {a,b}} (geordnetes Paar von a und b), häufig auch mit

<a,b> bezeichnet.

4.7 Satz

(a,b) = (c,d) → a = c ∧ b = d , insbesondere:

(a,b) = (b,a) ↔ a = b.

Beweis: Es sei (a,b) = (c,d), d.h. {{a},{a,b}} = {{c},{c,d}}. Wie vorher (4.4. (vi)) trifft man

am besten eine Fallunterscheidung:

1.Fall: c = d . Die Vor. lautet dann: {{a},{a,b}} = {{c},{c}} = {{c}}, also nach 4.4 (v):

{a} = {a,b} = {c}, also wiederum nach 4.4.(v): a = b = c.

2.Fall: c ≠ d . Wegen {a} ∈ {{a},{a,b}} = {{c},{c,d}} gilt: {a} ∈ {{c},{c,d}}, also nach 4.4 (i):

{a} = {c} oder {a} = {c,d} . Wegen c≠d kann (nach 4.4 (v)) letzteres nicht gelten, wir

erhalten also {a} = {c} und damit a = c.

Ähnlich gilt wegen {c,d} ∈ {{a},{a,b}} : {c,d} = {a} (nicht möglich wegen c≠d)

oder {c,d} = {a,b} = {c,b} (wegen a = c), dann aber nach 4.4 (vi): d = b.

Die (erste) Aussage von 4.7 charakterisiert das geordnete Paar; die genaue Definition kann man

jetzt (erst einmal) wieder vergessen. Hat man geordnete Paare zur Verfügung, so kann man

durch Iteration (geordnete) n-Tupel einführen:

4.8 Definition

(a1) = a1

(a1, . . . ,an) = (a1,(a2, . . . ,an)) für n>1.

4.9 Satz

(a1, . . . ,an) = (b1, . . . ,bn) → a1 = b1 ∧ . . . . ∧ an = bn .

(Der Beweis erfolgt durch metamathematische Induktion über n.)

14

§4 Relationen und Funktionen

4.10 Definitionen

(1) {x,y| ϕ (x,y) } : = {z| ∃x ∃y ( z = (x,y) ∧ ϕ(x,y)) } , oder manchmal auch geschrieben

{(x,y)| ϕ(x,y) } , bezeichnet die Klasse der Paare (x,y) mit ϕ(x,y).

Insbesondere erhalten wir aus (CS) die beiden folgenden Umformungsschemata:

c ∈ {x,y| ϕ (x,y) } ↔ ∃x ∃y ( c = (x,y) ∧ ϕ ( x , y ) ) ,

(a,b) ∈ {x,y| ϕ (x,y) } ↔ ϕ (a,b).

(2) A x B : = {x,y| x ∈ A ∧ y ∈ B} cartesisches Produkt von A mit B,

c ∈ A x B ↔ ∃x ∈ A ∃y ∈ B (c = (x,y)),

(a,b) ∈ A x B ↔ a ∈ A ∧ b ∈ B.

(3) Rel(R): ↔ R ⊆ V x V R ist eine (2-stellige) Relation

↔ ∀z∈R ∃x ∃y ( z = (x,y)),

a R b : ↔ (a,b) ∈ R.

Beispiele: I := {x,y| x = y} (Identität), E := {x,y| x ∈ y} (∈ -Relation).

Diese Begriffe kann man natürlich auch vom 2-stelligen auf den n-stelligen Fall übertragen:

{x1, . . , xn| ϕ(x1, . . . , xn)} := {z| ∃x1. . . ∃xn ( z = (x1, . . . , xn) ∧ ϕ (x1 , . . . , xn))},

oder auch mit {(x1, . . . , xn)| ϕ(x1, . . . , xn)} bezeichnet,

A1 x . . . . x An : = {x1, . . . , xn| x1∈ A1 ∧ . . . ∧ xn∈ An }, speziell

An : = A x . . . x A (n-mal) = {x1, . . . , xn| x1∈ A ∧ . . . ∧ xn∈ A },

Reln(R) : ↔ R ⊆ Vn,

insbesondere ist also A x B x C = A x (B x C) , aber i.a. ≠ (A x B) x C (obwohl auch diese

Definition möglich ist).

(4) D(R) := {x| ∃y xRy } Definitionsbereich (Vorbereich/domain) von R

(5) W(R) :={y| ∃x xRy } Wertebereich (Nachbereich/range) von R

(6) Feld(R):= D(R) ∪ W(R) Feld (field) von R

(7) R|A := {x,y| xRy ∧ x ,y ∈ A } Einschränkung von R auf A (als Feld)

(besonders für Relationen R)

(8) RÁA := {x,y| xRy ∧ x ∈ A } Einschränkung von R auf A (als Def.bereich)

(besonders für Funktionen R)

(9) R[A] := R" A: = {y| ∃x ∈ A xRy } Bild von A unter R

(10) Q ο R := {x,y| ∃z ( xQz ∧ zRy )} Verkettung von Q mit R

(11) QR := R ο Q = {x,y| ∃z ( xRz ∧ zQy )} Komposition von Q mit R

(12) R-1:= {y,x| xRy} Inverses zu R

4.11 Einfache Folgerungen aus den Definitionen:

15

§4 Relationen und Funktionen

( i ) Ø x A = A x Ø = Ø

( i i ) D(A x B) = A, W(A x B) = B, Feld(A x B) = A ∪ B , falls A, B ≠ Ø

( i i i ) Rel(R) ↔ R ⊆ D(R) x W(R)

( i v ) D(R-1) = W(R), W(R-1) = D(R)

( v ) R|A = R ∩ (A x A) , RÁA = R ∩ (A x V), R[A] = W(RÁA)

( v i ) R ο (S ο T) = (R ο S) οT , R (S T) = (R S) T

( v i i ) (A x B)-1 = B x A , (R ο S)-1 = S-1 ο R-1, (R S)-1 = S-1 R- 1

( v i i i ) RÁA , R|A, R ο S und R S sind stets Relationen

( i x ) D(RÁA) = D(R) ∩ A, D(R) = R-1[V] , W(R) = R[V]

4.12 Definition

Funktionen werden als Klassen von Paaren definiert, indem eine Funktion mit ihrem

Graphen identifiziert wird:

Fkt(F): ↔ Rel(F) ∧ ∀x,y,z [ (x,y) ∈ F ∧ (x,z) ∈ F → y = z ] F ist eine Funktion .

Ist F eine Funktion, a ∈ D(F), so gibt es also genau ein b ( ∈ W(F)) mit (a,b) ∈ F. Dieses b

bezeichnen wir wie üblich als den Funktionswert von F an der Stelle a:

F(a) = b : ↔ (a,b) ∈ F , falls Fkt(F) ∧ a ∈ D(F). Allgemeiner kann man auch setzen:

F(a) = dasjenige b mit (a,b) ∈ F , falls es genau ein solches b gibt,

Ø sonst.

Inj(F): ↔ Fkt(F) ∧ ∀x,y ∈ D(F) (F(x) = F(y) → x = y) F ist injektive Funktion

↔ Fkt(F) ∧ Fkt(F-1 )

F : A → B : ↔ Fkt(F) ∧ D(F) = A ∧ W(F) ⊆ B F ist Funktion von A nach B

F : A →> B : ↔ Fkt(F) ∧ D(F) = A ∧ W(F) = B F ist Funktion von A auf B

(F ist sur jekt iv)

F : A >→ B : ↔ Inj(F) ∧ D(F) = A ∧ W(F) ⊆ B F ist injektive Funktion von A nach B

F : A ↔ B : ↔ Inj(F) ∧ D(F) = A ∧ W(F) = B F ist Bijektion von A auf B

4.13 Definition

{F(x)| ϕ (x)} := {y| ∃ x (ϕ (x) ∧ y = F(x))}

(Diese Definition wird i.a. nur gebraucht, wenn F eine Funktion ist und ∀x(ϕ(x) → x∈D(F));

kann aber auch allgemein ohne Probleme verwendet werden, da im anderen Fall F(x) = Ø ist.)

Für eine Funktion F mit D(F) = A gilt somit:

F = {(x,F(x))| x ∈ A}

(den Klassenterm auf der rechten Seite bezeichnet man häufig auch als den Graphen von F),

und hierfür schreibt man auch (wenn W(F) ⊆ B ist):

F : A → B , x |→ F(x) für x ∈ A,

insbesondere wenn man die Funktion F dadurch bestimmt, daß man ihren Definitionsbereich

angibt und den jeweiligen Wert F(x) an der Stelle x im Definitionsbereich.

4.14 Einfache Folgerungen aus den Definitionen:

16

§4 Relationen und Funktionen

( i ) Fkt(F) → W(F) = {F(x)| x ∈ D(F)}, allgemeiner:

( i i ) Fkt(F) ∧ A ⊆ D(F) → F[A] = {F(x)| x ∈ A}

( i i i ) Fkt(F) ∧ a ∈ D(F) → F[{a}] = {F(a)}

4.15 Bemerkungι-Terme (Kennzeichnungsterme) bezeichnen eindeutig bestimmte Objekte:

(1) ∃ !x ϕ(x) ∧ ϕ(a) → a = ιx ϕ(x),

( 2 ) ¬ ∃!x ϕ(x) → ιx ϕ(x) = Ø (Konvention),

wobei ∃!x ϕ(x): ↔ ∃x ϕ(x) ∧ ∀ x,y (ϕ (x) ∧ ϕ(y) → x=y ) (es existiert genau ein x mit ϕ(x)).

In unserem Rahmen können wir diese Terme explizit einführen durch:

ιx ϕ (x): = {y| ∃ !x ϕ (x) ∧ ∃x (y ∈ x ∧ ϕ( x ) ) } .

4.16 Definition

∪ A : = ∪x∈A

x : = {z| ∃x ∈ A z ∈ x } Vereinigung (Summe)

∩ A : = ∩x∈A

x : = {z| ∀x ∈ A z ∈ x } Durchschnitt

4.17 Summenaxiom: (Sum) ∃y ∀z (z ∈ y ↔ ∃x ∈ a z ∈ x) (ZERMELO)

d.h. Mg(∪ a)

4.18 Lemma

( i ) ∪ {a} = a, ∪ {a,b} = a ∪ b ,

( i i ) ∩ {a} = a, ∩ {a,b} = a ∩ b ,

( i i i ) ∪ a ist das Supremum der Elemente von a (bzgl. ⊆ ):

∀x∈a x ⊆ ∪ a , ∀x∈a x ⊆ c → ∪ a ⊆ c ,

( i v ) ∩ a ist das Infimum der Elemente von a (bzgl. ⊆ ):

∀x∈a ∩ a ⊆ x , ∀x∈a c ⊆ x → c ⊆ ∩ a .

( v ) ∪ Ø = Ø, ∪ V = V ,

∩ Ø = V, ∩ V = Ø .

4.19 Bemerkungen

(1) Aus dem Summen- und Paarmengenaxiom folgt also nach 4.18 (i), daß für je zwei Mengen

a und b die Vereinigung a ∪ b wieder eine Menge ist, aber -a stets eine echte Klasse ist!

(2) Dagegen ist a ∩ b eine Menge nach dem Aussonderungsaxiom, allgemeiner gilt nach

(AusS):

A ≠ Ø → Mg( ∩ A),

17

§4 Relationen und Funktionen

die Umkehrung gilt aber auch wegen ∩ Ø = V , somit:

A ≠ Ø ↔ Mg( ∩ A).

18

§5 Ersetzungsaxiome

§ 5 Das Ersetzungsaxiom

Im Folgenden stehen im allgemeinen

F, G, H, . . . für Funktionen, R, S, T, . . . für Relationen (u.U. echte Klassen),

f, g, h, . . . für Funktionen, r, s, t, . . . für Relationen , die Mengen sind.

5.1 Definition

∪x∈A

F(x) := ∪ {F(x)| x ∈ A} = {z| ∃x ∈ A z ∈ F(x)} Vereinigung (Summe)

∩x∈A

F(x) := ∩ {F(x)| x ∈ A} = {z| ∀x ∈ A z ∈ F(x)} Durchschnitt

sind die Verallgemeinerungen der einfachen Summe bzw. des Durchschnitts (Def. 4.16).

5.2 BERNAYSsches Summenaxiom: (BSum) Mg(∪x∈a

F(x))

5.3 Ersetzungsaxiom (FRAENKEL): (Ers) Mg({F(x)|x ∈ a}),

bzw. Fkt(F) → Mg(F[a])

bzw. Fkt(F) ∧ Mg(D(F)) → Mg(W(F))

5.4 Bemerkungen

1) Das Ersetzungsaxiom besagt, daß das Bild einer Menge a unter einer Funktion F (welche

eine Klasse sein kann) wieder eine Menge ist, bzw. daß man wieder eine Menge erhält, wenn

man die Elemente x einer Menge a durch ihre Funktionswerte F(x) ersetzt.

2) Auf der Basis der bisherigen Axiome (Ext, Null, Paar) ist das

BERNAYSsche Summenaxiom äquivalent mit

(ZERMELOschen) Summenaxiom + (FRAENKELschen) Ersetzungsaxiom:

denn aus (BSum) folgt Sum, indem man für F die Identität (also F(x) = x ) setzt, und das (Ers)

wegen {F(x)| x ∈ a} = ∪ {{F(x)}| x ∈ a}; und umgekehrt gilt:

∪x∈a

F(x) = ∪ {F(x)| x ∈ a} = ∪ F[a] .

5.5 Satz

Fkt(F) ∧ D(F) ∈ V → W(F), F ∈ V,

d.h. ist der Definitionsbereich einer Funktion eine Menge, so ist nicht nur ihr Bild, sondern die

Funktion selber eine Menge.

Beweis: Zu gegebener Funktion F definiere eine Funktion G durch D(G) = D(F) und

G(x) = (x,F(x)) für x ∈ D(F).

Dann ist W(G) = {G(x)| x ∈ D(F)} ={(x,F(x))| x ∈ D(F)} = F, also auch F Menge nach dem

Ersetzungsaxiom (angewandt auf G).

5.6 Übungsaufgabe:

(i) Zeige, daß man auf die Voraussetzungen von 5.5. nicht verzichten kann!

(ii) Ist F : A →> B , so Mg(A) → Mg(B) ;

19

§5 Ersetzungsaxiome

(iii) Ist F : A >→ B , so Mg(B) → Mg(A) .

5.7 Satz Rel(r) → D(r), W(r) ∈ V .

Beweis: a) mit Hilfe des Ersetzungsaxioms: benutze die Projektionen

P1: r → > D(r) definiert durch P1((x,y)) = x und

P2: r → > W(r) definiert durch P2((x,y)) = y ,

b) mit Hilfe des Summen- und Aussonderungsaxioms: Zeige, daß

D(r), W(r) ⊆ ∪∪ r.

5.8 Lemma Mg({c} x b)

Beweis: {c} x b = {(c,y)| y ∈ b} = ∪y∈b

{(c,y)} , ist also Menge nach (BSum). Man kann aber

auch das Ersetzungsaxiom benutzen, indem man eine Funktion F: b →> {c} x b definiert.

5.9 Satz Mg(a x b)

Beweis: Definiere (mit Hilfe von 5.8) eine Funktion F: a → V durch F(x) = {x} x b . Es ist

dann

a x b = ∪x∈a

({x} x b) = ∪x∈a

F(x).

5.10 Satz Rel(R) → ( R ∈ V ↔ D(R), W(R) ∈ V ) ,

Rel(r) ↔ ∃x ∃y r ⊆ x x y .

Beweis: Es ist R ⊆ D(R) x W(R) .

5.11 Axiome und Axiomenschemata

Neben den Axiomen (Ext), (Null), (Paar), (Sum), in deren Formalisierung nur Mengen-

variable vorkommen, haben wir auch Axiome eingeführt, in denen Klassenvariable auftreten:

(Aus), (BSum), (Ers). Hierbei stehen - gemäß unserer Vereinbarung in §2 - die

Klassenvariable A, F, . . . eigentlich für beliebige Klassenterme der Form {x: ϕ(x)}, die sich

wiederum mit Hilfe des CHURCHschen Schemas eliminieren lassen - man erhält dann das

entsprechende Axiomenschema:

Aussonderungsaxiom (Aus): Mg(a ∩ A)

Aussonderungsschema (AusS): ∃y ∀x( x ∈ y ↔ x ∈ a ∧ ϕ( x ) )

Ersetzungsaxiom (Ers): Fkt(F) ∧ Mg(D(F)) → Mg(W(F))

Ersetzungsschema (ErsS): ∀x∀y∀z (ϕ(x,y) ∧ ϕ(x,z) → y = z ) →→ ∃u∀y (y ∈ u ↔ ∃x ∈ a ϕ(x,y)).

Dabei haben wir beim Übergang vom Ersetzungsaxiom zum entsprechenden Schema auch noch

20

§5 Ersetzungsaxiome

die Benutzung des geordneten Paares eliminiert.

Soweit man Klassenvariable nur als (Metavariable für) Klassenterme (also für definierbare

Klassen) auffaßt, stehen die obigen Axiome für die entsprechenden Schemata; sobald man aber

in einem anderen formalen Rahmen Klassenvariable als Variable für (nicht notwendig

definierbare) Klassen auffaßt, können die Bedeutungen auseinanderfallen.

5.12 Metatheorem

(i) Aus den Axiomen (Ext), (Null), (Paar), (Ers) folgt (Aus),

( i i ) Aus (ErsS) folgt (AusS).

Beweis von (i): zu zeigen ist: a ∩ A ∈ V.

1. Fall: a ∩ A = Ø : Dann gilt die Beh. wegen des Nullmengenaxioms.

2. Fall: a ∩ A ≠ Ø: Wähle ein b ∈ a ∩ A und definiere eine Funktion F: a →> a ∩ A durch

F(x) = x , falls x ∈ a ∩ A, F(x) = b sonst,

und wende das Ersetzungsaxiom an.

Beweis von (ii): Zu zeigen ist: ∃y ∀x( x ∈ y ↔ x ∈ a ∧ ϕ(x)). Definiere eine Formel

ψ (x,y): ↔ ( ϕ (x) ∧ x = y ).

Es gilt dann: ψ(x,y) ∧ ψ(x,z) → y = z , also ex. nach (ErsS) ein b mit

∀y (y ∈ b ↔ ∃x ∈ a ψ(x,y)),

∀y (y ∈ b ↔ ∃x ∈ a ( ϕ(x) ∧ x = y )),

∀y (y ∈ b ↔ y ∈ a ∧ ϕ (y) ) .

Zur Axiomatisierung haben wir somit folgende Möglichkeiten:

(a) (in der engeren ZF-Sprache ohne Klassenvariable):

(Ext), (Paar), (Sum), (ErsS) (sowie später: (Pot), (Un), (Fund)),

als Folgerungen: (Null), (AusS)

(b) (in der erweiterten ZF-Sprache mit Klassenvariablen und dem (CS)):

(Ext), (Null), (Paar), (Sum), (Ers) (sowie später: (Pot), (Un), (Fund)),

als Folgerung: (Aus),

(wobei (Sum) und (Ers) zum (BSum) zusammengefaßt werden können und auch hier es so

eingerichtet werden kann, daß das Nullmengenaxiom überflüssig wird).

5.13 Bemerkung: Es gibt eine natürliche Verallgemeinerung des de MORGANschen Gesetzes

((7) von 3.4 auf S.12), wobei nur die Formalisierung Schwierigkeiten bereitet, da das

Komplement einer Menge stets eine echte Klasse ist; denn offensichtlich gilt:

− ∪x∈A

F(x) = ∩x∈A

−F(x) .

Diese Schreibweise wird zulässig, wenn wir entweder relativieren (b − ... statt − ... ) oder für

eine Folge von Klassen Ai , die durch eine Klasse A definiert sind, so daß x∈Ai ↔ (x,i)∈A

21

§5 Ersetzungsaxiome

gilt, definieren: ∪i∈ I

Ai : = {x| ∃ i∈ I x∈Ai} = {x| ∃ i∈ I (x,i)∈A } .

22

§6 Potenz- und Produktmenge

§ 6 Potenz- und Produktmenge

6.1 Definition

P (A): = {x| x ⊆ A } Potenzklasse von A

bA := {f | f: b → A } Belegungsklasse von b nach A

6.2 Bemerkungen

( 1 ) Da Elemente von Klassen stets Mengen sind, ist P(A) nur als Klasse aller Teilmengen

von A definierbar, ebenso ist bA nur für Mengen b definierbar.

( 2 ) Es ist stets Ø , a ∈ P(a) , ferner Ø ∈ P(A).

( 3 ) a x b ⊆ P(P(a ∪ b)) (aufgrund der spezifischen Definition des geordneten Paares).

6 .3 Potenzmengenaxiom: (Pot) M g ( P (a ) )

Belegungsmengenaxiom: (B) Mg(ab)

6.4 Satz

( i ) Mg(a x b) folgt aus den Axiomen (AusS), (Paar), (Sum), (Pot).

(ii) Potenzmengenaxiom (Pot) und Belegungsmengenaxiom (B) sind äquivalent.

Beweis: (i) folgt aus obiger Bemerkung 6.2 (3). Zu (ii): Es ist

f ∈ ba → f ⊆ b x a → f ∈ P(b x a) , also ba ⊆ P(b x a) und somit (Pot) ⇒ (B).

Zum Beweis der Umkehrung definieren wir

O := Ø, 1 := {Ø}, 2 : = {0,1} = {Ø,{Ø}}.

Indem man jeder Menge x ⊆ a ihre charakteristische Funktion cx zuordnet, erhält man eine

Bijektion der Potenzklasse P(a) auf die Belegungsklasse a2:

h: P(a) ↔ a2

x |→ cx mit cx: a → 2, definiert durch cx(y) = 1 falls y ∈ x

0 falls y ∉ x.

Somit gilt auch (B) ⇒ (Pot) (unter Benutzung des Ersetzungsaxioms).

6.5 Definition

∏x∈a

F(x) := {f| Fkt(f) ∧ D(f) = a ∧ ∀x ∈ a f(x) ∈ F(x)} allgemeines Produkt

∏x∈a

x := ∏ a := {f| Fkt(f) ∧ D(f) = a ∧ ∀x ∈ a f(x) ∈ x} Produktmenge

Die Produktmenge ist offensichtlich ein Spezialfall des allgemeinen Produkts, ebenso das

endliche Produkt: Es gibt einfache Bijektionen

∏ {a} ↔ a , ∏ {a,b} ↔ a x b (für a ≠ b), und allgemeiner: ∏

x∈{a} F(x) ↔ F(a), ∏

x∈{a,b} F(x) ↔ F(a) x F(b) (für a ≠ b), usw.

23

§6 Potenz- und Produktmenge

6.6 Produktmengenaxiom : (P) Mg(∏ a)

Allgem. Produktmengenaxiom: (AP) Mg(∏x∈a

F(x))

Auf der Basis der bisherigen Axiome sind alle diese Axiome, (Pot), (B), (P) und (AP),

miteinander äquivalent:

6.7 Satz

∏x∈a

F(x) ⊆ P(a x ∪x∈a

F(x))

6.8 Satzab = ∏

x∈a F(x) , wobei F: a → {b} die konstante Funktion F(x) = b ist.

6.9 Satz

∏x∈a

F(x) = {W(g)| g ∈ ∏ B}, wobei

B: = {{x} x F(x)| x ∈ a} = W(G) mit G: a → V, G(x) = {x} x F(x) für x ∈ a.

Insbesondere ist B eine Menge nach dem Ersetzungsaxiom.

Somit gilt:

(Pot) ⇒ (AP) nach 6.7,

(AP) ⇒ (P) durch Spezialisierung,

(P) ⇒ (AP) nach 6.9,

(AP) ⇒ (B) nach 6.8, und (B) ⇒ (Pot) nach 6.4.

6.10 Bemerkung

In verschiedenen Gebieten der Mathematik wird häufig auch der Begriff der Fami l ie

verwendet: mengentheoretisch handelt es sich dabei auch um eine Funktion F: I → V , die man

mit (Ai |i ∈ I), oder < Ai >i ∈ I bezeichnet, wobei Ai = F(i). Falls I eine Menge und für jedes

i∈I auch Ai eine Menge ist, so schreibt man für das Produkt der Ai, i ∈ I, gelegentlich auch

∏i ∈ I

Ai = { (ai)i ∈ I | ∀ i ∈ I ai ∈ Ai}.

6.11 Obwohl wir es erst später benutzen werden, erwähnen wir hier bereits das

Fundierungsaxiom: (Fund) a ≠ Ø → ∃x ∈ a x ∩ a = Ø.

Indem man für a speziell {a} bzw. {a,b} einsetzt, erhält man als

Folgerungen aus (Fund):

(i) a ∉ a ( somit ist die RUSSELLsche Klasse gleich der Klasse aller Mengen)

( i i ) es gilt nicht: a ∈ b ∧ b ∈ a , ebenso gibt es keine Mengen a, b, c mit

a ∈ b ∧ b ∈ c ∧ c ∈ a , u.s.w.

24