5 ms·

As the author points out that Banach-Tarski theorem is an example of hard-to-accept result that comes out of the easy-to-accept axiom of choice. There is a pop

As the author points out that Banach-Tarski theorem is an example of hard-to-accept result that comes out of the easy-to-accept axiom of choice. There is a popular quote that related to this: > The axiom of choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma? From https://en.wikipedia.org/wiki/Axiom_of_choice https://en.wikipedia.org/wiki/Axiom_of_choice Axiom of choice, the well-ordering principle and Zorn's lemma are equivalent statements (any one proves the other two). But each has a very different "believability" feel to it.

jiggawatts 4y ago
The Axiom of choice has never felt completely self-evident to me. E.g.: what if you have sets where the elements are non-computable? How do you "choose" objects that cannot even be named? Something like: "the set of all programs that cannot be proven to halt" and the like can be used to create pathological sets where the set itself obviously exists, but you cannot name any of the members. Actually, an ever better example is: "The set of reals that are not the solution to any equation that can be written with a finite number of symbols." -- an infinite set that has no nameable members!
- H8crilA 4y ago
  I think your second set doesn't exist (exactly like the set of all sets doesn't exist) under the axiom of choice, for I can use the axiom of choice to select an element, hence giving it a name :). I took some liberty with the allowable names, of course. You still have a point, though.
