[Math] Most ‘unintuitive’ application of the Axiom of Choice

Question

It is well-known that the axiom of choice is equivalent to many other assumptions, such as the well-ordering principle, Tychonoff's theorem, and the fact that every vector space has a basis. Even though all these formulations are equivalent, I have heard many people say that they 'believe' the axiom of choice, but they don't 'believe' the well-ordering principle.

So, my question is what do you consider to be the most unintuitive application of choice?

Here is the sort of answer that I have in mind.

An infinite number of people are about to play the following game. In a moment, they will go into a room and each put on a different hat. On each hat there will be a real number. Each player will be able to see the real numbers on all the hats (except their own). After all the hats are placed on, the players have to simultaneously shout out what real number they think is on their own hat. The players win if only a finite number of them guess incorrectly. Otherwise, they are all executed. They are not allowed to communicate once they enter the room, but beforehand they are allowed to talk and come up with a strategy (with infinite resources).

The very unintuitive fact is that the players have a strategy whereby they can always win. Indeed, it is hard to come up with a strategy where at least one player is guaranteed to answer correctly, let alone a co-finite set. Hint: the solution uses the axiom of choice.

Answer 1

I have enjoyed the other answers very much. But perhaps it would be desirable to balance the discussion somewhat with a counterpoint, by mentioning a few of the counter-intuitive situations that can occur when the axiom of choice fails. For although mathematicians often point to what are perceived as strange consequences of AC, many of the situations that can arise when one drops the axiom are also quite bizarre.

• There can be a nonempty tree $T$, with no leaves, but which has no infinite path. That is, every finite path in the tree can be extended one more step, but there is no path that goes forever.
• A real number can be in the closure of a set $X\subset\mathbb{R}$, but not the limit of any sequence from $X$.
• A function $f:\mathbb{R}\to\mathbb{R}$ can be continuous in the sense that $x_n\to x\Rightarrow f(x_n)\to f(x)$, but not in the $\epsilon\ \delta$ sense.
• A set can be infinite, but have no countably infinite subset.
• Thus, it can be incorrect to say that $\aleph_0$ is the smallest infinite cardinality, since there can be infinite sets of incomparable size with $\aleph_0$. (see this MO answer.)
• There can be an equivalence relation on $\mathbb{R}$, such that the number of equivalence classes is strictly greater than the size of $\mathbb{R}$. (See François's excellent answer.) This is a consequence of AD, and thus relatively consistent with DC and countable AC.
• There can be a field with no algebraic closure.
• The rational field $\mathbb{Q}$ can have different nonisomorphic algebraic closures (due to Läuchli, see Timothy Chow's comment below). Indeed, $\mathbb{Q}$ can have an uncountable algebraic closure, as well as a countable one.
• There can be a vector space with no basis.
• There can be a vector space with bases of different cardinalities.
• The reals can be a countable union of countable sets.
• Consequently, the theory of Lebesgue measure can fail totally.
• The first uncountable ordinal $\omega_1$ can be singular.
• More generally, it can be that every uncountable $\aleph_\alpha$ is singular. Hence, there are no infinite regular uncountable well-ordered cardinals.
• See the Wikipedia page for additional examples.