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’