On Page 100 of Naive set Theory by Halmos, He asserted that the cardinal number of the power set of a set $A$ is $2^a$ if $card(A)=a$, because "the proof is immediate from the fact that P(A) is equivalent to $2^a$"

However, we defined the cardinal of a set is the least element of the ordinals that are equivalent to $A$. How can we prove that $2^a$ is the least?

  • $\begingroup$ You can think about elements of $2^a$ as characteristic function on set $a$. $\endgroup$ – user52045 Nov 18 '13 at 1:25
  • 1
    $\begingroup$ @Newb: but the problem is you can't get a limit ordinal by doing this, and every infinite cardinal by definition is a limit ordinal. $\endgroup$ – Alex Nov 18 '13 at 4:30

There is an abuse of notation here that I think may be confusing you: The notation $2^X$ can refer to the set of all functions $X \to 2$, but when $X$ happens to be a cardinal it can also refer to the cardinality of this set of functions (in which case it is a cardinal by definition.)

Note that even if $X$ happens to be a cardinal the set of functions $X \to 2$ is not literally a cardinal, nor even an ordinal, except in the trivial case $X = 0$.

Letting $A$ be any set and letting $a = \text{card}(A)$, we have $$\text{card}(\mathcal{P}(A)) = \text{card}\big(2^A\big) = \text{card}(2^a)$$ where the first equality comes from considering characteristic functions and the second equality comes from a bijection from $A$ to $a$. If desired, the last step is to drop the "$\text{card}(\cdot )$" from $\text{card}(2^a)$ in accordance with the conventional abuse of notation, giving $\text{card}(\mathcal{P}(A)) = 2^a$.

Remark: For ordinals $\alpha$ and $\beta$ there is another meaning of $\alpha^\beta$, namely ordinal exponentiation. If $\alpha$ and $\beta$ are finite then the two meanings are the same modulo the aforementioned difference between a set of functions and its cardinality.

It can be proved by induction that $\mathcal{P}(\alpha)$ has the same cardinality as $2^\alpha$ in both the ordinal exponentiation and the cardinal exponentiation sense when $\alpha$ is finite, which may be what Newb's comment is alluding to. This equality breaks down at limit stages; ordinal exponentiation is continuous in the exponent and cardinal exponentiation is not.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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