Let us assume that the following four statements are Peano's first four axioms, leaving only the fifth (principle of mathematical induction).

1) Zero is a natural number. 2) Every natural number has a successor, which is also a natural number. 3) Zero is no successor to any natural number. 4) Two natural numbers that have equal successors are themselves equal.

Let s and t be successors of the natural number n. How can we prove that s = t? That is, how can we prove, using only the four axioms above, that every natural number has a single successor?

It seems to me that this is not possible. I need help.

  • 3
    $\begingroup$ In first order logic, "successor" is given a functional notation, which means implicitly that each number has a single successor. There is nothing in the above axioms, without that assumption, which prevents them from describing an infinite binary tree, where every element has two successors. Indeed, even with induction, you still have an infinite binary tree as a model. $\endgroup$ – Thomas Andrews Aug 18 '17 at 14:17
  • $\begingroup$ The original Peano's formulation (that was not formalized as today's first-order logic: see comemnt above) has for 4) "two natural numebrs are equal iff they have equal successors": $a, b \in \mathbb N \to (a = b \leftrightarrow a + 1 = b + 1)$ (slightly modernized). $\endgroup$ – Mauro ALLEGRANZA Sep 12 '17 at 8:39
  • $\begingroup$ By definition, $s$ is a fucntion, and thus: $t=s(n)=s$. $\endgroup$ – Mauro ALLEGRANZA Nov 27 '17 at 9:12

If you assume, as it seems, that "successor" is a relation on $\Bbb N$ rather that a function $f:\Bbb N\to\Bbb N$, then you are correct in saying that uniqueness cannot be deduced. Consider a "bifurcated $\Bbb N$", that is $$\Bbb N':=\{(n,0)\,:\,n\in\Bbb N\setminus\{0\}\}\cup \{(n,1)\,:\,n\in\Bbb N\setminus\{0\}\}$$ and the successor relation $$(a,i)R(b,j)\stackrel\Delta\iff (i=j\wedge b=a+1)\vee (b=1\wedge a=0)$$

In this, $0:=(0,0)$ has exactly two successors, which generate two "disjoint copies" of $\{1,2,3,\cdots\}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.