Church’s Paradox by Gödel

Page last updated 07 Oct 2021

In the book “A Logical Journey”, by Hao Wang, (Footnote: Hao Wang. A Logical Journey: From Gödel to Philosophy, MIT Press, 1997 ISBN: 9780262231893 Wang, A Logical Journey: Details.) which is an account by Wang of conversations with Gödel, Gödel talks about a paradox based on the notion of something not applying to itself. Gödel calls it Church’s paradox because it can be derived in Church’s lambda system (a system which as Church first devised it, is inconsistent). Gödel remarks that it is striking that this paradox is not well known because, Gödel claims, it proves that several paradoxes have no simple solution.

Note: This paradox should not be confused with another paradox that is also sometimes called Church’s Paradox, a paradox concerning identity and equivalence. (Footnote: Church’s other paradox: Suppose that there are two names, A and B, for the same thing. And suppose that Sam encounters the names A and B without knowing that they are both names for the same thing. But two things are identical only if they are identical in every respect - but they are not identical in Sam’s mind - hence we have a paradox. See also the page Natural language and reality which discusses this in detail.)

As Gödel states it, the paradox is as follows:

A function is said to be regular if it can be applied to every entity [which may be an object or a function (a concept)]. Consider now the following regular function of two arguments:

This is the contradiction that Gödel considers paradoxical. However, this ‘paradox’ only arises because Gödel’s construction involves a confusion of language. Contrary to Gödel’s claim, there is a very simple solution, which is to always maintain the distinction between levels of language. Gödel’s construction is in what is commonly called ‘higher-order logic’, where there are variables for functions - whereas, in first-order logic, variables only apply for individual entities - for example, in first-order arithmetic, you can have expressions such as 3x + 6y = 7z, where x, y and z are variables for numbers.

Many people, the most well-known being Quine, (Footnote: See, for example, Willard Quine. Philosophy of Logic. Harvard University Press, 2nd edition, 1986. ISBN‑10: 0674665635 Quine, Philosophy of Logic: Details.) have argued that ‘higher-order logic’ is not entirely logical, or that it is a ‘set theory in sheep’s clothing’. And many others, such as Boolos (Footnote: See, for example, George Boolos. Logic, Logic, and Logic. Harvard University Press, 1999. ISBN‑13: 978‑0674537675 Boolos, Logic, Logic, and Logic: Details.) and Shapiro, (Footnote: See, for example, Stewart Shapiro. Foundations Without Foundationalism: A Case for Second-Order Logic. Oxford University Press, 1991. ISBN‑10: 0198250290 Shapiro, Foundations Without Foundationalism: Details.) have argued against Quine. However, these arguments all seem to miss the crucial points, which all revolve around levels of language.

Returning to the paradox - consider the function d(F, x) in the initial definition. In this function, F may be a function, and if that is the case, then it must have at least one free variable. But this variable of the function F, regardless of whatever symbol may be used for it, is not free in the expression d(F, x). This can be seen by the following: observe that the domain of a variable is a domain of objects; the substitution of a variable by a member of its domain means that the variable has been substituted by an object, and not by a variable quantity. If the substituted entity itself has a variable which itself is to be free in the substituted expression, then this is not in fact a true substitution of the original variable, it is a case of swapping one variable quantity for the original, akin to a change of the variable name. This should not change the overall expression nor its value subsequent to a valid substitution. (Footnote: Although one could change a variable to a new one that has a restricted domain that is a subset of the original variable’s domain.)

It is also the case that in the function d(F, x), the variable of the function F is not a bound variable, since it is not subject to any quantifier. Since it is neither a free nor a bound variable in the expression d(F, x), the free variable of F is not a variable within the expression d(F, x) - it is an object within that expression, and that means that the function d is a function in a language that is a meta-language to the language of the function F, which is a sub-language to the language of the expression d(F, x).

Now, what about the variable x in the function d(F, x)? According to Gödel’s definition of regular, x may be anything, so it may be a function - which means that the variable x is also a variable of the meta-language.

Now, bearing the above in mind, we examine Gödel’s argument where he states:

Let H(x) be E[d(x, x)], so d(H, x) = H(x) = E[d(x, x)], and substitute H for x.

But, as was the case for F, the free variable of H (and E) cannot be free in the function d(H, x), and so the function H (and E) must be a function of a sub-language, not of the meta-language. And that means that we cannot substitute the free variable of E by d(x, x), which is a function of the meta-language - that would be substituting a variable of a sub-language by an expression of a meta-language, which would be an absurdity.

Gödel’s assertions hopelessly confuse the different levels of language, and so, it isn’t any wonder that he ends up with an absurd contradiction. It’s a contradiction that is the inevitable consequence of confusing meta-language and sub-language. And quite possibly, it’s no coincidence that the flaw in Gödel’s proof of incompleteness exhibits this same confusion of meta-language and sub-language.

Gödel, along with most of today’s logicians, seem to greet such contradictions with welcoming arms, and one might think that the derivation of a contradiction within a system of logic is to be celebrated.

Note: the paradox could also be prevented by a typed system which assigns different levels to functions so that the circularity of the paradox is prevented.

Other paradoxes