Ordinary Induction

Ordinary induction can be viewed as a special case of this. The set of positive integers N can be defined recursively:
Basis
Constructor If then .
Extremal Clause The usual

A recursive proof with respect to this definition of N consists of proving P(1) and that for any if P(n) is true then P(n+1) must be true, i.e. and this is exactly what we do for ordinary induction.

(Another piece of intuition as to why recursive proofs work is to think of the set

The above proof shows that 4 and 10 are in and that for any x and y in , both x+y and x-y are in . Thus satisfies essentially the same recursive definition as S does. Therefore .)

Another example: Here we prove something about the functions defined on elements of a recursively defined set S.

We can define the set B of all binary trees by the following two rules:

BASIS: `` '' is a binary tree

CONSTRUCTOR: If and are binary trees then so is:

We can define a couple of functions on binary trees:

Define by: and and define by: and where T is the tree:

Now we want to prove that for all , .