Mappings and Gödel numbering

Section VI of Nagel and Newman's book describes mappings. A mapping is an operation that applies to two sets called the domain and the co-domain. More specifically, a mapping associates to each element of the domain one or more elements of the co-domain.

I found the examples of mappings in this section underwhelming. For example, the book discusses the so-called Richard's paradox which is based on a mapping between the set of non-negative integers and the set of English sentences that define arithmetical properties of integers (for example, the definition of an even integer or the definition of a prime number).

However, as the book explains well, the reasoning leading to the "paradox" is actually fallacious, since it confuses reasoning (i.e., reasoning within the system) and meta-reasoning (i.e., reasoning about, and thus, outside the system). The system under consideration here is the set of rules for building English sentences describing arithmetical properties of integers (obviously, this system is not formal).

So there is really no paradox in this example. Nevertheless, Gödel mentions it in his 1931 paper because the construction of the mapping and the way it is used share some similarities with the mapping used by Gödel (who, of course, did not make any logical error in his paper).

So I think it makes more sense to jump immediately to the mapping used by Gödel. In this post, we will discuss only the first step in Gödel's construction, which is described in Part A of Section VII of Nagel and Newman's book. This first step is the famous "Gödel numbering" scheme by which Gödel establishes a mapping between the set of well-formed formulas in his formal system and the set of non-negative integers.

Before we can describe the mapping, we must describe the formal system itself, which is a combination of Whitehead and Russell's Principia Mathematica and Giuseppe Peano's axioms. We will only give enough details about the formal system to be able to explain Gödel numbers.

Since the formal system is supposed to model the arithmetic of non-negative integers, we will occasionally refer to this intended interpretation of the symbols and well-formed formulas. Of course, the formal system is (by definition) purely syntactical. Reasoning within it does not rely on meaning at all. Nevertheless, it will help to keep the intended model in mind.

First, the alphabet of the formal system is made up of the symbols shown in the leftmost column of Table 1 below (the rightmost column can be ignored until we turn our attention to the mapping). The first 8 basic signs (as Gödel calls them) are constant symbols. Their meaning is alluded to in the table.

Table 1: Basic signs (i.e., alphabet symbols)

Basic Signs of the Formal System	Gödel Numbers of the Basic Signs
0 the numeral for zero	1
f the successor function	3
¬ logical negation	5
∨ logical disjunction	7
∀ "for all" quantifier	9
( left parenthesis	11
) right parenthesis	13
= numerical equality	15
x numerical variable	17
y numerical variable	19
z numerical variable	23
... numerical variable	29
p propositional variable	172
q propositional variable	192
r propositional variable	232
... propositional variable	292
P predicate variable	173
Q predicate variable	193
R predicate variable	233
... predicate variable	293

The expression f(0) represents the successor of 0, that is, 1 = f(0) = 0 + 1; the expression f(f(0)) represents the successor of f(0), that is, 2 = f(1) = 1 + 1; the expression f(f(f(0))) represents the successor of f(f(0)), that is, 3 = f(2) = 2 + 1; etc. Therefore, any arbitrarily large integer can be represented in this system.

These "numbers," of the form f( ... f(0)...), can be combined with the equality symbol to form propositions, which are either true or false. So, under the intended interpretation, the proposition 0 = 0 is true but the proposition 0 = f(0) is false.

In turn, these propositions can be combined using the logical connectives OR and NOT. For example, under the intended interpretation, the compound proposition (0 = 0) ∨ (0 = f(0)) is true, while the compound proposition ( ¬ (0 = 0)) ∨ (0 = f(0)) is false. Note how the left and right parentheses are used both around function arguments, like in f(0), and for grouping sub-sequences of symbols that go together.

The last constant symbol we have yet to discuss is the "for all" (or universal) quantifier. Before we do so, we need to describe the first class of variables: the numerical variables x, y, z, x1, x2, etc., simply stand for unknown numerical expressions of the form f( ... f(0) ... ). Therefore, the formula 

(0 = x) ∨ (¬ (x = f(x))) 

is neither true nor false, since the value of x is unknown. We say that x is a free variable in this formula. 

To eliminate this free variable, we could either replace every free occurrence of x in the formula by a "number" (this operation is called substitution) or  we could add ∀x in front of the formula to yield: 

