3
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ What does the statement of that proposition even mean? What would it mean for these sets to "not be unique"? $\endgroup$ Commented Nov 10, 2015 at 23:01
  • $\begingroup$ @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? $\endgroup$ Commented Nov 10, 2015 at 23:10
  • $\begingroup$ @BrianO I see you're right. I apologize I misquoted the book! Regularity has not been introduced. $\endgroup$ Commented Nov 10, 2015 at 23:18
  • $\begingroup$ 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. $\endgroup$ Commented Nov 10, 2015 at 23:27

1 Answer 1

Reset to default
2
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ (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? $\endgroup$ Commented Nov 10, 2015 at 23:37
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Nov 11, 2015 at 0:11
  • 1
    $\begingroup$ OK I'll go for that. We still have integers in the metatheory, after all. $\endgroup$ Commented Nov 11, 2015 at 0:12

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.