Results 1 to 7 of 7

Math Help - The Principal of Transitive Induction

  1. #1
    Newbie
    Joined
    Apr 2010
    From
    Ohio
    Posts
    12

    The Principal of Transitive Induction

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

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

    <br />
(S_{\alpha} \subset J_0) ==> \alpha \in J_0.<br />

    Theorem (The principal of transitive induction). If J is a well-ordered set and J_0 is an inductive subset of J, then 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  \alpha \in J, assuming that  \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  \alpha \in J and assume that  \alpha \notin J_0. Then J_0\subseteq S_\alpha.

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

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

    This is a contradiction.

    If J_0 = S_\alpha, for this case, I can not find any kind of contradiction. Any suggestions?
    Last edited by auitto; October 15th 2010 at 06:10 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by auitto View Post
    Let J be a well-ordered set. A subset J_0 of J is said to be inductive if for every \alpha\inJ, (S_{\alpha} \subset J_0) ==> \alpha \in J_0.
    (I assume you intend for \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 ' \alpha' supposed to range over members of some particular set? Or over ordinals?

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

    More technically, you've got a free variable ' 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?
    Last edited by MoeBlee; October 15th 2010 at 08:45 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,535
    Thanks
    778
    Quote Originally Posted by auitto View Post
    Also, note that S_\alpha = \{j |j\in J\quad and\quad j<\alpha\}.
    This should come at the top.

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

    Proof: Choose  \alpha \in J and assume that  \alpha \notin J_0. Then J_0\subseteq S_\alpha.
    I am not sure why this is so. I see that \alpha\notin J_0 implies \neg(S_\alpha\subseteq J_0), but not necessarily 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 \alpha such that \alpha\notin J_0.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    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.
    Last edited by MoeBlee; October 15th 2010 at 11:55 AM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    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 \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?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    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.
    Last edited by MoeBlee; October 15th 2010 at 12:21 PM.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Apr 2010
    From
    Ohio
    Posts
    12
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Transitive Set Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: August 30th 2011, 11:19 AM
  2. Product of non principal ideals is principal.
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: June 12th 2011, 01:17 PM
  3. Transitive set
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: February 24th 2009, 09:15 AM
  4. Transitive closure
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: August 14th 2008, 11:06 PM
  5. Transitive
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: September 12th 2007, 07:50 AM

/mathhelpforum @mathhelpforum