Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
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
add comment

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.