15 ms·
An intutive counterexample to the axiom of choice
- sylware 4y agoIf I recall properly, at the time I was "building maths from the ground up (aka axioms)", I was very uncomfortable with THE axioms: this mixing between discret/finite concepts/objects and infinite concepts/objects was too easy for my taste.
- moron4hire 4y agoA variable name and the thing it points to are not the same thing. Symbols aren't numbers. They are a means to communicate numbers.
- n4r9 4y agoThis has a similar feel to Russell's paradox: Let R be the set of all sets that are not members of themselves. If R is not a member of itself, then its definition entails that it is a member of itself; if it is a member of itself, then it is not a member of itself, since it is the set of all sets that are not members of themselves. https://en.m.wikipedia.org/wiki/Russell's_paradox https://en.m.wikipedia.org/wiki/Russell's_paradox Also the Lowest Uninteresting Number paradox: If there exists a non-empty set of uninteresting natural numbers, there would be a smallest uninteresting number – but the smallest uninteresting number is itself interesting because it is the smallest uninteresting number, https://en.m.wikipedia.org/wiki/Interesting_number_paradox https://en.m.wikipedia.org/wiki/Interesting_number_paradox I suspect that the resolution boils down to what it means to "describe" a number.
- pavlov 4y agoI’m not a mathematician but I wonder why the Lowest Uninteresting Number paradox can’t be resolved by simply adjusting the definition of “interesting”? After all that’s a purely human concept. If we say a number isn’t interesting simply due to its proximity to other interesting numbers, then we can draw the boundary. It seems a bit like making a list of important cities. Borders are very important to countries, but not every border city is economically or historically important. It’s not unreasonable to say that a city must meet other criteria than simply being close to a border.
- mannykannot 4y agoYes... when I first saw this paradox, the author of the article I was reading (maybe Martin Gardner?) pointed out that 'uninteresting' is itself not well-defined.
- tuatoru 4y agoThe set of uninteresting numbers is probably empty.
- kybernetikos 4y agoI think the uninteresting number one can be described without worrying about 'interestingness'. It works out as the same as saying something like the set of numbers that are not the smallest number in any set in some arbitrary collection of sets including this one. It's the 'including this one' part that is causing the trouble, not which other sets are included in the arbitrary collection.
- deleted 4y ago[deleted]
- zaroth 4y agoYou can’t say you can’t chose an item from a set because you can’t describe the item. If it is sufficiently impossible to describe the number, how did it get in the set. Irrational numbers are not impossible to identify symbolically, so if you stuff them in a bag and ask me to pick one, I’ll just take sqrt(2) thanks.
- quchen 4y ago> You can’t say you can’t chose an item from a set because you can’t describe the item. Or rather: the whole point of the axiom is giving you such a description.
- vintermann 4y ago> If it is sufficiently impossible to describe the number, how did it get in the set. It got added along with infinitely many others! That's the thing, it's no problem dealing with "hairy" reals as long as you deal with infinitely many of them at a time. You can say, "all the numbers between zero and one", and the fact that it will include numbers whose decimal expansion can't be described by any rule shouldn't cause any trouble. But if I ask you, "show me one of these numbers whose decimal expansion can't be described by any rule", then by definition, you can't.
- hgsgm 4y agoHow did God create universe? Does your (non) answer imply that Universe doesn't exist?
- heinrichhartman 4y agoThe axiom of choices is about picking elements of infinitely many sets at once. In the example we are talking about a single set. The deduction "the set is non-empty => we can pick an element" is much more basic than AC.
- nhatcher 4y agoYeah, that is not the axiom of choice and even if it were their conclusion is not correct. You can't characterize a set as non being described by finite symbols. On the other hand, it's always refreshing to see someone pushing us to think in this constructs. Logic is hard!
- lheck 4y agoTrue. It's always good to see someone thinking about math concepts in critical ways to understand them. But this post doesn't really have a place here on hacker news as it's just born of faulty premises and of misunderstanding what the Axiom of Choice states. The actual HARD PART about the axiom of choice is that the thing f that picks from the collection of sets to its elements that has to exist must be a function. The axiom of choice does not have any reference to f being "described using any finite collection of symbols", or "computable". f must not be computable or graspable or describable, these are not constraints put onto f by the Axiom of Choice. But it must be a function! Why is "being a function" a constraint for f at all? Not everything that goes from set A to set B is a function. Functions have to be able to be described in terms of sets, and not every collection of items is a set. The notion that every collection is a set is called naive set theory, and it does not work (see Russel's paradox). This is the hard part about the axiom of choice. So if someone invokes some argument over complex concepts about computability, or being stateable, that's not even true of stuff outside of the Axiom of Choice and definitely not why specifically the AoC is hard.
- quchen 4y agoThanks for pointing out that the f must be a function part is particularly difficult. Is this only a problem for infinite sets (of sets to pick from)? Is it trivial to construct a function that picks a single element from an arbitrary set that’s not ordered numbers (say, the real endomorphisms)?
- hackandthink 4y agoI would pick Chaitin's constant. It is not only transcendantal like Pi, it is even uncomputable, so it would be part of his counterexample set. (Pi is computable, so you can describe it with an algorithm (finite number of characters))
- moron4hire 4y agoBut can't Chaitin's constant be described using a finite set of symbols, those symbols being in the set [achinost'] (at least, in English)?
- tromp 4y agoSure; a simple definition is at https://tromp.github.io/cl/Binary_lambda_calculus.html#Halting_probability https://tromp.github.io/cl/Binary_lambda_calculus.html#Halti...
- hackandthink 4y agoOK, original poster doesn't speak about computable numbers: "consider the set of numbers that cannot be described using any finite collection of symbols" But I have a hard time accepting numbers, which can only be described in natural language.
- NotYourLawyer 4y ago> the set of numbers that cannot be described using any finite collection of symbols Not clear that this is a well-defined set.
- deleted 4y ago[deleted]
- hgsgm 4y agoIt's probably not well-defined. https://en.m.wikipedia.org/wiki/Richard's_paradox https://en.m.wikipedia.org/wiki/Richard's_paradox
- jinpa_zangpo 4y agoI believe the definition of this set is contradictory. The set is defined as all numbers that cannot be described with a finite number of symbols. But that set must have a member whose value is closest to zero. So you can describe at least one member of this supposedly indescribable set.
- Slow_Dog 4y ago"the member whose value is closest to zero" is described by those 14 symbols within the speech marks. As you say, the definition is contradictory.
- tsimionescu 4y agoExcept no such member need exist. For example, there is no number that corresponds to the description "the smallest positive real number greater than 0". Edit: note that even "the smallest positive rational number greater than 0" doesn't exist, even though the rationals are merely countably infinite.
- tuatoru 4y agoThis (no smallest positive element of Q) is sensible. But how can you have a procedure that requires making an infinite number of choices?[1] It's not an algorithm; they have to terminate. 1. Wikipedia explanation of the axiom of choice.
- tsimionescu 4y agoI was only pointing out the problem with your argument not arguing that the AoC is necessary or intuitive. Also, algorithms that don't terminate are still algorithms - especially if they keep emitting pieces of a solution, instead of producing the whole solution at the end. For example, here is an algorithm for printing all of the natural numbers: i <- 0 while true: print(i) i <- successor(i) Finally, computability is not typically considered necessary for a mathematical construct to exist or be useful. Just like geometry sometimes studies shapes that can't be constructed in the physical world, other kinds of mathematics sometimes studies concepts that can't be computed (at least not given known models of computation).
- xen0 4y agoThe OP's argument seems to be just that you cannot always construct a choice function. But the entire point of the axiom of choice is to say "that's fine; you're still allowed to use 'unconstructed' choice functions in your proofs". Would the OP reject the statement "let x be an element of the set of numbers that cannot be defined with finitely many symbols"; such a statement does not depend on the AoC, but I think the OP complains about making even a single choice.
- rini17 4y agoHow is that different from claiming, say, there's an integer betwen three and four, oh we can't construct it but that's not a problem, gonna use it in the proofs anyway?
- jbnicolai 4y agoThat's essentially what axioms are. Wether it's reasonable or not depends on your intuition of both axiom & implications. This is where the axiom of choice is interesting; many people feel that it seems intuitively reasonable, but the implications are counterintuitive (e.g. banach-tarski)
- contravariant 4y agoWell an integer between three and four is going to cause some contradictions, depending on your definition of 'integer'. You can assume there exists a number between 3 and 4 though, no problems there.
- jacobmartin 4y agoThis is an interesting question that gets to the heart of the constructivism debate, which I won't touch on here. As for the integer example, the integers are all easily (finitely) constructed (successors to 0 and their additive opposites), so it isn't a consistent concept to say "This is an unconstructable integer." Sets, on the other hand, are not necessarily always constructable, unless you only take the constructivist axioms.
- xigoi 4y ago
- Sankozi 4y ago"consider the set of numbers that cannot be described using any finite collection of symbols" - isn't that set empty? If "numbers" mean "real numbers" then I can describe easily "smallest positive number in the set" and "biggest negative number in the set" - so neither negative, 0 nor positive real numbers might be in the set.
- norrius 4y agoWhat is the "smallest positive number" in the set {x | x in reals and 0 < x < 1}?
- tsimionescu 4y agoIt's trivial to prove that the number you are describing doesn't exist: Let x be the smallest positive real greater than 0. Since x > 0, x/10 < x, and x/10 > 0. But now we have a contradiction, since x was supposed to be the smallest positive real number. So, x doesn't exist. Edit: note that this doesn't even require real numbers. Even for the rational numbers, with common definitions of less-than, there is no smallest positive rational number >0, per the same logic.
- mjburgess 4y agoThe axiom of choice is intuitive because its seems one should always be able to take many aggregates of elements and make a new aggregate. The axiom of choice is counter-intuitive because it provides no reason to, in the case of a uniform aggregate, choose one element over another. Nor a reason to suppose in the case of a "complex aggregate" that "choice" is even well-defined. Perhaps one way of thinking of the issue here is the tension between the discrete and continuous. Of course, one can always recombine even inifnite number of discrete things. But what does it mean to "choose" a "point" on a "line" ? Can one "choose" pi? One could, for example, take the view that the very notion of membership, "choice", etc. is conceptually inadequate for handling geometrical matters such as the reals.
- auggierose 4y ago> Here's how: consider the set of numbers that cannot be described using any finite collection of symbols. Such numbers must exist because there are only a countably infinite number of numbers that can be described using a finite collection of symbols, but there are an uncountably infinite number of real numbers. But there are uncountably many finite collections of symbols. Sorry, you will have to take the axiom of choice out of my dead cold hands. Banach-Tarski just tells us if we use un-measurable sets, they don't have much to do with our understanding of physical space. But that's fine, because sets are just collections, and physical space is undoubtedly more than that.
- sebzim4500 4y ago>But there are uncountably many finite collections of symbols How do you mean? Because there are uncountably many symbols? I'm not really sure what a symbol means in this context.
- auggierose 4y agoI just picked on one of the points in the post that make no sense without further explanation. Just take each real number as a symbol.
- davrosthedalek 4y agoIt's normally assumed that the number of symbols is finite.
- ceceron 4y agoThe number of symbols in the language may countable, but the number of sets of symbols will be indeed uncountable, i.e. AFAIR the number of sets of natural numbers is uncountable — you can even construct real numbers as sets on rational (still countable) numbers.
- deleted 4y ago[deleted]
- jonathanstrange 4y agoI don't think we could talk about numbers that cannot be described by finitely many symbols (let alone a countably infinite number of symbols).
- voldacar 4y agoThe axiom of choice is not really about assigning names to objects using finite strings of symbols. In this example, you take R, remove countably infinitely many elements, and end up with a set with uncountably many elements. From a set theoretic perspective, it is not any more difficult or unintuitive to select an element from this set using AoC than it would be for R. When we use AoC, we are not really assigning a name to anything or doing any computation. We merely claim that a function exists which returns some element from the set. AoC doesn't compute or describe this function.
- horsawlarway 4y ago> We merely claim that a function exists which returns some element from the set. Isn't this where the challenge lies, though? What if you have a set for which there is no function which returns some element from the set, but the set is non-empty?
- drdeca 4y agoFor any set S which is non-empty, there is an element x of that set. For any set S and any x, the set S * {x} is a function which sends every element of S to x. Therefore, for every non-empty set S, there is a function with domain S, and range a single element of S. Did you mean a set S of sets such that there is no f : (A in S) -> A ?
- hgsgm 4y agoIt's only a challenge if you want to actually do it. Mathematicians figured out that it's impossible to actually do, so they decided to pretend it's possible, because nothing else breaks if they just pretend it's possible. Mathematicians like pretending.
- _hark 4y agoThese kinds of non-constructive results are almost always present when you invoke choice (when it's actually relevant), and this is a well-known example of the non-intuitiveness of choice. If you don't like this, you're probably a constructivist and may also disagree with the law of the excluded middle. A classic quote/joke on the topic: "The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?"
- phkahler 4y agoI've always called BS on the math community for this. Let's talk about real numbers between. 0 and 1 (because we can map all of them to this range anyway). I can (count) enumerate all of them. Simply flip the digits over the decimal point, so 0.14159 become integer 95141. Done. Now you ask where pi sits? It's infinitely far down the list of integers. It's position is as precise as your definition. We can extend this to (I forget the terminology) enumerate the numbers that can be named, by converting the names to integers. Now pi has several location in this mapping, as do a lot of real numbers. Infinite sets are interesting, but I've never been convinced that there are more reals than integers. It seems plausible but I don't think pi not mapping to a specific integer in the above scheme invalidates the mapping.
- 101008 4y agoIf you sort this set after you apply your transformation, what's the number that comes right after pi?
- dsr_ 4y agoYou can begin looking for it knowing just two facts: the last digit of pi, and the magnitude of that digit. Easy! [sarcasm]
- phkahler 4y agoThis is all related to the ability to name a specific number. If there are reals that can't be named in a finite number of symbols, why can't there be integers like that as well?
- davrosthedalek 4y agoBecause a property of the numbers we call integers is that we can name them. You can certainly rename some of the numbers which are indescribable and call that set your integers, but these are different integers than what everyone else talks about.
- 4y ago
- boole1854 4y agoThe argument here seems to rely on a natural language intuition, or perhaps even a physical or computational intuition, about what it mean to "choose" something from a collection. However, remember that the axiom of choice is technically a statement about the existence of certain functions, specifically functions that map from any set of non-empty sets to elements of those sets. Whether or not the existence of those functions says something about the possibility of "choosing" is more of a terminological question about how to connect informal natural language to mathematics than it is a substantive mathematical question. Turning to the mathematical question itself, it seems to me that the author's intuitions fare poorly. The author argues that we apparently cannot "choose" an element from a set that contains only numbers that are not finitely describable. But the mathematical question is about the existence of a mapping function, and it seems that whether or not the numbers in each set are finitely describable is irrelevant to this question: Consider the function f(x) = x + 1. This function is defined for all real numbers x. It maps each real number to another real number. Note that the domain of the function includes even those real numbers that are not finitely describable. The meaning of the function itself is nevertheless clear and the function is easy to write down. The fact that the domain of the function includes indescribable numbers is not relevant to the question of whether such a function exists mathematically.
- JackFr 4y agoI'm not sure you've shown anything. f(x) = x + 1 is a mapping from the reals to the reals. A choice function, with respect to the axiom of choice, is a mapping from the set to an element.
- boole1854 4y agoThe point of my example is to show that the functions can exist even if their domain includes "indescribable" numbers. It shows that trivially the "indescribable-ness" of numbers in the domain of the function is not relevant to whether the function exists. The author's argument relies on "indescribable-ness" somehow blocking the ability to "choose" an element. But that trades on a vague, intuitive understanding of "choosing", which doesn't capture what the AC is about. The AC is about the existence of certain functions. Since the "indescribable-ness" of the domain of a function is not relevant to its existence, the author's argument doesn't successfully attack the AC.
- tel 4y agoAC fails to exist, in its normal form, in constructive or intuitionistic formulations of math. This post appeals to that sort of mathematics and thus correctly identifies that it wouldn’t make sense there. There are weaker forms of AC which do exist, though. And formulations of math where AC is necessary and obvious, but doesn’t really imply the same thing as classical AC. But these formulations of math are very unlike the classical one we normally enjoy. For instance, they often disallow the construction of the Reals altogether.
- quchen 4y agoWhy does it fail to exist? It’s an axiom that can be added to intuitionistic axiom systems just as well as for classical ones, no? It’s orthogonal to the law of the excluded middle after all. In constructive mathematics with AC, you would just call the selected set element AC(your-set).
- tel 4y agoIt's been a while so I've forgotten the details, but I believe in some versions of constructive mathematics AC is enough to derive LEM.
- quchen 4y agoOh hey Tel, do I remember you right from #haskell on Freenode? : - D
- tel 4y agoNot on there a ton, but yes!
- throwaway81523 4y agoThat is called Diaconescu's theorem. https://en.wikipedia.org/wiki/Diaconescu%27s_theorem https://en.wikipedia.org/wiki/Diaconescu%27s_theorem
- jerf 4y agoThis is close to why I'm not in love with the Axiom of Choice. I don't hate it, and I don't "mind" it, but I do think mathematicians are perhaps more comfortable with it than they should be. The reason is, I think proofs of the form: 1. A 132 bit (in the information theory sense) definition of something. 2. A 98 bit definition of something else. 3. A 4 bit procedure that puts them together. 4. A 2883 bit object of interest. 5. An uncountably infinite number of bits added to the objects in 3 and 4, with no mechanism for determining any of them even in theory. 6. Therefore, a 76 bit conclusion of interest. is just intrinsically more icky to me than mathematicians in general think. You know, mathematically icky. It's a technical term. There's a step here that sticks out like a sore thumb. Sure, there's a whole lot of fuzziness around measuring the size of a statement in bits, but no matter how you slice it, you're not going to get away from a certain amount of distinction between the statements that are finite, and probably even fairly small in absolute terms, versus the invocation of infinite numbers of bits of information. (Note that having a decision procedure to determine something, e.g., "here's the set of the primes", is a finite number of bits, and in fact, not even a very large number of them. The set of the primes is completely computable. It may not be "efficiently" computable but it completely computable. It's not just "infinite sets" in general that cause the issue I complain about in general. The axiom of choice specifically invokes infinite numbers of bits, if not uncountably infinite numbers of bits, out of the ether.) Now, does that make it "invalid"? No. As the article says, it's an axiom, it is what it is. And I don't go to the extreme of tossing it out and completely going to the belief that constructivism is the only valid mathematics. I just am nowhere near as comfortable with it as mathematicians in general are.
- karpierz 4y agoWhere is infinite information invoked?
- jerf 4y agoThe Axiom of Choice is that I can have an infinite number of sets and I can "choose" a value from each of them. A choice from a set is basically what a bit is (give or take the question of probabilistic weighting of the values in the set, which is important in the finite case but can't save you in this case so it's a distraction here). Invoking the Axiom of Choice, which is only interesting in the infinite case, is injecting an infinite number of bits into the proof that uses it, as it involves an infinite number of choices. At best the invocation has an acceptance procedure, but it does not come with a procedure for making the choice. Probably in most cases it doesn't even have an acceptance procedure, which is to say, if we were presented with the choices (or a finite subset of them, since we can't handle the infinite set) we couldn't even tell if they are "correct". So it is not the case that it's just like the primes case, which I mentioned is distinctly finite in bits even if the set is infinite in cardinality. The Axiom of Choice is an infinite (even uncountably infinite or more) number of selections with no way given of representing that in any finite manner. In many cases the Axiom of Choice is invoked when we can't even define the sets we are choosing from, if not most or all of them. So, from my computer science, information theory point of view, proofs involving the Axiom of Choice are proceeding along nicely, finite statement here, finite statement there, finite logic done on these finite statements, everything's all nice and finite and comprehensible and then BANG an infinite number of unknownable bits are dumped on me, and then we proceed along like nothing weird has happened and do some more finite logic on finite values based on this infinite pile of unknownable bits. It is what it is, but what it is is strange. I mean, it's not news to mathematicians that it can be a bit strange, but I think this "infinite number of bits" is one of the better ways to see how strange it is. Another way to look at it is, the AoC is generally invoked without even a theoretical decision procedure to make the choices. It just has a demonstration that such a choice exists. So it amounts to "and then god chooses a value in these sets for us in accordance to our criteria". Lowercase on purpose. A more conventional term in computer science is "oracle". Every invocation of the AoC is basically adding this mathematical entity of such incredible power that we can't determine anything about how it does its thing, or whether or not it is correct. Again. Legal. But something I think is taken more casually than I would like, and I think doing mathematics without scattering infinitely knowledgeable (if only in very constrained ways) and powerful oracles around everywhere with the same casualness as one might do a disjunction or implication in all our proofs is underrespected as a discipline within mathematics in general.
- bell-cot 4y agoReaction: "Intuition" works about as well with the Axiom of Choice as it does with brain surgery, nuclear physics, and rocket science.
- rtpg 4y agosince everyone here is bike shedding about the axiom of choice... I have this axiom of choice book (by Thomas Jech). It includes the following: > if F is a finite family of nonempty sets, then there is a choice function (to show this one uses induction on the size of F; naturally a choice function exists for a family which consists of a single nonempty set). could someone lay out how one would "correctly" describe a choice function for a family with a single nonempty set? I feel like I understand theoretically this idea that choosing isn't about providing the value, but some... logical instantiation? What is the piece of the puzzle I'm missing here to understand why the choice function exists "naturally"?
- quchen 4y agoGood question, I’m confused about this as well! Take for example the single-element set containing the set of ℝ→ℝ functions, so { {f | f: ℝ→ℝ} }. The author seems to suggest there’s a natural choice for those functions. To me this sounds as hard as choosing from a larger set-of-sets.
- housecarpenter 4y agoI don't think Jech is using "naturally" as in "natural choice"; he's just using it as a synonym for "obviously". If X is non-empty set then there exists an x in X, because that's what it means for X to be non-empty. The choice is arbitrary: if X is the set of all functions from R to R then you could take the exponential function, the x^2 function, etc., whatever you like; the point is that it is certainly possible to make some choice. Doubting the axiom of choice means thinking that when you have infinitely many sets to choose from, it is possible that not only is there is no natural choice function, but there is no choice function at all.
- rtpg 4y agoBut why do we need the axiom of choice at all? By this logic I have any family of non-empty sets then I’m good? But surely there’s a distinction here
- wizeman 4y agoPerhaps we should start admitting to ourselves that infinity is not really something that actually exists but instead it's just an imaginary concept that we created but that has no correspondence to anything that makes sense in our universe? Or at least, some versions of infinity (I will leave which ones, exactly, to the experts). Hence all the paradoxes that derive from it. I mean, perhaps we can work with some version(s) of infinity, without creating a plethora of paradoxes. The natural numbers, for example, might be something that is infinite and makes sense. However, perhaps talking about a single set that contains an infinite amount of natural numbers might not make sense (or perhaps it still might?). Or perhaps we just need a new language for talking about infinite things without re-using the language we use for describing (finite) sets, so that we don't try to reuse concepts from finite objects with infinite objects. Or perhaps the only objects that exist (and can be meaningfully talked about) are the computable ones. And/or perhaps "computable function" is one that can use infinite amounts of time but only finite amounts of storage (rather than infinite amounts of storage). Would it make sense to go back to classical finitism and re-evaluate some of the choices that were made along the way to where we are now? I can't help but think about the many paradoxes that arise from the very (supposed) existence of infinity. For example, everybody thinks the halting problem is undecidable. The halting problem is clearly not undecidable on finite-state machines (i.e. real computers), it's only undecidable if you use imaginary Turing machines (which supposedly can have literally infinite state) as a model. But of course, Turing machines cannot exist in our universe. So it's rather ironic that people say the Halting problem is undecidable, when this is only true for (impossible to construct) imaginary machines but it's not true for the real machines that we actually have and that are possible to construct. Or think about Hilbert's paradox of the Grand Hotel. Or the Banach-Tarski paradox. Or Galileo's paradox. Or other such paradoxes that only exist if you believe that imaginary infinite objects could possibly exist. Most people will tell you "well, it's just that our intuition doesn't work for infinite things", but in this specific instance, it's really hard for me to believe that it's our intuitions that are mistaken rather than that we actually made some conceptual mistakes along the way. To me, this argument sounds more like gaslighting rather than a real convincing argument. I'm not saying our intuition is always correct, though. For example, the quantum properties of our universe are clearly not intuitive but it's hard to argue that our universe is not quantum, after all the scientific experiments that have clearly verified this to be true. I don't think that invalidates my argument, though, because the convincing argument in that case is not "sorry, you must believe my theory that the universe is quantum" despite not existing any evidence that this was true, but rather, "sorry, but here's all this real evidence that our universe truly is quantum". Am I crazy here?
- huitzitziltzin 4y agoThis part: > Here's how: consider the set of numbers that cannot be described using any finite collection of symbols. Such numbers must exist *because there are only a countably infinite number of numbers that can be described using a finite collection of symbols*, but there are an uncountably infinite number of real numbers. That’s clearly wrong. The real numbers between 0 and 1 (an uncountable collection) are describable with a finite collection of symbols - the digits between 0 and 9. Each real number is an equivalence class of sequences with the same limit. (It’s been a while since I took real analysis but I believe this is the construction due to Weierstrass?)
- danbruc 4y agoThe author means finite sequence over finite alphabet, i.e. the finite collection of symbols does not refer to the alphabet.
- deleted 4y ago[deleted]
- johnnny 4y agoThe set of numbers that can be written with a finite number of 0-9 digits is countable. That set is called the decimal numbers, and is a subset of the rational numbers which itself is countable too.
- huitzitziltzin 4y agoThe set of numbers which can be written with finitely many members of a finite set of symbols is countable, sure. That doesn’t sound like the claim the author is making in the sentence I quoted but maybe I am being uncharitable?
- johnnny 4y agoIf you allow infinitely long descriptions, then I don't know what's the score. In the case of "descriptions" that amount to (potentially infinite) decimal expansions, I think an argument akin to Cantor's diagonal will show that you can't possibly describe all real numbers (or all numbers between 0 and 1), but I'm not confident I can assert this to be true.
- tomp 4y agoThis is not intuitive at all. I have a masters in math. Concrete numbers are irrelevant to me, and their explicit representation is even less relevant. Any number can easily be described by x. Btw this is just the standard reason for the existence of the Axiom of Choice. If there exists a procedure to describe which number to choose (i.e. an algorithm/formula), you don't need AC at all. IMO the only "intuitive" anti-AC argument is, that you can get most of math with Axiom of Countable Choice, while you avoid paradoxes like Banach-Tarski.
- davrosthedalek 4y agoQuestion: While the standard construction of the set for Banach-Tarski requires AOC, is it proven that without AOC, Banach-Tarksi isn't true?
- tomp 4y agoNot sure, but if you replace AC with a weaker axiom, Axiom of Dependent Choice, you can construct a model in which all subsets of reals are measurable (called the Solovay model), which precludes the Banach-Tarski paradox (which requires non-measurable sets). Could BT be constructed without AC but with other way of ensuring there exist non-measurable sets? No idea.
- throwaway81523 4y agoBy "without AC" I think you mean "with the negation of AC". It turns out that BT+ZF is equivalent to ZF + a weaker version of AC called the Ultrafilter Lemma, iirc. There is more info in the Wikipedia article about BT. Also, the Hahn-Banach theorem (plus ZF) proves BT.
- Kranar 4y agoDepends what you mean by without AOC. If you just mean whether Banach-Tarski can be proven in ZF the answer is no. But you also don't need the full power of AOC to prove Banach-Tarski.
- lisper 4y ago> If there exists a procedure to describe which number to choose (i.e. an algorithm/formula), you don't need AC at all. The problem here is not that there does not exist a procedure to describe which number to choose, the problem is that there does not exist any way to describe which number you chose. Those are not the same thing.
- otikik 4y agoYou can say: “The first number that can’t be described using a finite number of symbols” But then you have just used a finite number of symbols to describe it, haven’t you?
- karpierz 4y agoThis assumes your numbers are well ordered (IE, any set of numbers has a "first"), which is called Zorn's Lemma. It's equivalent to the axiom of choice.
- WastingMyTime89 4y agoYou can't say that unambiguously, no. You haven't defined a well order which would allow you to talk about a first element (well, smallest).
- psychoslave 4y agoSaying something doesn’t imply saying something about a denotable entity.
- deleted 4y ago[deleted]
- orlp 4y ago> Such numbers must exist because there are only a countably infinite number of numbers that can be described using a finite collection of symbols, but there are an uncountably infinite number of real numbers. So not only are there numbers that cannot be described using a finite number of symbols, there are vastly more of these than numbers that can be so described. Why is almost no one more critical of this? A 'number' you can't describe or do computation with? Why do we still call this a number? If I ask Google to define number I get > an arithmetical value, expressed by a word, symbol, or figure, representing a particular quantity and used in counting and making calculations. Almost all (in the mathematical sense) 'real' 'numbers' can not be expressed, nor can be used for counting or making calculations. Over the years I'm becoming more and more convinced we should reject the 'real' numbers as our default mathematical object for numbers, and switch to a basis that has a computable foundation. There is some work being done in this area, but not nearly enough in my opinion: https://en.wikipedia.org/wiki/Computable_number#Use_in_place_of_the_reals https://en.wikipedia.org/wiki/Computable_number#Use_in_place...
- dia80 4y agoYou are going to love this: How real are real numbers? https://arxiv.org/abs/math/0411418 https://arxiv.org/abs/math/0411418
- deleted 4y ago[deleted]
- mik1998 4y agoReal numbers are interesting and math is not about computation, counting or calculation.
- hgsgm 4y agomath is not only about computation, counting or calculation.
- hgsgm 4y agoMathematicians hijacked numbers. Computer scientist don't accept noncomputable objects. Mathematicians do. To a scientist, existence means "you, or someone, can find it, at least potentially". To a non-constructive mathematician (the common kind) existence means "you can't prove it doesn't exist, and I choose to believe it does, at least in the current game I am playing." Mathematicians use the term "real numbers" to describe precisely the set of numbers you get when you take all the numbers that could plausibly be computed, and then declare that all the holes between numbers we can individually compute/describe are completely full of numbers. This is justified because you can't prove that any specific one of them is impossible to write. (But there are some so called "real" numbers that are impossible to calculate, even approximately, like Chaitin's constant https://en.m.wikipedia.org/wiki/Chaitin%27s_constant https://en.m.wikipedia.org/wiki/Chaitin%27s_constant but you could write it in infinite time if God told you the digits.)
- renewiltord 4y agoThis doesn't make sense. That's not what AoC means. It is a statement that the cartesian product is non-empty if the sets are non-empty. One might as well say "Well, if I were to lobotomize you, you would not be able to choose". The "choice" here is a term of art. There is no actual "choosing" going on here.
- psychoslave 4y agoNaming is not a requirement to selecting. I can pick a tool, and even use a tool, without having to name it. Most selection process out there work without relying on any explicit name. In the theory of natural selection for example, specimens are selected without being named.
- bannedbybros 4y ago[dead]
- Chinjut 4y agoAs others have noted, this has little to do with the Axiom of Choice per se. The Axiom of Choice is not needed to prove that one can make a choice from a single inhabited set, where this boils down to the tautology "If a set has at least one element, then it has at least one element". The Axiom of Choice is only needed for making infinitely many choices at once. (There IS a sense in which what is going on here is the distinction between what category theorists call "internal" and "external" Choice, but I'll not get into that for now since I think the following is more important to point out first.) The result/paradox here has more to do with Tarski's indefinability theorem, under which no suitable formal language is able to define the concept of definability in that same language. See also https://mathoverflow.net/a/44129/3902 https://mathoverflow.net/a/44129/3902 for more discussion on what goes wrong in attempting to formally prove that "undefinable" numbers exist by this common but naive argument from uncountability. The gist of the above MathOverflow link and of Tarski's indefinability theorem is that we must keep in mind that Cantor's famed diagonal argument for uncountability is a constructive argument. Given any function from N to 2^N, it defines an explicit element of 2^N not in the range of that function. So there would be something paradoxical in concluding that this explicitly defined value is not definable.
- IngoBlechschmid 4y agoYou do not need to worry about the axiom of choice because: (1) Provably so in a very weak (and hence trustworthy) metatheory, assuming the axiom of choice does not result in any new inconsistencies. More precisely: The systems ZFC (Zermelo–Fraenkel set theory with the axiom of choice) and ZF (ZFC but without choice) are equiconsistent; if ZF is consistent, then so is ZFC. (2) There is a mechanical procedure for transforming ZFC-proofs of number-theoretic statements into ZF-proofs. That is, appeals to the axiom of choice can always be mechanically eliminated from proofs of number-theoretic statements, even if those proofs rely on results in other areas which crucially depend on the axiom of choice. You should worry about the axiom of choice because: (3) Assuming the axiom of choice imposes an undue restriction on the scope of your results: Any theorem proven without the axiom of choice and without the law of excluded middle (which is implied by the axiom of choice) automatically also applies to continuous families. For instance, the theorem "every real symmetric matrix has an eigenvalue" has a proof avoiding AC and LEM. Hence it also holds that for every continuous family of symmetric matrices, locally on the parameter space, there is a continuous eigenvalue-picking function. PS: One could also wonder whether one should worry about the law of excluded middle. One should not because: (1') The systems ZF and IZF (ZF but without LEM) are equiconsistent. (2') There is a mechanical procedure for transforming ZF-proofs of number-theoretic statements of the special kind "for every numer x, there exists a number y such that some equation holds" into IZF-proofs. On the other hand, one should worry because of (3). PPS: The axiom which one should truly worry about is the inconspicuous powerset axiom. In contrast with ZFC, ZF and IZF, which are all equiconsistent, removing the powerset axiom results in a drastically weaker system. The proof-theoretic strength of Kripke–Platek set theory (ZF without powerset) is a reasonably large ordinal, whereas we are lacking the technology to even fathom the ordinal calibrating the strength of IZF/ZF/ZFC.
- hackandthink 4y agoI am confused: "From a proof-theoretic perspective, Heyting’s calculus is a restriction of classical logic in which the law of excluded middle and double negation elimination have been removed" (1) "Intuitionistic logic can be understood as a weakening of classical logic, meaning that it is more conservative in what it allows a reasoner to infer" (1) How is this compatible with: "The systems ZF and IZF (ZF but without LEM) are equiconsistent." ? (1) https://en.wikipedia.org/wiki/Intuitionistic_logic https://en.wikipedia.org/wiki/Intuitionistic_logic Seems to be quite subtle (proof theoretic strength and consistency strength) (2) https://mathoverflow.net/questions/126002/interpretability-and-consistency-strength https://mathoverflow.net/questions/126002/interpretability-a...
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- deleted 4y ago[deleted]
- bmitc 4y agoThe axiom of choice is not a definition or theorem or problem. It is an axiom. You either take it or leave it.
- tshaddox 4y ago> Here's how: consider the set of numbers that cannot be described using any finite collection of symbols. Such numbers must exist because there are only a countably infinite number of numbers that can be described using a finite collection of symbols, but there are an uncountably infinite number of real numbers. But wait. It’s true that there are only countably many “symbolic descriptions,” and uncountably many real numbers, but it doesn’t follow that there are specific real numbers which cannot be described using a finite collection of symbols, does it? You can, of course, have a computer algebra system that includes a symbol for a non-computable number like a Chaitin constant (with a well-defined encoding). Wouldn’t it be the case that you could define symbols for any countably infinite set of non-computable numbers? It doesn’t seem to me that there is a fixed set of specific non-computable numbers that cannot be referred to by a symbol. Instead, it’s just that any particular countably infinite set of symbols can only refer to a countably infinite set of non-computable numbers.
- rcme 4y ago> But wait. It’s true that there are only countably many “symbolic descriptions,” and uncountably many real numbers, but it doesn’t follow that there are specific real numbers which cannot be described using a finite collection of symbols, does it? It does follow because the set of finite collections of symbols is countable.
- tshaddox 4y agoI'm not sure what you mean, because you just repeated the first part of my sentence. The fact that one set is countable and the other is uncountable doesn't mean there are specific, fixed numbers in the uncountable set which cannot be paired with any element in the first set. Consider the usual example of the natural numbers (countable) and the reals (uncountable). It doesn't follow that there is some specific, fixed real number which cannot be part of a bijection of the naturals and the reals. Name any real number and I can give you a bijection of the naturals and the reals which contains your real number.
- rcme 4y ago
- mannykannot 4y agoI suspect this posting might have been prompted by the recent one of Colin Wright's "The Point of the Banach-Tarski Theorem."[1] Regardless, Colin has also written about the axiom of choice, in "In Defense Of The Axiom Of Choice"[2] and "A Point Against The Axiom Of Choice."[3] [1] https://www.solipsys.co.uk/new/ThePointOfTheBanachTarskiTheorem.html https://www.solipsys.co.uk/new/ThePointOfTheBanachTarskiTheo... https://news.ycombinator.com/item?id=34482226 https://news.ycombinator.com/item?id=34482226 [2] https://www.solipsys.co.uk/new/InDefenseOfTheAxiomOfChoice.html https://www.solipsys.co.uk/new/InDefenseOfTheAxiomOfChoice.h... [3] https://www.solipsys.co.uk/new/APointAgainstTheAxiomOfChoice.html https://www.solipsys.co.uk/new/APointAgainstTheAxiomOfChoice...
- raldi 4y agoEven more intuitive: What's the first positive real number? If you can't tell me that, or even be sure that it even exists, how can you be sure you can identify the first item in any set?
- malaya_zemlya 4y agoA slightly more elaborate setup which showcases the weirdness of the Axiom of Choice. Consider a group of countably infinite wizards w_1, w_2,... A king has put a number 0 or 1 on their backs and ordered the wizards to stand in a single file, such that wizard w_n can only see the numbers on the backs of all wizards with higher numbers (w_n+1, w_n+2...). As is the tradition, the king gave them a challenge: if you can guess the number on your back, your life is spared, otherwise off with your head. The wizards can discuss their actions beforehand, but no communications is allowed after the numbers have been assigned. The wizards cannot see their own numbers, they cannot exchange information, yet, if we assume the Axiom of Choice, they still can work out a strategy, such that all but a finite number of wizards survive. The trick is to break the space of all 0-1 sequences into equivalence classes, whre X is equivalent to Y if they disagree only in finite number places. (in other words, they fully agree starting from some index k). That's an equivalence relation, as you can easily verify. Then the wizards use the Axiom of Choice to remember one representative sequence from each class (there are infinitely many such sequences, but our wizards are infinitely wise). During the test, each wizard would look at what numbers they see in front of them, pick the representative sequence that is equivalent to what they are seeing, and guess the number that corresponds to their place in the sequence. All wizards will agree on what representative sequence will need to be picked (because the king's sequence belongs to a single equivalence class), and that sequence will agree with the king's sequence everywhere except for a finite number of places. Boom!
- voldacar 4y ago>Then the wizards use the Axiom of Choice to remember one representative sequence from each class I don't think AoC is enough here becuase the wizards need to evaluate the choice function to get the representative from each equivalence class. AoC merely states that there is some function that maps each equivalence class to some element within that equivalence class. It doesn't tell you how to actually evaluate it, which is what the wizards need to do.
- CaptainNegative 4y agoWhat's the role of restricting the number domain to binary here? Can't they each have a real-valued number on their back (or worse, something from a larger set) with the same argument still going through?
- deleted 4y ago[deleted]
- Aardwolf 4y agoBut even if you have the set of all reals not describable with a finite amount of symbols, I can still imagine what happens e.g. if you multiply all its values by 2, or what the cartesian product of this set with another is like. At least, I can reason sbout that result in a way that's not worse than reasoning about the set itself. Using axiom of choice on it does not make things harder than the set itself already is
- hgsgm 4y agoAoC lets you ignore how bad the set it. Banach-Tarski says: Take a measurable set. Split it up into 2 unmeasurable sets. Recombine them into a set with twice the measure of the original. OK, you can do that, but you've lost the ability to make any reasonable theorems about measure of measurable sets, unless you add qualifications of the form "this theorem does not apply if you introduce a set of uncountable sets" which. What's the benefit? To get a bunch of "proofs" for things that are only true because of the axiom, and don't model anything else we care about?
- dang 4y agoThe thread this post is continuing: https://news.ycombinator.com/item?id=34484011 https://news.ycombinator.com/item?id=34484011
- cousin_it 4y ago> consider the set of numbers that cannot be described using any finite collection of symbols. Such numbers must exist because there are only a countably infinite number of numbers that can be described using a finite collection of symbols, but there are an uncountably infinite number of real numbers. So not only are there numbers that cannot be described using a finite number of symbols, there are vastly more of these than numbers that can be so described. Maybe you already know, but this argument is wrong, see Hamkins "Pointwise definable models of set theory". It's a triple whammy: 1) You can't state the argument formally, because the property of describability is undefinable (Tarski's undefinability of truth). 2) Whatever your theory claims about uncountability, from the outside there's always a countable model of it (Lowenheim-Skolem). 3) And if you have a countable model, there's nothing stopping you from having a finite formula for every member of it (making it a "pointwise definable model"). All the details are worked out in the paper: yes Virginia, there are models of ZFC whose every member - every set, every function, every real number - is definable by a finite formula. Also a lot of nice counterexamples in this reddit thread: https://www.reddit.com/r/math/comments/d9sp9h/the_math_tea_argument_there_must_exist_real/ https://www.reddit.com/r/math/comments/d9sp9h/the_math_tea_a... For example: > "Take your favorite real in some model M. We can take a forcing extension to a model M[G] in which the real is coded in the continuum function below aleph_omega. Now it's definable." Or: > "There is a computable real that ZFC doesn't prove is a computable real."
- CamperBob2 4y agoAn object exists prior to being named. If the act of naming (or "counting") the object is all it takes to move it to a different set, then the paradox vanishes, no? What does it even mean to refer to a "set" of named/unnamed objects or counted/uncounted numbers?
- deleted 4y ago[deleted]
- thehappypm 4y agoDoesn’t this simply create a contradiction? Call the set S. In this set, call the first element S_0. You’ve now described the first element with a finite number of symbols!
- schemester 4y agoThe sets {x+n : n in Z} where x in R are almost entirely sets comprised of only noncomputable elements. We don’t even need AoC to choose an element from each: pick the smallest positive element (the element in (0,1]). There is nothing special about noncomputable set elements.