# Prove that for any two sets $A$ and $B$, $A\notin B$ or $B\notin A$

A quick preface to the below question: this is my first post on math.se! I am excited to begin participating in such a wonderful community. Any feedback as to how I can improve this or subsequent posts is certainly feedback from which I could benefit.

(Exercise 3.2.2 of Tao's Analysis I) Use the axiom of regularity (and the singleton set axiom, which guarantees the existence of the singleton set) to show that if $A$ is a set, then $A\notin A{. \kern 0.05em}^\text{1}$ Furthermore, show that if $A$ and $B$ are sets, then $A\notin B$ or $B\notin A$.

Thoughts: Consider some set $A$ and the singleton $\{A\}$. By the axiom of regularity, the only element of $\{A\}$, namely $A$, is not a set or disjoint from $\{A\}$. Clearly, $\{A\}\cap A=\emptyset$ and thus, $A\notin A$.

Moreover, suppose $B$ is some other set such that $\neg(A\notin B \lor B\notin A)$, i.e. $A\in B\land B\in A$. This implies, in very vauge notation, that $A=\{\{A,\dots\},\dots\}$ and $B=\{\{B,\dots\},\dots\}$. Can I get a contradiction out of this? In the case of $A$, we get that $x\in\{A,\dots\}\lor x\in \{a\}$ for some $x\in A$ and all other objects $a\in A$. How can I prove that there exists no element of $A$ (and $B$) that is not a set unless it is disjoint from $A$. I would greatly appreciate any hints as to how I can complete my argument.

1 This first problem has been discussed on this site times before (see here and here). I include a solution only because the context demands it, but to avoid a duplicate question, I ask that it not be discussed here.

• How does $\{A\}\cap A=\emptyset$ follow from the singleton set axiom? – Hagen von Eitzen Jun 7 '18 at 18:33
• If $A\in B$ and $B\in A$ consider the set $\{A,B\}$... – David C. Ullrich Jun 7 '18 at 18:34
• @HagenvonEitzen It really doesn't. That was just bad wording, sorry. I edited my question. – Crosby Jun 7 '18 at 18:36
• I suppose you wanted to write "... is not a set or disjoint from $\color{red}\{A\color{red}\}$" – Hagen von Eitzen Jun 7 '18 at 18:38
• Oh, yes. That was what I meant – Crosby Jun 7 '18 at 18:39

If $A\in B$ and $B\in A$, then $X=\{A,B\}$ is a set which is:

1. Non-empty,
2. each of the members of $X$ has a non-empty intersection with $X$. Namely, $A\in B\cap X$ and $B\in A\cap X$.

This is a contradiction to the axiom of regularity, therefore either $X$ is not a set, or $A\in B\land B\in A$ is false. But since pairing ensures that $X$ is a set, we can only conclude that $A\notin B$ or $B\notin A$.

By contraddiction, suppose that $A\in B$ and $B\in A$.

By Axiom of Regularity you can prove :

There is no infinite sequence $(a_n)_n$ such that $a_{i+1}$ is an element of $a_i$ for all $i$.

But if you choose $a_n=A$ if $n$ is odd and $a_n=B$ otherwise you have a contraddiction.