Definition. We say that $A$ is an inductive set if $\varnothing\in A$, and whenever $x\in A$ then $x\cup\{x\}\in A$ as well.

I am trying to prove the following exercise:

If $X$ is inductive, then, the set, $\{ x \in X \mid x $ is transitive and $ x \notin x \}$ is inductive.

My question is: what does it mean $x \notin x$? Don't we know (Russel Paradox) that $x \notin x$ for every $x \in X$?

  • $\begingroup$ What do you mean by inductive set? $\endgroup$ – Snufsan Sep 11 '14 at 16:35
  • 2
    $\begingroup$ I don't understand your first question. What do you mean with 'meaning'? The expression $x\not \in x$ as an abbreviation of $\neg (x\not\in x)$ is a perfectly valid formula once quantified. In your second question, what is $a$? $\endgroup$ – Git Gud Sep 11 '14 at 16:48
  • $\begingroup$ @Snufsan: See here. $\endgroup$ – Frunobulax Sep 11 '14 at 16:58
  • $\begingroup$ Every set $x$ satisfy $x \notin x$ because if $x$ would satisfy $x \in x$, we would get Russel paradox $\endgroup$ – A student Sep 11 '14 at 17:18

The axiom of infinity simply tells you that some inductive set exists. And you can even show that the minimal inductive set indeed satisfies $x\notin x$ for all its elements.

But it is consistent without the axiom of regularity that there is a set $x$ satisfying $x=\{x\}$. Now consider $X=\omega\cup\{x\}$, this set is inductive, since whenever $a\in\omega\cup\{x\}$ either $a\in\omega$ and $a\cup\{a\}\in\omega$, so $a\cup\{a\}\in X$ or $a=x$ in which case $a\cup\{a\}=x\cup\{x\}=x\cup x=x\in X$; and of course $\varnothing\in\omega$ so $\varnothing\in X$.

So the question asks you to show that given an inductive set, we can even omit the elements $x\in x$, or $x$ is not transitive, and still have an inductive set.

As for the remark about Russell's paradox, no. Russell's paradox only tells us that:

  1. The class $\{x\mid x\notin x\}$ is a proper class. Being a proper class doesn't mean being the entire universe.
  2. When applied with conjunction of separation axioms, it means that every set $A$ has a subset $B$ which is not an element of $A$.

As I wrote above, it is consistent that $x=\{x\}$ is true for some set $x$. The axiom which guarantees us that this doesn't happen is the axiom of regularity (also known as axiom of foundations sometimes).

  • $\begingroup$ I thought that no set can satisfy $x \in x$ because if there would be a set $x$ for which $x \in x$ we would get Russel Paradox $\endgroup$ – A student Sep 11 '14 at 17:27

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.