Logic and Language

Logic and Language

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

This page is keyboard accessible:

• 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.

• For more information, click here: Accessibility Close this tip.

• Use

• The

• To skip the menu and move to the main content, press

• To get back to the top of the page anytime, press the

• For more information, click here: Accessibility Close this tip.

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

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.

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* ⇔

**0** ⇔ **3**, * f* ⇔

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 _{1} ∨ 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:

**2 ^{5} · 3^{11} · 5^{17} · 7^{7} · 11^{3} · 13^{3} · 17^{3} · 19^{3} · 23^{1} · 29^{13}** (note: the dot

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} · 5^{11} · 11^{17} · 17^{7} · 23^{3} · 31^{3} · 41^{3} · 47^{3} · 59^{1} · 67^{13}**

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

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:

**Gödel numbers**are those given by the Gödel numbering function on symbol strings of the formal system.- 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}**17**to correspond to the variable of the formal system, rather than**2**. For convenience we will call such numbers^{17}. (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.)**Gödel variable numbers**

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:

**2 ^{a} · 3^{b } · 5^{c} · … · p^{17} · q^{w} · r^{y} · s^{z } · …**

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

and **y** takes the value:

**2 ^{9 } · 3^{7 } · 5^{9}**,

and **v** takes the value **17**,

then the function will return the value:

**2 ^{a} · 3^{b } · 5^{c} · … · p^{9} · q^{7} · r^{9} · s^{w } · t^{v} · …**

Here the exponent **17** in **p ^{17}** has been replaced by

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**is the Gödel number (by the Gödel number encoding in Gödel’s paper) of that symbol string.^{9 }· 3^{7 }· 5^{9}

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:

**2 ^{3} · 3^{3 } · 5^{3} · … · p^{3} · q^{3} · r^{1}**

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} · 3^{3 } · 5^{3} · … · p^{3} · q^{3} · r^{1}**

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

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 (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.

Flawed proofs of the Diagonal Lemma by Panu Raatikainen and Vann McGee have been added to the Diagonal Lemma web page.

16th Mar 2015 Bishops Dancing with Pixies?

23rd Feb 2015 Artificial Intelligence

31 Mar 2015 Cranks and Crackpots

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.

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 - 2016

www.jamesrmeyer.com