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.

V. Galerkin
  • 1,512
  • 3
    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

2 Answers2

6

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

Brian M. Scott
  • 616,228
3

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

Peter Smith
  • 54,743