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
``tree''.
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
tomorrow).
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
Pi{i<n}(b(i)).
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
Multiplication.