Most 'unintuitive' application of the Axiom of Choice? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T05:31:10Z http://mathoverflow.net/feeds/question/20882 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice Most 'unintuitive' application of the Axiom of Choice? Tony Huynh 2010-04-10T01:21:18Z 2013-04-28T03:10:37Z <p>It is well-known that the <a href="http://en.wikipedia.org/wiki/Axiom_of_choice" rel="nofollow">axiom of choice</a> is equivalent to many other assumptions, such as the <a href="http://en.wikipedia.org/wiki/Well-ordering_principle" rel="nofollow">well-ordering principle</a>, <a href="http://en.wikipedia.org/wiki/Tychonoff%27s_theorem" rel="nofollow">Tychonoff's theorem</a>, 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. </p> <p>So, my question is what do you consider to be the most unintuitive application of choice?</p> <p>Here is the sort of answer that I have in mind. </p> <p>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).</p> <p>The <em>very</em> unintuitive fact is that the players have a strategy whereby they can <em>always</em> win. Indeed, it is hard to come up with a strategy where at least <em>one</em> player is guaranteed to answer correctly, let alone a co-finite set. <strong>Hint</strong>: the solution uses the axiom of choice. </p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/20883#20883 Answer by François G. Dorais for Most 'unintuitive' application of the Axiom of Choice? François G. Dorais 2010-04-10T01:32:21Z 2013-04-28T03:10:37Z <p>I highly recommend reading this paper by Chris Hardin and Al Taylor, <a href="http://www.math.upenn.edu/~ted/203S10/References/peculiar.pdf" rel="nofollow">A Peculiar Connection Between the Axiom of Choice and Predicting the Future</a>, as well as this shorter piece by Mike O'Connor <a href="http://xorshammer.com/2008/08/23/set-theory-and-weather-prediction/" rel="nofollow">Set Theory and Weather Prediction</a>.</p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/20886#20886 Answer by John Stillwell for Most 'unintuitive' application of the Axiom of Choice? John Stillwell 2010-04-10T02:42:26Z 2010-04-10T02:42:26Z <p>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.</p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/20905#20905 Answer by Sune Jakobsen for Most 'unintuitive' application of the Axiom of Choice? Sune Jakobsen 2010-04-10T08:55:58Z 2010-04-10T08:55:58Z <p>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).</p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/20909#20909 Answer by Tran Chieu Minh for Most 'unintuitive' application of the Axiom of Choice? Tran Chieu Minh 2010-04-10T10:15:12Z 2010-04-10T10:15:12Z <p>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.</p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/20918#20918 Answer by Chad Groft for Most 'unintuitive' application of the Axiom of Choice? Chad Groft 2010-04-10T12:38:15Z 2010-04-10T12:38:15Z <p>The Axiom of Determinacy (AD) fails.</p> <p>What that means: Partition the set <em><sup>&omega;</sup>&omega;</em> into two sets <em>S</em> and <em>T</em>, and think of this partition as a <em>game</em> (<em>S</em>, <em>T</em>) with two players. To play, player 1 picks a natural number <em>a</em><sub>0</sub>, then player 2 picks <em>b</em><sub>0</sub> (as a function of <em>a</em><sub>0</sub>), then player 1 picks <em>a</em><sub>1</sub> (as a function of <em>b</em><sub>0</sub>), then player 2 picks <em>b</em><sub>1</sub> (as a function of <em>a</em><sub>0</sub> and <em>a</em><sub>1</sub>), and so on until <em>a<sub>n</sub></em> and <em>b<sub>n</sub></em> are selected for all <em>n</em> &isin; <em>&omega;</em>. Then the sequence <em>a</em><sub>0</sub>, <em>b</em><sub>0</sub>, <em>a</em><sub>1</sub>, <em>b</em><sub>1</sub>, &hellip; is either in <em>S</em> (in which case player 1 wins), or in <em>T</em> (in which case player 2 wins).</p> <p>The game (<em>S</em>, <em>T</em>) is <em>determined</em> if either player 1 or player 2 has a winning strategy, <em>i.e.</em>, if there are functions <em>f<sub>n</sub></em>: <em><sup>n</sup>&omega;</em> &rarr; <em>&omega;</em> where choosing <em>a<sub>n</sub></em> = <em>f<sub>n</sub></em>( <em>b</em><sub>0</sub>, &hellip;, <em>b</em><sub><em>n</em>–1</sub> ) 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 <strong>R</strong>. </p> <p>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.)</p> <p>There are apparently many set theorists that agree with this assessment, since they try to rescue AD as relativized to <em>L</em>(<strong>R</strong>). 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<sup><em>L</em>(<strong>R</strong>)</sup> is outright provable in ZFC + "there is a measurable cardinal which is greater than infinitely many Woodin cardinals".</p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/20933#20933 Answer by Kevin Buzzard for Most 'unintuitive' application of the Axiom of Choice? Kevin Buzzard 2010-04-10T16:19:55Z 2011-07-15T13:43:44Z <p>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!]</p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/70338#70338 Answer by Ron Maimon for Most 'unintuitive' application of the Axiom of Choice? Ron Maimon 2011-07-14T15:46:45Z 2011-07-14T15:46:45Z <p>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.</p> <p>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.</p> <p>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 <a href="http://en.wikipedia.org/wiki/Wiener_process" rel="nofollow">http://en.wikipedia.org/wiki/Wiener_process</a> for a picture of a "realization" of a random walk). These pictures do not signify anything when the axiom of choice is present.</p> <p>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.</p> <p>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.</p> <p>(I realize that this answer overlaps with a previous one, but it corrects a serious central mistake in the former.)</p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/70386#70386 Answer by Christoph-Simon Senjak for Most 'unintuitive' application of the Axiom of Choice? Christoph-Simon Senjak 2011-07-14T23:13:41Z 2011-07-14T23:13:41Z <p>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.</p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/70387#70387 Answer by Asaf Karagila for Most 'unintuitive' application of the Axiom of Choice? Asaf Karagila 2011-07-14T23:36:20Z 2011-07-14T23:36:20Z <p>I think that it might not be the <em>most</em> unintuitive but the fact there exists sets which intersect with <em>every</em> perfect subset (but contains none of them!) of the reals is fairly bizarre.</p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/70392#70392 Answer by Nate Eldredge for Most 'unintuitive' application of the Axiom of Choice? Nate Eldredge 2011-07-15T02:47:17Z 2011-07-15T02:47:17Z <p>Since this question has been resurrected...</p> <p>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.</p> <p>Can you spot the flaw?</p> <p>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.</p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/70393#70393 Answer by Carl Mummert for Most 'unintuitive' application of the Axiom of Choice? Carl Mummert 2011-07-15T03:01:43Z 2011-07-15T03:01:43Z <p>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. </p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/70413#70413 Answer by Chris Eagle for Most 'unintuitive' application of the Axiom of Choice? Chris Eagle 2011-07-15T08:32:24Z 2011-07-15T08:32:24Z <p>Lebesgue measure exists for every Borel set, and is countably additive.</p> <p>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.</p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/70435#70435 Answer by Joel David Hamkins for Most 'unintuitive' application of the Axiom of Choice? Joel David Hamkins 2011-07-15T13:12:02Z 2012-01-02T23:04:59Z <p>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.</p> <ul> <li>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.</li> <li>A real number can be in the closure of a set $X\subset\mathbb{R}$, but not the limit of any sequence from $X$.</li> <li>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.</li> <li>A set can be infinite, but have no countably infinite subset.</li> <li>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 <a href="http://mathoverflow.net/questions/25132/cardinality-why-is-there-no/25152#25152" rel="nofollow">this MO answer</a>.)</li> <li>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 <a href="http://mathoverflow.net/questions/22927/why-worry-about-the-axiom-of-choice/22935#22935" rel="nofollow">François's excellent answer</a>.) This is a consequence of AD, and thus relatively consistent with DC and countable AC.</li> <li>There can be a field with no algebraic closure.</li> <li>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.</li> <li>There can be a vector space with no basis.</li> <li>There can be a vector space with bases of different cardinalities.</li> <li>The reals can be a countable union of countable sets.</li> <li>Consequently, the theory of Lebesgue measure can fail totally.</li> <li>The first uncountable ordinal $\omega_1$ can be singular.</li> <li>More generally, it can be that <em>every</em> uncountable $\aleph_\alpha$ is singular. Hence, there are no infinite regular uncountable well-ordered cardinals.</li> <li>See the <a href="http://en.wikipedia.org/wiki/Axiom_of_choice#Statements_consistent_with_the_negation_of_AC" rel="nofollow">Wikipedia page</a> for additional examples.</li> </ul> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/70504#70504 Answer by Ron Maimon for Most 'unintuitive' application of the Axiom of Choice? Ron Maimon 2011-07-16T14:09:43Z 2011-07-16T23:37:33Z <p>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).</p> <p>What is the axiom of choice doing in physics?</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/20882/most-unintuitive-application-of-the-axiom-of-choice/84780#84780 Answer by Richard Stanley for Most 'unintuitive' application of the Axiom of Choice? Richard Stanley 2012-01-03T00:54:08Z 2012-01-03T13:48:47Z <p>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. </p>