5.8: Gödel Numbers and N

Suppose we asked you if the number

\[\begin{align} a = &35845617479137924179164136401747192469639 \\ &33857123846474406114544531958789925746411 \\ &80793941381251818131650014462814216151784 \\ &37797240847442423809728350349681982162407 \\ &86504920777012547391538781481141489453194 \\ &04814037245506808496961291846992606460711 \\ &74235438629125412438572089750021624696475 \\ &32686017988856987542814858951450213588587 \\ &45976629206001394705081676818056243914838 \\ &10641798001801554788070758142606590669736 \\ &02492132671739715266307333432862633253105 \\ &8659079930322842573861827424036194222176 \\ &00000 \end{align}\]

was the Gödel number of an \(\mathcal{L}_{NT}\)-term. How would you go about finding out? A reasonable approach would be to factor \(a\) and try to decode. It turns out that \(a = 2^{14} 3^{1025} 5^9\), and since \(1024 = 2^{10} = \ulcorner 0 \urcorner\) and \(8 = 2^3 = \ulcorner v_1 \urcorner\), you know that \(a\) is the Gödel number of the term \(+0v_1\). That was easy.

What makes this more interesting is that the above is so easy that \(N\) can prove that \(a\) is the Gödel number of a term. Establishing this fact is the goal of this section.

We will show how to construct certain \(\Delta\)-formulas, for example the formula \(Term \left( x \right)\), such that for every natural number \(a\), \(\mathfrak{N} \models Term \left( \bar{a} \right)\) if and only if \(a\) is the Gödel number of a term. Since our formula will be a \(\Delta\)-formula, this tells us that \(N \vdash Term \left( \bar{a} \right)\) if \(a\) is the Gödel number of a term.

The problem is going to be in writing down the formula. As you look at the definition of the function \(\ulcorner \cdot \urcorner\) in Definition 5.7.1, you can see that the definition is by recursion, and we will need a way to deal with recursive definitions within the constraints of \(\Delta\)-definitions. We would like to be able to write something like

\[Term \left( x \right) = \cdots \lor \left( \exists y < x \right) \left[ x = 2^{11} 3^y \land Term \left( y \right) \right] \lor \cdots,\]

but this definition is clearly circular. A technical trick will get us past this point.

But we should start at the beginning. You know that the collection of \(\mathcal{L}_{NT}\)-terms is the closure of the set of variables and the collection of constant symbols under the function symbols. We will begin by showing that the collection of Gödel numbers of variables is representable.

lemma 5.8.1.

The set

\[VARIABLE = \{ a \in \mathbb{N} | a = \ulcorner v \urcorner \: \text{for some variable} \: v \}\]

is representable.

proof

It suffices to provide a \(\Delta\)-definition for \(VARIABLE\):

\(Variable \left( x \right) =\)

\[\left( \exists y < x \right) \left( Even \left( y \right) \land 0 < y \land x = 2^{Sy} \right).\]

Notice that we use the fact that if \(x = 2^{Sy}\), then \(y < x\). It is easy to see that \(\mathfrak{N} \models Variable \left( \bar{a} \right)\) if and only if \(a \in VARIABLE\), so our formula shows that \(VARIABLE\) is a representable set.

To motivate our development of the formula \(Term\), consider the term \(t\), where \(t\) is \(+0Sv_1\). We are used to recognizing that this is a term by looking at it from the outside in: \(t\) is a term, as it is the sum of two terms. Now we need to start looking at \(t\) from the inside out: \(t\) is a term, as there is a sequence of terms, each of which is either a constant symbol, a variable, or constructed from earlier entries in the sequence by application of a function symbols of the appropriate arity. Here is a construction sequence for our term \(t\):

\[\left( v_1, Sv_1, 0, +0Sv_1 \right).\]

From this construction sequence we can look at the associated sequence of Gödel numbers:

\[\begin{align} \left( \ulcorner v_1 \urcorner, \ulcorner Sv_1 \urcorner, \ulcorner 0 \urcorner, \ulcorner +0Sv_1 \urcorner \right) &= \left( \langle 2 \rangle, \langle 11, \ulcorner v_1 \urcorner \rangle, \langle 9 \rangle, \langle 13, \ulcorner 0 \urcorner, \ulcorner Sv_1 \urcorner \rangle \right) \\ &= \left( \langle 2 \rangle, \langle 11, 8 \rangle, \langle 9 \rangle, \langle 13, 1024, \langle 11, \ulcorner v_1 \urcorner \rangle \rangle \right) \\ &= \left( \langle 2 \rangle, \langle 11, 8 \rangle, \langle 9 \rangle, \langle 13, 1024, \langle 11, 8 \rangle \rangle \right) \\ &= \left( \langle 2 \rangle, \langle 11, 8 \rangle, \langle 9 \rangle, \langle 13, 1024, 2^{12} 3^9 \rangle \rangle \right) \\ &= \left( 8, 2^{12} 3^9, 1024, 2^{14} 3^{1025} 5^{80621569} \right) \\ &= \left( 8, 80621568, 1024, a \right) \end{align}\]

