# 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.

• Would you add "integer" before "numbers" in the title and in the first sentence? Your intuition is correct. – egreg Dec 29 '13 at 17:09
• You can try Hrbacek, Jech - Introduction to set theory – Giulio Bresciani 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. – Dutta 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)$. – Dutta 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. – André Nicolas Dec 30 '13 at 1:57
• It is clear now. – Dutta 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. – André Nicolas 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. – Dutta Jan 1 '14 at 16:15