# Difference between first and second order induction?

Can anyone explain the difference between induction as it's stated in first order logic and that from second order logic? I don't understand the difference as it pertains to things like Peano axioms.

• Second-order induction is an axiom which applies to any set $X\subseteq \mathbb{N}$: if $0\in X$ and $\forall n(n \in X \rightarrow n+1\in X)$, then $X=\mathbb{N}$. First-order induction is an axiom (or, to be rigorous, a scheme of axioms) which works the same way but only applies to those set defined by some first-order formula $\phi$, i.e., sets of the form $X=\{ n\in \mathbb{N}: \phi(n)\ \mathrm{is\ true}\}$. Nov 4, 2018 at 16:34
• @realdonaldtrump: of course, when we work in second-order arithmetic, the "first order induction scheme" is typically defined to include the formula "$n \in X$", and so the second-order induction axiom is just one particular axiom in the induction scheme. Nov 4, 2018 at 19:41
• @user525966 - it is not completely clear to me what you're asking. Which induction statement in second order logic are you looking at? What kind of second order theories are you interested in? The induction axioms aren't really part of logic, they are specific to theories of arithmetic. Nov 4, 2018 at 19:43
• I suggest you don't touch second-order arithmetic (including second-order induction) before you can handle first-order logic. However, my answer to your other question (which incidentally is on the hot-network-questions list) does in fact answer this one as well; first-order induction (and the only one that ever matters) always involves properties that can be written down. In any practical foundational system you can write down only countably many properties, and hence first-order induction says nothing about the subsets of naturals that do not correspond to a property you can write down. Nov 5, 2018 at 7:52

The informal statement of induction is:

For any property $$P$$ of natural numbers, if $$P(0)$$ holds, and $$P(n)$$ implies $$P(n+1)$$ for all $$n$$, then $$P(n)$$ holds for all $$n$$.

Of course, this raises the question: What exactly do we mean by a "property of natural numbers"?

One natural interpretation is to identify properties of natural numbers with sets of natural numbers. That is, for any property $$P$$, we can form the set of all natural numbers satisfying that property. And for any set of natural numbers $$X$$, we can consider the property of being in $$X$$. For example, the property of being a prime number corresponds to the set $$\{n\in \mathbb{N}\mid n\text{ is prime}\}$$

Another natural interpretation is to identify properties of natural numbers with formulas in one free variable in some logic (in this discussion, let's just talk about first-order logic in the language of arithemetic). Here the syntax of the logic gives us a language for writing down properties of natural numbers. For example, the property of being a prime number corresponds to the formula $$\lnot (x= 1)\land \forall y\, (\exists z\, (y\cdot z = x) \rightarrow (y = 1 \lor y = x))$$.

Induction under the interpretation "properties are sets" can be formalized as follows:

$$\forall P\subseteq \mathbb{N}: ((0\in P\land \forall n\in \mathbb{N}: (n\in P \rightarrow (n+1)\in P))\rightarrow \forall n\in \mathbb{N}: n\in P)$$

This is a sentence of second-order logic, since it involves a quantification $$\forall P\subseteq \mathbb{N}$$ over subsets of $$\mathbb{N}$$.

The interpretation "properties are formulas" leads to the following formalization of induction:

$$(\varphi(0)\land \forall n\, (\varphi(n)\rightarrow \varphi(n+1)) \rightarrow \forall n\,\varphi(n)$$

Here we have an infinite schema of sentences of first-order logic, one for each first-order formula $$\varphi(x)$$. It's first-order because the quantifiers only range over elements of $$\mathbb{N}$$, not subsets, and the formulas $$\varphi(x)$$ are themselves first-order.

It's worth noting that second-order induction is much stronger than first-order induction. Second-order induction applies to all subsets, while first-order induction only applies to those which can be defined by some first-order formula (and since there are are $$2^{\aleph_0}$$-many subsets of $$\mathbb{N}$$ and only $$\aleph_0$$-many first-order formulas, there are many subsets which are not definable).

The second-order Peano axioms (which consist of some basic rules of arithmetic, together with the second-order induction axiom above) suffice to pin down $$\mathbb{N}$$ up to isomorphism.

The first-order Peano axioms (which consist of some basic rules of arithmetic, together with the first-order induction axiom schema above) cannot hope to pin down $$\mathbb{N}$$ up to isomorphism (thanks to the Löwenheim-Skolem theorems). That is, there are "non-standard models" of the first-order Peano axioms, which satisfy induction for all first-order definable properties, but not for arbitrary subsets.

• It is true that second-order induction is stronger than first-order, but only when we are working in a context where we have strong comprehension axioms as well. For example, if we are working syntactically, and we want to prove some formula using second-order induction, we will have to construct the set $P$ in our formal proof before we can apply induction to it, and so the strength of the induction axiom will depend on which sets we can construct in our proofs - essentially reducing things to the question of which formulas have a comprehension axiom. Nov 4, 2018 at 19:27
• Of course, when we work semantically with full second order semantics, in essence we have comprehension for all subsets of N, and so second-order induction is much stronger than the first-order induction scheme in that setting. But when we begin to look at particular formal theories, the relationship is more complex. Nov 4, 2018 at 19:31
• @CarlMummert Yes, of course when I write "second-order" in this answer, I mean with the full semantics. Nov 4, 2018 at 19:49