Ersetzungsaxiom

Das Ersetzungsaxiom ist ein Axiom, das Abraham Fraenkel 1921 als Ergänzung zur Zermelo-Mengenlehre von 1907 vorschlug und später ein fester Bestandteil der Zermelo-Fraenkel-Mengenlehre (ZF) wurde.^[1] Es besagt informell, dass die Bilder von Mengen ebenfalls Mengen sind.

Durch das Ersetzungsschema kann man zum Beispiel die Elemente der Menge der natürlichen Zahlen

${\displaystyle \{0,1,2,\ldots \}}$,

deren Existenz nach dem Unendlichkeitsaxiom gegeben ist, „ersetzen“ durch

${\displaystyle \{\omega ,\omega +1,\omega +2,\ldots \}}$,

wobei ${\displaystyle \omega }$ die kleinste Ordinalzahl ist und wir eine Funktion (bzw. einen funktionalen Ausdruck) der Form ${\displaystyle x\mapsto \omega +x}$ benutzten. In der prädikatenlogischen Sprache wird das Ersetzungsaxiom präzisiert als Axiomenschema, das unendlich viele Axiome umfasst. Daher wird es heute auch oft als Ersetzungsschema bezeichnet.

In den heute üblichen Formulierungen innerhalb der Prädikatenlogik lautet es als Schema wie folgt: Für jedes Prädikat ${\displaystyle E(x,y)}$, in dem die Variable ${\displaystyle M}$ nicht vorkommt, ergibt das Schema das Axiom

${\displaystyle \forall x,y,z\colon (E(x,y)\land E(x,z)\Rightarrow y=z)\Rightarrow \forall A\colon \exists M\colon \forall y\colon (y\in M\iff \exists x\colon (x\in A\land E(x,y)))}$.

Alle Axiome dieser Form sind Axiome der Zermelo-Fraenkel-Mengenlehre. Die Bedingung ${\displaystyle E(x,y)\land E(x,z)\Rightarrow y=z}$ im Axiom besagt, dass das zweistellige Prädikat ${\displaystyle E(x,y)}$ rechtseindeutig (funktional) ist, das heißt, zu jedem ${\displaystyle x}$ gibt es höchstens ein ${\displaystyle y}$ mit ${\displaystyle E(x,y)}$. Der Teilausdruck ${\displaystyle \forall y\colon (y\in M\iff \exists x\colon (x\in A\land E(x,y)))}$ formalisiert, dass ${\displaystyle M}$ das Bild von ${\displaystyle A}$ unter ${\displaystyle E}$ ist.

Die Menge ${\displaystyle M}$, deren Existenz das Ersetzungsaxiom garantiert, ist aufgrund des Extensionalitätsaxioms eindeutig bestimmt.

Die Existenz einer Menge der Form ${\displaystyle \{\mathbb {N} ,{\mathcal {P}}(\mathbb {N} ),{\mathcal {P}}({\mathcal {P}}(\mathbb {N} )),\ldots \}}$ lässt sich in der Zermelo-Mengenlehre nicht beweisen, wie Fraenkel in seiner Veröffentlichung von 1921 bemerkte. Dies gilt auch dann, wenn man Fundierungsaxiom und Auswahlaxiom hinzunimmt. Ebenso wenig lässt sich die Existenz einer Menge größer als jedes ${\displaystyle {\mathcal {P}}^{n}(\mathbb {N} )}$ mit ${\displaystyle n\in \mathbb {N} }$ beweisen (also die Existenz einer Menge mindestens der Mächtigkeit ${\displaystyle \beth _{\omega }}$, siehe Beth-Funktion), und schon die Existenz einer Ordinalzahl ${\displaystyle \omega +\omega }$ (das heißt einer Menge ${\displaystyle \{0,1,2,\ldots ,\mathbb {N} ,\mathbb {N} \cup \{\mathbb {N} \},\mathbb {N} \cup \{\mathbb {N} \cup \{\mathbb {N} \}\},\ldots \}}$) lässt sich nicht zeigen. Dies folgt daraus, dass ${\displaystyle V_{\omega +\omega }}$ in ZFC ein Modell der Zermelo-Mengenlehre mit Fundierungsaxiom und Auswahlaxiom ist (Skolem bemerkte dies 1922^[2]). In diesem Modell ist die Kardinalität jeder Menge durch ein ${\displaystyle \beth _{n}}$ mit ${\displaystyle n\in \mathbb {N} }$ beschränkt, jede Ordinalzahl der Form ${\displaystyle n}$ oder ${\displaystyle \omega +n}$ mit ${\displaystyle n\in \mathbb {N} }$.

