▶ DAVID PIERCE, Induction and recursion. Mathematics Department, Middle East Technical University, Ankara 06531, Turkey.

E-mail: dpierce@metu.edu.tr.

Dedekind [1, II.130] makes an observation overlooked by Peano [7] and others: A set with an initial element and a successor-operation may admit proof by induction without admitting inductive or rather recursive definition of functions.

Landau [3, Preface for the Teacher] confesses to having confused induction with recursion. Henkin [2] works out the distinction. Yet the confusion continues to be made, even in textbooks intended for students of mathematics and computer science who ought to be able to understand the distinction. Textbooks also perpetuate related confusions, such as suggestions that induction and ‘strong’ induction (or else the ‘well-ordering principle’) are logically equivalent, and that either one is sufficient to axiomatize the natural numbers.

In an exercise in one noteworthy textbook [5, II.1, p. 38], the reader is invited to show the logical independence of the three axioms introduced by Dedekind, but commonly called by the name of Peano: (α) the initial element is not a successor, (β) the successor-operation is injective, and (γ) proof by induction works. But first, just after the introduction of these as axioms for the natural numbers, these numbers are used to index iterates of functions. This indexing is used later (II.2) to define addition and multiplication. But this indexing strictly requires all three of the axioms, normally in the equivalent form introduced only later still (II.11) and called the Peano–Lawvere Axiom. (Mention of this is absent from later editions, as [6]; it is called the Dedekind– Peano Axiom in [4, 9.1, p. 156].)

Landau implicitly (and Henkin explicitly) shows that addition and multiplication can be defined by induction alone. But the argument takes some work. (Strictly, the argument requires that these operations are being defined on a set. However, with more work, one can avoid this assumption.) If one thinks that the recursive definitions of addition and multiplication—n + 0 = n, n + (k + 1) = (n + k) + 1, n · 0 = 0, n · (k + 1) = n · k + n—are obviously justified by induction alone, then one may think the same for exponentation, with n^{0} = 1, n^{k+1} = n^{k} · n. However, while addition and multiplication are well-defined on ℤ/(n) (which admits induction), exponentiation is not; rather, we have (x, y) ↦ x^{y}: ℤ/(n) × ℤ/ϕ(n) → ℤ/(n). This is one example to suggest that getting things straight may make a pedagogical difference.

[1] Richard Dedekind, Essays on the theory of numbers. I: Continuity and irrational numbers. II: The nature and meaning of numbers, Dover, 1963

[2] Leon Henkin, On mathematical induction, The American Mathematical Monthly, vol. 67 (1960), no. 4, pp. 323–338

[3] Edmund Landau, Foundations of Analysis, Chelsea, 1966

[4] F. William Lawvere and Robert Rosebrugh, Sets for mathematics, Cambridge, 2003

[5] Saunders Mac Lane and Garrett Birkhoff, Algebra, Macmillan, 1967 [6] , Algebra, third ed., Chelsea, 1988

[7] Guiseppe Peano, The principles of arithmetic, presented by a new method, From Frege to Gödel, (Jean van Heijenoort, editor), Harvard, 1967