1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – J. W. Tanner May 31 at 21:55
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can I look at $\{\eta\}$ as an infinite union of finite sets (each set in the size of $2^n$? $\endgroup$ – Gal Ben Ayun May 31 at 22:01
  • $\begingroup$ @GalBenAyun: So you don’t yet have the theorem that the union of countably many countable sets is countable? $\endgroup$ – Brian M. Scott May 31 at 22:03
  • $\begingroup$ 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? $\endgroup$ – Gal Ben Ayun May 31 at 22:06
  • $\begingroup$ @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. $\endgroup$ – Brian M. Scott May 31 at 22:08
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\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.