0

Using the Peano's Axioms from MathWorld as the basis, I'm wondering if it is implied that the successor of a number is not the number itself, or is it deducible?

KGhatak
  • 196
  • 1
    It is possible to deduce it, using the fact that $0$ is not a successor, and using the induction axiom – Maxime Ramzi Jul 17 '17 at 09:51
  • 2
    Hint: assume that for some $z: S(z)=z$. Applying induction, let $n_0$ the least $z$ such that ... and assume that $n_0 \ne 0$ (otherwise: $S(0)=0$ contradicting Peano Ax.1). Thus, $S(n_0)=n_0=S(n_0-1)$; by Ax.2: $n_0=n_0-1$ and thus $S(n_0-1)=n_0-1$, contradicting the "minimality" of $n_0$. – Mauro ALLEGRANZA Jul 17 '17 at 09:58
  • @ Mauro ALLEGRANZA : Not sure how $S(0)=0$ is a contradiction. Are you referring to '0 is a natural number' for Ax.1 ? – KGhatak Jul 17 '17 at 10:07
  • 1
    @KGhatak: Writing $0$ as the successor of $0$ contradicts the axiom that $0$ is not a successor of any number. –  Jul 17 '17 at 10:20
  • Thanks a lot. Somehow I missed it.. – KGhatak Jul 17 '17 at 10:23
  • 1
    Ax.3: $\forall x \ (S(x) \ne 0)$ and thus also $S(0) \ne 0$. – Mauro ALLEGRANZA Jul 17 '17 at 10:56

1 Answers1

3

We can formalize these Peano's Axioms in first-order logic as follows:

$\forall x \ s(x) \not = 0$ (this is Peano axiom 3)

$\forall x \ \forall y \ (s(x) = s(y) \rightarrow x = y)$ (this is Peano Axiom 4)

for any formula $\varphi(x)$:

$(\varphi(0) \land \forall x (\varphi(x) \rightarrow \varphi(s(x)))) \rightarrow \forall x \ \varphi(x)$ (this is a general scheme that captures Peano Axiom 5 ... $S$ would be the set of all objects for which $\varphi(x)$ is true)

Using this, you can derive the statement $\forall x \ s(x) \not = x$, i.e. that the successor of any number is never that number itself:

enter image description here

Bram28
  • 100,612
  • 6
  • 70
  • 118