Results 1 to 11 of 11

Math Help - Cardinality of Rational Sequences

  1. #1
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8

    Cardinality of Rational Sequences

    My friend and I were discussing the cardinality of the countable cartesian product of countable sets. This is clearly bijective to the set of ALL rational sequences. We couldn't figure out the cardinality of this set. I say it's \alpeh_1, while he thinks that it may be \aleph_2.

    It is clear that the set of rational Cauchy sequences is \aleph_1, but this is merely a subset of All rational sequences.

    What is the cardinality of the set of All rational sequences? I would appreciate a sketch of a proof of this. Thanks in Advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    |\mathbb{Q}^{\mathbb{N}}|=|\mathbb{N}^{\mathbb{N}}  |=|2^{\mathbb{N}}|=|\mathbb{R}|=2^{\omega}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    Quote Originally Posted by DrSteve View Post
    |\mathbb{Q}^{\mathbb{N}}|=|\mathbb{N}^{\mathbb{N}}  |=|2^{\mathbb{N}}|=|\mathbb{R}|=2^{\omega}
    Yes, but why does |\mathbb{N}^\mathbb{N}| = |2^\mathbb{N}|? It is not obvious to me that there is a bijection (or an injection) between the sequences of natural numbers, and the power set of the natural numbers. Could you show me an injection from \mathbb{N}^\mathbb{N} to \mathcal{P}(\mathbb{N})?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Guy
    Guy is offline
    Member
    Joined
    Mar 2010
    Posts
    98
    Quote Originally Posted by Haven View Post
    Yes, but why does |\mathbb{N}^\mathbb{N}| = |2^\mathbb{N}|? It is not obvious to me that there is a bijection (or an injection) between the sequences of natural numbers, and the power set of the natural numbers. Could you show me an injection from \mathbb{N}^\mathbb{N} to \mathcal{P}(\mathbb{N})?
    It's easy enough to get a one-one mapping from the sequences of naturals to the unit interval. I think the map that takes 1, 3, 5, 7, ... into .373337333337.... works.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Quote Originally Posted by Guy View Post
    It's easy enough to get a one-one mapping from the sequences of naturals to the unit interval. I think the map that takes 1, 3, 5, 7, ... into .373337333337.... works.
    This map is not an injection. The sequence 5, 0, 0, 0... would map to .5000... = .5, and the sequence 4, 9, 9, 9, ... would map to .4999... = .5.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Guy
    Guy is offline
    Member
    Joined
    Mar 2010
    Posts
    98
    Quote Originally Posted by roninpro View Post
    This map is not an injection. The sequence 5, 0, 0, 0... would map to .5000... = .5, and the sequence 4, 9, 9, 9, ... would map to .4999... = .5.
    I think you misread. 5, 0, 0, ... maps to .33333777777777.... while 4, 9, 9, 9... maps to .3333733333333373333333337....

    Incidentally, I picked 3 and 7 so that I would avoid things like .99999999... = 1.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member roninpro's Avatar
    Joined
    Nov 2009
    Posts
    485
    Quote Originally Posted by Guy View Post
    I think you misread. 5, 0, 0, ... maps to .33333777777777.... while 4, 9, 9, 9... maps to .3333733333333373333333337....

    Incidentally, I picked 3 and 7 so that I would avoid things like .99999999... = 1.
    Yes, sorry - I read it too quickly. I think that you are correct.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    \mathbb{N}^{\mathbb{N}}\subseteq P(\mathbb{N}\times \mathbb{N})\Leftrightarrow P(\mathbb{N}) \Leftrightarrow 2^{\mathbb{N}}.

    Here \Leftrightarrow means "is equinumerous with" (or there is a bijection).

    The other direction is trivial. By the Schroeder-Bernstein Theorem the 2 sets have the same cardinality.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8
    Technically speaking wouldn't  \mathbb{N}^\mathbb{N} \not\subseteq \mathcal{P}(\mathbb{N}\times \mathbb{N}), however, there is a natural injection.

    Which would be  \{a_n\}_{n=1}^\infty \in \mathbb{N}^\mathbb{N} \mapsto \{ (a_n,a_{n+1}) : n=2t+1 \}_{t=0}^\infty \in \mathcal{P}(\mathbb{N} \times \mathbb{N})
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780
    You can consider a graph of a function from \mathbb{N}^\mathbb{N} as a subset of \mathbb{N}\times\mathbb{N}.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    Quote Originally Posted by Haven View Post
    Technically speaking wouldn't  \mathbb{N}^\mathbb{N} \not\subseteq \mathcal{P}(\mathbb{N}\times \mathbb{N}), however, there is a natural injection.

    Which would be  \{a_n\}_{n=1}^\infty \in \mathbb{N}^\mathbb{N} \mapsto \{ (a_n,a_{n+1}) : n=2t+1 \}_{t=0}^\infty \in \mathcal{P}(\mathbb{N} \times \mathbb{N})
    An element of \mathbb{N}^\mathbb{N} is a function, which in turn is a set of ordered pairs, thus it is also an element of \mathcal{P}(\mathbb{N}\times \mathbb{N}). Perhaps we're using different definitions here.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Prove rational raised to a rational is rational.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: February 15th 2011, 08:12 PM
  2. Replies: 2
    Last Post: December 8th 2009, 06:48 AM
  3. Replies: 6
    Last Post: May 5th 2009, 06:49 AM
  4. Replies: 4
    Last Post: March 27th 2009, 08:19 PM
  5. Replies: 5
    Last Post: January 16th 2008, 04:51 PM

/mathhelpforum @mathhelpforum