Logic and
Language
Load the menuLoad the menu


Copyright   James R Meyer    2012 - 2024 https://www.jamesrmeyer.com

BANNER CONTENT

A Simplified Explanation of Gödel’s Incompleteness Proof:
Part 1


 

 


 

Basic Logical Concepts

Page last updated 11 May 2021

 

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, and for every variable there is a set of permissible values for that variable, called the domain:

 

The domain of a variable is the set of all possible values that may be substituted for that variable.

 

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 (do not confuse this with the domain of a variable).

 

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

 


 

 


 

Interested in supporting this site?

You can help by sharing the site with others. You can also donate at Go Get Funding: Logic and Language where there are full details.

 

 

As site owner I reserve the right to keep my comments sections as I deem appropriate. I do not use that right to unfairly censor valid criticism. My reasons for deleting or editing comments do not include deleting a comment because it disagrees with what is on my website. Reasons for exclusion include:
Frivolous, irrelevant comments.
Comments devoid of logical basis.
Derogatory comments.
Long-winded comments.
Comments with excessive number of different points.
Questions about matters that do not relate to the page they post on. Such posts are not comments.
Comments with a substantial amount of mathematical terms not properly formatted will not be published unless a file (such as doc, tex, pdf) is simultaneously emailed to me, and where the mathematical terms are correctly formatted.


Reasons for deleting comments of certain users:
Bulk posting of comments in a short space of time, often on several different pages, and which are not simply part of an ongoing discussion. Multiple anonymous user names for one person.
Users, who, when shown their point is wrong, immediately claim that they just wrote it incorrectly and rewrite it again - still erroneously, or else attack something else on my site - erroneously. After the first few instances, further posts are deleted.
Users who make persistent erroneous attacks in a scatter-gun attempt to try to find some error in what I write on this site. After the first few instances, further posts are deleted.


Difficulties in understanding the site content are usually best addressed by contacting me by e-mail.

 

Based on HashOver Comment System by Jacob Barkdull

Copyright   James R Meyer   2012 - 2024
https://www.jamesrmeyer.com