Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
What type(s) of thing are $a$ and $b$? –  Eric Towers Mar 23 at 4:48
    
@Eric: Sets, of course. –  Asaf Karagila Mar 23 at 4:52
    
ZF? ZFC? New Foundations? –  Eric Towers Mar 23 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 at 4:58
    
@EricTowers- ZF –  algebraically_speaking Mar 23 at 4:59

3 Answers 3

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|improve this answer
    
why "meta-set" instead of the standard "class"? –  Andres Caicedo Mar 23 at 7:01
    
@AndresCaicedo, no particular reason. Feel free to edit with more standard terminology if you wish. –  goblin Mar 23 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.

share|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 at 6:17
    
I meant $\langle x,c\rangle$ –  algebraically_speaking Mar 23 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 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|improve this answer

Your Answer

 
discard

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.