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.