next up previous
Next: Some Examples Done in Up: Lecture Notes Previous: Wednesday, April 19, 2000

Monday, April 24, 2000

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:


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

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

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!

Randall Holmes