How is raising 2 to the power of a cardinality equivalent to taking the power set?

Question

I've read that for a set of cardinality $\aleph_n$, the cardinality of the power set of that set is $2^{\aleph_n}$, and the cardinality of the power set of that power set is $2^{2^{\aleph_n}}$, and so on. I understand the concept of a power set as the set of all subsets of a set, but I don't see how this is equivalent to this exponent definition. So could someone explain it?

Answer 1

If $\lambda$ and $\kappa$ are cardinals, $\lambda^\kappa$ represents the cardinality of the set of functions $f\!:A\to B$ where $A,B$ are fixed sets of cardinality $\kappa,\lambda$ respectively. (One needs to check this is independent of which specific sets $A,B$ we pick, of course.)

At least for finite numbers, this is something you may have encountered in a discrete mathematics context. For example, $9=3^2$ and indeed there are 9 functions $f$ from $\{0,1\}$ (a set of size $2$) to $\{a,b,c\}$ (a set of size 3), since there are 3 choices for what $f(0)$ is, and independently of this, there are 3 choices for what $f(1)$ is.

In this manner, $2^\kappa$ is the size of the set of functions $f\!:A\to \{0,1\}$, where $A$ is your favorite set of size $\kappa$. But these functions are precisely the characteristic functions of subsets of $A$: Given such an $f$, you identify it with the set of $a\in A$ such that $f(a)=1$. This gives us a bijection between the set of functions from $A$ to $\{0,1\}$ and the power set of $A$.

Answer 2

Hint: A function $f:X\rightarrow \{0,1\}$ defines a subset of $X$ and the set of such functions is $2^{\operatorname{card}(X)}$.

Answer 3

In short, every element of the set is either contained within a given subset, or it is not contained within a given subset. These 2 choices exist for every element of the set, giving $2^S$ choices (in the set-theoretic sense, as well as in the number-sense if $|S|$ is finite) overall.