next up previous
Next: Induction Proof Format

Induction Proofs for Recursively Defined Sets

These notes are intended to supplement the text by giving a definition of inductive proofs for recursively defined sets. A recursive definition of a set has three parts:
A basis telling what elements are in the set initially;
the recursive or constructor part: which tells how to add elements to the set given that a list of certain elements already are in the set;
and an extremal clause which is the legal fine print saying that all elements in the set follow from the basis and the recursive part.





Paul Beame
Fri Oct 23 10:05:51 PDT 1998