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.