# Finding a correspondence between $\{0,1\}^A$ and $\mathcal P(A)$

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!

#### Solutions Collecting From Web of "Finding a correspondence between $\{0,1\}^A$ and $\mathcal P(A)$"

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

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

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.