2
$\begingroup$

I stumbled upon this exercise:

Prove that, if $X$ is an inductive set, then $Y=\{x \in X\colon x \subset X\}$ is inductive.

I easily proved that $\emptyset \in Y$ but then I could not find a way to show that $\forall y \in Y, y \cup \{ y \} \in Y$.

Is every inductive set transitive? Obviously, if every inductive set were transitive, the exercise would be pretty trivial. Could anyone clarify this for me? I would be really grateful.

Thanks!

  • 0
    Ah, you are correct. I'm sorry for not reading better... :-)2012-09-02

5 Answers 5

1

$\emptyset \in Y$ since $X$ is inductive.

Suppose $x \in Y$. Then by definition $x \in X$ and $x \subset X$. Since $X$ is inductive $x \cup \{x\} \in X$. $x \cup \{x\} \subset X$ since $x \subset X$ and $x \in X$. So $x \cup \{x\} \in Y$ since it has been shown that $x \cup \{x\} \in X$ and $x \cup \{x\} \subset X$.

  • 0
    Thank you! Now i got it and it was pretty easy.2012-09-02
1

If $A$ is any set, then you can start making an inductive set by letting $S_0=\{A\}$ and recursively $S_{n+1} = \{ x \cup \{x\}\mid x \in S_n\} \cup S_0$. Then $S_\omega :=\bigcup S_n$ has the successor property of an inductive set. Finally $I:=\omega \cup S_\omega$ is inductive, that is $\emptyset \in I$ and $x\in I\Rightarrow x\cup\{x\}\in I$.

Note that $A\in I$ but not necessarily $A\subset I$, for example if the elments of $A$ are not ordinals.

  • 0
    Yes, now I understand! Thank you!2012-09-02
1

As to your question about whether every inductive set is transitive, certainly not. Let $\mathbb{N}$ be the natural numbers as ordinarily defined. Let $a=\{\{\{\{\emptyset\}\}\}\}$, and let $A$ be the inductive closure of $\{a\}$. Let $B=\mathbb{N}\cup A$. The $B$ is inductive but not transitive.

0

No, it does not need to be transitive. I suspect you're overcomplicating the task; what you need follows directly from the definitions:

If $y\in Y$, then in particular $y\in X$. Because $X$ is transitive we then have $y\cup\{y\}\in X$. That is half or proving that $y\cup\{y\}$ is in $Y$. The other half requires $y\cup\{y\}\subset X$. Now remember what $y\in Y$ means...

  • 0
    Thank you. The only inductive sets I could think of were simply $\omega$ in disguise (that's why I thought they were all transitive!).2012-09-02
0

Look again at the definition of $Y$: $Y=\{x\in X:x\subseteq X\}$, so by definition every element of $Y$ is both a subset and an element of $X$. Thus, if $y\in Y$, automatically $y\in X$ and $\{y\}\subseteq X$. Since $y\in X$, $y\cup\{y\}\in X$, and clearly $y\cup\{y\}\subseteq X$, so $y\cup\{y\}\in Y$.