10 ms·
My favourite statement of the Axiom of Choice, from AlienAtSystem via https://www.irregularwebcomic.net/4035.html https://www.irregularwebcomic.net/4035.html :
by exmadscientist 5y ago
My 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.