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.

I got this question in homework:

Let $\{0,1\}^A$ the set of all functions from A (not necessarily a finite set) to $\{0,1\}$. Find a correspondence (function) between $\{0,1\}^A$ and $\mathcal P(A)$ (The power set of $A$). Prove that this correspondence is one-to-one and onto.

I don't know where to start, so I need a hint. What does it mean to find a correspondence? I'm not really supposed to define a function, right? I guess once I have the correspondence defined somehow, the proof will be easier.

Any ideas? Thanks!

share|improve this question
    
I think it's uncanny that I cannot find this question on the site. I would have bet a large amount of money on it being here. Good thing I didn't. :-) –  Asaf Karagila Nov 21 '11 at 19:50

4 Answers 4

up vote 2 down vote accepted

This is essentially the same as Martin and yuone's answers:

Fix a set $A$. For a function $f$ from $A$ to $\{0,1\}$, let $ A_f$ be the set of elements of $A$ that are mapped to 1 by $f$. That is, $a\in A_f$ if and only if $f(a)=1$.

Consider the map $\Phi(f) =A_f$.

Now if $f\ne g$, there is an $a\in A$ with $f(a)=0$ and $g(a)=1$ (or $f(a)=1$ and $g(a)=0$).

Then $A_f\ne A_g$. So $\Phi$ is one-to-one.

Now let $B\in{\cal P}(A)$. Define $f(x)=\cases{1,&x\in B\cr 0,&x\notin B }$.

Then $\Phi(f)=B$. This shows that $\Phi$ is onto ${\cal P}(A)$

share|improve this answer
    
I don't understand - why define a group of elements that are mapped to 1 (Af)? –  yotamoo Nov 21 '11 at 11:31
    
This gives the correspondence between $f$ and a subset of the power set of $A$. $f$ is determined by the elements of $A$ that get mapped to 1. –  David Mitra Nov 21 '11 at 11:39
    
Right, but there are so many other subsets in P(A). I fail to see how this proof includes them. It gives me a headache :) –  yotamoo Nov 21 '11 at 11:47
    
Yes, but the other subsets correspond to different functions. Any particular subset $B$ will define a function ($f(x)$ as in my post). And any function will give a subset ($A_f$). For each function $f$ in $\{0,1\}^A$, match it with the set $A_f$. This is my function $\Phi$. –  David Mitra Nov 21 '11 at 12:03
    
Think of it this way: Take the set $A$. How can you define a function from $A$ to $\{0,1\}$? Well, you could circle the elements of $A$ that get mapped to 1. The uncircled elements will be mapped to 0. This gives the rule for the function. But the circled elements also give a subset of $A$. So, matching $f$ with the set of circled elements gives the desired correspondence. –  David Mitra Nov 21 '11 at 12:07

For any function $f\in\{0,1\}^A$ try associating it with $f^{-1}(1)$ in $\mathcal{P}(A)$, that is, the subset of $A$ whose elements map to $1$ under $f$.

share|improve this answer
    
So, just to make sure: proving that for every f∈{0,1}A there exist an inverse g∈P(A) means that the correspondence between {0,1}A and P(A) is one-to-one and onto? –  yotamoo Nov 21 '11 at 10:51
    
@yotamoo Yes, it can be shown that a function is bijective (1-1 and onto) if and only if it is invertible. Be careful about which function you're dealing with, the function in question is one which maps a function to a set, and whose inverse should map a set to a function. –  yunone Nov 21 '11 at 10:55

What about $f:{\mathcal P (A)}\to {\{0,1\}^A}$ and $g:{\{0,1\}^A}\to{\mathcal P(A)}$ given by $$ \begin{align} &f(X)=\chi_X &\text{ for $X\subseteq A$,}\\ &g(h)=\{x\in A; h(x)=1\} &\text{ for $h:A\to{\{0,1\}}$,} \end{align} $$ where $\chi_X(x)=1$ for $x\in X$ and $\chi_X(x)=0$ for $x\notin X$, i.e. $\chi_X$ is the characteristic function of the set $X$.

Can you show that these two functions are inverse to each other?

NOTE: This is basically the same thing as yunone's answer, I've just added the inverse function too.

share|improve this answer

I'll try to say this without all the technicalities that accompany some of the earlier answers.

Let $B$ be a member of $\mathcal{P}(A).$

That means $B\subseteq A$.

You want to define a function $f$ corresponding to the set $B$. If $x\in A$, then what is $f(x)$? It is: $f(x)=1$ if $x\in B$ and $f(x) = 0$ if $x\not\in B$.

After that, you need to show that this correspondence between $B$ and $f$ is really a one-to-one correspondence between the set of all subsets of $A$ and the set of all functions from $A$ into $\{0,1\}$. If has to be "one-to-one in both directions"; i.e. you need to check both, and you need to check that the word "all" is correct in both cases.

share|improve this answer

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.