# Thread: The Principal of Transitive Induction

1. ## The Principal of Transitive Induction

Note that $\displaystyle S_\alpha = \{j |j\in J\quad and\quad j<\alpha\}.$

Let $\displaystyle J$ be a well-ordered set. A subset $\displaystyle J_0$ of $\displaystyle J$ is said to be inductive if for every $\displaystyle \alpha\inJ,$

$\displaystyle (S_{\alpha} \subset J_0) ==> \alpha \in J_0.$

Theorem (The principal of transitive induction). If J is a well-ordered set and $\displaystyle J_0$ is an inductive subset of $\displaystyle J$, then $\displaystyle J_0=J$.

Can someone help me get started on proving this. I am trying to show that [tex] J \subseteq J_0 [/Math] by choosing $\displaystyle \alpha \in J,$ assuming that $\displaystyle \alpha \notin J_0$ and showing that there is a contradiction. Is this a good approach and do you have any hints that I can use to get anywhere?

Ok so I made some progress, but I am not sure if I am moving in the right direction.

Proof: Choose $\displaystyle \alpha \in J$ and assume that $\displaystyle \alpha \notin J_0.$ Then $\displaystyle J_0\subseteq S_\alpha.$

If $\displaystyle J_0\subset S_\alpha$ then consider $\displaystyle \{\beta\in S_\alpha }| \beta\notin J_0\}.$

Then this set has a least-element, call it $\displaystyle \beta_0.$ It follows that $\displaystyle S_{\beta_0}\subset J_0 ==> \beta_0\in J_0.$

If $\displaystyle J_0 = S_\alpha,$ for this case, I can not find any kind of contradiction. Any suggestions?

2. Originally Posted by auitto
Let $\displaystyle J$ be a well-ordered set. A subset $\displaystyle J_0$ of $\displaystyle J$ is said to be inductive if for every $\displaystyle \alpha\inJ, (S_{\alpha} \subset J_0) ==> \alpha \in J_0.$
(I assume you intend for $\displaystyle \subset$ to stand for "is a subset of" as opposed to "is a proper subset of"?)

In any case, I don't understand that definition.

Is '$\displaystyle \alpha$' supposed to range over members of some particular set? Or over ordinals?

And why should using $\displaystyle \alpha$ as an INDEX for $\displaystyle S$ have anything to do with $\displaystyle \alpha$ as a MEMBER of $\displaystyle J_0$? As far as I can tell, the way you've set it up, I could use ANY $\displaystyle \alpha$ from ANY index set to prove that $\displaystyle \alpha$ is in $\displaystyle J_0$ just by taking $\displaystyle S_0$ to be the empty set.

More technically, you've got a free variable '$\displaystyle S$' in your definiens that is not in your definiendum. That won't work to make a proper definition.

What book is this problem from?

3. Originally Posted by auitto
Also, note that $\displaystyle S_\alpha = \{j |j\in J\quad and\quad j<\alpha\}.$
This should come at the top.

I agree with MoeBlee: if $\displaystyle \subset$ stands for "is a proper subset" in $\displaystyle S_{\alpha}\subset J_0\Rightarrow\alpha\in J_0$, then your claim is false. Indeed, let $\displaystyle J$ be the set of natural numbers with the usual order and let $\displaystyle J_0=\{0,\dots,5\}$. Then $\displaystyle S_n\subset J_0$ iff $\displaystyle n < 5$ (and $\displaystyle S_6=J_0$), and $\displaystyle n < 5$ implies $\displaystyle n\in J_0$; however, $\displaystyle J_0\ne J$. If the condition said $\displaystyle S_{n}\subseteq J_0\Rightarrow n\in J_0$, then it would be false for this $\displaystyle J_0$: $\displaystyle S_6\subseteq J_0$, but $\displaystyle 6\notin J_0$.

Proof: Choose $\displaystyle \alpha \in J$ and assume that $\displaystyle \alpha \notin J_0.$ Then $\displaystyle J_0\subseteq S_\alpha.$
I am not sure why this is so. I see that $\displaystyle \alpha\notin J_0$ implies $\displaystyle \neg(S_\alpha\subseteq J_0)$, but not necessarily $\displaystyle J_0\subseteq S_\alpha$.

I believe that the Principle of Transitive Induction is nothing other than the principle of transfinite induction. The latter is usually formulated for ordinals but holds for any well-ordered set. Your proof idea is close, but consider the least $\displaystyle \alpha$ such that $\displaystyle \alpha\notin J_0$.

4. EDIT: Darn, something sems wrong here. The assumption "x in J" doesnt' seem to be used, which would imply that K is the class of all ordinals!

All we know about J is that there is a well ordering of J? I'm sensing, from the definition of S, that J itself is supposed to be a set of ordinals and the mentioned well ordering on J is '<', which is membership on ordinals. Is that right? I'll assume it is. So:

J is a set of ordinals.

S is an operation on the class of ordinals such that S(x) = J intersect x.

Definition here: K is inductive iff (K is a subset of J and for all ordinals x, if S(x) is a subset of K then x in K).

Show: If K is inductive, then K = J.

Suppose x in J. It suffices to show that J intersect x is a subset of K.

Toward a contradiction, let y be the least that is in J intersect x but not in K.

So J intersect y is not a subset of K.

So let z in J intersect y but not in K. So, since y in x, we have z in J intersect x.

Such a z contradicts the leastness of y.

5. But wait a minute, weren't there posts between the poster Plato and me about the subset symbol? What happened to those posts?

Is PROPER subset indeed not supposed to be indicated by $\displaystyle \subset$ so that the two different symbols in the original poster's post are irrelevant, or not? If proper subset is not what's meant, then why are there two different kinds of subset symbols in the post?

6. Now I suspect that the defintion was supposed to be this actually:

K is inductive iff (K is a subset of J and for all x in J, if S(x) is a subset of K then x in K).

Note that "x in J" replaces "ordinals x".

THEN the assumption "x in J" is used in the proof as given previously.

7. The symbol is intended to mean "is proper subset of."

This problem is from Munkres, Topology 3rd Edition. It is exercise #7 in section 10.

Also, nothing is mentioned about J being a set of ordinals, just that it is well-ordered.