5.5: Coding - Naïvely

If you know a child of a certain age, you have undoubtedly run across coded messages of the form

\[1 \: 14 \: \: \: 1 \: 16 \: 16 \: 12 \: 5 \: \: \: 1 \: \: \: 4 \: 1 \: 25\]

where letters are coded by numbers associated with their place in the alphabet. If we ignore the spaces above, we can think of the phrase as being coded by a single number, and that number can have special properties. For example, the code above is not prime and it is divisible by exactly five distinct primes. If we like, we could say that the coding allows us to assert the same statements about the phrase that has been coded. For example, if we take the phrase

The code for this phrase is even

and coded it as a number, you might notice that the code ends in 4, so you might be tempted to say that the phrase was correct in what it asserts.

What we are doing here is representing English statements as numbers, and investigating the properties of the numbers. We can do the same thing with statements of \(\mathcal{L}_{NT}\). For example, if we take the sentence

\[= 0S0,\]

we could perhaps code this sentence as the number

\[1042492561137562500000000,\]

and then we can assert things about the number associated with the string. For example, the code for \(= 0S0\) is an element of the set of numbers that are divisible by 10, and it is in the set of numbers that are larger than the national debt. What will make all of this interesting is that we ask if the code for \(= 0S0\) is an element of the set of all codes of sentences that can be deduced from \(N\). Then we will be asking if our sentence is a theorem of \(N\). If it is, then we will know that \(N\) is inconsistent. If it is not, then \(N\) is consistent. Thus we will have reduced the question of consistency of \(N\) to a question about numbers and sets!

This is the insight that led Gödel to the Incompleteness Theorem. Given any reasonable set of axioms \(A\), Gödel showed a way to code the phrase

This phrase is not a theorem of \(A\)

as a sentence of \(\mathcal{L}_{NT}\) and prove that this sentence cannot be in the collection of sentences that are provable from \(A\). So he found a sentence that was true, but not provable. We will, in this chapter and the next, do the same thing.

But first, we will have to establish our coding mechanism. In this section we will not develop our official coding, but rather, a simplified version to give you a taste of the things to come. Let us describe the system we used for the example above.

We started by assigning symbol numbers to the symbols of \(\mathcal{L}_{NT}\), as given in Table 5.1. Notice that the symbol numbers are only assigned for the official elements of the language, so if you need to use any abbreviations, such as \(\rightarrow\) or \(\exists\), you will have to write them out in terms of their definitions.

\[\begin{array}{||c|c||c|c||} \hline \text{Symbol} & \text{Symbol Number} & \text{Symbol} & \text{Symbol Number} \\ \hline \neg & 1 & + & 13 \\ \lor & 3 & \cdot & 15 \\ \forall & 5 & E & 17 \\ = & 7 & < & 19 \\ 0 & 9 & ( & 21 \\ S & 11 & ) & 23 \\ & & v_i & 2i \\ \hline \end{array}\]

Table 5.1: Symbol Numbers for \(\mathcal{L}_{NT}\)

Then we had to figure out a way to code up sequences of symbols. The idea here is pretty simple, as we will just take the symbol numbers and code them using the scheme that we outlined in Section 4.5. For example, if we look at the sequence

\[= 0S0\]

the sequence of the symbol numbers this generates is

\[\left( 7, 9, 11, 9 \right),\]

so the code for the sequence would be (remember that we add one to the exponent when we code sequences of numbers)

\[2^8 3^{10} 5^{12} 7^{10},\]

which is also known as

\[1042492561137562500000000,\]

the example that we looked at earlier.

Notice that our coding is effective, in the sense that it is easy, given a number, to find its factorization and thus to find the string that is coded by the number.

Chaff: The word easy is used here in its mathematical sense, not in its computer science sense. In reality it can take unbelievably long to factor many numbers, especially numbers of the size that we will discuss.

Now, the problem with all of this is not that you would find it difficult to recognize code numbers, or to decode a given number, or anything like that. Rather, what turns out to be tricky is to show that \(N\), our collection of axioms, is strong enough to be able to prove true assertions about the numbers. For example, we would like \(N\) to be able to show that the term

\[\overline{1042492561137562500000000}\]

represents a number that is the code for an \(\mathcal{L}_{NT}\)-sentence. The details of showing that \(N\) has this strength will occupy us for the next several sections.

Exercise

1. Decode the message that begins this section.
2. Code up the following \(\mathcal{L}_{NT}\)-formulas using the method described in this section and in Section 4.5.
   (a) \(= + 000\)
   (b) \(= E v_1 S v_2 \cdot E v_1 v_2 v_1\)
   (c) \(\left( = 00 \lor \left( \neg < 00 \right) \right)\)
   (d) \(\left( \exists v_2 \right) \left( < v_2 0 \right)\)
3. Find the \(\mathcal{L}_{NT}\)_formula that is represented by the following numbers. A calculator (or a computer algebra system) will be helpful. Write your answer in a form that normal people can understand - normal people with some familiarity with first-order logic and mathematics, that is.
   (a) \(773190132422400000000000000\)
   (b) \(29986008216169640502067200000000\)
   (c) \(2^{22} 3^6 5^7 7^{24} 11^{22} 13^8 17^7 19^{10} 23^{24}\)