Addition Theorem Proof - Foundations of Analysis by Edmund Landau

In summary, Theorem 4 states that for any pair of numbers x and y, there is exactly one way to assign a natural number (denoted as x + y) such that certain properties are satisfied. These properties include x + 1 = x' for every x and x + y' = (x + y)' for every x and y. The proof of this theorem involves using the axioms of natural numbers and the concept of recursion. The proof can be found in Edmund Landau's book Foundation of Analysis and it involves showing both the uniqueness and existence of the defined operation.
  • #1
dobry_den
115
0
Hi! I'm currently reading Edmund Landau's book Foundation of Analysis. I kinda got stuck right at the beggining where the author tries to develop the natural numbers theory from axioms. Theorem 4 states the following:

To every pair of numbers x, y, we may assign in exactly one way a natural number, called x + y (+ to be read "plus"), such that
1) x + 1 = x' for every x,
2) x + y' = (x + y)' for every x and every y.
x + y is called the sum of x and y, or the number obtained by the addition of y to x.

(where x' denotes the successor of x)

The following proof is quite hard to grasp (at least for me), so I'd be very grateful if anyone of you could post a link with a proof of this theorem or propose their own proof. Thanks very much.

P.S. If needed, I can post Landau's axioms & his proof.
 
Mathematics news on Phys.org
  • #2
Number 1) follows directly from the definition of the successor function. Further on, the successor function exists due to Peano's axioms.
 
  • #3
In questions like these it is vital that you post the axioms that you're supposed to deduce things from since they are *not* automatically something anyone else will know. For me, in many a case like this, I would assume that the definition of successor x is x+1, if it isn't what is your definition of successor? So, what is your definition of the set of natural numbers?
 
  • #4
1) x + 1 = x' for every x,
2) x + y' = (x + y)' for every x and every y.
Notice that for a particular x, this recursively defines a function:
y --> x + y​
where y is a natural number. Have you talked about recursion yet? Or seen the recursion theorem?
 
  • #5
matt grime said:
In questions like these it is vital that you post the axioms that you're supposed to deduce things from since they are *not* automatically something anyone else will know. For me, in many a case like this, I would assume that the definition of successor x is x+1, if it isn't what is your definition of successor? So, what is your definition of the set of natural numbers?

Well, the axioms are following:
Axiom 1 - 1 is a natural number
Axiom 2 - For each x there exists exactly one natural number, called the successor of x, which will be denoted by x'
Axiom 3 - We always have x' (not)= 1
Axiom 4 - 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 5 (Axiom of Induction) - Let there be given a set M of natural numbers, with the following properties:
I) 1 belongs to M.
II) If x belongs to M then so does x'.​
Then M contains all the natural numbers.
 
  • #6
Hurkyl said:
Notice that for a particular x, this recursively defines a function:
y --> x + y​
where y is a natural number. Have you talked about recursion yet? Or seen the recursion theorem?

Yep, I've heard about recursion, but Landau doesn't mention it there. I'm not really sure how can that help to prove the "Theorem 5"...?
 
  • #7
Well, it is rather clear, that we can define at least one operation that satisfies the properties: define x+1 to be x'+1. It is the uniqueness that might trouble you, perhaps. Why not post the proof, and indicate the points that trouble you?
 
  • #8
matt grime said:
Well, it is rather clear, that we can define at least one operation that satisfies the properties: define x+1 to be x'+1. It is the uniqueness that might trouble you, perhaps. Why not post the proof, and indicate the points that trouble you?

Because it's the whole proof, that troubles me... :confused:

