Errors in incompleteness proofs by Kleene and Rogers

Page last updated 14 Feb 2023

This page demonstrates an error common to S. C. Kleene’s 1952 book Introduction to Metamathematics  (Footnote: Stephen Cole Kleene: “Introduction to metamathematics”, North-Holland, 1952.) and Hartley Rogers’s 1987 book “Theory of Recursive Functions and Effective Computability”  (Footnote: Hartley Rogers Jr, “Theory of recursive functions and effective computability”. MIT press, 1987.) and which renders invalid the subsequent arguments in the books that follow on from that error and which include incompleteness results. It can be noted that much of Rogers’s material is taken almost directly from Kleene’s book, so that the overall argument is broadly similar in both.

The error in brief

Rogers and Kleene both make a classic mathematical blunder, in that they simply assume that since they are unable to find a disproof of an assertion, then they conclude that that assertion must be “true” (i.e: provably correct in the mathematical system that the assertion resides in). The assumption is that there can be a function that is an enumeration of all partial recursive functions of any given mathematical system, and where that function is necessarily expressible in that system.

The error in Kleene’s proof

First we will refer to Kleene’s Chapter XXII: Partial Recursive Functions, Section 65, in his “proof ” of his Theorem XXII; you can see the relevant extract from Kleene’s text below in Appendix: Extracts from Kleene’s text.

Stephen Cole Kleene

Kleene states that while Cantor’s diagonal argument proves that there cannot be an enumeration function for functions that are defined for every instance of the free variables, he notes that the diagonal argument fails to prove that the same applies to partial functions - functions that are only defined for a certain proper subset of the domains of the free variables. Kleene’s conclusion at that point and in the following text is that, on the basis that since he cannot find a diagonal method that might result in a contradiction, then there cannot be any possibility that an assumption of an enumeration of partial functions could result in a contradiction.

This, of course, is mathematical anathema, one cannot simply assume something must be the case simply because one has been unable to prove the converse. This renders untenable any result that depends on Kleene’s unproven assumption. Of course, of itself the assumption does not indicate that the result is necessarily wrong; we will consider this point later on this page.

We can also note that in the same “proof ”, Kleene blithely introduces Gödel numbers as though they are referenceable within the system of recursive functions, simply stating expressions such as Φ (q, q, x₂, …, x_n ) where he states that q is a Gödel number, which implies that the recursive functions of the system in question can express Φ (GN(Q), GN(Q), x₂, …, x_n ), where GN() is the Gödel numbering function, and Q is the sequence of symbols of the system in question that corresponds to the number q. Of course the system cannot reference the Gödel numbering function, since that numbering function is in a meta-language to the system. (Footnote: See PDF The Impossibility of Representation of a Gödel Numbering Function by a Formula of the Formal System.)

The error in Rogers’s proof

Hartley Rogers

As already noted, much of Rogers’s material is an uncritical rehash of Kleene’s methods, albeit in a somewhat different order, so it is not surprising that Rogers’s version is broadly similar. You can see relevant extracts from Rogers’s text below in Appendix: Extracts from Rogers’s text.

(A) In Rogers’s Section 1.4 Diagonalization, he refers to total recursive functions, and says that there cannot be an enumeration of such functions, since if there were, call it g (n, x), where n defines the enumeration, then we could define a new total recursive function h (n), where for any given n, the value of h (n) = g (n, x + 1). By definition, this function must be different to every function in the enumeration. This is a contradiction, hence the assumption of enumeration must be false.

(B) In the next Section 1.5 Formal Characterization, Rogers says: “We can avoid the diagonalization difficulty by allowing sets of instructions for non-total partial functions as well as for total functions”, and later “With a formal characterization for a class of partial functions we are not immediately subject to the diagonalization difficulty…” He then proceeds on the basis that since he cannot find a diagonal method that might result in a contradiction, then it cannot be the case that an assumption of an enumeration of the partial functions could produce a contradiction.

As in Kleene’s case, this is mathematical anarchy, one cannot simply assume something must be the case simply because one has been unable to prove the converse. This renders untenable anything that depends on Rogers’s unproven assumption, although as noted in the case of Kleene, the assumption does not of itself mean that the result is necessarily wrong. We consider this in the next section.

Demonstration of the error

It is not difficult to demonstrate that the Kleene/Rogers assumption is in fact erroneous, i.e: the negation of the assumption is provable, as follows:

First note that in the following, for convenience, we will refer to a given mathematical system in which recursive functions are defined as the system S.

Before proceeding further, considering (A) above, in fact what Rogers has proved in that section is only that there cannot be an enumeration function g of total recursive functions where it must be possible to define another function h in terms of g. But that states nothing as to whether there can be an enumeration function in a higher level language, a meta-language to the system S, from which a function such as h cannot be defined within the system S.

At this point, we note that there is a non-diagonal method of proving that there cannot be an enumeration function of total recursive functions within the system S. We now demonstrate this below as it serves to clarify the overall context.

Enumeration of functions: The general case

In the following, we will deal first with recursive functions in general, then we consider the specific case of partial recursive functions that Kleene and Rogers specifically refer to.

