3
$\begingroup$

If I recall correctly the Peano axioms of natural numbers includes the axiom that proofs of induction should be valid. I am curious about what properties these "not so natural" numbers could have if it did not hold?

$\endgroup$
5
  • 1
    $\begingroup$ See Presburger arithmetic and Robinson arithmetic or Q for some ideas. Presburger arithmetic allows induction with addition formulas but lacks multiplication (and is decidable), while Robinson arithmetic lacks induction altogether (being finitely axiomatizable) but remains undecidable. $\endgroup$
    – hardmath
    Dec 20, 2015 at 15:15
  • 1
    $\begingroup$ Robinson arithmetic, or Q is "essentially PA without the axiom schema of induction" (according to Wikipedia), so it should be your answer. $\endgroup$
    – user236182
    Dec 20, 2015 at 15:18
  • $\begingroup$ @user236182: Perhaps I should post an answer, but I interpreted the question to be, what sort of "integers" could we have without induction? So the models of Robinson arithmetic will of course fall into this topic, but I think it fair to bring up Presburger arithmetic, with its omission of multiplication, as this arguably (esp. in the original Peano axioms) illustrates what might happen. $\endgroup$
    – hardmath
    Dec 20, 2015 at 15:21
  • $\begingroup$ Thanks guys. I would accept both those as answers. Presburger seems really interesting even though wikipedia says it does actually include a schema of induction and being "not as powerful", does it dodge Gödel incompleteness theorem? $\endgroup$ Dec 20, 2015 at 15:30
  • 1
    $\begingroup$ Yes, that's kind of the point of Presburger arithmetic. Lacking multiplication, even though it has a first-order scheme of induction, the theory of Presburger arithmetic turns out to be decidable and therefore it does "dodge Gödel incompleteness theorem". Robinson arithmetic demonstrates the other side of the balance, that despite lacking a scheme of induction, the properties of addition and multiplication are finitely axiomatized in a way that gives an undecidable (essentially incompleteable, in first-order logic) theory. $\endgroup$
    – hardmath
    Dec 20, 2015 at 15:37

1 Answer 1

2
$\begingroup$

In Peano's original axiomatization of the natural numbers, induction is provided as a second-order logical schema. This turns out to be a very powerful notion, and in particular allows us to define binary operations of addition and multiplication from the more basic (unary) operation of successor. This theory escapes Gödel's incompleteness theorems in that it is not a first-order theory, and indeed has only the canonical model of natural numbers (up to isomorphism).

Let us then speak of Peano arithmetic as the "familiar" first-order theory, to which Gödel's (first and second) incompleteness theorems apply. Axioms for addition and multiplication in relation to each other and to the successor operation can be stated in first-order logic, but the first-order scheme of induction doesn't permit us to dispense with these extra-logical axioms and simply prove them from other axioms.

Some evidence for this can be seen in the weaker first-order theories of Presburger arithmetic and Robinson arithmetic (or Q).

Presburger arithmetic has a first-order schema of induction, but only the successor operation and addition (no multiplication). This turns out to be a complete and decidable theory, which illustrates one clear way it is weaker than Peano arithmetic with its Gödel numberings and incompleteness theorems. There one is unable to develop a general notion of divisibility and of primality in particular.

Robinson arithmetic has only finitely many first-order logical axioms and thus no schema of induction. However it includes axioms for multiplication and has enough power (despite being weaker than Peano arithmetic) to be essentially incomplete. One model for Robinson arithmetic, besides the usual natural numbers, is the subset of integer polynomials which have positive leading coefficient and zero.

$\endgroup$

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.