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 1


 

 


 

Part 1: Basic Logical Concepts

Gödel’s proof, like any proof, is based on fundamental logical concepts. We are not disputing the underlying concepts of logic used in the proof – but does Gödel apply those fundamental logical concepts correctly? To answer that question, we need to have a clear idea of the basic logical concepts used in the proof. In order to be able to follow what is going on, you need to be familiar with some basic concepts.

 

The fundamental concepts involved in Gödel’s proof are

  1. numbers and variables
  2. propositions and functions
  3. relationships between numbers, and relationships between variables for numbers (Gödel calls these number-theoretic relations)
  4. formal languages and formal systems

 

First of all we look at the concepts of variables and propositions.

 

Variables

A variable is often defined in terms such as

“A variable is a general term, not a fixed value.”

“Variables occur in natural language as well as in mathematical language.”

 

For example:

‘The dog Freddy chased a cat’

 

in that sentence ‘a cat’ is a variable. It doesn’t tell you what particular cat it is; only that it is some cat. So it might be the case that Freddy was chasing a particular cat called BagPuss, or it could be the case that maybe it was some other cat.

 

So variables represent something in general, rather than one specific thing.

 

Free and Bound Variables and Substitution

A variable can be either what is called a free variable, or a bound variable. We first of all explain this in terms of natural language. If we take the sentence:

 

‘Persons who were born in Aberdeen have red hair’

 

then, as it stands, the sentence is ambiguous and it is not clear whether I mean that every single person who was born in Aberdeen has red hair, or whether I mean that some people who were born in Aberdeen have red hair. Whereas in the sentences

 

‘Every person who was born in Aberdeen has red hair’ and

‘At least one person who was born in Aberdeen has red hair’,

 

there is no ambiguity. It is quite clear what is meant (here we are not concerned whether the sentences are factually correct). And that is because I used the term ‘Every’ or ‘At least’. The terms ‘Every’ or ‘At least’ are terms that apply to a variable. In logic ‘Every’ and ‘At least’ are called variable quantifiers.

 

So if you want to make an unambiguous statement that makes a clear assertion, if there’s a variable in your statement you must apply a variable quantifier to it. Variable quantifiers only apply to variables – they cannot apply to a specific value.

 

When we replace a variable in a sentence by one of the specific values that the variable stands for, we call that substitution. Suppose that I take the sentence:

 

‘Every person who was born in Aberdeen has red hair’.

 

and I replace the word ‘person’, which is a variable, by a word which isn’t a variable. We suppose there’s a particular person called ‘Ashmir Jellyfingers’, and there’s no other person with that name. So we get the sentence

 

‘Every Ashmir Jellyfingers who was born in Aberdeen has red hair’

 

But that is not a valid statement, since although Ashmir Jellyfingers is a particular person, in the above sentence, Ashmir Jellyfingers is being treated as a variable. So we can have two sentences, ‘Every person who was born in Aberdeen has red hair’, and ‘Every Ashmir Jellyfingers who was born in Aberdeen has red hair’, but only one of those is a logically meaningful sentence.

 

In mathematical terms, substitution only refers to a variable being replaced by some particular value. When a variable is bound that means we’re not allowed to substitute that variable – or if we do try to substitute it, we end up with a meaningless sentence. The terms ‘Every’ or ‘At least’ are terms that make a variable a bound variable.

 

Now, when there is a sentence with a bound variable such as ‘Every person who was born in Aberdeen has red hair’, you can take away the quantifier ‘Every’ and then you can substitute the variable ‘person’ to get the sentence, ‘Ashmir Jellyfingers who was born in Aberdeen has red hair’. And that is a meaningful sentence.

 

A free variable is a variable that isn’t controlled by a quantifier. That means that in the sentence

 

‘Person who was born in Aberdeen has red hair’,

 

‘person’ is a free variable in that sentence. That sentence is the English equivalent of a mathematical sentence with a free variable. If you take the sentence,

 

‘Person who was born in Aberdeen has red hair’,

 

and if you substitute the variable ‘person’ by some specific value, you do get a normal English sentence, such as

 

‘Ashmir Jellyfingers who was born in Aberdeen has red hair’.

 

While the sentence ‘Ashmir Jellyfingers who was born in Aberdeen has red hair’ can be said to be true or false, a sentence with a free variable cannot be said to be either true or false. Although we have to be careful with what we mean by true or false. For the sentence

 

