Gödel's First Incompleteness Theorem

In the first chapter you read an informal preview of Gödel's first incomnpleteness theorem. The time has come to give the detailed, precise account of this great discovery of Gödel's. (Gödel brought to our race quite a few historic results. These include his second incompleteness theorem, which is touched upon briefly at the conclusion of this chapter.)

To begin, note that at least for the time being we shall restrict ourselves to first-order formulas ``about arithmetic." More precisely, our formulas (which we will sometimes call `arithmetic formulas') will be based on this symbol set, the so-called symbol set for arithmetic:

$$S_{ar} = \{\tilde{+}, \tilde{\times}, \tilde{0}, \tilde{1} \}.$$

Notice here that some rather familiar symbols have dots atop them. Why is this? The reason for these dots is to make clear that the symbols here could be interpreted to denote any number of things. Even under the assumption that the domain in question is N, there is nothing to stop us from stipulating that, say, $\tilde{0}$ refers to the natural number 99. However, as a matter of fact, in this chapter we will use a symbol $\tilde{s}$ to refer to the object picked out by the familiar, everyday symbol s.

Next, we say that $T \subseteq L_0^S$ is a theory iff T is satisfiable and is closed under consequence. (To say that T is closed under consequence is to say that if $\phi$ is a consequence of T -- written, recall, as $\Phi \models \phi$ -- then $\phi \in \Phi$.) For every structure $\cal U$, the set

$$Th(\mbox{$\cal U$}) = \{ \phi \in L_0^S : \mbox{$\cal U$} \models \phi\}$$

is a theory, the theory of $\cal U$. The particular theory of elementary arithmetic is denoted by $Th(\mbox{$\cal R$ })$, where $\cal R$ is the structure

$$({\bf N}, \tilde{+}^{\mbox{$\cal R$}}, \tilde{\times}^{\mbox{... ...$}}, \tilde{0}^{\mbox{$\cal R$}}, \tilde{1}^{\mbox{$\cal R$}}),$$

where, recall, $\tilde{s}^{\mbox{$\cal R$ }}$, with $\tilde{s}$ a symbol, denotes that which the structure $\cal R$ maps $\tilde{s}$ to. In the case of $\cal R$, each symbol s is interpreted so as to denote exactly what you would expect. So, for example, $\tilde{0}^{\mbox{$\cal R$ }}$ denotes zero, the first natural number.

The Peano axiom system $\Phi_{PA}$ consists of the first six S_ar-sentences in the following list, as well as the seventh entry, an axiom schema (in which, recall, $\psi \frac{t}{x}$, where t is a term and x a variable, is the result of substituting t for x in $\psi$).

1.

$\forall x \, \neg (x + 1 = 0)$

2.

$\forall x \forall y \, ((x + 1 = y + 1) \rightarrow x = y)$

3.

$\forall x \, x + \tilde{0} = x$

4.

$\forall x \forall y \, x + (y + \tilde{1}) = (x + y) + \tilde{1}$

5.

$\forall x \, x \times \tilde{0} = \tilde{0}$

6.

$\forall x \forall y \, x \times (y + \tilde{1}) = x \times y + x$

7.

for all $x_1, \ldots, x_n, y$ and all $\phi \in L^{S_{ar}}$ such that free $(\phi) \subseteq \{x_1, \ldots, x_n, y\}$ the sentence

$$\forall x_1 \ldots \forall x_n \, ((\phi \frac{\tilde{0}}{y} ... ...tarrow \phi \frac{y+\tilde{1}}{y})) \rightarrow \forall y \phi)$$

First-order Peano arithmetic is a theory denoted by Th_PA. For $\Phi \subseteq L^S_0$ we let $\Phi^{\models} = \{ \phi$ $\in L^S_0 : \Phi \models \phi \}$. If T is a theory, then $T = T^{\models}$, and if $\Phi$ is satisfiable, $\Phi^{\models}$ is a theory. You should make sure you that $Th_{PA} = \Phi_{PA}^{\models}$.

For the following, we assume that some Gödel numbering scheme has been configured, according to which $n^\phi$ is the Gödel number of arithmetic formula $\phi$, and $\phi_n$ is the arithmetic formula having Gödel number n. (The specifics of the numbering scheme are at this point left to the reader.) Next,we turn to the crucial concept of representability.

Definition 6.1   Let $\Phi$ by a set of S_ar-sentences. And let $\cal R$ by an m-ary relation defined on N the natural numbers, i.e., $\cal R$ $\, \subseteq {\bf N}^m$. $\cal R$ is representable in $\Phi$ iff there is a formula $\phi(v_1, \ldots, v_m) \in L_m^{S_{ar}}$ such that for all $n_1, \ldots, n_m \in {\bf N}$:

