# Logical Completeness

Created | Updated Aug 23, 2007

Numbers
| A History of Numbers
| Propositional Logic
| Logical Completeness
| The Liar's Paradox

Logical Consistency
| Basic Methods of Mathematical Proof
| Integers and Natural Numbers

Rational Numbers
| Irrational Numbers
| Imaginary Numbers
| The Euler Equation

Mathematicians were always sure that every question had an answer that could be proven to be true. Maths, to them, was an open book, just waiting for people to be able to read it. This notion of completeness was argued on aesthetic grounds: it just wasn't *elegant* to have ugly, difficult problems that couldn't be solved. Some may take longer to prove or disprove, but they were always proved eventually. The idea of completeness was one of the main foundations of maths... until the early 20th Century, when one man destroyed any hope of a complete mathematics.

In the first half of the 20th century, a German-American mathematician by the name of Kurt Gödel proved his Incompleteness Theorem and so ended the hopes of ever finding a complete mathematical model. Gödel's famous theorem is steeped in bizarre logical constructions, but the following tale helps to explain it without resorting to scary maths.

### The Librarian Paradox

A librarian is wandering round her library one day and comes across a shelf of catalogues. There are catalogues of novels, poems, essays and so on, and some of these catalogues, she discovers, list themselves, while others do not.

In order to simplify the system, the hard-working (and rigorously logical) librarian makes two more catalogues. One lists all those catalogues that list themselves; the other lists all those that don't. Once she has completed this task, she has a problem: should the catalogue which lists all the other catalogues which do not list themselves, be listed in itself? If it is listed, then by definition it should not be listed. However, if it is not listed, then by definition it should be.

This situation therefore creates a contradiction - the Librarian Paradox.

### Indecidable Elements

Gödel showed that this paradox could be expressed rigorously and used it to show that there are some problems which simply cannot be proved to be true or false. In fact, they are already known to be true (since if they were false a counter-example would exist which would act as proof for their falsity), but this knowledge is useless since it isn't shown logically.

Gödel managed to show that this was a feature of any rigorous logical system. Furthermore, should a second logical system be used to prove 'indecidable' statements from our system, some of the axioms would be contradictory and thus incompatible. This means that no logical system is complete and no system is any more logical than the other.

Luckily this only applies to very few problems and, for the most part, maths is complete... which means we can use it to solve most problems we come across (just not *all* problems).