Tao Analysis I - 3.2.2

Exercise 3.2.2

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).

Lets' write out the Axiom of Regularity.

Axiom 3.10 (Regularity). If $A$ is a non-empty set, then there is at least one element $x$ of $A$ which is either not a set, or is disjoint from $A$.

Show that if $A$ is a set, then $A \notin A$

Using the singleton set axiom, we can create a set $\{A\}$ from $A$.

Now we apply the axiom of regulatory to $\{A\}$. The axiom states that if $\{A\}$ is a non-empty set, then there is at least one element $x=A$ of $\{A\}$ which is either not a set, or is disjoint from $\{A\}$.

Let's consider these two cases:

• $x=A$ is not a set. This case is not true because we are given $A$ as a set.
• $x=A$ is disjoint from $\{A\}$. 

This means $A \cap \{A\} = \emptyset$. If it were true that $A \in A$, then we would have $A=\{A, ...\}$. But $\{A, ..\} \cap \{A\} \neq \emptyset$ since $A$ is a non-empty set. We conclude $A \notin A$. $\square$

This solution is inspired by Issa Rice's solution.

Show that if $A$ and $B$ are two sets, then either $A \notin B$ or $B \notin A$ (or both).

Let's follow a similar strategy and use the pair set axiom to construct a set $\{A,B\}$.

Assuming $A$ and $B$ are non-empty, applying the axiom of regularity tell us that if $\{A,B\}$ is a non-empty set, then there is at least one element of $\{A,B\}$ which is either not a set, or is disjoint from $\{A,B\}$.

Let's consider these two cases:

• At least one of $A$ and $B$ is not a set. This is not true because we are given $A$ and $B $ as sets.
• At least one of $A$ and $B$ is disjoint from $\{A,B\}$.

This gives us two further cases, either or both of which are true:

• $A \cap \{A,B\} = \emptyset$. This means $B \notin A$. If it were, then ${B, ..} \cap \{A,B\} = \emptyset$ is false.
• $B \cap \{A,B\} = \emptyset$. This means $A \notin B$. If it were, then ${A, ..} \cap \{A,B\} = \emptyset$ is false.

So we conclude that, either or both,  $B \notin A$ and  $A \notin B$ are true. $\square$

This solution is inspired by Issa Rice's solution.