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.
 

A Simplified Explanation of Gödel’s proof - Part 4


 

 


 

Part 4: Creating a special number relationship

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 x and y – provided I’ve already said that x and y are variables for numbers.

 

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 S is {2 + y}.

 

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

 

So, given the sentence {x + y}, we can write the expression GN({x + y}).

 

That expression GN({x + y}) represents the Gödel number of the sentence {x + y}, which is the number 16486713209345820741011250000.

 

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 GN(Formal Sentence) is a name for the Gödel number that matches to the formal sentence that we represent by the variable Formal Sentence.

 

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(Pis the G‑proof of GN(S)’.

 

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

 

G‑proof is only a name for a relationship. GN(P) and GN(S) are only numbers, and a number can’t actually be a proof of another number. Although we used the name G‑proof for the relationship between the numbers GN(P) and GN(S), we could have used any name. We use the name G‑proof so that it is easier to remember what it stands for.

 

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

 

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 …  

 

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