# Proving that there can be no set of all ordered pairs.

I have to prove that there is no set which contains all ordered pairs $\langle a,b\rangle$. in set theory, $\langle a,b\rangle$ is defined as $\{\{a\},\{a,b\}\}$.

My proof: Say $S$ is the set with all ordered pairs. Then $S=A\times B$, where $A$ contains all the first coordinates and $B$ contains all the second coordinates. However, there has to be a set that is not contained within $A$, as there can be no set of all sets. Let that set be $r$. Then $\langle r,c\rangle\notin S$, where $c$ is any set of your choice.

Is the proof correct?

-
What type(s) of thing are $a$ and $b$? –  Eric Towers Mar 23 '14 at 4:48
@Eric: Sets, of course. –  Asaf Karagila Mar 23 '14 at 4:52
ZF? ZFC? New Foundations? –  Eric Towers Mar 23 '14 at 4:53
Since the axiom of choice has nothing to do with it; and I believe that in $\sf NF$ the collection of all ordered pairs is indeed a set; my guess that one of the first two. –  Asaf Karagila Mar 23 '14 at 4:58
@EricTowers- ZF –  algebraically_speaking Mar 23 '14 at 4:59

Here's how I would do it.

Let $V$ denote the meta-set of all entities, and $P$ denote the meta-set of all ordered pairs. Furthermore, let $\pi_0 : P \rightarrow V$ denote the unique meta-function with defining property

$$\pi_0(a,b) = a.$$

Now assume for a contradiction that $P$ can be internalized as a set. Then by replacement, since the domain of $\pi_0$ is a set, we have that $\pi_0[P]$ is also a set.

Exercise 0. Verify that $\pi_0[P]$ is a universal set. i.e. $\pi_0[P] = V.$

Exercise 1. Recall the axiom schema of separation implies that a universal set cannot exist, via Russell's paradox.

-
why "meta-set" instead of the standard "class"? –  Andres Caicedo Mar 23 '14 at 7:01
@AndresCaicedo, no particular reason. Feel free to edit with more standard terminology if you wish. –  goblin Mar 23 '14 at 7:04

No. The proof you have written says: If the set of all ordered pairs is constructed as a cartesian product, then the first member of that product is a set we have all agreed doesn't exist. So, that's (only) one possible way of constructing the set of all ordered pairs rejected. Now we just have to adapt this for every possible way of constructing the set of all ordered pairs.

Alternatively, we can show that the assumption that the set of all ordered pairs exists leads to a contraduction no matter how it was constructed.

Let $P$ be the set of all ordered pairs of sets. Let $f(\langle a,b \rangle) = a$ be the function that picks out the first member of a pair. Then $F = \{f(x) \mid x \in P\}$ is a set. It contains all of the first members of the pairs in the set of all ordered pairs of sets. It therefore is a set containing all sets. Since no such set exists, $F$ does not exist, so either $f$ is not a valid function of $P$ does not exist.

Do you believe that $f$ is a valid function? If so, then $P$ does not exist.

-
I think there is only one way to construct such a set of ordered sets. Let us suppose $A$ is not the set of all sets. Then there is one set $x\notin A$. Hence, $\langle x,x\rangle$ does not exist, where $c$ is any element. –  algebraically_speaking Mar 23 '14 at 6:17
I meant $\langle x,c\rangle$ –  algebraically_speaking Mar 23 '14 at 6:25
@algebraically_speaking: How do you know that $P$ can't be the union of perfectly good sets? Or the intersection of perfectly good sets? Or that $P$ isn't the subset of some other set specified by a membership predicate? There are many ways to make a set. You'd have to eliminate every possible alternative. –  Eric Towers Mar 23 '14 at 6:29

If you're assuming Kuratowski pairs, then there's a very easy reductio. We know that for any $a,b$ we can form both $\langle a,b\rangle$ and $\langle b,a \rangle$, so every set would appear in some ordered pair. If $\mathsf{Pair}$ is our hypothetical set of all ordered pairs, then the axiom of Union says we can form $\bigcup\bigcup\mathsf{Pair}$. This would be $V$, which is impossible in ZF.

-