Section 1.4: Induction and Recursion
Induction
Consider a set
and initial subset
. Suppose
is a set of operations on
. The set
we wish to construct must contain all elements
whenever
is a n-ary operation on
and
.
- From the top down. is closed under , iff for all , . is inductive iff it contains and is closed. is the intersection of all the inductive subsets of .
- From the bottom up. Let where or for some and . Then .
- is called the set generated from by the functions in .
(Induction principle) If
, where
is generated from
by
, and
,
is closed under
, then
.
Recursion
is freely generated from
by
iff a)
is bijective for all
, b) the range of
, the range of
, and
are pairwise disjoint for any
.
(Recursion theorem) If
is freely generated from
by
,
, and
, where for an
-ary operation
on
,
is an
-ary operation on
, then there is a unique function
such that a)
, and b) for
,
.
This is one of those theorems that seem obvious, until one need to prove it. See pages 54-57.
- In other words: if there is a rule how to paint each point of ( ), there are rules how to paint each combination of points of based on their colors ( ), and there is a unique way to construct each point of ( is freely generated from ), then all of can be painted in a determined way.
- The set of wffs is freely generated from the set of sentence symbols under the five building operations.