Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 3 down vote accepted

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}$!

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.