================================================================================ UTF-8-file qedeq_set_theory_v1 Generated from http://www.qedeq.org/0_04_04/doc/math/qedeq_set_theory_v1.xml Generated at 2011-07-30 02:23:24.300 ================================================================================ If the characters of this document don't display correctly try opening this document within a webbrowser and if necessary change the encoding to Unicode (UTF-8) Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. Axiomatische Mengenlehre ════════════════════════ Michael Meyling Die Quelle für dieses Dokument ist hier zu finden: http://www.qedeq.org/0_04_04/doc/math/qedeq_set_theory_v1.xml Die vorliegende Publikation ist urheberrechtlich geschützt. Bei Fragen, Anregungen oder Bitte um Aufnahme in die Liste der abhängigen Module schicken Sie bitte eine EMail an die Adresse mime@qedeq.org Die Autoren dieses Dokuments sind: Michael Meyling ___________________________________________________ Vorwort ═══════ Mathematik ist eine Wissenschaft mit einer Struktur, die im Laufe der Zeit riesige Dimensionen erreicht hat. Diese unglaublich hohe Burg besitzt nur ein ganz schmales Fundament und ihre Festigkeit gründet sich auf einfachem prädikatenlogischen Mörtel. Im Prinzip kann der Aufbau von jeder Mathematikerin verstanden werden. Von dem neuesten Gipfel mathematischer Erkenntnis kann jeder Pfad logisch folgerichtig bis in die mengentheoretischen Wurzeln nachvollzogen werden. Bei diesem Unternehmen will dieses Dokument Hilfestellung geben. Ziel ist eine Präsentation der mengentheoretischen Wurzeln in verständlicher Weise. Bei aller Verständlichkeit soll es jedoch jederzeit möglich sein, tief in die Details einzusteigen, ja sogar bis auf die Ebene eines formal korrekten Beweises hinab. Dazu soll es dieses Dokument in verschiedenen Detaillierungen geben. Für alle aber gilt, dass die Formeln in Axiomen, Definitionen und Propositionen in formal korrekter Form vorliegen. Wir wollen bei den Wurzeln anfangen... Dieses Dokument ist im Entstehen begriffen und wird von Zeit zu Zeit aktualisiert. Insbesondere werden an den durch „+++” gekennzeichneten Stellen noch Ergänzungen oder Änderungen vorgenommen. Besonderer Dank geht an meine Frau G e s i n e  D r ä g e r und unseren Sohn L e n n a r t für ihre Unterstützung und ihr Verständnis für ihnen fehlende Zeit. Hamburg, Juli 2011 Michael Meyling ___________________________________________________ Einleitung ══════════ In diesem Dokument nutzen wir die Ergebnisse aus [l]. Nachdem durch die Logik die Art der mathematischen Argumentation vorgegeben wird, wird in der Mengenlehre ganz allgemein über Objekte und ihre Zusammenfassungen gesprochen. Besonders interessant ist die Mengenlehre dadurch, dass sie zum einen von eigentlich allen mathematischen Disziplinen verwendet wird. Zum anderen lässt sich jede mathematische Disziplin innerhalb der Mengenlehre definieren. Zahlentheorie, Algebra, Analysis und alle weiteren Gebiete lassen sich darauf aufbauen. Dieses Dokument beschreibt die mathematischen Grundlagen der Mengenlehre. Ziel ist dabei die Bereitstellung von elementaren Ergebnissen der Mengenlehre, die in anderen mathematischen Disziplinen benötigt werden. Nach den Grundlagen wird die Boolsche Algebra der Klassen betrachtet. Es schliessen sich Betrachtungen über Relationen und Funktionen an. Ein weiteres wichtiges Ergebnis sind die Definition der natürlichen Zahlen und die Erfüllung der Peano-Axiome durch diese, auch auf den Begriff der Rekursion wird eingegangen. Anschließend wird das Auswahlaxiom behandelt. Am Schluss geht es um das Kontinuum. Die Darstellung erfolgt in axiomatischer Weise, soll aber im Ergebnis der mathematischen Praxis entsprechen. Daher wird auch das Axiomensystem der Mengenlehre von A .  P .  M o r s e und J .  L .  K e l l e y (MK) verwendet. Der Aufbau lehnt sich stark an das exzellente und sehr empfehlenswerte Buch von E .  J .  L e m m o n  [lemmon] an. ___________________________________________________ Kapitel 1 Anfangsgründe ═════════════ In diesem Kapitel beginnen wir mit den ganz elementaren Axiomen und Definitionen der Mengenlehre. Wir versuchen nicht, eine formale Sprache einzuführen, ┌ │ Dessen ungeachtet sind die Formeln der Axiome, Definitionen und Propositionen in dem Ursprungstext dieses Dokuments in einer formalen Sprache notiert. Der Ursprungstext ist eine XML-Datei, deren Syntax mittels der XSD http://www.qedeq.org/current/xml/qedeq.xsd definiert wird. Eine nähere Beschreibung der Formelsprache ist unter http://www.qedeq.org/current/doc/project/qedeq_logic_language_de.pdf zu finden. └ und setzen das Wissen um den Gebrauch von logischen Symbolen voraus. Noch genauer formuliert: wir arbeiten mit einer Prädikatenlogik erster Stufe mit Identität. G .  C a n t o r , der als Begründer der Mengenlehre gilt, hat in einer Veröffentlichung im Jahre 1895 eine Beschreibung des Begriffs M e n g e gegeben. Unter einer „Menge” verstehen wir jede Zusammenfassung M von bestimmten wohlunterscheidbaren Objekten m unserer Anschauung oder unseres Denkens (welche die „Elemente” von M genannt werden) zu einem Ganzen. Diese Zusammenfassung kann über die Angabe einer Eigenschaft dieser Elemente erfolgen. Um 1900 wurden verschiedene Widersprüche dieser naiven Mengenlehre entdeckt. Diese Widersprüche lassen sich auf trickreich gewählte Eigenschaften zurückführen. Es gibt verschiedene Möglichkeiten diese Widersprüche zu verhindern. In diesem Text schränken wir zwar die Angabe von Eigenschaften in keiner Weise ein, aber wir nennen das Ergebnis der Zusammenfassung zunächst einmal K l a s s e . Zusätzliche Axiome regeln dann, wann eine bestimmte Klasse auch eine Menge ist. Alle Mengen sind Klassen, aber nicht alle Klassen sind Mengen. Eine Menge ist eine Klasse, die selbst Element einer anderen Klasse ist. Eine Klasse, die keine Menge ist, ist nicht Element irgend einer anderen Klasse. 1.1 Klassen und Mengen ―――――――――――――――――――――― Obgleich wir im Wesentlichen über M e n g e n sprechen wollen, haben wir am Anfang nur K l a s s e n . Dieser Begriff wird nicht formal definiert. Anschaulich gesprochen, ist eine Klasse eine Zusammenfassung von Objekten. Die beteiligten Objekte heißen auch E l e m e n t e der Klasse. Mengen werden dann als eine besondere Art von Klassen charakterisiert. Die folgenden Definitionen und Axiome folgen dem Aufbau einer vereinfachten Version der Mengenlehre nach v o n  N e u m a n n - B e r n a y s - G ö d e l ( N B G ). Die genaue Bezeichnung lautet M K nach M o r s e - K e l l e y . Die hier vorgestellte Mengenlehre hat als Ausgangsobjekte K l a s s e n . Weiterhin wird nur ein einziges Symbol für eine binäre Relation vorausgesetzt: der E n t h a l t e n s e i n o p e r a t o r . ☉ initiale Definition 1 (Elementbeziehung) [definition:in] x ∈ y Wir sagen auch „x i s t E l e m e n t v o n y”, „x g e h ö r t z u y”, „x l i e g t i n y” oder auch „x i s t i n y”. Neben der Identität ist dies das einzige Prädikat welches wir zu Beginn haben. Alle anderen werden definiert. Auch Funktionskonstanten haben wir zu Anfang nicht, ihre Bedeutung wird sukzessive im weiteren Verlauf festgelegt. Obgleich wir die Elementbeziehung einfach negieren können, möchten wir dafür eine Abkürzung definieren. ☉ Definition 2 (Negation der Elementbeziehung) [definition:notIn] x ∉ y ↔ ¬ x ∈ y Unser erstes Axiom besagt, dass beliebige Klassen x und y identisch sind, wenn sie dieselben Elemente enthalten. ☉ Axiom 1 (Extensionalität) [axiom:extensionality] ∀ z (z ∈ x ↔ z ∈ y) → x = y Die Klassen x und y können verschieden definiert sein, beispielsweise: x = Klasse aller nichtnegativen ganzen Zahlen, y = Klasse aller ganzen Zahlen, die als Summe von vier Quadraten geschrieben werden können, aber wenn sie dieselben Elemente besitzen, sind sie identisch. Nun zu unserer ersten Proposition. In dem Extensionalitätsaxiom können wir die Implikation umkehren. ☉ Proposition 1 [theorem:extensonalityEquivalence] ∀ z (z ∈ x ↔ z ∈ y) ↔ x = y Beweis: Dies ist eine einfache Anwendung des zweiten identitätslogischen Axioms. Wir setzen x=y voraus. Nun folgt φ(x) ↔ φ(y) für jedes Prädikat φ. So bekommen wir z ∈ x ↔ z ∈ y für beliebiges z. Also haben wir ∀ z z ∈ x ↔ z ∈ y. Damit zeigten wir x = y → ∀ z z ∈ x ↔ z ∈ y. Zusammen mit dem Axiom 1 erhalten wir das gewünschte Ergebnis. q.e.d. Falls wir das Identitätsprädikat nicht als logisches Symbol voraussetzen würden, dann würden wir es hiermit definieren. Aber dann wird auch ein weiteres Axiom benötigt und es ergeben sich technischen Schwierigkeiten bei der Herleitung der Identitätsaxiome. ┌ │ Zusätzlich zur Definition der Identität muss das Axiom der Extensionalität in folgender Formulierung treten: (x = y ∧ x ∈ z) → y ∈ z. Das ist ein Spezialfall der Leibnizschen Ersetzbarkeit, die wir bereits als Axiom 8 [l] kennen. Die Gültigkeit im allgemeinen Fall kann durch Rekursion über den Aufbau der Formeln nachgewiesen werden. Siehe auch [schmidt] § 6. │ │ Alternativ können wir definieren (x = y ↔ (∀ z (x ∈ z → y ∈ z)) ∧ ∀ z (x ∈ z → z ∈ y)). └ Jetzt legen wir fest, was eine M e n g e ist. ☉ Definition 3 (Menge) [definition:isSet] ℳ(x) ↔ ∃ y x ∈ y Mengen sind also nichts anderes als Klassen mit einer besonderen Eigenschaft. Eine Klasse ist genau dann eine Menge, wenn sie Element irgendeiner Klasse ist. Eine triviale Folgerung aus dieser Definition ist die folgende Äquivalenz. ☉ Proposition 2 [theorem:inSetEqualInSetAndIsSet] x ∈ y ↔ (ℳ(x) ∧ x ∈ y) Beweis: ‘⇒’: Sei x ∈ y. Es folgt ∃ u x ∈ u und daher ℳ(x) und logisch ℳ(x) ∧ x ∈ y. ‘⇐’: Aus ℳ(x) ∧ x ∈ y schließen wir x ∈ y. q.e.d. Nun können wir das Extensionalitätsaxiom wie folgt schreiben. ┌ │ Es wird ein eingeschränkter Allquantor benutzt, z läuft nur über Mengen. └ ☉ Proposition 3 [theorem:extensionalitySetRestricted] x = y ↔ ∀ ℳ(z) (z ∈ x ↔ z ∈ y) Beweis: ‘⇒’: Genauso wie im Beweis zu Proposition 1 erhalten wir die erste Implikation mit dem zweiten identitätslogischen Axiom. ‘⇐’: Angenommen es gelte ∀ ℳ(z) ( z ∈ x ↔ z ∈ y). Sei u eine beliebige Klasse. Falls u ∈ x dann gilt u ist eine Menge nach Definition 3, und daraus folgt mit der Annahme u ∈ y. Analog folgt u ∈ y → u ∈ x. Da u beliebig, haben wir ∀ u (u ∈ x ↔ u ∈ y). Und mit dem Axiom 1 erhalten wir daraus x = y. q.e.d. Beweis: x = y ↔ ∀ z ( z ∈ x ↔ z ∈ y) dies ist Proposition 1 ↔ ∀ z ( ℳ(z) ∧ z ∈ x ↔ ℳ(z) ∧ z ∈ y) Proposition 2 ↔ ∀ z ( ℳ(z) → (z ∈ x ↔ z ∈ y)) Proposition 1 (bh) [l] ↔ ∀ ℳ(z) z ∈ x ↔ z ∈ y) Axiom 11 [l] q.e.d. Unser nächstes Axiom der Mengenlehre ermöglicht uns in simpler Art und Weise neue Klassen zu bilden. Eine Klasse wird ganz einfach durch die Angabe einer prädikatenlogischen Formel charakterisiert. ☉ Axiom 2 (Komprehension) [axiom:comprehension] ∃ x ∀ y (y ∈ x ↔ (ℳ(y) ∧ φ(y))) Durch eine kleine Änderung dieses Axioms würden wir im Folgenden ein N B G -Axiomensystem der Mengenlehre erhalten, welches auf J o h n v o n N e u m a n n , I s a a k B e r n a y s und K u r t G ö d e l zurückgeht. Dazu definieren wir: eine Formel, in der alle gebundenen Subjektvariablen auf Mengen restringiert sind, wird p r ä d i k a t i v e F o r m e l genannt. Prädikative Formeln formalisieren also diejenigen Eigenschaften, die man als „Eigenschaften von Mengen” bezeichnen kann. ┌ │ Noch etwas formaler: in einer prädikativen Formel laufen alle Quantorenvariablen nur über Mengen: ∀ ℳ(x) ∃ ℳ(y) ... └ Fordern wir nun also zusätzlich, dass φ prädikativ sein muss, dann erhalten wir ein NBG-System ┌ │ Dazu werden noch einige andere Axiome --- analog zu den folgenden --- benötigt └ . Durch das Komprehensionsaxiom und die Extensionalität wird nun der Zusammenhang zwischen einer Aussage φ(y) und der durch sie definierten Klasse festgelegt. Dabei behauptet das Komprehensionsaxiom die Existenz mindestens einer Klasse, deren Elemente die Aussage ℳ(y) ∧ φ(y) erfüllen. Das Extensionalitätsaxiom und die Identitätsaxiome sichern ab, dass es höchstens eine solche Klasse gibt: irgend zwei Klassen, welche dieselben Elemente besitzen, sind gleich im Sinne der Ersetzbarkeit in allen einschlägigen Aussagen. Mit anderen Worten: es gibt nur genau eine solche Klasse. ☉ Proposition 4 [theorem:comprehension] ∃! x ∀ y (y ∈ x ↔ (ℳ(y) ∧ φ(y))) Beweis: Zu zeigen ist: ∃ x ∀ y (y ∈ x ↔ ℳ(y) ∧ φ(y)) ∧ ∀ u ∀ v (∀ y (y ∈ u ↔ ℳ(y) ∧ φ(y)) ∧ ∀ y ( y ∈ v ↔ ℳ(y) ∧ φ(y))) → u = v) Seien u und v beliebig. Es gelte weiterhin: ∀ y (y ∈ u ↔ ℳ(y) ∧ φ(y)) ∧ ∀ y ( y ∈ v ↔ ℳ(y) ∧ φ(y))) Dann folgt mit Proposition 2 (h) [l]: ∀ y ((y ∈ u ↔ ℳ(y) ∧ φ(y)) ∧ (y ∈ v ↔ ℳ(y) ∧ φ(y))) Daraus erhalten wir mit Proposition 1 (bg) [l]: ∀ y ((y ∈ u ↔ y ∈ v )). Und mit Proposition 1 folgt nun u = v. Also haben wir gezeigt: ∀ u ∀ v (∀ y (y ∈ u ↔ ℳ(y) ∧ φ(y)) ∧ ∀ y (y ∈ v ↔ ℳ(y) ∧ φ(y))) → u = v) Zusammen mit dem Axiom 2 folgt nun die Behauptung. q.e.d. Ausgehend von Proposition 4 können wir die Sprachsyntax erweitern und eine neue abkürzende Schreibweise einführen. ☉ Regel 1 (Klassenschreibweise) [rule:classDefinition] Name: CLASS_DEFINITION_BY_FORMULA - Version: 1.00.00 Für jede Formel α(x₁) definieren wir den Termausdruck { x₁ | α(x₁)}, wobei x₁ eine Subjektvariable ist, die in α(x₁) nicht gebunden ist. Die freien Variablen von { x₁ | α(x₁)} sind die freien Variablen von α(x₁). Die gebundenen Variablen entsprechen den gebundenen Variablen von α(x₁) ergänzt um x₁. Alle Ableitungsregeln werden entsprechend erweitert. Basierend auf: (theorem:comprehension) Insbesondere müssen die Substitutionsregeln überprüft werden, weil ein Term nun auch gebundene Subjektvariablen enthalten kann. ┌ │ Glücklicherweise haben wir das jedoch schon bei der Formulierung unserer Substitutionsregeln berücksichtigt, so dass wir nichts tun müssen. └ Im Folgenden wird auf diese neue Schreibweise zurückgegriffen. Wir wollen der neu eingeführten Syntax eine Bedeutung geben, und nach einem Blick auf Proposition 4 führen wir das folgende Axiom ein. ☉ Axiom 3 (Axiom der Klassenschreibweise) [axiom:classDefinition] y ∈ { x | φ(x) } ↔ (ℳ(y) ∧ φ(y)) Dies Axiom zusammen mit Regel 1 führt nur zu einer k o n s e r v a t i v e n Erweiterung unserer formalen Sprache. Das bedeutet, dass mit der Erweiterung nicht mehr Formeln, die der alten Syntax genügen, abgeleitet werden können. Es ist nur bequem, eine neue elegante Schreibweise zu besitzen. ┌ │ Unter einer konservativen Erweiterung verstehen wir das Folgende: Sei ℒ eine Sprache und ℒ’ eine Erweiterung von ℒ. Da ℒ’ ⊃ ℒ gilt auch Formel_(\mathfrak)L’ ⊃ Formel_(\mathfrak)L. Falls nun für jede Formelmenge Γ ⊆ Formel_(\mathfrak)L und jede Formel α ∈ Formel_(\mathfrak)L gilt: Γ ⊢_(\mathfrak)L’ α ⇒ Γ ⊢_(\mathfrak)L α, dann heißt ℒ’ eine k o n s e r v a t i v e Erweiterung von ℒ. └ . Die neue Schreibweise kann auch in einfacher Weise in die alte Syntax transformiert werden. Die Gültigkeit der Ausgangsprädikate drückt sich für diese neue Termart wie folgt aus. ☉ Proposition 5 [theorem:setNotation] (a) z ∈ { x | φ(x) } ↔ (ℳ(z) ∧ φ(z)) (b) z = { x | φ(x) } ↔ ∀ u (u ∈ z ↔ u ∈ { x | φ(x) } ) (c) { x | φ(x) } = { y | ψ(y) } ↔ ∀ u (u ∈ { x | φ(x) } ↔ u ∈ { y | ψ(y) } ) (d) { x | φ(x) } ∈ { y | ψ(y) } ↔ ∀ u ∀ v ((u = { x | φ(x) } ∧ v = { y | ψ(y) } ) → u ∈ v) (e) { x | φ(x) } ∈ z ↔ ∀ u (u = { x | φ(x) } → u ∈ z) +++ wenn diese Formel richtig gesetzt würde, sollte sie so aussehen: y ∈ { x | φ(x) } ↔ ℳ(y) ∧ φ(y) (a) y = { x |  φ(x) } ↔ ∀ z (z ∈ y ↔ z ∈ { x | φ(x) }) (b) { x | φ(x) } = { x | ψ(x) } ↔ ∀ z (z ∈ { x | φ(x) } (c) ↔ z ∈ {x | ψ(x) }) { x | φ(x) } ∈ { x | ψ(x) } ↔ ∀ u ∀ v ((u = { x | φ(x) } ∧ v = { x | ψ(x) }) → u ∈ v) (d) { x | φ(x) } ∈ y ↔ ∀ u (u = { x | φ(x) } → u ∈ y) (e) Beweis: Die Formel in a) ist einfach Axiom 3. Mit Proposition 1 erhalten wir b) und c). Mit den Identitätsgesetzen bekommen wir d) und e). q.e.d. Durch sukzessives Anwenden des obigen Satzes kann also die neue Syntax in die alte überführt werden. Da durch die neue Schreibweise ein Term eindeutig festgelegt wird, muss natürlich auch das Folgende gelten. ☉ Proposition 6 [theorem:setDefinitionUnique] ∃! x x = { y | φ(y) } Beweis: ∃! x ∀ z ( z ∈ x ↔ ℳ(z) ∧ φ(z)) dies ist Proposition 4 ∃! x ∀ z ( z ∈ x ↔ z ∈ { y | φ(y) } Proposition 5 ∃! x x = { y | φ(y) } Proposition 1 q.e.d. Aus der Äquivalenz von Aussageformen kann auf die Gleichheit der daraus gebildeten Klassen geschlossen werden. ☉ Proposition 7 [theorem:propositionEqualImplClassEqual] ∀ x (φ(x) ↔ ψ(x)) → { x | φ(x) } = { x | ψ(x) } Beweis: (φ(x) ↔ ψ(x)) → (φ(x) ∧ ℳ(x) ↔ ψ(x) ∧ ℳ(x)) Proposition 1 (bl) [l] ∀ x ((φ(x) ↔ ψ(x)) → (φ(x) ∧ ℳ(x) ↔ ψ(x) ∧ ℳ(x))) Regel 11 [l] ∀ x (φ(x) ↔ ψ(x)) → ∀ x (φ(x) ∧ ℳ(x) ↔ ψ(x) ∧ ℳ(x)) Proposition 2 (a) [l] → ∀ x ( x ∈ { y | φ(y) } ↔ x ∈ { y | ψ(y) }) Proposition 5 → { y | φ(y) } = { y | ψ(y) } Proposition 5 q.e.d. Die Umkehrung gilt jedoch nicht. Das liegt daran, dass mit der Klassenschreibweise nur Mengen zusammengefasst werden. Beispiel: wenn φ(x) ↔ x ≠ x und ψ(x) ↔ ∀ y (y ∈ x → y ∉ y), dann sind die durch beide Aussageformen erzeugten Klassen identisch mit der leeren Klasse (Definition 6). Keine Klasse erfüllt φ(x), allerdings erfüllt die Russellsche Klasse (Definition 4) die Bedingung ψ(x). Jede Klasse lässt sich durch eine Aussage beschreiben, indem auf ihre Elemente Bezug genommen wird. ☉ Proposition 8 [theorem:classDescriptionPossible] x = { y | y ∈ x } Beweis: z ∈ x ↔ z ∈ x ∧ ℳ(z) Proposition 2 z ∈ x ↔ z ∈ {y | y } Proposition 5 ∀ z (z ∈ x ↔ z ∈ {y | y }) Regel 11 [l] x = {y | y } Proposition 1 q.e.d. 1.2 Spezielle Klassen ――――――――――――――――――――― In diesem Abschnitt definieren wir die ersten Klassen. Die Russellsche Klasse kann nun einfach definiert werden. ☉ Definition 4 (Russell-Klasse) [definition:RussellClass] ℛu = { x | x ∉ x } Die Russellsche Klasse ist eine e c h t e Klasse, d. h. sie ist keine Menge. ☉ Proposition 9 [theorem:RussellClassIsClass] ¬ ℳ(ℛu) Beweis: y ∈ { x | φ(x) } ↔ ℳ(y) ∧ φ(y) das ist Proposition 5 y ∈ { x | x ∉ x } ↔ ℳ(y) ∧ y ∉ y Substitution für φ y ∈ ℛu ↔ ℳ(y) ∧ y ∉ y Definition 4 ℛu ∈ ℛu ↔ ℳ(ℛu) ∧ ℛu ∉ ℛu Substitution für y ℳ(ℛu) ∧ ℛu ∈ ℛu ↔ ℳ(ℛu) ∧ ℛu ∉ ℛu Proposition 2 ¬ ℳ(ℛu) Proposition 1 (bi) [l] q.e.d. Die A l l k l a s s e soll alles mögliche umfassen. ☉ Definition 5 (Allklasse) [definition:universalClass] Ʋ = { x | x = x } Da in einer Klasse nur Mengen als Elemente vorkommen, verwundert es nicht, dass folgendes gilt. ☉ Proposition 10 [theorem:isInUniversalClass] x ∈ Ʋ ↔ ℳ(x) Beweis: x ∈ { y | φ(y) } ↔ ℳ(x) ∧ φ(x) dies ist Proposition 5 x ∈ { y | y = y } ↔ ℳ(x) ∧ y = y Substitution für φ x ∈ Ʋ ↔ ℳ(x) ∧ y = y Definition 5 x ∈ Ʋ ↔ ℳ(x) Proposition 1 (au) [l] und Axiom 7 [l] q.e.d. Mitgliedschaft in der Allklasse ist daher gleichbedeutend mit der Eigenschaft, eine Menge zu sein. Die Allklasse umfasst alle Mengen. ☉ Proposition 11 [theorem:universalClassContainsAllSets] Ʋ = { x | ℳ(x) } Beweis: Ʋ = { x | x = x} Definition 5 ∀ y (y ∈ Ʋ ↔ y ∈ { x | x = x} Proposition 1 ∀ y (y ∈ Ʋ ↔ ℳ(y) ∧ y = y Proposition 5 ∀ y (y ∈ Ʋ ↔ ℳ(y) ∧ ⊤ Regel 10 [l] ∀ y (y ∈ Ʋ ↔ ℳ(y) Proposition 1 (au) [l] ∀ y (y ∈ Ʋ ↔ ℳ(y) ∧ ℳ(y) Proposition 1 (al) [l] ∀ y (y ∈ Ʋ ↔ y ∈ { x | ℳ(x)} Proposition 5 Ʋ = { x | ℳ(x)} Proposition 1 q.e.d. Entsprechend definieren wir die l e e r e K l a s s e . Später werden wir feststellen, dass die leere Klasse eine Menge ist. Dazu benötigen wir jedoch weitere Mengenaxiome. Wir bezeichnen diese Klasse jedoch schon jetzt mit den Worten l e e r e M e n g e . ☉ Definition 6 (Leere Klasse) [definition:emptySet] ∅ = { x | x ≠ x } Keine Klasse ist Element der leeren Klasse. ☉ Proposition 12 [theorem:noClassIsMemberOfEmptySet] ∀ z z ∉ ∅ Beweis: Annahme: z ∈ ∅ z ∈ { x | x ≠ x} Definition 6 ℳ(z) ∧ z ≠ z Axiom 3 z ≠ z elementary logic ¬ (z = z) Definition 4 [l] Damit haben wir einen Widerspruch zu Axiom 7 [l] und unsere Annahme muss falsch sein. Also gilt ¬ (z ∈ ∅) und wir können weiter folgern. ¬ ( z ∈ ∅) z ∉ ∅ Definition 2 ∀ z z ∉ ∅ Regel 11 [l] q.e.d. Eine Klasse, welche keine Elemente besitzt, ist die leere Klasse. ☉ Proposition 13 [theorem:noClassIsMemberIsEmptySet] ∀ z z ∉ x ↔ x = ∅ Beweis: x = ∅ ↔ ∀ z (z ∈ x ↔ z ∈ ∅) Proposition 1 ↔ ∀ z (z ∉ x ↔ z ∉ ∅) Regel 8 [l] mit Proposition 1 (ao) [l] ↔ ∀ z (z ∉ x ↔ ⊤) Proposition 12 ↔ ∀ z z ∉ x Regel 8 [l] mit Proposition 1 (be) [l] q.e.d. ___________________________________________________ Kapitel 2 Boolesche Algebra der Klassen ═════════════════════════════ Die elementaren Operationen von Klassen und ihre Eigenschaften werden nun beschrieben. Eine Boolesche Algebra, oft auch Boolescher Verband genannt, ist eine spezielle algebraische Struktur, die die Eigenschaften der logischen Operatoren u n d , o d e r , n i c h t sowie die Eigenschaften der mengentheoretischen Verknüpfungen D u r c h s c h n i t t , V e r e i n i g u n g und K o m p l e m e n t abstrahiert. Sie ist benannt nach G . B o o l e , der sie in der Mitte des 19. Jahrhunderts definierte, um algebraische Methoden in der Aussagenlogik anwenden zu können. 2.1 Boolesche Klassenoperatoren ――――――――――――――――――――――――――――――― Die Klassenschreibweise Regel 1 ermöglicht die Definition von Klassenoperatoren mithilfe logischer Verknüpfungen. Die Vereinigung zweier Klassen besteht aus den Elementen beider Klassen. ☉ Definition 7 (Vereinigung) [definition:union] (x ∪ y) = { z | (z ∈ x ∨ z ∈ y) } Entsprechend wird der Durchschnitt zweier Klassen definiert, als die Klasse, die aus den Elementen besteht, die in beiden Klassen vorhanden sind. ☉ Definition 8 (Durchschnitt) [definition:intersection] (x ∩ y) = { z | (z ∈ x ∧ z ∈ y) } Auch das Komplement einer Klasse kann einfach definiert werden. ☉ Definition 9 (Komplement) [definition:complement] ∁x = { z | z ∉ x } Ob eine Menge ein Element der Vereinigung zweier Klassen ist, kann natürlich auch direkt angegeben werden. ☉ Proposition 14 [theorem:unionMember] z ∈ (x ∪ y) ↔ (z ∈ x ∨ z ∈ y) Beweis: (x ∪ y) = { z | (z ∈ x ∨ z ∈ y ) } Definition 7 u ∈ (x ∪ y) ↔ u ∈ { z | (z ∈ x ∨ z ∈ y ) } Proposition 3 [l] u ∈ (x ∪ y) ↔ (ℳ(u) ∧ (u ∈ x ∨ u ∈ y)) Axiom 3 u ∈ (x ∪ y) ↔ ((ℳ(u) ∧ u ∈ x ) ∨ (ℳ(u) ∧ u ∈ y)) Proposition 1 (at) [l] u ∈ (x ∪ y) ↔ (u ∈ x ∨ u ∈ y) Proposition 2 q.e.d. Entsprechendes gilt für den Durchschnitt zweier Klassen. ☉ Proposition 15 [theorem:intersectionMember] z ∈ (x ∩ y) ↔ (z ∈ x ∧ z ∈ y) Beweis: (x ∩ y) = { z | (z ∈ x ∧ z ∈ y ) } Definition 7 u ∈ (x ∩ y) ↔ u ∈ { z | (z ∈ x ∧ z ∈ y ) } Proposition 3 [l] u ∈ (x ∩ y) ↔ (ℳ(u) ∧ (u ∈ x ∧ u ∈ y)) Axiom 3 u ∈ (x ∩ y) ↔ ((ℳ(u) ∧ u ∈ x ) ∧ u ∈ y)) Proposition 1 (aj) [l] u ∈ (x ∩ y) ↔ (u ∈ x ∧ u ∈ y) Proposition 2 q.e.d. Analoges gilt für das Komplement, dort muss jedoch die Mengeneigenschaft explizit abgeprüft werden. ☉ Proposition 16 [theorem:complementMember] z ∈ ∁x ↔ (ℳ(z) ∧ z ∉ x) Beweis: ∁x = { z | z ∉ x } Definition 9 u ∈ ∁x ↔ u ∈ { z | z ∉ x } Proposition 3 [l] u ∈ ∁x ↔ (ℳ(u) ∧ u ∉ x) Axiom 3 q.e.d. Die vorherigen Sätze zeigen die Übertragbarkeit der Eigenschaften der logischen Verknüpfungen ∨, ∧ und ¬ auf die Klassenverknüpfungen ∪, ∩ und ‾ . Deshalb lassen sich die entsprechenden logischen Gesetzmässigkeiten direkt auf die Klassenverknüpfungen übertragen. ☉ Proposition 17 [theorem:unionIntersectionComplement] (a) (x ∪ y) = (y ∪ x) (b) (x ∩ y) = (y ∩ x) (c) ((x ∪ y) ∪ z) = (x ∪ (y ∪ z)) (d) ((x ∩ y) ∩ z) = (x ∩ (y ∩ z)) (e) x = (x ∪ x) (f) x = (x ∩ x) (g) ∁∁x = x (h) ∁(x ∪ y) = (∁x ∩ ∁y) (i) ∁(x ∩ y) = (∁x ∪ ∁y) (j) (x ∪ (y ∩ z)) = ((x ∪ y) ∩ (x ∪ z)) (k) (x ∩ (y ∪ z)) = ((x ∩ y) ∪ (x ∩ z)) (l) ∁∅ = Ʋ (m) ∁Ʋ = ∅ (n) (x ∩ Ʋ) = x (o) (x ∩ ∅) = ∅ (p) (x ∪ Ʋ) = Ʋ (q) (x ∪ ∅) = x (r) (x ∪ ∁x) = Ʋ (s) (x ∩ ∁x) = ∅ Beweis: Exemplarisch beweisen wir (g). u ∈ x ↔ (ℳ(u) ∧ u ∈ x) Definition 9 ↔ (⊥ ∨ (ℳ(u) ∧ u ∈ x)) Proposition 1 (ax) [l] ↔ ((ℳ(u) ∧ ¬ ℳ(u)) ∨ (ℳ(u) ∧ u ∈ x)) Proposition 1 (az) [l] ↔ (ℳ(u) ∧ (¬ ℳ(u)) ∧ u ∈ x)) Proposition 1 (at) [l] ↔ (ℳ(u) ∧ (¬ ℳ(u)) ∧ ¬ ¬ u ∈ x)) Proposition 1 (am) [l] ↔ (ℳ(u) ∧ (¬ ℳ(u)) ∧ ¬ u ∉ x)) Definition 2 ↔ (ℳ(u) ∧ ¬ (ℳ(u)) ∨ u ∉ x)) Proposition 1 (aq) [l] ↔ (ℳ(u) ∧ ¬ (u ∈ ∁x)) Proposition 16 ↔ (ℳ(u) ∧ u ∉ ∁x) Definition 2 ↔ u ∈ ∁∁x Proposition 16 Also haben wir gezeigt: u ∈ x ↔ u ∈ ∁∁x Nun können wir weiter schließen. u ∈ x ↔ u ∈ ∁∁x ∀ u (u ∈ x ↔ u ∈ ∁∁x) Regel 11 [l] ∀ u u ∈ x ↔ ∀ u u ∈ ∁∁x Proposition 2 (c) [l] x = ∁∁x Proposition 3 q.e.d. 2.2 Boolsche Algebra ―――――――――――――――――――― Die Klassen bilden mit den Operatoren ∩, ∪, ‾  und den Konstanten ∅, Ʋ eine Boolesche Algebra. +++ Referenzen zu Kommutativität, Assoziativität, Distributivität, Idempotenz, etc. 2.3 Ordnung ――――――――――― Für eine Boolsche Algebra kann eine kanonische T e i l o r d n u n g definiert werden. Daher können wir auch für die Klassenalgebra eine Teilordnung festlegen. Wir definieren die T e i l k l a s s e n r e l a t i o n durch eine Schnittklassenbildung. ☉ Definition 10 (Teilklasse) [definition:subclass] x ⊆ y ↔ (x ∩ y) = x Sind x und y Mengen sagen wir auch: x ist T e i l m e n g e von y. Die übliche Definition der Teilklassenrelation erhalten wir nun als Satz. ☉ Proposition 18 [theorem:subsetIfMemberschipImpl] x ⊆ y ↔ ∀ z (z ∈ x → z ∈ y) Diese Relation ist reflexiv, transitiv und antisymmetrisch, definiert also eine Teilordnung mit ∅ als kleinstem und Ʋ als größtem Element. ☉ Proposition 19 [theorem:subsetIsPartialOrdered] (a) x ⊆ x (b) (x ⊆ y ∧ y ⊆ z) → x ⊆ z (c) (x ⊆ y ∧ y ⊆ x) ↔ x = y (d) ∅ ⊆ x (e) x ⊆ Ʋ (f) x ⊆ ∅ → x = ∅ (g) Ʋ ⊆ x → x = Ʋ Eine Schnittklasse ist immer Teilmenge ihrer Ausgangsklassen. ☉ Proposition 20 [theorem:intersectionIsSubset] (a) (x ∩ y) ⊆ x (b) (x ∩ y) ⊆ y Eine Vereinigungsklasse hat ihre Ausgangsklassen als Teilklassen. ☉ Proposition 21 [theorem:unionIsSuperset] (a) x ⊆ (x ∪ y) (b) y ⊆ (x ∪ y) Für zwei Teilklassen ist auch die Vereinigungsklasse Teilklasse. Und falls eine Klasse Teilklasse von zwei Klassen ist, dann ist sie auch Teilklasse der Schnittklasse. Beide Beziehungen sind auch umkehrbar. ☉ Proposition 22 [theorem:subsetAndAddition] (a) (x ⊆ z ∧ y ⊆ z) ↔ (x ∪ y) ⊆ z (b) (z ⊆ x ∧ z ⊆ y) ↔ z ⊆ (x ∩ y) Bei Schnitt oder Vereinigung bleibt eine Teilklassenbeziehung erhalten. ☉ Proposition 23 [theorem:subsetAddition] (a) x ⊆ y → (x ∪ z) ⊆ (y ∪ z) (b) x ⊆ y → (x ∩ z) ⊆ (y ∩ z) Bei der Bildung des Komplements kehrt sich die Teilklassenbeziehung um. ☉ Proposition 24 [theorem:subsetComplement] x ⊆ y ↔ ∁y ⊆ ∁x Für das Komplement und die Teilklassenbeziehung gelten die folgenden Äquivalenzen. ☉ Proposition 25 [theorem:subsetComplementEquations] (a) x ⊆ y ↔ (x ∩ ∁y) = ∅ (b) x ⊆ y ↔ (∁x ∪ y) = Ʋ (c) x ⊆ ∁y ↔ (x ∩ y) = ∅ (d) (x ∩ y) ⊆ z ↔ x ⊆ (∁y ∪ z) 2.4 Einerklassen und Klassenpaare ――――――――――――――――――――――――――――――――― Eine Klasse kann auch durch explizite Auflistung ihrer Elemente definiert werden. Insbesondere kann durch Angabe eines Elements die sogenannte E i n e r k l a s s e festgelegt werden. Wiederum mit Regel 1 können wir die Sprachsyntax erweitern und eine neue abkürzende Schreibweise einführen. ☉ Definition 11 (Einerklasse) [definition:singleton] { x } = { y | (ℳ(x) → y = x) } Da der Ausdruck {x} für jegliches x definiert ist, kann er auch für den Fall, dass x eine echte Klasse ist, gebildet werden. In diesem Fall erfüllen alle Mengen y die Bedingung ℳ(y) ∧ (ℳ(x) → y = x) und die Einerklasse ist mit der Allklasse identisch. Das führt zu einem technisch einfacheren Umgang mit der Einerklasse. ┌ │ Andere Autoren wie z. B. auch K. Gödel, definieren {x} durch {y | y = x}. └ Für Mengen enthält die Einerklasse wie gewünscht nur die Menge selbst. ☉ Proposition 26 [theorem:setSingletonHasSetAsOnlyElement] ℳ(x) → ∀ z (z ∈ { x } ↔ z = x) Für echte Mengen ist die Einerklasse mit der Allklasse identisch. ☉ Proposition 27 [theorem:properSingletonIsUniversalClass] ¬ ℳ(x) → { x } = Ʋ Einerklasse einer Menge zu sein ist äquivalent dazu Element seiner Einerklasse zu sein. ☉ Proposition 28 [theorem:setSingletonEqualHasItselfAsElement] ℳ(x) ↔ x ∈ { x } Nun kann einfach durch Vereinigung zweier Einerklassen das P a a r zweier Klassen definiert werden. ☉ Definition 12 (Paar) [definition:pair] { x, y } = ({ x } ∪ { y }) Ein Klassenpaar kann auch direkt, d. h. ohne Zuhilfenahme der Einerklassen beschrieben werden. ☉ Proposition 29 [theorem:classPairIsEqual] { x, y } = { z | ((ℳ(x) ∧ ℳ(y)) → (z = x ∨ z = y)) } Für Klassenpaare, die aus Mengen gebildet werden, kann die Eigenschaft, Element des Klassenpaares zu sein, einfacher ausgedrückt werden. ☉ Proposition 30 [theorem:membershipOfClassPair] (ℳ(x) ∧ ℳ(y)) → ∀ z (z ∈ { x, y } ↔ (z = x ∨ z = y)) Falls bei der Klassenpaarbildung eine echte Klasse dabei ist, dann ist das resultierende Klassenpaar mit der Allklasse identisch. ☉ Proposition 31 [theorem:properClassPairIsUniversalClass] (¬ ℳ(x) ∨ ¬ ℳ(y)) → { x, y } = Ʋ Wir notieren, dass die Klassenpaarbildung kommutativ ist. ☉ Proposition 32 [theorem:classPairBuildingIsCommutative] { x, y } = { y, x } Die Einerklasse ist ein Spezialfall des Klassenpaares. ☉ Proposition 33 [theorem:singletonIsClassPair] { x } = { x, x } Menge zu sein ist äquivalent dazu, Element eines Klassenpaares zu sein. ☉ Proposition 34 [theorem:setEquiInClassPair] ℳ(x) ↔ x ∈ { x, y } Für Mengen ist die Elementbeziehung äquivalent zur Teilklassenbeziehung für die zugehörige Einerklasse. ☉ Proposition 35 [theorem:elementEquiSingletonSubclass] ℳ(x) → (x ∈ y ↔ { x } ⊆ y) Die Gleichheit von aus Mengen gebildeten Klassenpaaren ist wie erwartet. ☉ Proposition 36 [theorem:pairIdentities] (ℳ(x) ∧ ℳ(y) ∧ ℳ(u) ∧ ℳ(v)) → ({ x, y } = { u, v } → ((x = u ∧ y = v) ∨ (x = v ∧ y = u))) 2.5 Unendliche Boolsche Operatoren ―――――――――――――――――――――――――――――――――― Es können auch beliebige Schnittklassen und Vereinigungsklassen gebildet werden. Dazu muss nur festgelegt werden, über welche Klassen jeweils geschnitten bzw. vereinigt wird. Für eine Klasse von Mengen wird ein P r o d u k t so definiert, dass genau die Elemente, die in allen Mengen enthalten sind, in dem Produkt liegen. ☉ Definition 13 (Mengenprodukt) [setProduct] ⋂ x = { z | ∀ y (y ∈ x → z ∈ y) } Diese Funktion kann als Verallgemeinerung der Schnittklassenbildung angesehen werden. Siehe auch Proposition 46. Wir sagen auch, dass die Klasse x eine M e n g e n f a m i l i e festlegt. Jedes Element von x ist ein Mitglied der Familie. Wie üblich können wir die Elementbeziehung zum Mengenprodukt wie folgt beschreiben. ☉ Proposition 37 [theorem:setProductMembership] z ∈ ⋂ x ↔ (ℳ(z) ∧ ∀ y (y ∈ x → z ∈ y)) Für den Speziallfall x = ∅ erhalten wir. ☉ Proposition 38 [theorem:emptySetProduct] ⋂ ∅ = Ʋ Falls wir das Mengenprodukt einer nichtleeren Klasse bilden, können wir die Mengenbedingung weglassen. ☉ Proposition 39 [theorem:nonEmptySetProductMembership] x ≠ ∅ → (z ∈ ⋂ x ↔ ∀ y (y ∈ x → z ∈ y)) Analog können wir die M e n g e n s u m m e definieren. Genau die Elemente, die in irgend einer der Mengen vorkommen, sollen in der Summe liegen. ☉ Definition 14 (Mengensumme) [definition:setSum] ⋃ x = { z | ∃ y (y ∈ x ∧ z ∈ y) } Die Zugehörigkeit zur Mengensumme kann wie folgt ausgedrückt werden. ☉ Proposition 40 [theorem:setSumMembership] z ∈ ⋃ x ↔ ∃ y (y ∈ x ∧ z ∈ y) Hier können wir die Mengenbedingung ℳ(z) weglassen. Für die leere Klasse erhalten wir. ☉ Proposition 41 [theorem:emptySetSum] ⋃ ∅ = ∅ Die Teilklassenrelation verhält sich zu Mengenprodukt und Mengensumme wie folgt. ☉ Proposition 42 [theorem:subsetSumProductImplication] (a) x ⊆ y → ⋂ y ⊆ ⋂ x (b) x ⊆ y → ⋃ x ⊆ ⋃ y Die Elementbeziehung induziert Teilklassenbeziehungen in der folgenden Weise. ☉ Proposition 43 [theorem:membershipToSetProductAndSum] (a) x ∈ y → x ⊆ ⋃ y (b) x ∈ y → ⋂ y ⊆ x Die Vereinigungs- und Schnittklassenbildung passt zu Mengensumme und Mengenprodukt wie nachfolgend beschrieben. ☉ Proposition 44 [theorem:unionIntersectionSetSumProduct] (a) ⋂ (x ∪ y) = (⋂ x ∩ ⋂ y) (b) ⋃ (x ∪ y) = (⋃ x ∪ ⋃ y) (c) ⋃ (x ∩ y) ⊆ (⋃ x ∩ ⋃ y) Für den Fall einer nichtleeren Mengenfamilie haben wir dieses Ergebnis. ☉ Proposition 45 [theorem:nonEmptySumProductSubSet] ∀ x (x ≠ ∅ → ⋂ x ⊆ ⋃ x) Für Mengenpaare erhalten wir die erwarteten Ergebnisse. ☉ Proposition 46 [theorem:setPairSetSumProduct] (a) (ℳ(x) ∧ ℳ(y)) → ⋂ { x, y } = (x ∩ y) (b) (ℳ(x) ∧ ℳ(y)) → ⋃ { x, y } = (x ∪ y) Für Einermengen erhalten wir analoge Aussagen. ☉ Proposition 47 [theorem:singletonSetSumProduct] (a) ℳ(x) → ⋂ { x } = x (b) ℳ(x) → ⋃ { x } = x 2.6 Potenzklassenbildung ―――――――――――――――――――――――― Ein wichtiger Operator fehlt uns noch. Aus der Teilklassenrelation lässt sich ein weiterer Klassenoperator gewinnen, die P o t e n z k l a s s e n b i l d u n g . ☉ Definition 15 (Potenzklasse) [definition:power] ℘(x) = { z | z ⊆ x } Wir erinnern noch einmal daran, dass nur Mengen in der Potenzklasse enthalten sein können. Für diesen neuen Operator gelten die folgenden Aussagen. ☉ Proposition 48 [theorem:powerPropositions] (a) z ∈ ℘(x) ↔ (ℳ(z) ∧ z ⊆ x) (b) ℘(Ʋ) = Ʋ (c) ℘(∅) = { ∅ } (d) ℳ(x) ↔ x ∈ ℘(x) (e) x ⊆ y → ℘(x) ⊆ ℘(y) (f) (ℳ(x) ∧ ℘(x) ⊆ ℘(y)) → x ⊆ y (g) ℘((x ∩ y)) = (℘(x) ∩ ℘(y)) (h) (℘(x) ∪ ℘(y)) ⊆ ℘((x ∪ y)) (i) x ⊆ ℘(⋃ x) (j) ⋃ ℘(x) ⊆ x Speziell für die Potenzklasse einer Menge lässt sich Proposition 48 verschärfen. ☉ Proposition 49 [theorem:powerSetPropositions] ℳ(x) → x = ⋃ ℘(x) Für Mengen heben sich die Potenzklassenbildung und die Mengensumme (in dieser Reihenfolge) gegenseitig auf. Später können wir die Mengenbedingung fallenlassen, da wir dann über weitere Axiome verfügen. ___________________________________________________ Kapitel 3 Mengen, Relationen und Funktionen ═════════════════════════════════ In diesem Kapitel wird noch einmal genauer auf die Mengeneigenschaft eingegangen und es werden neue Axiome angegeben, um die Existenz von Mengen abzusichern. Um Relationen definieren zu können, wird der Begriff des g e o r d n e t e n K l a s s e n p a a r e s benötigt, der es ermöglicht, das c a r t e s i s c h e P r o d u k t von Klassen zu definieren. Relationen sind Teilklassen von cartesischen Produkten und bilden zusammen mit bestimmten Operationen eine u n i v e r s e l l e A l g e b r a . Spezielle Relationen sind die Ä q u i v a l e n z r e l a t i o n e n , die einen etwas weiter gefassten Gleichheitsbegriff ermöglichen. Funktionen sind ebenfalls spezielle Relationen, Das Fraenkelsche Ersetzungsaxiom garantiert, dass Mengen auf Mengen abgebildet werden. 3.1 Mengen ―――――――――― Zur Darstellung der Booleschen Klassenalgebra wurden noch keine mengentheoretischen Axiome benötigt Im Folgenden werden weitere Axiome vorgestellt, die Bedingungen dafür angeben, wann eine Klasse eine Menge ist. Die leere Klasse soll eine Menge sein. ☉ Axiom 4 (Axiom der leeren Menge) [axiom:emptySet] ℳ(∅) Damit haben wir zum ersten Mal Kenntnis über die Existenz einer Menge. Um die Mengeneigenschaft für Paare von Mengen zu erhalten, haben wir das folgende Axiom. ☉ Axiom 5 (Axiom der Paarmenge) [axiom:pairingSet] (ℳ(x) ∧ ℳ(y)) → ℳ({ x, y }) Auch die Mengensumme einer Menge soll wieder eine Menge sein. ☉ Axiom 6 (Summenmengenaxiom) [axiom:setSumSet] ℳ(x) → ℳ(⋃ x) Die Potenzklasse einer Menge soll auch wieder eine Menge sein. ☉ Axiom 7 (Axiom der Potenzmenge) [axiom:powerSet] ℳ(x) → ℳ(℘(x)) Die Teilklasse einer Menge soll wieder eine Menge sein. ☉ Axiom 8 (Teilmengenaxiom) [axiom:subset] (ℳ(x) ∧ y ⊆ x) → ℳ(y) Die obigen Mengenaxiome ermöglichen es uns Mengen zu konstruieren. Durch das Axiom 4 haben wir eine erste Menge ∅. Durch die Anwendung von Axiom 7 erhalten wir die Menge { ∅ }. Die erneute Bildung der Potenzmenge erzeugt die Menge { ∅, { ∅ } }. Durch wiederholtes Anwendung der Prozedur bekommen wir eine beliebige Anzahl von Mengen. ┌ │ Dass die Mengen alle paarweise voneinander verschieden sind, ist leicht zu zeigen. └ Weiterhin stellen wir fest, dass wir mit unseren bisherigen Axiomen nur die Existenz von Mengen mit einer endlichen Elementanzahl nachweisen können. Diese endlichen Mengen sind „sicher” in dem Sinne, dass sie nicht zu den Widersprüchen führen, wie sie in der uneingeschränkten Mengenlehre Zermelos auftreten, Mit Hilfe der neuen Axiome können weitere Folgerungen gezogen werden. ☉ Proposition 50 [theorem:isSet] (a) (¬ ℳ(y) ∧ y ⊆ x) → ¬ ℳ(x) (b) ¬ ℳ(Ʋ) (c) (ℳ(x) ∧ ℳ(y)) → ℳ((x ∪ y)) (d) (ℳ(x) ∧ ℳ(y)) → ℳ((x ∩ y)) (e) ℳ(x) → ℳ({ x }) (f) ℳ(x) → ¬ ℳ(∁x) (g) x = ⋃ ℘(x) (h) ℳ(x) ↔ ℳ(⋃ x) (i) ⋂ Ʋ = ∅ (j) ⋃ Ʋ = Ʋ (k) x ≠ ∅ → ℳ(⋂ x) Wir stellen abschließend fest, dass wir Axiom 4 (Axiom der leeren Menge) in den Beweisen bisher noch nicht verwendet haben. Da bedeutet, dass alle bisherigen Sätze unabhängig von der Existenz einer einzigen Menge gültig sind. 3.2 Geordnetes Klassenpaar ―――――――――――――――――――――――――― Das Konzept eines geordneten Paares ist für die weitere Entwicklung unserer Theorie wichtig. Es ermöglicht uns die Objekte anzuordnen. Bisher hingen unsere Objektzusammenfassungen nicht von der Reihenfolge der Sammlung ab. Wir wollen nun aber auch nach der Zusammenfassung herausfinden können, welches das e r s t e Element und welches das z w e i t e Element war. Die Definition eines geordneten Paares 〈 x, y〉 erfolgt nach N .  W i e n e r (1914) bzw. K .  K u r a t o w s k i (1921). ☉ Definition 16 (Geordnetes Paar) [definition:orderedPair] 〈 x, y 〉 = { { x }, { x, y } } Für geordnete Paare von Mengen spielt die Reihe der angegebenen Elemente eine Rolle. Geordnete Paare sollten nur dann identisch sein, wenn ihre ersten Elemente und ihre zweiten Elemente identisch sind. ☉ Proposition 51 [theorem:orderedPairEquality] (ℳ(x) ∧ ℳ(y) ∧ ℳ(u) ∧ ℳ(v)) → (〈 x, y 〉 = 〈 u, v 〉 → (x = u ∧ y = v)) Ein aus Mengen gebildetes geordnetes Paar ist auch eine Menge. Die Umkehrung gilt auch. ☉ Proposition 52 [theorem:orderedPairOfSets] (ℳ(x) ∧ ℳ(y)) ↔ ℳ(〈 x, y 〉) Falls eine der Klassen keine Menge ist, dann ist das geordnete Paar mit der Allklasse identisch. ☉ Proposition 53 [theorem:orderedPairWithNonSet] (¬ ℳ(x) ∨ ¬ ℳ(y)) → 〈 x, y 〉 = Ʋ Um über geordnete Paare sprechen zu können, benötigen wir ein neues Prädikat „ist ein geordnetes Paar ”. ☉ Definition 17 (Eigenschaft geordnetes Paar) [definition:isOrderedPair] isOrderedPair(x) ↔ ∃ u ∃ v x = 〈 u, v 〉 Wir betonen noch einmal, dass auch Ʋ ein geordnetes Paar ist. Aber da wir meistens über Elemente von Klassen sprechen, haben wir nur mit Mengen zu tun, die eventuell auch geordnete Paare sind. 3.3 Kartesisches Produkt ―――――――――――――――――――――――― Für die geordneten Klassenpaare brauchen wir eine Metastruktur. Dafür fassen wir einfach geordnete Paare in einer Klasse zusammen. Das Kartesische Produkt ┌ │ Kartesisch oder kartesianisch nach der lateinischen Namensform C a r t e s i u s des Philosophen und Mathematikers R .  D e s c a r t e s . └ , auch K r e u z p r o d u k t genannt, ist die Klasse aller geordneter Paare, deren Elemente aus den Ausgangsklassen stammen. ☉ Definition 18 (Kartesisches Produkt) [definition:cartesianProduct] ( x × y) = { z | ∃ u ∃ v (u ∈ x ∧ v ∈ y ∧ z = 〈 u, v 〉) } 3.4 Relationen ―――――――――――――― Es ist wichtig, Relationen zwischen mathematischen Objekten ausdrücken zu können und sie auch als Objekte behandeln zu können. Es stellt sich heraus, dass wir keine neuen Objektarten benötigen. Unsere bisherigen Strukturen reichen aus. Nun können wir den Begriff der R e l a t i o n auch innerhalb unserer Mengenlehre definieren. ☉ Definition 19 (Relation) [definition:relation] ℛℯℓ(x) ↔ ∀ y (y ∈ x → isOrderedPair(y)) Ein paar Aussagen über Relationen. ☉ Proposition 54 [theorem:relationProperties] (a) ℛℯℓ(∅) (b) ℛℯℓ(( Ʋ × Ʋ)) (c) (ℛℯℓ(x) ∧ ℛℯℓ(y)) → ℛℯℓ((x ∩ y)) (d) (ℛℯℓ(x) ∧ ℛℯℓ(y)) → ℛℯℓ((x ∪ y)) Wie geben nun eine allgemeine Definition des Begriffs D e f i n i t i o n s b e r e i c h an. ☉ Definition 20 (Definitionsbereich) [definition:domain] Dℴm(x) = { y | ∃ z 〈 y, z 〉 ∈ x } Analog zu dem Definitionsbereich legen wir den W e r t e b e r e i c h einer Klasse fest. ☉ Definition 21 (Wertebereich) [definition:range] ℛnℊ(x) = { y | ∃ z 〈 z, y 〉 ∈ x } 3.5 Relationenalgebra ――――――――――――――――――――― MISSING! OTHER: +++ 3.6 Äquivalenzrelationen ―――――――――――――――――――――――― MISSING! OTHER: +++ 3.7 Abbildungen und Funktionen ―――――――――――――――――――――――――――――― MISSING! OTHER: +++ Eine Funktion ist einfach eine spezielle Art von Relation. ☉ Definition 22 (Funktion) [definition:function] ℱunct(x) ↔ (ℛℯℓ(x) ∧ ∀ y (y ∈ Dℴm(x) → ∃! z 〈 y, z 〉 ∈ x)) Falls der Definitionsbereich einer Funktion eine Menge ist, dann sollte auch ihr Wertebereich eine Menge sein. ☉ Axiom 9 (Fraenkelsches Ersetzungsaxiom) [axiom:FraenkelsReplacement] (ℱunct(f) ∧ ℳ(Dℴm(f))) → ℳ(ℛnℊ(f)) ___________________________________________________ Kapitel 4 Natürliche Zahlen ═════════════════ MISSING! OTHER: +++ 4.1 Fundierung und Unendlichkeit ―――――――――――――――――――――――――――――――― MISSING! OTHER: +++ Mengen x sollten sich nicht selbst als Element enthalten oder ein Element besitzen, das wiederum x als Element hat. Um diese und andere Enthaltenseinszirkel auszuschließen, stellen wir das folgende Axiom vor. ☉ Axiom 10 (Fundierungsaxiom) [axiom:foundation] x ≠ ∅ → ∃ y (y ∈ x ∧ (y ∩ x) = ∅) Dieses Axiom heißt auch Regularitätsaxiom. Eine naheliegende Klassenerweiterung ist die Bildung der Vereinigungsmenge mit der Einerklasse. ☉ Definition 23 (Nachfolger) [definition:successor] x’ = (x ∪ { x }) Weil x ∉ x fügt die Nachfolgerfunktion der orginalen Klasse genau ein Element hinzu. Wir wollen eine Menge mit unendlich vielen Elementen haben. So fordern wir einfach ihre Existenz. ☉ Axiom 11 (Unendlichkeitsaxiom) [axiom:infinity] ∃ x (ℳ(x) ∧ ∅ ∈ x ∧ ∀ y (y ∈ x → y’ ∈ x)) 4.2 Definition und Grundeigenschaften ――――――――――――――――――――――――――――――――――――― MISSING! OTHER: +++ 4.3 Induktion ――――――――――――― MISSING! OTHER: +++ 4.4 Folgen und normale Funktionen ――――――――――――――――――――――――――――――――― MISSING! OTHER: +++ 4.5 Rekursion ――――――――――――― MISSING! OTHER: +++ ___________________________________________________ Kapitel 5 Auswahlaxiom ════════════ +++ 5.1 Wohlordnungen ――――――――――――――――― +++ Nun kommen wir zu dem bekannten Auswahlaxiom. Wir formulieren es für Relationen. ☉ Axiom 12 (Auswahlaxiom) [axiom:choice] ℛℯℓ(x) → ∃ y (ℱunct(y) → (y ⊆ x ∧ Dℴm(x) = Dℴm(y))) 5.2 Anwendungen des Auswahlaxioms ――――――――――――――――――――――――――――――――― MISSING! ___________________________________________________ Kapitel 6 Kontinuum ═════════ ___________________________________________________ Literaturverzeichnis ════════════════════ Benutzte andere QEDEQ-Module: [l] qedeq_logic_v1 http://www.qedeq.org/0_04_04/doc/math/qedeq_logic_v1.xml Andere Referenzen: [lemmon] E . J . L e m m o n , Introduction to Axiomatic Set Theory, Routledge & Kegan Paul Ltd, London 1968 [monk] J . D . M o n k , Introduction to Set Theory, McGraw-Hill, New York 1996 [schmidt] J . S c h m i d t , Mengenlehre I, BI, Mannheim 1966