5
$\begingroup$

I think $\{0,1\}^*$ represents all $0,1$-sequences, and $\{0,1\}^{\mathbb{N}}$ is the $0,1$-sequences with infinite length. So $\{0,1\}^{\mathbb{N}}$ is a subset of $\{0,1\}^*$. $\{0,1\}^*$ is countable, while $\{0,1\}^\mathbb{N}$ is uncountable.

It's really strange, because I can count the whole set and cannot when it comes to its subset! I don't know how to understand it. Who can save me? Thanks in advance.

$\endgroup$
  • 6
    $\begingroup$ You are wrong, $\{0,1\}^*$ does represent all finite 0, 1-sequences, so the set $\{0, 1\}^{\mathbb{N}}$ of infinite 0, 1-sequencces isn't a subset of it. No contradiction here. $\endgroup$ – vonbrand Mar 13 '13 at 10:44
11
$\begingroup$

The set of all $0$-$1$ sequences is uncountable. $\{0,1\}^*$ more commonly means the set of finite $0$-$1$ sequences, which is countable.

$\endgroup$
  • $\begingroup$ Why it's not countable? we can count it in this way: 1 - 0, 2 - 1, 3 - 00, 4 - 01, 5 - 10, 6 - 11 , 7 - 000, 8 - 001, 9 - 010... $\endgroup$ – Sayakiss Mar 13 '13 at 10:26
  • 6
    $\begingroup$ @Sayakiss What Chris means is, you have misunderstood the definition of $\{0,1\}^\ast$. $\{0,1\}^\ast$ is the set of all finite 0-1 sequences. Sequences of infinite length are not included. So $\{0,1\}^{\mathbb{N}}$ is not a subset of $\{0,1\}^\ast$. In fact, the two sets are disjoint. Now $\{0,1\}^\ast$ is countable, but $\{0,1\}^{\mathbb{N}}$ is not. $\endgroup$ – user1551 Mar 13 '13 at 10:43

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.