7
$\begingroup$

Is anyone aware of alternative axioms to induction? To be precise, consider peano axioms without induction PA-. Is there any axiom/axiom schema that is equiconsistent to induction, assuming PA-? If so, why does it appear that nobody investigating it?

To contextualize this question, I refer to discovery of the equiconsistency of the non-Euclidean geometries. The geometry has flourished (or at least, developed) to its modern state with manifold theories and later developments was only possible with the recognition of non-Euclidean geometries. For a long time, Euclidean geometry and the Parallel Postulate was seen as the only geometry, very much as today's standard model for number theory ${\mathbb N}$ and the induction axiom is seen as the only number theory. (at least to the extent that i'm aware of, so that's why I'm asking this question.) I wonder why, therefore, that there is only one number theory, and no alternatives like non-Induction number theory.

Note: I am aware that recursion theorists study fragments of induction. However, in the sense of which I'm asking, this does not count at alternative axioms to induction since ${\mathbb N}$ is still a model of these these fragments. Using my geometry analogy, these fragments amount to saying that the Parallel Postulate does not hold everywhere throughout space, something like space is not homogeneous but still has some symmetry.

$\endgroup$
3
  • $\begingroup$ If you can't encode peano arithmetic, you can't do peano arithmetic. This question doesn't make any sense. $\endgroup$ Dec 13, 2009 at 15:04
  • 1
    $\begingroup$ To amplify a bit on Harry's comment, any set together with a map which is injective but not onto is a model of the Peano axioms without induction. This class of models seems too wide to be of much use. $\endgroup$ Dec 13, 2009 at 16:35
  • 6
    $\begingroup$ @Harry & Harald. The question and answers (well, at least the answers) are about the first-order theory PA, not about the second order Peano's axioms, which have only one model as you point out. There is a rich and interesting model theory of models of PA and fragments/extensions of PA. $\endgroup$ Jan 12, 2010 at 13:32

4 Answers 4

15
$\begingroup$

A crucial difference between non-Euclidean geometries and "non-inductive" models of PA- is that any model of PA- contains a canonical copy of the true natural numbers, and in this copy of $N$, the induction schema is true. In other words, PA is part of the complete theory of a very canonical model of PA-, and as such it seems much more natural (so to speak) to study fragments of PA rather than extensions of PA- which contradict induction.

To make this a little more precise (and sketch a proof), the axioms of PA- say that any model $M$ has a unique member $0_M$ which is not the successor of anything, and that the successor function $S_M: M \to M$ is injective; so by letting $k_M$ (for any $k \in N$) be the $k$-th successor of $0_M$, the set $\{k_M : k \in N\}$ forms a submodel of $M$ which is isomorphic to the usual natural numbers, $N$. Any extra elements of $M$ not lying in this submodel lie in various "Z-chains," that is, infinite orbits of the model $M$'s successor function $S_M$.

(In the language of categories: the "usual natural numbers" are an initial object in the category of all models of PA-, where morphisms are injective homomorphisms in the sense of model theory.)

So, while PA seems natural, I'm not sure why there would be any more motivation to study PA- plus "non-induction" than there is to study any of the other countless consistent theories you could cook up, unless you find that one of these non-inductive extensions of PA- has a particularly nice class of models.

$\endgroup$
9
$\begingroup$

The literature on this question is large!

First recommendation: take a look at George Boolos (1984/1998)'s "The Justification of Mathematical Induction", in Logic, Logic, And Logic, pp. 370—375, Harvard University Press.

Boolos talks there about the general idea of proving induction, and discusses several principles whose correctness might be seen as more immediately amenable to intuition. He then discusses an idea of Dana Scott's, that induction can be justified in terms of an extended language of set theory with a relation "<" expressing which of two sets was formed at the earlier stage in the cumulative hierarchy. He argues that the principles of this theory are much less inductive that the principle of induction. This is Good Stuff, easy to follow, and an antidote to inappropriate worries about the logical strength of the principles involved.

Then, I recommend thinking about Getzen's proof of the consistency of arithmetic. The tricky issue with induction is that it expresses a metatheoretic property of the structure $\mathbb N$. Gentzen's proof transforms the issue, showing finitarily that the consistency of the whole system is the same thing as the well-foundedness of XP (the extended polynomials, i.e. the polynomials with addition, multiplication, and exponentiation). So the metatheoretical basis for the induction principle gets transformed, proof-theoretically, into a combinatorial thesis.

$\endgroup$
6
$\begingroup$

I found the citation below here

89e:03084 03E20 Swanson, Leonard G. (1-PRLS); Hansen, Rodney T. The equivalence of the multiplication, pigeonhole, induction, and well ordering principles. Internat. J. Math. Ed. Sci. Tech. 19 (1988), no. 1, 129--131.

Informal set-theoretic arguments are given for the equivalence of the principles mentioned in the title, all of which are stated for the natural numbers. The authors work in Zermelo-Fraenkel set theory, but such arguments should be given in a weaker system of set theory or arithmetic in which the principles in question are not theorems. The strength of several forms of the pigeonhole principle was studied by T. von der Twer [Arch. Math. Logik Grundlag. 21 (1981), no. 1-2, 69--76; MR 84e:03072].

$\endgroup$
1
0
$\begingroup$

I think that PA without the induction axiom schemata is equivalent to Robinson Arithmetic, often called Q. This was isolated in the 1950s as an example of an incomplete theory of arithmetic, which is in some way minimal (in the sense that removing any of its axioms leaves a theory which can be negation-complete).

This might be what you meant by recursion theorists studying fragments of induction? If so, sorry the answer is not helpful as it is indeed a theory modeled by $\mathbb{N}$.

As for what use these models of arithmetic might be, I cannot even speculate! They are certainly curious.

$\endgroup$
1
  • 1
    $\begingroup$ Not quite: you need an axiom to do non-inductive case reasoning on naturals in Q. $\endgroup$ Jun 25, 2013 at 14:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.