∀x ( (0 = x) ∨  (¬ (x = f(x))) )

In this new formula, x is not a free variable any longer because it appears within the "scope" of the universal quantifier, that is, between the two outermost parentheses. We say that x is bound by the quantifier. The intended meaning of this formula is the following: for every possible integer x, either x is equal to 0 or x is not equal to its successor, which is a true statement.

The previous formula would have been false under the intended interpretation if the logical conjunction (OR) had been replaced with a logical conjunction (AND). Even though the logical connective AND is not explicitly part of Gödel's formal system, it can easily be simulated using one of de Morgan's laws. In fact, the ∨ and ¬ connectives are logically complete, which means that all of the other logical connectives (logical implication, equivalence, exclusive or, etc.) can all be simulated using only the two logical connectives in Gödel's alphabet.

Another class of variables are the propositional variables p, q, r, p1, p2, etc., which stand for propositions such as 0 = 0, ∀x ( ¬ ( x = f(x)) ), and (¬ p) ∨ q.

Finally, the last class of variables are the predicates P, Q, R, P1, P2, etc., which stand for properties of integers. For examples, P(x) could stand for "x is a prime number" or "x is even." Note that we could have also considered predicates for relations between two or more integers such as Q(x,y) to mean "x is greater than y" or "x is divisible by y." Then, of course, we would need to include the comma in our alphabet of basic signs.

I hope that this description of the alphabet as well as the examples of formulas just mentioned are sufficient to give a sense of what it means for a formula to be well-formed, that is, syntactically correct, in Gödel's formal system. For example, the expression ¬ 0 is not a well-formed formula (or wff) since logical negation can only be applied to propositions, not to numbers. In contrast, both 0 = f(0) and 0 = 0 are wff's (but only the second one is true under the intended interpretation). This formal system is essentially first-order predicate calculus with equality, together with the basic vocabulary and axioms of integer arithmetic. We'll leave the axioms and inference rules for another time.

Now we can turn our attention to Gödel's mapping between the set of wff's (the domain) and the set of non-negative integers (the co-domain). Gödel's numbering scheme is the name given to the way he assigned a single integer to each wff (as well as to each sequence of wff's) of this formal system. 

First, as shown in Table 1 above, Gödel associated each basic sign or symbol in his alphabet with a unique integer. He mapped the constant signs to the first 8 odd integers (from 1 to 15). Then he mapped the numerical variables to the prime numbers larger than 15. Note that there are an infinite number of such variables (including subscripted ones x1, x2, etc. if we needed to add those to the alphabet) and an infinite number of primes. Then he mapped the propositional variables to the squares of primes larger than 15. Finally, he mapped the predicate variables to the cubes of primes larger than 15.

So, in the first part of the mapping just described, each alphabet symbol is mapped to a distinct integer.

Second, Gödel mapped the set of wff's to a subset of the integers as follows. Each wff is made up of an (ordered) sequence of alphabet symbols. Any wff made up of n symbols, say the wff c₁c₂c₃...c_n, is mapped to the product of n integers, namely

2^Φ(c₁) × 3^Φ(c₂) × 5^Φ(c₃) × ... × p_n^Φ(c_n) 

where p_n is the n^th prime number and Φ(c) is the Gödel number of the symbol c. Despite the complicated-looking notation, this mapping is quite simple. First, you must keep in mind the first few prime numbers (2,3,5,7,11,13,17,19,23, 29, 31, 37, 41, etc.), Second, you raise each prime to the power of the corresponding symbol in the wff. Finally, you multiply all of these powers of primes to get the Gödel number for the wff.

For example, the wff 0 = 0 is made up of three symbols, whose Gödel numbers, from left to right, are 1, 15, and 1 (see Table 1). Therefore, the Gödel number of the wff 0 = 0 is

2¹ × 3¹⁵ × 5¹

A longer (but no more complicated) example is the mapping of the wff

∀x ( ¬ ( x = f(x) ) )

to its Gödel number

2⁹ × 3¹⁷ × 5¹¹ × 7⁵ × 11¹¹ × 13¹⁷ × 17¹⁵ × 19³ × 23¹¹ × 29¹⁷ × 31¹³ × 37¹³ × 41¹³

Third (and lastly), Gödel mapped each sequence of wff's to a unique integer as follows. I will just illustrate the process with an example. Consider the following sequence of wff's:

