# Cardinality of all the functions from $\mathbb N$ to $\{0,1\}$.

Is it true to say that: $$|\{0,1\}^\mathbb N| = |\{0,1\}|^{|\mathbb N|} = 2^{\aleph_0}=\aleph$$

As I know the right part of the equation is true, but I don't know if the equations to it are allowed.

-
What is the "$=\aleph$" part all about? What is $\aleph$? – Trevor Wilson Feb 13 '13 at 20:23
$\aleph$ is the cardinality of $\mathbb R$ – Georgey Feb 17 '13 at 8:03

Yes, that is valid cardinal arithmetic. In fact, this nice algebraic manipulation was the reason why the "power set" notation exists.

The number of functions $f : \mathbb{N} \to \{0, 1\}$ is $\{0, 1\}^\mathbb{N}$, which is also the number of subsets of $\mathbb{N}$ (if $n$ is inside the subset then $f(n) = 1$, otherwise $f(n) = 0$), hence the power set cardinality $2^{|\mathbb{N}|}$.

It is worth noting that $2$, defined as an ordinal, is equal to $\{0, 1\}$. Nonnegative integers can be seen as the set of all nonnegative integers smaller than them. Hence, $\{0, 1\}^\mathbb{N} = 2^\mathbb{N}$!

-
It's quite comforting to learn those algebraic manipulations from a different angle in an advanced discrete math course :-) – Georgey May 27 '13 at 19:13

Yes. It is true, and it's fine to do that.

Recall the basics of cardinal exponentiation: $$\left|A^B\right|=|A|^{|B|}$$

Since $|\{0,1\}|=2$ and $|\mathbb N|=\aleph_0$, the equation holds.

-