Bijection $f:\mathcal{P}(A)\to(A\to \{0,1\})$

Solution 1:

I’ll do most of it and leave the last bit for you; ping me if you get stuck.

First you actually have to specify the function $f$: for each $S\in\wp(A)$ you want $f(S)$ to be the function

$$f(S):A\to\{0,1\}:a\mapsto\begin{cases} 1,&\text{if }a\in S\\ 0,&\text{if }a\notin S\;. \end{cases}$$

This is the indicator or characteristic function of $S$, often denoted by $1_S$ or by $\chi_S$, so for short I’ll write $f(S)=1_S$.

To prove that $f$ is a bijection, you must show that it is both injective and surjective. To show that it’s injective, suppose that $S,T\subseteq A$ and $f(S)=f(T)$; we want to show that $S=T$. We have $1_S=1_T$, meaning that for each $a\in A$, $1_S(a)=1_T(a)$. Suppose that $1_S(a)=1_T(a)=1$; then $a\in S$ and $a\in T$. Now suppose that $1_S(a)=1_T(a)=0$; then $a\notin S$ and $a\notin T$. In other words, for each $a\in A$ we have $a\in S$ if and only if $a\in T$, and hence $S=T$, as desired.

To show that $f$ is surjective, let $\varphi:A\to\{0,1\}$ be any function. Can you write down a description in terms of $\varphi$ of the set $S\subseteq A$ such that $f(S)=\varphi$?

Solution 2:

Which function do you have in mind? As I read that notation, it just says $f$ is $a$ function with domain $\mathcal{P}(A)$ and codomain the functions from $A$ to $\{0, 1\}$. And there are lots of functions with that domain and codomain which aren't bijections!

However, of course there do exists bijections with that domain and codomain. Take, for a canonical example, the function defined as follows

For $S \in \mathcal{P}(A)$, i.e. $S \subseteq A$, map $S$ to its characteristic function, i.e. the function $F$ defined by $c_S(x) = 1$ iff $x \in S$, and $c_S(x) = 0$ otherwise.

Now you have a definite map $f$ in view, showing it is a bijection is easy!

[Of course, now you have one bijection you can find more: for a start, you could swap the values 0 and 1, or -- if you are perverse -- you could compound with a permutation of the set $A$.]