• if $(n_1, \ldots, n_m) \in$ $\cal R$ then $\Phi \vdash \phi(\tilde{n_1}, \ldots, \tilde{n_m})$
• if $(n_1, \ldots, n_m) \not\in$ $\cal R$ then $\Phi \vdash \neg \phi(\tilde{n_1}, \ldots, \tilde{n_m})$

Here we say that $\phi(v_1, \ldots, v_m)$ represents $\cal R$ in $\Phi$. (It is important to note that the symbol $\tilde{n_i}$ is a constant interpreted to refer to the number n_i. The dot appears over n_i to make explicit the distinction between the particular constant used to denote a particular number, and that number itself.) Next, a function $f : {\bf N}^m \rightarrow {\bf N}$ is called representable in $\Phi$ iff there is a formula $\phi(v_1, \ldots, v_{m+1}) \in L_{m+1}^{S_{ar}}$ such that for all $n_1, \ldots, n_{m+1} \in {\bf N}$,

• if $f(n_1, \ldots, n_m) = \tilde{n_{m+1}}$ then $\Phi \vdash \phi(\tilde{n_1}, \ldots, \tilde{n_{m+1}})$
• if $f(n_1, \ldots, n_m) \not= \tilde{n_{m+1}}$ then $\Phi \vdash \neg \phi(\tilde{n_1}, \ldots, \tilde{n_{m+1}})$
• $\Phi \vdash \exists^{=1} v_{m+1} \, \phi(\tilde{n_1}, \ldots, \tilde{n_m}, v_{m+1})$

Here we say that $\phi(v_1, \ldots, v_{m+1})$ represents f in $\Phi$.

Definition 6.2   Let $\Phi \subseteq L_0^{S_{ar}}$. Rep $\Phi$ iff all Turing-decidable relations and Turing-computable functions on N are representable in $\Phi$.

We have the following propositions:

Proposition 6.1   Rep Th($\cal R$).

Proposition 6.2   Rep $\Phi_{PA}$.

Now, in order to prove Gödel's first incompleteness theorem, we will need a certain theorem and a key lemma. Here, first, is the theorem, and the corresponding proof.

Theorem 6.1 (Fixed Point Theorem)   If Rep $\Phi$, then for every arithmetic formula $\psi$ with one free variable (i.e., formally, for every $\psi \in L_1^{S_{ar}}$) there is an arithmetic sentence $\phi$ such that

$$\Phi \vdash \phi \leftrightarrow \psi(\tilde{n^\phi}).$$

Proof. Let f be a function from ${\bf N} \times {\bf N}$ to N defined by

$$f(n, m)=\left\{ \begin{array}{ll} n^{\delta(\tilde{m})} & \mb... ...in L_1^{S_{ar}}$} \\ 0 & \mbox{otherwise.} \end{array} \right.$$

This function takes two natural numbers n and m in as input. If n is the Gödel number for some arithmetic formula having one free variable v, then the Gödel number of the sentence resulting from substituting the constant denoting m for v is returned. If there is no such formula 0 is returned.

The function f is computable. (Why, exactly?) If $\delta$ is an arithmetic formula having one free variable, then

$$f(n^\delta, m) = n^{\delta(\tilde{m})}.$$

Since by hypothesis Rep $\Phi$, f can be represented by a formula having three free variables, say $\alpha(v_1, v_2, v_3)$. We write x, y, z for these three variables, respectively. For a given $\psi \in L_1^{S_{ar}}$ we set

$$\beta = \forall z \, (\alpha(x, x, z) \rightarrow \psi(z)).$$

$$\phi = \forall z \, (\alpha(\tilde{n^\beta}, \tilde{n^\beta}, z) \rightarrow \psi(z)).$$

Since $\beta \in L_1^{S_{ar}}$ and $\phi = \beta\frac{\tilde{n^\beta}}{x}$, it follows that $f(n^\beta, n^\beta) = n^\phi$, from which, by the definition of representability, it follows that

$$\Phi \vdash \alpha(\tilde{n^\beta}, \tilde{n^\beta}, \tilde{n^\phi}).$$ (6.1)

At this point, if we can show

$$\Phi \vdash \phi \leftrightarrow \psi(\tilde{n^\phi})$$ (6.2)

we will be done. To establish , first note that by the defintion of $\phi$ we have

$$\Phi \cup \{\phi\} \vdash \alpha(\tilde{n^\beta}, \tilde{n^\beta}, \tilde{n^\phi}) \rightarrow \psi(\tilde{n^\phi}).$$ (6.3)

From and the only-if part of , $\Phi \vdash \phi \rightarrow \psi(\tilde{n^\phi})$, is obtained. Since $\alpha$ represents the function f in $\Phi$, it follows that

