Results 1 to 2 of 2

Math Help - uncountable diagnol argument

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    38

    uncountable diagnol argument

    I need to prove that there are uncountably many functions from N to N using a diagonal argument.

    I begin by saying, suppose there are countably many function from N to N.
    Therefore they can be listed....

    However i'm not sure how to build a function which leads to a contradiction.

    Help would be greatly appreciated. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,403
    Thanks
    1486
    Awards
    1
    Make a countable list of all functions \left\{ {f_1 ,f_2 , \cdots f_n , \cdots } \right\}\,,\,\left( {\forall n} \right)\left[ {f_n :N \mapsto N} \right].
    Define a function \left[ {g:N \mapsto N} \right] by g(n) = \left\{ {\begin{array}{rl}   {2,} & {f_n (n) = 1}  \\   {1,} & {f_n (n) \ne 1}  \\<br />
 \end{array} } \right..
    But \left( {\exists K} \right)\left[ {g = f_K } \right].
    Is that possible?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. A has rank n iff diagnol entries of R^ are non zero
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: September 30th 2009, 05:17 PM
  2. [SOLVED] uncountable subset is itself uncountable
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 3rd 2009, 10:30 AM
  3. Replies: 4
    Last Post: October 11th 2008, 01:42 PM
  4. N^N is uncountable
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 22nd 2008, 01:34 AM
  5. Diagnol Argument #2
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: February 6th 2006, 02:32 PM

Search Tags


/mathhelpforum @mathhelpforum