Difference between first and second order induction?

Question

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.

Answer 1

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.