Substitution axiom

The replacement axiom is an axiom that Abraham Fraenkel proposed in 1921 as a supplement to the Zermelo set theory of 1907 and which later became an integral part of the Zermelo-Fraenkel set theory ZF. It informally states that the images of sets are also sets. In the language of predicate logic, the substitution axiom is specified as an axiom scheme that includes an infinite number of axioms. Therefore, it is often referred to as the substitution scheme today.

formulation

In the formulations customary today within predicate logic, the schema is as follows: For every predicate in which the variable does not appear, the schema results in the axiom ${\displaystyle E(x,y)}$ ${\displaystyle M}$

${\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)))}$.

All axioms of this form are axioms of the Zermelo-Fraenkel set theory. The condition in the axiom says that the two-digit predicate is right unambiguous (functional), that is, for each there is at most one with . The partial expression formalizes that the picture is from below . ${\displaystyle E(x,y)\land E(x,z)\Rightarrow y=z}$ ${\displaystyle E(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle E(x,y)}$ ${\displaystyle \forall y\colon (y\in M\iff \exists x\colon (x\in A\land E(x,y)))}$ ${\displaystyle M}$ ${\displaystyle A}$ ${\displaystyle E}$

The set whose existence the replacement axiom guarantees is uniquely determined on the basis of the axiom of extensionality . ${\displaystyle M}$

Significance for the construction of "large quantities"

The existence of a set of the form cannot be proved in Zermelo set theory, as Fraenkel noted in his 1921 publication. This also applies if you add the axiom of foundation and axiom of choice. Neither can the existence of a set larger than each be proven with (i.e. the existence of a set of at least the power , see Beth function ), and even the existence of an ordinal number (i.e. a set ) cannot be shown. This follows from the fact that in ZFC there is a model of Zermelo set theory with a foundation axiom and a choice axiom (Skolem noted this in 1922). In this model the cardinality of any set is constrained by an with , any ordinal of the form or with . ${\displaystyle \{\mathbb {N} ,{\mathcal {P}}(\mathbb {N} ),{\mathcal {P}}({\mathcal {P}}(\mathbb {N} )),\ldots \}}$ ${\displaystyle {\mathcal {P}}^{n}(\mathbb {N} )}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle \beth _{\omega }}$ ${\displaystyle \omega +\omega }$ ${\displaystyle \{0,1,2,\ldots ,\mathbb {N} ,\mathbb {N} \cup \{\mathbb {N} \},\mathbb {N} \cup \{\mathbb {N} \cup \{\mathbb {N} \}\},\ldots \}}$ ${\displaystyle V_{\omega +\omega }}$ ${\displaystyle \beth _{n}}$ ${\displaystyle n\in \mathbb {N} }$ ${\displaystyle n}$ ${\displaystyle \omega +n}$ ${\displaystyle n\in \mathbb {N} }$

The substitution axiom allows the construction of all these "large sets".

Relationship to other axioms and equivalent principles

If you allow, as in the formulation above, that not all sets have to be mapped onto another, the replacement scheme results directly in the disposal scheme : Every set for a predicate is precisely the image of below the predicate . ${\displaystyle E}$ ${\displaystyle \{x\in A\mid P(x)\}}$ ${\displaystyle P}$ ${\displaystyle A}$ ${\displaystyle E(x,y)\colon \Leftrightarrow y=x\wedge P(x)}$

The replacement axiom allows to prove the principle of transfinite recursion . In ZFC without the replacement axiom, this principle is equivalent to the replacement axiom. Transfinite recursion directly allows the construction of the ordinal number arithmetic , the Aleph function , the Beth function and the Von Neumann hierarchy as well as the proof that every well-order is isomorphic to an ordinal number.

In 1960 Azriel Levy showed the equivalence of the substitution axiom to the Levy-Montague reflection principle , assuming the other axioms. This makes the replacement axiom in Scott's system of axioms superfluous . This also shows that finitely many instances of the axiom scheme are not sufficient to axiomatize ZF: For every such finite set of axioms there is a model of Z with a foundation axiom and this finite set. In particular, the leaves consistency of ZFC any subset of the ZFC axioms not be derived from the consistency with only a finite number of instances of the replacement scheme. ${\displaystyle V_{\alpha }}$

Importance in mathematics

