next up previous
Next: Wednesday, April 19, 2000 Up: Lecture Notes Previous: Monday, April 17, 2000

Tuesday, April 18, 2000

This section is devoted to developing a counting principle for
``sequences of choices'' represented by trees.

Much of our time will be occupied by a careful definition of the concept

We recall some definitions of properties of relations.

(A,R,A) is 

i.  ``reflexive'' iff (Ax E A.x R x)

ii.  ``antisymmetric'' iff (Axy E A.((x R y & y R x) -> x=y))

iii.  ``transitive'' iff (Axyz.((x R y & y R z)-> x R z))

A relation which is reflexive, antisymmetric, and transitive is said
to be a ``partial order''.

iv.  ``connected'' iff (Axy.(x R y | y R x))

A connected partial order is said to be a ``linear order'' or a
``total order''.

Lemma (not proved):  If (A,R,A) is a partial order or a linear order,
and B c= A, then (B,(R ^ (BxB)),B) is also a partial order or linear order.
We call it the restriction of (A,R,A) to B; we may use the notation
R /| B for R ^ (B x B).

Definition: A partial order (T,<=(T),T) is called a ``tree'' iff for
each x E A, {y E T : y <=(T) x} is a finite set and the restriction of
(T,<=(T),T) to {y : y <=(T) x} is a linear order.  We also require
that there be an element r E A such that for all x E A, r <=(T) x; r
is called the ``root'' of the tree.

Notice that a tree can have only one root:  if r and s are roots of
a tree (T,<=(T),T), then r <=(T) s and s <=(T) r, from which r = s
by antisymmetry of partial orders.

Definition:  Let (T,<=(T),T) be a tree.

For each element x of A, we call the set {y E T : (x =/= y & y <=(T) x)} 
the set of ``ancestors of x'', and abbreviate this A_x (when the
identity of the tree is understood).

We say that x (an element of T) is at level n of the tree just in case
|A_x| = n; notice that this puts the root at level 0.  We use L_n to
denote the set {x E T : |A_x| = n} of elements of level n.

We say that y is a child of x iff x <=(T) y and |A_x| + 1 = |A_y|.

Lemma:  For each y, there is at most one x such that y is a child of x.
(We call such an x the parent of y; the root does not have a parent).

   Suppose otherwise.  Let u and v be two distinct parents of x.  Then
   we have u <=(T) x, v <=(T) x, u =/= v, and |A_u| = |A_v| = |A_x|-1.
   Note that there is exactly one element of A_u which is not in A_x.
   This element must be u itself.  Since v is in A_x, it must be in
   A_u.  By exactly the same argument, u must be in A_v.  But this
   implies by antisymmetry of <=(T) that u=v, which is a
   contradiction!  (I am actually cheating here -- I use a counting
   principle that I have not proved!  Can you identify it?)

Lemma:  The root of a tree does not have a parent; every other
element of the tree does.

   The set of ancestors of any element x of the tree is a finite
   linearly ordered set.  The root has no ancestors; every other
   element has a nonempty set of ancestors.  A nonempty finitely
   linearly ordered set must have a largest element in the linear
   order; the ``largest'' ancestor of x is easily seen to be the
   parent.  (Here I have definitely cheated; there are statements here
   which absolutely require proof, though they are obviously true).

Now we develop the kind of trees we need for our counting argument.

Definition: A uniformly branching tree is a tree (T,<=(T),T) such that
there is a function (N,b,N) (a function from the natural numbers to
the natural numbers, called the ``branching function'' of the tree)
such that for each natural number n, each element of level n of the
tree has exactly b(n) children.

We review the recursive definition of ``partial product of a
sequence''.  (We will formally discuss recursive definitions

Definition: For any function (N,f,N) from the natural numbers to the
natural numbers, we define Pi{i<0}(f(i)) as 1 and Pi{i<n+1}(f(i)) as
(Pi{i<n}(f(i)))*f(i).  Pi{i<n}(f(i)) is the product f(0)*...*f(n-1).

Now we can state and prove

Counting Property of Uniformly Branching Trees:  The size of level n
of a uniformly branching tree with branching function (N,b,N) is 

   We prove this by induction on n.  

   Clearly level 0 is of size Pi{i<0}(f(i)) = 1.

   Now suppose that level n is of size Pi{i<n}(f(i)).  For each
   element x of level n, consider the set C_x of children of x.  Every
   element of level n+1 has a parent, so belongs to some C_x and
   distinct C_x's are disjoint, because no element of the tree has
   more than one parent.  Each C_x is of size b(n), by definition of a
   uniformly branching tree.  There are Pi{i<n}(f(i)) sets C_x by ind
   hyp.  So level n+1 is the union of Pi{i<n}(f(i)) pairwise disjoint
   sets, each of size b(n), and so has (Pi{i<n}(f(i)))*b(n) =
   Pi{i<n+1}(f(i)) elements by the Basic Counting Principle for

Randall Holmes