Results 1 to 3 of 3

Math Help - Cardinality Problem (2)

  1. #1
    Junior Member
    Joined
    Mar 2010
    Posts
    63

    Cardinality Problem (2)

    Prove that |\mathbb{N}^{\mathbb{N}}| = |\mathbb{N}^{\mathbb{N} \times \mathbb{N}}|.

    I know of a fact that |\mathbb{N}| = |\mathbb{N} \times \mathbb{N}|. The problem here is how I can go about establishing the bijective function non-trivially.

    Thanks in advance.
    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

    Re: Cardinality Problem (2)

    Quote Originally Posted by Markeur View Post
    Prove that |\mathbb{N}^{\mathbb{N}}| = |\mathbb{N}^{\mathbb{N} \times \mathbb{N}}|.

    I know of a fact that |\mathbb{N}| = |\mathbb{N} \times \mathbb{N}|. The problem here is how I can go about establishing the bijective function non-trivially.

    Thanks in advance.
    If you know basic cardinal arithmetic you can say that |\mathbb{N}^\mathbb{N}|=\aleph_0^\aleph_0=\aleph_0  ^{\aleph_0\aleph_0}=|\mathbb{N}^{\mathbb{N} \times\mathbb{N}}|, but this is really just what you're asking, isn't it? If you know there exists a bijection f:\mathbb{N}\times\mathbb{N}\to\mathbb{N} define F:\mathbb{N}^\mathbb{N}\to\mathbb{N}^{\mathbb{N} \times\mathbb{N}} by taking k\in \mathbb{N}^\mathbb{N} to the function F(k)\in\mathbb{N}^{\mathbb{N}\times\mathbb{N}} given by F(k)(n,m)=k(f(n,m)). To see this is a bijection you must merely note that if k\ne h then there exists some n\in\mathbb{N} for which k(n)\ne h(n) check then that F(k)(f^{-1}(n))\ne F(h)(f^{-1}(m,n)). I leave it to you to show that this is a surjection.


    Note, this extends to show that |X|=|Y|\implies |Z^X|=|Z^Y|.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Cardinality Problem (2)

    Quote Originally Posted by Markeur View Post
    The problem here is how I can go about establishing the bijective function non-trivially.
    This is just an instance of the more general theorem:

    If S and T are 1-1, then B^S and B^T are 1-1.

    I would just prove that more general result.

    Or are you asking how to prove that N and NxN are 1-1?

    Do you have the fundamental theorem of arithmetic at your disposal? If so, it's easy to get an injection form NxN into N. If not, then there are other ways too.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Cardinality Problem
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 4th 2011, 05:49 AM
  2. Cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: December 7th 2010, 10:01 AM
  3. Cardinality
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: January 4th 2010, 02:45 AM
  4. cardinality
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 9th 2008, 03:37 AM
  5. Cardinality Problem
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: February 27th 2007, 03:04 PM

Search Tags


/mathhelpforum @mathhelpforum