Gödel’s Substitution Function

Page last updated 16 Feb 2024

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 his Gödel numbering system. This consists of a function in a meta-language (a language that talks about a sub-language such as the formal system) that defines 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 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 defined to be 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 defined to be Gödel numbers of symbol strings of the formal system, nor Gödel variable numbers of variables of the formal system, there cannot be such a corresponding relationship.

Caveats of Gödel numbering

However, there is a drawback to this Gödel numbering: number-theoretic expressions can be generated where there can be numbers which have the characteristic of a Gödel number (in that its prime factors all have exponents that belong to a specific predefined set), but where that generation has absolutely nothing to do with an association to an expression of the formal system. And that is why examining of a number-theoretic expression without taking account of how such numbers were generated may lead to an erroneous conclusion that a number in an expression has an inherent association to an expression of the formal system.

But this difficulty does not apply to a purely number-theoretic expression that contains a purely numerical function where its free variable have been substituted by specific values, and whose output has the characteristic of a Gödel number - in contrast to the same expression but which only contains the numerical value of the function’s output, rather than the function itself. This is because it can immediately be seen that this characteristic of a Gödel number has originated not externally to the system by Gödel numbering, but within the system itself, and hence has no inherent association to some expression of the formal system - in other words, that function is a function of the formal system, not a function of the meta-language, hence it cannot be a Gödel numbering function, nor can it be equivalent to a Gödel numbering function, even though it generates numbers that have the characteristic of a Gödel number in that its prime factors all have exponents that belong to a specific predefined set.

Although 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 symbol strings of the formal system, whereas bold lower letters indicate numbers of the meta-language (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 numerical value that the function outputs is not a Gödel number since it does not have any inherent correspondence to the notion of 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 is 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.

When Gödel uses the composite function Sb(x, v, Z(w)) in Proposition VI of his proof, he requires that the first variable x and the third variable w must have the same value - as in Sb(x, v, Z( x)).

But, crucially, for the function Sb(x, v, x) to be a number-theoretic function that corresponds by Gödel numbering to a function in the meta-language whose input is a formal system expression, the value given for third variable x of the function must be declared, outside of the formal system, to be a Gödel number, that is, it must be declared in the meta-language that x = GN(X), where X is some formal expression. This means that Gödel has to assume that Sb(x, v, Z( x)) is precisely equivalent to the entirety of the requirements of a correspondence by Gödel numbering, which is:

Sb(x, v, y), where y = GN(Y) and x = GN(X) and x = Y

since the free variables of Sb must be Gödel numbers.

But the free variable x of Z( x) is a variable of the formal system with the domain of natural numbers, whereas Y must be an expression of the formal system. They belonging to different language systems, and the notion that they can be equivalent as Gödel claims is nonsensical. The claim of equivalence is an absurd conflation of two different levels of language, a cheap trick to achieve a superficial appearance of self-reference within the formal system.

Really, nothing more needs to be said - Gödel’s illogical assumptions render his proof completely invalid. But we can achieve the same result in different ways, as shown below, just in case the reader might suspect that we have somehow misled them.

The Gödel number of a Gödel number

With the function GN(X), i.e, “the Gödel number of the expression  X” there is a perfectly logical and valid specific number for a specific formal system expression X, so that there must be some number n that corresponds to X by Gödel numbering. And while the formal system cannot express the Gödel numbering function, we can say that there is a valid formal system expression that has a given numerical value for the first term x in Sb(x, v, Z( x)).

But the same does not apply for the third term Z( x)). Gödel wants us to assume that this generates the notion of GN(GN(X)), i.e, “the Gödel number of the Gödel number of X”, and Gödel also wants us to assume that this is a logically valid concept that preserves the correspondences given by Gödel numbering.

But the inner GN must give an output that is a number that is not an expression of the formal system, whereas the input of the outer GN must be an input that is an expression of the formal system. And this means that there is no number that is a logically valid output for the notion GN(GN(X)).

