Mathematical paradoxes?

Question

What are some interesting mathematical paradoxes?

What I have in mind are things like the Banach-Tarski paradox, Paradox of Zeno of Elea, Russel's paradox, etc..

Edit: As an additional restriction, let us focus on paradoxes that are not already in the list at:

https://secure.wikimedia.org/wikipedia/en/wiki/Category:Mathematics_paradoxes

Answer 1

One example not in the above list is Goodstein's theorem, a highly nonintuitive concrete number theoretic theorem which is unprovable in Peano arithmetic (or, similarly, the Hercules vs. Hydra game). They essentially encode induction up to the ordinal $\epsilon_0 = \omega^{\omega^{\omega^{\cdot^{\cdot^{\cdot}}}}}$ - something that is not at all intuitive to those who are not familiar with such ordinals - especially their Cantor normal form.

Answer 2

A nice paradox (in the sense of going against the common opinion) which is not in that list is Arrow's theorem. More or less, it states the following. Let be given a set of people who vote on some issue, and have a finite number of alternatives (at least 3). Each person orders the alternatives according to her preferences; the outcome of the vote is an order on the set of alternatives which is supposed to reflect the common consensus.

More formally, a preference is a total order on the set of alternatives, and a voting system is a function which associates to each $n$-uple of preferences another preference. It turns out that the only voting system which satisfies some innocent-looking hypothesis is the projection on some factor, that is, the dictatorship of one of the people.

Answer 3

One of the consequences of Goedel's incompleteness theorem is that if $T$ is a finitely axiomatizable theory of arithmetic, then

• $T$ proves that $T$ is consistent

if and only if

• $T$ is inconsistent!

The reason is that an inconsistent theory proves anything, and a consistent theory never proves its own consistency.