# Most 'unintuitive' application of the Axiom of Choice?

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.

-
I would guess that Banach-Tarski is about as unintuitive a result as there is. –  Steve Huntsman Apr 10 '10 at 1:24
The Banach-Tarski paradox loses some its counterintuitive appeal once you know how it works, but then the fact that it doesn't work in for disks in the plane becomes a little shocking. –  François G. Dorais Apr 10 '10 at 1:40
True, but I could say that any apparently counterintuitive theorem loses either the property of counterintuitiveness or of truth once you know how it either works or doesn't, respectively. –  Steve Huntsman Apr 10 '10 at 1:49
Not Banach-Tarski, its ramifications never stopped surprising me. –  François G. Dorais Apr 10 '10 at 1:57
This blog post is somewhat relevant: cornellmath.wordpress.com/2007/09/13/…. I especially like Terence Tao's comment. –  Qiaochu Yuan Apr 10 '10 at 2:06

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.
-
My personal favorite is the partition of $\mathbb{R}$ described in this MO post - mathoverflow.net/questions/22927/… –  François G. Dorais Jul 15 '11 at 13:54
Counterpoint is appreciated. –  Jim Conant Jul 15 '11 at 14:14
Asaf, I was referring to the distinction between "minimal" and "smallest" in a partial order (without AC the natural order on cardinalities may not be linear). In this terminology, it can be incorrect to say that $\aleph_0$ is the (or even a) smallest infinity, since when there are infinite Dedekind finite sets, then $\aleph_0$ is merely minimal as opposed to smallest among infinite cardinalities. –  Joel David Hamkins Jul 15 '11 at 14:44
Another example, due to Läuchli, is that $\mathbb Q$ can have non-isomorphic algebraic closures. Here, an algebraic closure of a field $K$ is defined to be an algebraically closed extension of $K$ that contains no algebraically closed subfield. In the absence of choice, you can have an algebraic closure of $\mathbb Q$ that is a countable union of finite sets but is not itself countable. –  Timothy Chow Jul 15 '11 at 18:35
Resurrecting an old answer here: It should be noted that many of these can be ruled out by resorting to countable AC or dependent choice, which avoid many of the strange consequences of full AC. For example, "A set can be infinite, but have no countably infinite subset", is ruled out by countable AC. –  Chad Groft Oct 14 '11 at 1:49

I highly recommend reading this paper by Chris Hardin and Al Taylor, A Peculiar Connection Between the Axiom of Choice and Predicting the Future, as well as this shorter piece by Mike O'Connor Set Theory and Weather Prediction.

-
NB. The O'Connor piece covers what Tony was talking about with hats. –  Steve Huntsman Apr 10 '10 at 1:52
(So do Hardin and Taylor.) –  François G. Dorais Apr 10 '10 at 1:59
Thanks Francois, the weather prediction angle is quite interesting. –  Tony Huynh Apr 10 '10 at 3:01

Maybe this is not the kind of application you have in mind, but a well-ordering of the reals seems highly counterintuitive to me. I would argue that well-ordering of $\mathbb{R}$ is the essence of many of the other counterintuitive results that have been mentioned.

-
Some years ago I also thought that well-ordering the reals is unintuitive, but now I know better: When you speak of the reals, you think of the structure of a complete ordered field. But well-ordering only refers to the size of the set. It's merely that first it's hard to imagine a uncountable well-ordering at all. –  Martin Brandenburg Apr 10 '10 at 9:33
I'm not concerned with the algebraic structure of the reals, only the size of the set. Nor do I have trouble with uncountable well-orderings per se; $\omega_1$ is fairly intuitive. I just find it hard to claim intuition about well-ordering the continuum when the known independence results for ZF are so stacked against it. How can its well-ordering be intuitive when we can't say what its ordinal number is? And when it is consistent for the continuum to have no well-ordering? –  John Stillwell Apr 10 '10 at 11:45
John, does this mean that you find the continuum hypothesis highly counterintuitive? And does the Banach-Tarski paradox follow from the well-orderability of the reals? –  Timothy Chow Jul 16 '11 at 23:11
Timothy, I'm torn about CH. I'd like it to be true, for the sake of simplicity, but it seems too simple to be true. As for Banach-Tarski, I think it follows from well-ordering of $\mathbb{R}$. One has to choose from subsets of $\mathbb{S}^2$, but I presume there is a definable bijection between $\mathbb{R}$ and $\mathbb{S}^2$. –  John Stillwell Jul 17 '11 at 1:00
I don't claim to have much intuition about what a well-ordering of $\mathbb{R}$ would look like (whatever that means), but the existence (even in the absence of AC) of a whole range of well-orderable uncountable sets makes it fairly believable that there's a bijection from $\mathbb{R}$ to one of them. Banach–Tarski, on the other hand, offers me no intuition even while I stare at its proof. –  Zach N Nov 13 '11 at 16:46

