# How is a formal system including only a first-order axiomatization of induction stronger than a system without?

Stumbled upon another aspect of Peano arithmetic that I find confusing...

I understand that what I write in the title is in fact the case, e.g. certain statements provable in PA not being provable in Robinson arithmetic, for example.

I can also see how a second-order axiomatization of induction (such as in Peano's original axioms) makes a crucial difference by excluding non-standard models of the axioms.

But I don't quite see how a first-order axiomatization of induction allows us to show anything about $\mathbb{N}$ beyond what the same theory without induction does.

May I ask you to show me where I go wrong with the following informal argument:

(I will refer to the axioms of PA excluding the axiom schema of induction as the 'basic axioms' of PA, i.e. "There exists an x s.t. 0 = x", "For all x, there exists a y s.t. S(x) = y", and so on.)

1. Consider any first-order definable property P that holds for all n in $\mathbb{N}$. This property is fully characterized by the 'basic axioms' of PA, since these define the relevant properties of the natural numbers - even if they do not uniquely characterize them.

2. Now consider PA without induction: the basic axioms ensure that all elements of the domain have these characteristics, both in the standard model and the non-standard models. In particular, in the non-standard model, the elements that are not natural numbers still must follow the basic axioms, since the axioms range over the entire domain of interpretation.

3. But then, in all models, the basic axioms hold for all elements, so any relevant first-order property defined on the basis of these axioms will hold. Since PA (with or without induction) is a first order theory, there must be a proof of the statement, by first-order completeness.

To paraphrase, I don't grasp how all models of PA (including the non-standard ones) can both satisfy the basic properties of natural numbers outlined by the non-induction axioms, and at the same time contain elements for which not all first-order properties of the natural numbers hold. For example, the Wikipedia article on Robinson arithmetic quotes Burgess, Fixing Frege:

Similarly, one cannot prove that Sx ≠ x

This property already seems to be defined by the axioms that demand that every element has a successor, and that the successor function is an injection, so regardless of the induction axiom, it seems it should universally hold (for both standard and non-standard elements of the domain). But then, it seems it should also be provable, by completeness of our first-order theory.

• It is unclear what you mean by "fully characterized by the basic axioms of PA". What does it mean for a property to be "characterized by" a set of axioms? In which sense do the Robinson axioms "characterize" the property $\varphi(n)\equiv \exists x (n=n\land x=S(x))$, for example? – hmakholm left over Monica Jun 12 '15 at 16:59
• @Henning Point taken. My confusion is seems to be the result of not properly thinking through my intuition of 'fully characterized by' vs. what I formally learned about first-order definability. That said, I can now pinpoint my earlier confusion a bit more precisely: in order to prove the induction steps of, say, the property I mention above (Sx ≠ x), we only make use of the basic axioms. So what I really needed to do was to think about what the induction axiom (schema) "adds" then in terms of excluding models that are not excluded otherwise. – Bert Zangle Jun 13 '15 at 11:12
• x @zanglebert: Semantically, "excluding models that are not excluded otherwise" is all any axiom ever does. By the way, your examples ("0 exists", "$S(x)$ exists for all $x$") would not count as "axioms" in contemporary presentations of mathematical logic -- they're just properties of the language you're working with. – hmakholm left over Monica Jun 13 '15 at 12:09

What goes wrong with your argument is that what you call the "basic axioms" of PA admit models that are excluded by the induction axioms. For example, let $\mathbb{N}_{\infty}$ be the structure for the language of PA with underlying set $\mathbb{N} \cup \{\infty\}$ with the usual arithmetic on $\mathbb{N}$ and with $\infty + x = x + \infty = \infty$, $0\times \infty = \infty\times 0 = 0$, $S(x)\times\infty=\infty\times S(x) = \infty$ for any $x$, and $S(\infty) =\infty$. Then $\mathbb{N}_{\infty}$ is a model of Robinson's axioms that does not satisfy $S(x) \neq x$. So $\mathbb{N}_{\infty}$ is a model of Robinson's axioms that is not a model of PA.
• I think I see the point, but I'd like to ask to be sure. I am not familiar with the notation (and possibly, the concept) of: "For example, let $\mathbb{N}$ be the structure for the language of PA with underlying set $\mathbb{N} \cup \{\infty\}$" Here, $\infty$ stands for a limit ordinal, in particular: the smallest ordinal greater than every natural number? – Bert Zangle Jun 13 '15 at 11:44
• @zanglebert: No, $\infty$ here just stand for something that is not already an element of $\mathbb N$, and the text specifies explicitly how $S$, $+$, and $\times$ works on it. It doesn't act like an ordinal. – hmakholm left over Monica Jun 13 '15 at 12:02