1

I'm doing my research project on Peano Arithmetic, and need to show the PA can prove that no number is the successor of itself.

I've seen an answer here: Peano's Axiom: Is it implied that successor of a number is not the number itself?, but I'm struggling to understand from line 5 - why is it introduced? And why is line 6 introduced?

Thanks in advance for your help

Dani

José Carlos Santos
  • 427,504
Dani
  • 13
  • Looks like a proof by induction where you show that the property $s(x)\neq x$ is true for all $x$. Line 5 would be your induction hypothesis, or whatever it is called in English. Edit: It seems it is called the "inductive hypothesis". – N.Bach Nov 21 '17 at 13:41
  • Are you familiar with mathematical induction? – DanielV Nov 21 '17 at 13:42
  • @DanielV - yes I am. You prove something for the base case (in this case '0') and the for all number up to 'n'; if you can prove for 'n + 1' you can prove for all 'n'...? – Dani Nov 21 '17 at 14:18
  • @N.Bach - thank you. That helps a lot... – Dani Nov 21 '17 at 14:34

1 Answers1

0

In order to answer that, it must be seen what lines # and fou say.

Line 3: If $s(0)\neq0$ and if, for every natural $n$, $s(n)\neq n\implies s\bigl(s(n)\bigr)\neq s(n)$, then, for every $n$, $s(n)\neq n$.

This is just the induction principle applied to the proposition $(\forall n\in\mathbb{N}):s(n)\neq n$.

Line 4: $s(0)\neq 0$

This is here to assert that the base case of induction holds.

Then lines 5 to 10 are here to prove that if $s(n)\neq n$, then $s\bigl(s(n)\bigr)\neq s(n)$, that is, in order to comple that induction proof. So, he starts by picking an $a\in\mathbb N$ and he assumes that $s(a)\neq a$. In order to prove that $s\bigl(s(a)\bigr)\neq s(a)$, he assumes that they are equal and reaches a contradiction. Since such a contradiction is reached, $s\bigl(s(a)\bigr)$ is indeed different form $s(a)$ and the theorem is proved.

José Carlos Santos
  • 427,504
  • thank you. It makes more sense now. When he says in line 5: s(a) not equal to a, that is an assumption? Then it makes sense! Thank you :) – Dani Nov 21 '17 at 14:22
  • @Dani Yes, that is an assumption. He assumes that $s(a)\neq a$ and he deduces from this that $s\bigl(s(a)\bigr)\neq s(a)$. – José Carlos Santos Nov 21 '17 at 14:24