Paradoxes

Melt your brain

A paradox is a simple logical statement that has two or more contradictory interpretations. Although they may seem like silly plays-on-words, it turns out that there are certain paradoxes at the root of mathematics that you cannot just hand-wave away.

The Cretan paradox

This is probably the simplest paradox of them all, attributed to Epimenides (a Greek philosopher)...

"I am a liar!"

If I am a liar, then I would lie about being a liar.

So, I can't be a liar.

But if I am a not a liar, I would not say I was a liar, because that itself is a lie.

Oh dear. An even better way of putting this paradox is...

"This statement is false".

If the statement is false, then it must be true, but if it is true, it must be false. This paradox was known the the ancient Greeks, but its unpleasant side effects on mathematics were only discovered in 1930. See below for details.

Hempel's ravens

This is an interesting paradox for a scientist, as it relies on empirical evidence. Our common experience is that...

"All ravens are black".

So it logically follows that...

"All non-black (white, yellow, blue) objects are non-ravens (milk, lemons, sky)".

So every time you see a red apple, the existence of these non-black non-ravens is also evidence for the existence of black ravens! So by merely examining the universe, we can accumulate evidence for the existence of black ravens from all the non-black non-ravens we see.

Unfortunately, the red apples are not just non-black non-ravens. They are also non-white non-ravens (not to mention non-blue non-ravens, non-pink non-ravens, etc). Since a red apple is a non-white non-raven, it also provides evidence for the existence of white ravens. So red apples are evidence that all ravens are black, and that all ravens are white. Which is something of a problem.

Hilbert's hotel

Hilbert's hotel isn't really a paradox, but shows the problems humans have getting their heads round the idea of infinity. Mr. Hilbert has opened an infinitely large hotel, with each room numbered 1, 2, 3, etc. Unfortunately, the hotel is full when you arrive asking for a room. "Not to worry," says Hilbert, "we'll just call all the rooms and get the occupants to move to the next room down." This he does, leaving you with room 1, and all the other guests happy. So, infinity + 1 = infinity.

Then an infinite number of new guests arrives. Hilbert looks worried for a moment, then has a bright idea. He phones everyone in the hotel and gets them all to move to the room with double the number of the one they're currently in, so the people in room 2 end up in room 4, those in room 102 in room 204, etc. This leaves all the odd numbered rooms free, of which there are an infinite number, just big enought to squeeze in the infinite number of guests. Hence, infinity + infinity = infinity.

Both these examples show that no matter how many things you add to an infinite set, the set won't get any bigger, putting paid to playground arguments about "I hate you infinity plus one!"

Russell's editor

Now it gets serious. All the other paradoxes have a get-out clause, but the next two eat away at the heart of mathematics. There are lots of ways of putting this paradox, the most common is the one about, 'Should the barber who shaves everyone who does not shave himself, shave himself?'. Another way is...

Most books have a bibliography at the end where references and further reading are listed. Very bad books with careless authors might list themselves in the bibliography. This is very silly (it's like putting yourself as a reference on a CV), so the librarian of the school library tells you to through all the school's books and write a (very boring) book that lists all the [good] books that do not list themselves. This sounds east enough, but the problem comes at the end: should you list the book you are writing? If you don't list it, then your list will be incomplete, because it won't list itself. But if you do list it, then by definition you shouldn't, because it now lists itself, and our book will be inconsistent, because it will list one book that does list itself. We have paradox: either our book is inconsistent, or it is incomplete.

The only way out of this paradox is to add a new rule ('axiom') to mathematics that says, "the list of lists-that-do-not-list-themselves does not contain itself" (i.e. to settle for incompleteness. However, adding new axioms to mathematics is generally seen as bad form.

Gödel's theorem

And finally, the big grand-daddy of paradoxes, Gödel's theorem. This one is very difficult to really get your head round, but basically it's just a more formal version of the Cretan paradox from earlier. It deal two blows to mathematics.

The first to the idea that mathematics is complete: if we have an unproven theorem, like the Riemann Hypothesis (or until recently, Fermat's last theorem), mathematics must contain some way of proving whether it is true or not if it is complete.

The second blow is to consistency: if we have a set of basic mathematical rules (the axioms, like 'there is a number 1'), you should not be able to prove the statement is true using one mathematical method, and false using another if mathematics is consistent.

Gödel's theorem turns mathematical formulae and proofs like 2+2=4 into statements about numbers. This allowed him to create statements about mathematical theorems which could be manipulated by simple arithmetic to produce proofs. Gödel's theorem states...

"In any consistent axiomatic system sufficiently strong to allow you to do basic arithmetic, you can construct a statement about natural numbers that can be neither proved nor disproved within that system. Furthermore, any sufficiently strong consistent system cannot prove its own consistency".

No, that doesn't make much sense to me either. How about this instead...

"1. This statement cannot be proven".

Now, if we assume mathematics can't contradict itself (it's consistent), then we cannot prove this statement, because a proof would contradict the statement itself. This means that mathematics cannot be complete, because we can never prove a statement like the one above.

Unfortunately, it gets worse. We would also like to be able to prove that mathematics cannot lead to contradictions. To prove that mathematicals is consistent, we need to prove that...

"2. The statement "this statement cannot be proven" cannot be proven".

Yes, even thinking about what that means hurts. Gödel's master stroke was showing that the second statement is mathematically identical to the first. If we can prove the second statement, we simultaneously prove the first statement. But we already showed we cannot prove this if mathematics is consistent! This is obviously a contradiction, and means that our mathematical system is not only incomplete, but is also inconsistent!

The upshot is that mathematics cannot prove certain theorems, and one of the theorems that it cannot prove is that mathematics is consistent. In fact, if mathematicals were able prove itself to be consistent, by definition it would be inconsistent! So mathematicians desperately hope that mathematics is consistent, whilst simultaneously hoping that no-one ever manages to prove it, since that would disprove it! I think we'll stop there, as my brain hurts.

Paradoxes on the web