‘Person who was born in Aberdeen has red hair’

 

although we say that it is neither true nor false, what we mean is that, regardless of how much information we have about people, and Aberdeen and red hair, we can never have information that will enable us to prove the sentence, or the negation of the sentence which is, ‘Person who was born in Aberdeen has not red hair’.

 

Negation

We assume that the reader knows what we mean by negation. Although everyone has learnt the concept of negation, a clear definition of negation is rather elusive.

 

Propositions

A proposition is a sentence that makes some sort of assertion or claim. A proposition cannot have any free variables; any variable in a proposition must be controlled by a quantifier. A sentence in which there is a variable which isn’t controlled by a quantifier cannot be a proposition. See also propositions on the formal language page.

 

Functions

It might seem from the above, that if you have a sentence with a free variable, and you replace the free variable by some specific value, then the new sentence must be a proposition, since it’s got no free variables. But simply substituting a free variable in a sentence with some specific value doesn’t necessarily mean that the new sentence is a proposition.

 

The easiest way to explain what a function is, is by an example. Consider the sentence

 

x = 2’.

 

That has a free variable, which is x. When I replace the free variable x by some number, say three, I get ‘3 = 2’. That is a proposition, and which can be said to be false – as long as the logic is consistent, it cannot be proved that 3 = 2, but the negation can be proved, that is

 

3 ≠ 2

 

can be proved. Now consider the sentence

 

x + 2’.

 

When the x is substituted by the number three, we have the sentence

 

3 + 2’.

 

That is not a sentence that makes an assertion. It can be said that it cannot be true or false, or it can be said the sentence ‘3 + 2’ cannot be proved (and neither can ‘not(3 + 2)’).

 

A function is a sentence in which there are free variables, and when the free variables are substituted by specific values, we get a sentence that is not a proposition, but a sentence that represents some specific value.

 

There are two types of functions. The only type that we need to consider here is what is called a one-to-one function. With any function, when the free variable is replaced by a specific value, we get a sentence that represents some specific value. With a one-to-one function you always get a sentence that represents a different value for every value you put in for the free variable. For example consider the one-to-one function

 

x + 1

 

No matter what value is chosen for x, the result will always be a different value. For example, if we substitute x by 3, I end up with ‘3 + 1’ , which has the value 4. If we substitute x by 72, we get 73. It is obvious that we always get a different value.

 

The range of a function is the set of all possible values that the function can evaluate as, given any of the possible values of its free variables.

 

A further point about bound variables

If a variable appears more than once in a proposition, then it must be bound everywhere it appears. Otherwise it can’t be a meaningful proposition. For example, the sentence:

 

‘Every person who was born in Aberdeen has red hair and person who was born in Aberdeen has blue eyes’,

 

is not a valid meaningful sentence.

 

But the sentence:

 

‘Every person who was born in Aberdeen has red hair and every person who was born in Aberdeen has blue eyes’,

 

that is a meaningful sentence, even if it’s not true. We could also say it in another way, for example,

 

‘For every person who was born in Aberdeen, that person has red hair and blue eyes’.

 

And for a sentence like:

 

‘Person who was born in Aberdeen has red hair and person who was born in Aberdeen has blue eyes’,

 

this sentence has two occurrences of the variable ‘person’, and which are both there as free variables. In this case the sentence isn’t a proposition.

 

And another point about variables

Conventionally, when we say that a sentence has one free variable, that doesn’t mean that the variable can only occur once in the sentence. It can appear several times in the sentence. And when we talk about substituting a free variable of some sentence, that means we substitute the variable everywhere that it appears in that sentence. For a simple example, we take

 

x + x + 1

 

We say that this is a sentence with just one free variable, which is x, even though x occurs twice in the sentence. When we talk about substituting the variable x, we mean that we substitute both occurrences of x in the sentence. So if we substitute the free variable x in ‘x + x + 1’ by 3, we get the sentence

 

3 + 3 + 1

 


 

 


Diverse opinions and criticisms are welcome, but messages that are frivolous, irrelevant or devoid of logical basis will be blocked. 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 - any address will do, it does not require verification. Your e-mail will only be used to notify you of replies to your comments - it will never be used for any other purpose and will not be displayed. If you cannot see any comments below, see 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  

 

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