Gödel’s 1934 Undecidability lectures

Page last updated 20 July 2022

Kurt Gödel

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 books:
The undecidable: Basic papers on undecidable propositions, unsolvable problems and computable functions, ed Martin Davis, Raven Press Books, 1965, and
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:

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

and continues:

and also:

and he continues:

When Gödel states that χ(n) is “the number of z_n”, that raises more questions than it answers, since the Gödel number of  z_n necessarily requires that  z_n is a sequence of symbols that is the format of a number in the formal system (N(0), N(N(0)), N(N(N(0))), …), whereas Gödel uses n as a number without specifying any format, although we can note that outside of the formal system he uses conventional base 10 positional notation. This can be seen to be the same fudge as in his original paper, where he simply assumes that a purely number-theoretic function is equivalent to the Gödel numbering function see Gödel’s flawed assumption of equivalence and The Flaw in Gödel’s proof of his Incompleteness theorem and also the formal paper The Fundamental Flaw in Gödel’s Proof of his Incompleteness Theorem.

We follow the line of Gödel’s argument above while bearing in mind the ambiguity of what is intended by χ(n). In the following, we will use GN to indicate the Gödel numbering function, which is not a function of the formal system, nor is it a purely number-theoretic function. This gives us that Gödel is asserting:

U(w) = Πv[¬B(v, S(w, w))]

and

p = GN{ U(w) }

so:

U(z_p) = Πv[¬B(v, S(z_p, z_p))]

and so:

γ(p, p) = GN{ U(z_p) } = GN{ Πv[¬B(v, S(z_p, z_p))] }

and since S(u, v) is the expression in the formal system that expresses γ(x, y), and since both should evaluate as the same numerical value, we now have the rather roundabout way in which Gödel generates the apparent self-reference:

(1)S(z_p, z_p) = GN{ Πv[¬B(v, S(z_p, z_p))] }

We note that S(z_p, z_p) appears on both sides of the equation, but 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). Hence this equation (1) is an illogical equivalence, since the equivalence is being stated in the meta-language, but the left side is a sequence of symbols of the formal system, and such symbol sequences are simply objects in the meta-language and have no syntactical meaning in the meta-language. Hence, within the meta-language the expression S(z_p, z_p) does not evaluate as a numerical value, it only does so within the formal system. This means that the entire equation (1) is asserting an equivalence between the expression on the left side that has no numerical value in the meta-language and an expression on the right side that has a numerical value in that meta-language. The absurdity of the entire equation (1) is an indication of an illogical confusion of language at some prior point in the argument; the source of this confusion is demonstrated below.

It is noteworthy that Gödel never clearly defines the function Sb in these lectures, even though it is a crucial part of his argument. It is however clearly defined as his relation 31 in his original paper (Footnote: Here I have changed the variable names to avoid confusion with the names used in the 1934 lectures. The English translation of the definition of the function Sb in the original paper can be seen at definition of Sb.) as Sb[h, ^a/_k], where h =GN(H), k = GN(K), and a is a prime number greater than 13, where if H is a formula with a free variable (corresponding to a) to be substituted by a symbol sequence K, then Sb[h, ^a/_k] is the value of the Gödel number of the formula that results from that substitution. Note that the sequence of symbols K is not necessarily a number, and that the result of such a substitution is not necessarily a valid formula in the formal system.

At this point we note that the fundamental underlying concept behind Gödel numbering is that, for every relationship that can be defined between two sequences of symbols A and B of the formal system there is a corresponding number-theoretic relation between the Gödel numbers of the sequences A and B, such that given that number-theoretic relation, the information of original relationship between the two sequences A and B is uniquely retrievable.

The key point here is that since Sb[h, ^a/_k] is a purely number-theoretic function, then there is an expression in the formal system that precisely expresses that function, and given numerical values of h and k, it will give a resultant value that is the Gödel number of the corresponding substituted formula, and if k is the Gödel number of symbol sequence that is a number in the formal system, that is, in the format N(0), N(N(0)), N(N(N(0))), …, then that formula should be a well-formed formula of the system. (Footnote: N(0), N(N(0)), N(N(N(0))), … is the format that Gödel uses for the formal system in the 1934 lectures.)

But if we look a bit more closely we see that when Gödel defines γ(p, p) as Sb[p, ^a/_χ(p)], i.e:

γ(p, p) = Sb[p, ^a/_GN(p)]

