# Is every inductive set also transitive?

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!

• Well, I do actually ask the question which is in the title also in the body. The (other) question in the body is what made me think about the question in the title. – user39280 Sep 2 '12 at 21:47
• Ah, you are correct. I'm sorry for not reading better... :-) – Asaf Karagila Sep 2 '12 at 21:48

$\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$.

• Thank you! Now i got it and it was pretty easy. – user39280 Sep 2 '12 at 20:35

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.

• Yes, now I understand! Thank you! – user39280 Sep 2 '12 at 20:53

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.

• 1. What does "inductive closure" mean? 2. Just to be clear, is the following definition correct? A set $x$ is inductive iff every subset of $x$ is a member of $x$. – Evan Aad Jul 18 at 15:57

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...

• @dado: If $A\subset X$ and $B\subset X$ then $A\cup B\subset X$. Now set $A=y$ and $B=\{y\}$. The two premises are then exactly the condition for $y\in Y$ to hold. – Henning Makholm Sep 2 '12 at 20:27
• But I still don't see how an inductive set need not be transitive. All the examples of inductive set that I can think of are transitive (i.e. every element is also a subset of the set!). – user39280 Sep 2 '12 at 20:38
• @dado: On further thought I think there are perhaps multiple definitions of "inductive" around, where some may imply that $\omega$ is the only inductive set around, and if so, every inductive set is transitive simply because $\omega$ is. However, I think the more common definition is that an inductive set is one that contains $\varnothing$ and is closed under the function $S(a)=a\cup\{a\}$. Then the set $\omega \cup \{S^n(\{\{42\}\})\mid n\in\omega\}$ is inductive but not transitive, since it contains $\{\{42\}\}$ but not $\{42\}$. – Henning Makholm Sep 2 '12 at 20:47
• Thank you. The only inductive sets I could think of were simply $\omega$ in disguise (that's why I thought they were all transitive!). – user39280 Sep 2 '12 at 20:51

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