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?
Answer
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.
No comments:
Post a Comment