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 ,
.