Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
If you can't encode peano arithmetic, you can't do peano arithmetic. This question doesn't make any sense. –  Harry Gindi Dec 13 '09 at 15:04
1  
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. –  Harald Hanche-Olsen Dec 13 '09 at 16:35
3  
@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. –  Joel David Hamkins Jan 12 '10 at 13:32

4 Answers 4

up vote 13 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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].

share|improve this answer
    
In case anyone else goes hunting, the IJMEST article is available online at tandfonline.com/doi/abs/10.1080/0020739880190116, and the AMLG article at link.springer.com/article/10.1007/BF02011634. –  L Spice Feb 8 '13 at 14:48

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.

share|improve this answer
    
Not quite: you need an axiom to do non-inductive case reasoning on naturals in Q. –  Charles Stewart Jun 25 '13 at 14:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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