Peano Axioms and First-Order Logic

Question

I've been reading Tao's Analysis 1 recently and I've learnt about the Peano Axioms. I believe I have a good understanding of the axioms and I have been able to complete the problems in the chapter. However, I am aware that Tao is adopting a rather unconventional (or non-standard) approach to the topics in the book. Therefore, I always like looking up additional info online to complement the concepts I learn in his book.

My problem concerns the difference between first and second order logic. In Tao's book, the axiom of induction is described as an 'axiom schema', which is a template for creating an infinite number of axioms for every property P(n). I'm perfectly fine with this concept, but then I looked up the Peano Axioms on Wikipedia, and the article there mentions a distinction between using first and second order logic to frame the axiom of induction.

The article seems to state that the axiom is in second-order logic when it

"quantifies over predicates (equivalently, sets of natural numbers rather than natural numbers)"

, but is in first-order logic when treated as an axiom schema. I understand the phrase 'quantifies over predicates' as being something like $\forall P$ (for all predicates). What I don't understand is 1. how is this different from an axiom schema (having an axiom for every P(n)), and also 2. why does the Wikipedia article say this is equivalent to 'sets of natural numbers'?

(Sorry if this question might seem obvious for experts out there. I'm a physics student with a mathematical bent and I'm still quite new to an axiomatic treatment of maths at such a foundational level. I've only taken an intro math course on logic so I understand things like conjunction, implication, truth-tables, for all, there exists and all that but I don't really understand the difference between first and second order logic. Thank you very much in advance for taking the time to read through my question.)

Answer 1

Let's stress one difference between first and second-order logic.

• Both have variables ($x , y, z , \dots$) whose intended interpretation are the objects we want to talk about.
• But only second-order logic has an additional range of distinguished variables ($X, P, Q, \dots$) whose intended interpretation are subsets / predicates on the objects.

To be precise then this necessitates two kinds of quantifiers, $\forall_x \,\exists_x$ for object variables and $\forall_X \,\exists_X$ to quantify over predicate variables. If you want to express induction in second-order logic, you need one single well-formed formula to do so, namely the before mentioned $$ \forall_X P \Big( P(0) \rightarrow \big( \forall_x n. \, P(n) \rightarrow P(n+1) \big) \rightarrow \forall_x n.\, P(n) \Big) $$ Now how do we quantify over all predictes/subsets/properties in first-order logic? We simply can't.

But what we can do is define well-formed formulas expressing some properties we might want to talk about, like the formula $$ \varphi(x) := \forall x \, (x = 0 \, \lor \, \exists y. x = y + 1) $$ expressing that any object is either $0$ or something plus one. And this is all we can do. The only properties we can talk about in first-order logic are those for which we can write down a formula $\varphi(x)$ and if we want the induction axiom for every one of those formulas, then we need to add the axiom for every formula. This is then usually written / described as an axiom schema for induction: $$ \text{For every $\varphi(x)$ we have the axiom }~~ \varphi(0) \rightarrow \big( \forall n. \, \varphi(n) \rightarrow \varphi(n+1) \big) \rightarrow \forall n.\, \varphi(n). $$

---

Now there is still something off here. You might ask: "Ok but how do I actually use the second-order induction axiom? It seems I need to provide some $Q$ to get going. How do I get one?"

And that's a good question. And the answer is that we need to add comprehension axioms which look like $$ \exists_X Q \,(\forall_x n. Q(n) \leftrightarrow \varphi(n)) $$ for every formula in the second-order language which does not have $Q$ as a free variable. So in the end: yes we now only have one axiom expressing all of induction, but we do also need another axiom schema.

---

References

Second-Order Arithmetic and Reverse Mathematics (Henry Towsner)

Subsystems of Second Order Arithmetic (Stephen G. Simpson)

Answer 2

In first order logic, as you describe, induction is not one axiom. It is one axiom per proposition.

But in second order logic, you can quantify over sets of naturals instead of just naturals. And so you can phrase induction as

$\forall S\subseteq\mathbb{N}.(\left(0 \in S\land (n\in S \implies (n+1) \in S)\right)\implies S = \mathbb{N}).$$

That is, for every set of naturals, if $0 \in S$ and the successor of every element of $S$ is in $S,$ then $S$ is every natural. In practice, induction is usually used with $S = \{n\in\mathbb{N} \mid P(n)\}$ where $P$ is some proposition; and indeed for any set there's a corresponding proposition $P(n) = n\in S.$ So instead of phrasing induction as a second-order axiom quantifying over sets, Wikipedia is saying you could equivalently phrase it as

$$\forall P . ((P(0) \land (P(n)\implies P(n+1)) \implies (\forall n. P(n)))$$

quantifying over all propositions. The first way of specifying it is cleaner, but only works in second-order logic, where I am allowed to quantify over sets. In first order logic, I need to have a new axiom for each proposition.

The difference is very, very subtle: Infinitely many axioms versus one axiom. An axiom schema is a metamathematical statement, saying we have infinitely many axioms of this form. An axiom is a single precise mathematical statement.