where the large number \(a\) is the Gödel number of the term \(+0Sv_1\). Now we can code up this sequence of Gödel numbers as a single number

\[c = 2^9 3^{80621569} 5^{1025} 7^{a+1}.\]

Now we can begin to see waht our formula \(Term \left( a \right)\) is going to look like. We will know that \(a\) is the Gödel number of a term if there is a number \(c\) that is the code for a construction sequence for a term, and the last term is that construction sequence has Gödel number \(a\). To formalize all this, let us begin by defining the collection of construction sequences:

Definition 5.8.2.

A finite sequence of \(\mathcal{L}_{NT}\)-terms \(\left( t_1, t_2, \ldots, t_l \right)\) is called a term construction sequence for \(t_l\) if, for each \(i\), \(1 \leq i \leq l\), \(t_i\) is either a variable, the constant symbol 0, or is one of \(t_j\), \(St_j\), \(+t_j t_k\), \(\cdot t_j t_k\), or \(E t_j t_k\), where \(j < i\) and \(k < i\).

proposition 5.8.3.

The set

\(TERMCONSTRUCTIONSEQUENCE =\)

\[\{ \left( c, a \right) | c \: \text{codes a term construction sequence for the term with Gödel number} \: a \}\]

is representable.

proof

Here is a \(\Delta\)-definition for the set:

\(TermConstructionSequence \left( c, a \right) =\)

\[CodeNumber \left( c \right) \land \\ \left( \exists l < c \right) \left[ Length \left( c, l \right) \land IthElement \left( a, l, c \right) \land \\ \left( \forall e < c \right) \left( \forall i \leq l \right) \left( IthElement \left( e, i, c \right) \rightarrow \\ Variable \left( e \right) \lor e = \bar{2}^{\bar{10}} \lor \\ \left( \exists j < i \right) \left( \exists k < i \right) \left( \exists e_j < c \right) \left( \exists e_k < c \right) \\ \left( IthElement \left( e_j, j, c \right) \land IthElement \left( e_k, k, c \right) \land \\ \left[ e = e_j \lor e = \bar{2}^{\bar{12}} \cdot \bar{3}^{Se_j} \lor \\ e = \bar{2}^{\bar{14}} \cdot \bar{3}^{Se_j} \cdot \bar{5}^{Se_k} \lor \\ e = \bar{2}^{\bar{16}} \cdot \bar{3}^{Se_j} \cdot \bar{5}^{Se_k} \lor \\ e = \bar{2}^{\bar{16}} \cdot \bar{3}^{Se_j} \cdot \bar{5}^{Se_k} \lor e = \bar{2}^{\bar{18}} \cdot \bar{3}^{Se_j} \cdot \bar{5}^{Se_k} \right] \right) \right) \right].\]

This just says that \(\left( c, a \right) \in TERMCONSTRUCTIONSEQUENCE\) if and only if \(c\) is a code of length \(l\), \(a\) is the last number of the sequence coded by \(c\), and if \(e\) is an entry at position \(i\) of \(c\), then \(e\) is either the Gödel number of a variable, the Gödel number of 0, a repeat of an earlier entry, or is the Gödel number that is the result of applying \(S\), \(+\), \(\cdot\), or \(E\) to earlier entries in \(c\). As all of the quantifiers are bounded, this is a \(\Delta\)-definition, so the set \(TERMCONSTRUCTIONSEQUENCE\) is representable.

Now it would seem that to define \(Term \left( a \right)\), all we would have to do is to say that \(a\) is the Gödel number of a term if there is a number \(c\) such that \(TermConstructionSequence \left( c, a \right)\). This is not quite enough, as the quantifier \(\exists c\) is not bounded. In order to write down a \(\Delta\)-definition of \(Term\), we will have to get a handle on how large codes for construction sequences have to be.

Lemma 5.8.4.

If \(t\) is an \(\mathcal{L}_{NT}\)-term and \(\ulcorner t \urcorner = a\), then the number of symbols in \(t\) is less than \(a\).

proof

The proof is by induction on the complexity of \(t\). Just to give you an idea of how true the lemma is, consider the example of \(t\), where \(t\) is \(S0\). Then \(t\) has two symbols, while \(\ulcorner t \urcorner = a = 2^{12} 3^{1025}\), which is just a little bigger than 2.

lemma 5.8.5.

