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

From: Leonard Blackburn (blackbur_at_math.umn.edu)
Date: 06/30/04 

Date: 30 Jun 2004 10:17:50 -0700

ddtl <this.is@invalid> wrote in message news:<dc83e01tftfm1v5s8rhgvnn70cmlrbc4tp@4ax.com>...
> Hello,
>
>
> Hello,
>
> There is a book written by Edmund Landau, called "Foundations of Analysis",
> which rigorously proves properties of real/complex numbers using
> Peano's 5 axioms for natural numbers as a foundation on which the proofs are
> built.
>
> Here are the axioms (as I don't have an English translation of the book,
> all the quotes are translated by me. '!=' means 'not equal'):
>
> 1) 1 is a natural number.
> 2) For every natural number x, there is exactly another natural number
> called x's successor, denoted as x'
> 3) 1 != x'
> 4) If x' = y', then x = y
> 5) If set of natural numbers X has the following properties:
> a) 1 belongs to X
> b) if x belongs to X, then x' also belongs to X
> then all natural numbers belong to X.
>
>
>
> The first 3 theorems have a fairly easy proofs, so I just quote
> the theorems themselves:
>
> 1) If x != y then x' != y'
> 2) x' != x
> 3) If x != 1, then exists such a "u" for which x = u'
>
>
> What I don't understand, is the proof to the 4th theorem:

Good, because Landau's proof is wrong.

>
> "Theorem 4, also Definition 1:
> For every couple of natural numbers x and y it is possible to find a natural
> number, and only one natural number, denoted x+y (+ read: plus), so
> that:
> 1) x + 1 = x' for every x
> 2) x + y' = (x + y)' for every x and for every y
>
> x+y called the sum of numbers x and y, or the number obtained by addition
> of y to x"
>
> The problem already begins when I try to understand where is a definition
> and where is a theorem.

Let me clarify. The Theorem can be restated as follows (where N denotes
the set of natural numbers):

"There exists a unique function + : N x N -> N such that (1) and (2)
(as you've written them above) hold."

There is no definition in this theorem. It is about the existence and
uniqueness of a function. Although, some people take properties (1) and
(2) as a definition of addition. This is legitimate once you proof something
called the Recursion Theorem. (1) and (2) define addition by recursion.
But Landau is attempting to be as rigorous as possible and to start from
first principles, so we won't allow him the Recursion Theorem.

> As I understand that definition/theorem, it means
> the following:
>
> 1) We define a word (and notification) "addition" - operation which maps
> couples of natural numbers to other natural numbers.
> 2) We define laws of such a mapping: x + 1 = x' and x + y' = (x + y)'.

No. You prove that there is an addition function that satisfies those
laws.

> 3) Theorem (a): addition is possible for every couple of natural numbers
> x and y
> 4) Theorem (b): for every couple of natural numbers x and y, the addition
> will produce one and only one natural number.
>
>

No. Take my interpretation of the theorem above.

> Now, the biggest problem is the proof of Theorem (a) (I didn't understand
> the second proof (for Theorem (b)) at all, so I don't even know what
> to ask about it :( ). It goes like that:
>
>
> "Let's show that for each x it is possible to find x+y for each y so, that
> x + 1 = x'
> and
> x + y' = (x + y)' for every y.
>
> Let X be a set of x for which it is possible to perform an addition.
> 1) for x = 1, y' has the required properties.
>
> Indeed:
> x+1 = 1' = x'
> x+y' = (y')' = (x+y)'
> Which means that 1 belongs to X
>
> 2) let x belong to X, so that x+y defined for all y. Then:
> x'+y=(x+y)'
> gives us the required sum for x'.
>
> Indeed:
> x'+1=(x+1)'=(x')'
>
> and
> x'+y'=(x+y')'=((x+y)')'=(x'+y)'
> Which means that x' also belongs to X. For that reason, X contains
> all natural numbers"
>

I think you would do best to scrap Landau's incorrect proof and read
another like that found in H. Enderton's _Elements of Set Theory_ (in which
the author mentions that there are other erroneous proofs in print).

Or more quickly, read my assesment of Landau's proof and a correction of
it (which is a rewriting of what Enderton wrote). Go to

  http://www.math.umn.edu/~jodeit/course/LBonADDed.pdf

I hope that helps,
Leonard Blackburn

>
> For example, how do we get from x'+y' to (x+y')'? It is indeed fairly
> obvious - according to definition, x+1=x', and x belongs to the set X.
> So we substitute x'<=>x+1:
>
> x'+y'=x+1+y'
>
> Then: x+1+y'=x+y'+1=(x+y')+1=(x+y')'
>
> But the problem is, that associativity law for addition is still not defined
> (it is defined in the next theorem), and associativity law depends
> on our theorem, so how can we say that x+1+y'=(x+y')+1 ???
> I can understand that x+1=1+x, because it is only notation, and
> actually means "operation of addition on a couple of numbers",
> but how to deal with associativity problem?
>
> Is there is a solution to this - otherwise the whole chain of proof
> is broken for me :(.
>
>
> ddtl.

Relevant Pages