$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 4.1: Introduction to Incompleteness

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$ $$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

Now, we hope that you have been paying attention closely enough to be bothered by the title of this chapter. The preceding chapter was about completeness, and we proved the Completeness Theorem. Now we seem to be launching an investigation of incompleteness! This point is pretty confusing, so let us try to start out as clearly as possible.

In Chapter 3 we proved the completeness of our axiomatic system. We have shown that the deductive system described in Chapter 2 is sound and complete. What does this mean? For the collection of logical axioms and rules of inference that we have set out, any formula $$\phi$$ that can be deduced from a set of nonlogical axioms $$\Sigma$$ will be true in all models of $$\Sigma$$ under any variable assignment function (that's soundness), and furthermore any formula $$\phi$$ that is true in all models of $$\Sigma$$ under every assignment function will be deducible from $$\Sigma$$ (that's completeness). Thus, our deductive system is as nice as it can possibly be. The rough version of the Completeness and Soundness Theorems is: We can prove it if and only if it is true everywhere.

Now we will change our focus. Rather than discussing the wonderful qualities of our deductive system, we will concentrate on a particular language, $$\mathcal{L}_{NT}$$, and think about a particular structure, $$\mathfrak{N}$$, the natural numbers.

Wouldn't life be just great if we knew that we could prove every true statement about the natural numbers? Of course, the statements that we can prove depend on our choice of nonlogical axioms $$\Sigma$$, so let us start this paragraph over.

Wouldn't life be just great if we could find a set of nonlogical axioms that could prove every true statement about the natural numbers? We would love to have a set of axioms $$\Sigma$$ such that $$\mathfrak{N} \models \Sigma$$ (so our axioms are true statements about the natural numbers) and $$\Sigma$$ is rich enough so that for every sentence $$\sigma$$, if $$\mathfrak{N} \models \sigma$$, then $$\Sigma \vdash \sigma$$. Since $$\Sigma \vdash \sigma$$ has a model, we know that $$\Sigma$$ is consistent, so by soundness our wished-for $$\Sigma$$ will prove exactly those sentences that are true in $$\mathfrak{N}$$. The set of sentences of $$\mathcal{L}_{NT}$$ that are true in $$\mathfrak{N}$$ is called the Theory of $$\mathfrak{N}$$, or $$Th \left( \mathfrak{N} \right)$$.

Since we know that a sentence is either true in $$\mathfrak{N}$$ or false in $$\mathfrak{N}$$, this set of axioms $$\Sigma$$ is complete - complete in the sense that given any sentence $$\sigma$$, $$\Sigma$$ will provide either a deduction of $$\sigma$$ or a deduction of $$\neg \sigma$$.

Definition 4.1.1.

A set of nonlogical axioms $$\Sigma$$ in a language $$\mathcal{L}$$ is called complete if for every $$\mathcal{L}$$-sentence $$\sigma$$, either $$\Sigma \vdash \sigma$$ or $$\Sigma \vdash \neg \sigma$$.

Chaff: To reiterate, in Chapter 3 we showed that our deductive system is complete. This means that for a given $$\Sigma$$, the deductive system will prove exactly those formulas that are logical consequences of $$\Sigma$$. When we say that a set of axioms is complete, we are saying that the axioms are strong enough to provide either a proof or a refutation of any sentence. This is harder.

Our goal is to find a complete and consistent set of $$\mathcal{L}_{NT}$$-axioms $$\Sigma$$ such that $$\mathfrak{N} \models \Sigma$$. So this set $$\Sigma$$ would be strong enough to prove every $$\mathcal{L}_{NT}$$-sentence that is true in the standard structure $$\mathfrak{N}$$. Such a set of axioms is said to axiomatize $$Th \left( \mathfrak{N} \right)$$.

Definition 4.1.2.

A set of axioms $$\Sigma$$ is an axiomatization of $$Th \left( \mathfrak{N} \right)$$ if for every sentence $$\sigma \in Th \left( \mathfrak{N} \right)$$, $$\Sigma \vdash \sigma$$.

Actually, as stated, it is pretty easy to find an axiomatization of $$Th \left( \mathfrak{N} \right)$$: Just let the axiom set be $$Th \left( \mathfrak{N} \right)$$ itself. This set clearly axiomatizes itself, so we are finished! Off we go to have a drink. Of course, our answer to the search has the problem that we don't have an easy way to tell exactly which formulas are elements of the set of axioms. If we took a random sentence in $$\mathcal{L}_{NT}$$ and asked you if this sentence were true in the standard structure, we doubt you'd be able to tell us. The truth of nonrandom sentences is also hard to figure out - consider the twin prime conjecture, that there are infinitely many pairs of positive integers $$k$$ and $$k + 2$$ such that both $$k$$ and $$k + 2$$ are prime. People have been thinking about that one for over 2000 years and we don't know if it is true or not, although we seem to be currently (summer 2014) getting close. But at least as of now, we really have no idea if the twin prime conjecture is in $$Th \left( \mathfrak{N} \right)$$ or not. So it looks like $$Th \left( \mathfrak{N} \right)$$ is unsatisfactory as a set of nonlogical axioms.

So, to refine our question a bit, what we would like is a set of nonlogical axioms $$\Sigma$$ that is simple enough so that we can recognize whether or not a given formula is an axiom (so the set of axioms should be decidable) and strong enough to prove every formula in $$Th \left( \mathfrak{N} \right)$$. So we search for a complete, consistent, decidable set of axioms for $$\mathfrak{N}$$. Unfortunately, our search is doomed to failure, and that fact is the content of Gödel's First Incompleteness Theorem, which we shall prove in Chapter 6 then again in Chapter 7. (You know a theorem is important if we're going to prove it more than once...)

What, precisely, is it that we will do? Given any complete, consistent, and decidable set of axioms for $$\mathfrak{N}$$, we are going to find a sentence $$\sigma$$ that is a true statement about the natural numbers (so $$\sigma \in Th \left( \mathfrak{N} \right)$$) but $$\sigma$$ will not be provable from the collection of axioms. And how complicated must this sentence $$\sigma$$ be? It turns out that it doesn't have to be very complicated at all. The next subsection will provide some structure to the collection of $$\mathcal{L}_{NT}$$-formulas and give us some language with which to talk about the complexity of formulas.