First assume that there can be an enumeration function f (n) within the system S, which has at least one free variable n (the enumeration variable) and which enumerates every function of S. A definition of the function consists of symbols that can be divided into two groups:

• symbols for numbers (which we will call digit symbols, for example 0,1,2,3,4,5,6,7,8,9)
  and
• other symbols (non-digit symbols).

The total information content of an expression thus depends on these two types of symbols. The digit symbols contain object information - information about the objects of the system, in this case numbers. The non-digit symbols contain syntactical information, which deals with information regarding relationships between the objects of the expression.

Now, according to the definition of f (n), whenever the enumeration variable n of f (n) is substituted by some specific number (which consists only of digit symbols), the resultant expression must always have the same finite quantity of non-digit symbols, regardless of whatever number is substituted (since only digit symbols are added). In addition the relative positions of the non-digit symbols are unchanged and hence the syntax of the resultant expression is always identical, regardless of whatever number is substituted. The only difference between any two such resultant expressions is the digit symbols.

This means that the assumption of the existence of the enumeration function f (n) also entails the assumption that every function of S can be expressed by a finite quantity of non-digit symbols in a fixed order, which implies that there is a finite limit on the amount of syntactical information required to define any function of the system. This, of course is absurd, hence the purported function f (n) cannot possibly reference nor enumerate all functions.

While the above applies for the case of all functions, in general for any specific type of function (such as recursive or partial recursive) there is always no upper limit on the amount of syntactical information required to define a function of that type, hence the above applies in general to any type of function. (Footnote: Obviously, this does not necessarily apply to a type of function that includes only finitely many functions.)

Enumeration functions in a meta-language

That leaves the question of an enumeration function that is defined outside of the system S. Clearly, a dictionary style lexicographical enumeration function L(n) can be defined simply by creating a dictionary style list of all sequences of the symbols of the alphabet of the system S. (Footnote: All permutations of the symbols of any given alphabet can be put in a dictionary style list, by first deciding an alphabetical order of the symbols, then the first part of the list will be that list of single symbols, then taking all permutations of two symbols in an alphabetical order, then taking all permutations of three symbols in alphabetical order, and continue the list by taking all permutations of four symbols, and so on. The permutations may contain the same symbol repeated several times. This is called a lexicographical order.)

We can observe that any such lexicographical enumeration function L(n) requires at least 2 variables that cannot belong to the system S; one is a variable whose domain is all symbols of the given alphabet, and the other is a variable whose domain is all sequences of symbols of that alphabet. Neither of these variables can be a symbol or a sequence of symbols of the alphabet of the system S, since then such symbols/sequences of symbols would be at the same time both variables and non-variables, which is logically absurd. (Footnote: They must be non-variables since they must be members of the domain of a variable. Note that replacing a variable by another variable is not substitution of the variable by a member of its domain, that is simply a change of variable.) This means that the system S cannot reference that lexicographical enumeration function L(n), hence no contradiction arises, even though the function L(n) can be considered to be an enumeration function - but it is an enumeration function outside of the system S. As such, a lexicographical enumeration function such as L(n) is not available to be used in proofs within the system S.

This is why all references to enumeration functions in general should make it abundantly clear as to whether the enumeration function being talked about is within or outside of the system. The failure to do so explains many of the conundrums, contradictions and paradoxes that are prevalent in current mathematics.

Information content is language dependent

Note that the matter of the quantity of non-digit symbols is not relevant when the enumeration function is defined outside of the system S. The function L(n) is an expression in the syntax of the meta-language, not of the system S. And a meta-language to S, as well as referencing the symbols of the system S (only as objects, never as variables), has its own symbols, and which can be configured as a function L(n), and which is an instruction for the creation of sequences of symbols of S.

The crucial point is that sequences of symbols, of themselves, have no specific information content - any information content that can be extracted from a sequence of symbols can only be done by reference to the rules and grammar of a specific system. Indeed, the same sequence of symbols can have a particular information content within one language system, and a completely different information content within a different language system.

Outside of the system S, the information required to define the lexicographical sequences of signals of S is finite, since the object information is simply the finite set of symbols of the system S, while the same syntactical information applies for the definition of the entire lexicographical enumeration, and hence also for each individual instance. No information is required other than the order in which the symbols occur in the sequence, and there is no correlation whatsoever of that information within the meta-language to the information content of these sequences as seen within the system S, where the syntactical information content of the sequences depends completely on the axioms and rules of inference of that system S.

From the general case to a specific case

The above applies in general to functions of any given type, and hence it applies also to partial recursive functions. Hence Kleene’s/Rogers’s naive assumption that because the author cannot conceive of any reason why there should not be such an enumeration function, then there must be one, is simply wrong. Of course, as shown above, there can be an enumeration outside of the system S of all sequences of the symbols of the system S, but such an enumeration is inaccessible to the system S, and cannot be used in proofs within the system S.

It can also be noted that the same principles above can be applied to certain other sets of mathematical entities, for example to show that there can be no enumeration of real numbers within the language system in which those numbers are defined, see Non-Diagonal Proofs: Enumerations in different language systems.

Sloppy failures to observe delineation of languages

