Astonishing and innocent results with the axiom of choice

Question

The product of nonempty sets is nonempty.

I am fascinated that such a simple and seemingly intuitive statement can lead to rather astonishing results such as the Banach-Tarski paradox or the solution to this riddle.

I am also intrigued by the seemingly innocent results that rely on AC (the existence of algebraic closures, any ideal is contained in a maximal ideal) and I wonder if I am missing some intuition to see how truly remarkable they are.

My question: What are other examples of seemingly magical results whose proofs rely explicitly on AC, and what are examples of seemingly innocent results that rely on AC that upon further examination turn out to be fairly remarkable themselves?

Answer 1

From the top of my head:

1. Continuity of real functions at a point $x$ is equivalent to sequential continuity.
2. Every infinite set has a countable infinite subset.
3. The countable union of countable sets is countable.
4. There exists an injection from $\aleph_1$ into $\Bbb R$.
5. There are non-Borel sets.
6. Every non-empty set can be endowed with a structure of a group (and so, abelian group, ring, field, and so on follow).
7. Every free abelian group is projective.
8. Every divisible abelian group is injective.
9. There are "enough" projective (or injective) abelian groups. (The last two are full-on equivalents to choice, this one is weaker.)
10. Every tree of height $\omega$ where all the levels are finite has a branch.
11. Every field has an algebraic closure.
12. If a field has an algebraic closure, then it has a unique algebraic closure (up to isomorphism).
13. Subgroup of a free group is free.
14. Subgroup of a free abelian group is free abelian.
15. Every vector space has a basis.

The list goes on forever. I may add a few more later.

Answer 2

This isn't an answer to the question in the last paragraph, but here's one way to repair your intuition about applications of the axiom of choice. One way to think about why choice is not intuitive is to think in terms of computational resources (see, for example, this blog post by Terence Tao). For any kind of mathematical construction you might want to do, think about what kind of computational resources you'd need to actually carry it out. Some sets have the property that it takes a lot of computational resources to write down an element of that set. For example, the set of solutions to a Diophantine equation may be non-empty, but it may still take a long time to actually write one down.

Whenever you have a bounded amount of computational resources, the axiom of choice is going to be false because you'll run out of computational resources when you try to write down an element of a sufficiently large product of non-empty sets. For example, suppose you have only a finite amount of computational resources. Then the axiom of countable choice will be false: if I take countably many Diophantine equations, none of which you currently know solutions to, and ask you to write down a solution to each, you may not be able to do it even if I guarantee to you that solutions exist because it may take you an infinite amount of computational resources, which you don't have. (Of course, you may be able to cleverly solve them all at once, but I may be able to stump you with an even trickier set of Diophantine equations. Matiyasevich's theorem shows that I can just ask you to write down the solutions to every Diophantine equation.)

You can think about algebraic closures and maximal ideals similarly. When you actually try to construct the algebraic closure of a field, you need to repeatedly find irreducible polynomials so you can adjoin their roots and get a bigger algebraic extension. It takes computational resources to find irreducible polynomials, depending on the nature of the field you started with, and if the field you started with is sufficiently complicated it may take more computational resources than you have. Similarly, when you actually try to write down a maximal ideal containing an ideal, you need to repeatedly find elements not contained in the ideal but that do not, together with the ideal, generate the unit ideal. It takes computational resources to do this, etc.