Recursive Definitions The simplest kind of recursion is found in the definition we gave above of Pi{i<n}(f(i)). To see that it is simple, we abbreviate Pi{i<n}(f(i)) as F(i) and note that we defined it as follows: F(0) = 1 F(n+1) = F(n)*f(n). In general, the kind of recursive definition I will talk about first looks like this: F(0) = x F(n+1) = f(n,F(n)) where x and f are already defined. This kind of recursion is a device for defining a function from the natural numbers (to anything!) using information about each value to compute the next. The naive reaction might be that we are defining F in terms of F; that this is a circular definition. We show how to define F using our set theory. Let A be any set. Let x E A and let f be a function from NxA to A. We define F as {(n,y) E N x A : (Ac E P(N x A).((0,x) E c & (Auv.(u,v) E c ->(u+1,f(u,v)) E c)) -> (n,y) E c)}. In words, F is the intersection of all subsets of N x A which contain (0,x) and, if they contain (u,v), also contain (u+1,f(u,v)). The form of this definition is very similar to the form of the definition of the set N itself! It is clear that F, thus defined, is a set. We do not prove but simply state the Recursion Theorem: (N,F,A) as defined above is a function, and it is the unique function from N to A satisfying the equations F(0) = x and F(n+1) = f(n,F(n)) for all values of n. Uniqueness is easy: any function which satisfied the conditions would satisfy the conditions on classes c in the definition, and so would be a subset of F, and so would equal F. To prove that F is a function, prove that there is one and only one y such that (n,y) E F by mathematical induction on n; this is straightforward, if a bit tedious. There are more general kinds of recursive definition. For example, consider the Fibonacci numbers: 0,1,1,2,3,5,8,13,... defined by Fib(0) = 0 Fib(1) = 1 Fib(n+2) = F(n) + F(n+1). We can define Fib as the intersection of all subsets of N x N which contain (0,0) and (1,1) and, whenever they contain (n,a) and (n+1,b), also contain (n+2,a+b). This is a generalization of the kind of definition given above. Definition: A sequence is a function with domain N or domain some natural number n (a sequence with domain n has terms indexed by the natural numbers 0 to n-1). We define s_i when s is a sequence as s(i). The definition could be generalized to allow the domain to be any interval in the natural numbers (so we could start the indexing at 1 instead of 0, for example). The most powerful kind of recursion uses all values of F below n to define F(n). The values of F below n are described by the restriction F |\ {0,1,...,n-1} = F |\ n. The most general recursion theorem takes this form: Generalized Recursion Theorem: Let A be any set. Let G be any function from the set of all finite sequences with codomain A to A. Then there is a unique function F such that for all n E N, F(n) = G(F |\ n). The forms of recursion seen above are defined as follows: The usual recursion uses a G with the properties G({}) = x and, for nonempty s, G(s) = f(|s|-1,s(|s|-1)). The Fibonacci recursion uses a G with the properties G({}) = 0, G({(0,x)}) = 1, and, for s with at least two elements, G(s) = s(|s|-1) + s(|s|-2). I'm not planning to work directly with this formalization, necessarily, but it isn't bad for you to see it. All forms of recursive definition are intimately associated with proofs by mathematical induction. The Generalized Recursion Theorem should suggest proofs by complete induction (which we have not discussed so far). The Least Number Principle Definition: If (A,R,A) is a partial order and x E A, we say that x is a smallest element of A (with respect to R) if x R y for all elements y of A. Theorem: Any nonempty set of natural numbers has a smallest element (relative to the usual order on the natural numbers). Proof: Suppose that A is a set of natural numbers with no smallest element. We prove by induction that A is empty. Clearly 0 does not belong to A -- if it did, it would be the smallest element of A. So no number <= 0 belongs to A. Suppose that no number <= n belongs to A. Then if n+1 belonged to A it would clearly be the smallest element of A, which by hypothesis has no smallest element. So no number <= n+1 belongs to A. We have proved, for all natural numbers n, that no m <= n belongs to A, which is clearly enough to show that no natural number belongs to A. Counting and Subtraction We haven't formally defined subtraction yet, but that is an easy step in terms of our formal arithmetic. Definition: If n <= m, we have (by definition of <=) that there is a number k such that n+k=m. By the cancellation property of addition, proved in our formal arithmetic, this k is unique: if n+k = n+k' = m, then k = k'. We define n-m as this uniquely determined k. If n<m, we leave open what we might do. A common convention is to define n-m = 0 in this case. We know that if A and B are disjoint finite sets, that |A U B| = |A| + |B|. So we think we know that if A is a finite set and B is a subset of A, that |B| + |B-A| = |A|, so |A| - |B| = |B-A|. There is a hidden assumption here which we have not verified, which I now state as a Theorem: Any subset B of a finite set A is finite! It is sufficient to show that any subset of a natural number is finite (why?). Let m be a natural number, and let A be a subset of m. We need to define a bijection between some natural number k and the set A. We define a map as follows: if A is empty, we have A ~=~ 0 and the result is proved. If A is nonempty, it has a smallest element a by the Least Number Principle. We define F(0) as a. Otherwise we define F(0) as m. For each n, it is either the case that there are elements of A larger than F(n) or it is not the case. If it is not the case, we define F(n+1) = m. If it is the case, we define F(n+1) as the smallest element of A larger than F(n). F(0) = the smallest element of A, or m if there is no smallest element. F(n+1) = the smallest element of A greater than F(n) or m if there is no smallest element. is a valid recursive definition. We can prove by induction that for each n, either F(n+1) > F(n) or F(n+1) = m, and we can prove, also by induction, that for each n, any element of A <= F(n) is in the range of F. We can also prove F(n) >= n. So F(m) >= m (and so F(m) = m). There is a smallest k such that F(k) = m (Least Number Principle). We claim that F |\ k is a bijection from k to A. Don't forget to include proof that a linear order of length n contains one element!