Is the axiom of induction required for proving the first Gödel’s incompleteness theorem

first-order-logicincompletenesslogicpeano-axiomssecond-order-logic

I'm reading a book about the mathematical logic. In the 6.3 chapter of that book, a theory $Q$ is introduced that contains precisely these axioms:

$Q1: \forall x. (S(x) \not= 0)$

$Q2: \forall x,y. (S(x) = S(y) \rightarrow x = y)$

$Q3: \forall x \not= 0. (\exists y. x = S(y))$

$Q4: \forall x. (x + 0 = x)$

$Q5: \forall x, y. (x + S(y) = S(x+y))$

$Q6: \forall x. (x \cdot 0 = x)$

$Q7: \forall x,y. (x \cdot S(y) = x \cdot y + x)$

It is then claimed that $Q$ is incomplete and that every larger consistent theory $T \supset Q$ is also incomplete. This claim is essentially the first Gödel's incompleteness theorem.

According to my understanding, the theory $Q$ does not contain the induction axiom:

$\forall P. [(P(0) \wedge \forall x. P(x) \rightarrow P(S(x))) \rightarrow \forall x. P(x)]$

and yet the incompleteness of $Q$ is enough to prove the incompleteness of other theories like $PA$ or $ZFC$ due to $ZFC \supset PA \supset Q$.

The questions I have are:

  • do I misunderstand this material or the induction axiom is not necessary to conclude the first Gödel's incompleteness theorem?

  • Does Gödel's first theorem apply only to the language where the unification of predicates is allowed in the statement?

  • Is $Q$ theory complete or not for the first-order language? I.e. for the language where we are allowed to write $\forall x$ where $x$ is a variable, but not $\forall P$ where $P$ is a predicate.

Best Answer

Below, all theories/sentences are first-order.

First, let's recall the meaning of (in)completeness:

A theory $T$ is incomplete if there is some sentence $\alpha$ in the language of $T$ such that $T$ neither proves nor disproves $\alpha$.

Note that $\alpha$ must be a sentence - that is, it cannot involve free variables.

It turns out that this purely syntactic situation can equivalently be described semantically:

$T$ is incomplete iff there is some sentence $\alpha$ in the language of $T$ such that $\alpha$ is true in some models of $T$ and false in other models of $T$.

This is (an equivalent rephrasing of) what could be called the "Fundamental Theorem of Provability" - but is unfortunately called the completeness theorem (even worse, it's also due to Godel!). Note that the term "(in)complete" is annoyingly overloaded: (in)completeness of a theory is a very different thing from (in)completeness of a proof system.

With that out of the way, you are correct: induction plays no role in Godel's first incompleteness theorem. The most general common phrasing of GFIT is the following (basically observed by Robinson, following Rosser's improvement on Godel's original argument):

Suppose$^1$ $T$ is a consistent first-order theory which is computably axiomatizable and interprets Robinson arithmetic $\mathsf{Q}$. Then $T$ is incomplete - that is, there is a sentence $\alpha$ in the language of $\mathsf{Q}$ such that $T$ neither proves nor disproves $\alpha$ (and so by the completeness theorem, is true in some models of $T$ and false in others).

(The term "interprets" here is a technical one - basically, it lets us shift attention to theories in other languages, like $\mathsf{ZFC}$. If you like, ignore it for now and replace it with "contains $\mathsf{Q}$.")

So $\mathsf{Q}$ is in fact very strongly incomplete. This property is called essential incompleteness.$^2$ Note that unlike mere incompleteness, essential incompleteness is not "downwards hereditary" - every essentially incomplete theory has a subtheory which is not essentially incomplete, namely the set of all tautologies. So while the incompleteness of $\mathsf{Q}$ trivially follows from the incompleteness of $\mathsf{PA}$, the essential incompleteness of $\mathsf{Q}$ isn't a trivial consequence of the essential incompleteness of $\mathsf{PA}$. This failure of downwards hereditariness means that the irrelevance of induction here is actually quite interesting.

For an in-depth analysis of what exactly is necessary for GFIT, and why in particular interpreting $\mathsf{Q}$ is fairly optimal, see e.g. this article of Beklemishev, especially section $4$.

$^1$Each of the hypotheses in GFIT (consistency, computable axiomatizability, and interpreting $\mathsf{Q}$) is necessary. It's obvious that consistency can't be dropped. To see that computable axiomatizability can't be dropped, consider the set of all true sentences of arithmetic; this is trivially complete and consistent and interprets $\mathsf{Q}$, but it isn't computably axiomatizable. Finally, there are in fact quite interesting examples of computably axiomatizable complete consistent theories - e.g. real closed fields (and this means that in a precise sense $\mathbb{R}$ is logically simpler than $\mathbb{N}$!) - but these are "weak" in the sense that they do not interpret $\mathsf{Q}$.

$^2$ Actually, essential incompleteness is usually phrased as the weaker property "$T$ is essentially incomplete iff every consistent computably axiomatizable extension of $T$ is incomplete," rather than in terms of interpretability, but this in fact implies the stronger version involving interpretations.

Related Question