1
$\begingroup$

I know that the set of all infinite sequences with finite length is countable, this set seems like its just countable copies of the set of all infinite sequences with finite length. How to show this rigorously?

$\endgroup$
  • $\begingroup$ Consider $A_n$ to be the set of such sequence $(a_k)$ so that $a_k$ is fixed if $k\geq n$. It suffices to show that $A_n$ is countable for all $n$. $\endgroup$ – user99914 Feb 12 '15 at 7:20
  • $\begingroup$ You don't even need "the set of all infinite sequences with finite length". Simply map it to rational numbers in the range $[0,1)$. You may have to do some additional work on those infinite sequences which are eventually $0$ (for example, you can map them in the same manner, but then add the value of the finite sequence that comes before the infinite sequences of zeros. $\endgroup$ – barak manos Feb 12 '15 at 7:22
  • $\begingroup$ @barakmanos how do I construct a mapping to rational numbers? $\endgroup$ – grayQuant Feb 12 '15 at 13:14
  • $\begingroup$ @grayQuant: I wrote an answer below, but deleted it because it was not complete, and needed to be refined. You can have a look at it (assuming you can see deleted answers). $\endgroup$ – barak manos Feb 12 '15 at 13:18
  • $\begingroup$ @barakmanos I can't not enough rep $\endgroup$ – grayQuant Feb 12 '15 at 13:19
1
$\begingroup$

Given such a sequence $a:\mathbb{N}\to \mathbb{N}$ define, $$ f(a) = (a_0,a_1,a_2,...,a_k,c) $$ (I live is up to you to figure out what that means above).

Thus, we have constructed an injection $f:\text{const}\to F$, where $F$ are the finite sequences of the natural numbers and $\text{const}$ are the eventually constant sequences.

$\endgroup$
  • $\begingroup$ you are taking every element of the sequence and mapping it to F, correct? $\endgroup$ – grayQuant Feb 12 '15 at 12:59
  • $\begingroup$ @gray Mr gray, I am sorry for the confusion, I edited the post above. Hopefully it will make it clearer. $\endgroup$ – Nicolas Bourbaki Feb 12 '15 at 17:11
1
$\begingroup$

If you're already at the point where you accept that the finite sequences are countable, then you can simply say that the eventually constant sequences are accounted for by taking any finite sequence and then concatenating it with an infinitely repeated value.

I.e, every eventually constant sequence is equal to some $s^\frown x$ where $s\in\mathbb{N}^{<\mathbb{N}}$ and $x=\langle n,n,n,\ldots\rangle$ for some $n\in\mathbb{N}$.

Thus, you've got an injection from the eventually constant sequences into $\mathbb{N}^{<\mathbb{N}}\times \mathbb{N}$, which is countable since $\mathbb{N}^{<\mathbb{N}}$ and $\mathbb{N}$ are countable.

$\endgroup$
0
$\begingroup$

Let $$ A_n=\left\{(a)\in \Bbb N^{\Bbb N}\middle|\forall k\in\Bbb N: |a_k|\le N\land a_{n+k}=a_n\right\} $$ be the set of sequences bounded by $n$ and constant after element index $n$ (earlier included). Then all $A_n$ are finite and $A_n\subset A_{n+1}$ and the requested set is the limit $\bigcup_{n\in \Bbb N}A_n$ of this nested sequence.

$\endgroup$

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.