Melt your brain
A paradox is a seemingly simple logical statement, but one that has two or more irreconcilable interpretations.
The Cretan paradox
This is probably the simplest logical paradox of them all, attributed to Epimenides:
I am a liar!
If I am a habitual liar, then I would lie about being a liar.
So, I must be a habitually truthful person.
But if I am a habitually truthful person, I would not say I was a liar, because that itself is a lie.
An even better way of putting this paradox is:
This statement is false.
Again, if the statement is false, then it must be true, but if it is true, it must be false. This paradox was known to the ancient Greeks, but its unpleasant side effects on mathematics were only formalised in 1930.
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.
It therefore logically follows that:
All non-black (white, yellow, blue) objects are non-ravens (milk, lemons, sky).
So every time you see a red apple or a pink Hydrangea, 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. Although this is a silly way to go about studying something (looking at all non-black non-ravens is a very slow way of finding out about black ravens), it is possible, especially in a finite universe.
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 supporting the hypothesis that all ravens are black, and the hypothesis that all ravens are white.
The omnipotent being
A favourite atheism/theism argument.
If god is omnipotent, then can She make a rock that is too heavy to lift?
If a god is all-powerful, then She must be able to create rocks of arbitrary mass. However, if She is all-powerful, She also ought to be able to make a rock too massive for Her to move. But that would mean She is not all-powerful, as She cannot move the rock.
The problem here is what we mean by 'omnipotent'. We might mean 'can defy physical law', or 'can defy physical law and logic'.
If we define omnipotence as the ability to do the physically impossible, whilst abiding by the laws of logic, a Goddess cannot create a rock too heavy for Her to lift. This is not paradoxical, since the concept 'a rock too heavy for an omnipotent being to lift' is meaningless if we accept She cannot transcend logic: it is logically impossible for there to be a stone She cannot move. So our omnipotent deity can transcend physical law, but is still grounded by logic.
However, if we define omnipotence as the ability to jump on logic till it's good and pulpy, then our Goddess is truely paradoxical: She can make a rock too heavy for Her to lift, but still be omnipotent. Some would argue that is all well and good, and their Goddess is just like that. In which case, your Goddess is also a giant cheese and pickle sandwich, since by defying logic, She makes any statements about Her properties immune to logical (dis)proof.
Hilbert's hotel
Hilbert's hotel isn't really a paradox, but is instead representative of the problems humans have getting their heads round the idea of infinity. 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 (taking an infinite amount of time on the phone presumably), leaving you with room 1, and all the other guests happy. Hence, 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 inhabitants of 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 naďve playground shouting matches about "I hate you infinity plus one!"
Russell's editor
The other paradoxes mentioned have a get-out clause of some sort, but the next two eat away at the heart of mathematics. There are lots of ways of putting this paradox, the most ubiquitous is the one about, 'Should the barber who shaves everyone who does not shave himself, shave himself?'. For what it's worth, here's my version:
A good scientific paper is one that does not contain a reference to itself: you cannot say, "This was discovered by Cook in 2004 (Journal of Meretricity)" in the 2004 Journal of Meretricity paper, because that is cheating: it's like putting yourself as a reference on a CV. So bad scientific papers will contain references to themselves. You have been told by the editor of the Journal of Meretricity to write a review paper in which you list every good paper in existence. You duly do this, but then run into a problem. Should you add a reference to the paper you are writing? If you want this paper to be good, then you must not reference it, as this would make the paper bad. However, if you don't reference it then the paper won't contain a list of all the good papers because it misses itself out. We have paradox: either our paper is inconsistent, or it is incomplete. To put it another way, our paper is the 'set' of all papers that do not reference themselves. If we include a reference to our paper, then by definition, we should not, because it refers to itself. However, if we do not add a reference to our paper, then by definition we should include it, because it does not refer to itself. Ouch.
The formulator of the paradox, Bertrand Russell, had this take on it:
The set of all things that are teaspoons is not a teaspoon. However, should the set of all-things-that-are-not-teaspoons be included in the set of all-things-that-are-not-teaspoons?
The only way out of this paradox is to define sets so as to exclude themselves, i.e. to add a new axiom to set theory that says, "the set of not-teaspoons cannot contain itself". However, adding new axioms to mathematics is generally seen as bad form.
Gödel's theorem
Gödel's theorem is the big grand-daddy of paradoxes. However, basically it's just a more formal version of the Cretan paradox from earlier. It deals two blows. The first to the idea that mathematics is complete, i.e. given an unproven theorem, such as the Riemann Hypothesis, mathematics must embody some way of proving whether it is true or not. If mathematics is complete, then with sufficient ingenuity, every theory can be proven to be either true or false. The second blow is to consistency, i.e. given a statement and a set of basic mathematical axioms (like 'there is a number 1'), you should not be able to prove a statement is true using one mathematical method, and false using another. If mathematics is consistent, you cannot generate a horrible contradiction by both proving and disproving a theory. Gödel's theorem uses a technique that turns mathematical expression and formulae 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.
Or more succinctly:
1. This statement cannot be proven.
If we assume mathematics (or any sub-system complex enough to contain arithmetic) is consistent, then we cannot prove this statement, because a proof would contradict the statement itself. Therefore if mathematics is consistent, then it cannot be complete because we cannot prove a statement like the one above. The statement is 'undecidable'. This implies that some theories will forever be inaccessible to proof.
Unfortunately, it gets worse. We would also like to be able to prove that the axioms of mathematics are consistent, and cannot lead to contradictions, rather than just assuming that they are. To prove a mathematical system is consistent, we need to be able to prove that the statement "this statement cannot be proven" cannot be proven, i.e. we need to prove:
2. The statement "this statement cannot be proven" cannot be proven.
However, Gödel used his numbering system to show that this second statement is equivalent to the first (their Gödel numbers are equal), so if we can prove it, we can also prove the first statement, which we already showed we cannot prove 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, any arithemtical system that can prove itself to be consistent is by definition 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!