# Finding a correspondence between two sets

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!

-
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

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

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

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

-

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.

-