Cardinality of $\{0,1\}^\mathbb{N}$

Question

For if I understand this correctly, given any two sets X and Y, $card(X^Y)=cardX^{cardY}.$ However, from what I read, $\{0,1\}^{\Bbb N}$ is supposedly countable. It is also said that $2^{\aleph_0}>\aleph_0.$ How is this consistent? Are one of these two statements incorrect?

Answer 1

Yes, the statement "$\{0, 1\}^{\mathbb N}$ is countable" is incorrect. It is uncountable (by the standard diagonal argument).

Answer 2

The set $\{0,1\}^{\mathbb N}$ is uncountable, and in fact, you can construct a fairly intuitive surjective function from $\{0,1\}^\mathbb N$ to $[0,1]$ by mapping

$$(a_1,a_2,a_3,a_4,\dots)\mapsto 0.a_1a_2a_3a_4\dots_2$$

where the right side is a binary expansion, i.e.

$$0.a_1a_2a_3\dots = \frac{a_1}{2}+\frac{a_2}{4}+\frac{a_3}{8} + \cdots = \sum_{n=1}^\infty 2^{-n} a_n$$

It's easy to see that all numbers in $[0,1]$ (an uncountable set) are covered. Since only a countable number of numbers are covered more than once (and they are always covered no more than twice), it's easy to modify the function to a (not as nice looking) bijection, but that's not even neccesary if all you want to do is prove your original set is not countable.