- soVeryTired 4y ago
  Those are just subsets of R though (though I think your last example would take more work to make rigorous, if it's even possible). The weirdness of the axiom of choice only really comes through when you consider bigger and bigger collections of sets. For example: - sets indexed by the natural numbers: S_1, S_2, ... It seems totally reasonable that you should be able to make a new set by picking something from the first set, something from the second set, etc - sets indexed by continuous time (i.e. real numbers). Here it's a bit less 'obvious'. If I have sets S_t for _every_ time t > 0, can I really make choices 'fast' enough? What if the sets are so unstructured that I'm forced to stop and look at each set in turn to make my choice? - sets indexed by the power set of the real numbers. If you weren't convinced that I'd struggle to pick elements of S_t for all t > 0, what if I had to make a choice for every _possible combination_ of real numbers, infinite or otherwise? I feel like the last example demonstrates how powerful the full axiom of choice actually is. NB - I'm a dilettante rather than an actual logician, so there may be mathematical inaccuracies here.
  - lmm 4y ago
    > Those are just subsets of R though (though I think your last example would take more work to make rigorous, if it's even possible). You could form e.g. the non-algebraic reals, which is almost all of the reals. > sets indexed by the power set of the real numbers. If you weren't convinced that I'd struggle to pick elements of S_t for all t > 0, what if I had to make a choice for every _possible combination_ of real numbers, infinite or otherwise? To the extent to which you can form that indexed collection of sets in the first place, surely you can form a similarly indexed collection of elements of them the same way. How can you say you've formed a non-empty set if you can't select an element of it? If we permit ourselves to form this indexed collection "lazily", surely we can do the choice "lazily" as well. (Just my intuition about these things)
- thaumasiotes 4y ago
  > Actually, an ever better example is: "The set of reals that are not the solution to any equation that can be written with a finite number of symbols." -- an infinite set that has no nameable members! That's not a good example; the problem you're creating is due to sloppy use of language, not any cleverness in the definition. All real numbers, and all numbers of any other variety, can be written with a finite number of symbols. That's what it means to give something a name.
  - theemathas 4y ago
    > All real numbers, and all numbers of any other variety, can be written with a finite number of symbols. This is false. In some sense, there exist numbers that can't be referred to. We can refer to the set of real numbers as a whole, but not some of the elements. https://en.wikipedia.org/wiki/Definable_real_number https://en.wikipedia.org/wiki/Definable_real_number But then there are issues with defining "definable numbers", which complicates things by a lot. https://mathoverflow.net/questions/44102/is-the-analysis-as-taught-in-universities-in-fact-the-analysis-of-definable-numb/44129#44129 https://mathoverflow.net/questions/44102/is-the-analysis-as-...
    - kgwgk 4y ago
      Apparently by “finite number of symbols” he means, for example, {0 1 2 3 4 5 6 7 8 9 .} but he allows the representation of a number to contain infinitely many of them.
  - jiggawatts 4y ago
    > All real numbers, and all numbers of any other variety, can be written with a finite number of symbols. That's what it means to give something a name. Counter-intuitively, this is not true. The vast, vast majority of real numbers cannot be named, not even in principle. Their definitions would have to be infinitely long. Or to put it another way, no matter how close two named numbers are, there is an infinite number of reals in between them. If you say, okay, sure, but some of those might be named, then pick the two closest and then there is still an infinite number of other reals in between those two! Another way to look at it is that the amount of information (measured in bits) between any two real numbers is literally infinite. If the reals were represented with binary digits, then a sequential subset of them would have a common finite prefix, and then all possible infinite bit strings would be the suffixes!
- theemathas 4y ago
  An alternative formulation of the axiom of choice: The cartesian product of a collection of non-empty sets is non-empty.
  - deleted 4y ago
    [deleted]
- lisper 4y ago
  > the set of all programs that cannot be proven to halt That's easy: pick the TM which is minimal according to some lexicographic ordering on the specification of TM's. That's not computable (obviously) but it's perfectly well defined. > The set of reals that are not the solution to any equation that can be written with a finite number of symbols Yeah, that one is harder :-) (I would simply say "The set of numbers that cannot be described by any finite number of symbols" in order to short-circuit arguments about what constitutes an "equation" and whether or not Chaitin's constant is the solution to some equation.)
- bmitc 4y ago
  It sounds like you're adding an additional constraint though. By requesting all the members of each set to be able to be named, it seems like you're restricting the sets to be countable. > E.g.: what if you have sets where the elements are non-computable? That includes the unmodified real numbers.

jiggawatts 4y ago

The Axiom of choice has never felt completely self-evident to me. E.g.: what if you have sets where the elements are non-computable? How do you "choose" objects that cannot even be named? Something like: "the set of all programs that cannot be proven to halt" and the like can be used to create pathological sets where the set itself obviously exists, but you cannot name any of the members. Actually, an ever better example is: "The set of reals that are not the solution to any equation that can be written with a finite number of symbols." -- an infinite set that has no nameable members!

H8crilA 4y ago
I think your second set doesn't exist (exactly like the set of all sets doesn't exist) under the axiom of choice, for I can use the axiom of choice to select an element, hence giving it a name :). I took some liberty with the allowable names, of course. You still have a point, though.
soVeryTired 4y ago
Those are just subsets of R though (though I think your last example would take more work to make rigorous, if it's even possible). The weirdness of the axiom of choice only really comes through when you consider bigger and bigger collections of sets. For example: - sets indexed by the natural numbers: S_1, S_2, ... It seems totally reasonable that you should be able to make a new set by picking something from the first set, something from the second set, etc - sets indexed by continuous time (i.e. real numbers). Here it's a bit less 'obvious'. If I have sets S_t for _every_ time t > 0, can I really make choices 'fast' enough? What if the sets are so unstructured that I'm forced to stop and look at each set in turn to make my choice? - sets indexed by the power set of the real numbers. If you weren't convinced that I'd struggle to pick elements of S_t for all t > 0, what if I had to make a choice for every _possible combination_ of real numbers, infinite or otherwise? I feel like the last example demonstrates how powerful the full axiom of choice actually is. NB - I'm a dilettante rather than an actual logician, so there may be mathematical inaccuracies here.
- lmm 4y ago
  > Those are just subsets of R though (though I think your last example would take more work to make rigorous, if it's even possible). You could form e.g. the non-algebraic reals, which is almost all of the reals. > sets indexed by the power set of the real numbers. If you weren't convinced that I'd struggle to pick elements of S_t for all t > 0, what if I had to make a choice for every _possible combination_ of real numbers, infinite or otherwise? To the extent to which you can form that indexed collection of sets in the first place, surely you can form a similarly indexed collection of elements of them the same way. How can you say you've formed a non-empty set if you can't select an element of it? If we permit ourselves to form this indexed collection "lazily", surely we can do the choice "lazily" as well. (Just my intuition about these things)
thaumasiotes 4y ago
> Actually, an ever better example is: "The set of reals that are not the solution to any equation that can be written with a finite number of symbols." -- an infinite set that has no nameable members! That's not a good example; the problem you're creating is due to sloppy use of language, not any cleverness in the definition. All real numbers, and all numbers of any other variety, can be written with a finite number of symbols. That's what it means to give something a name.
- theemathas 4y ago
  > All real numbers, and all numbers of any other variety, can be written with a finite number of symbols. This is false. In some sense, there exist numbers that can't be referred to. We can refer to the set of real numbers as a whole, but not some of the elements. https://en.wikipedia.org/wiki/Definable_real_number https://en.wikipedia.org/wiki/Definable_real_number But then there are issues with defining "definable numbers", which complicates things by a lot. https://mathoverflow.net/questions/44102/is-the-analysis-as-taught-in-universities-in-fact-the-analysis-of-definable-numb/44129#44129 https://mathoverflow.net/questions/44102/is-the-analysis-as-...
  - kgwgk 4y ago
    Apparently by “finite number of symbols” he means, for example, {0 1 2 3 4 5 6 7 8 9 .} but he allows the representation of a number to contain infinitely many of them.
- jiggawatts 4y ago
  > All real numbers, and all numbers of any other variety, can be written with a finite number of symbols. That's what it means to give something a name. Counter-intuitively, this is not true. The vast, vast majority of real numbers cannot be named, not even in principle. Their definitions would have to be infinitely long. Or to put it another way, no matter how close two named numbers are, there is an infinite number of reals in between them. If you say, okay, sure, but some of those might be named, then pick the two closest and then there is still an infinite number of other reals in between those two! Another way to look at it is that the amount of information (measured in bits) between any two real numbers is literally infinite. If the reals were represented with binary digits, then a sequential subset of them would have a common finite prefix, and then all possible infinite bit strings would be the suffixes!
theemathas 4y ago
An alternative formulation of the axiom of choice: The cartesian product of a collection of non-empty sets is non-empty.
- deleted 4y ago
  [deleted]
lisper 4y ago
> the set of all programs that cannot be proven to halt That's easy: pick the TM which is minimal according to some lexicographic ordering on the specification of TM's. That's not computable (obviously) but it's perfectly well defined. > The set of reals that are not the solution to any equation that can be written with a finite number of symbols Yeah, that one is harder :-) (I would simply say "The set of numbers that cannot be described by any finite number of symbols" in order to short-circuit arguments about what constitutes an "equation" and whether or not Chaitin's constant is the solution to some equation.)
bmitc 4y ago
It sounds like you're adding an additional constraint though. By requesting all the members of each set to be able to be named, it seems like you're restricting the sets to be countable. > E.g.: what if you have sets where the elements are non-computable? That includes the unmodified real numbers.