Thread: Little Proof

Hi I'm reading this great book Foundations of Analysis by Edmund Landau, a really old book that aims to build the foundations of analysis from basic arithmetic.

I'm not that strong on proofing yet but am trying, here is my problem.

Using these 5 axioms for the Natural numbers;











with the following properties





I want to prove that x' ≠ x. It's the second theorem, the first being;

If x ≠ y then x' ≠ y'

which is proved by assuming x ≠ y and x' = y'

so we find a contradiction with axiom IV above because x' = y' means x = y.

This is beautiful and understandable but in proving x' ≠ x the proof goes as follows,

By axioms I and III above,

i) 1' ≠ 1 because 1' = 1 + 1.

so 1 belongs in R.

Then it says;

ii) If x ∈ R then x' ≠ x and by theorem 1 (x')' ≠ x' so x' ∈ R

This makes no sense to me, where did it come from

I don't know why you can't use axiom II and just rearrange x' = x + 1 into x = x' - 1 to prove it

Originally Posted by sponsoredwalk

...
Then it says;

ii) If x ∈ R then x' ≠ x and by theorem 1 (x')' ≠ x' so x' ∈ R

This makes no sense to me, where did it come from
...

Replace x and y in theorem 1 with x' and x, respectively.

Originally Posted by sponsoredwalk

I don't know why you can't use axiom II and just rearrange x' = x + 1 into x = x' - 1 to prove it

Have you defined the string a - b? If not, you cannot use that type of algebra, as the symbol "-" has not been defined, nor have you defined the concept of additive inverse (the set of natural numbers has no additive inverses), so it is not apparent that the concept of addition has a unique inverse operation per addend.

