# Prove $\{0, 1\}^{\mathbb{N}}$ is uncountable.

Prove that $\{0, 1\}^\mathbb{N}$ (the product of countably many copies of the two-point set) is uncountable.

-
....$\,2^{\aleph_0}\,$ ...? –  DonAntonio Feb 5 '13 at 20:12
Binary numbers? –  copper.hat Feb 5 '13 at 20:14
@Michael: If you're correcting the braces, why did you leave the ones after the \mathbb? It works perfectly well without any braces: $\{0,1\}^\mathbb N$. –  Asaf Karagila Feb 5 '13 at 20:43

$$\left|\{0, 1\}^\mathbb{N}\right| = \left|\{0, 1\}\right|^{|\mathbb{N}|} = 2^{\aleph_0} = \left|\mathbb{R}\right|$$

-
See also Cantor's Diagonal Argument if you haven't yet encountered it. –  amWhy Feb 5 '13 at 20:24
Do any of these answers make sense, Cornelius? –  amWhy Feb 5 '13 at 22:02

Hint: Show that $\{0,1\}^A$ is the same thing as $\mathcal P(A)$; and use Cantor's theorem to show that $|A|<|\mathcal P(A)|$. Deduce the wanted conclusion.

-

Hint: Cantor's Diagonal argument.

-