Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|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
add comment

2 Answers

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|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
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.