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.

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.

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

2 Answers 2

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

share|improve this answer
    
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.

share|improve this answer
    
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

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.