Logic and Language
Load the menuLoad the menu


Copyright   James R Meyer    2012 - 2020 https://www.jamesrmeyer.com

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

Gödel’s 1934 Undecidability lectures

This article demonstrates the inherent conflation of language in lectures given by Gödel at the Institute for Advanced Study during the spring of 1934, the notes of which were taken by S. C. Kleene and J.B. Rosser. (Footnote: Gödel, Kurt. “On Undecidable Propositions of Formal Mathematical Systems, Mimeographed lecture notes by SC Kleene and JB Rosser”, Institute for Advanced Study, Princeton, NJ (1934): 39-74,  also published in the book The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions, ed Martin Davis, Raven Press Books, 1965,
  and in Kurt Gödel: Collected Works: Volume I: Publications 1929-1936. Vol. 1, ed Solomon Feferman, Oxford University Press, USA, 1986.)
Note that in the following text, for clarity (as in my English translation of Gödel’s 1931 incompleteness paper) we shall give a blue background to all instances of formulas, variables, and numerical values of the formal system, or terms that indicate such sequences of the formal system.

 

In section 5: Representation of recursive functions, Gödel defines a function z by:

 

We abbreviate certain formal expressions as follows: z0 for 0, z1 for N(0), z2 for N(N(0)), etc. The z’s then represent the natural numbers in the formal logic.

 

Gödel later in that section states: (Footnote: In the Gödel Collected Works, Vol 1, the γ(x, y) function is given as 𝔖(x, y) ) (Footnote: Note that where Gödel says “is a number”, that means that it is a number given by what we now call the Gödel numbering function, as described in more detail in his paper, see Gödel numbering function )

 

γ(x, y) is the number of the formula which results when we replace all free occurrences of w by zy in the formula whose number is x.

 

and continues:

In fact, if a is the number of w and χ(n) the number of zn , γ(x, y) is Sb[x a/χ(y))].

 

and also:

Hence there is a formula B(u, v) which represents x 𝔅 y and a formula S(u, v) which represents γ(x, y).

 

and he continues:

Let U(w) be the formula ΠvB(v, S(w, w))] and let p be the number of U(w). Now U(zp) is the formula which results when we replace all free occurrences of w by zp in the formula whose number is p, and hence has the number γ(p, p). Hence if U(zp) is provable, there is a k such that k 𝔅 γ(p, p). But since S(u, v) represents γ(x, y) and B(u, v) represents x 𝔅 y, it follows that B(zp, S(zp, zp))] is provable.

 

Hence, in a rather roundabout way, Gödel generates the apparent self-reference:

S(zp, zp) = GN{ ΠvB(v, S(zp, zp))] }

 

where GN is the Gödel numbering function, and where S(zp, zp) appears on both sides of the equation, where the left side is an expression of the sub-language that is the formal system, and the right side is an expression of the meta-language to that sub-language (the relevant text from the lectures is given below in the appendix).

 

To demonstrate the conflation of language that is inherent in the above, all that is required is to observe that there is no reason at all in principle to use any mathematical system other than the formal system to express all the arithmetical relations and functions that are used. After all, since one of the principal claims is that the formal system can express all the arithmetical concepts used, then in principle, there is no problem whatsoever in stating all these concepts directly in the formal language. (Footnote: Of course, stating all the mathematical statements in the formal language would be extremely long-winded, but that in itself does not affect the underlying principle.) Of course, it is also the case that if the formal system could not express the mathematical concepts used, then it would not be surprising at all if it were incomplete.

 

Furthermore, this simplifies matters immensely, since we should now only have one sub-language - the mathematical formal language - and one meta-language, the meta-language that talks about this mathematical sub-language, with no dichotomy of mathematical systems to confuse matters.

 

So, in this way, we produce a perfect separation of meta-language and sub-language - right?

 

Wrong.

 

It is now patently obvious that the definition of the Gödel numbering system, since that definition necessarily requires mathematical functions, is itself a conflation of the meta-language and the mathematical sub-language. It involves a direct conflation of two distinct levels of language. Of itself, that does not result directly in any illogical statement, but it should be obvious that a careless usage of that numbering system can produce illogical results.

 

