Results 1 to 2 of 2

Math Help - Countability of N x N (Naturals x Naturals)

  1. #1
    Member
    Joined
    Nov 2010
    Posts
    86

    Countability of N x N (Naturals x Naturals)

    To Prove: N (set of Naturals numbers) * N (set of Natural numbers) is countable.

    The way I need to go about writing this proof is to find a surjection from N --> NxN and then apply the fact that: a nonempty set A is countable if and only if there exists a surjection N --> A

    Any help would be appreciated!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by jstarks44444 View Post
    To Prove: N (set of Naturals numbers) * N (set of Natural numbers) is countable.

    The way I need to go about writing this proof is to find a surjection from N --> NxN and then apply the fact that: a nonempty set A is countable if and only if there exists a surjection N --> A

    Any help would be appreciated!
    Oh god. Do you actually have to exhibit the surjection? You could note that the map n,m)\mapsto 2^n3^m" alt="f:\mathbb{N}\times\mathbb{N}\to\mathbb{N}n,m)\mapsto 2^n3^m" /> is an injection and conclude that there must be a surjection the other way.

    Or, I think f(n,m)\mapsto 2^{m-1}(2n-1) is a bijection, I think.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. naturals as a subset of the reals
    Posted in the Differential Geometry Forum
    Replies: 6
    Last Post: January 25th 2011, 09:44 AM
  2. 10 naturals numbers.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: December 8th 2009, 03:06 PM
  3. Find all naturAls numbers. X , Y..
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: August 4th 2009, 09:49 AM
  4. [SOLVED] Proof Help with Naturals
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 18th 2009, 01:21 AM
  5. Constructing Z from N (integers from naturals)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 3rd 2007, 04:59 AM

Search Tags


/mathhelpforum @mathhelpforum