Show that $| \{ 0,1 \}^{A} | = | \mathcal P(A) |$

Question

Let $A$ be a set, and $ \left \{ 0,1 \right \}^{A}$ be the set of all functions $f$ from $A$ to $\left \{ 0,1 \right \}$

Show that $\left | \left \{ 0,1 \right \}^{A} \right | = \left | 2^{A} \right |$

We disccused this question on discrete math class the other day, and the teacher showed a rather nasty way of solving this using a very un-intuitive "hat trick"

I understand why the cardinalities of both sets are equal using combinatorics.

However, when the teacher showed a bijection I rather lost her..

Could any of you provide me with a practical and intuitive (Maybe a dummie explanation, or a step by step solution) bijection to solve this? I really want to understand the idea behind it.

edit:

$2^{A} = P(A)$

@Arthur: Not necessarily. Some texts seem to use $2^A$ as the official notation for a power set (though doing that in the same breath as one also uses $B^A$ for a set of functions seems rather cruel). — hmakholm left over Monica, May 11 '19 at 19:37
@vpam could you describe the "nasty" approach you didn't find satisfying, and say something about what you feel is nasty about it? — hmakholm left over Monica, May 11 '19 at 19:39
@HenningMakholm Well, I didn't really manage to get it through my mind properly, otherwise I would just post it here. Could we just start a fresh page and try approaching this in couple of ways? or it is too much to ask — GoodWilly, May 11 '19 at 19:42

score 3 · Accepted Answer · answered May 11 '19 at 19:38

3

An explicit bijection $$\varphi:\{f:A\to\{0,1\}\}\to\mathcal{P}(A)$$ is given by $$\varphi(f)=\{a\in A:f(a)=0\}.$$ Clearly, $\varphi$ is surjective: given $B\in\mathcal{P}(A)$, take $f(a)=0$ if $a\in B$ and $f(a)=1$ if $a\in A\backslash B$ and then $\varphi(f)=B$. The map $\varphi$ is also injective: for if $\varphi(f)=\varphi(g)$, we have $f(a)=0$ if $a\in \varphi(f)$ and $f(a)=1$ if $a\in A\backslash\varphi(f)$ and also $g(a)=0$ if $a\in\varphi(g)$ and $g(a)=1$ if $a\in A\backslash \varphi(g)$ but $\varphi(f)=\varphi(g)$ so $f=g$.

answered May 11 '19 at 19:38

RMWGNE96

801

Could you elaborate furthermore? Your proof is kinda mixed to the un-experienced eye – GoodWilly May 12 '19 at 09:25
1

We have two sets: the set of all maps from $A$ to ${0,1}$ (${f:A\to{0,1}}$) and the power set of $A$ ($\mathcal{P}(A)$). A map $f:A\to{0,1}$ is fully characterized by what it does to the elements of $A$. We construct a bijection $\varphi$ from the first set to the second by sending an arbitrary map $f:A\to{0,1}$ to the subset of $A$ of all elements that are mapped to $0$ under $f$, i.e. $\varphi(f)=f^{-1}(0)$. Then, we show that $\varphi$ is a bijection by showing that $\varphi$ is injective and surjective with ${f:A\to{0,1}}$ as domain and $\mathcal{P}(A)$ as co-domain. – RMWGNE96 May 12 '19 at 12:52

Show that $| \{ 0,1 \}^{A} | = | \mathcal P(A) |$

1 Answers1