$$\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]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 6.1: Introduction to the Incompleteness Theorems

$$\newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

Suppose that $$A$$ is a collection of axioms in the language of number theory such that $$A$$ is consistent and is simple enough so that we can decide whether or not a given formula is an element of $$A$$. The First Incompleteness Theorem will produce a sentence, $$\theta$$, such that $$\mathfrak{N} \models \theta$$ and $$A \nvdash \theta$$, thus showing our collection of axioms $$A$$ is incomplete.

The idea behind the construction of $$\theta$$ is really neat: We get $$\theta$$ to say that $$\theta$$ is not provable from the axioms of $$A$$. In some sense, $$\theta$$ is no more than a fancy version of the Liar's Paradox, in which the speaker asserts that the speaker is lying, inviting the listener to decide whether that utterance is a truth or a falsehood. The challenge for us is to figure out how to get an $$\mathcal{L}_{NT}$$-sentence to do the asserting!

You will notice that there are two parts to $$\theta$$. The first is that $$\theta$$ will have to talk about the collection of Gödel numbers of theorems of $$A$$. That is no problem, as we will have a $$\Sigma$$-formula $$Thm_A \left( f \right)$$ that is true (and thus provable from $$N$$) if and only if $$f$$ is the Gödel number of a theorem of $$A$$. The thing that makes $$\theta$$ tricky is that we want $$\theta$$ to be $$Thm_A \left( \bar{a} \right)$$, where $$a = \ulcorner \theta \urcorner$$. In this sense, we need $$\theta$$ to refer to itself. Showing that we can do that will be the content of the Self-Reference Lemma that we address in the next section.

After proving the First Incompleteness Theorem, we will discuss some corollaries and improvements to the theorem before moving on to discuss the Second Incompleteness Theorem, which states that the set of axioms of Peano Arithmetic cannot prove that Peano Arithmetic is consistent, unless (of course) Peano Arithmetic is inconsistent, in which case it can prove anything. So our goal of proving that we have a complete, consistent set of axioms for $$\mathfrak{N}$$ is a goal that cannot be reached within the confines of first-order logic.