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

From: David C. Ullrich (ullrich_at_math.okstate.edu)
Date: 07/01/04 

Date: Thu, 01 Jul 2004 05:01:43 -0500

On Wed, 30 Jun 2004 16:00:30 -0500, David C. Ullrich
<ullrich@math.okstate.edu> wrote:

>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>.)

As an addendum: I didn't see immediately what to say
about your comment that further evidence the proof
is incorrect is provided by the fact that the proof
does not use the fact that 0 is not a successor
and s is 1-1. In fact the "wrong proof" _does_
depend on these two facts, if you write out the
details very carefully - the way it depends on
them is not mentioned explicitly in Landau,
but the proof _does_ need them, making this
another "gap" instead of an error:

Reverting to the previous notation because
it's simpler, we're showing that for every n
there exists p_n such that, among other things,

(*) p_{s(n)}(x) = p_n(s(x)).

We give p_0 explicitly and then define p_{s(n))
in terms of p_n. Now showing that (*) is
actually satisfied requires the fact that
0 is not a successor and s is 1-1: The fact
that our explicit definition of p_0 cannot
contradict (*) depends on the fact that 0
is not a successor, while deducing that (*)
holds for a given n depends on the fact
that s is 1-1; if we had s(n) = s(m) for
n <> m then our definition of p_{s(n)}
would not be well-defined.

>>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

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

David C. Ullrich

Relevant Pages