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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.