Timeline for Unnecessary uses of the axiom of choice
Current License: CC BY-SA 4.0
38 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 29 at 8:19 | comment | added | bof | Isn't the "habitual proof" in your example the sort where it's "transparently obvious" that the axiom of choice is not needed because a suitable choice function can be defined explicitly? Usually when you "choose an epsilon" the only requirement is that epsilon be small enough, so instead of "choose epsilon such that" you could say "let epsilon be the first term of the sequence {1/n} such that." | |
| Jul 29 at 0:55 | answer | added | Lucenaposition | timeline score: 1 | |
| Sep 4, 2023 at 12:55 | comment | added | Jianing Song | Not exactly on-topic, but there are many situations where we assume choice but (much) weaker form of it is needed. For example, only countable choice is needed to prove that the countable union of countable sets is countable. Baire category theorem is equivalent to dependent choice. Only WPP (weak partition principle) is needed to show that nonmeasureable subsets of $\mathbb{R}$ exist. Personally, if AC were not that powerful, I would definitely have no worry using it. | |
| Jan 8, 2023 at 12:52 | answer | added | Timothy Chow | timeline score: 6 | |
| Mar 4, 2022 at 11:52 | answer | added | Sam Sanders | timeline score: 2 | |
| Mar 2, 2022 at 9:58 | answer | added | Gro-Tsen | timeline score: 8 | |
| Mar 2, 2022 at 8:52 | answer | added | Samuel Mimram | timeline score: 1 | |
| Feb 23, 2022 at 16:05 | answer | added | daw | timeline score: 4 | |
| Feb 22, 2022 at 9:50 | comment | added | Asaf Karagila♦ | @AndreaFerretti: The blog post doesn't make it very clear, I agree. As for the circular nature of the proof, if my memory serves me right, it's done by analysis of polynomials and not by using the irrationality of roots. But maybe I'm misremembering. | |
| Feb 22, 2022 at 8:29 | comment | added | Andrea Ferretti | Btw, I didn't check it in detail, but the proof is probably circular: both reciprocity for the prime two and Dirichlet theorem for arithmetic progressions use quadratic fields. Now, there are a lot of proofs for reciprocity so maybe not... | |
| Feb 22, 2022 at 8:26 | comment | added | Andrea Ferretti | @AsafKaragila cool, I didn't know it was you! :-) | |
| Feb 20, 2022 at 21:44 | comment | added | Asaf Karagila♦ | @AndreaFerretti: Or, you know, the original. | |
| Feb 18, 2022 at 19:34 | comment | added | Z. M | @AnuragSahay To compare, a comment of an answer below points to a fact that ZF (without any form of AC) is enough to show that any countable field admits a unique countable algebraic closure (up to a non-unique isomorphism). Recall that ZF is not enough to show that every countable union of countable sets is countable. | |
| Feb 18, 2022 at 18:40 | comment | added | Ray | Would a proof that uses Choice when Countable Choice suffices qualify? | |
| Feb 18, 2022 at 17:16 | answer | added | Julia Williams | timeline score: 26 | |
| Feb 18, 2022 at 16:53 | answer | added | Willie Wong | timeline score: 4 | |
| Feb 18, 2022 at 16:26 | comment | added | Andrea Ferretti | Tongue in cheek, but this proof of the irrationality of $\sqrt{2}$ :-) florianfelix.net/math/An-outrageous-proof | |
| Feb 18, 2022 at 15:29 | answer | added | user21820 | timeline score: 12 | |
| Feb 18, 2022 at 14:31 | comment | added | Z. M | @AnuragSahay It is more complicated than one might think. In fact, first, one does not need the full strength of AC to prove the existence and "the" uniqueness of algebraic closures — the ultrafilter lemma suffices, and it seems open whether the existence and/or the uniqueness of algebraic closures imply the ultrafilter lemma. On the other hand, I don't know an example of a field of which the existence of an algebraic closure in unprovable in ZF. In short, what I know is that a weaker version of AC suffices, but I don't know whether it is necessary. | |
| Feb 18, 2022 at 13:27 | answer | added | Ege Erdil | timeline score: 36 | |
| Feb 18, 2022 at 13:00 | answer | added | Tim Campion | timeline score: 14 | |
| Feb 18, 2022 at 12:31 | answer | added | Ege Erdil | timeline score: 10 | |
| Feb 18, 2022 at 11:59 | answer | added | Tom Leinster | timeline score: 17 | |
| Feb 18, 2022 at 11:32 | comment | added | Anurag Sahay | @Z.M: Your comment should definitely be an answer. If someone had asked me whether existence of a maximal atlas for every manifold depended on choice before I saw your comment, I would almost certainly have said "yes". It would also be interesting if you or someone else could point out what makes this different from other similar phenomenon (e.g., existence a maximal ideal in a ring, basis for vector spaces, algebraic closure for fields, all of which require choice). | |
| Feb 18, 2022 at 5:14 | history | became hot network question | |||
| Feb 18, 2022 at 3:04 | comment | added | Jim Conant | Doyle and Conway's division by three paper. | |
| Feb 18, 2022 at 2:07 | answer | added | Pace Nielsen | timeline score: 8 | |
| Feb 18, 2022 at 0:58 | comment | added | Asaf Karagila♦ | Unfortunately I lost my laptop charger, so I have to use my phone. There are several examples I can give, and will do so once I am back home. | |
| Feb 17, 2022 at 21:49 | comment | added | Vanni | You might find the article "A proof of two fundamental theorems on linear transformations in Hilbert space, without use of the axiom of choice" by Iacopo Barsotti interesting. | |
| Feb 17, 2022 at 21:47 | history | edited | Tom Leinster |
edited tags
|
|
| Feb 17, 2022 at 21:47 | history | made wiki | Post Made Community Wiki by Stefan Kohl♦ | ||
| Feb 17, 2022 at 21:32 | comment | added | Z. M | Zorn's lemma is sometimes invoked to show that the maximal atlas (in the definition of differentiable manifolds) exists, but it is unnecessary. | |
| Feb 17, 2022 at 21:31 | comment | added | Will Sawin | The snake lemma is an interesting case where I'm not sure if the habitual proof where you choose an inverse image should be counted as using the axiom of choice. (If you choose at once an inverse image for each element, you are unnecessarily using Choice, but if you, for each element, choose an inverse image, follow it around the diagram, observe that the destination doesn't depend on your choice, and then map the element to the unique value that works for every choice, you aren't.) | |
| Feb 17, 2022 at 21:24 | comment | added | Tom Leinster | Of course, "obvious" is subjective. I don't think the example I gave is entirely obvious, although we all know that for any given mathematical thing, some mathematician will come along and tell you it's trivial. if you want some other topological examples, try "product of two compact spaces is compact", or "every open cover of a sequentially compact metric space has a Lebesgue number". The first can certainly done without choice, but it's harder than the example I gave. The second, I don't know. And I don't think I have any non-topological examples, actually. | |
| Feb 17, 2022 at 21:22 | answer | added | Michael Hardy | timeline score: 44 | |
| Feb 17, 2022 at 21:22 | comment | added | Tom Leinster | Mostly I'm interested in examples that lie between "transparently obvious how to remove dependence on choice" and "major new idea needed to remove dependence on choice". But what I find interesting may be different from what others find interesting, so let a thousand flowers bloom. | |
| Feb 17, 2022 at 21:17 | comment | added | LSpice | Do you have any non-topological examples, or, alternatively, could you share some more topological examples? This seems like the sort of tic where people, e.g., will order a finite set when they don't have to; I imagine one could find plenty of proofs that artificially use choice in a transparently unnecessary way (and I'd dare to include your given topological example in that category), but it seems like you're looking for something more interesting. | |
| Feb 17, 2022 at 21:12 | history | asked | Tom Leinster | CC BY-SA 4.0 |