Das Ersetzungsaxiom erlaubt die Konstruktion all dieser „großen Mengen“.

Erlaubt man, wie in der obigen Formulierung, dass ${\displaystyle E}$ nicht alle Mengen auf eine weitere abbilden muss, ergibt sich aus dem Ersetzungsschema direkt das Aussonderungsschema: Jede Menge ${\displaystyle \{x\in A\mid P(x)\}}$ für ein Prädikat ${\displaystyle P}$ ist gerade das Bild von ${\displaystyle A}$ unter dem Prädikat ${\displaystyle E(x,y)\colon \Leftrightarrow y=x\wedge P(x)}$.

Das Ersetzungsaxiom erlaubt es, das Prinzip der transfiniten Rekursion zu beweisen. In ZFC ohne das Ersetzungsaxiom ist dieses Prinzip äquivalent zum Ersetzungsaxiom. Transfinite Rekursion erlaubt direkt die Konstruktion der Ordinalzahlarithmetik, der Aleph-Funktion, der Beth-Funktion und der Von-Neumann-Hierarchie sowie den Beweis, dass jede Wohlordnung isomorph zu einer Ordinalzahl ist.^[3]

Azriel Levy zeigte 1960 die Äquivalenz des Ersetzungsaxioms zum Levy-Montague-Reflexionsprinzip unter Voraussetzung der übrigen Axiome. Dies erübrigt das Ersetzungsaxiom im Scottschen Axiomensystem. Dieses zeigt auch, dass endlich viele Instanzen des Axiomenschemas nicht ausreichen, um ZF zu axiomatisieren: Für jede solche endliche Menge von Axiomen findet sich ein ${\displaystyle V_{\alpha }}$, das Modell von Z mit Fundierungsaxiom und dieser endlichen Menge ist. Insbesondere lässt sich die Widerspruchsfreiheit von ZFC nicht aus der Widerspruchsfreiheit irgendeiner Teilmenge der ZFC-Axiome mit nur endlich vielen Instanzen des Ersetzungsschemas ableiten.

Die Bedeutung des Ersetzungsaxioms außerhalb der Mengenlehre wird mitunter infrage gestellt.^[4] Es wird nicht für jegliche Bildung einer Bildmenge benötigt: Ist bekannt, dass ${\displaystyle \{(x,y)\mid E(x,y)\}}$ oder ${\displaystyle \{y\mid \exists xE(x,y)\}}$ eine Menge ist (wie es etwa der Fall ist, wenn ${\displaystyle E}$ als Funktion von einer Menge in eine andere gegeben ist), so genügt das Aussonderungsaxiom, um das Bild von ${\displaystyle E}$ als Menge zu bilden.

Die Mengenlehre, die Nicolas Bourbaki 1949 zur Grundlegung der gesamten Mathematik in einem Aufsatz vorschlug und die als Teilsystem der Zermelo-Mengenlehre mit Auswahlaxiom gesehen werden kann, verzichtet auf das Ersetzungsaxiom. Der 1954 erstmals (und dann überarbeitet 1970) erschienene Teil des Bandes Théorie des ensembles zur Begründung der Élements de mathématique enthielt dann eine Variante des Ersetzungsaxioms, genannt « schéma de sélection et réunion » (deutsch: „Schema der Aussonderung und Vereinigung“). Unter Verwendung der hier gewählten Formelzeichen lautet die Variante so, dass von ${\displaystyle E}$ nicht angenommen wird, dass es funktional ist, sondern nur, dass für jedes ${\displaystyle x}$ eine Menge aller ${\displaystyle y}$ mit ${\displaystyle E(x,y)}$ existiert.^[5][6][7][8] Auch die kategorientheoretische Axiomatisierung der Mengenlehre über eine Elementary theory of the category of sets verzichtet auf ein dem Ersetzungsaxiom entsprechendes Prinzip, während das System gleichwertig zu ZFC ohne das Ersetzungsaxiom ist.^[9][10]

