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

How can I formalize that the function $$f:\mathcal{P}(A)\to(A\to \{0,1\})$$ is bijective? It seems clear to me but I don't know how to write a proof. Thanks in advance.

-
The first thing to do is make sure you understand what your function $f$ does. How about you walk us through that by editing your thoughts into the post? If you know how $f$ works, and you know what 1-1 means, the proof will write itself. –  rschwieb Jan 11 '13 at 16:55

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

-
Well, for every $\varphi:A\to\{0,1\}$ there exists $S = \{a\in A \,|\, \varphi(a)=1 \} \subseteq A$ s.t. $f(S) = \varphi$, right? –  V. Galerkin Jan 11 '13 at 17:19
@V.Galerkin: That’s exactly right: $\varphi=f\big(\{a\in A:\varphi(a)=1\}\big)$. –  Brian M. Scott Jan 11 '13 at 17:23

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

-
And @Brian gave the full answer while I was typing! :-) –  Peter Smith Jan 11 '13 at 17:06
Nice and complete too. +1 –  Babak S. Jan 11 '13 at 17:34