The meaning of the substitution axiom outside of set theory is sometimes called into question. It is not needed for every formation of a set of images: If it is known that or is a set (as is the case, for example, if as a function of one set is given into another), the axiom of discarding is sufficient to express the image of as a set to build. ${\displaystyle \{(x,y)\mid E(x,y)\}}$ ${\displaystyle \{y\mid \exists xE(x,y)\}}$ ${\displaystyle E}$ ${\displaystyle E}$

Set theory, which Nicolas Bourbaki proposed in an essay in 1949 for the foundation of all mathematics and which can be seen as a subsystem of Zermelo set theory with axiom of choice, dispenses with the axiom of substitution. The part of the volume Théorie des ensembles to establish the Élements de mathématique , first published in 1954 (and then revised in 1970), then contained a variant of the substitution axiom, called “  schéma de sélection et réunion  ” (German: “scheme of segregation and association”). Using the selected symbols here the variant is such that from it is not believed that it is functional, but only that for each of all a lot to exist. The category-theoretical axiomatization of set theory via an elementary theory of the category of sets dispenses with a principle corresponding to the substitution axiom, while the system is equivalent to ZFC without the substitution axiom. ${\displaystyle E}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle E(x,y)}$

An example of a theorem with direct points of contact with other areas of mathematics, which cannot be proven in Zermelo set theory (even with the axiom of foundation and choice), is Borel determinacy (i.e. that in certain games, the winning condition of which is a Borel set is always a player has a winning strategy). The proof of the Borel determinacy in ZFC is done by recursion over the Borel hierarchy .

Although the modern theory of ordinal numbers and cardinal numbers, which according to John von Neumann are defined as certain sets ordered by the element relation, is based on the replacement axiom, parts of the ordinal number arithmetic, for example, can also be reconstructed without replacement axiom, if ordinal numbers are considered as isomorphism classes of well-orders understand. The ordinal number then results, for example, as the order-theoretical sum of two well-orders (clearly spoken by “connecting”). A global axiom of choice allows a canonical representative to be chosen for each ordinal number. ${\displaystyle \omega +\omega }$

The replacement axiom in set theory with real classes

In Neumann-Bernays-Gödel set theory , the replacement axiom is formulated as an axiom in which a class is quantified instead of substituting for predicates. In the formulation of John von Neumann from 1925, this axiom follows, among others, from the limitation of size , or more specifically from the fact that a class is real if and only if there is a surjection on the universal class . The same applies to the stronger Morse-Kelley set theory . ${\displaystyle E}$ ${\displaystyle E}$

Counterpart in categorical set theory

The elementary theory of the category of sets (ETCS) can be expanded to include a counterpart of the substitution axiom, so that ZFC can be interpreted in the resulting theory and vice versa. One possibility is as follows: For every predicate logic formula (about morphisms and objects ) the following statement is an axiom: If there is an object, so that exactly one object exists for all elements except for isomorphism with , then an object and a morphism exist , so that for all elements are the fibers of under (" ", can be formulated in terms of category theory as pullback ). ${\displaystyle R(x,Y)}$ ${\displaystyle x}$ ${\displaystyle Y}$ ${\displaystyle A}$ ${\displaystyle x\colon 1\to A}$ ${\displaystyle S_{x}}$ ${\displaystyle R(x,S_{x})}$ ${\displaystyle S}$ ${\displaystyle f\colon S\to A}$ ${\displaystyle x\colon 1\to A}$ ${\displaystyle S_{x}}$ ${\displaystyle x}$ ${\displaystyle f}$ ${\displaystyle f^{-1}(\{x\})}$

An earlier formulation can be found in an article by Gerhard Osius from 1973, referring to William Lawvere's 1964 introduction of the ETCS.

history

Georg Cantor wrote to Richard Dedekind in 1899 :

"Two equivalent multiplicities are either both 'sets' or both are inconsistent."

In modern (class-theoretical) language, if there is a bijection between two classes, either both sets or both are real classes. Colin McLarty uses this requirement as the motivation for his categorical formulation of the substitution axiom. According to McLarty, Cantor's requirement can be simplified to the effect that a class that is an image of a crowd is also a crowd.

In 1921 Fraenkel formulated the axiom as follows:

"If there is a set and every element of is replaced by a 'thing of the area ' [...], then again goes over into a set." ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle {\mathfrak {B}}}$ ${\displaystyle M}$