The fact that there exist non-measurable sets is highly counter-intuitive; the reason we don't find it so is that we've all been conditioned from day 1 to do measure theory very carefully, and define Borel sets, measurable sets, etc, so we all know that non-measurable sets exist because what would be the point of doing it all so carefully otherwise. At high school we were all taught that the probability of an event occurring was "do it a million times, count how often it happened, divide by a million, and now let a million tend to infinity". And no-one thought to ask "what if this process doesn't tend to a limit?". I bet if anyone asked their teacher they'd say "well it always tends to a limit, that's intuitively clear". But am I right in thinking the following: if we take a subset $X$ of [0,1] with inner measure 0 and outer measure 1, and we keep choosing random reals uniformly in [0,1] and asking whether they land in $X$, and keep a careful table of the result, then the number of times we land in $X$ divided by the number of times we tried just oscillates around between 0 and 1 without converging? That is fundamentally counterintuitive and in some sense completely goes against the informal (non-rigorous) training that we all got in probability at high school. [if I've got this right!]

-
Suppose you construct a non-measurable set of 01-sequences as follows. Call two sequences equivalent if they differ in finitely many places. Choose a sequence from each equivalence class, and then let your set be the set of all sequences that have even symmetric difference with the chosen representative of its equivalence class. It feels as though a random sequence should have probability 1/2 of belonging to the set. And if you change the definition to "symmetric difference has size congruent to 0 mod 100, it feels as though the probability should be 1/100. I'm confused. –  gowers Apr 10 '10 at 16:45
Another point I wanted to make was that if your set is chosen using AC, then it's not really clear what it means to choose a random real and ask whether it lands in the set. After all, you haven't said what the set is. So I'm not sure we would get this oscillatory behaviour because I'm not sure it's possible to make mathematical sense of the experiment in the first place. I do like it though ... –  gowers Apr 10 '10 at 17:25
The fact that a nonprincipal ultrafilter on $\omega$ is weaker than a well-ordering of $\mathbb{R}$ has been confirmed by Simon Thomas here: mathoverflow.net/questions/21031/ultrafilters-vs-well-orderings –  John Stillwell Apr 12 '10 at 23:19
I agree with Ron that the answer is wrong, but I don't agree with his reason. First, one can adjoin random reals (in the sense of Solovay) to models that satisfy choice, and the resulting models will still satisfy choice. What one cannot reasonably do is to ask whether such a random real belongs to a set $X$ from the ground model. If one takes that question literally, the answer is no; ground-model sets have only ground-model members. Some ground-model sets, Borel sets, have canonical extensions $X'$ to the forcing model, and one can ask (see next comment) –  Andreas Blass Jul 14 '11 at 18:39
whether a random real is in $X′$, but that doesn't work for "wild" sets $X$. Second, to say that a random real has some property (like being in X) doesn't require Solovay forcing. (People talked sensibly about properties of random reals before Solovay came along). In particular, Kevin's answer can be interpreted as saying that the set $Z$ of those sequences $z$ of reals for which the proportion among the first $n$ terms in $z$ that are in $X$ has liminf=0 and limsup=1 as $n\to\infty$ has measure 1. But I'm fairly confident that this is not the case; $Z$ is also non-measurable. –  Andreas Blass Jul 14 '11 at 18:45

There can be graphs all of whose cycles have even length and whose chromatic number is greater than two. In fact, let $G$ be the graph whose vertices are the real numbers, with $x$ and $y$ adjacent if $|x-y|=\sqrt{2}+r$, where $r$ is rational. Then $G$ has only even length cycles. Assuming that every subset of $\mathbb{R}$ is measurable (which is consistent with ZF), then the chromatic number of $G$ is uncountable. This is a result of Shelah and Soifer. If we assume the Axiom of Choice, then the chromatic number of $G$ is two.

