Assuming that the Peano Axioms hold (without the axiom of induction), and assuming one of Robinson's Axioms, namely

Every natural number is either $0$ or the successor of a natural number.

It can be shown that you cannot use the above axiom to prove mathematical induction, since there's an inherent circularity, but I can't seem to pin down what will go wrong.

  • 1
    $\begingroup$ Can you write down your proof of the axiom of induction via Robinson's axiom, please? $\endgroup$ – Cave Johnson Jul 30 '16 at 14:53
  • $\begingroup$ I've edited my question. I know it cannot, but I can't seem to show why it can't be done. $\endgroup$ – Maxis Jaisi Jul 30 '16 at 14:57
  • $\begingroup$ What can you even do with such an axiomatic system? $\endgroup$ – mathreadler Jul 30 '16 at 14:57
  • 1
    $\begingroup$ Is that really Robinson's Axiom? It would seem to imply a universe with only two elements. $\endgroup$ – John Coleman Jul 30 '16 at 14:59
  • $\begingroup$ I've again edited my question; it should be "one" of Robinson's Axioms instead of "the" Robinson Axiom. $\endgroup$ – Maxis Jaisi Jul 30 '16 at 15:04

Let $X$ be the set of polynomials $f(x)$ with integer coefficients which are either $0$ or have positive leading coefficient. This then satisfies your axioms. However, it does not satisfy induction. For instance, if it did, then it would have to satisfy $$\forall a\exists b (a=2b\vee a+1=2b),$$ since you can prove this statement by induction. But this statement is not true for $a=x$.


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.