He saw the impossibility of constructing the set mentioned above as an inadequacy of Zermelo set theory to justify Cantor's set theory . ${\displaystyle \{\mathbb {N} ,{\mathcal {P}}(\mathbb {N} ),{\mathcal {P}}({\mathcal {P}}(\mathbb {N} )),\ldots \}}$

Thoralf Skolem confirmed this impossibility and in 1922 gave it a formulation as an axiom scheme. In its formulation, it is also no longer required that the predicate should map any quantity to another.

In Zermelo's formulation of the Zermelo-Fraenkel set theory from 1930, the substitution axiom was:

"If the elements of a set are clearly replaced by any elements of the area, then this also contains a set that has all of these elements." ${\displaystyle x}$ ${\displaystyle m}$ ${\displaystyle x'}$ ${\displaystyle m'}$ ${\displaystyle x'}$

He also noticed that the axiom of discarding and the axiom of pairs can be derived from the axiom of substitution .

Von Neumann also called the axiom von Fraenkel's axiom .

literature

• Akihiro Kanamori : In Praise of Replacement . In: The Bulletin of Symbolic Logic . tape 18 , no. 1 . Association for Symbolic Logic, March 2012.

Individual evidence

1. ↑ ^{a b c} Abraham Fraenkel : To the basics of Cantor-Zermeloschen set theory. (1921).  ( Page no longer available , search in web archives )  Info: The link was automatically marked as defective. Please check the link according to the instructions and then remove this notice.   In: Mathematical Annals . Volume 86, 1922, pp. 230-237.
2. ↑ Kanamori, p. 61.
3. ↑ Joel David Hamkins: transfinite recursion as a fundamental principle in set theory. October 20, 2014, accessed December 23, 2014 . 
4. ↑ Kanamori, p. 46.
5. ↑ Adrian Mathias: unordered pairs in the set theory of Bourbaki 1949 . In: Archives of Mathematics . tape 94 , no. 1 . Springer , 2010, p. 1–10 , doi : 10.1007 / s00013-009-0006-7 ( online (PDF)).
6. ↑ Maribel Anacona, Luis Carlos Arboleda, F. Javier Pérez-Fernández: On Bourbaki's axiomatic system for set theory . In: Synthesis . tape 191 . Springer, 2014, p. 4078 , doi : 10.1007 / s11229-014-0515-1 .
7. ^ Nicolas Bourbaki : Théorie des ensembles (=  Eléments de mathématique ). Herman, Paris 1954, chapter 2, p. 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, p. 4 (French).
9. ↑ axiom of replacement , entry in the nLab . (English)
10. ^ Saunders Mac Lane, Ieke Moerdijk: Sheaves in Geometry and Logic . Springer, 1992, ISBN 0-387-97710-4 , pp. 335 .
11. ^ Harvey Friedman: Higher set theory and mathematical practice . In: Annals of Mathematical Logic . tape 2 , no. 3 , 1971, p. 325-357 , doi : 10.1016 / 0003-4843 (71) 90018-0 .
12. ↑ Kanamori, p. 64.
13. ^ ^{A b} Colin McLarty: Exploring Categorical Structuralism . In: Philosophia Mathematica . tape 12 , no. 1 . Oxford University Press, 2004, pp. 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 . tape 4 , no. 1 . North-Holland, 1974, p. 116 , doi : 10.1016 / 0022-4049 (74) 90032-2 .
15. ↑ Georg Cantor: Collected treatises of mathematical and philosophical content . Ed .: Ernst Zermelo. Springer , 1932, ISBN 978-3-642-30416-3 , from the correspondence between Cantor and Dedekind, p. 444 .
16. ↑ Thoralf Skolem : Some remarks on the axiomatic justification of set theory. In: Scientific lectures, given at the 5th Congress of Scandinavian Mathematicians in Helsingfors from July 4 to 7, 1922. 1923, ZDB -ID 771194-3 , pp. 217–232.
17. ↑ Ernst Zermelo : limiting numbers and ranges of amounts , Fundamenta Mathematicae 16 (1930), Note 31 S.
18. ^ Walter Felscher : Naive sets and abstract numbers I, Mannheim, Vienna, Zurich, 1978, p. 62.
19. ↑ Wolfgang Rautenberg : Basic course set theory . (PDF; 1.0 MB) Version Berlin 2008, p. 26
20. ↑ Kanamori, p. 62.