View source for Axiom schema of replacement

{{short description|Concept in set theory}}
{{more footnotes|date=March 2013}}
In [[set theory]], the '''axiom schema of replacement''' is a [[Axiom schema|schema]] of [[axiom]]s in [[Zermelo–Fraenkel set theory]] (ZF) that asserts that the [[image (mathematics)|image]] of any [[Set (mathematics)|set]] under any definable [[functional predicate|mapping]] is also a set. It is necessary for the construction of certain infinite sets in ZF.

The axiom schema is motivated by the idea that whether a [[class (set theory)|class]] is a set depends only on the [[cardinality]] of the class, not on the [[rank (set theory)|rank]] of its elements. Thus, if one class is "small enough" to be a set, and there is a [[surjection]] from that class to a second class, the axiom states that the second class is also a set. However, because [[ZFC]] only speaks of sets, not proper classes, the schema is stated only for definable surjections, which are identified with their defining [[Well-formed formula|formulas]].

== Statement ==
[[File:Axiom schema of replacement.svg|thumb|Axiom schema of replacement: the image <math>F[A]</math> of the domain set <math>A</math> under the definable class function <math>F</math> is itself a set, <math>B</math>.]]
Suppose <math>P</math> is a definable [[binary relation]] (which may be a [[proper class]]) such that for every set <math>x</math> there is a unique set <math>y</math> such that <math>P(x,y)</math> holds. There is a corresponding definable function <math>F_P</math>, where <math>F_P(x)=y</math> [[if and only if]] <math>P(x,y)</math>. Consider the (possibly proper) class <math>B</math> defined such that for every set <math>y</math>, <math>y\in B</math> if and only if there is an <math>x\in A</math> with <math>F_P(x)=y</math>. <math>B</math> is called the image of <math>A</math> under <math>F_P</math>, and denoted <math>F_P[A]</math> or (using [[set-builder notation]]) <math>\{F_P(x):x\in A\}</math>.

The '''axiom schema of replacement''' states that if <math>F</math> is a definable class function, as above, and <math>A</math> is any set, then the image <math>F[A]</math> is also a set. This can be seen as a principle of smallness: the axiom states that if <math>A</math> is small enough to be a set, then <math>F[A]</math> is also small enough to be a set. It is implied by the stronger [[axiom of limitation of size]].

Because it is impossible to quantify over definable functions in first-order logic, one instance of the schema is included for each formula <math>\phi</math> in the language of set theory with free variables among <math>w_1,\dotsc,w_n,A,x,y</math>; but <math>B</math> is not free in <math>\phi</math>. In the formal language of set theory, the axiom schema is:
:<math>\begin{align}
\forall w_1,\ldots,w_n \, \forall A \, ( [ \forall x \in A &\, \exists ! y \, \phi(x, y, w_1, \ldots, w_n, A) ]\ \Longrightarrow\ \exists B \, \forall y \, [y \in B \Leftrightarrow \exists x \in A \, \phi(x, y, w_1, \ldots, w_n, A) ] )
\end{align}</math>

For the meaning of <math>\exists!</math>, see [[uniqueness quantification]].

For clarity, in the case of no variables <math>w_i</math>, this simplifies to:
:<math>\begin{align}
\forall A \, ( [ \forall x \in A &\, \exists ! y \, \phi(x, y, A) ]\ \Longrightarrow\ \exists B \, \forall y \, [y \in B \Leftrightarrow \exists x \in A \, \phi(x, y, A) ] )
\end{align}</math>

So whenever <math>\phi</math> specifies a unique <math>x</math>-to-<math>y</math> correspondence, akin to a function <math>F</math> on <math>A</math>, then all <math>y</math> reached this way can be collected into a set <math>B</math>, akin to <math>F[A]</math>.

== Applications ==
The axiom schema of replacement is not necessary for the proofs of most theorems of ordinary mathematics. Indeed, [[Zermelo set theory]] (Z) already can interpret [[second-order arithmetic]] and much of [[type theory]] in finite types, which in turn are sufficient to formalize the bulk of mathematics. Although the axiom schema of replacement is a standard axiom in set theory today, it is often omitted from systems of [[type theory]] and foundation systems in [[topos]] theory.

At any rate, the axiom schema drastically increases the strength of ZF, both in terms of the theorems it can prove—for example the sets shown to exist—and also in terms of its [[proof-theoretic]] consistency strength, compared to Z. Some important examples follow:

