# 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
• @Asaf: Pretty much any kind of ordered pair has a "set of all ordered pairs" in NF, but the sets of all Quine pairs and of all Kuratowski pairs have different cardinalities. I mention this because it's weird, and because I'm prone to pointlessly spouting NF trivia. – Malice Vidrine Mar 23 '14 at 6:56

No. Take $R_1=\{(1,a),(2,b)\}$.Then $R_1$ cannot be written as $A \times B$. So a set of ordered pair may not be written as cartesian product.

Below I give two proofs independent of perticular definition, say Kuratowski or Weiner or Hausdroff or short def etc.\

Proof1: Let $A$ be a set.Let us construct $B=\{(x,y)$$\in A$$\mid$ $(x,y)$$\notin x$$\}$. We claim $(B,1)\notin A$.\ If possible let $(B,1)\in A$. Then by construction of $B$, $(B,1)\in B$ iff $(B,1)\in A$ and $(B,1)\notin B$. Since we assume $(B,1)\in A$, $(B,1)\in B$ iff $(B,1)\notin B$. So our assumption $(B,1)\in A$ is false. Since $A$ is arbitary, the proof follows. \ Proof2: Let $A$ be the set of all ordered pairs. Since $A$ is a set of ordered pairs, $A$ is relation. Let $B=dom A$.Then $B$ is set$($Since $B\subseteq \bigcup \bigcup A$, by subset axiom, $B$ exists $)$ . There is set $C\notin B$, since there is no set of all sets. Fortiori $(C,1)\notin A$. This contradicts our assumtion. Hence such $A$ does not exists.

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"? – Andrés E. 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.

I think basically your approach is valid, but you could skip $A$ and $B$ and just consider the hypotheticall set $S$. Then by the axiom of union theres a set $U$, the union over the set $S$. Now if you know that universal set doesn't exist you have a contradiction since $U$ is just that.

The proof sketch has a significant gap — it does not attempt to justify writing $S = A \times B$ for sets $A$ and $B$.

Any attempt to justify this step will likely uncover a more direct proof of the theorem in the process.

• It's not just a significant gap, it's a mistake that a set of ordered pairs is of the form $A\times B$. Just look at $\{(n,n)\mid n\in\Bbb N\}$. – Asaf Karagila Mar 14 '18 at 8:17