It has come to my attention that the pairing axiom and the separation axiom schema are rarely listed since they follows from the replacement axioms. I see how this works for the pairing axiom, since we can take some set, say $A=\{\emptyset,\{\emptyset\}\}$, which exists by the power set axiom and the existence of the emptyset, and define a nominating formula on $A$ by $$ \phi(u,v)\colon (u=\emptyset\land v=a)\lor(u\neq\emptyset\land v=b) $$ to see that $\{a,b\}$ is a set for any sets $a$ and $b$. However, I don't see it for the separation schema. Could someone enlighten me on how they follow? Thanks.


The replacement axiom (axiom scheme) is the most general form you need, essentially saying that if you have a function whose domain is a set then the image is also a set. Furthermore, the empty set can be inferred by an existence of any set at all, when combined with separation (and hence, can be inferred by replacement).

Formally speaking the replacement schema says that for every formula $\varphi(u,v,p_1,\ldots,p_n)$, fix the parameters $p_1,\ldots,p_n$ and pick any set $A$, whenever $u\in A$ has at most one $v$ for which $\varphi(u,v,p_1,\ldots,p_n)$ is true, then the collection of $\{v\mid\varphi(u,v,p_1,\ldots,p_n), u\in A\}$ is also a set.

How to infer separation and pairing? Simple.

First we infer separation. Given $\phi(x)$, we simply define $\varphi(u,v,p)$ to be $$\varphi(u,v,p)\stackrel{\text{def}}{=} u=v\land u\in p\land\phi(u)$$ This is a functional formula (i.e. for every $u$ there is at most a single $v$ for which $\varphi(u,v,p)$ holds) and it is easy to verify that the image of $\varphi(u,v,a)$ is indeed $\{x\in a\mid \phi(x)\}$.

The empty set exists by separation - simply take some $a$ (which exists because we assume there is some set in the universe) and the function $\phi(x)\colon = x\neq x$.

As you noted, $\{\emptyset ,P(\emptyset)\}$ exists by the Power set axiom.

Now for a given $x,y$ we want to have $\{x,y\}$ so we define the following $\varphi(u,v)$ as following: $$\varphi(u,v) \colon = (u=\emptyset\wedge v=x)\vee (u=P(\emptyset)\wedge v=y)$$

Note that $\varphi$ is a functional formula, i.e. for a given $u$ there is only one $v$ for which $\varphi(u,v)$ is true. By the axiom of replacement we have now that $\{x,y\}$ is a set. Therefore the axiom of pairing holds if we assume Power set and Replacement.

Now we have two ways of looking at ZFC. Sometimes we want to prove that something is a model for ZFC and need to verify the list of axioms in which case proving both Separation and Replacement is completely redundant. At other times we want to prove certain things which are quicker when using the more specific axioms (e.g. pairing (or even ordered pairing, which can be quickly inferred from pairing itself)).

This is a sort of freedom that we allow ourselves. We add extra axioms that we don't really need. Then if we want to ensure all the axioms hold we check for the "core" of the axiomatic system, and when we want to ease on ourselves in other cases we can just use the extra axioms for our convenience.

  • $\begingroup$ I know this post is quite old, but since my question is about your proof, I thought it might be better to just comment than start a new question: In the definition of $\varphi(u,v,p)$ must it not be: $u=v \wedge u\in p \wedge \phi(u)$? And another question. Do we remain the seperation axiom ($(\forall X)(\forall p)(\exists Y)(\forall u)(u\in Y \leftrightarrow u\in X\wedge \varphi(u,p))$) in the notation as above by $\forall x(x\in \{x\in p|\phi(x)\}\leftrightarrow x\in p \wedge \phi(x))$? I hope it is clear what I mean :) $\endgroup$ – Luca May 30 '13 at 13:07
  • $\begingroup$ @Luca, I'm not sure what you mean by "Do we remain the separation axiom". $\endgroup$ – Asaf Karagila May 30 '13 at 14:52
  • $\begingroup$ I am not really sure how I see that this proved the separation... So I tried so somehow connect the Axiom we had in the lecture with the proof above. I don'T know if this made sense? $\endgroup$ – Luca May 30 '13 at 16:00
  • $\begingroup$ @Luca, I don't know how you formulated separation in the lecture. $\endgroup$ – Asaf Karagila May 30 '13 at 16:05
  • $\begingroup$ It's this: $(\forall X)(\forall p)(\exists Y)(\forall u)(u\in Y \leftrightarrow u\in X \wedge \varphi(u,p))$. So I tried to get this with the results of the proof: Replacement $\Rightarrow$ Separation. $\endgroup$ – Luca May 30 '13 at 16:11

