5.6: Coding Is Representable

A basic part of our coding mechanism will be the ability to code finite sequences of numbers as a single number. A number $c$ is going to be a code for a sequence of numbers $\left( k_1, k_2, \ldots, k_n \right)$ if and only if

$$c = \langle k_1, k_2, \ldots, k_n \rangle = 2^{k_1+1} 3^{k_2+1} \cdots p_n^{k_n+1},$$

where $p_n$ is the $n$th prime number.

Chaff: Be careful with the notation here. The sequence of numbers is enclosed by parentheses, while the $\langle \cdot \rangle$ denotes the coding function introduced back in Chapter 4.

We show now that $N$ is strong enough to recognize code numbers. In other words, we want to establish

proposition 5.6.1.

The collection of numbers that are codes for finite sequences is a representable set.

proof

It is easy to write a $\Delta$-definition for the set of code numbers:

$Codenumber \left( c \right) =$

$$Divides \left( SS0, c \right) \land \left( \forall z < c \right) \left( \forall y < z \right) \\ \left[ \left( Prime \left( z \right) \land Divides \left( z, c \right) \land Primepair \left( y, z \right) \right) \rightarrow Divides \left( y, c \right) \right].$$

Notice that $Codenumber \left( c \right)$ is a formula with one free variable, $c$. If you look at it carefully, all the formula says is that $c$ is divisible by $2$ and if any prime divides $c$, so do all the earlier primes. Since the definition above is a $\Delta$-definition, Corollary 5.3.15 tells us that the set $CODENUMBER$ is a representable set.

Since $CODENUMBER$ is representable and $Codenumber$ is a $\Delta$-formula, we now know (for example) that

$$N \vdash Codenumber \left( \overline{18} \right)$$

and

$$N \vdash \neg Codenumber \left( \overline{45} \right).$$

Now, suppose that we wanted to take a code number $c$, and decode it. To find the third element of the sequence of numbers coded by $c$, we need to find the exponent of the third prime number. Thus, for $N$ to be able to prove statements about the sequence coded by a number, $N$ will need to be able to recognize the function that takes $i$ and assigns it to the $i^\text{th}$ prime number, $p_i$. Proving that this function $p$ is representable is our next major goal.

proposition 5.6.2.

The function $p$ that enumerates the primes is a representable function.

proof

We start by constructing a measure of the primes. A number $a$ will be in the set $YARDSTICK$ if and only if $a$ is of the form $2^1 3^2 5^3 \cdots p_i^i$ for some $i$. So the first few elements of the set are $\{ 2, 18, 2250, 5402250, \ldots \}$.

$Yardstick \left( a \right) =$

$$Codenumber \left( a \right) \land \\ Divides \left( SS0, a \right) \land \neg Divides \left( SSSS0, a \right) \land \\ \left( \forall y < a \right) \left( \forall z < a \right) \left( \forall k < a \right) \\ \left[ \left( Divides \left( z, a \right) \land Primepair \left( y, z \right) \right) \rightarrow \\ \: \: \: \: \: \left( Divides \left( y^k, a \right) \leftrightarrow Divides \left( z^{Sk}, a \right) \right) \right].$$

If we unravel this, all we have is that 2 divides $a$, 4 does not divide $a$, and if $z$ is a prime number such that $z$ divides $a$, then the power of $z$ that goes into $a$ is one more than the power of the previous prime that goes into $a$.

Now it is relatively easy to provide a $\Delta$-definition of the function $p$:

$IthPrime \left( i, y \right) =$

$$Prime \left( y \right) \land \\ \left( \exists a \leq \left( y^i \right)^i \right) \left[ Yardstick \left( a \right) \land Divides \left( y^1, a \right) \land \neg Divides \left( y^{Si}, a \right) \right].$$

Notice the tricky bound on the quantifier! Here is the thinking behind that bound: If $y$ is, in fact, the $i^\text{th}$ prime, then here is an $a \in YARDSTICK$ that shows this fact: $a = 2^1, 3^2, \ldots y^i$. But then certainly $a$ is less than or equal to $y^i y^i, \cdots y^1 \left( i \: \text{terms} \right)$, and so $a \leq \left( y^1 \right)^i$. This bound is, of course, much larger than $a$ (the lone exception being when $i = 1$ and $y = 2$), but we will only be interested in the existence of bounds, and will pay almost no attention to making the bounds precise in any sense.

Chaff: There is a bit of tension over notation that needs to be mentioned here. Suppose that we wished to discuss the seventeenth prime number, which happens to be 59, and that $y$ is supposed to be equal to 59. The obvious way to assert this would be to state that $y = p_{17}$, but we will tend to use the explicit $\mathcal{L}_{NT}$-formula $IthPrime \left( 17, y \right)$. Our choice will give us a great increase in consistency, as our formulas become rather more complicated over the rest of this chapter. We will tend to write all of our functions in this consistent, if not exactly intuitive manner.

Now we can use the function $IthPrime$ to find each element coded by a number:

$IthElement \left( e, i, c \right) =$

$$Codenumber \left( c \right) \land \left( \exists y < c \right) \left( IthPrime \left( i, y \right) \land \\ Divides \left( y^{Se}, c \right) \land \neg Divides \left( y^{SSe}, c \right) \right).$$

So intuitively, $IthElement \left( e, i, c \right)$ is true if $c$ is a code and $e$ is the number at position $i$ of the sequence coded by $c$.

The length of the sequence coded by $c$ is also easily found:

$Length \left( c, l \right) =$

$$Codenumber \left( c \right) \land \left( \exists y < c \right) \left[ \left( IthPrime \left( l, y \right) \land Divides \left( y, c \right) \\ \land \left( \forall z < c \right) \left[ PrimePair \left( y, z \right) \rightarrow \neg Divides \left( z, c \right) \right] \right) \right].$$

All this says is that if the $l^\text{th}$ prime divides $c$ and the $\left( l + 1 \right)^\text{st}$ prime does not divide $c$, then the length of the sequence coded by $c$ is $l$.

Exercises

1. Decide if the following statements are true or false as statements about the natural numbers. Justify your answers.
   (a) $\left( 5, 13 \right) \in ITHPRIME$
   (b) $\left( 1200, 3 \right) \in LENGTH$
   (c) $IthElement \left( \bar{1}, \bar{2}, \overline{3630} \right)$ (Why are there those lines over the numbers?)