# Cardinality of all sequences of non-negative integers with finite number of non-zero terms. (NBHM 2012)

Consider the set $S$ of all sequences of non-negative integers with finite number of non-zero terms.

1. Is the set $S$ countable or not?
2. What is the cardinality of the set $S$ if it is not countable?

My intuition is the set is countable. The sequence has only finitely many non-zero terms. For any fixed $N$ consider the set $A_N$ which contains all sequences $\{a_n\}$ s.t. $a_k = 0$ $\forall$ $k >N$. The set $A_N$ is countable as the first $N$ terms of a sequences can be filled up by non-negative integers in a countable number of ways. So $A_N$ is countable and $S$ is a countable union of countable sets. So $S$ is countable.

I do not know if it is true or false. If it is false please identify the mistake. Thank you for your help.

Please suggest me a book where I shall get sufficient number of such type of problem to clear basic ideas on cardinal number.

If it has been already discussed please post the like and reply the reference request.

• Would you add "integer" before "numbers" in the title and in the first sentence? Your intuition is correct. Dec 29 '13 at 17:09
• You can try Hrbacek, Jech - Introduction to set theory Dec 29 '13 at 17:27

You can think a sequence as a finite subset of $\mathbb{N}^2$: for all $a_n\neq 0$, take the point $(n,a_n)$. This way, you can inject $S$ in the set $\mathcal{P'}(\mathbb{N}^2)$ (with $\mathcal{P'}$ I mean the set of finite subsets) and this is in bijection with $\mathcal{P'}(\mathbb{N})$. But $\mathcal{P'}(\mathbb{N})$ is countable, because it is a countable union of countable sets (subsets with $0$ elements, subsets with $1$ element, subsets with $2$ elements...).

• Thank you for the answer supporting my approach. Dec 30 '13 at 1:46

Let $\mathbb{N}$ be the set of non-negative integers. If $s=s_0,s_1,s_2,\dots,s_n,\dots$ is a sequence in $S$, define $\psi(s)$ by $$\psi(s)=\left(\prod_{i=0}^\infty p_i^{s_i}\right)-1,$$ where $p_i$ is the $i$-h prime. By the Unique Factorization Theorem, $\psi$ is a bijection from $S$ to $\mathbb{N}$.

• Nicolas: Thank you for introducing a new concept. Let me know why you are subtracting 1 from the product in the definition of $\phi(s)$. Dec 30 '13 at 1:46
• That is because I am using as $\mathbb{N}$ the non-negative integers. If we are making a bijection to the positive integers, there is no $-1$ term. Of course it makes no real difference, since there is an obvious bijection between the non-negatives and the positives. Dec 30 '13 at 1:57
• It is clear now. Dec 30 '13 at 2:02
• I think the answer by Giulio Bresciani is more "versatile," and therefore more worthy of accepting. Mine is a little too cute, too tailored to the specific situation. Dec 30 '13 at 2:06

Put a decimal point in front of any of these sequences and you have a rational number between 0 and 1. The set is countable. There is a bit more to it than just that. You will need to consider repetitions. You end up with a countable number of equivalence classes that are each at most countable. 1,1,0,0,0,0... becomes .110000... and 11,0,0,0,0... also becomes .110000...

• Happy new year. This is also a nice answer. Jan 1 '14 at 16:15