$$\Phi \vdash \exists^{=1} z \, \alpha(\tilde{n^\beta}, \tilde{n^\beta}, z),$$

from which, in conjunction with , it follows that

$$\Phi \vdash \forall z \, ((\alpha(\tilde{n^\beta}, \tilde{n^\beta}, z) \rightarrow z = \tilde{n^\phi}).$$

From this last equation, in turn, we have

$$\Phi \vdash \psi(\tilde{n^\phi}) \rightarrow (\forall z \, \alpha(\tilde{n^\beta}, \tilde{n^\beta}, z) \rightarrow \psi(z)),$$

which is equivalent to the if direction of . QED

Now set

$$\Phi^\vdash = \{\phi \in L_0^{S_{ar}} : \Phi \vdash \phi\}.$$

Note that we can speak coherently about the recasting of $\Phi^\vdash$ into corresponding Gödel numbers, i.e., $\Phi^\vdash$ can be treated as $\{n^\phi : \phi \in \Phi^\vdash\}$; call this latter set $\Phi^\vdash_g$. The set $\Phi^\vdash_g$ is a set of natural numbers and as such is some unary relation on N. Now for the aforementioned key lemma:

Lemma 6.1   Suppose that $\Phi$ is consistent, that Rep $\Phi$, and that $\Phi^\vdash_g$ is representable in $\Phi$. Then there is an S_ar-sentence $\phi$ such that neither $\Phi \vdash \phi$ nor $\Phi \vdash \neg\phi$.

Proof. Assume the hypotheses of the lemma; suppose in particular that $\delta(v_1) \in L_1^{S_{ar}}$ represents the set $\Phi^\vdash_g$ in $\Phi$. Then if $n^\alpha \in \Phi^\vdash_g$, we know that $\Phi \vdash \delta(\tilde{n^\alpha})$, and this in turn holds exactly when $\Phi \vdash \alpha$; hence

$$\Phi \vdash \delta(\tilde{n^\alpha}) \mbox{ iff } \Phi \vdash \alpha.$$ (6.4)

We turn now to the Fixed Point Theorem: Set $\psi$ therein to $\neg\delta$; then there is an arithmetic sentence $\phi$ such that

$$\Phi \vdash \phi \leftrightarrow \neg\delta(\tilde{n^\phi}).$$ (6.5)

From this point it is easy to show that neither $\phi$ nor $\neg\phi$ can be proved from $\Phi$. Suppose that $\Phi \vdash \phi$. Then, with $\phi = \alpha$, it follows by it follows that $\Phi \vdash\delta(\tilde{n^\phi})$, and hence by modus tollens on it follows that $\Phi \vdash \neg\phi$. This implies that $\Phi$ is inconsistent, a contradiction (with one of our original assumptions). So suppose that $\Phi \not\vdash \phi$; then by it follows that $\Phi \vdash\delta(\tilde{n^\phi})$, and therefore -- by -- that $\Phi \vdash \phi$. This amounts also to a contradiction since $\Phi$ would be inconsistent. QED

And now, finally, we are ready to present and prove Gödel's first incompleteness theorem:

Theorem 6.2 (Gödel's First Incompleteness Theorem)   Suppose that $\Phi$ is consistent and decidable, and that Rep $\Phi$ as well. Then there is an S_ar-sentence $\phi_g$ such that neither $\Phi \vdash \phi_g$ nor $\Phi \vdash \neg\phi_g$.

Proof. The proof, given the foregoing, is straightforward. Assume the hypotheses of the theorem for some $\Phi$, and suppose furthermore for contradiction that the negation of the consequent holds, i.e., that for every arithmetic sentence $\phi$ it is true that either it or its negation can be proved from $\Phi$. From this it follows that $\Phi^\vdash_g$ is decidable: a Turing machine (or other equivalent device) can, when given an arithmetic sentence $\phi$, decide whether or not it can be proved from $\Phi$. Because by hypothesis Rep $\Phi$, $\Phi^\vdash_g$ is representable in $\Phi$. But then, using Lemma , it follows that it is not true that for every arithmetic sentence $\phi$, either it or its negation can be proved from $\Phi$ -- contradiction. QED

Suppose that $\Phi$ is a set of first-order sentences. Suppse as well that there is some way, given such a $\Phi$, to construct a first-order sentence $\psi_c$ which is such that it ``says" that $\Phi$ is consistent. Gödel's second incompleteness theorem consists in showing that any superset $\Delta$ of Peano Arithmetic is such that it cannot be proved from $\Delta$ that $\psi_c$ is true. In short, it is impossible to prove mathematically that mathematics is consistent!