[HM] mathematical induction
Carlos Cesar de Araujo (lavarini@digitus.com.br)
21 Mar 99 16:28:04 -0500 (EST)
This note is a hasty attempt to answer the question about the first
to formalize mathematical induction.
"Mathematical induction" has a fascinating history really. I am still
waiting for a complete discussion of it, one which would include not
only the names of Euclid, al-Karaji, Levi ben Gerson, Maurolycus,
Pascal, Fermat, Wallis, Jacob Bernoulli, De Morgan, Grassmann, Frege,
Dedekind, Peano, Poincare' and Russell, but of Padoa, Pieri, Hilbert,
Skolem, von Neumann, Landau, Henkin, Shepherdson and Moschovakis as
well.
Despite all these names, Richard Dedekind was the first man who
formalized the principle in a clear, elegant, rigorous and "modern"
set-theoretical fashion. This he did in his Was sind und Was sollen
die Zahlen? [VI, Definition 71], first published in 1887 after "a
first rough draft which several mathematicians examined" and which was
prepared "in the years 1872 to 1878". He understood completely, more
than any of his predecessors or contemporaries, what "volstandige
Induktion" ("complete induction", in his terminology) was all about.
After him, I would rank Frege and then Peano in discernment as to the
matter. It is important to stress the adjective "set-theoretical"
above, because Thoralf Skolem (another giant) was the first who saw
clearly the huge difference between the principle of mathematical
induction in Dedekind's universe of sets and in a dry first-order
setting.
Well, after reading an article by H. C. Kennedy entitled "The origin
of modern axiomatics: Pasch to Peano" (Amer. Math. Monthly, 1972, pp.
133-136) I became convinced that "Peano's discovery of the postulates
for the natural numbers was entirely independent of the work of
Dedekind, contrary to what is often supposed". But Dedekind rushed
into the problem much more deeply. For instance, in Fraenkel's
"Abstract Set Theory" (1952) we read:
"(...) mathematical induction is used not only for proving
propositions but also in order to define relations (...). A classical
instance, known at least since Peano, is the definition of the
addition of two natural numbers (...) for many decades this fact
helped to create the conviction that our rule constitutes a complete
definition (...) As early as 1887 R. Dedekind pointed out the
necessity of providing an adequate basis for inductive definition
(...) and in [IX, "126. Theorem of the definition by induction"] such
a basis is given in full rigor (...) For forty years, however, no
attention was paid to these remarks, and when J. von Neumann and E.
Landau independently raised the matter, they met with general surprise
and even with some opposition."
Neither Peano nor Frege, who were both in Cantor's paradise, had at
their disposal anything like "Dedekind's powerful Theorem 126" (in
Heijenoort words). As Haskell Curry said in his "Foundations of
mathematical logic", Dedekind is "the grand-father of present-day
recursive arithmetic". (The "father", I suppose, is Skolem.) In
summary, Dedekind was the first to see that the principle of
mathematical induction does not itself justify "definitions by
mathematical induction".
Apropos of Dedekind's work on induction, Hilbert said in 1904 (after
mentioning Frege):
"(...) for the first time he offered a construction of the theory of
integers, and in fact an extremely sagacious one. However, I would
call his method transcendental insofar as in proving the existence of
the infinite he follows a method that (...) I cannot recognize as
practicable or secure (...)".
But let us turn our attention, for a moment, to Fefermann's "The
Number Systems" (1964), Chapter 3, where one can see:
3.1. Definition. By a Peano system ...
3.2 Axiom. There exists at least one Peano system.
3.4. Theorem. [Definition by induction.]
3.5. Any two Peano systems are isomorphic.
Well, we can see all that in Dedekind's booklet MODULO the following
main differences: (1) he tried to prove 3.2 above by "proving" that
"There exist infinite systems" through his "meine Gedankenwelt". In
this he failed, as was stressed by many (Hilbert, Keyser, Russell,
Zermelo). (2) for him a function was not a set of ordered pairs; that
is why (3) he did not reach immediately at 3.4 (he developed order
theory first), but his proof is, as today, essentially a process of
"gluing" partial functions.
Later, Zermelo was forced to add an "axiom of infinity" to fill the
gap. We can say that, MODULO the existence of an infinite set in a
naive set theory, Dedekind's work was logically impeccable.
See also my entry "CHAIN" in Jeff Miller's web page.
Carlos Cesar de Araujo.