$$\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}}$$

# 6.2: The Self-Reference Lemma

$$\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}}$$

Our goal in this section is to show that, given any formula with only one free variable, we can construct a sentence that asserts that the given formula applies to itself. Before we do that, however, we need a lemma.

You will certainly(!) recall from Section 5.9 that we have the representable function $$\text{Num} : \mathbb{N} \rightarrow \mathbb{N}$$ such that $$\text{Num} \left( n \right) = \ulcorner \bar{n} \urcorner$$. We have a $$\Delta$$-formula, $$Num \left( x, y \right)$$, that represents the representable relation $$\text{Num}$$. We would love to know that $$N$$ is strong enough to prove, for example, the $$\mathcal{L}_{NT}$$-formula

$Num \left( \bar{3}, y \right) \leftrightarrow y = \overline{\text{Num} \left( 3 \right)}.$

Chaff: You weren't confused by the use of $$\text{Num} \left( 3 \right)$$, were you? It might be confusing since $$\text{Num}$$ is a set, and $$\text{Num} \subseteq \mathbb{N}^2$$. But we know that $$\text{Num}$$ is a function and so the thing that is named $$\text{Num} \left( 3 \right)$$ is the unique element $$y$$ of the codomain $$\mathbb{N}$$ such that the ordered pair $$\left( 3, y \right) \in \text{Num}$$. That was obvious, right?

Unfortunately, although wanting the displayed equivalence to be provable in $$N$$ is eminently reasonable, we cannot quite do it. The problem is that our formula $$Num$$ is not quite tricky enough. The lemma that we will state will give this result for any representable function, so we will state it in that generality. For our purposes, however, it will be enough to know that it applies to the representable functions $$\text{Num}$$ and $$\text{Sub}$$ of Section 5.9.

lemma 6.2.1.

Suppose that $$\text{R} \subseteq \mathbb{N}^{n+1}$$ is a representable set represented (in $$N$$) by the $$\mathcal{L}_{NT}$$-formula $$R$$. If $$\text{R}$$ is a function with domain $$\mathbb{N}^n$$ and codomain $$\mathbb{N}$$, then there is a formula $$Rf$$ such that

1. $$Rf$$ represents $$\text{R}$$, and
2. for any $$a_1, \ldots, a_n \in \mathbb{N}$$,
$N \vdash \left( Rf \left( \bar{a}_1, \ldots, \bar{a}_n, y \right) \leftrightarrow y = \overline{\text{R} \left( a_1, \ldots, a_n \right)} \right).$

proof

To improve the readability, we assume that $$n = 1$$. Let the relation $$\text{R}$$ be a function with domain $$\mathbb{N}$$, and let the formula $$Rf$$ be defined by

$Rf \left( x, y \right) : \equiv R \left( x, y \right) \land \left( \forall i < y \right) \left[ \neg R \left( x, i \right) \right].$

We first prove (1), that $$Rf$$ represents the set $$\text{R}$$. As we already know that $$R$$ represents $$\text{R}$$, it suffices to prove that $$N \vdash R \left( \bar{a}, \bar{b} \right) \iff N \vdash Rf \left( \bar{a}, \bar{b} \right)$$.

Assume that $$N \vdash Rf \left( \bar{a}, \bar{b} \right)$$. Then, we have $$N \vdash R \left( \bar{a}, \bar{b} \right)$$ by our rule of inference (PC).

For the converse, assume that $$N \vdash R \left( \bar{a}, \bar{b} \right)$$. Since $$\text{R}$$ is a function, we have $$\left( a, i \right) \not\in \text{R}$$ for all $$i < b$$. Thus, since $$R$$ represents $$\text{R}$$, we have

$N \vdash \neg R \left( \bar{a}, \bar{0} \right) \land \neg R \left( \bar{a}, \bar{1} \right) \land \ldots \land \neg R \left( \bar{a}, \overline{b-1} \right).$

