Is there a *simple* example of how the axiom of choice can lead to a counterintuitive result?

Solution 1:

Intuitive and counterintuitive results are tricky, as you said, it's a subjective thing.

Let me try and give you one example, a discontinuous solution to Cauchy's functional equation. Namely, a function $f\colon\Bbb{R\to R}$ satisfying $f(x+y)=f(x)+f(y)$.

It's not hard to see that such function is necessarily $\Bbb Q$-linear, so start with a Hamel basis for $\Bbb R$ over $\Bbb Q$, now pick any permutation of the basis, and extend it to a linear automorphism. Since you switched two basis elements, you didn't get a scalar multiplication, so you got a function which is not continuous or even measurable.

The last sentence also show that choice is necessary, since it is consistent with the failure of choice that all $\Bbb Q$-linear functions are measurable, which implies they are continuous, which implies they are scalar multiplications.

There are two issues here: the axiom of choice allows us to go "outside the structure", and infinite sets are weird.

Outside the structure?

One of the arguments about choice not being constructive is that the axiom of choice does not tell you how to obtain a choice function, it just tells you that such function exists. But because we are not limited to a specific construction, or constraints, or anything, this function does not have to obey any rules whatsoever.

From a more category-centered view, you can show that the axiom of choice does not hold for $\bf Ab$ or $\bf Grp$, because not every epimorphism splits in these categories (case in point, $\Bbb R\to\Bbb{R/Q}$).

But set theory doesn't care. Set theory ignores structure. There is a function, and its range is a set, and we have to deal with the fact that this might be counterintuitive and lead to things like the Banach–Tarski paradox or a Vitali set existing, because once you have a set (of representatives), the rest is just stuff you can do by hand.

So we get that the axiom of choice, by letting us split surjections, creates sets which sort counter our understanding of a given "structure". But of course, this is not the fault of the axiom of choice. This is our fault, for not understanding the interactions (or lack thereof) between "structure" and "sets" in general.

Infinite sets are weiiiiirrrrrdddd!

The second reason for many of the paradoxes is that infinite sets are weird. Look at the free group with two generators, $F_2$. Would you have expected it to have a subgroup which is generated by three generators? By infinitely many? No, that makes no sense. And yet, this is true. $F_2$ has a copy of $F_\infty$, and thus of $F_n$ for all $n$.

Or, for example, would you expect $\Bbb Q$ to be homeomorphic to $\Bbb Q^2$? That's also weird.

But these things don't even have to do with the axiom of choice. They have to do with the fact that we are finite, and these sets are not. And we base our naive intuition off finite sets, and then it fails. So we fix it, but we still base our intuition off of sets which "we hoped were good enough" (hence the ubiquity of the terms "regular" and "normal"), but these too fail us.

What's really funny is that when the axiom of choice fails, and you look at those extreme counterexamples (e.g. amorphous sets), then these look even weirder because choice is in fact very ingrained into our intuition.

To sum up?

The axiom of choice is really not at fault here. It lets us prove the existence of sets which lie outside of our intuition, because our intuition is honed to understand a given structure (e.g. topological structures, group structures, etc.), and it doesn't help when the infinitude of the sets lets us stretch and bend them in all kinds of ways to create weird stuff like the Banach–Tarski Banach–Tarski paradox.

Epilogue?

So there are two more minor points that I want to touch on.

1. Our intuition is crap. We used to think that functions are "more or less continuous", then we learned that in fact almost none of them are continuous. Then we figured that almost all continuous functions are differentiable, but then learned that almost none of them are... and you see where this trend is going.

   If you trace things back in history you run into physics or physical things in many cases. And physics is about phenomenon, things we can see and measures, which we automatically assume are continuous and "make sort of sense". But the mathematical world, as we have it in the post-post-modern era has a lot more to offer, and that sort of clashes with the roots, and sometimes with the intuition we carried from the original motivations.

2. The axiom of choice is not really to blame. If you deny the Banach–Tarski paradox, and require that all sets of reals are Lebesgue measurable instead, then you can partition the real numbers into strictly more non-empty parts than elements. This is just bonkers. And it's not because of the axiom of choice, that is out the window here. It's because infinite sets are weird.

So what comes next? Next comes the fatalistic understanding that you can do nothing to change this. Unless you want to work in constructive mathematics, in which case you will run into a lot of other weird results, like non-empty sets that have no elements.

Solution 2:

You may not have asked quite the question you want to ask. You sound like you're trying to understand exactly why some people object to AC - but that doesn't really have to do with the counterintuitive results. In particular, I'm not sure you're ever going to find a proof where "naive intuition 'goes wrong' exactly at the step where we use the axiom of choice", because I think in general, that isn't really where your intuition goes wrong, and it isn't the source of the counterintuitiveness of the result. It's literally just a coincidence that some counterintuitive results happen to involve choice in their proof.

It's a common (I think) misunderstanding that the objections to the axiom of choice have to do with it leading to strange results. Mathematicians have no problem accepting counterintuitive results. Counterintuitive results occur all the item with no axiom of choice. The trouble is that accepting the axiom of choice forces you to take a very questionable philosophical point of view on what it means to "exist".

Now, listen, to say that a mathematical object "exists" at all is already somewhat dubious. The number five doesn't "exist" like a table or an apple exists. We're already stretching the definition of the verb "to exist" just by doing arithmetic and geometry, but at least I can sort of imagine an object like a number or a circle. They exist in my mind, if nothing else, or I can describe them or even write down a formula for them.

But now we get to a set like the Vitali set. The construction of the Vitali set and the conclusion that its length is simultaneously zero and non-zero (or more precisely, that it has no reasonable concept of length) is definitely simple, although I don't know if the existence of non-measurable sets is exactly counterintuitive. The point is, though, think about how I show that this set "exists". All I do is, after partitioning the real number into a disjoint family of "dusts", I use choice to grab one point from each set.

I can't tell you one single number in the Vitali set. If you give me a number, I can't tell whether it's in the Vitali set or not. You want a picture? Forget it. A formula? Fat chance. I can't even imagine the Vitali set in my head. At this point I seem to have no excuse to be using the word "exists".

The reason this happened is because AC lets me claim something exists without having to explicitly describe it. This is really what people (used to) object to in AC.