\magnification=\magstep1
\centerline{Mathematics 243 -- Mathematical Structures}
\centerline{A ``bijective proof'' that $\{1,2,\ldots,n\}$ has $2^n$ subsets}
\centerline{September 27, 2017}
\bigskip
\noindent
{\it Background}
\bigskip
Recall that a couple of days ago we showed by mathematical induction that
for all $n \ge 1$, $\{1,2,\ldots,n\}$ has $2^n$ subsets. Today we want
to see an explicit bijection between the subsets and a set of $2^n$ integer 
values, so we can see that we are directly ``counting the subsets.''  It will show
the same result we already know, but by a different method that does not use 
induction.  Mathematicians often look for different proofs of results because 
having more than one way to prove something often reveals interesting connections
or relationships that might not be visible otherwise!  The sort
of proof we will see in this discussion is called a {\it bijective proof} 
in the area of mathematics known as {\it combinatorics} -- the subject of 
the MATH 357 course offered every other year in the mathematics major here.  
\bigskip
\noindent
{\it Questions}
\bigskip
\item{(A)} To study subsets of $\{1,2,\ldots,n\}$, with enough thought, you
might come up with an idea like this:  {\it Every subset $S$ can be described
by giving a vector $v_S = (v_1,v_2,\ldots,v_n)$ where for each} $i$, $1 \le i \le n$, 
$$v_i = \cases{1 & if $i \in S$\cr
               0 & if $i \notin S$\cr}$$
(You might also think $1 = $ ``true'' and $0 = $ ``false'' for the truth value
of the statement $i \in S$.)  Write out the 8 subsets $S$ of $\{1,2,3\}$ and
their corresponding vectors $v_S$.  
\item{(B)}  Let ${\cal S}$ be the set of all subsets of $\{1,2,\ldots,n\}$ and 
Let ${\cal V}$ be the set of all length-$n$ vectors with entries either 0 or 1.
 Prove that the mapping $V : {\cal S} \to {\cal V}$
defined by $V(S) = v_S$ is a bijection (injective and surjective).  
\item{(C)}  How many possible length-$n$ vectors with all entries $0$ and $1$ are there?
(For now, just ``figure out'' what the answer should be.  We'll sketch a possible proof next.)
\item{(D)}  Here's a way to ``count'' the set ${\cal V}$ that you might not have
thought of.  For each vector $v = (v_1,\ldots,v_n) \in {\cal V}$, define an integer $N(v)$
by the rule
$$N(v) = v_1 + v_2\cdot 2 + v_3 \cdot 2^2 + \cdots + v_n 2^{n-1}$$
What are the $N(v_S)$ for the 8 vectors you found in part (A)?
\item{(E)} The mapping $N : {\cal V} \to {\bf N}$ defined by the formula in part B
defines a bijection between ${\cal V}$ and the subset $\{0,1,\ldots,2^n - 1\}$ in 
${\bf N}$.  Explain why using the notion of the {\it base}-2 or {\it binary} 
representation of integers.  If you have not seen this before, look it up online to 
see the idea (the Wikipedia article  ``Binary Number'' is a good source).  Explain
this in your own words.
\item{(F)}  To wrap things up, notice we have a bijection between the subsets ${\cal S}$ and
the vectors ${\cal V}$ given by part (B).  Then, in turn, there is a bijection between
${\cal V}$ and the set $\{0,1,\ldots,2^n-1\}$ given by part (E).  Explain why this
shows there is a bijection between ${\cal S}$ and the set $\{0,1,\ldots,2^n-1\}$.  
(Hint:  Think composition of functions.)
\bye
