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 3


 

 


 

Part 3: Gödel’s special numbering system

Gödel’s numbering system is a way of representing any sentence of the formal language as a number. That means that every sentence of the formal language can be represented as a number. And not only sentences. Every proof sequence of sentences of the formal language can also be represented as a number (a proof sequence is a list of all the sentences that go together to make a proof of some sentence).

 

The Gödel numbering system is a one-to-one function. That simply means that it takes in one value, which is some combination of symbols of the formal language, and puts out another value, which is a number. Every combination of symbols is matched to a unique number, so that no two combinations can have the same number, and no two numbers can match to the same combination.

 

The way that it works is by a two-step process.

 

The first step is to take every symbol of the formal language and you define that a specific number is to be associated to every symbol, so that no two formal symbols are associated with the same number.

 

For example, suppose we take the sentence {x + y}, and we match numbers to the symbols.

 

We might define:

  • the opening bracket symbol ‘{’ to match to 4,
  • the symbol x to match to 6,
  • the symbol ‘+’ to 7,
  • the symbol y to 8,
  • and the closing bracket symbol ‘}’ to 12.

 

That gives you the sequence of numbers, 4, 6, 7, 8, and 12. But 4, 6, 7, 8, 12 is only a sequence of numbers and isn’t actually a number itself, so there’s a bit more to be done. We need to be able to make this sequence into a number, and we’ve to do that without losing any information, so that you can always convert the number back into the formal sentence.

 

It isn’t sufficient to take the numbers and put them together to make the 467812, because that method can lose information. You can’t say whether the original sequence was 46, 7, 81, 2, or 4, 67, 8, 1, 2 or 4, 6, 78, 12 or some other sequence.

 

To be sure that you can always get back the original information that you started with, Gödel devised a way of converting these sequences of numbers into numbers in a way that retains all the original information. The reverse process can be applied in order to retrieve the original information.

 

Gödel’s encoding system uses prime numbers (prime numbers are numbers that can only be divided by themselves and by one without leaving a remainder).

 

Gödel’s system takes the prime numbers in order, so that for example, to encode a sequence of five numbers, we start off with the first five prime numbers – which are 2, 3, 5, 7 and 11.

 

We now encode our sample sequence, which is 4, 6, 7, 8, 12 as follows:

 

Multiply the first prime, which is 2, by itself 4 times. We use 4 times because 4 is the first number in our sequence. We call this raising 2 to the power of 4 and we denote this as 24.

 

Then for the next prime number, which is 3, we multiply it by itself by 6 times, 6 being by the next number in our sequence. This is called raising 3 to the power of 6, and we denote this by 36.

 

Do the same with the rest of the numbers. This give us

 

243657781112,

 

where each bit works out as

 

16729781255764801 and 3138428376721.

 

Then we multiply these all together. We can denote that by 24 · 36 · 57 · 78 · 1112 and that gives 16486713209345820741011250000. That is the matching Gödel number for the sentence {x + y}.

 

Given a Gödel number, you can always reverse the process. So, given the number 16486713209345820741011250000, first divide by the first prime number, which is 2. Keep dividing by 2 until you don’t get an even division and you end up with a remainder, as follows:

 

16486713209345820741011250000 divided by 2 gives:

8243356604672910370505625000

 

8243356604672910370505625000 divided by 2 gives:

4121678302336455185252812500

 

4121678302336455185252812500 divided by 2 gives:

2060839151168227592626406250

 

2060839151168227592626406250 divided by 2 gives:

1030419575584113796313203125

 

1030419575584113796313203125 divided by 2 gives:

515209787792056898156601562, with remainder 1.

 

This gives the information about how many 2s were multiplied by each other originally, which was 4.

 

We repeat the process with the next prime number, until we get no remainder at all. And this will give you the information that originally we multiplied 2 by itself 4 times, 3 by itself 6 times, 5 by itself 7 times, 7 by itself 8 times, and 11 by itself 12 times. We can write that as 24 · 36 · 57 · 78 · 1112. That means our original number sequence was 467812.

 

And that means that, given the definition of which symbol matches to which number, that we can tell that we started with {x + y}. This means that this method of encoding gives a unique number that retains all the original information of any combination of symbols of the formal language.

 

That’s all there is to Gödel’s method of encoding the sentences of the formal language. For the full details of the actual Gödel numbering function that Gödel used, please see Gödel proof guide - the Gödel numbering function.

 


 

 


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

Lebesgue Measure

There is now a new page on Lebesgue measure theory and how it is contradictory.

 

 

Illogical Assumptions

There is now a new page Halbach and Zhang’s Yablo without Gödel which demonstrates the illogical assumptions used by Halbach and Zhang.

 

 

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.

 

 

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  

 

13 May 2015 Good Math, Bad Math?

 

30 Apr 2015 The Chinese Room

 

31 Mar 2015 Cranks and Crackpots

 

16th Mar 2015 Bishops Dancing with Pixies?

 

23rd Feb 2015 Artificial Intelligence

 

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