Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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.

share|cite|improve this answer
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. 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.

share|cite|improve this answer

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.

share|cite|improve this answer
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.

share|cite|improve this answer

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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