Given a set $A$ and a formula $\phi(x)$ we create the function-class that sends every element $a\in A$ to $\{a\}$ if $\phi(a)$ and to $\varnothing$ otherwise. Typically this would be written $$\psi(x,y): (\phi(x)\to y=\{x\})\land(\lnot\phi(x)\to y=\varnothing)$$

Then taking the union of the set that is produced through the axiom of replacement you get what you are looking for.

  • $\begingroup$ The usual way I've seen the existence of $\{x\}$ established is through the use of pairing and separation. Since we're trying to show that these two axioms follow from replacement, they can't be used in that process. So how do we know that $\{x\}$ is a set? $\endgroup$ – objectivesea Feb 18 '14 at 2:28
  • $\begingroup$ @objectivesea: I hadn't seen your comment. You don't need separation to show that $\{x\}$ is a set. Pairing (and extension) is enough, you just take $x=y$. Still, Asaf's answer is the standard solution to this problem. $\endgroup$ – Apostolos Feb 23 '14 at 0:51

Let $A$ be a set. We want to prove the existence of the set $X$ of all elements of $A$ which satisfy a certain formula $\phi$. If no element of $A$ satisfies $\phi$, the existence of $X$ is easy.

Otherwise, suppose that $a \in A$ satisfies $\phi$. Define the functional relation $\rho$ by $\rho(x,a)$ if $x$ does not satisfy $\phi$, and $\rho(x,x)$ if $x$ satisfies $\phi$. Then $X$ is the "range" of $\rho$ as $x$ travels over $A$.

  • $\begingroup$ If no element of $A$ satisfies $\phi$ then $X = \emptyset$. If we have the ability to use comprehension, then the existence of $\emptyset$ is straightforward. But without comprehension, I'm having a hard time seeing how we can show the existence of $\emptyset$. $\endgroup$ – objectivesea Feb 18 '14 at 2:52
  • $\begingroup$ I am replying more to your comment to Apostolos. We do have Pairing. $\endgroup$ – André Nicolas Feb 18 '14 at 2:59
  • 1
    $\begingroup$ The version of the Replacement schema in "Set Theory:An Introduction to Independence Proofs" by Kunen is weaker than the version here. It says that if the domain of a function is a set, then the members of the range all belong to some set. In general, Separation (Comprehension in Kunen"s book) is then needed to then obtain the range-set. $\endgroup$ – DanielWainfleet Aug 2 '15 at 3:02
  • $\begingroup$ @objectivesea it depends on the exact formulation of Replacement. If in your formulation, functions are defined on the entire domain, and you say that $F[A]$ is a set whenever $A\subseteq dom(F)$ is a set, then you do have a problem. But if you just say that $F[A]$ is a set whenever $A$ is a set, then the relation $F=\{<x,x>\mid x\ne x\}$ will give $F[A]=\varnothing$ for any $A$. Also if you formulate it as Asaf did - that every u∈A has at most one v etc. then you are OK. $\endgroup$ – Ur Ya'ar Apr 17 '18 at 8:42

The formulation of Replacement in the book Set Theory:An Introduction to Independence Proofs, by K. Kunen,is different : When $f$ is a formula whose free variables are among $x,y,A,v_1,...,v_n$ then $$\forall A\;\forall_{j=1}^nv_i\;[\;\forall x\in A\;\exists! y\;(f) \implies \exists Y\;\forall x\in A\;\exists y\in Y\;(f)\;].$$ This is weaker than $$\forall A\;\;\forall_{j=1}^nv_i\;[ \;\forall x\in A\;\exists!y\;(f)\implies\exists Y\;\forall y \;(\;y\in Y\iff \exists x\in X \;(f)\;)\;].$$ The latter can be deduced by combining Replacement and Comprehension (Separation). This approach goes back a long time. Godel showed that in ZF minus the Axiom of Infinity minus Comprehension, the Comprehension schema can be replaced by a collection of $ 8$ axioms which he explicitly wrote out. (Or,if you want, by one rather long single sentence.) Comprehension replaces the earlier, naive, schema of Abstraction, which is $\exists Y \;\forall y\;[y\in Y\iff f]$ which leads to paradoxes, e.g. Russell's Paradox.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.