# Proving Separation from Replacement

I'm trying to show that separation follows from replacement. There are at least two questions here on SE that deal with the question. See The comprehension axioms follows from the replacement schema. and How do the separation axioms follow from the replacement axioms?. I'm not completely satisfied with the answers there.

The basic idea for the proof that most people use seems to be this: Say we have some set $D$ and some formula $\varphi(x)$. To prove separation, we're trying to show that $\{x \in D| \varphi(x)\}$ is a set. Using separation, we need to write a formula $\psi(x,y)$ such that for each $x \in D$ there is exactly one $y$ such that $\psi(x,y)$.

Here's one attempt: $\psi(x,y) = \text{"}x = y \wedge \varphi(x) \text{''}$. IF this formula satisfies the separation axiom, THEN this should work fine. The problem: at least in the version of the separation axiom I know, we need for there to be a unique $y$ for all $x \in D$, such that $\psi(x,y)$. So say $x \in D$ is such that $\neg \varphi(x)$, then $\psi(x,y)$ is always false (and so not true for a unique $y$ as required for the use of replacement).

Here's another attempt: $\psi(x,y) = \text{''}(\{x\}=y \wedge \varphi(x))\vee y=\emptyset \text{''}.$ Now we have a function whose domain is the entire set $D$. And we can use replacement and union to get the set we want. But this requires that both $\emptyset$ and $\{x\}$ are sets. This is the usual argument that they are sets. $D$ is a set, so $\{x \in D| x \not = x\}=\emptyset$ is a set. But that's a straightforward use of separation. We have the same problem for $\{x\}$. Using pairing we get that there is a set $A$ such that $x \in A$, but we don't necessarily have as a result that there is a set that contains only $x$. Of course we could construct this set with $\{y \in A | y = x\}$, but again we've used separation.

It's for the reasons above that I'm not perfectly satisfied with the answers to other questions here on SE. Perhaps I've made some mistake, or there actually is a better answer.

-

## 1 Answer

You can see in Stanford Encyclopedia of Philosophy the entry on Set Theory .

The Supplement listing the axioms of Zermelo-Fraenkel Set Theory has :

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 \equiv \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$. That is, suppose that $\psi(x,û)$ has $x$ free and may or may not have $u_1, …,u_k$ free. And let $\psi_{x,û}[r,û]$ be the result of substituting $r$ for $x$ in $\psi(x,û)$. Then the Separation Schema asserts:

Separation Schema:

$\forall u_1 …\forall u_k[\forall w \exists v \forall r(r \in v \equiv r \in w \land \psi_{x,û}[r,û])]$

In other words, if given a formula $\psi$ and a set $w$, there exists a set $v$ which has as members precisely the members of $w$ which satisfy the formula $\psi$.

A formal proof of the relation between the two is in Gaisi Takeuti & Wilson Zaring, Introduction to Axiomatic set theory (1971), page 17 (we omit the initial string of $\forall$s) :

Axiom Schema of Replacement

$\forall a [\forall u \forall v \forall w [\phi(u, v) \land \phi(u, w) \rightarrow v = w] \rightarrow \exists b \forall x [x \in b \equiv \exists u [u \in a \land \phi(u, x)]]]$.

Note. The condition of functionality for $\phi$ has been unwinded.

Note also that $a$ is not mentioned in the antecedent, so you can rewrite the formula as : $\forall u \forall v \forall w [...] \rightarrow \forall a\exists b \forall x [x \in b \equiv \exists u [u \in a \land \phi(u, x)]]$. In this way, the consequent has clearly the "form" of Separation.

Zermelo's Schema of Separation

$\forall a \exists b \forall x [x \in b \equiv x \in a \land \phi(x)]$.

Applying Replacement to the wff $\phi(u) \land u = v$ where $v$ does not occur in $\phi(u)$ we have that $[\phi(u) \land u=v] \land [\phi(u) \land u=w] \rightarrow v = w$.

Note. After an "instantiation" of the Replacement schema, the universal closure of the above formula give us its antecedent ; so we can "detach" the consequent.

Therefore

$\exists b \forall x [x \in b \equiv \exists u [\phi(u) \land u = x \land x \in a]]$

i.e. [Note: here we have several steps in one; we need the equality axiom $\vdash u = x \rightarrow (\phi(u) \rightarrow \phi(x))$, "rearranged" as $\vdash (\phi(u) \land u = x ) \rightarrow \phi(x)$ and a final application of quantifier rules to get : $\vdash \exists u(\phi(u) \land u = x ) \rightarrow \phi(x)$.]

$\exists b \forall x [x \in b \equiv \phi(x) \land x \in a]$.

Note. The final step is to introduce the universal quantifier $\forall a$, by "generalization".

-
In Kenneth Kunen's The Foundations of Mathematics, the Replacement Scheme is listed as $\forall x \in A \exists ! y \varphi(x,y) \rightarrow \exists B \forall x \in A \exists y \in B \varphi(x,y)$ (with $A$ universally quantified implicitly). I'm guessing that this is probably equivalent to the version used in Gaisi Takeuti & Wilson Zaring, Introduction to Axiomatic set theory. But it makes the desired proof slightly more difficult. There is more constraint on $\varphi$, so that in addition to being functional, its domain must be the entire set $A$. – objectivesea Feb 22 '14 at 5:35
@objectivesea - but the SEP's version has : $\forall x \exists!y \phi (x,y) ...$ where the initial $x$ is not restricted: so his domain is all the "universe". The "functional expression" $\phi$ is defined for all $x$ and $y$, like all formulas of f-o logic ... – Mauro ALLEGRANZA Feb 22 '14 at 21:04
@MauroALLEGRANZA When you unwind the condition of functionality for $\phi$, could you explain how the existential part of "$\exists!y\phi(x,y)$" is in "$\phi(u,v)\wedge\phi(u,w)\to v=w$" ? – Guest Sep 16 '15 at 18:42
See Uniqueness quantification : it is $\forall u \forall v \forall w [ϕ(u,v)∧ϕ(u,w)→v=w]$ – Mauro ALLEGRANZA Sep 16 '15 at 18:50
@Guest - see Suppes, page 202 : the Ax Schema of Repl is stated with the uniqueness condition "unwinded" ; $∀x∀y∀z[ϕ(x,y)∧ϕ(x,z)→y=z]$. The initial clause $x \in A$, as by Nagase comment, is needed because Suppes theory includes urelements, i.e. "individual" objects that are not sets; thus, the initial clause is needed in order to exclude them from the application of the Ax. – Mauro ALLEGRANZA Sep 16 '15 at 19:08