Confronting The Unprovable - Gödel And All That
Written by Mike James   
Thursday, 20 December 2018
Article Index
Confronting The Unprovable - Gödel And All That
Failure of Logic
The Influence of the Infinite

The failure

What could possibly be wrong with this idea?

It seems so reasonable that what we know should be extended in this way using but the force of pure logic. There really isn’t any alternative to the idea of logical proof that sane people find acceptable.

It also seems entirely reasonable to suppose that applying this method will eventually get us to any statement that is true. What is more, you might as well give a computer the task of shuffling the symbols and seeing what is true. 

Yes math is soulless and a matter for mechanical computation. 

Consider now the problems discussed at the start – Fermat’s last theorem and the four-colour theorem – their solutions are just a matter of computing time.

Now we come to the downfall of the method.

You would assume that given a properly formed arrangement of symbols that the computer, or the human, could eventually work out either a proof of the theorem or an anti-proof, i.e. a proof that the negation of the theorem is true and the theorem is false. It might take a long time but in principle you could work out if the statement was true or false. This is the assumption of consistency that we suppose will hold for any reasonable or useful system of reasoning.

A theorem has to be either true or false – there is no middle ground and it isn’t reasonable to have proof that it is both.

This sounds so obvious that there is no need to really think about it too deeply but it is also equally obvious that a statement (let alone a proof or a theorem) has to be true or false – there is no middle ground.




Now consider:

                               This sentence is false

Well you can begin to see that things are not quite so simple.

If the statement is true it is false and if it is false it has to be true.

This is the paradox of Epimenides (named after the Cretan philosopher Epimenides of Knossos who was alive around 600 BC), and it is the key to Kurt Gödel’s proof that axiomatic systems aren’t consistent in the sense that there are theorems that cannot be proved true or false within the system.




There may be a larger system, i.e. one with more axioms in which these theorems are provable but that’s almost cheating.



Kurt Gödel (1906-1978)


The argument that Gödel used is very simple.

Let’s suppose that there is a machine M that can do the job we envisaged for a consistent system.

That is, the machine can prove or disprove any theorem that we feed to it. It is programmed with the axioms of the system and it can use them to provide proofs.

Now suppose we ask for the program for the machine written in the same logic used for the theorems that the machine proves. After all any computer can be reduced to logic and all we are requesting is the logical expression that represents the design of the computer – call this PM for "Program for M".

Now we take PM and construct a logical expression which says

“The machine constructed according to PM will never prove this statement is true”

and call this statement X.

Now we ask the machine to prove or disprove X.

Consider the results. If the machine says “yes this is true” then the statement is false. If the machine says that the statement is false then the statement is true.



The proof that there are theorems that cannot be proved


You see what the problem is here and you can do this sort of trick with any proof machine that is sufficiently powerful to accept its own description as a theorem.

Any such machine, and the system of logic on which it is based, must, by its very nature be inconsistent in that there are theorems that can be written using the system that it cannot be used to prove either true or false.

In other words there are three types of theorem in the system – those that are provably true, those that are provably false and those that are undecidable using the axioms that we have at our disposal.

OK, you may say but is it possible to for a machine to be powerful enough to attempt to prove a statement that involves its own description? Perhaps it is in the nature of machines that they cannot cope with their own description.

The really clever part of Gödel’s work was to find that any axiomatic system powerful enough to describe the integers, i.e. powerful enough to describe simple arithmetic, has this property.

That is arithmetic isn’t a consistent axiomatic theory which means that there are theorems about the integers that have no proof or disproof within the theory of arithmetic.

So now think about the 300-year search for a proof for Fermat’s last theorem.

Perhaps it wasn’t that the mathematicians weren’t trying hard enough. Perhaps there was no proof. As it turns out we now know that a proof exists but there was a long time when it was a real possibility that the theorem was undecidable.

You clearly understand the idea but do you believe it?

Consider the following problem: there seem to be lots of paired primes i.e. primes that differ by two (3,5), (5,7), (11,13) and so on. It is believed that there are an infinite number of such pairs - the so called "twin prime conjecture" but so far no proof. 

So what are the possibilities?

You examine number pairs moving over larger and large integers and occasionally you meet paired primes.

Presumably either you keep on meeting them or you there comes a point when you don’t.

In other words, the theorem is either true or false. And as it is true or false presumably there should be a proof of this.





Last Updated ( Thursday, 20 December 2018 )