|
|
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), 323-338.
Dave L. Renfro
|
|
