1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: [LOGIC] Proof by Induction in Peano Arithmetic

  1. Mar 18, 2012 #1
    I have to do the following using these axioms PA1-7, the others below it are previously proved results I can use too.

    [Sa] means the successor of a.


    Base Case: y = S0

    x.S0 = S0

    → x.0 + x = S0

    → 0 + x = S0

    → x = S0 & y=S0

    Now the induction step is usually y=a to y=Sa, however this does not work here, I assume I need to take a new y and it's successor to proceed. Would anyone know how to proceed and which y to take?

  2. jcsd
  3. Mar 18, 2012 #2


    User Avatar
    Gold Member

    Why are you inducting here? You usually only use induction when you are trying to show that something is true for all natural numbers. So while your base case holds, any other case you try will fail.

    How formally does this proof have to be done. If you are using the Peano axioms, then presumably you are taking a course in mathematical logic or something of the like, so it it alright to write the proof out in ordinary mathematical language?
  4. Mar 18, 2012 #3
    Yeah we are advised to do this proof 'mathematically' rather than 'logically' (i.e not by natural deductions using rules of inference)

    Here is an example proof, all the others have been done via the induction schema so I assumed this one was to be done that same way too


    If not then I have no idea how to do it without induction for those axioms

    I agree with what you're saying, it doesn't make sense that this holds for any other case other than S0, but then how do I show this?

    Unless I derive some contradiction using PA1, and hence I can derive anything from that contradiction..

Share this great discussion with others via Reddit, Google+, Twitter, or Facebook