5.6: Coding Is Representable
( \newcommand{\kernel}{\mathrm{null}\,}\)
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 (k1,k2,…,kn) if and only if
c=⟨k1,k2,…,kn⟩=2k1+13k2+1⋯pkn+1n,
where pn is the nth prime number.
Chaff: Be careful with the notation here. The sequence of numbers is enclosed by parentheses, while the ⟨⋅⟩ 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
The collection of numbers that are codes for finite sequences is a representable set.
It is easy to write a Δ-definition for the set of code numbers:
Codenumber(c)=
Divides(SS0,c)∧(∀z<c)(∀y<z)[(Prime(z)∧Divides(z,c)∧Primepair(y,z))→Divides(y,c)].
Notice that Codenumber(c) 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 Δ-definition, Corollary 5.3.15 tells us that the set CODENUMBER is a representable set.
Since CODENUMBER is representable and Codenumber is a Δ-formula, we now know (for example) that
N⊢Codenumber(¯18)
and
N⊢¬Codenumber(¯45).
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 ith prime number, pi. Proving that this function p is representable is our next major goal.
The function p that enumerates the primes is a representable function.
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 213253⋯pii for some i. So the first few elements of the set are {2,18,2250,5402250,…}.
Yardstick(a)=
Codenumber(a)∧Divides(SS0,a)∧¬Divides(SSSS0,a)∧(∀y<a)(∀z<a)(∀k<a)[(Divides(z,a)∧Primepair(y,z))→(Divides(yk,a)↔Divides(zSk,a))].
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 Δ-definition of the function p:
IthPrime(i,y)=
Prime(y)∧(∃a≤(yi)i)[Yardstick(a)∧Divides(y1,a)∧¬Divides(ySi,a)].
Notice the tricky bound on the quantifier! Here is the thinking behind that bound: If y is, in fact, the ith prime, then here is an a∈YARDSTICK that shows this fact: a=21,32,…yi. But then certainly a is less than or equal to yiyi,⋯y1(iterms), and so a≤(y1)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=p17, but we will tend to use the explicit LNT-formula IthPrime(17,y). 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(e,i,c)=
Codenumber(c)∧(∃y<c)(IthPrime(i,y)∧Divides(ySe,c)∧¬Divides(ySSe,c)).
So intuitively, IthElement(e,i,c) 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(c,l)=
Codenumber(c)∧(∃y<c)[(IthPrime(l,y)∧Divides(y,c)∧(∀z<c)[PrimePair(y,z)→¬Divides(z,c)])].
All this says is that if the lth prime divides c and the (l+1)st prime does not divide c, then the length of the sequence coded by c is l.
Exercises
- Decide if the following statements are true or false as statements about the natural numbers. Justify your answers.
(a) (5,13)∈ITHPRIME
(b) (1200,3)∈LENGTH
(c) IthElement(ˉ1,ˉ2,¯3630) (Why are there those lines over the numbers?)