next up previous
Next: Monday, April 24, 2000 Up: Lecture Notes Previous: Tuesday, April 18, 2000

Wednesday, April 19, 2000

Instead of talking about the planned new content (which you can see
under ``Future Notes'' at the moment, if it doesn't have a date yet),
we talked about examples.

Example 1:  Exhibit a bijection which witnesses 2*3 = 6.

This is an exercise in reading definitions.

2*3 is defined as |2 x 3|.

|2 x 3| = 6 is equivalent to (2 x 3) ~=~ 6.

So we are looking for a bijection between 2 x 3 and 6.

2 x 3 = {0,1} x {0,1,2} = {(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)}.

6 = {0,1,2,3,4,5}.

A suitable bijection is {((0,0),0),((0,1),1),((0,2),2),
                              ((1,0),3),((1,1),4),((1,2),5)}.

Example 2:  Prove using the counting property of uniformly branching trees
that the natural number n (or any n-element set) has 2^n subsets.

The point here is to exhibit an actual tree which ``implements'' the
informal tree we can all draw.

The natural tree has the property that each node in the tree has two
children, representing the choice to include or not include an element
of the set associated with that level.

The first idea one might try is to associate with each node of the tree
at level m the subset of m = {0,1,...,m-1} including the elements 
included in the set so far.  This does not work because many nodes 
will be represented by the same set {}.

So instead of coding our choices by sets directly, we code them by
functions.  Our tree will be (T,<=(T),T), where

i.  T is the set of all functions with domain a natural number <= n
(i.e., a set {0,...,m-1} for m <=n) and codomain {0,1}.

ii.  The order on T will be the subset relation c= restricted to T.

We illustrate this for the tree with n = 2:


level 0:                          {}

                      ----------------------------
                      |                          |

level 1             {(0,0)}                     {(0,1)}


              ------------------            ---------------
              |                |            |             |

level 2    {(0,0),(1,0)}   {(0,0),(0,1)}  {(0,1),(1,0)}  {(0,1),(1,1)}


The four subsets of {0,1} are coded on level 2 by their ``characteristic
functions''.

The idea of a characteristic function is important enough to deserve
a definition.

Definition:  Fix a set A.  With each subset B of A we can associate
a characteristic function with range A and codomain {0,1} defined
thus:  (A,{(x,b) : x E A & (b=0 <-> ~x E B) & (b=1 <-> x E B)},{0,1})

It is easy to see that there is a precise one-to-one correspondence
between functions from A to {0,1} and subsets of A.

We need to verify the following points to get a proof that n =
{0,...,n-1} has 2^n subsets.

i.  We need to verify that the structure we have defined really is
a tree.  Suppose f is a function with domain a natural number m <= n and
range {0,1}.  The predecessors of f in the tree are those subsets
of f which are also functions with domain a natural number <= n and
range {0,1}.  It should be clear that these functions are just the
restrictions of f to sets {0,1,...,k} with k <= m, and these make
up a finite set linearly ordered by inclusion as required for this
to be a tree.

ii.  We need to verify that it is a uniformly branching tree.  The
elements of level m of this tree (for each m <= n) are the functions
from m = {0,...,m-1} to {0,1}.  An element of level m+1 which
is a child of one of these functions will be a superset of the
function at level m and will have domain m+1.  So the only choice
we have is what value to assign to the child function at m (the only
element of m+1 which is not also an element of m):  this value will
be 0 or 1, so there will be exactly two child functions.  This means
that our tree is uniformly branching with b(m) = 2 for all m <= n.

iii.  This means by our counting principle for uniformly branching trees
that the cardinality of level n of the tree is Pi{i<n}(2) = 2^n (the
product of n copies of 2).

iv.  The objects on level n of the tree are the characteristic functions
of subsets of n = {0,...,n-1}, and it is easy to see that there is a bijection
between characteristic functions of subsets and the corresponding subsets.

Exercise for Friday: Describe the tree which one would use to prove
that there are n! (n factorial) bijections from n to n.



Randall Holmes
2000-05-05