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 $U = \{ x \in X \mid x $ is transitive and $ x \notin x \}$ is inductive.

Proof: Let $\alpha \in U$, we have to show that $\alpha \cup \{ \alpha \} \in U$. But $\alpha \cup \{ \alpha \}$ is transitive since $(\beta \in \alpha \Rightarrow \beta \subseteq \alpha)$ and $(\alpha \subseteq \alpha \cup \{ \alpha \})$. Left to show: $\alpha \cup \{ \alpha \} \notin \alpha \cup \{ \alpha \}$. Suppose in contradiction that $\alpha \cup \{ \alpha \} \in \alpha \cup \{ \alpha \}$. This would imply $\alpha \cup \{ \alpha \} \in \alpha$ which implies $\alpha \in \alpha$ ($\alpha$ transitive). contradiction.

Is my proof correct?


Seeing as the definition of transitive and the notion that $x\notin x$ are fairly simplistic, your proof might be correct.

I can think of two problems:

  • $\alpha\subseteq\alpha\cup\{\alpha\}$ does not imply $\alpha\in\alpha\cup\{\alpha\}$ so your logic here is flawed.

  • In the second part, your logical deductions of the implications are without foundations.

There is more on inductive sets and the ZF axiom of infinity here.

An interesting case is where the base elements of a set are $a$ and $\{a\}$, at level $1$ we have induced elements $a\cup\{a\}$ and $\{a\}\cup\{\{a\}\}$, making the conjecture more difficult.

My attempt at a proof is:

Given $\alpha\in U$, we need to show:

  1. $\alpha\cup\{\alpha\}$ is transitive
  2. $\alpha\cup\{\alpha\}\notin \alpha\cup\{\alpha\}$

1) If $\beta\in\alpha\cup\{\alpha\}$, then we have one of $\beta\in\alpha$ and/or $\beta\in\{\alpha\}$ and $\beta\in\alpha\cup\{\alpha\}, \beta\notin\alpha, \beta\notin\{\alpha\}$. All $3$ imply $\beta\subseteq\alpha\cup\{\alpha\}$, hence $\alpha\cup\{\alpha\}$ is transitive.

2) Note that $\alpha\in\{\alpha\}$ therefore $\{\alpha\}\notin\alpha$, otherwise we would have $\alpha=\{\alpha\}$ which is absurd.

If $\alpha\cup\{\alpha\}\in\alpha\cup\{\alpha\}$ then we have $\alpha\cup\{\alpha\}\in\{\alpha\}$ because we already know $\alpha\notin\alpha$ (from $\alpha\in U$), and therefore $\alpha\cup\{\alpha\}\notin\alpha$.

But we also have $\{\alpha\}\in\alpha\cup\{\alpha\}$, and so using the same idea as before, $\{\alpha\}=\alpha\cup\{\alpha\}$, which again is absurd. Therefore $\alpha\cup\{\alpha\}\notin\alpha\cup\{\alpha\}$.

Therefore $U$ is inductive.

  • $\begingroup$ Actually, everything implies that $\alpha\in X\cup\{\alpha\}$, regardless to the contents of $X$. $\endgroup$ – Asaf Karagila Aug 8 '15 at 10:43

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.