Edmund Landau - "Foundations of Analysis"

sponsoredwalk

Hey, I've got this strange little book called Foundations of Analysis &
I have to say that it's sets out to do a lot from the looks of it.

I tried reading it a month ago but got stuck on the second theorem :eek:
because I was really overthinking the whole thing, using algebra when
it's not even defined! etc... but I'm going to come back to it.

Anyway, the idea of the book is to prove everything based on it's axioms
(much like everything else in math ) along with obvious things like x = y
being the same as y = x & if x = y & y = z then x = z...

Well, I'd like to write out the 5 axioms as I understand them & do the
first 3 theorems to make sure I have this correct because the second
theorem really has me worried I'll make stupid assumptions
This is all using just the Natural numbers.

Axiom I: 1 ∈ N, i.e. N ≠ [latex]\emptyset [/latex]

Axiom II: ∀ x ∃ exactly one number x' that is the successor of x. (This axiom assures that if x = y then x' = y').

Axiom III: x' ≠ 1 (1 cannot be a numbers successor).

Axiom IV: If x' = y' then x = y

("That is, for any given number there exists either no number or exactly
one number whose successor is the given number.").

Axiom V: ∃ a set R of Natural numbers with the properties that

i) 1 ∈ R
ii) if x ∈ R then x' ∈ R

Then N = R.

What Landau says in Axiom IV is a little confusing, there is either one
number or no number whose successor is the given number, is he saying
there can either be one number or no number whose successor is that
same number??? Like, the successor of 2 can be 2 for some strange
number 2??? I don't know if he's leaving the possibility open or something,
it seems to me that axiom II already explains that the successor of a
number has to be different. I really really doubt it but I thought I'd mention it.

Anyway, using these 5 axioms we'll do the first 3 proofs!

Theorem I: If x ≠ y then x' ≠ y'

Proof: If x ≠ y & x' ≠ y' then the theorem holds.

If x ≠ y but x' = y' then we contradict Axiom IV because if x' = y' then
x = y & this contradicts our assumption that x ≠ y.

if x = y but x' ≠ y' then we contradict Axiom II so If x ≠ y then x' ≠ y'.

Theorem II: x' ≠ x

Proof: If we set x = 1 then by Axiom III the theorem holds.

Seeing as Axiom II defines x' as the successor of x we can assume the
theorem holds for all x.

The book then does the following;

Since x' ≠ x we can say (x')' ≠ x'.

