# Tricky set proof in Halmos Naive Set Theory

Proposition: All sets obtained from successive applications of the axiom of pairing to the empty set are unique.

My attempts on this so far are to start with the empty set and pair upwards to an arbitrary number of nested sets, but my professor slams this approach because we haven't yet constructed the idea of "numbers", so this proof is meaningless. Instead I'm supposed to "start from above" with "any number(!!) of applications of pairing, and then start stripping away using extension."

What the hell is going on? How do I prove this?

• What does the statement of that proposition even mean? What would it mean for these sets to "not be unique"? – Eric Wofsey Nov 10 '15 at 23:01
• @EricWofsey Good point. If the integers ($\omega$) aren't yet proven to exist, then how do you know that the collection of all sets thus obtained is in fact a set? No ordinals, so no notion of "rank". The book (1st Ed) is online here. It seems this is on p.10 of that edition, phrased differently than what's quoted above. Has he even introduced Regularity? – BrianO Nov 10 '15 at 23:10
• @BrianO I see you're right. I apologize I misquoted the book! Regularity has not been introduced. – Aidan Nov 10 '15 at 23:18
• No problem. But the Exercise has problems:) By p.10 (or whichever in 2nd Ed), all he has going on is Extensionality, Separation ("Specification"), and Pairing. You can show that if $\{a,b\} = \{c,d\}$ then ($a=c$ or $a=d$) and similarly ($b=c$ or $b=d$), and $a\ne b$ iff $c\ne d$. But you can't prove a theorem in this weak system such as you quoted, too many axioms and too much machinery is lacking. – BrianO Nov 10 '15 at 23:27

## 1 Answer

Note that each pair has two elements. So if two pairs are equal, then their elements are equal. This allows you to run an exhaustion game: if two pairs are equal, then their "components" are equal; if any of these is a pair, then their components are equal, etc. Any "pair of pairs of pairs" will be made of a finite number of pairs and so this decreasing comparison test can always be run.

• (Note that these are unordered pairs, so each unordered pair has one or two elements.) The problem is, when Halmos gives this exercise, the only axioms introduced are Extensionality, Separation and (unordered) Pairing. Oh, and existence of something. There's no notion of integers yet, no notion of "finite" yet, so... "decreasing"? in what sense? – BrianO Nov 10 '15 at 23:37
• In the sense that, precisely because you have so few axioms, you can only assume that the "pair buildup" is a finite concrete process. As Halmos says, even if "two" or "three"are not defined from the point of view of set theory, they do exist in a naive way in the English language, no math needed. So you have to assume that any pair is "writable" by using enough labels (whether these are numbers, or letters, or animals); and then you can perform the process I mentioned. – Martin Argerami Nov 11 '15 at 0:11
• OK I'll go for that. We still have integers in the metatheory, after all. – BrianO Nov 11 '15 at 0:12