Section 1.4: Problem 1 Solution »

Section 1.4: Induction and Recursion


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 .


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.