A connection between functions and powerset

Question

This a homework question.

There are $8$ possible functions $f : \{a, b, c\} → \{0, 1\}$. What's the connection between these functions and the power set of $\{a, b, c\}$ ?

All I can think of is the numbers are same? 8 possible functions and 8 sets in the power set. Is there some kind of relation between these?

Answer 1

Take one of those $8$ functions and consider the subset of $\{a, b, c\}$ which is sent to $1$ by that function.

Or in the other direction, take one of the $8$ subsets, and make a function by sending anything in that subset to $1$ and anything not in the subset to $0$.

Answer 2

For each subset $A$ of $\{1,2,3\}$, take the characteristic function

$$\chi_A : \{1,2,3\}\rightarrow\{0,1\}: x\mapsto \left\{\begin{array}{ll} 1 & \mbox{if }x\in A\\0& \mbox{otherwise}\end{array}\right.$$

These are all the functions you are asking for.

For instance, if $A=\{1,3\}$, then $\chi_A(1)=\chi_A(3)=1$ and $\chi_A(2)=0$.

If $A=\emptyset$, then $\chi_A(1)=\chi_A(2)=\chi_A(3)=0$, i.e., $\chi_\emptyset$ is the zero function.

If $A=\{1,2,3\}$, then $\chi_A(1)=\chi_A(2)=\chi_A(3)=1$, i.e., $\chi_{\{1,2,3,\}}$ is the all-1 function.

Answer 3

More general let $X$ be a set and let $\mathcal F$ denote the set of functions $X\to\{0,1\}$.

• Prescribe $\phi:\mathcal F\to\wp X$ by $f\mapsto f^{-1}(\{1\})$ where $f^{-1}(\{1\}):=\{x\in X\mid f(x)=1\}$.

• Prescribe $\psi:\wp X\to\mathcal F$ by $A\mapsto\mathbf1_A$ where $\mathbf1_A$ denotes the indicator function of set $A$.

Then $\phi\circ\psi$ and $\psi\circ\phi$ are identities, hence $\phi$ and $\psi$ are bijections.

So there is a one-to-one correspondence between elements of $\mathcal F$ and subsets of $X$.