# A set $\,\{0,1\}^*$ is countable , but its subset $\,\{0,1\}^{\Bbb N}\,$ is uncountable?

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.

• 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. – vonbrand Mar 13 '13 at 10:44

The set of all $0$-$1$ sequences is uncountable. $\{0,1\}^*$ more commonly means the set of finite $0$-$1$ sequences, which is countable.
• @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. – user1551 Mar 13 '13 at 10:43