Tuesday, January 8, 2019

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



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



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$.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...