Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer
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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.