By Corollary 5.3.12, this means that $$N \vdash \left( \forall i < \bar{b} \right) \left[ \neg R \left( x, i \right) \right]$$. Therefore, $$N \vdash Rf \left( \bar{a}, \bar{b} \right)$$, establishing (1).

We now turn to the proof of (2). First we prove that $$N \vdash Rf \left( \bar{a}, y \right) \rightarrow y = \overline{\text{R} \left( a \right)}$$. Since $$\text{R}$$ is a function and $$R$$ represents $$\text{R}$$, we have

$N \vdash \neg R \left( \bar{a}, \bar{0} \right) \land \ldots \land \neg R \left( \bar{a}, \overline{\text{R} \left( a \right) - 1} \right).$

(Be careful with the typeface there - remember the difference between the formula $$R$$ and the function $$\text{R}$$.)

Again by Corollary 5.3.12, we have $$N \vdash \left( \forall y < \overline{\text{R} \left( a \right)} \right) \left[ \neg R \left( \bar{a}, y \right) \right]$$. Thus, we also have

$N \vdash \left( y < \overline{\text{R} \left( a \right)} \rightarrow \neg R \left( \bar{a}, y \right) \right). \tag{i}$

By (i) and (PC), we have

$N \vdash \left( R \left( \bar{a}, y \right) \rightarrow \neg y < \overline{\text{R} \left( a \right)} \right). \tag{ii}$

By the logical axioms, we know that

$N \vdash \left[ \left( \forall i < y \right) \left[ \neg R \left( \bar{a}, i \right) \right] \rightarrow \left( \overline{\text{R} \left( a \right)} < y \rightarrow \neg R \left( \bar{a} \overline{\text{R} \left( a \right)} \right) \right) \right]. \tag{iii}$

In addition, since the formula $$R$$ represents the function $$\text{R}$$, we have

$N \vdash R \left( \bar{a}, \overline{\text{R} \left( a \right)} \right). \tag{iv}$

By (iii), (iv), and (PC), we have

$N \vdash \left( \left( \forall i < y \right) \left[ \neg R \left( \bar{a}, i \right) \right] \rightarrow \neg \overline{\text{R} \left( a \right)} < y \right). \tag{v}$

By (ii), (v), and (PC), we have

$N \vdash \left( R \left( \bar{a}, y \right) \land \left( \forall i < y \right) \left[ \neg R \left( \bar{a}, i \right) \right] \right) \rightarrow \left( \neg y < \overline{\text{R} \left( a \right)} \land \neg \overline{\text{R} \left( a \right)} < y \right). \tag{vi}$

By (vi) and the axiom N11, we have

$N \vdash \left( R \left( \bar{a}, y \right) \land \left( \forall i < y \right) \left[ \neg R \left( \bar{a}, i \right) \right] \right) \rightarrow y = \overline{\text{R} \left( a \right)},$

that is, $$N \vdash \left( Rf \left( \bar{a}, y \right) \rightarrow y = \overline{\text{R} \left( a \right)} \right)$$, which establishes the forward direction of our biconditional.

To complete the proof of (2), we also need to prove that

$N \vdash \left( y = \overline{\text{R} \left( a \right)} \rightarrow Rf \left( \bar{a}, y \right) \right).$

This is left for the reader as Exercise 1.

Now, to the Self-Reference Lemma. This is just a lovely result, insightful in its concept and far reaching in its consequences. We'd love to say that the proof was also lovely and enlightening, but to be honest, we don't have an enlightening sort of proof to show you. Sometimes the best way to describe a proof is that the argument sort of picks you up and shakes you until you agree that it does, in fact, establish what it is supposed to establish. That's what you get here. So, get ready for a technical argument and some intricate calculations, but keep in mind that the result, key to establishing the Incompleteness Theorem, really is quite pretty.

Lemma 6.2.2: Gödel's Self-reference lemma

Let $$\psi \left( v_1 \right)$$ be an $$\mathcal{L}_{NT}$$-formula with only $$v_1$$ free. Then there is a sentence $$\phi$$ such that

