Exercise 1 on page 10 in Naive Set Theory, following Axiom of Pairing

In Section 3 "Axiom of Pairing" in Naive Set Theory on page 10 Halmos proposes the following argument.

"Consider the sets $\emptyset , \lbrace \emptyset \rbrace , \lbrace \lbrace \emptyset \rbrace \rbrace , \lbrace \lbrace \lbrace \emptyset \rbrace \rbrace \rbrace ,$ etc.; consider the pairs such as $\lbrace \emptyset , \lbrace \emptyset \rbrace \rbrace ,$ formed by any two of them; Consider the pairs formed any two such pairs, or else the mixed pairs formed by any singleton and any pair; and proceed so on ad infinitum.

Exercise Are all the sets obtained in this way distinct from one another?

I really didn't get what he asks. Does he ask question about the first sequence only, then about the second sequence of pairs and so on or does he ask about any possible mix of sets of empty sets?

Can anyone elucidate this exercise for me with suggested justification or hint how to show that they are distinct?

• @Andres I am not sure how this question should be tagged. The questions about axioms of ZFC (including pairing) belong to set-theory tag. On the other hand, this question seems to be more about equality of sets and about clarification of a text of an exercise – Martin Sleziak Jul 10 '15 at 8:16

We produce an infinite sequence of sets where each set is defined by taking two already defined sets and pairing them. So if we have already producs $a$ and $b$ (where possibly $a=b$) then we can produce $\{a,b\}$ next. Then the only way to produce a duplicate consists of picking the same $a$ and $b$ again (recall that $\{a,b\}=\{c,d\}$ iff ...), which we of course won't do - though we should make it clear that we pick unordered pairs, i.e., if we pick $a$ and $b$ then we won't pick $b$ and $a$ later. So the pair sets a different simply because we pick different unordered pairs. Actually, this may seem a bit handwavy mostly because the means to formalize this process are not there yet.

EDIT: The text below is my original post which contains my (incorrect) interpretation of the question. (Since there were some comments about it, so I think I should leave it here so that comments make sense. The comment exchange below contributes, in my opinion, to better understanding of the question in the book, so I consider them worth keeping.)

Let us denote $a=\emptyset$, $b=\{\emptyset\}$, $c=\{\{\emptyset\}\}$, $d=\{\{\{\emptyset\}\}\}$. (It might be useful to notice that these are four different sets.)

In the first stage you have 6 sets $\{a,b\}$, $\{a,c\}$, $\{a,d\}$, $\{b,c\}$, $\{b,d\}$, $\{c,d\}$.

In each of the following stages you consider sets of the form $\{a,e\}$, $\{b,e\}$, $\{c,e\}$, $\{d,e\}$, where $e$ is some of the sets obtained in the previous stages. (So if we exclude the 6 cases mentioned above, the set $e$ will have two elements.)

This is how I would understand the wording of that exercise.

• I do not think that is exactly what he means. There are not only 4 elements but infinite of them. So, you should continue inserting the set as element in the following set up to infinity. Then yes, you should create all sets of two elements. and so on. Let's forget about this new mixes and consider only the first sequence. Do you know how to formalize they each of them in that sequence is distinct. My guess is that we should use axiom of extensionality but since we do not know natural numbers yet upto this chapter we cannot use induction on sequence. – G.T. Jul 10 '15 at 8:02
• Re: Let's forget about this new mixes and consider only the first sequence. If you are allowed to use axiom of regularity then for any two sets $a$, $b$ in that sequence you have a sequence of the form $a=x_0 \in x_1 \in \dots \in x_n=b$. This contradicts axiom of regularity. (But I would prefer a proof without this axiom.) – Martin Sleziak Jul 10 '15 at 8:11
• You can describe this sequence inductively $a_0=\emptyset$, $a_{n+1}=\{a_n\}$. With the exception of $a_0$ you have singletons. Two singletons are equal if and only if the elements contained in them are equal. (I.e., $\{x\}=\{y\}$ if and only if $x=y$.) So I would try to show by induction on $k$ that $a_k \ne a_{k+n}$ for $n>0$. Does this answer your question: Do you know how to formalize they each of them in that sequence is distinct? – Martin Sleziak Jul 10 '15 at 8:14
• Axiom of regularity is not proposed until this chapter. According to the structure of the book this exercise must be solved without axiom of regularity. – G.T. Jul 10 '15 at 8:24
• As for Induction, I know how to formalize the induction in the way you described. But he has not introduced natural numbers either. But for Induction we need that natural numbers is a well-ordered set. Don't we? – G.T. Jul 10 '15 at 8:25

For the set of pairs from $A$ and $B$ let's write $A \times B$. The operator $\times$ is commutative because $\{a,b\}=\{b,a\}$. But it is not associative because $\{\{a,b\},c\} \ne \{a,\{b,c\}\}$

The set of singletons is $S=\left\{\emptyset , \lbrace \emptyset \rbrace , \lbrace \lbrace \emptyset \rbrace \rbrace , \lbrace \lbrace \lbrace \emptyset \rbrace \rbrace \rbrace , \ldots\right\}$,
we call this set $S_1$. So we have

$$S_1:=S$$

Now we set $n=1$.

We pair $S_n$ with all sets $S_i$ with $i$ equal or less than $n$. So we get the set of pairs $$S_2:=S_1 \times S_1=S \times S$$ we increase $n$ to $2$.

Now we pair $S_n$ with all sets $S_i$ with $i$ equal or less to $n$. So we get the set of pairs of pairs is $$S_3:=S_2 \times S_2=(S \times S) \times (S \times S)$$

and the mixed pairs
$$S_4:=S_2 \times S_1=S \times (S \times S)$$ which is the same as $(S \times S) \times S$.

we increase $n$ to $3$

We pair $S_n$ with all sets $S_i$ with $i$ equal or less to $n$. So we get the set of pairs $$S_5.=S_3 \times S_3=((S \times S) \times (S \times S)) \times ((S \times S) \times (S \times S))$$

and the sets $$S_6:=S_3 \times S_2=((S \times S) \times (S \times S))\times(S \times S)$$ and $$S_7:=S_3 \times S_1=((S \times S) \times (S \times S))\times S$$

now we increase $n$ to $4$ and so on.