• Use Tab, Shift + Tab keys to traverse the main menu. To enter a sub-menu use the Right Arrow key. To leave a sub-menu use the Left Arrow or the Escape key.
• The Enter or the Space key opens the active menu item.
• To skip the menu and move to the main content, press Tab after the page loads to reveal a skip button.
• To get back to the top of the page anytime, press the Home key.

Note: Full functionality of this web page requires JavaScript to be enabled in your browser.

# Gödel’s Substitution Function

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 Gödel’s incompleteness proof, 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., xff0) 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 17n, 19n, 23n,  … . 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:

~(x1 ∨ fff0)

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:

25 · 311 · 517 · 77 · 113 · 133 · 173 · 193 · 231 · 2913   (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:

25 · 511 · 1117 · 177 · 233 · 313 · 413 · 473 · 591 · 6713

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 217, Gödel uses the number 17 to correspond to the variable of the formal system, rather than 217. 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. Gödel asserts that this is a function that corresponds, by Gödel numbering with the substitution of a free variable in a formal system formula by some symbol string of the formal system (where x and y are Gödel numbers, and v is a Gödel variable number). The following explains the essence of the operation of this function.

If x takes the value:

2a · 3 · 5c · … · p17 · qw · ry · s · …

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

and y takes the value:

2 · 3 · 59,

and v takes the value 17,

then the function will return the value:

2a · 3 · 5c · … · p9 · q7 · r9 · s · tv · …

Here the exponent 17 in p17 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 · 59 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 will return a value which is not the Gödel number of any symbol string of the formal system. This follows, since the notion of correspondence of Sb(x, v, y) to a function on Gödel numbers/Gödel variable numbers is 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:

23 · 3 · 53 · … · p3 · q3 · r1

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

23 · 3 · 53 · … · p3 · q3 · r1

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. (Footnote: See also the paper The Fundamental Flaw in Gödel’s proof of his Incompleteness Theorem PDF, where it is shown that Gödel incorrectly assumes that there is an equivalence between the function Z and the Gödel numbering function - but that is absurd, since the Gödel numbering function is a function of the meta-language, and the function Z is a function of a system that the meta-language is referring to. It is indicative of a confusion of systems.) Now, as shown above, given a relation/function of natural numbers which is claimed to correspond to a relation/function on formal symbol strings, then the correspondence cannot apply unless the free variables of the number-theoretic relation/function are Gödel numbers/Gödel variable numbers.

Gödel, in his proof (in his Propositions V and VI), assumes that the function Sb(x, v, Z(w)) corresponds precisely to a function on formal symbol strings, and that the correspondence is by the Gödel numbering system. But Gödel’s actual use of the function allows that the variable w may be any numerical value, but that the correspondence by Gödel numbering still applies. This is nonsensical, since if there is a correspondence by Gödel numbering, then the numbers of the number relation/function for which the correspondence applies must be only Gödel numbers. (Footnote: Or Gödel variable numbers (as referred to above) - this is not the case here for the variable w.) In this way, Gödel makes a fundamental error 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 which discusses this in detail.

### 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: E Nagel and J Newman. Gödel’s Proof. New York University Press, revised edition, 2001. ISBN: 0814758169 Nagel and Newman, Gödel’s Proof: Details ), 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: here 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: here for an overview of Hofstadter’s book.

Footnotes:

Diverse opinions and criticisms are welcome, but messages that are frivolous, irrelevant or devoid of logical basis will be blocked. Difficulties in understanding the site content are usually best addressed by contacting me by e-mail. Note: you will be asked to provide an e-mail address - any address will do, it does not require verification. Your e-mail will only be used to notify you of replies to your comments - it will never be used for any other purpose and will not be displayed. If you cannot see any comments below, see Why isn’t the comment box loading?.

## NEWS

### Lebesgue Measure

There is now a new page on a contradiction in Lebesgue measure theory.

### Illogical Assumptions

There is now a new page Halbach and Zhang’s Yablo without Gödel which analyzes the illogical assumptions used by Halbach and Zhang.

### Easy Footnotes

I found that making, adding or deleting footnotes in the traditional manner proved to be a major pain. So I developed a different system for footnotes which makes inserting or changing footnotes a doddle. You can check it out at Easy Footnotes for Web Pages (Accessibility friendly).

### O’Connor’s “computer checked” proof

I have now added a new section to my paper on Russell O’Connor’s claim of a computer verified incompleteness proof. This shows that the flaw in the proof arises from a reliance on definitions that include unacceptable assumptions - assumptions that are not actually checked by the computer code. See also the new page Representability.

### Previous Blog Posts

For convenience, there are now two pages on this site with links to various material relating to Gödel and the Incompleteness Theorem

– a page with general links:

– and a page relating specifically to the Gödel mind-machine debate:

Gödel, Minds, and Machines

### Printer Friendly

All pages on this website are printer friendly, and will print the main content in a convenient format. Note that the margins are set by your browser print settings.

Note: for some browsers JavaScript must be enabled for this to operate correctly.

Comments on this site are welcome, please see the comment section.

Please note that this web site, like any other is a collection of various statements. Not all of this web site is intended to be factual. Some of it is personal opinion or interpretation.

If you prefer to ask me directly about the material on this site, please send me an e-mail with your query, and I will attempt to reply promptly.

Feedback about site design would also be appreciated so that I can improve the site.

Copyright © James R Meyer 2012 - 2018
www.jamesrmeyer.com