2

I've gotten a lot of (constructive!) criticism by friends over this proof recently, so I've grown to feel it may be a bit lacking. I'd really appreciate it if someone could run through it and tell me if it's falling short of successfully proving what is required.

Question: It is not unreasonable to use $2^A$ to denote the set of functions from an arbitrary set $A$ to a set with $2$ elements (say $\{0, 1\}$). Prove that there is a bijection between $2^A$ and the power set of $A$.

Proof: Firstly, have $2^A$ be shorthand for $\{ 0,1 \}^A$, although note the proof is valid for any two element set.

Let $S$ denote an element of $\mathcal{P}(A)$, and have $a \in S$. Let $\textbf{1}_S: \mathcal{P}(A) \to 2^A$ be an indicator function defined as $$ \textbf{1}_S(a) := \begin{cases} 1 & \text{if $a \in S$} \\ 0 & \text{if $a\notin S$} \end{cases} $$ for all sets $S$. Each $\textbf{1}_S$ for some set $S$ is then equal to the graph of some function $f \in 2^A$, where the graph $\Gamma_{f}$ is given by $$ \{ (a,b) \in A \times \{ 0,1 \} \ | \ a\in A, \ b=f(a)\}.$$

Since no two subsets $S'$ and $S''$ are equal in $\mathcal{P}(A)$, they do not contain the same elements thus are mapped by $\textbf{1}_S$ to different function graphs in $2^A$, therefore $\textbf{1}_S$ is injective. Since $\mathcal{P}(A)$ contains all possible subsets of $A$, all possible mappings of the elements of $A$ are done through $\textbf{1}_S$, hence $\textbf{1}_S$ is surjective.

Therefore $\textbf{1}_S$ is a bijection and $\mathcal{P}(A) \cong 2^A$

Asaf Karagila
  • 393,674
Andrew Tawfeek
  • 2,555

1 Answers1

5

Like someone else has mentioned, it seems like it'd be easier to just show directly that $S\mapsto\mathbf{1}_S$ gives the bijection, rather than ever mentioning the graphs $\Gamma_f$.

For instance, if $\mathbf 1_S=\mathbf 1_T$ for $S,T\in\mathcal P(A)$, then $a\in S$ if and only if $\mathbf 1_S(a)=1$ if and only if $\mathbf 1_T(a)=1$ if and only if $a\in T$. In conclusion, $a\in S$ if and only if $a\in T$, so $S=T$.

For surjectivity, if you have $f:A\to\{0,1\}$, then define $S=\{a\in A\mid f(a)=1\}$, and you'll have $\mathbf 1_S=f$.

Edit: I'm noticing a mistake, and I'm not sure if it's a misunderstanding or a typo on your part. The indicator functions are functions $A\to\{0,1\}$, not $\mathcal P(A)\to 2^A$ as you've written. The mapping $S\mapsto\mathbf 1_S$ is the function $\mathcal P(A)\to 2^A$, and this is what you should be checking is bijective.

Alex Mathers
  • 18,509
  • I like this a lot! Thank you. Also, I understand now what you and @EthanBolker had meant, so I'll take out the needless reference back to $\Gamma_f$. :) – Andrew Tawfeek Mar 31 '17 at 17:48
  • @AndrewTawfeek Glad I could help! Let me know if you need anything clarified as you're going back over it – Alex Mathers Mar 31 '17 at 17:52
  • Regarding your new edit, I originally had a function $h: \mathcal{P}(A) \to 2^A$ defined as (for $S \in \mathcal{P}(A)$): $$h(S) = { (a,b) \ | \ b=0 \text{ if } a \notin S, \ b=1 \text{ if } a \in S }$$ but started using indicator functions because it was recommended to me (by a friend, not a professor). Should this be what's used instead here and shown is bijective? – Andrew Tawfeek Mar 31 '17 at 17:54
  • @AndrewTawfeek Please disregard my last comment. Technically, in your definition $h(S)$ is an element of $2^A$, using the "correct" definition of a function. However, I think defining $h(S)=\mathbf 1_S$, which is indeed also an element of $2^A$, amounts to the same exact thing, and I think the latter is easier to read. – Alex Mathers Mar 31 '17 at 18:06
  • I think I understand the problem now and I'll go work on showing the bijection of $\mathcal{P}(A) \to 2^A$. Thanks for all your help! (I take it what I originally showed was $\textbf{1}_A \cong f$?) – Andrew Tawfeek Mar 31 '17 at 18:15
  • 1
    @AndrewTawfeek yes that's precisely what you showed! And no problem. – Alex Mathers Mar 31 '17 at 18:48