0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ The axiom is used to prove that $E$ exists, granted that the existence of $\omega$ has already been proved. See Axiom schema of replacement. $\endgroup$ – Mauro ALLEGRANZA Jan 13 '18 at 18:33
  • $\begingroup$ How would you propose to prove $E$ is a set without Replacement? $\endgroup$ – Eric Wofsey Jan 13 '18 at 18:44
  • 1
    $\begingroup$ Relpacement works this way: consider a formula of the language $\phi(x,y)$ that is "functional", i.e. such that for every $a$ there is exactly one $b$ such that $\phi(a,b)$ holds, and consider a set $A$. Thus, for every $z \in A$ the formula $\phi$ "pick up" a corresponding $w$; thus we can consider the collection $B$ corresponding to $A$ by way of $\phi$. In a sense, we "replace" $A$ with its "image" $B$ produced bt $\phi$. The "image" $B$ exists (i.e. is a set) because the axiom holds. $\endgroup$ – Mauro ALLEGRANZA Jan 13 '18 at 19:09
  • $\begingroup$ @MauroALLEGRANZA this should be an answer, not a comment $\endgroup$ – Eddy Jan 13 '18 at 19:19
  • 1
    $\begingroup$ For each $n, f(n)= \omega +n$ is a set; but we have an infinite "union" of them, because $n$ ranges over $\omega$. $\endgroup$ – Mauro ALLEGRANZA Jan 13 '18 at 19:57
1
$\begingroup$

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)).$

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ Thanks for this clearest and viable answer. I have been thrown by the comment above that intimates this; yet was thrown by the : but we have an infinite union of them. Were it not for timing, I would have accepted this. With regards, $\endgroup$ – user12802 Jan 14 '18 at 20:23
  • $\begingroup$ @Andrew I am glad this helped you :). No worries, I do not ask for accepting this. I was on recommending to wait some hours (maybe even a day) before accepting an answer because a second opinion can never hurt, but I see you already asked this yesterday! So everything is fine! :) $\endgroup$ – M. Winter Jan 14 '18 at 20:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy