Replacement (Set Theory)

Definition

The axiom schema of replacement states that the image of any set under a definable class function is itself a set. Formally, for each formula $\phi (x,y,\bar{p})$ in the language of set theory, the following is an axiom:

$\forall A.\forall \bar{p}.(\forall x\in A.\exists !y.\phi (x,y,\bar{p}))\to \exists B.\forall y.(y\in B⟺\exists x\in A.\phi (x,y,\bar{p})).$

That is: if $\phi$ defines a function $F$ on the set $A$ (each $x\in A$ is sent to a unique $y$), then the collection $F[A]=\{F(x)\mid x\in A\}$ is a set $B$.

The parameters $\bar{p}$ are any sets used as auxiliary inputs; one axiom instance is generated for each choice of formula $\phi$.

Motivation

Separation alone can only carve out subsets of an existing set. It cannot produce a set whose members are the outputs of a function applied to an existing set when those outputs are not already known to lie in some ambient set. Replacement fills this gap.

A concrete example: from the set $\omega =\mathbb{N}$, one would like to form the set $\{\omega ,\omega +\omega ,\omega +\omega +\omega ,\dots \}=\{\omega \cdot n\mid n\in \omega \}.$ None of these ordinals lie in $\omega$ itself, so separation cannot produce this collection. Replacement asserts it is a set because it is the image of $\omega$ under the definable function $n\mapsto \omega \cdot n$.

More generally, replacement is what allows transfinite constructions to produce sets at every stage: once one has a set $A$ and a function $F$ defined by a formula, $F[A]$ is guaranteed to exist as a set.

Role in ZF

Replacement is one of the most powerful axiom schemas in ZF. Together with the axiom of infinity, it allows the construction of:

• $V_{\omega +\omega }$ and higher levels of the cumulative hierarchy
• ordinal arithmetic: $\alpha +\beta$, $\alpha \cdot \beta$, ${\alpha }^{\beta }$ defined by transfinite recursion
• the set of all finite ordinals, of all countable ordinals, and so on
• ordinals $\omega +\omega$, ${\omega }^2$, ${\omega }^{\omega }$, ${\epsilon }_0$, …

Without replacement, the accessible universe is essentially $V_{\omega +\omega }$, which satisfies all of the other ZF axioms but fails replacement. This model is sometimes called Zermelo set theory (Z).

Transfinite Recursion

The primary application of replacement is justifying transfinite recursion: given an ordinal $\alpha$ and a rule $F$ computing the next value from all previous values, the sequence $(x_{\beta }{)}_{\beta <\alpha }$ defined by $x_{\beta }=F(⟨x_{\gamma }{⟩}_{\gamma <\beta })$ exists as a set. Each stage of the recursion is a set by replacement applied to the ordinal $\alpha$.

Relationship to Separation

The axiom schema of separation is a consequence of replacement in the presence of the other axioms of ZF: to separate $\{x\in A\mid \psi (x)\}$, apply replacement to the function $x\mapsto x$ restricted to those $x\in A$ satisfying $\psi$. Conversely, separation alone does not imply replacement.

In Class Theories

In NBG (von Neumann–Bernays–Gödel) set theory, replacement is a consequence of the class comprehension axioms: every definable class function $F$ (now a genuine object) may be applied to any set, and the image is a set. The finitely many axiom schemas of ZF replacement collapse to a single axiom about classes.

Related Concepts

• Comprehension
• Axiom of Infinity
• Ordinal
• Well-Ordering
• Set Theory
• Class (Set Theory)