# How to show equinumerosity of the powerset of $A$ and the set of functions from $A$ to $\{0,1\}$ without cardinal arithmetic?

How to show equinumerosity of the powerset of $A$ and the set of functions from $A$ to $\{0,1\}$ without cardinal arithmetic?

Not homework, practice exercise.

-
– Martin Sleziak Oct 24 '15 at 4:51

For each subset $S$, define the characteristic function $\chi_S\colon A\to\{0,1\}$ by $$\chi_S(a) = \left\{\begin{array}{ll} 1&\text{if }a\in S,\\ 0&\text{if }a\notin S. \end{array}\right.$$ The map $S\mapsto \chi_S$ is one-to-one: if $S\neq T$, then there exists $x\in S\triangle T$; hence $\chi_S(a)\neq \chi_T(a)$.

The map is onto: given $f\colon A\to\{0,1\}$, let $S=\{a\in A\mid f(a)=1\}$. Then $\chi_S = f$.

This gives the desired bijection.

-
More-or-less the same answer: It is all about noticing that the maps $S\mapsto \chi_S$ and $A\mapsto\{a\in A\mid f(a)=1\}$ (between the sets $\mathcal P(A)$ and $\{0,1\}^A$) are inverse to each other. If a function has an inverse, then it is a bijection. (I added this comment because in some situations it might be easier to find the inverse function than to verify "bijectiveness" directly from definition. So I thought that it might be good to remind this possibility, too.) – Martin Sleziak May 24 '11 at 11:09

Arturo Magidin has given an answer in symbols. In words it might be something like:

For any subset $S$ of $A$ (i.e. element of the powerset) there is a unique function which sends each element of $S$ to $1$ and everything else in $A$ to $0$; conversely, for any function $f$ from $A$ to $\{ 0,1 \}$ there is a unique subset of $A$ which contains all the elements of $A$ sent to $1$ and none of those sent to $0$.

-