9
$\begingroup$

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.

  • 1
    See also: http://math.stackexchange.com/questions/84180/finding-a-correspondence-between-two-sets2015-10-24

2 Answers 2

11

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.

  • 0
    @philmcole: Because you are showing that given **any** function $f\colon X\to\{0,1\}$, the set $A=\{x\in X\mid f(x)=1\}$ has the property that $f=\chi_{A}$. So every function can be realized that way.2017-10-29
3

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