-
A graph with zero edges is bipartite but its chromatic number is not 2 :-)  That nitpick aside, it's a neat example, though we must be careful to define "bipartite" as "no odd cycles", not the definition suggested by "bipartite = two parts" which is immediately equivalent to "chromatic number at most 2". –  Noam D. Elkies Jan 3 '12 at 5:00
@Noam, yes I realized this also and have changed the wording. –  Richard Stanley Jan 3 '12 at 13:46
I find this result quite intuitive. What intuition is it supposed to violate? “Every nice property of finite graphs must fail for infinite graphs?” Anyway, the wording is misleading: since the question asks for unintuitive consequences of the axiom of choice, the first sentence should read “There is no graph ...”, otherwise it looks like the pathological example is constructed using choice. –  Emil Jeřábek Jan 3 '12 at 15:29

One counterintuitive aspect of the axiom of choice is a theorem of Diaconescu and independently Goodman and Myhill that, in some constructive set theories that don't begin with the law of the excluded middle, the axiom of choice implies the law of the excluded middle. But in other systems such as Martin-Löf type theory, the corresponding form of the axiom of choice is completely constructive and does not imply the law of the excluded middle.

-

The Axiom of Determinacy (AD) fails.

What that means: Partition the set ωω into two sets S and T, and think of this partition as a game (S, T) with two players. To play, player 1 picks a natural number a0, then player 2 picks b0 (as a function of a0), then player 1 picks a1 (as a function of b0), then player 2 picks b1 (as a function of a0 and a1), and so on until an and bn are selected for all nω. Then the sequence a0, b0, a1, b1, … is either in S (in which case player 1 wins), or in T (in which case player 2 wins).

