Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Addition Theorem

  1. Nov 12, 2006 #1
    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:

    (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.
     
  2. jcsd
  3. Nov 12, 2006 #2

    radou

    User Avatar
    Homework Helper

    Number 1) follows directly from the definition of the successor function. Further on, the successor function exists due to Peano's axioms.
     
  4. Nov 12, 2006 #3

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  5. Nov 12, 2006 #4

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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?
     
  6. Nov 13, 2006 #5
    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.
     
  7. Nov 13, 2006 #6
    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"...?
     
  8. Nov 13, 2006 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    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?
     
  9. Nov 14, 2006 #8
    Because it's the whole proof, that troubles me... :confused:

    Edmund Landau writes:
    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.
     
  10. Nov 14, 2006 #9
    I found the proof on the Internet, so if you prefer reading it from a PDF file, it's here - PDF file, 200.71KB. It's on the page 12 as Theorem 4.
     
  11. Nov 15, 2006 #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.
     
  12. Nov 15, 2006 #11

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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.
     
  13. Nov 15, 2006 #12
    Ok. But does ay represent (x + y)?
     
  14. Nov 15, 2006 #13

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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: Nov 15, 2006
  15. Nov 15, 2006 #14
    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: Nov 15, 2006
  16. Nov 15, 2006 #15
    In Part B.I) of the proof, Landau writes:
    for x = 1. How come (x + y)' = (1 + y)' = (y')' when the Commutative Law of Addition hasn't been proved yet (in the book)?
     
  17. Nov 15, 2006 #16

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The commutative law hasn't been used. He's showing that the definition

    1 + y := y'

    satisfies the recursion.
     
  18. Nov 15, 2006 #17
    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.
     
  19. Nov 15, 2006 #18

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What is (1 + y')?

    What is (1 + y)? What is (1 + y)'?
     
  20. Nov 15, 2006 #19
    Not sure what you are aiming for...? :blushing:
     
  21. Nov 15, 2006 #20

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Well, apply the definition that

    for any y: 1 + y := y'

    and see what you get!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?