Gödel’s Substitution Function

Page last updated 03 Mar 2023

A formal system is a language system consisting of an alphabet, a set of axioms that is a set of formal strings composed from that alphabet, and a set of rules of inference that determine what formal strings are valid strings, and a set of rules of inference that determine what strings can be constructed from the axiom strings.

In the incompleteness proof by Kurt Gödel, a proponent of intelligent design (see Statements by Kurt Gödel), one of the principal ideas is that a Gödel numbering system is used to define a correspondence between symbol strings of a formal system and natural numbers.

Infinitely many possible Gödel Numbering Systems

Now, while Gödel chooses one particular Gödel encoding system, there are, in fact infinitely many possible different Gödel numbering encoding systems. Gödel’s numbering system works by matching every symbol of the formal system to some number - and there are infinitely many ways of doing this matching. For example, Gödel’s system matches up the symbols as:

0 ⇔ 1, f ⇔ 3, ~ ⇔ 5, ∨ ⇔ 7, ∀ ⇔ 9, ( ⇔ 11, ) ⇔ 13

and variables as 17, 19, 23 etc. (Footnote: In Gödel’s own numbering system, variables that consist of more than one symbol (e.g. x_ss0) are treated as though they are one symbol. In Gödel’s formal system, there are higher type variables, where type n variables match to 17ⁿ, 19ⁿ, 23ⁿ, … . This is ignored in the above for the sake of simplicity; it makes no difference to the logical argument.)

One could use another matching, such as:

0 ⇔ 3, f ⇔ 11, ~ ⇔ 17, ∨ ⇔ 23, ∀ ⇔ 41, ( ⇔ 53, ) ⇔ 71

and variables as 101, 107, 113 etc (every second prime number over 100)

As well as that matching of symbols to numbers, Gödel’s numbering system also matches up each such matching number to consecutively larger prime numbers:

2, 3, 5, 7, 11, 13, 17, 19, …

for example, the string:

~ (x₁ ∨ fff 0)

matches in Gödel’s system to the series of numbers:

5, 11, 17, 7, 3, 3, 3, 3, 1, 13

and this, in Gödel’s system, gives rise to the number:

2⁵ · 3¹¹ · 5¹⁷ · 7⁷ · 11³ · 13³ · 17³ · 19³ · 23¹ · 29¹³ (note: the dot · represents multiplication)

but it does not have to be done in that way.

For example, the one could have a system that only leaves out every second prime number, giving the series:

2, 5, 11, 17, 23, …

so for the above example we would have:

2⁵ · 5¹¹ · 11¹⁷ · 17⁷ · 23³ · 31³ · 41³ · 47³ · 59¹ · 67¹³

which is a completely different number.

Correspondences defined by a Gödel Numbering System

So what are the correspondences defined by a Gödel numbering system?

A Gödel numbering system defines a correspondence from

symbol strings of the formal system to natural numbers.

This correspondence is given by a function called a Gödel numbering function, and the natural numbers defined by this correspondence are called Gödel numbers. However, to be precise, the numbers that Gödel uses for the correspondence are actually of two types:

1. Gödel numbers are those given by the Gödel numbering function on symbol strings of the formal system.
2. For variables of the formal system, Gödel uses the exponent of Gödel numbers to correspond to the variables of the formal system - for example, while the Gödel number of a variable might be 2¹⁷, Gödel uses the number 17 to correspond to the variable of the formal system, rather than 2¹⁷. For convenience we will call such numbers Gödel variable numbers. (Footnote: It might be noted that while Gödel uses ‘Gödel variable numbers’ for numbers corresponding to variables, he could have used the actual Gödel numbers for variables instead. Presumably the reason he did not was that it would have entailed further complexity in his definitions of various relations. )

In Gödel’s proof, various relations of natural numbers are defined, and Gödel asserts that these number-theoretic relations correspond to relationships between symbol strings of the formal system - but that applies only when the natural numbers are Gödel numbers, or Gödel variable numbers. This is fundamental to the correspondence defined in Gödel’s proof, so we will repeat it in order to emphasize it:

Given a relation between natural numbers, there may be a corresponding relationship between symbol strings of the formal system - but when those natural numbers are not Gödel numbers of symbol strings/variables of the formal system, nor Gödel variable numbers of variables of the formal system, there cannot be such a corresponding relationship.

While this is a fundamental point, Gödel’s proof manages to ignore it, which results in an illogical confusion, as will be detailed below.

The ‘Substitution’ Function

Gödel’s ‘substitution’ function (Gödel’s relation 31) which is Sb(x, v, y), is a function of natural numbers that, for numerical values for x, v and y, returns some numerical value. (Footnote: See Functions 27-31: Defining numbers that correspond to substitution in the formal system and Relation 31 in Gödel’s paper for the formal presentation of this function in Gödel’s paper.) In the following, bold capital letters indicate symbols strings of the formal system, whereas bold lower letters indicate numbers (not numbers of the formal system). Gödel asserts that Sb(x, v, y) is a function that corresponds, by Gödel numbering to the expression that results from the substitution of a free variable V in a formal system formula X by some symbol string Y of the formal system, where x and y are Gödel numbers (where GN(u) is the Gödel numbering function x = GN(X) and y = GN(Y) and v is a Gödel variable number corresponding to a formal system variable V). The following explains the essence of the operation of this function.

If x takes the value:

2^a · 3^b · 5^c · … · p¹⁷ · q^w · r^y · s^z · …

where p, q, r and s are consecutive prime numbers,

and y takes the value:

2⁹ · 3⁷ · 5⁹,

and v takes the value 17, then the function will return the value:

2^a · 3^b · 5^c · … · p⁹ · q⁷ · r⁹ · s^w · t^v · …

Here the exponent 17 in p¹⁷ has been replaced by 9, and the exponent of the next two prime numbers above p have been replaced by 7 and 9 respectively, and the exponents of the remaining prime numbers have been ‘shifted’ up by three ‘places’.

The idea is that, if

• the number x in the function is a number that is a Gödel number that corresponds to a formal system formula with a free variable, and
• the number 17 corresponds to that free variable by the Gödel numbering system (here, for simplicity, we assume that the free variable symbol v only occurs once in the formula), and
• if y is a number that is a Gödel number that corresponds to a formal system symbol string, then the function is said to correspond to the substitution of the free variable of a formula by that symbol string of the formal system. In the above example, this is by the symbol string ‘∀∨∀’, since 2⁹ · 3⁷ · 5⁹ is the Gödel number (by the Gödel number encoding in Gödel’s paper) of that symbol string.

Note that if the variable is not free in the formula, there will be no substitution, and the function then simply has the value x; and if there is more than one occurrence of the free variable in the formula, there will be more than one occurrence of the substitution. If y is not a valid Gödel number (i.e: not a Gödel number of any formal system symbol string), then the function cannot return a value which is the Gödel number that corresponds to the substitution of the variable of the formula by some numerical value. This follows, since the notion of the correspondence of Sb(x, v, y) by Gödel numbering is such a one-to-one correspondence only when the domain of x and y are Gödel numbers, and the domain of v is Gödel variable numbers.

The Use of the ‘Substitution’ Function in Gödel’s Proof

In Gödel’s proof, after having defined the function Sb, it turns out that his actual use of the substitution function in his proof is as a combination of the function Sb and another function, the Z function (Gödel’s relation 17), that is, in the form Sb(x, v, Z(w)).

The function Z(w) is a function of natural numbers that, given the number w, returns the value:

2³ · 3³ · 5³ · … · p³ · q³ · r¹

where there are exactly w consecutive prime numbers with the exponent 3. (In Gödel’s encoding, 3 corresponds to the successor symbol s, and 1 to the zero symbol 0).

Consider now the Gödel numbering function, which we will call GN(u). This is a meta-language function that given the symbol string in the form sss…0, where there are u s’s returns the value

2³ · 3³ · 5³ · … · p³ · q³ · r¹

where there are exactly u consecutive prime numbers with the exponent 3. (In Gödel’s encoding, 3 corresponds to the successor symbol s, and 1 to the zero symbol 0).

Certainly there is a similarity between the function Z(w) and the function GN(u) - but being similar should never be confused with being identical. And since there are infinitely many different Gödel numbering functions, there are infinitely many functions like Z(w) that are similar to some Gödel numbering function.

Gödel uses the composite function Sb(x, v, Z(w)) in the Proposition V and Proposition VI of his proof, assuming that it is precisely equivalent to Sb(x, v, GN(W)). But W and w are different variables, belonging to different language systems, and with different domains. The only way around this might be to use the function Sb(x, v, Z[C(W)]), where C(W) is a conversion function that converts the number W, which is in the format of the formal system, into the format of the number-theoretic relations used in Gödel’s paper.

In his Proposition VI Gödel relies on the assumption that he can take the function Sb(x, v, Z(w)) and make the two variables x and w identical. But in fact if he was actually using the function Sb(x, v, Z[C(W)]) then that is impossible, and so his result is logically impossible.

Gödel makes fundamental errors and manages to confuse different systems by his incorrect and illogical assumptions regarding his Sb(x, v, Z(w)) function; this confusion renders his proof invalid. See also Gödel’s Proposition V and the paper PDF The Fundamental Flaw in Gödel’s Proof of his Incompleteness Theorem where it is shown in detail that Gödel incorrectly assumes that there is an equivalence between the function Z and the Gödel numbering function, and why this renders his result logically impossible. There is now a section to the paper that gives a brief summary of the underlying illogical assumption that the proof relies on, so that the reader can see in a few pages that the proof is flawed. See also the web-page Gödel’s Proposition V: The Z function which describes the contradictions in Gödel’s use of the Z function.

The Use of the ‘Substitution’ Function by Nagel-Newman and Hofstadter

As a point of interest, Nagel-Newman’s book, Gödel’s Proof, (Footnote: PDF E Nagel and J Newman: Gödel’s Proof New York University Press, revised edition, 2001. ISBN: 0814758169.) also refers to this substitution function. Nagel-Newman also makes erroneous assumptions in the treatment of that function, but the error in the use of the function is subtly different. See Nagel-Newman for an overview of Nagel-Newman’s book.

Similarly, Douglas Hofstadter also refers to a substitution function in his book, Gödel, Escher, Bach, (Footnote: Douglas Hofstadter. ‘Gödel, Escher, Bach’. Basic Books, 1999, ISBN‑13: 978‑0465026562 Gödel, Escher, Bach - Hofstadter: details.) and he also makes erroneous assumptions regarding that function. See Gödel, Escher, Bach for an overview of Hofstadter’s book.