* Using the modern definition due to [[John von Neumann|von Neumann]], proving the existence of any [[limit ordinal]] greater than <math>\omega</math> requires the replacement axiom. The [[ordinal number]] <math>\omega+\omega</math> is the first such ordinal. Indeed, the [[axiom of infinity]] asserts the existence of an infinite set <math>\omega=\{0,1,2,\dots\}</math>. One may hope to define <math>\omega+\omega</math> as the union of the sequence <math>\{\omega,\omega+1,\omega+2,\dots\}</math>. However, arbitrary such [[class (set theory)|classes]] of ordinals need not be sets; for example, the class of all ordinals is not a set. Replacement now allows one to replace each finite number <math>n</math> in <math>\omega</math> with the corresponding <math>\omega+n</math>, and thus guarantees that this class is a set. As a clarification, note that one can easily construct a [[well-ordered set]] that is isomorphic to <math>\omega+\omega</math> without resorting to replacement: simply take the [[disjoint union]] of two copies of <math>\omega</math>, with the second copy greater than the first; however, that is not an ordinal since it is not totally ordered by inclusion.

* Larger ordinals rely on replacement less directly. For example, <math>\omega_1</math>, the [[first uncountable ordinal]], can be constructed as follows: the set of countable well orders exists as a subset of <math>P({\mathbb N}\times {\mathbb N})</math> by the axioms of [[axiom of separation|separation]] and [[axiom of power set|power set]] (a [[binary relation|relation]] on <math>A</math> is a subset of <math>A\times A</math>, and so an element of <math>P(A\times A)</math>. A set of relations is thus a subset of <math>P(A\times A)</math>). Replace each well-ordered set with its ordinal. This is the set of countable ordinals <math>\omega_1</math>, which can itself be shown to be uncountable. The construction uses replacement twice; once to ensure an ordinal assignment for each well ordered set and again to replace well ordered sets by their ordinals. This is a special case of the result of [[Hartogs number]], and the general case can be proved similarly.

* In light of the above, the existence of an assignment of an ordinal to every well-ordered set requires replacement as well. Similarly the [[von Neumann cardinal assignment]] which assigns a [[cardinal number]] to each set requires replacement, as well as [[axiom of choice]].

* For sets of tuples recursively defined as <math>A^n=A^{n-1}\times A</math> and for large <math>A</math>, the set <math>\{A^n\mid n\in {\mathbb N}\}</math> has too high of a rank for its existence to be provable from set theory with just the axiom of power set, choice and without replacement.

* Similarly, [[Harvey Friedman (mathematician)|Harvey Friedman]] showed that at least some instances of replacement are required to show that [[Borel set|Borel games]] are [[determinacy|determined]]. The proven result is [[Donald A. Martin]]'s [[Borel determinacy theorem]]. A later, more careful analysis by Martin of the result showed that it only requires replacement for functions with domain an arbitrary countable [[ordinal number|ordinal]].