Ein Beispiel für einen Satz mit direkten Berührungspunkten zu anderen Teilgebieten der Mathematik, der sich in der Zermelo-Mengenlehre (auch mit Fundierungs- und Auswahlaxiom) nicht beweisen lässt, ist die Borel-Determiniertheit (das heißt, dass in gewissen Spielen, deren Gewinnbedingung eine Borel-Menge ist, stets ein Spieler eine Gewinnstrategie besitzt).^[11] Der Beweis der Borel-Determiniertheit in ZFC erfolgt per Rekursion über die Borel-Hierarchie.

Zwar baut die moderne Theorie der Ordinalzahlen und der Kardinalzahlen, die nach John von Neumann als bestimmte durch die Elementrelation geordnete Mengen definiert werden, auf dem Ersetzungsaxiom auf, Teile der Ordinalzahlarithmetik beispielsweise lassen sich jedoch auch ohne Ersetzungsaxiom rekonstruieren, wenn man Ordinalzahlen als Isomorphieklassen von Wohlordnungen auffasst. Die Ordinalzahl ${\displaystyle \omega +\omega }$ ergibt sich dann beispielsweise als ordnungstheoretische Summe von zwei Wohlordnungen (anschaulich gesprochen durch „Aneinanderhängen“). Ein globales Auswahlaxiom erlaubt die Wahl eines kanonischen Repräsentanten für jede Ordinalzahl.

In der Neumann-Bernays-Gödel-Mengenlehre wird das Ersetzungsaxiom als ein Axiom formuliert, in dem über eine Klasse ${\displaystyle E}$ quantifiziert wird, anstatt für ${\displaystyle E}$ Prädikate einzusetzen. In der Formulierung von John von Neumann von 1925 folgt dieses Axiom neben anderen aus der limitation of size, oder spezieller daraus, dass eine Klasse genau dann echt ist, wenn eine Surjektion auf die Allklasse existiert.^[12] Analoges gilt für die stärkere Morse-Kelley-Mengenlehre.

Die Elementary theory of the category of sets (ETCS) lässt sich um ein Pendant des Ersetzungsaxioms erweitern, sodass in der resultierenden Theorie ZFC interpretierbar wird und umgekehrt. Eine Möglichkeit lautet wie folgt: Für jede prädikatenlogische Formel ${\displaystyle R(x,Y)}$ (über Morphismen ${\displaystyle x}$ und Objekte ${\displaystyle Y}$) ist die folgende Aussage ein Axiom: Ist ${\displaystyle A}$ ein Objekt, sodass für alle Elemente ${\displaystyle x\colon 1\to A}$ bis auf Isomorphie genau ein Objekt ${\displaystyle S_{x}}$ existiert mit ${\displaystyle R(x,S_{x})}$, so existiert ein Objekt ${\displaystyle S}$ und ein Morphismus ${\displaystyle f\colon S\to A}$, sodass für alle Elemente ${\displaystyle x\colon 1\to A}$ ${\displaystyle S_{x}}$ die Faser von ${\displaystyle x}$ unter ${\displaystyle f}$ („${\displaystyle f^{-1}(\{x\})}$“, kategorientheoretisch formulierbar als Pullback) ist.^[13]

Eine frühere Formulierung findet sich in einem Aufsatz von Gerhard Osius aus dem Jahr 1973, auf William Lawveres 1964 veröffentlichte Einführung der ETCS verweisend.^[14]

Georg Cantor schrieb 1899 an Richard Dedekind:

In moderner (klassentheoretischer) Sprache formuliert: Existiert eine Bijektion zwischen zwei Klassen, so sind entweder beide Mengen oder beide echte Klassen. Colin McLarty zieht diese Forderung als Motivation seiner kategorialen Formulierung des Ersetzungsaxioms heran. Cantors Forderung lässt sich laut McLarty dahingehend vereinfachen, dass eine Klasse, die Bild einer Menge ist, auch eine Menge ist.^[13]

Fraenkel formulierte 1921 das Axiom wie folgt:

Er sah in der Unmöglichkeit, etwa die oben genannte Menge ${\displaystyle \{\mathbb {N} ,{\mathcal {P}}(\mathbb {N} ),{\mathcal {P}}({\mathcal {P}}(\mathbb {N} )),\ldots \}}$ zu konstruieren, eine Unzulänglichkeit der Zermelo-Mengenlehre zur Begründung der Cantorschen Mengenlehre.^[1]

Thoralf Skolem bestätigte diese Unmöglichkeit und gab 1922 eine Formulierung als Axiomenschema. In seiner Formulierung wird auch nicht mehr gefordert, dass das Prädikat jede Menge auf eine weitere abbildet.^[16]

