David Pierce: Induction and Recursion

D. Pierce, Induction and Recursion, The De Morgan Journal, 2 no. 1 (2012),  99-125.

From the Introduction:

In mathematics we use repeated activity in several ways:

  1. to define sets;
  2. to prove that all elements of those sets have certain properties;
  3. to define functions on those sets.

These three techniques are often confused, but they should not be. Clarity here can prevent mathematical mistakes; it can also highlight important concepts and results such as Fermat’s (Little) Theorem, freeness in a category, and Goedel’s Incompleteness Theorem.
The main purpose of the present article is to show this.

In the `Preface for the Teacher’ of his Foundations of Analysis of 1929, Landau discusses to the confusion just mentioned, but without full attention to the logic of the situation. The present article may be considered as a sketch of how Landau’s book might be updated.

One thought on “David Pierce: Induction and Recursion

  1. A radical approach to the Peano arithmetic was used in the course of calculus which I took as a first year student of the Novosibirsk University: the existence of reals \(\mathbb{R}\) was postulated, and then the induction property of natural numbers deduced. I quote the following from the textbook written by my lecturer, Gleb Pavlovich Akilov (G. P. Akilov and V. P. Dyatlov, Foundations of Mathematical Analysis. Nauka, Novosibirsk, 1980 (in Russian)).

    Consider the map \(s: x \mapsto x+1\) of \(\mathbb{R}\) into itself. A subset \(A \subseteq \mathbb{R}\) is inductive if \(1\in A\) and \(s[A] \subseteq A\). Obviously, \(\mathbb{R}\) is inductive and the intersection of all inductive subsets of \(\mathbb{R}\) is inductive and is the smallest (with respect to inclusion) inductive subset of \(\mathbb{R}\). Its elements are called natural numbers and the set is denoted by \(\mathbb{N}\).

    Hence we can say that the set of natural numbers is the smallest of all subsets \( A \subseteq \mathbb{R}\) containing \(1\) and such that \(A+1 \subseteq A\). In particular, if a subset \(M \subseteq \mathbb{N}\) is inductive then \(M=\mathbb{N}$. This statement is called the induction principle.

    Note a few application of the induction principle.

    IV. \(\mathbb{N} + \mathbb{N} \subseteq \mathbb{N} \).

    [I skip the proof.]

    V. Let \(m\) and \(n\) be natural numbers such that
    \[n \le m \le m+1.\] Then either \(m=n\) or \(m=n+1\).

    [Again, I skip the proof, but it uses (postulated) linear ordering of \(\mathbb{R}\).]

    And, after some further development, comes the pride of place, the principle of construction by induction:

    Theorem 1(5.I) Assume that we are given a set \(X\) and a sequence of maps \(\{\phi_n\}\) from |(X\) to \(X\) such that \[{\rm Domain}(\phi_{n+1}) \supseteq {\rm Range}(\phi_n)\] for every \(n\in \mathbb{N}\). Then if \(x \in {\rm Domain}(\phi_1)\) then there exists a unique sequence \(\{x_n\}\) of elements of the set \(X\) such that \[x_1=x,\quad x_n \in {\rm Domain}(\phi_n),\quad x_{n+1} = \phi_n(x_n)\quad (n\in \mathbb{N}).\]

    This theorem then was used to define power functions \[ x \mapsto x^n\] for natural exponents \(n\); proofs, by induction, that \[ x^mx^n = x^{m+n} \mbox{ and } (x^m)^n = x^{mn}\]
    were left to students (readers) as exercises.

Leave a Reply