The crucial fact that must be recognized is that while every instance of the application of the Gödel numbering function on an sequence of symbols of the formal system always produces a unique corresponding number, the converse does not apply. Numbers can be generated entirely within the formal system that have no inherent correspondence by Gödel numbering to sequences of the formal system, but which happen to have the same format as a Gödel number. Assuming, as Gödel does, that one can treat such instances as though they are numbers that correspond by Gödel numbering to sequences of the formal system is patently absurd. (Footnote: See also the paper The Fundamental Flaw in Gödel’s Proof of his Incompleteness Theorem for more on the absurdity of assuming false equivalence.)

 

The resultant discrepancies, such as statements that appear to self-reference, rather than indicating some profound insight regarding incompleteness, are merely indicators of the underlying problem, and are the result of the confusion engendered by the fact that Gödel’s meta-language refers, on the one hand, to number-theoretic relations as objects, which means that any system of number-theoretic relations (including the formal system) that he refers to is a sub-language to that meta-language, but at the same time, on the other hand, this meta-language uses number-theoretic relations as an inherent part of that meta-language in order to define the Gödel numbering system.

 

It is this fact that there are

  • numbers in number-theoretic relations/functions that do logically correspond to sequences of symbols of the formal system by Gödel numbering
    but also
  • numbers in number-theoretic relations/functions that do not logically correspond to sequences of symbols of the formal system by Gödel numbering

that results in the confusion and apparent self-reference, since it is inevitable that there can be confusion as to which numbers can logically correspond to sequences of symbols of the formal system. It is precisely this confusion which Gödel uses to produce his illogical result.

 

There is no logical “undecidability” result as indicated by Gödel’s fallacious outline proof. A proof by contradiction - as is the proof in these lectures - simply means that the contradiction indicates that at least one of the prior assumptions is wrong or/and one of the steps is incorrect. Gödel’s naive presumption is that the contradiction engendered by his outline proof (Footnote: The contradiction generated by an assumption that a certain statement or its negation must be provable, vis-a-vis the appearance (generated by language conflation) that neither the statement nor its negation is provable.) was simply the direct result of the assumption that the formula ΠvB(v, S(zp, zp))] nor its negation is provable. But, as demonstrated above, that contradiction that was engendered by his outline proof was the result of conflation of levels of language. Remove that conflation and Gödel’s result disappears.

 

The above demonstrates the folly of the attempt to make a formula of a well-defined consistent formal system self-reference. It should be obvious that the apparent self-reference is not within the formal system, since without any mention of the Gödel numbering function, the formal system formula shows no self-reference whosoever. In the lectures, where it is claimed that a formal system statement appears to refer to itself as:

S(zp, zp) = GN{ ΠvB(v, S(zp, zp))] }

 

and where S(zp, zp) appears on both sides of the equation, but the fact is that the formal system is not referring to itself at all. This is a statement that confuses levels of language, since the left side is an expression of the sub-language (the formal system) while on the right side the Gödel numbering function is a not an expression of the formal language. It is only by the combination of a function that conflates the sub-language of the formal system and the meta-language to that system that can generate the apparent (and illogical) self-reference. Anyone who thinks that this demonstrates that the formal system can reference itself is making a grave error, as this apparent self-reference is generated solely by the conflation of levels of language caused by the use of a Gödel numbering system that is itself defined in terms of a conflation of two levels of language.

 

That conflation is a clear demonstration of the abject futility of such attempts at proving incompleteness, where primitive recursive functions are described in detail, and then the application of such to an actual formal system is skimmed over with no attention to detail. For the simple-minded, the fudge succeeds in concealing the real conflation of meta-language and sub-language that is the nub of the flaw in Gödel’s proof.

 

Some other remarks

Reading the lecture notes, it is readily apparent that almost all of the material is on primitive recursive functions and relations, and assertions as to how the computability of such functions and relations means that they are expressible in the formal system. But the crucial aspects of meta-language and sub-language are only afforded a few brief paragraphs.

 