In Zermelos Formulierung der Zermelo-Fraenkel-Mengenlehre von 1930 lautete das Ersetzungsaxiom:

Er bemerkte auch, dass aus dem Ersetzungsaxiom das Aussonderungsaxiom und das Paarmengenaxiom ableitbar sind.^[17][18][19]

Von Neumann nannte das Axiom auch Axiom von Fraenkel.^[20]

• Akihiro Kanamori: In Praise of Replacement. In: The Bulletin of Symbolic Logic. Band 18, Nr. 1. Association for Symbolic Logic, März 2012. 

1. ↑ ^{a b c} Abraham Fraenkel: Zu den Grundlagen der Cantor-Zermeloschen Mengenlehre. (1921).Abraham Fraenkel: Zu den Grundlagen der Cantor-Zermeloschen Mengenlehre. In: Mathematische Annalen. Band 86, 1922, S. 230–237. Abgerufen am 8. Mai 2023. 
2. ↑ Kanamori, S. 61.
3. ↑ Joel David Hamkins: Transfinite recursion as a fundamental principle in set theory. 20. Oktober 2014, abgerufen am 23. Dezember 2014. 
4. ↑ Kanamori, S. 46.
5. ↑ Adrian Mathias: Unordered pairs in the set theory of Bourbaki 1949. In: Archiv der Mathematik. Band 94, Nr. 1. Springer, 2010, S. 1–10, doi:10.1007/s00013-009-0006-7 (online [PDF; 194 kB; abgerufen am 23. August 2021]). 
6. ↑ Maribel Anacona, Luis Carlos Arboleda, F. Javier Pérez-Fernández: On Bourbaki’s axiomatic system for set theory. In: Synthese. Band 191. Springer, 2014, S. 4078, doi:10.1007/s11229-014-0515-1. 
7. ↑ Nicolas Bourbaki: Théorie des ensembles (= Eléments de mathématique). Herman, Paris 1954, Kapitel 2, S. 64. 
8. ↑ Nicolas Bourbaki: Théorie des ensembles (= Eléments de mathématique). Diffusion, Paris 1977, ISBN 2-225-81909-2, Théorie des ensembles, S. 4 (französisch). 
9. ↑ axiom of replacement, Eintrag im nLab. (englisch)
10. ↑ Saunders Mac Lane, Ieke Moerdijk: Sheaves in Geometry and Logic. Springer, 1992, ISBN 0-387-97710-4, S. 335. 
11. ↑ Harvey Friedman: Higher set theory and mathematical practice. In: Annals of Mathematical Logic. Band 2, Nr. 3, 1971, S. 325–357, doi:10.1016/0003-4843(71)90018-0. 
12. ↑ Kanamori, S. 64.
13. ↑ ^{a b} Colin McLarty: Exploring Categorical Structuralism. In: Philosophia Mathematica. Band 12, Nr. 1. Oxford University Press, 2004, S. 48, doi:10.1093/philmat/12.1.37. 
14. ↑ Gerhard Osius: Categorial Set Theory: A Characterization of the Category of Sets. In: Journal of Pure and Applied Algebra. Band 4, Nr. 1. North-Holland, 1974, S. 116, doi:10.1016/0022-4049(74)90032-2. 
15. ↑ Georg Cantor: Gesammelte Abhandlungen mathematischen und philosophischen Inhalts. Hrsg.: Ernst Zermelo. Springer, 1932, ISBN 978-3-642-30416-3, Aus dem Briefwechsel zwischen Cantor und Dedekind, S. 444. 
16. ↑ Thoralf Skolem: Einige Bemerkungen zur axiomatischen Begründung der Mengenlehre. In: Wissenschaftliche Vorträge, gehalten auf dem 5. Kongress der skandinavischen Mathematiker in Helsingfors vom 4. bis 7. Juli 1922. 1923, ZDB-ID 771194-3, S. 217–232.
17. ↑ Ernst Zermelo: Grenzzahlen und Mengenbereiche, Fundamenta Mathematicae 16 (1930), Bemerkung S. 31
18. ↑ Walter Felscher: Naive Mengen und abstrakte Zahlen I, Mannheim, Wien, Zürich, 1978, S. 62.
19. ↑ Wolfgang Rautenberg: Grundkurs Mengenlehre. (PDF; 1,0 MB) Fassung Berlin 2008, S. 26
20. ↑ Kanamori, S. 62.