August | 2022 | Tao Analysis Solutions

Exercise statement

Use the axiom of regularity (and the singleton set axiom) to show that if $A$ is a set, then $A \notin A$ . Furthermore, show that if $A$ and $B$ are two sets, then either $A \notin B$ or $B \notin A$ (or both).

Hints

Think about which set you want to construct using the singleton set axiom.

How to think about the exercise

We are told to use the singleton set axiom. There is really only one choice of a set we can construct using this axiom, because we are only given the set $A$ . So we make the set $\{A\}$ .

Now when we use the axiom of regularity, we know of two sets, $A$ and $\{A\}$ , so we have the choice of applying the axiom to either set. Let’s take a guess and apply it to $\{A\}$ . Since $\{A\}$ is non-empty, the axiom of regularity says that there is at least one element $x \in \{A\}$ which is either not a set or is disjoint from $\{A\}$ . But the only element in $\{A\}$ is $A$ , so we must have that either $A$ is not a set or $A$ is disjoint from $\{A\}$ . Since $A$ is a set, we conclude that $A$ is disjoint from $\{A\}$ , i.e. $A \cap \{A\} = \emptyset$ . In particular, this means that $A$ cannot be an element of both $A$ and $\{A\}$ ; since $A \in \{A\}$ , we therefore conclude that $A \notin A$ .

How should we do the second part of the exercise? A good guess is to repeat the same technique as the first part. But now we have two sets $A$ and $B$ , so we can use the pair set axiom instead and consider the set $\{A,B\}$ .

We then apply the axiom of regularity to the set $\{A,B\}$ : there must be some $x \in \{A,B\}$ which is either not a set or is disjoint from $\{A,B\}$ . The only two elements of $\{A,B\}$ are the sets $A$ and $B$ , so the axiom of regularity tells us that either $A$ is disjoint from $\{A,B\}$ or $B$ is disjoint from $\{A,B\}$ . In the first case, $A \cap \{A,B\} = \emptyset$ so in particular $B \notin A \cap \{A,B\}$ ; since $B \in \{A,B\}$ this means that $B \notin A$ . In the second case, $B \cap \{A,B\} = \emptyset$ so in particular $A \notin B \cap \{A,B\}$ ; but since $A \in \{A,B\}$ this means $A \notin B$ .

As you can see, once you know to use the singleton set axiom (or pair set axiom), each step of the solution is just the next obvious step. So the real insight of this proof is to consider using the singleton set axiom (or pair set axiom) in the first place, or alternatively to think of constructing the sets $\{A\}$ and $\{A,B\}$ , which Tao just gave away in the exercise statement itself! How would we have thought of that?

I think the trick is to realize that the axiom of foundation only tells us about the existence of a certain element in a given set. We want to use the axiom of foundation (since this axiom was introduced specifically to rule out Russell’s paradox), but if a set contains a bunch of elements like $1$ or $\emptyset$ then the axiom of foundation will only tell us something we already know. To get some actual value out of the axiom of foundation, we must construct a simple set, the elements of which we want to know more about. So constructing a set consisting only of the supposedly “paradoxical” sets $A$ and $B$ will give us what we need.

One last note: it is easy to write this proof as a proof by contradiction, but notice how it’s not required (or more precisely, we can push the “proof by contradiction” nature to start at the very end of the proof, rather then declaring it at the start). That makes the proof easier to read, in my opinion. It may still help you to discover the proof if you started out by assuming $A\in A$ though (as I actually did when I first started solving this exercise).

Model solution 1

Consider the set $\{A\}$ , which exists by the singleton set axiom. By the axiom of regularity applied to $\{A\}$ , there is at least one element $x \in \{A\}$ which is either not a set or is disjoint from $\{A\}$ . Since $x \in \{A\}$ , we must have $x=A$ . Since $x=A$ is a set, this means that it is disjoint from $\{A\}$ , i.e. $A\cap \{A\}=\emptyset$ . If $A \in A$ then $A$ would be in $A\cap \{A\}$ , so we must have $A \notin A$ as required.

Now consider the set $\{A,B\}$ , which exists by the pair set axiom. By the axiom of regularity applied to $\{A,B\}$ , there is at least one element $x \in \{A,B\}$ which is either not a set or is disjoint from $\{A,B\}$ . Since $x \in \{A,B\}$ we must have $x=A$ or $x=B$ . If $x=A$ then $A$ is disjoint from $\{A,B\}$ so in particular $B \notin A \cap \{A,B\}$ ; since $B \in \{A,B\}$ this means that $B \notin A$ . On the other hand, if $x=B$ then $B$ is disjoint from $\{A,B\}$ so in particular $A \notin B \cap \{A,B\}$ ; but since $A \in \{A,B\}$ this means $A \notin B$ . So either $B \notin A$ or $A \notin B$ , which is what we wanted to show.

Model solution 2

This version does the second part of the exercise first, exactly as in Model solution 1. Thus we know that if $A$ and $B$ are two sets, then either $A \notin B$ or $B \notin A$ (or both).

Now to show the first part of the exercise, let $A$ be given and take $B := A$ . Applying the first part of the exercise, we must have $A \notin B$ or $B \notin A$ . In other words, we must have $A \notin A$ or $A \notin A$ , i.e. we have $A \notin A$ as desired.