Copyright © James R Meyer 2012 - 2016 www.jamesrmeyer.com
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.
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.
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:
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.
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 · 3b · 5c · … · p17 · qw · ry · sz · …
where p, q, r and s are consecutive prime numbers,
and y takes the value:
29 · 37 · 59,
and v takes the value 17,
then the function will return the value:
2a · 3b · 5c · … · p9 · q7 · r9 · sw · 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
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.
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 · 33 · 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).
23 · 33 · 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.
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.
Diverse opinions and criticisms are welcome, but messages that are frivolous, irrelevant or devoid of logical basis will be blocked (comments will be checked before appearing on this site). 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 - this will only be used to notify you of replies to your comments - it will never be used for any other purpose, will never be displayed and does not require verification. Comments are common to the entire website, so please indicate what section of the site you are commenting on.
If you cannot see any comments below, it may be that a plug-in on your browser is blocking Disqus comments from loading. Avast anti-virus in particular is known to do this, especially with Internet Explorer and Safari. See Disqus Browser plug-in/extension conflicts or Why isn’t the comment box loading?.
Please wait for comments to load …
There is a new addition to the page Yet another flawed incompleteness proof, where Berto’s proof of incompleteness in his book There’s something about Gödel comes under scrutiny.
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).
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.
There is now a new page on Chaitin’s Constant (Chaitin’s Omega), which demonstrates that Chaitin has failed to prove that it is actually algorithmically irreducible.
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:
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.
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 - 2016