If \(t\) is a term, the length of the shortest construction sequence of \(t\) is less than or equal to the number of symbols in \(t\).

proof

Again, use induction on the complexity of \(t\).

These lemmas tell us that if \(a\) is the Gödel number of a term, then there is a construction sequence of that term whose length is less than \(a\).

lemma 5.8.6.

Suppose that \(t\) is an \(\mathcal{L}_{NT}\)-term, \(u\) is a subterm of \(t\). (In other words, \(u\) is a substring of \(t\), \(u\) is also an \(\mathcal{L}_{NT}\)-term, and \(u\) is not identical to \(t\).) Then \(\ulcorner u \urcorner < \ulcorner t \urcorner\).

Proof

Exercise 4.

lemma 5.8.7.

If \(a\) is a natural number greater than or equal to 1, then \(p_a \leq 2^{a^a}\), where \(p_a\) is the \(a\)th prime number.

proof

Exercise 5.

Now we have enough to give us our bound on the code for the shortest construction sequence for a term \(t\) with Gödel number \(\ulcorner t \urcorner = a\). Any such construction sequence must look like

\[\left( t_1, t_2, \ldots, t_k = t \right),\]

where \(k \leq a\) and each \(t_i\) is a subterm of \(t\). But then the code for this construction sequence is

\[\begin{align} c &= \langle \ulcorner t_1 \urcorner, \ulcorner t_2 \urcorner, \ldots, \ulcorner t \urcorner \langle \\ &= 2^{\ulcorner t_1 \urcorner + 1} 3^{\ulcorner t_2 \urcorner + 1} \cdots p_k^{\ulcorner t \urcorner + 1} \\ &\leq 2^{a+1} 3^{a+1} \cdots p_k^{a+1} \\ &\leq p_k^{a+1} p_k^{a+1} \cdots p_k^{a+1} \left( k \: \text{terms} \right) \\ &\leq p_a^{a+1} p_a^{a+1} \cdots p_a^{a+1} \left( a \: \text{terms} \right) \\ &= \left[ \left( 2^{a^a} \right)^{a+1} \right]^a \\ &= \left( 2^{a^a} \right)^{a^2+a}, \end{align}\]

which gives us our needed bound.

We are finally at a position where we can give a \(\Delta\)-definition of the collection of Gödel numbers of \(\mathcal{L}_{NT}\)-terms:

\(Term \left( a \right) =\)

\[\left( \exists c < \left( \bar{2}^{a^a} \right)^{a^{\bar{2}}+a} \right) TermConstructionSequence \left( c, a \right).\]

So the set

\[TERM = \{ a \in \mathbb{N} | a \: \text{is the Gödel number of an} \: \mathcal{L}_{NT} \text{-term} \}\]

is a representable set, and thus \(N\) has the strength to prove, for any number \(a\), either \(Term \left( \bar{a} \right)\) or \(\neg Term \left( \bar{a} \right)\). In Exercise 6 we will ask you to show that the set \(FORMULA\) is also representable.

Exercises

1. Assume that \(\phi\) is a formula of \(\mathcal{L}_{NT}\). Which of the following are also \(\mathcal{L}_{NT}\)-formulas? For the ones that are not formulas, why are they not formulas?
   (a) \(Term \left( \phi \right)\)
   (b) \(Term \left( \ulcorner \phi \urcorner \right)\)
   (c) \(Term \left( \overline{\ulcorner \phi \urcorner} \right)\)
2. Suppose that in the definition of \(TermConstructionSequence\), you saw the following string:
   \[\cdots \lor e = \overline{2^{11} \cdot 3^{e_j}} \lor \cdots\]
   Would that be a part of a legal \(\mathcal{L}_{NT}\)-formula? How do you know? What if the string were
   \[\cdots \lor e = \bar{2}^{\bar{11}} \cdot \bar{3}^{\bar{e_j}} \lor \cdots?\]
3. Prove Lemma 5.8.4.
4. Prove Lemma 5.8.6.
5. Prove Lemma 5.8.7 by induction. For the inductive step, if you are trying to prove that \(p_{n+1} \leq 2^{\left( n+1 \right)^{n+1}}\), use the fact that \(p_{n+1}\) is less than or equal to the smallest prime factor of \(\left( p_1 p_2 \cdots p_n \right) - 1\).
6. A proof similar to the proof that \(TERM\) is representable will show that
   \[FORMULA = \{ a \in \mathbb{N} | a \: \text{is the Gödel number of an} \: \mathcal{L}_{NT} \text{-formula} \}\]
   is also representable. Carefully supply the needed details and define the formula \(Formula \left( f \right)\). You will probably have to define the formula \(FormulaConstructionSequence \left( c, f \right)\) and estimate the length of such sequence as part of your exposition.