4
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ Thank you for the answer supporting my approach. $\endgroup$ – Dutta Dec 30 '13 at 1:46
3
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Dutta Dec 30 '13 at 1:46
  • 1
    $\begingroup$ 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. $\endgroup$ – André Nicolas Dec 30 '13 at 1:57
  • $\begingroup$ It is clear now. $\endgroup$ – Dutta Dec 30 '13 at 2:02
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Dec 30 '13 at 2:06
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Happy new year. This is also a nice answer. $\endgroup$ – Dutta Jan 1 '14 at 16:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.