# If $A$ is a set, then $\mathrm{card}(P(A)) = 2^{\mathrm{card} A}$.

Can anyone help me please (since I don't know how to work with Maps)? I looked online, but those proofs don't make any sense to me.

-
Induction is the easiest way to go. Have you learned how to prove by induction? –  anon271828 Mar 15 '13 at 23:55
Induction doesn't work when $A$ is not finite. –  Martin Brandenburg Mar 16 '13 at 0:00

In order to fully answer this question, first you need to understand what is cardinal exponentiation.

We define $|A|^{|B|}$ to be the cardinality of the set $\{f\colon B\to A\mid f\text{ is a function}\}$, which is often denoted as $A^B$. So we have that $|A|^{|B|}=\left|A^B\right|$. It is a good exercise to see that this definition is a good definition and if $|A|=|C|$ and $|B|=|D|$ then $\left|A^B\right|=\left|C^D\right|$.

So we have that $2$ is really just the cardinality of a set with two elements, say $\{0,1\}$. And so we wish to prove that $|\mathcal P(A)|$ is exactly $2^{|A|}$, or $\left|\{0,1\}^A\right|$.

The elements of $2^A$ are functions from $A$ into $\{0,1\}$, and we can think of each function as a huge set of switches, and when we enter the function $a\in A$ it tells us whether the switch is on or is it off. This is really saying whether $a$ is in a particular set or not. This set is defined by the function itself.

Therefore we define the function $F\colon2^A\to\mathcal P(A)$ as, $F(\pi)=\{a\in A\mid \pi(a)=1\}$. The function $F$ takes a function $\pi$ and returns the set of those elements of $A$ that $\pi$ returns $1$ for, that is "the switch is on".

Now it is up to you to show that this $F$ is a bijection. To see that, let me give you a hint that all the functions in $2^A$ have the same domains, and distinct functions with the same domain have some element that they disagree on (that is, $\pi(a)\neq\sigma(a)$ if $\pi,\sigma$ are such functions and $a$ is such element).

Also relevant:

How to Understand the Definition of Cardinal Exponentiation

-
Good answer. But about the last paragraph: One can just write down the inverse function (and verify that it is one). –  Martin Brandenburg Mar 16 '13 at 0:02
@Martin: Yes, that is another option. But either case is equally easy once you get them running. –  Asaf Karagila Mar 16 '13 at 0:05

For a given set $A=\{x_0,x_1,...,x_n\}$, you can see a part of a as a string over $\{0,1\}$. For example, for $A=\{x_0,x_1,x_2,x_2\}$, $0110$ is representing the sub set $\{x_1,x_2\}$ ($x_0$ is not present, $x_1$ is in the subset etc ...). Hence there are as much sub set in $A$ than string of length $Card(A)$ over $\{0,1\}$ hence exactly $2^{Card(A)}$ (numbers of binary of length $Card(A)$). Hence $Card(P(A))=2^{Card(A)}$.

I hope it helps.

-
And when $A$ is infinite? –  Asaf Karagila Mar 16 '13 at 0:10
then your answer is way better, no doubt about that :D –  wece Mar 16 '13 at 12:43