Results 1 to 4 of 4

Math Help - Set theory, transitive sets

  1. #1
    Junior Member
    Joined
    Jun 2008
    Posts
    56

    Set theory, transitive sets

    Could someone please prove, using the principle of mathematical induction, that the set \omega consisting of all natural numbers is a transitive set?

    That is, prove that:
    y \in x \in \omega \rightarrow y \in \omega

    Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Hi

    Do you agree that, for x=\emptyset, your formula is true?

    Now assume that it is true for a x\in\omega, we have to show that it's also true for its successor, x\cup\{x\}.

    Let y be an element of x\cup\{x\}, i.e. y\in x\ \text{or}\ y\in \{x\}. In the first case, the induction hypothesis states that y\in\omega. In the second case, y=x and then y\in\omega .

    So, using the mathematical induction principle, we proved that \omega is a transtive set.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Here is a non-induction way to prove this. I know you asked for induction but I bring this approach up because it might help you when you do more stuff on ordinals. If X is a set of ordinals then \cup X is a set of ordinals. Since \omega is the union of all natural numbers and since each natural number is an ordinal it follows that \omega is an ordinal.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Jun 2008
    Posts
    56
    Thanks to both of you, I will probably have another question or two in the next couple of days..
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Transitive Set Theory Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: January 24th 2011, 10:25 AM
  2. Model Theory - minimal sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 20th 2010, 01:10 PM
  3. Model theory - definiable sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 19th 2010, 09:12 AM
  4. Model theory - definiable sets 2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 16th 2010, 12:08 PM
  5. Naive set theory - show two sets are equal
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: November 10th 2010, 03:48 AM

Search Tags


/mathhelpforum @mathhelpforum