Understanding the Axiom of Replacement

2.3k Views Asked by At

This is from Devlin's "Joy of Sets," page 68, in a discussion that $\omega+\omega$ exists (using ZF axioms):

Let $f:\omega\rightarrow V$ be defined by $f(n)=\omega+n$.

By the Axiom of Replacement, the collection $E=\{f(n)|n\in\omega\}$ is a set.

Previously, the existence of $\omega$ was established.

I have several questions:

$1$) Wherein is the issue that Replacement is needed? $\omega$ was established and well as the natural numbers.

$2$) What is being replaced with what?

$3$) Is there a general rule regarding the use of Replacement along the lines such as when you have a 'collection' that is ...(maybe not seen as a set, e.g., too large), then... (here I really need help).

I have seen some instances where things are spelled out, but would like to be able to know when to and how to do things on my own.

Thanks

2

There are 2 best solutions below

0
On BEST ANSWER

We can see the SEP's entry on Set Theory, and sepcifically the Supplement listing the axioms of $\mathsf { ZF }$ :

The final axiom of $\mathsf {ZF}$ is the Replacement Schema. Suppose that $\phi(x,y,û)$ is a formula with $x$ and $y$ free, and let $û$ represent the variables $u_1,…,u_k$, which may or may not be free in $\phi$. Furthermore, let $\phi_{x,y,û}[s,r,û]$ be the result of substituting $s$ and $r$ for $x$ and $y$, respectively, in $\phi(x,y,û)$. Then every instance of the following schema is an axiom:

Replacement Schema:

$\forall u_1 …\forall u_k [\forall x \exists !y \phi(x,y,û) \rightarrow \forall w \exists v \forall r (r \in v \leftrightarrow \exists s(s \in w \land \phi_{x,y,û}[s,r,û]))]$

In other words, if we know that $\phi$ is a functional formula (which relates each set $x$ to a unique set $y$), then if we are given a set $w$, we can form a new set $v$ as follows: collect all of the sets to which the members of $w$ are uniquely related by $\phi$.

Note that the Replacement Schema can take you ‘out of’ the set $w$ when forming the set $v$. The elements of $v$ need not be elements of $w$. By contrast, the well-known Separation Schema of Zermelo yields new sets consisting only of those elements of a given set $w$ which satisfy a certain condition $\psi$.

In a nutshell, what we have to do is to define a formula $\phi(x,y)$ that corresponds to the function $f$ above :

$y = \omega + x$.

Then we have to prove that:

$ \text {if } \phi(x,y_1) \text { and } \phi(x,y_2), \text { then } y_1=y_2.$

Having done this, we use the Axiom schema to get:

$\exists E \ \forall y \ (y \in E \leftrightarrow \exists x \ (x \in \omega \land y=\omega+x)).$

2
On

My favorite (but not most rigorous) way to state the axiom of replacement is the following:

Let $\phi(x,y)$ be a functional formula (as explained by others already). For the sake of convenience, we do as if $\phi$ is a function, so we write $\phi(x)=y$ instead of $\phi(x,y)$, etc.

Axiom of Replacement: If $X$ is a set, so is its image $$\phi[X]:=\{\phi(x)\mid x\in X\}.$$


Application to your example

Since $\omega$ was shown to be a set, and $\phi(x,y)\equiv (y=\omega+x)$ is a valid functional formula (at least on ordinals), we have that $\phi[\omega]$ is a set too. Every $n\in\omega$ was replaced with $\phi(n)=\omega+n$.