15 ms·
What is the Axiom of Choice?
- exmadscientist 5y agoMy favourite statement of the Axiom of Choice, from AlienAtSystem via https://www.irregularwebcomic.net/4035.html https://www.irregularwebcomic.net/4035.html : > As there are infinitely many sets, instead of going through them manually, you have to find an algorithm [to select an item from each set]. So Person A tells the other player an algorithm to select an element. Then that other player finds a set where the algorithm fails. > If you, for example say: "Take the smallest element", then I say "One of my sets is all negative integers, it doesn't have a smallest element." > Then maybe you say: "Take the smallest element, or if it does not have that, take the largest." Then I say "One of my sets is all integers, which has neither". Then maybe you add: "If it has neither, take the element closest to 0 (in case of tie, take the larger one)". Then I say: "What about the set of all integers and all their reciprocals? It doesn't have an element closest to 0 either." > When Person A gives up and says: "Look, there's some algorithm that does it, right, why do I have to recite it manually?", then that person has taken the Axiom of Choice. If they say "Okay, fine, you win, there's no algorithm you can't find a counterexample to", then that person rejects the Axiom of Choice.
- jleahy 5y agoIs that not the axiom of finite choice, which holds in ZF set theory without AC?
- lupire 5y agoHow is it finite? Integers are infinite. It's Countable Choice, and of course the essence of Countability (why it's our favorite cardinality) is that almost all of our intuition about finite numbers can be correctly applied to countable infinities. Uncountable Choice (a set for every Real number, a choice from every set) is where thing ago off the rails and ZF looks substantially different from ZFC.
- oscardssmith 5y agoCan't you get countable choice with zf? Countable means there is a bijection to the naturals, so you can always pick the element that corresponds with 0.
- richardwhiuk 5y agoI think in the last example, you need "the set of all integers, except 0, and all their reciprocals", otherwise the answer is well-defined.
- eeegnu 5y agoOne of the many reasons for defining the natural numbers to begin at 1. I didn't even notice they said integers and thought they said naturals.
- coldtea 5y ago>If you, for example say: "Take the smallest element", then I say "One of my sets is all negative integers, it doesn't have a smallest element." Why would a set of "negative numbers" not have a smallest element? Negative numbers are also ordered in a number line (-5 is smaller than -2 for example).
- Filligree 5y agoIt's the set of all negative numbers. That doesn't have a smallest number, because negative infinity is not a number.
- nixpulvis 5y ago[3] (from OP) directly contradicts this, though I am also very confused why real numbers are somehow unorderable, while the integers are not. https://jaydaigle.net/blog/what-is-the-axiom-of-choice/#fn:3 https://jaydaigle.net/blog/what-is-the-axiom-of-choice/#fn:3
- joppy 5y agoThe set of positive integers starts {1, 2, 3, …} and there are no positive integers smaller than 1. On the other hand the set of positive real numbers has no smallest element, since for any positive real number x, the number x/2 is smaller and still a positive real. It’s not that the reals are unorderable (they are most certainly ordered), it’s that certain subsets of the reals do not necessarily contain a minimum/maximum.
- Sharlin 5y agoHow does it contradict that? The set of negative integers does not have a least element, and neither does the set of negative reals. (But the former does have a greatest element (–1) while the latter doesn’t have that, either.)
- nixpulvis 5y agoOh dear, I dropped the critical word "positive" from this in my reading. My bad.
- YetAnotherNick 5y agoFor (any subset of)rational numbers there exist many simple algorithms to form an ordering. eg. Take the number is reduced for `(+/-)a/b`. A number is smaller if its `a+b` is smaller. In case of tie number is smaller if its `a` is smaller. Even in case of tie positive number is smaller. I don't know the proof but there could be no algorithm like that for real numbers.
- wizzwizz4 5y ago$<$ gives an ordering over the reals. It's an ordering with a first element that's the tricky bit.
- pron 5y ago> ... then that person rejects the Axiom of Choice. You're looking at it from a philosophical perspective where people care about whether the axiom is "true" or not. Other approaches to mathematics don't care, because they view its value not in some metaphysical notion of truth but in utility. They might say: this proof requires the axiom of choice and that proof doesn't, without assigning either one any value beyond utility (where utility might be, in some case, just their intellectual edification). I think this is what the article is trying to drive at as well. We can't "accept" or "reject" the axiom of choice based on some philosophical grounds, because those philosophical grounds would need to involve infinities [1], which, themselves, are not philosophical but mathematical. We either choose to use it or not based not on where we come from but on where we want to go. [1]: The view that mathematical philosophy could be derived from core basic principles outside of mathematics was called Logicism, and was favoured by Bertrand Russell. Unfortunately, mathematical systems without some mathematical (i.e. non-"logical") axioms are quite limited, and almost all of them include at least one mathematical axiom, usually one that is equivalent to the existence of the natural numbers.
- cannabis_sam 5y ago>they view its value not in some metaphysical notion of truth but in utility. Isn’t this a philosophical perspective?
- pron 5y agoIt is a perspective in the philosophy of mathematics that rejects the idea that all of mathematics is necessarily anchored in philosophical truths beyond itself.
- cannabis_sam 5y ago> It is a perspective in the philosophy of mathematics So it is a philosophical perspective…?
- pron 5y ago
- shadowlight 5y agoThe algorithm that executes an element from the set of all algorithms one at a time until an algorithm succeeds to select an element from a set will work on any set and itself? a = the algorithm A = set of all selection algorithms b = any set def a(x): while True: f = a(A) # you have to select an algorithm from the set of selection algorithms result = f(x) if result is None: A = A - f # set of all selection algorithms without f continue else: return result a(b) #will always return a result or not terminate for any choice of b? Obviously there's problems with this because I'm not a mathematician and I'm just making stuff up off the top of my head. But would any one who's an expert care to explain what's the issue with the above? I'm looking at it and such an algorithm is defined in terms of itself (like a factorial, which is legal) and may never terminate (which also legal because an algorithm selecting the smallest number from all sets that only contain positive numbers will never terminate either). Wait but then if you look at the code it provably will never terminate because A does not shrink as it recurses.
- rocqua 5y agoI think that such an algorithm, if the order of algorirthms tried is random, is almost surely (so with probability 1) never going to terminate. Moreover, you'd probably want to limit the tries to algorithms that terminate. But that brings you into the halting problem.
- openasocket 5y agoYou can run a countably infinite sequence of algorithms in parallel and stop when one of them terminates without running into the halting problem. Say you have a set of algorithms, numbered 1, 2, 3, ... and each algorithm consists of a sequence of instructions (with jumps and gotos), where each instruction takes a finite amount of time to run. The algorithm is as follows: run the first instruction for algorithm 1, then the next instruction for algorithm 1, then the instruction for algorithm 2, then 1 again, then 2, then 3, then 1, 2, 3, and 4, and you can see the pattern now. If any of them reaches the halt instruction halt. Even if all but one of these algorithms runs forever, you'll still eventually halt when that one algorithm completes. I believe this approach is called dove tailing
- ASalazarMX 5y agoInstructions for a Banach-Tarski theorem demo: 1. Find any solid object. 2. Divide that object in infinite, dimensionless fragments. 3. Make as many copies as you want with the infinite fragments. 4. Reform the original object with the remaining fragments. ... I still have fragments please help.
- ColinWright 5y agoI assume you're joking, but in case anyone thinks your description is accurate, it's wrong in a significant way. Point (2) is fundamentally wrong in a critical way. The whole point of the Banach-Tarski Theorem is that you only have finitely many pieces. Of course these pieces are composed of infinitely many points, but it's a finite number of "pieces". Others may find it amusing, sense of humour vary widely. Usually I just shrug and move on, but in the essence of this "joke" you've genuinely misrepresented the entire point.
- ASalazarMX 5y agoI tried to joke about how real objects don't have an infinite number of surface points. This theorem is often quoted as "mathematically-proven way to deconstruct a sphere and build two identical spheres", but this can't translate to reality in any way, it's an abstract thought exercise. Of course, "mathematically-proven way to deconstruct a sphere and build two identical spheres in your imagination" doesn't sound as cool.
- ColinWright 5y agoFor anyone still following, the theorem is perhaps best described like this: We model spheres as collections of points, and given a collection of points there is a fairly obvious way to model the idea of moving that collection around in a way that reflects moving a physical object. The problem is, given a sphere, we can partition the points into six sets, move those sets around, and recombine them to give us two spheres the same size as the initial one. In a very real sense, in this model we can "cut up" a sphere, then rearrange the pieces to make two spheres. We've doubled our volume. Clearly this is nonsense, and it shows the limitations of the model. But equally, it tells us something important about the maths we use every day to model buildings, bridges, fluid flow, and more. All models are wrong, some models are useful. -- George E. P. Box I would add: Some things are nonsense, but sometimes the nonsense can tell us useful things about the way the models are wrong.
- einpoklum 5y agoWhat is the axiom of choice... hmm... maybe a way to claim legitimacy for the recent spate of US presidents?
- twic 5y ago> So here are a few things that don’t cause controversy: > * If we have one set, we can definitely pick an element from it. Can we? How? The point of a set is that it doesn't distinguish between its elements in any way. It's not ordered, there is no special element, etc. So how can you pick one element from a set? If you pick a total ordering over the elements in the set, then you can easily pick the smallest, or largest. But that's not picking an element from a set, it's picking an element from a specific ordering of that set! You can't do that without coming up with an actual ordering! Is picking an element from a single finite set something you can build using ZF? Or is it another, less controversial, axiom? What do constructivists think about this? Is there a flavour of mathematics where this axiom is not assumed? What are the consequences of that?
- siraben 5y ago> Is picking an element from a single finite set something you can build using ZF? In ZF it's tautological by the axiom of regularity[0]. If you have a non-empty set X, there is an element y such that y ∈ X and X and y are disjoint. [0] https://en.wikipedia.org/wiki/Axiom_of_regularity https://en.wikipedia.org/wiki/Axiom_of_regularity
- twic 5y agoIt seems to me that there is a huge difference between "a set X must have an element y" and "given a set X, you can get an element y". If set theorists do not make that distinction, then that is the answer to my question!
- l33t2328 5y agoWhat do you mean “you can get”? Being precise is especially important in math.
- ceh123 5y agoI think the commenter means that just because you know an element with a certain property is in the set, we can't conclude that there is a way to "choose" such an element. All we know is there exists at least one of these elements, there could be one (in which case we have a choice function that is well defined, choose the one element that satisfies the property) or there could be infinitely many such elements and we're stuck back at the beginning to construct a choice function. Edit: I think the above might be wrong actually, I haven't had a proper set theory course yet but it looks like "existential instantiation" [0] is what allows you to "choose" the element here (possibly?) but this sits within the logic that proceeds ZF set theory. Also see [1] for a decent discussion on AOC for finite sets. [0] https://en.wikipedia.org/wiki/Existential_instantiation https://en.wikipedia.org/wiki/Existential_instantiation [1] https://math.stackexchange.com/questions/132717/do-we-need-the-axiom-of-choice-for-finite-sets https://math.stackexchange.com/questions/132717/do-we-need-t...
- deleted 5y ago[deleted]
- siraben 5y agoSomewhat not well known among all mathematical circles, but Diaconescu's theorem states that the law of the excluded middle follows from the axiom of choice[0]. This means if you wish to work in constructive mathematics (which has great overlap with computer science), not only you must not take LEM as given but also not take choice as given. There is much to say—mathematically, computationally and philosophically—on the axiom of choice and its variants (countable choice, dependent choice) and subtle interactions with other axioms.[1][2][3] From my experience most mathematicians accept the axiom of choice (or an equivalent statement such as Zorn's lemma[4][5] or Teichmüller-Tukey[6]) because of its pervasiveness and usefulness in many areas of math, such as completeness of first-order logic, existence of a basis of any vector space, showing products of compact topological spaces are compact, and more. [0] Diaconescu's theorem https://en.wikipedia.org/wiki/Diaconescu%27s_theorem https://en.wikipedia.org/wiki/Diaconescu%27s_theorem [1] Exposition of choice, LEM, etc. in Coq http://adam.chlipala.net/cpdt/html/Universes.html http://adam.chlipala.net/cpdt/html/Universes.html [2] Choice vs. countable choice https://mathoverflow.net/questions/22990/choice-vs-countable-choice https://mathoverflow.net/questions/22990/choice-vs-countable... [3] Martin-Löf on choice https://raw.githubusercontent.com/michaelt/martin-lof/master/pdfs/One-hundred-years-of-Zermelo-s-axiom-of-choice-what-was-the-problem-with-it-2009.pdf https://raw.githubusercontent.com/michaelt/martin-lof/master... [4] Zorn's lemma https://en.wikipedia.org/wiki/Zorn%27s_lemma https://en.wikipedia.org/wiki/Zorn%27s_lemma [5] How to use Zorn's lemma https://gowers.wordpress.com/2008/08/12/how-to-use-zorns-lemma/ https://gowers.wordpress.com/2008/08/12/how-to-use-zorns-lem... [6] Teichmüller–Tukey lemma https://en.wikipedia.org/wiki/Teichm%C3%BCller%E2%80%93Tukey_lemma https://en.wikipedia.org/wiki/Teichm%C3%BCller%E2%80%93Tukey...
- PaulHoule 5y agoI don’t believe it. Steve Wolfram should grow some balls and say he doesn’t believe it either.
- soVeryTired 5y agoI don’t think it’s a question of ‘belief’. AOC is logically independent of the other ZF axioms: you may find it aesthetically ugly (a viewpoint I’m sympathetic to). But you can’t disbelieve it any more than you can disbelieve Euclid’s parallel postulate.
- naveen99 5y agoInterestingly politicians (like AOC) are also independent of logic.
- PaulHoule 5y agoBut I don't have to use it, or I can deprecate it. Particularly I think those "real" numbers are phony compared to the integers and rationals. (At least the latter have names)
- threatofrain 5y agoHere's a professor of math in some Australian university who has pursued a philosophy of mathematics while basically rejecting infinities, axiom of choice, and reals. https://www.youtube.com/watch?v=U75S_ZvnWNk https://www.youtube.com/watch?v=U75S_ZvnWNk
- xiaodai 5y agoWhat's yellow and equivalent to the Axiom of Choice? Zorn's lemon
- nixpulvis 5y agoBest quote so far: > If we have infinitely many pairs of shoes we don’t need the axiom of choice, since we can just take the left shoe from each pair; but if we have infinitely many pairs of socks, we do need the axiom of choice. - Bertrand Russell So randomness seems like a good fit for "choice" here, no? Or maybe call it ambivalence, or indifference. If the objects are truly unidentifiable, can it possibly matter which one you choose? As the argument surely goes...
- lmm 5y agoThe original statement of the axiom I heard was "it's possible to make an infinite number of arbitrary choices" - I think that's a good word for what you're getting at. Of course it doesn't matter which you choose - the axiom doesn't tell you anything about which you can choose - but whether you can choose at all is important. E.g. Hilbert's basis theorem relies on the idea that given an infinite-dimensional space you can always "start somewhere" - it doesn't matter specifically where, but it matters that you can pick a specific point in the space to start from. (The first journal he submitted it to rejected the paper with the comment "this is not mathematics, this is theology")
- nixpulvis 5y agoThe axiom of arbitrarity has an interesting ring to it... slightly avoiding the theological connotation, while being a bit bleak. Anyway, I hope they gave him a Ph.D for that comment, lolol. Oh and yikes, did Hilbert just bring roots of polynomials into the mix?
- siraben 5y ago> So randomness seems like a good fit for "choice" here, no? The axiom of choice is exactly the thing that tells us that we can make "random" choices. The way set theory works is that you have axioms to talk about intuitions of sets. So you might say that such a reasonable intuition is that we can make "make unlimited random choices", but this is exactly the axiom of choice! It's not about a choice from an infinity but an infinity of choices.
- Ostrogodsky 5y ago
- ColinWright 5y agoLess comprehensive, more specific: https://www.solipsys.co.uk/new/APointAgainstTheAxiomOfChoice.html?UG16HN https://www.solipsys.co.uk/new/APointAgainstTheAxiomOfChoice... Also submitted as a separate item: https://news.ycombinator.com/item?id=27855143 https://news.ycombinator.com/item?id=27855143 Broadly (and as this article explains), AC says that given any collection of non-empty sets, you're allowed to "choose" a set that contains one thing from each of them. In set theory terms, the "product" of non-empty sets is non-empty. This has some uncomfortable consequences.
- rssoconnor 5y agoTo build upon the "Just relax" section: by Shoenfield's absoluteness theorem[1], if ZFC proves some Sigma^1_3 statement, then ZF also proves it. In particular, the Axiom of Choice has no arithmetic consequences, and thus has no effect on number theory, nor what you are able to prove about the correctness of any particular algorithm, etc. [1] https://en.wikipedia.org/wiki/Absoluteness#Shoenfield's_absoluteness_theorem https://en.wikipedia.org/wiki/Absoluteness#Shoenfield's_abso...
- jaydaigle 5y agoThis is super cool and I wish I'd known about it before writing the piece; I'd have been comfortable being a lot more muscular in the conclusion. This seems like it makes precise my suggestion that the axiom of choice only matters for aggressively infinite and unphysical statements.
- hsn915 5y agoWhy is it only a problem when you have to choose from an infinite amount of sets? Why isn't the problem that you can get an infinite number of sets in the first place?
- Twisol 5y agoIf you allow yourself the infinite set of the natural numbers, you can pretty easily get an infinite set of sets. For instance, for every natural N, take the set of naturals less than N. Or greater than N, if you'd like an infinite set of infinite sets. As the article notes, these particular infinite families are easy to produce a choice function for: just take the least element of each set. But not all infinite families have enough determined structure for that kind of rule. If we tried to make it impossible to construct an infinite family of sets, we'd have to disallow relatively reasonable families like the ones I described above. Those are pretty useful, though, so it makes sense to address the problem further downstream. (I suppose another avenue is to try to isolate the features that make the above families "reasonable" and others unreasonable, so that only reasonable families can be constructed. That seems somewhat fraught, though.)
- hsn915 5y agoWhat's wrong with just choosing a random set element?
- tel 5y agoIt happens regularly when, surprise, you deal with infinities in some other place. A good, fairly intuitive example is integration where, I think, it's common to prove convergence using AoC in the multidimensional case. More or less, you want to integrate a function over, say, a square. We'll do it with a generalization of the Riemann sum by arbitrarily dividing up that square into little squares, measuring the function at one place in each square, multiplying the areas by those measurements, and summing. Then we take that process to its infinite limit. We have to be smart here, but we end up with an infinite set of contiguous pieces of our original square. Or, an infinite set of sets. We'd like to measure our function once from each of those pieces, so we need to choose one point from each piece. Which is easily dispatched with AoC. (In 1-dimensional integration, each subdivision of the domain has a total ordering, so you don't necessarily need AoC. Technically my example of a square also has a total ordering, so we could get away with not using AoC, but as you start to twist coordinates in the domain space more and more you can imagine places where seeking out an ordering of the space might be challenging. But no matter, AoC still works!)
- CompMan411 5y agoVeritasium describes a similar situation (not the AOC); a hotel that has infinite rooms and what happens when an infinite number of buses each with an infinite number of guests pulls up. https://youtu.be/OxGsU8oIWjY https://youtu.be/OxGsU8oIWjY
- jkhdigital 5y ago> Similarly, if we could prove the axiom of choice from the ZF axioms, we would have to either accept it as true, or completely rework all the foundations of math. And the footnote following this statement: > At the beginning of the 20th century, Bertrand Russell and others found deep contradictions in the naive version of set theory in use at the time, and the ZF axioms were developed to avoid those problems. But we’d rather avoid doing it again. My understanding is that the “constructive” mathematicians objected strenuously to these proposed foundational “solutions”. It’s starting to look like they may have been on to something, as there is an ongoing effort (since 2013 at least) to recast the foundations in a manner that accommodates both traditional and intuitionistic approaches. Short anecdote to confirm that this might gain traction: I’m a comp sci PhD student (focus on cryptography) and just yesterday I met with a math professor to ask her to serve on my advising committee. I had some brief run-ins with Homotopy Type Theory (the proposed “new foundations”) and was hoping she might be familiar with it—as it turns out, some of her own students had recently convinced her to start a weekly jam session where they gradually work through the HoTT textbook. She invited me to join them and I eagerly accepted :-)
- hebrox 5y agoIs this [1] perhaps the book you’ll work through? [1] https://homotopytypetheory.org/book/ https://homotopytypetheory.org/book/
- jkhdigital 5y agoYes, exactly. She actually had a physical copy of it
- pklausler 5y agoGoodness, a mathematics hardcover for $21? I'm in!
- dandanua 5y agoTo me, the Axiom of Choice is absolutely natural – if we can pick one element of a set then we surely can pick elements from a collection of sets, who cares that this collection can be infinite. The problem with this axiom is that it can't be formally proven from ZF axioms. But there are a lot of other natural things that can't be proven in ZF. For example, the consistency of ZF can't be proven in ZF due to Godel's incompleteness.
- shadowgovt 5y agoIs there a missing "deterministically" in the axiom of choice statement? I can imagine the common-sense "Of course you can choose one element" assumption breaks down if we add the constraint that you need to in some way be able to have another actor choose the same element. Because for an uncountably-infinite-sized set of uncountably-infinite-sized sets, perhaps there is no way to label individual elements such that if I choose A, someone else can also choose A (how will we know they're the same A?).
- thethimble 5y agoAh this is super helpful. I’m here stuck thinking “just pick any element at random”. Needing to have deterministically consistent pickings from infinite sets makes the problem clear and much more interesting.
- shadowgovt 5y agoI think that's why the "infinite socks vs. infinite shoes" are mentioned---because the socks are equivalent so you can't tell by the 'label' which one you grabbed.
- jaydaigle 5y agoBut what does "picking at random" mean? If you think it's obvious that you can just make infinitely many random choices at the same time, you're endorsing the axiom of choice. (If you think you can make one random choice at a time, you're endorsing the axiom of finite choice, which is just true. Determinism doesn't matter here, but "at the same time" matters a lot.)
- shadowgovt 5y agoExcellent! That's the piece of the puzzle I was missing. Thank you!
- antonzabirko 5y ago> Let’s assume there is a first person in the line, so it’s not infinite in both directions; you have infinitely many people in front of you, but only finitely many behind Is this even possible? One of the premises in the article. Won't it be infinity backwards for the nth person?
- magneticnorth 5y agoThey're just describing a set of people you could consider ordered by positive integers. The first person has no one behind them, the nth person has n-1 people behind them
- antonzabirko 5y agoBut how can that hold when you're approaching infinity? It would only apply to sets finite in both directions.
- magneticnorth 5y agoThe natural numbers (positive integers) are the numbers 1, 2, 3 , 4, 5, .... The "..." signifies that there are infinitely many such numbers, so there is no largest natural number but there is a smallest (1 is smallest). In that sense it is infinite in only one direction - written here it is infinite to the right but has an end at the left. Nothing special happens as you "approach infinity" and in fact that's not a thing you can do. No matter how high you count, you have only have counted finitely many numbers and there are an infinite set more that you have not counted.
- antonzabirko 5y agook thanks
- bvoq 5y agoReally good article. > You don’t have to explain how you’re choosing elements. We’ll just assume you can make it work somehow. Very interesting remark. The way I think about it now after reading your article is: If you prove something with the axiom of choice, all you need to do is provide an ordering to get practical results from it. If you fail to do so, oh well. That being said, I don't think you need R (the reals) for practical applications, countably infinite sets like IQ (intervals over Q) are enough and the well-ordering rule doesn't seem paradoxical anymore (countably infinite sets can be ordered as there is a bijection to N). Example: Pi can be approximated arbitrarily close with a lower and upper bound on Q. The functions used to derive the lower and upper bound with arbitrary precision (also a number in Q) are Pi in this sense
- iammisc 5y agoInteresting article... The derivative problem is particularly enlightening I think. A derivative is a limit. Thus the answer you get for a derivative is also a limit. For example, if you have the real speed of a car at every point in time as well as the position, then nominally, in infinite world, the speed is just the derivative of the position curve. But if you are in finite world, then the derivative curve in infinite world is the limit of the speed curve (and note that limit does not mean upper bound).. it just is a useful tool for reasoning what will happen if you take a more fine grained set of measurements. For some fineness of measurement, there will be a point at which your observed speed curve is always within epsilon of the ideal one. Good article
- dwheeler 5y agoIt's interesting to look at how people have handled the axiom of choice in Metamath, since the axiom of choice has long had some controversy. Metamath lets you state your axioms, then show that proofs build from their axioms. Each such collection of axioms & proofs is called a "database". There are Metamath databases that build on intuitionistic logic <http://us.metamath.org/ileuni/mmil.html http://us.metamath.org/ileuni/mmil.html> and New Foundations <http://us.metamath.org/nfeuni/mmnf.html http://us.metamath.org/nfeuni/mmnf.html> among others. The largest Metamath database by far uses ZFC (Zermelo-Fraenkel Set Theory with the Axiom of Choice). That's the Metamath Proof Exporer (MPE) database: <http://us.metamath.org/mpeuni/mmset.html http://us.metamath.org/mpeuni/mmset.html>. But even in that database, it's avoided where possible. Its conventions say, "We prefer proofs that depend on fewer and/or weaker axioms, even if the proofs are longer. In particular, we prefer proofs that do not use the axiom of choice where such proofs can be found. The axiom of choice is widely accepted, and ZFC is the most commonly-accepted fundamental set of axioms for mathematics. However, there have been and still are some lingering controversies about the Axiom of Choice. Therefore, where a proof does not require the axiom of choice, we prefer that proof instead. E.g., our proof of the Schroeder-Bernstein Theorem (sbth) does not use the axiom of choice. In some cases, the weaker axiom of countable choice (ax-cc) or axiom of dependent choice (ax-dc) can be used instead." <http://us.metamath.org/mpeuni/conventions.html http://us.metamath.org/mpeuni/conventions.html>
- dkarl 5y agoThe article leans pretty hard on the hat problem to show that the Axiom of Choice has intuitively unacceptable consequences, but I don't see why the solution is so "ridiculous," as they put it. Here's one "intuitive" way of looking at the problem: every person in the line sees an infinite number of hats in front of them, but not the finite number behind them. Intuitively, they see 100% of the information in the problem. The amount of information each of them can see is infinite, and the amount they can't see is finite. Is it so strange then that they only make a finite number of wrong guesses, and an infinite number of correct ones? I think the article artfully uses a framing of the problem that hides the inherent, inexorable alienness of infinite sets under a familiar-seeming surface just long enough for it to come bursting out in the solution. It's a trick of timing. If your brain lingers on the problem long enough, you realize that the problem itself violates our ordinary intuitions, independent of the solution. The idea of an infinite number of people agreeing on and memorizing representative members of R^N from each equivalence class and then determining the relevant equivalence class by reading an infinite number of real numbers from an infinite number of hats is completely fantastical. How could any solution to this problem not be nuts? More to the point, if the problem is presented without a bonkers framing that already violates our intuition, is the solution from the Axiom of Choice still counterintuitive? I didn't find it to be so when I first encountered it in class. Maybe the intuitiveness depends entirely on the metaphor used to bring intuition to bear.
- jaydaigle 5y agoI'd agree with this entirely, honestly. (Including the sleight-of-hand I'm engaging in to make things seem exactly the right amount of weird; see footnote 14.) Infinity is so weird that it's really hard to agree on what infinity "should" look like. And the axiom of choice only matters in situations where the weirdness of infinity really kicks in. So yeah, some people look at the whole list of AoC equivalents and think they all seem pretty reasonable. And other people look at the list and think none of them seem that plausible. And a lot of us are split, and find some of the claims obviously true and others obviously false. One of my goals in this piece was to try to let everyone see both sides of this: why you might find the axiom compelling and why you might find it troubling. And then to offer a pragmatic resolution at the end, which is basically another take on what you just said.