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?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ sorry, I am confused. so, is the set of all finite and countably infinite sequences over {0,1} countable? $\endgroup$
    – revisingcomplexity
    Apr 28, 2015 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, 2015 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.