Time for some hard-core geeking-out.

This comment on HN by /u/jiggawatts struck me as a brilliant idea: it’s an intuitive counter-example to the axiom of choice, which seem intuitively obvious, but leads to weird results like the Banach-Tarski paradox.

For those of you who are not hard-core geeks, the axiom of choice says (more or less) that if you are given a collection of non-empty sets, you can choose a member from each of those sets.  That seems eminently plausible.  How could it possibly not be true?

Here’s how: consider the set of numbers that cannot be described using any finite collection of symbols.  Such numbers must exist because there are only a countably infinite number of numbers that can be described using a finite collection of symbols, but there are an uncountably infinite number of real numbers.  So not only are there numbers that cannot be described using a finite number of symbols, there are vastly more of these than numbers that can be so described.

And yet… how would you describe such a number?  By definition it is not possible!  And so it is not at all clear (at least not to me) what it would even mean to “choose” a number from this set.

This is, of course, not a proof that the axiom of choice is wrong.  It’s an axiom.  It can’t be wrong.  But it is a good example for casting doubt in its intuitive plausibility, and that feels like progress to me.

Read More