I would also note that while the title of Kleene’s book refers to meta-mathematics, Kleene’s work both in the book and elsewhere demonstrates a very cavalier attitude to the fundamental aspect of meta-mathematics, which is that one must always maintain a clear distinction between different levels of language. Instead Kleene seems to be more interested in obtaining his desired goals by whatever means necessary, which can include the introduction of untenable assumptions whenever he fails to find a proof for a certain step. In fact his book might have been more suitably entitled as “Introduction to ignoring the fundamental characteristic of meta-mathematics”, since it demonstrates no deep insight into the principles involved in meta-mathematics. (Footnote: Here is an extract which sums up Kleene’s nonchalant attitude to rigor (my emphasis):
“The meta-theory belongs to intuitive and informal mathematics (unless the meta-theory is itself formalized from a meta-meta-theory, which here we leave out of account). The meta-theory will be expressed in ordinary language, with mathematical symbols, such as metamathematical variables, introduced according to need. The assertions of the meta-theory must be understood. The deductions must carry conviction. They must proceed by intuitive inferences, and not, as the deductions in the formal theory, by applications of stated rules… We shall understand this to mean that the ultimate appeal to justify a metamathematical inference must be to the meaning and evidence rather than to any set of conventional rules. It will not prevent us in practice from systematizing our metamathematical results in theorems or rules, which can then be applied quasi-formally to abbreviate the intuitive reasoning. This is a familiar procedure in informal mathematics…”
From Chapter 3, A Critique of Mathematical Reasoning, in the book “Introduction to metamathematics” by Stephen Cole Kleene, North-Holland, 1952.) For other examples of the insertions of untenable assumptions by Kleene, see my paper PDF A Fundamental Flaw in Incompleteness Proofs by S. C. Kleene.

The irony is that a full consideration of the fundamental principles of meta-mathematics - which is the referencing of a sub-language by a meta-language - provides a very simple method, as shown above, of determining whether certain enumerations of entities of that sub-language are possible. See also the page A brief history of meta-mathematics.

Conclusion

This error in Kleene’s/Rogers’s material is just one further instance of a type of flawed argument that is often used to generate a particular type of erroneous result, i.e: a “proof ” of incompleteness, where the desire to achieve the result appears to take precedence over any logical considerations. On my website I have detailed a huge number of similar cases, see the page Errors in Incompleteness Proofs.

Appendix: Extracts from Kleene’s text

From Kleene’s Chapter XXII: Partial Recursive Functions, Section 65: (Footnote: The term “≃” is defined as follows in Kleene’s text: We now introduce “ψ (x₁, …, x_n ) ≃ χ (x₁, …, x_n )” to express, for particular x₁, …, x_n , that if either of ψ (x₁, …, x_n ) and χ (x₁, …, x_n ) is defined, so is the other and the values are the same (and hence if either of ψ (x₁, …, x_n ) and χ (x₁, …, x_n ) is undefined,, so is the other). The difference in the meaning of (i) “ψ (x₁, …, x_n ) = χ (x₁, …, x_n )” and (ii) “ψ (x₁, …, x_n ) ≃ χ (x₁, …, x_n )” comes when one of ψ (x₁, …, x_n ) and χ (x₁, …, x_n ) is undefined. Then (i) is undefined, while (ii) is true or false according as the other is or is not undefined.)

Theorem XXII: The function Φ (z, x₁, …, x_n ) is partial recursive, and Φ (z, x₁, …, x_n ) for z = 0, 1, 2, … is an enumeration (with repetitions) of the partial recursive functions of n variables. Similarly, for completely defined Ψ, Φ_n^Ψ is partial recursive in Ψ and enumerates (with repetitions) the functions of n variables which are partial recursive in Ψ. (Enumeration theorem for partial recursive functions.)

 

This theorem is only possible because a partial recursive function may be undefined for some sets of arguments. Let us recapitulate the usual Cantor diagonal argument for completely defined functions. Suppose C is a class of such functions of various numbers of variables; and that Φ (z, x₁, …, x_n ) enumerates (with repetitions) the n‑variable functions of C (for some fixed n ≠ 1). Then Φ (x₁, x₁, x₂, …, x_n ) + 1 cannot ∈ C, because otherwise we would have

Φ (q, q, x₂, …, x_n ) + 1 = Φ (q, q, x₂, …, x_n )

for some number q, which is impossible. If C is closed under the operation of passing from a function φ (z, x₁, …, x_n ) to φ (x₁, x₁, x₂, …, x_n ) + 1 , then Φ (z, x₁, …, x_n ) cannot ∈ C. In particular, this shows that there is no corresponding enumeration theorem for the general recursive functions. But with partial functions, we would have instead

Φ (q…, q, x₂, , x_n ) + 1 ≃ Φ (q, q, x₂, …, x_n )

which is not impossible, but simply means that Φ (q, q, x₂, …, x_n) must be undefined. In particular, we thus prove that the partial recursive function Φ (z, x₁, …, x_n ) is undefined, when z = x₁ = q where q is any Gödel number of Φ (q, q, x₂, …, x_n ) + 1.

Footnotes: