Re: Rigorous proof of natural numbers' properties (by Edmund Landau).

From: David C. Ullrich (ullrich_at_math.okstate.edu)
Date: 06/30/04 

Date: Wed, 30 Jun 2004 16:00:30 -0500

On 30 Jun 2004 10:06:46 -0700, blackbur@math.umn.edu (Leonard
Blackburn) wrote:

>David C. Ullrich <ullrich@math.okstate.edu> wrote in message news:<u635e095i8kvh2gl6i2i6ig50lphv5gked@4ax.com>...
>> On Wed, 30 Jun 2004 10:01:39 +0200, ddtl <this.is@invalid> wrote:
>>
>
><snip>
>>
>> Uh, that book has been around for a _long_ time (and Landau was
>> an extremely careful writer to begin with). If you think one
>> of the proofs is not valid you're missing something (perhaps
>> not entirely your fault, probably it would be written in
>> different language today).
><snip>
>
>Be careful Professor Ullrich. Landau's book does indeed contain a fatal
>error in the proof of the existence of an addition function. I admit I
>only briefly skimmed this thread, but I can't help diving in right now
>before reading it carefully, as this very issue arose for me two years
>ago. At the University of Minnesota, Professor Max Jodeit had been giving
>a course based in part on Landau's book (the one in question). He had
>been teaching the addition theorem as Landau had presented it for some
>time. I was his teaching assistant in 2002. I noticed the serious
>error in the proof right after having been doing a lot of logic and
>set theory including learning various recursion theorems (like the one
>in H. Enderton's book _A Mathematical Introduction to Logic_. I pointed
>out the error to Professor Jodeit, and he did not believe me for more
>than a month of debate. But in the end he came to complete agreement with
>me and he now teaches a correct proof based on a recursion theorem for
>the natural numbers as given in H. Enderton's _Elements of Set Theory_.
>In that book, Enderton even mentions that there are some erroneous proofs
>of the addition theorem in print. Landau's is one of them. Enderton
>mentions that if a proof does not utilize the Peano axioms that 0 is not
>in the range of the successor function and that the successor function is
>one-to-one, then the proof cannot be correct. See p. 76 in _Elements of
>Set Theory_.
>
>For my discussion of Landau's error go to
>
> http://www.math.umn.edu/~jodeit/course/Math3283S02.html
>
>which is Professor Jodeit's course page and click on this link near the
>bottom:
>
> "Leonard Blackburn's Notes and Comments on the Addition Theorem."
>
>In this document, I've written everything but the first paragraph (written
>by Professor Jodeit). I don't agree with the emphasis on the proof being
>ok except for missing justification that is expressed in that paragraph.

I _really_ don't think that the sort of issue discussed there has
anything at all to do with what's confusing the OP (see my reply
to Michael Barr for more on that.)

I don't know exactly which gap he had in mind, but I do agree that
it's correct except for a gap. Tell me whether what I see as the
gap is the same as what he said the gap was:

(Yes, the "first error" is certainly an error, but it seems like,
at least _if_ we settle the questions regarding the "second error"
then the first error is trivial to fix, we just add uniqueness to
what we prove by induction. So we talk about the second error:)

I don't see your point when you say "We cannot define the set
p_s(n) in terms of a set p_n which we do not know exists
in the first place. I know that some readers would object to
this by saying that we are, in the course of our proof by
induction, _assuming_ that the set p_n exists. But this is
just an attempt to cleverly disguise a definition by
induction" [I wish people would talk about definitions
by "recursion" instead of by "induction", to keep the
two separate, by the way.]

Yes, I _do_ object by saying that - you _say_ that this
is just an attempt to disguise a definition by induction,
but it looks to me like a perfectly valid _proof_ by
induction.

I would change the notation to clarify what I see as
the gap. Instead of showing "For every n there exists
p_n such that [etc]" let's say we're proving that
"for every n there exists p such that [etc]". If you
put it that way then I simply don't see what the
problem is with the proof of this fact by induction.

Now, the reason I suggest we change the notation has
to do with where I see the gap: If we call that
function "p_n" then it looks like we've defined
a _sequence_ of functions. It seems to me that
we _do_ have a perfectly valid proof by induction
that for every n there exists a unique function
p such that [etc]. It's in jumping from the
existence of a unique p such that [etc], for
every n, to the existence of a single _sequence_
(p_n) such that for every n [etc] that seems
like a gap to me.

I bet that's the gap your professor complained about?

And come to think of it, the same gap does occur in
the proof that for every n there exists p such that
[etc]. I'm not saying I see any problem with the
induction step, using the existence of p such
that [etc(n, p}] to deduce the existence of q such
that [etc(s(n), q]; the gap is getting the values
of p(j) that we've defined one by one to fit
together into a single function p.

(And come to think of it, it's _possible_ that
I'm actually agreeing with you here, except
of course wrt the relevance of all this to
the OP's question. If I _am_ agreeing with
you I didn't follow what you wrote<g>.)

>The matter is also very briefly discussed in version 5 (?) of the Peano
>Postulates links.
>
>I hope this document also helps the OP.
>
>Sincerely,
>Leonard Blackburn

************************

David C. Ullrich

Relevant Pages