* ZF with replacement proves the [[consistency]] of Z, as the set <math>V_{\omega+\omega}</math> is a [[model (logic)|model]] of Z whose existence can be proved in ZF. The [[cardinal number]] <math>\aleph_\omega</math> is the first one which can be shown to exist in ZF but not in Z. For clarification, note that [[Gödel's second incompleteness theorem]] shows that each of these theories contains a sentence, "expressing" the theory's own consistency, that is unprovable in that theory, if that theory is consistent - this result is often loosely expressed as the claim that neither of these theories can prove its own consistency, if it is consistent.

== Relation to other axiom schemas ==
=== Simplifications ===
Some simplifications may be made to the axiom schema of replacement to obtain different equivalent versions. [[Azriel Lévy]] showed that a version of replacement with parameters removed, i.e. the following schema, is equivalent to the original form. In particular the equivalence holds in the presence of the axioms of extensionality, pairing, union and powerset.<ref>A. Kanamori, "[https://math.bu.edu/people/aki/20.pdf In Praise of Replacement]", pp.74--75. Bulletin of Symbolic Logic vol. 18, no. 1 (2012). Accessed 22 August 2023.</ref>

: <math>\forall A \, ( [ \forall x \, \exists ! y \, \phi(x, y, A) ]\ \Longrightarrow\ \exists B \, \forall y \, [y \in B \Leftrightarrow \exists x \in A \, \phi(x, y, A) ] )</math>

=== Collection ===
[[File:Codomain2 A B.SVG|thumb|Axiom schema of collection: the image <math>f[A]</math> of the domain set <math>A</math> under the definable class function <math>f</math> falls inside a set <math>B</math>.]]
The '''axiom schema of collection''' is closely related to and frequently confused with the axiom schema of replacement. 
Over the remainder of the ZF axioms, it is equivalent to the axiom schema of replacement. The axiom of collection is stronger than replacement in the absence of the [[power set axiom]]<ref>{{cite arXiv|eprint=1110.2430 |last1=Gitman |first1=Victoria |author2=Joel David Hamkins |last3=Johnstone |first3=Thomas A. |title=What is the theory ZFC without power set? |date=2011 |class=math.LO }}</ref> or its [[constructive set theory|constructive counterpart of ZF]] and is used in the framework of IZF, which lacks the [[law of excluded middle]], instead of Replacement which is weaker.<ref>{{cite journal | last1 = Friedman | first1 = Harvey M. | authorlink1=Harvey Friedman (mathematician) | last2 = Ščedrov | first2 = Andrej | title = The lack of definable witnesses and provably recursive functions in intuitionistic set theories | journal = [[Advances in Mathematics]] | volume = 57 | issue = 1 | pages = 1–13 | year = 1985 | issn = 0001-8708 | doi = 10.1016/0001-8708(85)90103-3 | doi-access = free }}</ref>

While replacement can be read to say that the image of a function is a set, collection speaks about images of relations and then merely says that some [[superset|superclass]] of the relation's image is a set. 
In other words, the resulting set <math>B</math> has no minimality requirement, i.e. this variant also lacks the uniqueness requirement on <math>\phi</math>. 
That is, the relation defined by <math>\phi</math> is not required to be a function—some <math>x\in A</math> may correspond to many <math>y</math>'s in <math>B</math>. In this case, the image set <math>B</math> whose existence is asserted must contain at least one such <math>y</math> for each <math>x</math> in the original set, with no guarantee that it will contain only one.

Suppose that the free variables of <math>\phi</math> are among <math>w_1,\dotsc,w_n,x,y</math>; but neither <math>A</math> nor <math>B</math> is free in <math>\phi</math>. Then the axiom schema is:
:<math>
\forall w_1,\ldots,w_n \,[(\forall x\, \exists\, y \phi(x, y, w_1, \ldots, w_n)) \Rightarrow \forall A\, \exists B\, \forall x \in A\, \exists y \in B\, \phi(x, y, w_1, \ldots, w_n)]
</math>

The axiom schema is sometimes stated without prior restrictions (apart from <math>B</math> not occurring free in <math>\phi</math>) on the predicate, <math>\phi</math>:
:<math>
\forall w_1,\ldots,w_n \, \forall A\, \exists B\,\forall x \in A\, [ \exists y \phi(x, y, w_1, \ldots, w_n) \Rightarrow \exists y \in B\,\phi(x, y, w_1, \ldots, w_n)]
</math>

In this case, there may be elements <math>x</math> in <math>A</math> that are not associated to any other sets by <math>\phi</math>. However, the axiom schema as stated requires that, if an element <math>x</math> of <math>A</math> is associated with at least one set <math>y</math>, then the image set <math>B</math> will contain at least one such <math>y</math>. The resulting axiom schema is also called the '''axiom schema of boundedness'''.

=== Separation ===
The [[axiom schema of separation]], the other axiom schema in ZFC, is implied by the axiom schema of replacement and the [[axiom of empty set]]. Recall that the axiom schema of separation includes
:<math>\forall A\, \exists B\, \forall C\, (C \in B \Leftrightarrow [C \in A \land \theta(C)])</math>
for each formula <math>\theta</math> in the language of set theory in which <math>B</math> is not free, i.e. <math>\theta</math> that does not mention <math>B</math>. 

The proof is as follows: Either <math>A</math> contains some element <math>a</math> validating <math>\theta(a)</math>, or it does not. In the latter case, taking the empty set for <math>B</math> fulfills the relevant instance of the axiom schema of separation and one is done. Otherwise, choose such a fixed <math>a</math> in <math>A</math> that validates <math>\theta(a)</math>. Now define <math>\phi(x, y):=(\theta(x)\land y=x)\lor(\neg\theta(x)\land y=a)</math> for use with replacement. Using function notation for this predicate <math>\phi</math>, it acts as the identity <math>F_a(x)=x</math> wherever <math>\theta(x)</math> is true and as the constant function <math>F_a(x)=a</math> wherever <math>\theta(x)</math> is false. By case analysis, the possible values <math>y</math> are unique for any <math>x</math>, meaning <math>F_a</math> indeed constitutes a class function. In turn, the image <math>B := \{F_a(x) : x\in A\}</math> of <math>A</math> under <math>F_a</math>, i.e. the class <math>A\cap\{x : \theta(x)\}</math>, is granted to be a set by the axiom of replacement. This <math>B</math> precisely validates the axiom of separation.

This result shows that it is possible to axiomatize ZFC with a single infinite axiom schema. Because at least one such infinite schema is required (ZFC is not finitely axiomatizable), this shows that the axiom schema of replacement can stand as the only infinite axiom schema in ZFC if desired. Because the axiom schema of separation is not independent, it is sometimes omitted from contemporary statements of the Zermelo-Fraenkel axioms.

Separation is still important, however, for use in fragments of ZFC, because of historical considerations, and for comparison with alternative axiomatizations of set theory. A formulation of set theory that does not include the axiom of replacement will likely include some form of the axiom of separation, to ensure that its models contain a sufficiently rich collection of sets. In the study of models of set theory, it is sometimes useful to consider models of ZFC without replacement, such as the models <math>V_\delta</math> in von Neumann's hierarchy.

The proof given above assumes the [[law of excluded middle]] for the proposition that <math>A</math> is [[Inhabited set|inhabited]] by a set validating <math>\theta</math>, and for any <math>\theta(x)</math> when stipulating that the relation <math>\phi</math> is functional. The axiom of separation is explicitly included in [[Constructive_set_theory#Separation|constructive set theory]], or a [[Axiom schema of predicative separation|bounded variant thereof]].

===Reflection===
{{main article|Reflection principle}}

Lévy's [[Reflection_principle#In_ZFC|reflection principle for ZFC]] is equivalent to the axiom of replacement, assuming the axiom of infinity. Lévy's principle is as follows:<ref>A. Kanamori, "[https://math.bu.edu/people/aki/20.pdf In Praise of Replacement]", p.73. Bulletin of Symbolic Logic vol. 18, no. 1 (2012). Accessed 22 August 2023.</ref>

: For any <math>x_1,\ldots,x_n</math> and any first-order formula <math>\phi(x_1,\ldots,x_n)</math>, there exists an <math>\alpha</math> such that <math>\phi(x_1,\ldots,x_n)\iff\phi^{V_\alpha}(x_1,\ldots,x_n)</math>.

This is a schema that consists of countably many statements, one for each formula <math>\phi</math>. Here, <math>\phi^M</math> means <math>\phi</math> with all quantifiers bounded to <math>M</math>, i.e. <math>\phi</math> but with every instance of <math>\exists x</math> and <math>\forall x</math> replaced with <math>\exists(x\in V_\alpha)</math> and <math>\forall(x\in V_\alpha)</math> respectively.

== History ==
The axiom schema of replacement was not part of [[Ernst Zermelo]]'s 1908 axiomatisation of set theory ('''Z'''). Some informal approximation to it existed in [[Georg Cantor|Cantor]]'s unpublished works, and it appeared again informally in [[Mirimanoff]] (1917).<ref>{{citation
 | last = Maddy | first = Penelope | author-link = Penelope Maddy
 | doi = 10.2307/2274520
 | jstor = 2274520
 | issue = 2
 | journal = [[Journal of Symbolic Logic]]
 | mr = 947855
 | pages = 481–511
 | quote =  Early hints of the Axiom of Replacement can be found in Cantor's letter to Dedekind [1899] and in Mirimanoff [1917]
 | title = Believing the axioms. I
 | volume = 53
 | year = 1988}}. Maddy cites two papers by Mirimanoff, "Les antinomies de Russell et de Burali-Forti et le problème fundamental de la théorie des ensembles" and "Remarques sur la théorie des ensembles et les antinomies Cantorienne", both in ''L'Enseignement Mathématique'' (1917).</ref>

[[File:Adolf Abraham Halevi Fraenkel.jpg|thumb|upright|alt=refer to caption|Abraham Fraenkel, between 1939 and 1949]] [[File:ThoralfSkolem-OB.F06426c.jpg|thumb|upright|alt=refer to caption|Thoralf Skolem, in the 1930s]]
Its publication by [[Abraham Fraenkel]] in 1922 is what makes modern set theory Zermelo-''Fraenkel'' set theory ('''ZFC'''). The axiom was independently discovered and announced by [[Thoralf Skolem]] later in the same year (and published in 1923). Zermelo himself incorporated Fraenkel's axiom in his revised system he published in 1930, which also included as a new axiom von Neumann's [[axiom of foundation]].<ref name="Ebbinghaus92">Ebbinghaus, p. 92.</ref> Although it is Skolem's first order version of the axiom list that we use today,<ref name="Ebbinghaus2"/> he usually gets no credit since each individual axiom was developed earlier by either Zermelo or Fraenkel. The phrase “Zermelo-Fraenkel set theory” was first used in print by von Neumann in 1928.<ref name="Ebbinghaus189">Ebbinghaus, p. 189.</ref>

Zermelo and Fraenkel had corresponded heavily in 1921; the axiom of replacement was a major topic of this exchange.<ref name="Ebbinghaus2">Ebbinghaus, pp. 135-138.</ref> Fraenkel initiated correspondence with Zermelo sometime in March 1921. However, his letters before the one dated 6 May 1921 are lost. Zermelo first admitted to a gap in his system in a reply to Fraenkel dated 9 May 1921. On 10 July 1921, Fraenkel completed and submitted for publication a paper (published in 1922) that described his axiom as allowing arbitrary replacements: "If ''M'' is a set and each element of ''M'' is replaced by [a set or an urelement] then ''M'' turns into a set again" (parenthetical completion and translation by Ebbinghaus). Fraenkel's 1922 publication thanked Zermelo for helpful arguments. Prior to this publication, Fraenkel publicly announced his new axiom at a meeting of the [[German Mathematical Society]] held in [[Jena]] on 22 September 1921. Zermelo was present at this meeting; in the discussion following Fraenkel's talk he accepted the axiom of replacement in general terms, but expressed reservations regarding its extent.<ref name="Ebbinghaus2"/>

Thoralf Skolem made public his discovery of the gap in Zermelo's system (the same gap that Fraenkel had found) in a talk he gave on 6 July 1922 at the 5th [[Congress of Scandinavian Mathematicians]], which was held in [[Helsinki]]; the proceedings of this congress were published in 1923. Skolem presented a resolution in terms of first-order definable replacements: "Let ''U'' be a definite proposition that holds for certain pairs (''a'', ''b'') in the domain ''B''; assume further, that for every ''a'' there exists at most one ''b'' such that ''U'' is true. Then, as ''a'' ranges over the elements of a set ''M<sub>a</sub>'', ''b'' ranges over all elements of a set ''M<sub>b</sub>''." In the same year, Fraenkel wrote a review of Skolem's paper, in which Fraenkel simply stated that Skolem's considerations correspond to his own.<ref name="Ebbinghaus2"/>

Zermelo himself never accepted Skolem's formulation of the axiom schema of replacement.<ref name="Ebbinghaus2"/> At one point he called Skolem's approach “set theory of the impoverished”. Zermelo envisaged a system that would allow for [[large cardinal]]s.<ref name="Ebbinghaus3">Ebbinghaus, p. 184.</ref> He also objected strongly to the philosophical implications of [[Skolem's paradox#Reception by the mathematical community|countable models of set theory]], which followed from Skolem's first-order axiomatization.<ref name="Ebbinghaus189"/> According to the biography of Zermelo by [[Heinz-Dieter Ebbinghaus]], Zermelo's disapproval of Skolem's approach marked the end of Zermelo's influence on the developments of set theory and logic.<ref name="Ebbinghaus2"/>

== References ==
*{{Citation |last=Ebbinghaus |first=Heinz-Dieter |title=Ernst Zermelo: An Approach to His Life and Work|year=2007|publisher=Springer Science & Business Media|isbn=978-3-540-49553-6}}.
*{{Citation|last=Halmos|first=Paul R.|author-link=Paul R. Halmos|orig-year=1960|year=1974|title=Naive Set Theory|publisher=Springer-Verlag|isbn=0-387-90092-6|url-access=registration|url=https://archive.org/details/naivesettheory0000halm_r4g0}}. 
*{{Citation |last=Jech|first=Thomas|author-link=Thomas Jech|year=2003|title=Set Theory: The Third Millennium Edition, Revised and Expanded|publisher=Springer|isbn=3-540-44085-2}}.
*{{Citation |first=Kenneth|last=Kunen|author-link=Kenneth Kunen|year=1980|title=Set Theory: An Introduction to Independence Proofs|publisher=Elsevier|isbn=0-444-86839-9}}.

===Citations===
{{Reflist}}

{{Set theory}}

[[Category:Axioms of set theory]]