# Proving the pairing axiom from the rest of ZF

In ZF, the pairing axiom states that for every $x,y$ there exists the set $\{x, y\}$. Wikipedia also tells us we can dispense this axiom:

This axiom is part of Z, but is redundant in ZF because it follows from the axiom schema of replacement applied to any two-member set. The existence of such a set is assured by either the axiom of infinity, or by the axiom of the power set applied twice to the empty set.

I have a few questions about it:

1. It seems to me we only need to prove that given $x$, there exists the set $\{x\}$ and use the axiom of union for $\{x\}, \{y\}$. Am I correct?
2. To prove $\{x\}$ exists we can apply separation on $P(x)$ - the power set of $x$ whose existence is guaranteed from the axiom of power set. Am I correct?
3. If both the previous statements were correct, is it correct to say that the axiom of pairing can be proved without the need to assume the existence of any set (i.e. without the axiom of infinity or the axiom of the empty set).
4. How can the axiom of infinity be stated without implicitly relying on the axiom of pairing? After all, the formulation I know of for this axiom literally says "there is an inductive set", and to formulate what "inductive set" means you have to use the expression $x\cup\{x\}$ which assumes $\{x\}$ is really an existing set...

## 1 Answer

You have $x,y$, let us construct the pair $\{x,y\}$.

First note that $\varnothing=\{z\in x\mid z\neq z\}$. So we have the empty set. Now by the power set axiom we have $P(\varnothing)=\{\varnothing\}$ and $P(P(\varnothing))=\{\varnothing,\{\varnothing\}\}$.

Now let us define a formula (with parameters $x,y$):

$$\varphi(u,v,x,y)\colon= (u=\varnothing\land v=x)\lor(u=\{\varnothing\}\land v=y\})$$

(Note that $\{\varnothing\}$ can be defined explicitly as the set that all its elements are the empty sets)

Using replacement now, we set the parameters $x,y$ now the axiom says that $\{u\mid\exists v\in P(P(\varnothing))\colon\varphi(v,u,x,y)\}$ exists. But this set is exactly $\{x,y\}$.

1. You cannot use the axiom of union to prove from the existence of $\{x\}$ and $\{y\}$ the existence of the set $\{x,y\}$. The axiom of union says that if $A$ is a set then $\bigcup A$ is a set. However you want to say that $\{\{x\},\{y\}\}$ is a set therefore its union, which is $\{x,y\}$ is a set. You already assume the existence of a pair.

2. You can indeed use separation to prove the existence of $\{x\}$ using the power set axiom as well.

3. To use a power set, or separation argument you have already the existence of some set. Note that the power set axiom says that if $x$ is a set then there exists a set which contains all the subsets of $x$. Separation is the same, you assume the existence of a set. If you wish to use these two, adding an assumption that an empty set exists is meaningless (note that empty sets exists due to separation, so using it for $\{x\}$ is the same as using it for $\varnothing$).

• You've already defined $\{\emptyset\}$--it is simply $P(\emptyset)$. – Cameron Buie May 6 '12 at 8:11
• @CameronBuie: There is no explicit operation in the language for the power set operation. Using the power set axiom I merely prove the existence of this set. – Asaf Karagila May 6 '12 at 8:31
• @AsafKaragila, thanks but this doesn't answer any of my questions. You simply repeat the usual proof and implicitly rely on the existence of a set (otherwise you can't prove the existence of the empty set). – Gadi A May 6 '12 at 8:33
• @Gadi: But if ZF is inconsistent, why would it have a model, why would it be able to prove the existence of any sets in a "consistent" way? – Asaf Karagila May 6 '12 at 8:38
• Your answer to 1 is exactly what I needed, thanks. – Gadi A May 6 '12 at 9:11