Results 1 to 4 of 4

Thread: 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 $\displaystyle \omega$ consisting of all natural numbers is a transitive set?

    That is, prove that:
    $\displaystyle 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 $\displaystyle x=\emptyset,$ your formula is true?

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

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

    So, using the mathematical induction principle, we proved that $\displaystyle \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
    10
    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 $\displaystyle X$ is a set of ordinals then $\displaystyle \cup X$ is a set of ordinals. Since $\displaystyle \omega$ is the union of all natural numbers and since each natural number is an ordinal it follows that $\displaystyle \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: Jan 24th 2011, 10:25 AM
  2. Model Theory - minimal sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Nov 20th 2010, 01:10 PM
  3. Model theory - definiable sets
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Nov 19th 2010, 09:12 AM
  4. Model theory - definiable sets 2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Nov 16th 2010, 12:08 PM
  5. Naive set theory - show two sets are equal
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: Nov 10th 2010, 03:48 AM

Search Tags


/mathhelpforum @mathhelpforum