mjhjmtu

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.

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 $nin mathbbNmid ntext 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, (ycdot z = x) rightarrow (y = 1 lor y = x))$.

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

$forall Psubseteq mathbbN: ((0in Pland forall nin mathbbN: (nin P rightarrow (n+1)in P))rightarrow forall nin mathbbN: nin P)$

This is a sentence of second-order logic, since it involves a quantification $forall Psubseteq mathbbN$ over subsets of $mathbbN$.

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 $mathbbN$, 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 $mathbbN$ 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 $mathbbN$ 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 $mathbbN$ 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.