[LOGIC] Proof by Induction in Peano Arithmetic

  • Thread starter Firepanda
  • Start date
  • #1
430
0
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.

263c5ee.png



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?

Thanks
 

Answers and Replies

  • #2
jgens
Gold Member
1,583
50
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?

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?
 
  • #3
430
0
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

155gqcl.png


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..

Thanks
 

Related Threads on [LOGIC] Proof by Induction in Peano Arithmetic

  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
9
Views
1K
  • Last Post
Replies
6
Views
871
  • Last Post
Replies
16
Views
2K
  • Last Post
Replies
2
Views
912
  • Last Post
Replies
4
Views
852
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
6
Views
1K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
4
Views
1K
Top