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:

-
You mean other than the ones in secure.wikimedia.org/wikipedia/en/wiki/… ? – J. M. Aug 9 '10 at 14:50
Yes, that is a very useful restriction to add. Sorry, I realize that my question is too broad as it stands. – user977 Aug 9 '10 at 14:53

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.

-
I don't view this as a paradox. – Carl Mummert Aug 9 '10 at 16:14
In my experience everyone who first sees this result finds it quite paradoxical that Goodstein sequences converge to 0. Indeed, by independence results, the only way to know otherwise is equivalent to having knowledge of the existence of said ordinal. Thus not only is it paradoxical but it is provably so! – Bill Dubuque Aug 9 '10 at 16:26
A counterintuitive result is not, in general, a paradox. In order for the convergence of Goodstein sequences to be a paradox, there would need to be some good reason to expect them not to converge; the fact that they seem to grow quickly at first is hardly evidence that they continue growing forever. Because there is no seeming contradiction inherent in Goodstein sequences converging, there is no paradox. – Carl Mummert Aug 9 '10 at 17:54
@Carl: Obviously I disagree. No doubt the interpretation of "paradox" is highly subjective. What one person views as a paradoxical might be obvious to someone else who has more expertise. In a few decades discussing Goodstein's theorem and related results almost everyone I've encountered (without expert knowledge) views it as paradoxical. Would your opinion be the same before you had such expert knowledge? – Bill Dubuque Aug 9 '10 at 18:17
It's not called "Goodstein's paradox" simply because of a historical accident: it was proved a theorem long before it became well known to nonexperts. Almost every nonexpert that I have encountered does seem to have the intuition that such sequences should remain increasing. As such it is paradoxical to them - even if they cannot explicitly formalize their intuition behind such. – Bill Dubuque Aug 9 '10 at 19:19

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.

-
Each person orders the alternatives according to [his or her] own preferences. You wouldn't use only "her," because we are not presuming that everyone is a female. – Olive Stemforn Jul 8 at 17:48

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.

-