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.

  • 1
    $\begingroup$ Every larger recursively enumerable theory is incomplete. $\endgroup$
    – Asaf Karagila
    Jun 8 '20 at 8:24
  • 2
    $\begingroup$ Usually with $\mathsf Q$ we denote Robinson arithmetic; it is a subsystem of Peano arithmetic without the axiom schema of mathematical induction. "The first incompleteness theorem applies only to axiomatic systems defining sufficient arithmetic to carry out the necessary coding constructions (of which Gödel numbering forms a part). The axioms of Q were chosen specifically to ensure they are strong enough for this purpose. Thus the usual proof of the first incompleteness theorem can be used to show that Q is incomplete and undecidable." $\endgroup$ Jun 8 '20 at 8:27
  • $\begingroup$ It is backwards to ask whether an extra axiom is "necessary" to prove incompleteness (in the sense of GIT). If a logic is incomplete, then removal of an axiom only can make it more incomplete. $\endgroup$
    – DanielV
    Jun 8 '20 at 11:01
  • $\begingroup$ @DanielV I modified the question a bit. The reason why the incompleteness of $Q$ = $PA\{induction}$ is interesting is that you can have a consistent set $S \supset Q$ such that Incomplete($Q$) $\rightarrow$ Incomplete($S$) but not Incomplete($PA$) $\rightarrow$ incomplete($S$) because $S$ is not a superset of $PA$. $\endgroup$ Jun 8 '20 at 12:14
  • $\begingroup$ @DanielV Thus, the incompleteness of $Q$ would allow us to deduce the incompleteness of $S$ for more sets than what the incompleteness of $PA$ could allow. $\endgroup$ Jun 8 '20 at 12:20

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.