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.

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

Church’s Paradox by Gödel

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

 

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:

 

(1)       d(F, x)  = F(x) if F is regular
    = 0 otherwise

 

Introduce now another regular function:

 

(2)       E(x)  = 0 if x ≠ 0
    = 1 if x = 0

 

We see immediately that

 

(3)       E(x)  ≠ x

 

Let H(x) be E[d(x,x)] which is regular. By (1), we have:

 

(4)       d(H,x)  = H(x)  = E[d(x,x)]

 

Substituting H for x, we get:

 

(5)       d(H,H)  = E(d(H,H))  , contradicting (3)

 

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 in the initial definition: d(F, x). 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). Neither is it a bound variable, since it is not subject to any quantifier. Since it is neither a free or 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.

 

 

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 …  

 

The Lighter Side

 

NEWS

Peter Smith’s ‘Proof’

It has come to my notice that, when asked about the demonstration of the flaw in his proof (see A Fundamental Flaw in an Incompleteness Proof by Peter Smith PDF), Smith refuses to engage in any logical discussion, and instead attempts to deflect attention away from any such discussion. If any other reader has tried to engage with Smith regarding my demonstration of the flaw, I would be interested to know what the outcome was.

 

 

There’s something about Gödel by Francesco Berto

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.

 

 

Easy Footnotes

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

 

 

O’Connor’s “computer checked” proof

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.

 

 

New page on Chaitin’s Constant

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.

 

Previous Blog Posts  

 

16th Mar 2015 Bishops Dancing with Pixies?

 

23rd Feb 2015 Artificial Intelligence

 

31 Mar 2015 Cranks and Crackpots

 

30 Apr 2015 The Chinese Room

 

Links  

 

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:

Gödel Links

 

– and a page relating specifically to the Gödel mind-machine debate:

Gödel, Minds, and Machines

 

Printer Friendly

 

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

 

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 - 2017  
www.jamesrmeyer.com