$N \vdash \left( \phi \leftrightarrow \psi \left( \overline{ \ulcorner \phi \urcorner} \right) \right).$

Chaff: Look at how neat this is! Do you see how $$\phi$$ "says" $$\psi$$ is true of me? And we can do this for any formula $$\psi$$! What a cool idea!

proof

We will explicitly construct the needed $$\phi$$. Recall that in Section 5.9 we defined representable functions $$\text{Num} : \mathbb{N} \rightarrow \mathbb{N}$$ and $$\text{Sub} : \mathbb{N}^3 \rightarrow \mathbb{N}$$ such that $$\text{Num} \left( n \right) = \ulcorner \bar{n} \urcorner$$ and $$\text{Sub} \left( \ulcorner \alpha \urcorner, \ulcorner x \urcorner, \ulcorner t \urcorner \right) = \ulcorner \alpha_t^x \urcorner$$. By Lemma 6.2.1 we know that there are formulas $$Numf$$ and $$Subf$$ such that

\begin{align} N &\vdash \left[ Numf \left( \bar{a}, y \right) \leftrightarrow y = \overline{\text{Num} \left( a \right)} \right], \: \text{and that} \\ N &\vdash \left[ Subf \left( \bar{a}, \bar{b}, \bar{c}, z \right) \leftrightarrow z = \overline{\text{Sub} \left( a, b, c \right)} \right]. \end{align}

Chaff: Remember, $$\text{Num}$$ is the function and $$Numf$$ is an $$\mathcal{L}_{NT}$$-formula that represents the function! Oh, and just because we're going to need it, $$\ulcorner v_1 \urcorner = 8$$.

Now suppose that $$\psi \left( v_1 \right)$$ is given as in the statement of the lemma. Let $$\gamma \left( v_1 \right)$$ be

$\forall y \forall z \left[ \left[ Numf \left( v_1, y \right) \land Subf \left( v_1, \bar{8}, y, z \right) \right] \rightarrow \psi \left( z \right) \right].$

Let us look at $$\gamma \left( n \right)$$ a little more closely, supposing that $$n = \ulcorner \alpha \urcorner$$. If the antecedent of $$\gamma \left( n \right)$$ holds, then the first part of the antecedent tells us that

y = \text{Num} \left( n \right) = \ulcorner \bar{n} \urcorner\) and the second part of the antecedent asserts that \[\begin{align} z &= \text{Sub} \left( n, 8, \ulcorner \bar{n} \urcorner \right) \\ &= \text{Sub} \left( \ulcorner \alpha \urcorner, \ulcorner v_1 \urcorner, \ulcorner \bar{n} \urcorner \right) \\ &= \ulcorner \alpha_{\bar{n}}^{v_1} \urcorner \\ &= \ulcorner \alpha_{\overline{\ulcorner \alpha \urcorner}}^{v_1} \urcorner. \end{align}

So $$z$$ is the Gödel number of {$$\alpha$$ with the Gödel number of $$\alpha$$ substituted in for $$v_1$$}.

One more tricky choice will get us to where we want to go. Let $$m = \ulcorner \gamma \left( v_1 \right) \urcorner$$, and let $$\phi$$ be $$\gamma \left( \bar{m} \right)$$. Certainly, $$\phi$$ is a sentence, so we will be finished if we can show that $$N \vdash \phi \leftrightarrow \psi \left( \overline{\ulcorner \phi \urcorner} \right)$$.

Let us work through a small calculation first. Notice that

\begin{align} \text{Sub} \left( m, 8, \ulcorner \bar{m} \urcorner \right) &= \text{Sub} \left( \ulcorner \gamma \left( v_1 \right) \urcorner, \ulcorner v_1 \urcorner, \ulcorner \bar{m} \urcorner \right) \\ &= \ulcorner \gamma \left( v_1 \right)_{\bar{m}}^{v_1} \urcorner \\ &= \ulcorner \gamma \left( \bar{m} \right) \urcorner \\ &= \ulcorner \phi \urcorner. \end{align}

With this in hand, the following are provably equivalent in $$N$$:

$\begin{array}{lr} \phi & \\ \forall y \forall z \left[ Numf \left( \bar{m}, y \right) \rightarrow \left( Subf \left( \bar{m}, \bar{8}, y, z \right) \rightarrow \psi \left( z \right) \right) \right] & \text{logic} \\ \forall y \forall z \left[ y = \overline{\text{Num} \left( m \right)} \rightarrow \left( Subf \left( \bar{m}, \bar{8}, y, z \right) \rightarrow \psi \left( z \right) \right) \right] & \text{Lemma 6.2.1} \\ \forall y \forall z \left[ y = \overline{\ulcorner \bar{m} \urcorner} \rightarrow \left( Subf \left( \bar{m}, \bar{8}, y, z \right) \rightarrow \psi \left( z \right) \right) \right] & \text{calculation} \\ \forall z \left( Subf \left( \bar{m} \bar{8}, \overline{\ulcorner \bar{m} \urcorner}, z \right) \rightarrow \psi \left( z \right) \right) & \text{quantifier rules} \\ \forall z \left( z = \overline{\text{Sub} \left( m, 8, \ulcorner \bar{m} \urcorner \right)} \rightarrow \psi \left( z \right) \right) & \text{Lemma 6.2.1} \\ \forall z \left( z = \overline{\ulcorner \phi \urcorner} \rightarrow \psi \left( z \right) \right) & \text{calculation (6.2.16-19) above} \\ \psi \left( \overline{\ulcorner \phi \urcorner} \right) & \text{quantifier rules} \end{array} \notag$

So $$N \vdash \phi \leftrightarrow \psi \left( \overline{\ulcorner \phi \urcorner} \right)$$, as needed.

Notice in this proof that if $$\psi$$ is a $$\Pi$$-formula, then $$\phi$$ is logically equivalent to a $$\Pi$$-sentence. By altering $$\gamma$$ slightly we can also arrange, if $$\psi$$ is a $$\Sigma$$-formula, to have $$\phi$$ logically equivalent to a $$\Sigma$$-sentence.

## Exercises

1. Complete the proof of Claim (2) of Lemma 6.2.1 by showing that
$N \vdash \left( y = \overline{\text{R} \left( a \right)} \rightarrow Rf \left( \bar{a}, y \right) \right).$
2. The proof of Lemma 6.2.1 depended on the use of the corollary to Rosser's Lemma, Corollary 5.3.12. To make the reading easier, we assumed in the proof that $$n = 1$$, which made the use of the corollary much easier. Work through the proof of Lemma 6.2.1 assuming that $$n = 2$$, being careful about the details.
3. Suppose that $$\psi \left( v_1 \right)$$ is $$Formula \left( v_1 \right)$$. By the Self-Reference Lemma, there is a sentence $$\phi$$ such that $$N \vdash \left( \phi \leftrightarrow Formula \left( \overline{\ulcorner \phi \urcorner} \right) \right)$$. Does $$N \vdash \phi$$? Does $$N \vdash \neg \phi$$? Justify your answer. What happens if we use $$\psi \left( v_1 \right) = \neg Formula \left( v_1 \right)$$ instead?
4. Let $$\psi \left( v_1 \right)$$ be $$Even \left( v_1 \right)$$, and let $$\phi$$ be the sentence generated when the Self-Reference Lemma is applied to $$\psi \left( v_1 \right)$$. Does $$N \vdash phi$$? Does $$N \vdash \neg \phi$$? How can you tell?
5. Show that the proof of the Self-Reference Lemma still works if we use
$\gamma \left( v_1 \right) = \exists y \exists z \left[ Numf \left( v_1, y \right) \land Subf \left( v_1, \bar{8}, y, z \right) \land \psi \left( z \right) \right].$
Conclude that if $$\psi$$ is a $$\Sigma$$-formula, then the $$\phi$$ of the Self-Reference Lemma can be taken to be equivalent to a $$\Sigma$$-sentence.