which means that Gödel is substituting the term GN(p) for the variable k in Sb[h, ^a/_k]

But this means that the symbol sequence of the formal system that is to be substituted in the formal formula is a symbol sequence that corresponds, according to Gödel numbering, to the numerical value, not of GN(P), but of GN(GN(P)), where P is, as Gödel defines it, the formal system formula:

P = U(w) = Πv[¬B(v, S(w, w))]

If GN(GN(P)) is an expression of the meta-language, then the format of numbers in the meta-language must be the format of numbers of the formal system, otherwise the resultant value of the inner GN(P) would not be a symbol sequence of the formal system, and therefore would not be in the domain of the variable of the outer GN. But trying to circumvent the problem by setting the format in that way simply generates another problem, since in the meta-language, any number-theoretic function may be substituted for a variable whose domain is natural numbers. For example, for numbers in the format of N(0), N(N(0)), N(N(N(0))), … we have that: (Footnote: As already noted, N(0), N(N(0)), N(N(N(0))), … is the format that Gödel uses for the formal system in the 1934 lectures.)

N(N(N(N(0)))) + N(N(0)) = N(N(N(N(N(N(0))))))

and the two sides of the equality are always interchangeable - for any function h[n] and where the format of the domain of n is N(0), N(N(0)), N(N(N(0))), …, then, for example:

h[N(N(N(N(0)))) + N(N(0))] = h[N(N(N(N(N(N(0))))))].

This means that if the format of numbers in the meta-language were also to be the same format N(0), N(N(0)), N(N(N(0))), … as the formal system, then we would have, for example, that:

GN[N(N(N(N(0)))) + N(N(0))] = GN[N(N(N(N(N(N(0))))))],

but at the same time the definition of GN requires that:

GN[N(N(N(N(0)))) + N(N(0))] ≠ GN[N(N(N(N(N(N(0))))))],

since the intended unique correspondence of every Gödel number to a specific singular symbol sequence. Hence GN(GN(P)) cannot be a valid expression of the meta-language.

One might then wonder if the expression could be valid for a different level of language. Clearly, there cannot be an expression of the formal system that expresses the inner GN(P) since P is a formula of the system, and in general, the free variable of GN may be substituted by any symbol sequence of the formal system. See PDF The Impossibility of Representation of a Gödel Numbering Function by a Formula of the Formal System for a detailed analysis of this impossibility.

One might consider that perhaps there is a possibility that the outer GN of GN(GN(P)) could be an expression of the formal system while the inner GN of GN(GN(P)) could be an expression outside of the formal system, since the outer GN of GN(GN(P)) has only to deal with numerical values. But we then have the same problem as before, in that the format of numbers in the meta-language must be the format of numbers in the formal system, otherwise the resultant value of GN(P) would not be a symbol sequence of the formal system, and hence not a valid value for the outer GN.

It follows that there is no expression that is a logically valid implementation of Gödel’s notion of

γ(p, p) = Sb[p, ^a/_GN(p)]

and hence the argument that is based on that false premise is fundamentally flawed.

This should not be a surprise, since the fact that certain terms are referred to in an ambiguous manner should alert readers to the possibility of deflection or evasion. In these lectures, the function Z(n) that plays a key role in his original paper is conspicuous by its complete absence in the 1934 lectures. In the lectures Gödel does not define any term that is equivalent to this simply defined function Z(n) that is his relation 17 in his original paper, and simply glosses over what might be intended by his glib assertion that “χ(n) [is] the number of z_n”. Thus the flaw in Gödel’s lectures turns out to be the very same flaw that afflicts his original paper; it is merely dressed up in a different subterfuge; the details of the illogical assumption regarding the Z function can be seen at The Flaw in Gödel’s proof of his Incompleteness theorem.

The page Gödel’s Substitution Function gives a detailed analysis of Gödel’s incompleteness paper and how Gödel uses the false equivalence of his Z function and the Gödel numbering function within the Sb function to generate an apparent self-reference within the formal system.

A single arithmetical language?

Another way 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 a 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, and indeed in his original incompleteness proof - 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 Πv[¬B(v, S(z_p, z_p))] 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(z_p, z_p) = GN{ Πv[¬B(v, S(z_p, z_p))] }

and where S(z_p, z_p) 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. And, as indicated above, in the meta-language, the left side is simply a sequence of symbols with no numerical value, while the right side does have a numerical value in the meta-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 mathematical 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.