1
$\begingroup$

Is the set of all finite and countably infinite sequences over $\{0,1\}$ countable?

From my analysis, I think it is countable. I think of this as the set of all strings from a finite alphabet $\Sigma=\{0,1\}$, hence $\Sigma^*$. (is this a good assumption?).

I later show that I can count each string in the following order: $0$,$1$ (length $1$), $00$, $01$, $10$, $11$ (length $2$) and so on.

However, I am very confused from the initial requirement "finite and countably infinite sequences". Does my method account for the countably infinite strings?

$\endgroup$
2
$\begingroup$

Your solution for proving that $\Sigma^*$ is countable is correct. However the set $\Sigma^\omega$ of infinite sequences is not countable, since it is in bijection with the set of subsets of $\mathbb{N}$, which is not countable. See this question.

$\endgroup$
  • $\begingroup$ sorry, I am confused. so, is the set of all finite and countably infinite sequences over {0,1} countable? $\endgroup$ – revisingcomplexity Apr 28 '15 at 14:49
  • $\begingroup$ The set of all finite and countably infinite sequences over $\{0,1\}$ contains as a subset the set $\{0,1\}^\omega$ of countably infinite sequences. Since this subset is not countable, the set of all finite and countably infinite sequences over $\{0,1\}$ is also not countable. $\endgroup$ – J.-E. Pin Apr 28 '15 at 16:10

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.