What does (x')' ≠ x' so x' ∈ R mean? Does it mean (x')' = (x + 1)' = (x + 1) + 1 ?

If I replace as you said I would follow the proof like this;

If x' ≠ x and (x')' = x' we see that (x')' ≠ x as well but x' = x + 1 by Axiom II, i.e. x' = x + 1, we must conclude that (x')' = x' = x + 1

I don't see how to get a contradiction, I think I'm just going to go in circles here

Yeah, I see what you mean - minus hasn't been defined, ty

Originally Posted by sponsoredwalk

What does (x')' ≠ x' so x' ∈ R mean? Does it mean (x')' = (x + 1)' = (x + 1) + 1 ?

Yes.

Originally Posted by sponsoredwalk

If I replace as you said I would follow the proof like this;

If x' ≠ x and (x')' = x' we see that (x')' ≠ x as well but x' = x + 1 by Axiom II, i.e. x' = x + 1, we must conclude that (x')' = x'
...

This equality is not supported by any of the axioms or theorems. x and ' are separate symbols and are replaced independently of each other.

Yeah I see what I did,

So, let me try it again.

If 1' = 1
there is a contradiction because axiom III states that
x' ≠ 1 ergo we can't choose 1 for x as it commits this error.

so

1' ≠ 1,

1' = 1 + 1

So,

if x' = x + 1,

then (x')' = (x + 1)' = (x + 1) + 1

and (x + 1) + 1 ≠ x + 1

so we see (x')' ≠ x'

Q.E.D.

I think that is convincing, what do you think?

This has kind of been confusing on my part however,

the addition sign hasn't even been defined yet

I wrote for axiom II x' = x + 1 because I read the
language and assumed that's what it meant,
(which it does, as the next page indicates )
but without the addition sign I think it's clearer.

Forget that stuff, it's my ineptness that made me
post this...

Axiom II actually says that for every x there exists
exactly one natural number that is the successor of x.

Going off that language I see why they combine
Axioms I & III,
to force us to designate the x in x' ≠ 1 from Axiom III
with the number 1 defined in axiom I.

Doing this is a way to show that 1' ≠ 1,
i.e. 1' = 1 is a false statement by
axiom III.

As for x' ≠ x, well if x' = x then we set
x to 1 we'll get x = x' = 1 and this contradicts
Axiom III, and theorem 1, so x' ≠ x

If this is correct then I think, by axiom V,
because x is in the set by definition x' is in the set
and we've proven x' ≠ x so I think we can just repeat
the ' action on x' ≠ x, i.e. (x')' ≠ x'

That seems a bit guessey to me though, have you any advice?

Originally Posted by sponsoredwalk

Yeah I see what I did,

So, let me try it again.

If 1' = 1
there is a contradiction because axiom III states that
x' ≠ 1 ergo we can't choose 1 for x as it commits this error.

so

1' ≠ 1,

1' = 1 + 1

So,

if x' = x + 1,

then (x')' = (x + 1)' = (x + 1) + 1

and (x + 1) + 1 ≠ x + 1

so we see (x')' ≠ x'

Q.E.D.

I think that is convincing, what do you think?

I don't see how you got that . Here is my stab at it: You proved the base case. Good.

Now assume that . Suppose (a little short-hand), then by Axiom IV, , contrary to assumption.

This has kind of been confusing on my part however, the addition sign hasn't even been defined yet

Actually, it has. The definition is just those five axioms. That's all that addition means at this point in the game.

Originally Posted by sponsoredwalk

...but in proving x' ≠ x the proof goes as follows,

By axioms I and III above,

i) 1' ≠ 1 because 1' = 1 + 1.

so 1 belongs in R.

Then it says;

ii) If x ∈ R then x' ≠ x and by theorem 1 (x')' ≠ x' so x' ∈ R

This makes no sense to me, where did it come from

I don't know why you can't use axiom II and just rearrange x' = x + 1 into x = x' - 1 to prove it

By the way, I find this "proof" wildly confusing. Isn't it an axiom that ? If so, why would a proof conclude with this fact? And how does that entail that ? Are you certain you've reproduced the axioms accurately? And what are the axioms ranging over? ? Do all axioms apply to all elements, or only the first four axioms apply to elements in ?

The whole setup is very odd.

... But I now understand how the proof of the second part goes. It says: Suppose x is in R. Now suppose x' =/= x (this is our inductive hypothesis, so the goal is now to show that x'' =/= x'). But the theorem we just proved (Theorem 1) said that things which are not equal, don't become equal by adding ' to them. I.e. x' =/= x implies that x'' =/= x', which is exactly what we wanted to show.

Here are the first 2 pages on which you'll read it, I've kind of messed it up with the way I wrote things, I assumed addition, subtraction and the exisence of the reals in one fell swoop, I think when you read it you'll see I've messed things up by assuming way too much. I think the fifth axiom is the one I don't understand or am not applying correctly...

Ahhhhhhhhhhhh, I see. Yes, this makes a lot more sense. Since it's the fifth axiom that you say you're confused about, I'll say a few words about it. It just means that the natural numbers are unique up to these two properties. To put it in a much more intelligible way: If you ever find a set of number which contains 1 and contains every successor of its elements, then it must be the natural numbers. To put it yet another way: Only the natural numbers has those two properties. Hopefully that's helpful. Thus the way this property is used in the book's proof of Theorem 2 is: take the set R of all elements which has this property. Then it satisfies property 1, and property 2. Therefore R is the whole set of natural numbers.

So this set R is not supposed to be the real numbers. You're a very, very long way from constructing the reals. What you've done so far is Peano arithmetic, so you still need to construct the integers, then the rationals, and then the reals, and this assumes you don't stop somewhere along the way to define notions of ordering (the '<' relation) and distance between points in a metric space, or other properties of more general mathematical structures than the reals.

Perhaps I can ask why you are looking into such a foundational approach to real analysis. If it's for curiosity or something not terribly pressing and serious, you might want to read a section or two from a text about logic, which will prepare you for mathematics-style arguments a bit.

So theorem V states that if you have a set of numbers including 1 and anything above 1 i.e. x = 2 or x = 3 it means that x' is included and therefore (x')' up to infinity i.e. including all of the numbers by iteration, or induction...

I've thought of a way to attempt this problem better, let me know if it's intelligible

So, to prove x' ≠ x we prove x = 1 first then move onto the general case x ≠ x' because, by axiom V, this will account for all natural numbers 1 upwards.

If 1 = x, 1' = x' by Axiom IV and 1 ≠ x' because if 1 = x' this breaks Axiom III, and theorem I.

So, by theorem 1, x ≠ x' for x = 1 because if x = x' and 1 = x then 1 = x = x' and this contradicts Axiom III.
This should settle the question for the base case, x = 1, that x ≠ x'

If we assume x to be something other than one, say 3, it is defined under this arithmetic as;

(x')' where x is 1. I think this makes sense, (1')'=(2)'=3 as defined by axiom II as it's written in the book. To me it seems logical, what do you think?

If we define numbers this way we can use the base case proof, define x as 1 so that
x ≠ x' can be iterated,

1 ≠ 1' ⇒ 1≠ 2

1 ≠ 1' ≠ (1')' ⇒ 1 ≠ 2≠ 3

(1')'≠ ((1')')' ⇒ 3 ≠ 4

etc...

so, for any x we choose, i.e. 1 = x and 2 = (1') = x' so it can be composed of 1's and (')'s and this applies for all x and x' by axiom V.

If you see what I'm trying to do, maybe it could be cleaned up? Thanks for the help so far anyway

So it seems like you mention some unnecessary things in your proof, and in my experience that indicates an un-clarity about what is essential to the proof. So here is the most precise proof I can give, in the spirit of what you've written:

If we take the set of numbers which satisfy the property that , let us call this set R. If we show that 1 is in R, and for every , if R then R, then we will have proved that R is the whole set of natural numbers, which will mean that every natural number has the property that . (This is a slightly long-winded appeal to Axiom V.)

To show that 1 is in R: By Axiom 3, . Since R just is the set of numbers such that , this proves that R.

To show that every successor is in R: Suppose some R. We hope to show that . But since R, by the definition I gave of R in the beginning,we know that . Also, by the definition of R, what we want to show is equivalent to showing that .

In order to obtain the desired result, let us assume that it is false. If we arrive at a contradiction, then the assumption cannot be false and so it must be true. Thus we assume that . But this implies, by Axiom 4, that . But we chose out of R, so we know this cannot be true. Thus we have our contradiction, and the proof is done.

(Equivalently, we could remove this last paragraph, and merely appeal to Theorem 1.)