# Thread: Cardinality of Rational Sequences

1. ## 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 $\displaystyle \alpeh_1$, while he thinks that it may be $\displaystyle \aleph_2$.

It is clear that the set of rational Cauchy sequences is $\displaystyle \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.

2. $\displaystyle |\mathbb{Q}^{\mathbb{N}}|=|\mathbb{N}^{\mathbb{N}} |=|2^{\mathbb{N}}|=|\mathbb{R}|=2^{\omega}$

3. Originally Posted by DrSteve
$\displaystyle |\mathbb{Q}^{\mathbb{N}}|=|\mathbb{N}^{\mathbb{N}} |=|2^{\mathbb{N}}|=|\mathbb{R}|=2^{\omega}$
Yes, but why does $\displaystyle |\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 $\displaystyle \mathbb{N}^\mathbb{N}$ to $\displaystyle \mathcal{P}(\mathbb{N})$?

4. Originally Posted by Haven
Yes, but why does $\displaystyle |\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 $\displaystyle \mathbb{N}^\mathbb{N}$ to $\displaystyle \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.

5. Originally Posted by Guy
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.

6. Originally Posted by roninpro
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.

7. Originally Posted by Guy
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.

8. $\displaystyle \mathbb{N}^{\mathbb{N}}\subseteq P(\mathbb{N}\times \mathbb{N})\Leftrightarrow P(\mathbb{N}) \Leftrightarrow 2^{\mathbb{N}}$.

Here $\displaystyle \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.

9. Technically speaking wouldn't $\displaystyle \mathbb{N}^\mathbb{N} \not\subseteq \mathcal{P}(\mathbb{N}\times \mathbb{N})$, however, there is a natural injection.

Which would be $\displaystyle \{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})$

10. You can consider a graph of a function from $\displaystyle \mathbb{N}^\mathbb{N}$ as a subset of $\displaystyle \mathbb{N}\times\mathbb{N}$.

11. Originally Posted by Haven
Technically speaking wouldn't $\displaystyle \mathbb{N}^\mathbb{N} \not\subseteq \mathcal{P}(\mathbb{N}\times \mathbb{N})$, however, there is a natural injection.

Which would be $\displaystyle \{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 $\displaystyle \mathbb{N}^\mathbb{N}$ is a function, which in turn is a set of ordered pairs, thus it is also an element of $\displaystyle \mathcal{P}(\mathbb{N}\times \mathbb{N})$. Perhaps we're using different definitions here.