Use the axiom of regularity (and the singleton set axiom) to show that if is a set, then . Furthermore, show that if and are two sets, then either or (or both).
- 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 . So we make the set .
Now when we use the axiom of regularity, we know of two sets, and , so we have the choice of applying the axiom to either set. Let’s take a guess and apply it to . Since is non-empty, the axiom of regularity says that there is at least one element which is either not a set or is disjoint from . But the only element in is , so we must have that either is not a set or is disjoint from . Since is a set, we conclude that is disjoint from , i.e. . In particular, this means that cannot be an element of both and ; since , we therefore conclude that .
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 and , so we can use the pair set axiom instead and consider the set .
We then apply the axiom of regularity to the set : there must be some which is either not a set or is disjoint from . The only two elements of are the sets and , so the axiom of regularity tells us that either is disjoint from or is disjoint from . In the first case, so in particular ; since this means that . In the second case, so in particular ; but since this means .
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 and , 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 or 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 and 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 though (as I actually did when I first started solving this exercise).
Model solution 1
Consider the set , which exists by the singleton set axiom. By the axiom of regularity applied to , there is at least one element which is either not a set or is disjoint from . Since , we must have . Since is a set, this means that it is disjoint from , i.e. . If then would be in , so we must have as required.
Now consider the set , which exists by the pair set axiom. By the axiom of regularity applied to , there is at least one element which is either not a set or is disjoint from . Since we must have or . If then is disjoint from so in particular ; since this means that . On the other hand, if then is disjoint from so in particular ; but since this means . So either or , 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 and are two sets, then either or (or both).
Now to show the first part of the exercise, let be given and take . Applying the first part of the exercise, we must have or . In other words, we must have or , i.e. we have as desired.