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

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$?

• What do you mean by inductive set? – Snufsan Sep 11 '14 at 16:35
• 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$? – Git Gud Sep 11 '14 at 16:48
• @Snufsan: See here. – Frunobulax Sep 11 '14 at 16:58
• Every set $x$ satisfy $x \notin x$ because if $x$ would satisfy $x \in x$, we would get Russel paradox – 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).

• 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 – A student Sep 11 '14 at 17:27