We can also see this by ensuring that the symbols of the meta-language for numbers are not the same as for the formal system. For example, if the numbers of the meta-language are always in the format 0, 1, 2, 3, …, awhile the numbers in the formal system are in the format 0, f 0, ff 0, fff 0, …, then it is obvious that the output of the GN function cannot also be the input of the GN function And this means that there is no number that is a logically valid output for the notion GN(GN(X)).

Now, while one could force the formats for numbers to be the same in both systems, that would not somehow magically make the conflation of meta-language and sub-language logically valid. in short, that would be a fudge that should fool no-one. The entire notion of Gödel numbering is that, for every relationship between expressions A and B of the formal system there is a corresponding relation between numbers a and b, where a = GN(A) and b = GN(B) (and similarly for more than two expressions). But Gödel’s construction is an illogical distortion of the correspondence between formal system expressions and Gödel numbers.

In summary, 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 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 webpage Gödel’s Proposition V: The Z function which describes the contradictions in Gödel’s use of the Z function.

Correspondences by Gödel numbering

We can also show that there isn’t even a correspondence through Gödel numbering between the Z function and the GN function. We suppose that there might be a function in the meta-language that corresponds to Gödel’s Z function. If we have two expressions C and D of the formal system, and if c and d are defined outside of the formal system to be Gödel numbers (i.e, c = GN[C] and d = GN[D]) then, according to the conventional assertions of Gödel numbering, given the formula d = Z(c), this should mean that the Z function is a number-theoretic function that corresponds to some function in the meta-language that outputs the formal expression D when given an input that is the expression C.

Now, considering the relation d = Z(c), if a correspondence is asserted through Gödel numbering, then according to conventional assertions regarding Gödel numbering, there should be some corresponding function F of the meta-language such that D = F[C]. But if this F could be the GN function, then we would have:

D = GN[C]

but it is also the case that:

c = GN[C]

which would give us that:

c = D

but c is an expression of the meta-language, whereas D is an expression of the formal system, so that this is an illogical conflation of levels of language.

Therefore the function F cannot be the Gödel numbering function, and hence the output of Z(c) cannot be a Gödel number that corresponds to an expression of the formal language. In other words, besides the absurdity of Gödel’s claim of equivalence of the Z function and the GN function, there isn’t even a correspondence through Gödel numbering between those two functions.

The reason for this is that, on the one hand, there is an implicit claim that the Gödel numbering system is a function that is in a meta-language to two separate language systems, one being number-theoretic relations and the other the formal system. But the definition of the Gödel numbering function itself necessarily uses number-theoretic relations, and in fact part of the definition of the Z function forms part of the definition of the Gödel numbering function.

Example for specific expressions C and D

For example, if C is the formal expression f 0, then:

c = GN(C) = 2³ * 3¹ = 24

and

d = Z(c) = 2³ · 3³ · 5³ · … · p³ · q¹, where p is the 24^th largest prime and q is the 25^th largest prime, (Footnote: This number is too large to be written here in standard notation.)

and the Z function here is a number-theoretic function that, according to the conventional assertions of Gödel numbering, should correspond to a function in the meta-language that outputs the formal expression D from the input as the formal expression C, where D is ffffffffffffffffffffffff 0, and d = GN[D].

As above, regarding the relation d = Z(c), if such a correspondence is asserted through Gödel numbering, that indicates that there is some corresponding function F of the meta-language such that D = F[C]. And if this F could be the GN function, then we would have:

D = GN[C], i.e, that ffffffffffffffffffffffff 0 = GN[ f 0],

but:

c = GN[C]

indicating that

c = D

i.e,

24 = ffffffffffffffffffffffff 0

but “24” is an expression of the meta-language (since GN[ f 0] = 2³ * 3¹ = 24), whereas “ffffffffffffffffffffffff 0” is an expression of the formal system.

The crucial point here is that an expression such as “24 = ffffffffffffffffffffffff 0” has no inherent meaning of itself, a meaning is only established by asserting which language system it belongs to - and in this case, it does not belong to a logically valid language system, since the left side belongs to the meta-language, while the right side belongs to the formal system.

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.