The game (S, T) is determined if either player 1 or player 2 has a winning strategy, i.e., if there are functions fn: nωω where choosing an = fn( b0, …, bn–1 ) guaranteed player 1 victory, or similarly for player 2. (We can't have both.) AD is just the statement that every such game is determined, which is false in ZFC. As with most of the weird examples, the undetermined game is constructed with a well-ordering of R.

What makes this so unintuitive to me is that both AC and AD are generalizations of statements that are easily seen for finite objects. (Any finite game, or even any game with finite depth, is determined, by an easy induction on the depth.)

There are apparently many set theorists that agree with this assessment, since they try to rescue AD as relativized to L(R). That the relative consistency strength of this statement is equivalent to that of large cardinals is considered good evidence that those large cardinals are, in fact, consistent. More precisely, ZF + AD is consistent iff ZFC + "there are infinitely many Woodin cardinals" is consistent, and ADL(R) is outright provable in ZFC + "there is a measurable cardinal which is greater than infinitely many Woodin cardinals".

-
I am unfamiliar with the notation ${}^n\omega$. What does it mean? –  Harald Hanche-Olsen Apr 10 '10 at 13:51
Just the set n-tuples in &omega;. It's usually written as &omega;<sup>n</sup>, but that notation could also refer to ordinal exponentiation, which is not quite the same. –  Chad Groft Apr 10 '10 at 16:12
We want to have the cake and eat it too :D. –  Tran Chieu Minh Apr 10 '10 at 16:13
@Tran: No problem, just apply the Banach-Tarski theorem to your cake. –  Andrej Bauer Jul 14 '11 at 21:43
Chad, to support your case for the naturality of AD a bit more: AD is precisely the statement $\neg\forall x_0\exists x_1\forall x_2\exists x_3\cdots A(\vec x)\iff \exists x_0\forall x_1\exists x_2\forall x_3\cdots \neg A(\vec x)$, an infinitary deMorgan law. The truth of the finitary deMorgan law constitutes a proof of determinacy for finite games. –  Joel David Hamkins Jul 15 '11 at 13:24

The most destructive aspect of uncountable choice is that it conflicts with random choice. With uncountable choice, any object which is constructed using randomness, like a random walk, a random field, or even a randomly picked real number, cannot exist, because there are sets which it cannot consistently be assigned membership to.

In order to define what it means to have a random walk, or a random graph, or a random infinite Ising model configuration, or whatever, you need to define what it means to have an infinite sequence of random coin flips. The result can be encoded as a real number, the binary digits of which are the results of the coin flip, and if this real number really exists, as an actual mathematical object, then this object either belongs to any given set S, or it doesn't.

It is so intuitive to think of random objects this way, that they are often illustrated with pictures, showing us what they look like (see http://en.wikipedia.org/wiki/Wiener_process for a picture of a "realization" of a random walk). These pictures do not signify anything when the axiom of choice is present.

The reason is that once you have actual random objects, for which you can assign membership to any set S, then you can define the probability of landing in S by choosing random objects again and again, and asking what fraction of the time you land in S. This always converges, because given any long finite sequence of 1's and 0's which represent independent random events, any permutation of the 1's and 0's has the same likelihood. This means that it is probability 0 that the seqeunce will oscillate in any way, and with certainty it will converge to a unique answer.

This answer is the measure of the set S, and every set is measurable in this universe. This makes analysis much easier, because everything is integrable, measurable, etc. This is so intuitive, that if you look at any probability paper, they will illustrate with random objects without hesistation, implicitly denying choice.

(I realize that this answer overlaps with a previous one, but it corrects a serious central mistake in the former.)

-
Ron, I don't understand how you conclude that "this means that it is probability 0 that the sequence will oscillate in any way." Could you expand on this? –  François G. Dorais Jul 14 '11 at 16:02
If you have a sequence of independent 0-1 events which are in every way identical, then any permutation of the 0s and 1s is just as likely to occur as any other. In order for the limit not to exist, there must be long segregated 0's followed by segregated 1's. But any segregated sequence of length N is segregated in only a negligible fraction of all permutations of this sequence, and the 0s and 1s can come in any permutation. There is no way in the world that an independent sequence of identical probabilistic 0-1's can fail to converge. –  Ron Maimon Jul 14 '11 at 23:09
François, I think Ron is saying that classically, if $S$ is a non-measurable subset of $[0,1]$ and $X$ is a random variable that is uniformly distributed in $[0,1]$, then we can't sensibly speak of "the event $X \in S$"; $a fortiori$, any attempt to formulate a strong law of large numbers for $S$ (by taking, as Kevin Buzzard suggested, a sequence $(X_n)$ of i.i.d. random variables, noting when "the event $X_n \in S$ happens", and seeing what almost surely happens to the proportion of successes as $n\to\infty$) fails. But... –  Timothy Chow Jul 15 '11 at 0:51
...if we discard the axiom of choice in favor of "all sets are Lebesgue measurable," then this sort of reasoning becomes legitimate for arbitrary sets $S$. Attempts to construct a counterexample by finding "bad" sequences of successes and failures whose proportion of successes oscillates wildly won't work, because such bad sequences will occur with probability 0. –  Timothy Chow Jul 15 '11 at 0:55
@Chow-- Thank you for stating it so clearly. I wanted to also emphasize that this is really the only counterintuitive aspect of uncountable choice, all the other examples are special cases. For example, the "predict the future/hats" business is counterintuitive because our intuition suggests that we can choose an infinite sequence of future-events/hat-colors at random. The axiom of choice forbids us from choosing at random. We must choose in an L-like model where choice holds. Similarly, random picks forbid Hamel bases for R over Q and for well-ordering of R, so this is the serious conflict. –  Ron Maimon Jul 15 '11 at 3:09

Using AC you can construct a (non-continuous) function that intersects any continuous function on any open interval (or even on any set with positive measure).

-

Every Vector Space has a Hamel basis. This is something that follows from the Axiom of Choice (though it is usually proved by Zorn's Lemma, which is equivalent to the AC). From this follows that $(\mathbb{C},+)$ is isomorphic to $(\mathbb{R},+)$, by considering $\mathbb{C}$ and $\mathbb{R}$ as $\mathbb{Q}$-Vectorspaces. I found this quite unintuitive.

-
This doesn't strike me as any more counter-intuitive than the fact that [0, 1) and (0,1) have the same cardinality... –  Simon Rose Jul 16 '11 at 17:18

I think that it might not be the most unintuitive but the fact there exists sets which intersect with every perfect subset (but contains none of them!) of the reals is fairly bizarre.

-

Lebesgue measure exists for every Borel set, and is countably additive.

I've always found it more surprising that our fuzzy intuitive ideas of area and volume can be pushed as far as they can than that they break when you push even further.

-
You actually don't need the axiom of choice at all to define the "Lebesgue" measure of an arbitrary sublocale of $\mathbb{R}$ and I found it equaly impressive. –  Simon Henry 8 hours ago

Not an answer but I think that AC itself is itself not intuitive if we look at it closely enough. The reason we think that AC is intuitive is because we have its counterpart for a finite collection, and we assume that an infinite collection should behave in the same way a finite collection does. That later assumption seems to require some faith, if we don't want to say entirely baseless.

-

Since this question has been resurrected...

One of my favorite things about the hat-guessing problem in the question is what happens when you think about it probabilistically. Let's say the hats are labeled by an adversary, whose goal is to make the players lose. Let's also say the number of players is countable, which should only make the game easier to win. A natural strategy for the adversary would be to choose the numbers randomly: say the $i$th hat is labeled with a random value $X_i$, where the $X_i$ are independently chosen from some continuous probability distribution. Let $Y_i$ be the $i$th player's guess. $Y_i$ can depend on all the $X_j$, $j \ne i$, but not on $X_i$, so clearly $Y_i$ is independent of $X_i$. Thus for each $i$, $P(Y_i = X_i) = 0$ since $X_i$ has a continuous distribution. So each player guesses correctly with probability 0. By countable additivity, almost surely, no player guesses correctly. So this is a "proof" that there can't be a strategy that guarantees that even one player guesses correctly.

Can you spot the flaw?

Rot13: Hfvat gur nkvbz bs pubvpr fgengrtl, gur qrcraqrapr bs gur Lf ba gur Kf vf abg zrnfhenoyr, fb va snpg gur Lf ner abg enaqbz inevnoyrf naq bar pnaabg qb cebonovyvgl jvgu gurz.

-
Rather than say "flaw", as if the proof is inherently wrong, you can ask "can you spot where choice ruins this probablistic argument?". Proofs like these are perfectly OK in a Solovay universe, and probability working correctly can be argued to be vastly more important than ineffable Hamel bases/well-orderings. –  Ron Maimon Jul 15 '11 at 3:32
In the hat-guessing game, $Y_i$ need only depend on the $X_j,j\gt i$, which is even less intuitive (a little bit less, anyway) than letting it depend on $X_j,j\ne i$. As stated in a long-ago Monthly problem, there is a function $f:s^\omega\to S$ such that, for each sequence $x_0,x_1,\dots\in S^\omega$, one has $x_n=f(x_{n+1},x_{n+2},\dots)$ for all but finitely many $n$. –  bof Oct 15 at 22:54

To me, the only "unintuitive" applications of uncountable choice is when it turns up in physics. The only case I know where this happens is in the maximal-extension theorem of Choquet-Bruhat (QM does not use uncountable choice). This uses local extension properties of solutions to General Relativity to prove, using Zorn's lemma, that there exists a maximal extension. The use of axiom of choice is, I think, essential. I couldn't see how to sidestep it when I read the paper a long time ago (somebody please correct me if I am wrong).

What is the axiom of choice doing in physics?

I believe that it is entirely due to the issue of double-sided maximally extended black holes. A maximal extension of General Relativity can contain "wormhole" like solutions (for example, a charged black holes with two patches connected by an interior region), and there can be countably many such bridges in any asymptotically flat patch. But each of these branches can connect you to another different asymptotically flat region, which might have its own countably infinite collection of bridges to other flat regions. The resulting spacetime is like a tree with countably many branches at each node, where each node represents an asymptotically flat spacetime, and each edge is a double-sided maximally extended black hole bridging the two nodes.

Such a tree can have infinite depth, and you must extend the solution to the whole tree. It seems intuitive that to patch the solutions together you need to extend the local solutions over continuum many nodes, and since GR is hyperbolic, you will get to make some arbitrary choices at each extension step. The dependence on choice then simply shows how unreasonable the maximally extended model of General Relativity is for physics.

-
Since this got downvoted, I started to worry that it might be incorrect. In particular, if one considers only regions which are a bounded geodesic distance from a given point, can the tree have infinitely many branchings? But it can, because the scale invariance allows ever smaller maximally extended black holes along a finite length geodesic to accumulate with nothing going wrong at the accumulation point. –  Ron Maimon Jul 16 '11 at 23:35
Perhaps this should be a question: is the maximal extension of Chonquet Bruhat always separable? The answer I give says no, but I am doubting now. –  Ron Maimon Jul 17 '11 at 13:40
The use of Zorn's lemma is not so shocking once you realise that causal inclusion gives a partial order on the set of all past sets. BTW, you seem to be talking about two different notions of maximal extensions here. The existence theorem of Choquet-Bruhat discusses maximally Globally Hyperbolic extensions, whereas your examples about black holes are talking about Analytic extensions. They are quite different beasts. –  Willie Wong Jan 3 '12 at 16:20
@WillyWong: They are not different--- the black holes are not analytic extensions, this is just a mischaracterization, they are globally hyperbolic extensions when you have a collapse, and there is no analyticity required (although people say so a lot for no good reason). –  Ron Maimon Oct 8 '12 at 18:26