Logic and Language

Logic and Language

Copyright © James R Meyer 2012 - 2016 www.jamesrmeyer.com

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.

• Use

• The

• To skip the menu and move to the main content, press

• To get back to the top of the page anytime, press the

• For more information, click here: Accessibility Close this tip.

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

By the previous part, Part 3: Gödel’s special numbering system, we know that for any combination of formal language symbols there’s a matching number. We’re going to call that number the matching Gödel number. So for any formal sentence there’s a matching Gödel number. And if there’s a formal proof that proves that sentence, then there must also be a matching Gödel number for that proof.

From Part 2: Formal Language Systems, we know that there’s a definite relationship between that proof and the sentence that it proves. We also know that that relationship can be completely and precisely defined. It may be a very complex relationship, but it can always be completely defined, since it can be broken down into simple steps, even if there are a large number of those simple steps. Each of those simple steps is a simple relationship between formal language sentences.

In Gödel’s proof, the idea is that, for every single one of those simple steps, which is a relationship between formal sentences, you can define a corresponding relationship between the numbers that are the matching Gödel numbers for those formal sentences – so that for every single simple step of any formal proof there is a single matching number relationship.

And if all those single number relationships can be put together in some way, you end up with another single number relationship, which is the relationship between the Gödel number of a formal sentence and the Gödel number of the proof that proves that sentence.

Up to this point, we have been talking in very general terms. Now we need to get into it a bit deeper.

We now need to use various symbols to make what we are saying more manageable. Some people find it hard to understand symbols, but it is actually very simple. A symbol can be considered as a name for something, and we use these names so that our expressions do not become too cumbersome.

We can use symbols as names for some particular thing, which might be a number. If I say *‘Bagpuss and Rover’*, when *Bagpuss* and *Rover* are names for particular animals, that’s basically no different to saying ‘**6** and **11**’, where **6** and **11** are names for particular numbers. I could call *Bagpuss* *A*, and *Rover* *B*, and when I say *‘A and B’*, it’s the same as saying *‘Bagpuss and Rover’* – as long as it is defined somewhere what *A* and *B* stand for.

We can also have names for variables. If I say, *‘a cat and a dog’*, that’s basically no different to saying *‘a number x and a number ’y*. And that’s really no different to saying

The definition of what constitutes a step of a proof can be defined in general terms, so that basically I can say:

*‘P is the proof of the sentence S’*.

In that expression *P* and *S* are variables – variables for formal sentences.

Given any two formal sentences, I can substitute them for *P* and *S*, and I get a proposition that is either correct or incorrect.

Suppose *P* is **{ x + 3}**, and

That gives the expression, ‘**{ x + 3} is the proof of {2 + y}**’.

Now that proposition is obviously wrong, but it serves to illustrates the principle – we end up with a proposition.

Now, instead of referring to the Gödel numbering system by simply saying *‘the Gödel numbering system’* we give the Gödel numbering system a shorter name, which is GN. When we write GN(F) that just means that F is a free variable – the free variable of the Gödel numbering system. It’s a variable that can take the value of any formal symbol sentence.

The example formal sentence that we used earlier was **{ x + y}** and its matching Gödel number was

So, given the sentence **{ x + y}**, we can write the expression

That expression ** GN({x + y})** represents the Gödel number of the sentence

So we can say that:

** GN({x + y}) = 16486713209345820741011250000**.

The name ** GN(F)** is simply a general name that we’ve chosen for the Gödel number that matches to the formal sentence F. And in exactly the same way, we could put it another way simply by using different names. For example, we could say that

Now, as we saw earlier, we can have a relationship between a formal sentence and a formal proof. If we use the names P and S as names for variables for formal symbol sentences, then the relationship we’re interested in is the relationship:

*‘ P is the proof of the sentence S’*

Since there are matching Gödel numbers for P and S, then there’s also a matching relationship between the Gödel numbers for the formal proof P and the formal sentence S. And we can write down that relationship as:

‘** GN(P) is the G‑proof of GN(S)**’.

Now we have to be careful not to get confused. That does not mean that ** GN(P)** proves

G‑proof is only a *name* for a relationship. ** GN(P)** and

G‑proof is a particular number relationship that corresponds to the relationship between the formal sentences P and S. That means that ‘**GN****( P) is the G‑proof of GN(S)**’ is a relationship that corresponds to the expression

Because G‑proof is a general number relationship, we could substitute any number for the variables into the relationship. So we can have ‘**3178934… is the G‑proof of 43476234…**’

And this can be either correct or incorrect, since the matching formal sequence for **3178934***…* is either the proof of the formal sentence that matches to **43476234**…or it isn’t.

Now, if the formal language is fully definable, then the general relationship between a formal proof and the formal sentence that it proves is fully definable. Gödel actually wrote out a detailed definition of the G‑proof relationship that he used in his paper for a particular formal system. That definition is quite long and complex. But in principle, if the Gödel numbering system is a completely accurate representation of the formal language, then the Gödel number of that formal proof and the Gödel number of that formal sentence must also have a matching number relationship that can be completely defined. And that actually is the number relationship that we have called G‑proof. That means that the exact definitions that Gödel used to generate his G‑proof relationship aren’t really that important. Even if he’d made a mistake in his definitions, in principle the definitions can be precisely made, and there must be some number relationship that actually is this G‑proof.

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 …

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.

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

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.

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.

Flawed proofs of the Diagonal Lemma by Panu Raatikainen and Vann McGee have been added to the Diagonal Lemma web page.

16th Mar 2015 Bishops Dancing with Pixies?

23rd Feb 2015 Artificial Intelligence

31 Mar 2015 Cranks and Crackpots

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:

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

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

www.jamesrmeyer.com