I assume we can do this ad infinitum and in doing so we have shown that
this is a description of the set R of natural numbers as described by
Axiom V. Is that correct thinking or can that be put better?
By ad infinitum repetition I mean we can then say that ((x')')' ≠ (x')' &
(((x')')')' ≠ ((x')')' etc...


Theorem III: If x ≠ 1 then there exists exactly one u such that x = u'

Proof: If you read the proof he gives one minute he's defined
x as u' and the next he denotes x = u :eek:

I'll write it out:

"Let R be the set consisting of the number 1 & all those x for which there exists such a u.
(For any such x we have of necessity that x 1 by Axiom III).
I) 1 belongs in R.
II) If x belongs to R, then, with u denoting the number x, we have
x' = u' so that x' belongs in R.
By Axiom V, R therefore contains all the natural numbers. Thus, for each
x ≠ 1 there exists a u such that x = u'."



You can read the first 3 pages in that link to see for yourself, hope this
isn't too taxing but it would be great to get a proper foundation in what
this book is talking about (let alone the subject!). Thanks for reading!

Fremen

I haven't worked through the theorems yet, but I guess the idea behind axiom four is "succession is a one-to-one function".

In the text below, he's using the words "for any given number". That number might be 1, in which case the theorem is false since 1 is not the successor of anything, so he has to weasel out of that.

Landau was an important mathematician, but to be honest, this is a slightly old-fashioned treatment of the foundations of analysis. If you want to see a modern construction, you should take a look at the chapter on set theory in section four of the princeton companion to mathematics (brilliant book). This is well worthwhile, since it also has some stuff on the incompleteness theorem and the continuum hypothesis which really shocked me when I first heard about it.

sponsoredwalk

Well that's an axiom & he's already stated that 1 can't be the successor to
a number so he can't be including 1.

If you read it, he says

"... for any given number there exists ...(yadda yadda yadda)... exactly one number whose successor is the given number."

I think he's allowing for the possibility that the successor can be the same
number as the one you're currently talking about. Notice he hasn't used
any other number than 1 yet.
He does define x' = x + 1 in the 4th proof which guarantee's the successor
can't be the same number so it's really a stupid point I suppose but I thought I'd mention it.

Let me know your thoughts on theorem's 2 & 3 if you get a chance, I'd
appreciate it.

I wouldn't be able to read the Princeton book yet, I've browsed it & it'd
be too much for me in it's substance, let alone timeframe :P

Fremen

Maybe we can summarise it in more familiar language.

I/ We have a non-empty set N with an element 1

II/ There exists a function f: N -> N such that the range of f is non-empty.
(successor function)

III/ 1 is not in the range of f

IV/ f is one-to-one

V (induction)

"for any given number there exists either no number or exactly
one number whose successor is the given number"

so suppose x is the given number. Then either there exists exactly one number y such that y = f(x), or possibly y does not exist. but we can't have

z = f(x)
y = f(x)
z not equal to y.

He hasn't explicitly ruled out f(x) = x, but he deals with it in theorem two.

By axiom three, f(1) is not equal to one.
By theorem one, f(f(1)) is not equal to f(1), and so on.

I guess what he's tacitly assuming is that eventually, by applying f to 1 enough times, you can eventually "hit" any x you want. I don't see where that's explicitly stated though.

sponsoredwalk

Well if it satisfies Axiom V then it will hit any x you want by repeatedly
applying f to 1, i.e. (fo(fo(fo(fo....(fof)))....))))(s) where s = 1 :P

So I think that's alright for theorem II, if you read theorem III by the
end of it he's come to the conclusion that R contains all of N but I don't
see how he gets there....

One minute: x = u'
The next: x' = u'
so x = x' :P

Obviously he's doing something but I don't see it

Enkidu

The point of Axiom four is basically as Fremen said, at least that is the way I would read it. As it stands Axiom II explicitly tells you that every number has one successor. At this point, if you take a given number it could be:
(a) The successor of no numbers.
(b) The successor of one unique number
(c) The successor of several numbers.

Axiom III tells you that (a) is true only for one, so for other numbers (b) or (c) could be true. Axiom IV is the assumption that (c) is never true. Hence for a given number either (a) or (b) are true:
"That is, for any given number there exists either no number or exactly
one number whose successor is the given number."

sponsoredwalk

So I think I've figured out what Theorem III is saying, I'm pretty confident
but if I'm wrong it would be of immense help for you to spot the flaw in
my answer!

Theorem III: If x ≠ 1 then there exists a "u" such that x = u'

I'm pretty sure the proof is saying that as long as x isn't 1 we can have
x = u' so that there will always be a u that is one less than u' which
guarantees there is a number below u'. Another way to say it is that
as long as x isn't 1 we can think of x as being a number that is greater
than some number "u".

Proof: Well if we take some indeterminate set containing 1 we know
that it has the potential to create the set R by Axiom V.
Now, if the set that includes 1 also includes x = u' then
by Axiom IV there must exist a "u".
We can set u equal to a different x & we'll see that if
x = u
then
x' = u'

When the book sets u = x it's a different x to that one first mentioned
in x = u'.

So, if there is an x = u' there basically exists a number below x,
the best way I can say it is

(x - 1) = u
x = u'

What do you think???

seandoiler

proof is in my mind:

define a set R to be the set consisting of 1 and those x's for which x=u' (for some u). Now clearly 1 is in R (by definition), so all that remains to be proven is that if x is in R, then x' (the successor of x) is in R as well and by induction we have the result.

now simply say that by setting x=u, we then have that x'=u' and whence x' is in R

(it's the same x, as mentioned in setting that x=u'...we're simply saying that x'=(x)'=(u')'=u' for the correct choice of u, ie u=x)

rjt

seandoiler wrote: »

proof is in my mind:

define a set R to be the set consisting of 1 and those x's for which x=u' (for some u). Now clearly 1 is in R (by definition), so all that remains to be proven is that if x is in R, then x' (the successor of x) is in R as well and by induction we have the result.

now simply say that by setting x=u, we then have that x'=u' and whence x' is in R

(it's the same x, as mentioned in setting that x=u'...we're simply saying that x'=(x)'=(u')'=u' for the correct choice of u, ie u=x)

This might seem nitpicky, but we can't necessarily assume the principal of induction. This probably seems ridiculous, but we're doing everything very formally using only the 5 axioms, and usually before we use induction we need an axiom telling us we can do so. Either way we don't need it.

For theorem III, we definitely need to use axiom V anyway. The way I'd do it:

Take any y in N that isn't 1. Assume there is more than one u with y = u', take two different ones, u1 and u2 say. Then (u1)' = (u2)' so u1 = u2 by axiom IV. But they were different, so we have a contradiction, and so our initial assumption was wrong. So there is at most one u with y = u'.

Now, assume there is no u with y = u'. Then take R to be the set N without y. Then if x is in R, x is in N. So x' is in N. Now, we know by our assumption that y is not equal to x'. So x' must be in R also. Now y is not 1, so 1 is in R. Then, by axiom V, N=R. But if two sets are equal, they contain the same elements. So because y is in N, y must be in R! But that contradicts our definition of R. So again, our initial assumption was false. So there is exactly one u with y = u'.

seandoiler

rjt wrote: »

This might seem nitpicky, but we can't necessarily assume the principal of induction.

axiom 5 provides us with the axiom of induction (you in fact use the axiom of induction as well in your proof) and this is what is used to finish the 'proof' i showed...and also takes advantage of some of the other axioms and theorems subtly as well ;-)

sponsoredwalk

The Principle of Induction is guaranteed by Axiom V, it's taken as axiomatic
that as long as whatever property you're discussing holds for 1 & x then x'
then you'll be working in the set defined as R by Axiom V.

Also, I like what you did with the (u_1)' = (u_2)' thing but Axiom IV
guarantees that if (u_1)' = (u_2)' then u_1 = u_2 so we can't originally
assume u_1 & u_2 are different and still claim (u_1)' = (u_2)' holds true.
This was proven in Theorem I as well.

I don't understand the last part of your argument but it seems to me you've
given the set R an upper bound of u seeing as you've claimed there
is no y in the set, where y = u' so in other words there is no u' meaning
u is the top of the set & we know this property does not hold
for the set R by Axiom V.

What do you think?

rjt

seandoiler: True! Fair point I think we were actually saying more or less the same thing?

sponsoredwalk: On the first point, I was just trying to show that a number can't be a successor to two numbers. I used the "assume the opposite, reach a contradiction, so the original assumption is wrong" trick, I think that's ok?

For the last bit, I'm only dealing with one specific y. I don't think I'm making any upper bound in there, though I'm open to correction. Assuming that there is no u such that y = u' is like assuming y doesn't feature in our 'order', it's trying to answer the question "so we have these axioms and know that elements have successors, but can we have some element out on its own that isn't a successor (and isn't 1)?". Like without axiom 5, we don't know that the set N is {1, 1.5, 2, 2.5, 3, 3.5, ...}. The last bit of the proof is showing we can't have 1.5 that isn't a successor of something else.

sponsoredwalk

rjt wrote: »

Take any y in N that isn't 1. Assume there is more than one u with y = u', take two different ones, u1 and u2 say. Then (u1)' = (u2)' so u1 = u2 by axiom IV. But they were different, so we have a contradiction, and so our initial assumption was wrong. So there is at most one u with y = u'.

Ahh!!! I didn't get this properly a minute ago, wow that's a good argument!
Tbh that's cleared up a lot & is a great application of the axioms, I wish I had
thought of that! :pac: My response to this actually contained all the ingredients
necessary to come to this conclusion and all but I didn't follow through with
the assumption & reach a logical contradiction I just threw out the baby
with the bathwater...

But when I think about it, I mean if you say you have two u_1 terms then
you can argue that (u_1)' = (u_1)' & u_1 = u_1 but you have two
seperate ones. Is this just begging the question, do you think it simply
can't happen because the equality means they are in fact the same thing.

I'm sorry but I am still a bit confused by the end of your argument but I'll
read it in the morning & get it! :pac:;)