Edmund Landau writes:
Proof: A) First we will show that for each fixed x there is at most one possibility of defining x + y for all y in such a way that
x + 1 = x'​
and
x + y' = (x + y)' for every y.​
Let ay and by be defined for all y and be such that
a1 = x', b1 = x',
ay' = (ay)', by' = (by)' for every y.​
Let M be the set of all y for which ay = by.
I)
a1 = x' = b1;​
hence 1 belongs to M.
II) If y belongs to M, then
ay = by,​
hence by Axiom 2,
(ay)' = (by)',​
therefore
ay' = (ay)' = (by)' = by',​
so that y' belongs to M.
Hence M is the set of all natural numbes; i.e. for every y we have
ay = by
B) Now we will show that for each x it is actually possible to define x + y for all y in such a way that
x + 1 = x'​
and
x + y' = (x + y)' for every y.​
Let M be the set of all x for which this is possible (in exactly one way, by A)).
I) For
x = 1​
the number
x + y = y'​
is as required, since
x + 1 = 1' = x',
x + y' = (y')' = (x + y)'.​
Hence 1 belongs to M.
II) Let x belong to M, so that there exists an x + y for all y. Then the number
x' + y = (x + y)'​
is the required number for x', since
x' + 1 = (x + 1)' = (x')'​
and
x' + y' = (x + y')' = ((x + y)')' = (x' + y)'.​
Hence x' belongs to M.
Therefore M contains all x.

I'm totally lost in this proof, so I'd be really grateful if there's anyone who could somehow comment on it and make it a little bit more clearer.
 
  • #9
I found the proof on the Internet, so if you prefer reading it from a PDF file, it's http://www.macs.hw.ac.uk/~mm20/papers/Kamareddine+Maarek+Wells:mkm_symposium-entcs-appendix-2004.pdf" - PDF file, 200.71KB. It's on the page 12 as Theorem 4.
 
Last edited by a moderator:
  • #10
My problem with the proof is that I do not really understand the significance of ay and by in part A of the proof. From this stems the complete confusion.
 
  • #11
It's proving the uniqueness part. The recursion theorem says that there's exactly one function satisfying the recursion. So, you have to prove that if you have two functions satisfying the recursion, then the two functions must be equal.
 
  • #12
Hurkyl said:
It's proving the uniqueness part. The recursion theorem says that there's exactly one function satisfying the recursion. So, you have to prove that if you have two functions satisfying the recursion, then the two functions must be equal.

Ok. But does ay represent (x + y)?
 
  • #13
Yes, more or less; a_y and b_y are both defined to satisfy the recursion by which we will eventually define x + y.

We don't yet know that a_y = x + y until we're done proving (the relevant parts of) this theorem, for two reasons:
(1) We don't yet know that x+y is well-defined.
(2) We don't yet know that the solution to the recursion is unique.
 
Last edited:
  • #14
Hurkyl said:
Yes, more or less; a_y and b_y are both defined to satisfy the recursion by which we will eventually define x + y.

We don't yet know that a_y = x + y until we're done proving (the relevant parts of) this theorem, for two reasons:
(1) We don't yet know that x+y is well-defined.
(2) We don't yet know that the solution to the recursion is unique.

Thanks very much for your replies.. So do I get it right that the recursion you wrote about is for example the folowing:

x + 4 = (x + 3') = (x + 3)' = ((x + 2)')' = (((x + 1)')')' = (((x')')')'​

i.e. by repetitive use of Part b) of the definition (plus bearing in mind that e.g. 4 =df 3' =df (2')' =df (1')')') we must arive at a step (((x + 1)')')' that is by definition identical with (((x')')')'. And Axiom 2 assures that the result is unique - a natural number.

Is this reasoning correct?
 
Last edited:
  • #15
In Part B.I) of the proof, Landau writes:
x + y' = (y')' = (x + y)'

for x = 1. How come (x + y)' = (1 + y)' = (y')' when the Commutative Law of Addition hasn't been proved yet (in the book)?
 
  • #16
The commutative law hasn't been used. He's showing that the definition

1 + y := y'

satisfies the recursion.
 
  • #17
Hurkyl said:
The commutative law hasn't been used. He's showing that the definition

1 + y := y'

satisfies the recursion.

The definition satisfies the recursion when (x + y') and (x + y)' are equal. He shows that both of them are equal to (y')', which - in my opinion - does not follow from the previous Part of Proof/Theorems/Axioms. The line (x + 1 = 1' = x') is quite clear, but the one below is not.
 
  • #18
What is (1 + y')?

What is (1 + y)? What is (1 + y)'?
 
  • #19
Hurkyl said:
What is (1 + y')?

What is (1 + y)? What is (1 + y)'?

Not sure what you are aiming for...? :blushing:
 
  • #20
Well, apply the definition that

for any y: 1 + y := y'

and see what you get!
 
  • #21
Hurkyl said:
Well, apply the definition that

for any y: 1 + y := y'

and see what you get!

But does this definition follow from the Addition Theorem? From what exactly?
 
  • #22
He's trying to show that the definition

1 + y := y'​

satisfies the recursion. He does so by first showing it satisfies the base case, and then showing it satisfies the recursive formula.
 

Related to Addition Theorem Proof - Foundations of Analysis by Edmund Landau

1. What is the Addition Theorem Proof in Foundations of Analysis by Edmund Landau?

The Addition Theorem Proof is a mathematical proof in the field of analysis, specifically in the study of real numbers. It is a fundamental proof that establishes the basic properties of addition, such as commutativity and associativity, which are essential for further mathematical analysis.

2. Who is Edmund Landau and why is his work important in the Addition Theorem Proof?

Edmund Landau was a German mathematician who made significant contributions to the field of analysis. He is specifically known for his work on number theory and the theory of functions. His work on the Addition Theorem Proof is important because it provides a rigorous and comprehensive foundation for the properties of addition, which are crucial in various areas of mathematics.

3. What are the key steps in the Addition Theorem Proof?

The Addition Theorem Proof involves several key steps, including defining the basic operations of addition and multiplication, proving the commutativity and associativity of addition, and establishing the distributive property. It also involves using axioms and logical deductions to derive the properties of addition from more basic principles.

4. How does the Addition Theorem Proof relate to other mathematical concepts?

The Addition Theorem Proof is closely related to other important mathematical concepts, such as number theory, algebra, and calculus. It provides a basis for understanding the properties of addition, which are essential in solving equations, manipulating algebraic expressions, and performing mathematical operations in various fields.

5. Why is the Addition Theorem Proof important in real-world applications?

The Addition Theorem Proof is crucial in real-world applications because it establishes the fundamental properties of addition, which are necessary for solving real-world problems. For example, in finance, the Addition Theorem Proof is used to calculate interest rates and investments, and in physics, it is used to analyze motion and forces.

Similar threads

  • General Math
Replies
6
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
613
  • Calculus and Beyond Homework Help
Replies
3
Views
674
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
3K
  • Differential Equations
Replies
5
Views
896
Replies
2
Views
582
  • Programming and Computer Science
Replies
1
Views
1K
  • General Math
Replies
7
Views
2K
Replies
2
Views
1K
Replies
2
Views
1K
Back
Top