In the lectures, Gödel places a lot of emphasis on constructibility, but for an entity to have the property that it can be constructed simply means that it is a sequence of symbols that is generated by prior sequences of symbols, either directly in the paper itself, or indirectly referred to by the paper. As such, being constructible, of itself, does not confer on an entity some sort of validity, since any such validity depends on the entire chain of construction, and it only takes one faulty link in the chain to destroy the assumed validity of the construction. And since, as demonstrated above, and elsewhere on this site, Gödel’s construction conflates at least two levels of language, the constructibility of Gödel’s sequence is worthless.

section divider

Footnotes:

section divider

The text of Gödel’s undecidability paragraphs

Let U(w) be the formula ΠvB(v, S(w, w))] and let p be the number of U(w). Now U(zp) is the formula which results when we replace all free occurrences of w by zp in the formula whose number is p , and hence has the number γ(p, p). Hence if U(zp) is provable, there is a k such that k 𝔅 γ(p, p). But since S(u, v) represents γ(x, y) and B(u, v) represents x 𝔅 y, it follows that B(zp, S(zp, zp))] is provable. Also, it is a property of our system that if ΠvF(v) is provable, then F(zl) is provable for all l; consequently, if U(zp) is provable, ¬B(zp, S(zp, zp)), as well as B(zp, S(zp, zp)), is provable, and the system contains a contradiction. Thus we conclude that U(zp) cannot be proved unless the system contains a contradiction.

 

Next we raise the question of whether ¬U(zp) can be proved if the system is not contradictory. If the system is not contradictory, U(zp) cannot be proved, as just seen. But U(zp) is the formula with the number γ(p, p), so that, for all k, ¬k 𝔅 γ(p, p). Therefore ¬B(zp, S(zp, zp)) is provable for all k. If furthermore ¬U(zp) , i.e. ¬ΠvB(v, S(w, w))] is provable, then we have that a formula is provable which asserts that ¬B(zp, S(zp, zp)) is not true for all k, and this, together with the fact that ¬B(zp, S(zp, zp)) is provable for all k, makes the system intuitively contradictory. In other words, if we consider the system to be contradictory not merely if there is an A such that both A and ¬A are provable, but also if there is an F such that all of the formulas, ¬ΠvF(v), F(v0), F(v1)… are provable, then, if ¬U(zp) is provable, the system is contradictory in this weaker sense. Hence neither U(zp) nor ¬U(zp) is provable, unless the system is contradictory.

 

Interested in supporting this site?

You can help by sharing the site with others. You can also donate at Go Get Funding: Logic and Language where there are full details.

 

As site owner I reserve the right to keep my comments sections as I deem appropriate. I do not use that right to unfairly censor valid criticism. My reasons for deleting or editing comments do not include deleting a comment because it disagrees with what is on my website. Reasons for exclusion include:
Frivolous, irrelevant comments.
Comments devoid of logical basis.
Derogatory comments.
Long-winded comments.
Comments with excessive number of different points.
Questions about matters that do not relate to the page they post on. Such posts are not comments.
Comments with a substantial amount of mathematical terms not properly formatted will not be published unless a file (such as doc, tex, pdf) is simultaneously emailed to me, and where the mathematical terms are correctly formatted.


Reasons for deleting comments of certain users:
Bulk posting of comments in a short space of time, often on several different pages, and which are not simply part of an ongoing discussion. Multiple anonymous usernames for one person.
Users, who, when shown their point is wrong, immediately claim that they just wrote it wrong and rewrite it again - still erroneously, or else attack something else on my site - erroneously. After the first few instances, further posts are deleted.
Users who make persistent erroneous attacks in a scatter-gun attempt to try to find some error in what I write on this site. After the first few instances, further posts are deleted.


Difficulties in understanding the site content are usually best addressed by contacting me by e-mail.

 

Note: a password enables editing of comments, an email enables notification of replies

HashOver logoBased on HashOver Comment System by Jacob BarkdullHashOver logo

Copyright   James R Meyer   2012 - 2020
https://www.jamesrmeyer.com