• x = 0 whose Gödel number is 2¹⁷ × 3¹⁵ × 5¹ (let's call this number α)
• 0 = 0 whose Gödel number is 2¹ × 3¹⁵ × 5¹ (let's call this number β)
• ^{p ∨ ¬ p whose Gödel number is 2172 × 37 × 55 × 7172} (let's call this number γ)

The Gödel number for this sequence of 3 wff's is obtained by raising the first three primes to their Gödel numbers (respectively) and then multiplying them all together, yielding:

2^α × 3^β × 5^γ

that is

 2^{(217 × 315 × 51)} × 3^{(21 × 315 × 51)} × 5^{(2172 × 37 × 55 × 7172)}

Now, why did Gödel map not only the set of wff's but also the set of sequences of wff's to the set of integers? That's because each wff may (or may not) be a theorem of the formal system and each sequence of wff's may (or may not) be a proof of a theorem in the formal system. Gödel will use (and significantly extend) this mapping to complete his famous proof.

But we are not there yet. This post has only explained the Gödel numbering scheme. This is all there is to it! Sure, the numbers get large. But that does not matter, since we are not going to compute their values. We just need to know that the mapping exists.

However, there is one important property of this mapping that I have not mentioned yet. Recall that, in general, a mapping assigns to each element of the domain one or more elements of the co-domain. In this case, the mapping is really a function, since it assigns to each element of the domain exactly one element of the co-domain.  But, more importantly, Gödel's function is injective.

In an injective (or one-to-one) function, all of the elements of the domain are mapped to distinct elements of the co-domain. In the case of Gödel's function, the domain is the set of wff's "unioned" with the set of sequences of 2 or more wff's. The co-domain is the set of positive integers.

In other words, if you take any two distinct wff's or sequences of wff's, their Gödel numbers are guaranteed to be distinct integers. This is an immediate consequence of the fundamental theorem of arithmetic, according to which, each integer greater than 1 can be decomposed into a unique product of powers of prime numbers.

In fact, there is a relatively simple algorithm to convert a given integer to its corresponding wff or sequence of wff's, if it exists. But before we get to the algorithm, a few observations are in order:

• Not all integers are mapped to an element of the domain (in other words, Gödel numbering is not a surjective or onto function). For example, the number 20 = 2² × 5¹ cannot be a valid Gödel number since it is missing a power of 3. Only consecutive primes (starting at 2) can appear in a Gödel number. Another counterexample is 3¹ × 5² = 75, since the power of 2 is missing.
• None of the numbers in Table 1 above are mapped to an element of the domain. By itself, no alphabet symbol is a wff, except for the propositional variables, such as p. But in this case, its Gödel number is 2⁽²¹⁷⁾, that is a one-symbol wff, as opposed to a single symbol whose Gödel number is 2¹⁷.
• In order to prevent a wff w and the sequence made up of the single wff  w (in essence, the same wff) from having two distinct Gödel numbers, we require sequences of wff's to contain at least two wff's.

A simple recursive algorithm to convert any integer n into its corresponding wff or sequence of wff's (if it exists) is as follows:

1. If n is less than 1 or is in Table 1 above, then no wff or sequence of wff's maps to it. Terminate with failure.
2. Compute the prime factorization of n.
3. If the primes in the factorization of n are not consecutive or do not start at 2, no wff or sequence of wff's maps to n. Terminate with failure.
4. If every exponent in the prime factorization of n is one of the numbers in Table 1 above, then convert the sequence of exponents in the prime factorization of n to the corresponding sequence of alphabet symbols. If the resulting sequence is a wff, terminate and return the wff.
5. If the prime factorization of n contains a single prime power, then terminate with failure.
6. Call this algorithm recursively on each exponent in the factorization of n. If all recursive calls return a wff, then n is mapped to this sequence of wff's. Terminate and return this sequence of wff's. Otherwise, terminate with failure.

In conclusion, since wff's in Gödel's formal system are, at least under the intended interpretation, arithmetical propositions, they are part of mathematics. Therefore, Gödel numbering is a mapping between (formal) mathematical statements and integers.

In future posts, we'll get into Gödel's proofs of the incompleteness theorems, which use a more sophisticated mapping involving meta-mathematical statements.