
Re: Devlin adn Recursion
Posted:
Nov 22, 2011 10:47 AM


Joe Niederberger wrote:
http://mathforum.org/kb/message.jspa?messageID=7613724
> I guess you didn't get the point Joshua  PA more or > less stands on its own. The Bourbakis no doubt would > insist on talking endlessly about "recurion principles" > and "inifintary objects" rather than take simple note > of the fact that, in PA, 3 * 4 amounts to 4 + 4 + 4.
What follows is a comment on the formal mathematics involved. This is not what I think school teachers should tell their students and, in most cases, this is not even what school teachers need to know.
It is my understanding that prior to stating something like 3 * 4 = 4 + 4 + 4 in Peano Arithmetic (PA), one has to define the functions + and * on the infinite set of pairs of natural numbers. Once these functions have been defined, fairly straightforward mathematical induction arguments (induction is essentially one of the PA axioms) can be used to prove statements such as "for each natural number n, 3*n = n + n + n", from which a universal instantiation then gives 3*4 = 4 + 4 + 4. Or you can skip proving the general result 3*n = n + n + n and give a (lengthy, if from first principles) direct proof that 3 * 4 = 4 + 4 + 4, although even in this case one needs to have the functions + and * defined in advance (and part of this "defining" process is a proof that they are functions from N x N into N), otherwise the statement to be proved is not yet a "well formed formula" in PA.
This subtle point about defining addition is given special mention in Edmund Landau's remarks "Preface for the Teacher" (dated 28 December 1929):
Edmund Landau, "Foundations of Analysis", translated by Fritz Steinhardt, Chelsea Publishing Company, 1930/1951, xiv + 134 pages.
The following is taken from Fritz Steinhardt's English translation of Landau's "Preface for the Teacher".
************************************************************** **************************************************************
My then assistant and dear colleague Privatdozent Dr. Grandjot (now Professor at the University of Santiago) was lecturing on the foundations of analysis and using my notebook as a basis for the lectures. He returned my manuscript to me with the remark that he had found it necessary to add further axioms to Peano's in the course of the development, because the standard procedure, which I had followed, had proved to be incomplete at a certain point.
On the basis of his five axioms, Peano defines x + y for fixed x and all y as follows:
x + 1 = x' x + y' = (x + y)',
and he and his successors then think that x + y is defined generally; for, the set of y's for which it is defined contains 1, and contains y' if it contains y.
But x + y has not been defined.
All would be well if  and this is not done in Peano's method because order is introduced only after addition  one had the concept "numbers <= y" and could speak of the set of y's for which there is an f(z), defined for z <= y, with the properties
f(1) = x f(z') = (f(z))' for z < y.
Dedekind's reasoning does follow these lines. With the kind help of my colleague von Neumann in Princeton I had worked out such a procedure, based on a previous introduction of ordering, for this book. This would have been somewhat inconvenient for the reader. At the last minute, however, I was informed of a much simpler proof by Dr. Kalmár in Szeged.
************************************************************** **************************************************************
Enderton (Chapter 4) gives a nice treatment of this issue by making use of a very carefully proved "Recursion Theorem on $\omega$".
See also the comments in Henkin (Section 8, p. 338).
Herbert B. Enderton, "A Mathematical Introduction to Logic", 2nd edition, Academic Press, 2001, xii + 317 pages.
Leon Henkin, "On mathematical induction", American Mathematical Monthly 67 #4 (April 1960), 323338.
Dave L. Renfro

