Most 'unintuitive' application of the Axiom of Choice? - MathOverflow

Most 'unintuitive' application of the Axiom of Choice?

2010-04-10T01:21:18Z

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 by François G. Dorais for Most 'unintuitive' application of the Axiom of Choice?

2010-04-10T01:32:21Z

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.

Answer by John Stillwell for Most 'unintuitive' application of the Axiom of Choice?

2010-04-10T02:42:26Z

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.

Answer by Sune Jakobsen for Most 'unintuitive' application of the Axiom of Choice?

2010-04-10T08:55:58Z

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).

Answer by Tran Chieu Minh for Most 'unintuitive' application of the Axiom of Choice?

2010-04-10T10:15:12Z

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.

Answer by Chad Groft for Most 'unintuitive' application of the Axiom of Choice?

2010-04-10T12:38:15Z

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 a₀, then player 2 picks b₀ (as a function of a₀), then player 1 picks a₁ (as a function of b₀), then player 2 picks b₁ (as a function of a₀ and a₁), and so on until a_n and b_n are selected for all n ∈ ω. Then the sequence a₀, b₀, a₁, b₁, … 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 f_n: ⁿω → ω where choosing a_n = f_n( b₀, …, b_n–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 AD^L(R) is outright provable in ZFC + "there is a measurable cardinal which is greater than infinitely many Woodin cardinals".

Answer by Kevin Buzzard for Most 'unintuitive' application of the Axiom of Choice?

2010-04-10T16:19:55Z

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!]

Answer by Ron Maimon for Most 'unintuitive' application of the Axiom of Choice?

2011-07-14T15:46:45Z

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.)

Answer by Christoph-Simon Senjak for Most 'unintuitive' application of the Axiom of Choice?

2011-07-14T23:13:41Z

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.

Answer by Asaf Karagila for Most 'unintuitive' application of the Axiom of Choice?

2011-07-14T23:36:20Z

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.

Answer by Nate Eldredge for Most 'unintuitive' application of the Axiom of Choice?

2011-07-15T02:47:17Z

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.

Answer by Carl Mummert for Most 'unintuitive' application of the Axiom of Choice?

2011-07-15T03:01:43Z

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.

Answer by Chris Eagle for Most 'unintuitive' application of the Axiom of Choice?

2011-07-15T08:32:24Z

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.

Answer by Joel David Hamkins for Most 'unintuitive' application of the Axiom of Choice?

2011-07-15T13:12:02Z

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.

Answer by Ron Maimon for Most 'unintuitive' application of the Axiom of Choice?

2011-07-16T14:09:43Z

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.

Answer by Richard Stanley for Most 'unintuitive' application of the Axiom of Choice?

2012-01-03T00:54:08Z

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.