seandoiler

sponsoredwalk wrote: »

Ahh!!! I didn't get this properly a minute ago, wow that's a good argument!
Tbh that's cleared up a lot & is a great application of the axioms, I wish I had
thought of that! :pac: My response to this actually contained all the ingredients
necessary to come to this conclusion and all but I didn't follow through with
the assumption & reach a logical contradiction I just threw out the baby
with the bathwater...

But when I think about it, I mean if you say you have two u_1 terms then
you can argue that (u_1)' = (u_1)' & u_1 = u_1 but you have two
seperate ones. Is this just begging the question, do you think it simply
can't happen because the equality means they are in fact the same thing.

I'm sorry but I am still a bit confused by the end of your argument but I'll
read it in the morning & get it! :pac:;)

i think that the u_1, u_2 argument that rjt used is in fact redundant as the uniqueness of y=u' is assured by axiom 2 and 4 (i think...don't have them in front of me)

rjt

seandoiler wrote: »

i think that the u_1, u_2 argument that rjt used is in fact redundant as the uniqueness of y=u' is assured by axiom 2 and 4 (i think...don't have them in front of me)

My argument is pretty redundant just with axiom 4, I just spelled it out a bit.

phloaw

sponsoredwalk wrote: »

Hey, I've got this strange little book called Foundations of Analysis &
I have to say that it's sets out to do a lot from the looks of it.

I tried reading it a month ago but got stuck on the second theorem :eek:
because I was really overthinking the whole thing, using algebra when
it's not even defined! etc... but I'm going to come back to it.

Anyway, the idea of the book is to prove everything based on it's axioms

Landau died before the first computer was made. The grand and pretentious idea (shared by Peano, Russel&Whitehead, de Bruijn and many others) to rigorously build mathematics on few simple axioms has since then made huge leaps. Instead of (or rather, along with) trying digging that charming yet dusty book, why don't you take a look at mizar mathematical library?
It contains the same things of that book (and many others), just mechanically certified by a machine, so you know they are correct.
Plus, having made understndable by a machine, it will be understandable by me, you, and anyone interested.
Ok, that's not answering your questions, hope sounds new to someone.

Morbert

sponsoredwalk wrote: »

What Landau says in Axiom IV is a little confusing, there is either one number or no number whose successor is the given number, is he saying there can either be one number or no number whose successor is that same number??? Like, the successor of 2 can be 2 for some strange number 2??? I don't know if he's leaving the possibility open or something, it seems to me that axiom II already explains that the successor of a number has to be different.

Axiom two guarantees that each number has only one successor, but it does not guarantee that each number has only one predecessor. 1' = 3, 2' = 3, 3' = 4 would be consistent with axiom II, for example but not IV (3 is a given number such that there are two numbers (1 and 2) whose successor is 3, which is forbidden by IV).

sponsoredwalk

Girls & guys, thanks for the help but I think this book is more trouble than it's
worth. Not only is the language arcane & vague but I was only reading it for
pleasure because it's stated goals were to prove little things you'd take for
granted with numbers & it's taking up too much time. I have a lot of other
things to do so thanks a lot for the help, & I do really appreciate it!,
but I'll stick to my other work.

Enkidu

phloaw wrote: »

Instead of (or rather, along with) trying digging that charming yet dusty book, why don't you take a look at mizar mathematical library?

The Mizar mathematical library is a very specialised site, choosing to build mathematics from Tarski-Grothendieck (TG) set theory as opposed to Zermelo-Fraenkel-Choice (ZFC) set theory. These foundational set theoretic issues are at the advanced undergraduate or early postgraduate level and I think it would be better to be acquainted with standard set theory (ZFC) first than go look at TG set theory.