# Infinite binary sequences countable set

I know that the set of all binary sequences is uncountable, and I'm asked to prove that the set of all binary sequences that are constant from a certain point ($$n\in\mathbb{N}$$) is countable, meaning the set: $$\{\eta:\eta\in\{0,1\}^{\mathbb{N}}\land\exists n\in\mathbb{N}\forall m>n(\eta(m)=\eta(n))\}$$ is countable. How does the fact that all binary sequences in this set are constant from a certain point make it countable?

• You could list them as follows: $0\overline0,0\overline1,1\overline0,1\overline1,10\overline0,10\overline1,11\overline0,11\overline1,100\overline0,100\overline1,101\overline0,101\overline1,110\overline0,110\overline1,111\overline0,111\overline1,...$; the list would have duplicates, but that's okay – J. W. Tanner May 31 at 21:55

HINT: For each $$n$$, the set of binary sequences that are constant from the $$n$$-th term on is finite; you should be able to write down its actual cardinality without much trouble.

• Can I look at $\{\eta\}$ as an infinite union of finite sets (each set in the size of $2^n$? – Gal Ben Ayun May 31 at 22:01
• @GalBenAyun: So you don’t yet have the theorem that the union of countably many countable sets is countable? – Brian M. Scott May 31 at 22:03
• I think the word that I was missing was union of countably many countable sets. It's countable because each subset in the union is determined uniquely by a natural number? – Gal Ben Ayun May 31 at 22:06
• @GalBenAyun: Yes: for each $n\in\Bbb Z^+$ you have a finite (hence countable) set of sequences that are constant from the $n$-th term on, and $\Bbb Z^+$ is countable. – Brian M. Scott May 31 at 22:08

Assume, $$E_n$$ be the collection of binary sequences which are constant after nth stage. $$|E_n| < 2^n \ \forall n \in \mathbb{N}$$.
and $$X$$ the collection of all the binary sequences which are constant after some stage. Then, $$X \subseteq \cup_{n \in \mathbb{N}} E_n$$ which is countable union of finite sets, hence, countable.

If $$\eta$$ has the binary number $$b$$ followed a string of all zeroes starting with the $$n^{th}$$, map $$\eta$$ to $$2b\in\mathbb N$$;

if $$\eta$$ has the binary number $$b$$ followed by a string of all ones starting with the $$n^{th}$$,

map $$\eta$$ to $$2b+1\in\mathbb N$$.

This is an injective function from to $$\{\eta\}$$ to $$\mathbb N$$, so $$\{\eta\}$$ is countable.