Results 1 to 4 of 4

Math Help - Prove that the set of increasing sequences...

  1. #1
    Newbie
    Joined
    Jan 2009
    Posts
    17

    Prove that the set of increasing sequences...

    Prove that the set of increasing sequences of natural numbers (n1<n2<...) is uncountable.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by jefferson_lc View Post
    Prove that the set of increasing sequences of natural numbers (n1<n2<...) is uncountable.
    Suppose we can enumerate them, for example,
    \left< \boxed{4}, 5, 11, 19, 121, ... \right>
    \left< 2, \boxed{7}, 12, 13, 99, ... \right>
    \left< 7, 8, \boxed{9}, 10, 12, ... \right>
    \left< 1, 2, 99, \boxed{100},222, ... \right>
    ...

    Define a new sequence:
    \left< 4+1,7+4,9+7,100+9, ... \right>

    I hope you can see how we defined this sequence? The first term is the boxed term +1, then the second term is the last term plus the second boxed term, and so on. This creates a new increasing sequence which is not found on this list.
    (This was the diagnol argument)

    EDIT: Mistake fixed.
    Last edited by ThePerfectHacker; January 8th 2009 at 06:38 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,775
    Thanks
    1514
    Quote Originally Posted by ThePerfectHacker View Post
    Suppose we can enumerate them, for example,
    \left< \boxed{4}, 5, 11, 19, 121, ... \right>
    \left< 2, \boxed{7}, 12, 13, 99, ... \right>
    \left< 7, 8, \boxed{9}, 10, 12, ... \right>
    \left< 1, 2, 99, \boxed{100},222, ... \right>
    ...

    Define a new sequence:
    \left< 4+1,7+4,9+7,100+9, ... \right>

    I hope you can see how we defined this sequence? The first term is the boxed term +1, then the second term is the last term plus the second boxed term, and so on. This creates a new increasing sequence which is now found on this list.
    (This was the diagnol argument)
    Unfortunate typo: "which is not found on this list".
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2009
    Posts
    17
    great! thanks
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove that the sequence is increasing
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: January 13th 2012, 01:37 PM
  2. prove increasing
    Posted in the Calculus Forum
    Replies: 4
    Last Post: March 19th 2011, 02:09 PM
  3. increasing functions prove strictly increasing
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: May 14th 2010, 03:19 PM
  4. increasing sequences
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: October 4th 2009, 01:04 PM
  5. Prove that φ(x) is entirely increasing?
    Posted in the Calculus Forum
    Replies: 3
    Last Post: April 28th 2009, 06:12 AM

Search Tags


/mathhelpforum @mathhelpforum