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 5


 

 


 

Part 5: Getting a number relationship to correspond to the concept of substitution

First we give an example of substitution, using the sentence {x + 2}. Suppose we substitute the x by 8, and that gives us the sentence {8 + 2}. That is one particular example of substitution. What we want is a completely general expression, and we can call it Substitution.

 

This expression will take two values, one for the sentence to be substituted, the other for the number that we’re going to use for the substitution. That means it will have two free variables. Instead of just calling it Substitution, we can call it Substitution (Sentence, Number).

 

If we fill in particular values for Sentence, and Number, and if the Sentence has only one free variable, then we’ll get a specific substitution. For our example, if we have:

 

Substitution ({x + 2}, 8)

 

then the value of that is {8 + 2}.

 

You can see that Substitution is a function – it takes one value and gives another value. This is a simple substitution function , but as given it is not defined what happens if the sentence has, for example, two free variables, such as the sentence {x + y + 2}.

 

In fact, for our purpose, we only need to work with sentences that have just one free variable. But the Substitution function will still work with a sentence with two free variables. All we have to do is to define the Substitution function so that if there’s more than one free variable, it will only substitute one of the free variables – we might specify that it takes the free variable that’s the first in alphabetical order. That would mean that Substitution ({x + y + 2}, 8) will give the sentence {8 + y + 2}, since x comes before y in alphabetical order. So that if you needed to substitute both variables of a sentence with two free variables, you simply use the Substitution function twice.

 

 

Considerations of Language and Meta-language

You will come across the term ‘meta-language’ in discussions about proofs of incompleteness. This is because any such proof makes assertions in one language about a formal language. The language that talks about another language, and makes statements about another language is called a meta-language. The language that is talked about may be called a ‘sub-language’, or an ‘object-language’.

 

Because the meta-language has to be able to refer to every symbol of the sub-language, there will be a variable of the meta-language whose domain (the set of allowable values of the variable) is the set of all combinations of symbols of the sub-language (including ‘combinations’ that are actually just single symbols). For this reason, no variable of the sub-language can also be a variable in the meta-language, because then it would be both a variable and a member of the domain of the variable at the same time, which would be absurd.

 

The Substitution function can lead to some confusion. A function always gives a specific value. In the above, Substitution ({x + y + 2}, 8) gives the specific value as the sentence {8 + y + 2}. But from another point of view, {8 + y + 2} is not a particular value, since y is a free variable, which means that the entire expression {8 + y + 2} is not a particular value.

 

The point that must be grasped here is that y is only a variable in the formal language, and it’s not a variable in the language we’re talking in. The language of the Substitution function is a language that is a different language to the formal sentence that we’re applying the substitution to. The language of the Substitution function makes statements about the formal language, so the language of the Substitution function is the meta-language.

And we call the formal language (the language that is talked about) the sub-language. From the point of view of the meta-language and the Substitution function, the values that it takes for Sentence and Number are simply symbols of the sub-language to be manipulated. So as far as the meta-language is concerned, {8 + y + 2} is just a combination of symbols, and it sees y as just another symbol of the sub-language, not as one of its own variables.

 

It is important to remember that the Substitution function can take all different sorts of symbols as its values, not just number values. The value for Sentence can be any combination of symbols of the formal language.

 

Now, you should recall that for any combination of symbols of the formal language there is a matching Gödel number. That means for valid values of Sentence and Number in Substitution (Sentence, Number), there is a matching Gödel number for the value for Sentence and a matching Gödel number for the value for Number. If you can define the Substitution function you should also be able to define another function that takes the matching Gödel numbers, and which mirrors the Substitution function exactly.

 

I’m going to call that function the G‑Substitution function. This function takes two number values, and so it will have two variables. So we can also call it G‑Substitution (Number1, Number2).

 

I’ll demonstrate how it works by an example. I’m going to use the sentence {x + 2} again. As before, we look up the definition of the symbols and the matching numbers, and we get the sequence of numbers, 4679, and 12, which gives the Gödel number 24, 36, 57, 79, 1112, which is 115406992465420745187078750000 (here we take the number 9 to match to the symbol 2 of the formal system).

 

So GN({x + 2}) = 11540699246​5420745187078750000

 

That gives us our first number, which is Number1.

 

Now, we are going to substitute the x of {x + 2} by 8. Suppose that the matching code for 8 is 10, and that gives the value of GN(8) as 210. That gives GN(8) = 210 = 1024, and that is our second number – Number2.

 

When we substitute the x of {x + 2} by 8 we get {8 + 2}, and the matching sequence of numbers for {8 + 2} is 41079, and 12.

 

And the Gödel number for that is given as:

 

GN({8 + 2} = 24  · 310 · 57 · 79 · 1112 = 93479663896990​80360153378750000.

 

Suppose we have Substitution ({x + 2}, 8). That gives the result of {8 + 2}.

 

The matching number function, which is G‑Substitution will take the matching Gödel number values. The matching Gödel numbers are GN({x + 2}) = 11540699246​5420745187078750000, and

 

GN(8) = 1024.

 

We put these values into the function G‑Substitution for Number1 and Number2. That can be written as G‑Substitution (115406992​465420745187078750000, 1024).

 

If it’s all done correctly, and if I had defined the G‑Substitution function properly, then you could give me those two numbers, and I could work out the value of G‑Substitution (11540699246​5420745187078750000, 1024)

 

The answer has to be some number, and I could find that answer without working out what the matching formal language equivalents of the numbers are. In fact, I could do it without knowing anything at all about the formal language at all, since all I’m doing is manipulating numbers, and coming up with the correct answer of 934796638969908​0360153378750000.

 

Then, and only then, if I wanted to, I could decode the number 934796638969908​0360153378750000, and work out that the matching formal sentence was {8 + 2}. So purely by working with numbers, you can get the desired result.

 

You might wonder, since G‑Substitution is a number relationship, what happens if you put in a number value that isn’t the Gödel number of any formal sentence. If you put in a number which isn’t a Gödel number for a sentence, then the G‑Substitution function simply gives the value that you put in for Number1. The same would happen if Number1 was the Gödel number of a nonsense sentence – a sentence that only uses the alphabet of the formal sentence, but which isn’t put together according to the rules – in English we’d call it a nonsensical sentence.

 

And the same would apply if you put in a number value for Number2 that isn’t the Gödel number of a number – the G‑Substitution function would simply give the value that you put in for Number1. And again, that’s the way it should be, since you can’t substitute variables of a formal sentence by anything other than a number value.

 

As was the case for Part 4: Creating a special number relationship, the exact definitions that Gödel used for his G‑substitution function aren’t really that important. Because it wouldn’t matter if he’d made some error in his definitions, in principle there must be a precise definition of substitution of a variable of a formal sentence by a number value. And that means that there must also be a precise definition that gives the matching transformation of the matching Gödel numbers of the sentence and the number – and which gives the Gödel number for the formal sentence that you’d get if you substituted the free variable of the sentence by the number. So there has to be some number relationship that actually is the G‑Substitution 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

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.

 

 

Updated: Diagonal Lemma

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

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