Section 1.4: Induction and Recursion

Induction

Consider a set $U$ and initial subset $B\subseteq U$ . Suppose $\mathcal{F}$ is a set of operations on $U$ . The set $C$ we wish to construct must contain all elements $f(a_{1},...,a_{n})$ whenever $f\in\mathcal{F}$ is a n-ary operation on $U,$ and $a_{1},...,a_{n}\in C\cup B$ .

From the top down. $S\subseteq U$ is closed under $\mathcal{F}$ , iff $f(a_{1},\ldots,a_{n})\in S$ for all $f\in\mathcal{F}$ , $a_{1},\ldots,a_{n}\in S$ . $S$ is inductive iff it contains and is closed. $C$ is the intersection of all the inductive subsets of $U$ .
From the bottom up. Let $C_{n}=$ $\{$ $x_{n}|\exists<x_{1},\ldots,x_{n}>$ where $x_{i}\in B$ or $x_{i}=f(x_{j_{1}},\ldots,x_{j_{k}})$ for some $f\in\mathcal{F}$ and $j_{1},\ldots,j_{k}<i$ $\}$ . Then $C=\cup_{n}C_{n}$ .
$C$ is called the set generated from $B$ by the functions in $\mathcal{F}$ .

(Induction principle) If $S\subseteq C$ , where $C$ is generated from $B$ by $\mathcal{F}$ , and $B\subseteq S$ , $S$ is closed under $\mathcal{F}$ , then $S=C$ .

Recursion

$C\subseteq U$ is freely generated from $B$ by $\mathcal{F}$ iff a) $f|_{C}$ is bijective for all $f\in\mathcal{F}$ , b) the range of $f|_{C}$ , the range of $g|_{C}$ , and $B$ are pairwise disjoint for any $f,g\in\mathcal{F}$ .

(Recursion theorem) If $C\subseteq U$ is freely generated from $B$ by $\mathcal{F}$ , $h:B\rightarrow V$ , and $t:\mathcal{F}\rightarrow\mathcal{G}$ , where for an $n$ -ary operation $f\in\mathcal{F}$ on $U$ , $t(f)$ is an $n$ -ary operation on $V$ , then there is a unique function $\overline{h}:C\rightarrow V$ such that a) $\overline{h}|_{B}=h|_{B}$ , and b) for $f\in\mathcal{F}$ , $\overline{h}(f(x_{1},\ldots,x_{n}))=(t(f))(\overline{h}(x_{1}),\ldots,\overline{h}(x_{n}))$ .

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 $B$ ( $h$ ), there are rules how to paint each combination $f$ of points of $C$ based on their colors ( $t(f)$ ), and there is a unique way to construct each point of $C$ ( $C$ is freely generated from $B$ ), then all of $C$ 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.

Subpages

Section 1.4: Induction and Recursion

Section 1.4: Induction and Recursion

Induction

Recursion