7 ms·

The 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

The 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 ago
I'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 ago
  The 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.
  - lisper 4y ago
    > The point of my example is to show that the functions can exist even if their domain includes "indescribable" numbers. But that is not at issue. What is at issue is whether or not a function exists whose domain is an (infinite) set of indescribable numbers and whose range is a member of the set. The existence of such a function is far less clear. Of course you can postulate the existence of such a function. But you can also postulate the existence of an oracle for the halting problem. My gut tells me that these two ideas have a lot in common.
    - boole1854 4y ago
      Remember that I am not here trying to argue for the truth of the AC; I'm arguing against the author's argument. The author's argument, as I read it, relies on an intuition that "choosing" an element that is not-finitely-describable is problematic. However, the mathematical meaning of "choosing", in the context of the AC, is a statement about the mathematical existence of a certain function. To respond to the author's intuition requires only showing that not-finitely-describable domains are not a "problem" for the existence of functions. Maybe it is difficult to "choose", in some natural language sense, an input to f(x) = x + 1 such that the output x + 1 is a real number (e.g., you can't write down such an input one digit at a time on a piece of paper, even an infinitely long piece of paper). But this does not mean it is problematic for the function to exist in the mathematical sense.
      - lisper 4y ago
        FYI, I am the author. > Remember that I am not here trying to argue for the truth of the AC; I'm arguing against the author's argument. Yep, I get that. > The author's argument, as I read it, relies on an intuition that "choosing" an element that is not-finitely-describable is problematic. Not quite. Choosing an element from a set where all of the members are not-finitely-describable is problematic. > However, the mathematical meaning of "choosing", in the context of the AC, is a statement about the mathematical existence of a certain function. Yep, I get that. > To respond to the author's intuition requires only showing that not-finitely-describable domains are not a "problem" for the existence of functions. No, you would have to show that defining a function on this particular set is not a problem. Note that this is not the same thing as defining a function on elements of this set. That is obviously not a problem. But defining a (non-trivial) function on the set itself is.
- jvanderbot 4y ago
  Like f(x) = 5?
  - yaakov34 4y ago
    Wouldn't work, since 5 is not a member of the set of indescribable numbers. I am still not sure that the original example is good, since serious difficulties with the axiom of choice have to do with infinite collections of sets, especially uncountably infinite, not with choosing a member of a single difficult-to-describe set. But you can't handle these non-describable numbers very easily.
    - davrosthedalek 4y ago
      That's fine. The point is that the x is also not in the set of indescribable numbers (because you have described it with f(x)=5), assuming f is describable.
    - deleted 4y ago
      [deleted]
  - davrosthedalek 4y ago
    The problem is that for every finite description of f, the x that fulfills f(x)=5 is not in the set of numbers than cannot be described by a finite set of symbols. (I assume here that there is only one solution of f(x)=5)
ketzu 4y ago
I wonder if the set of undescribable numbers is well defined at all. It seems to run into the same problem as the "minimum un-interesting number is interesting" as a function chosing a number from that set would be a finite description of that number, removing it from the set. (This already happens if you could select a finite subset of those numbers, as finite numbers could be ordered and you could just select the minimum.) edit: Hm... thinking about it. The finitely-many-symbols argument also only holds if you consider finitely many interpretations of those symbols and if there actually are only finitely many symbols.
- mckeed 4y ago
  That's the point though, right? Without Choice, there need be no way to select a number or subset from the set, so there's no paradox.
- hilbertseries 4y ago
  https://en.m.wikipedia.org/wiki/Computable_number https://en.m.wikipedia.org/wiki/Computable_number
  - mannerheim 4y ago
    There are uncomputable numbers which can still be defined. https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant
    - deleted 4y ago
      [deleted]
    - Beldin 4y ago
      See also this Numberphile video on numbers, including algebraic, computable, transcendental, and talking about numbers beyond those. https://m.youtube.com/watch?v=5TkIe60y2GI https://m.youtube.com/watch?v=5TkIe60y2GI
- LegionMammal978 4y ago
  It's not too mind-boggling: we can describe the set as a whole without any issues, we just can't uniquely describe any particular number in the set. That doesn't stop us from generalizing over all numbers in the set, or even over all numbers in a describable subset, such as "the set of all undescribable primes".
Retric 4y ago
f(x) = x + 1 is insufficiently defined here. It’s easy to pretend math is some universal language but it’s really several mutually exclusive languages. Infinity is not a number. You can pretend it is and there are several ways to build a mathematical system around such a choice, but it isn’t inherently correct. So in your example f(x) may no longer include negative infinity and there is no paradox, it may include multiple infinite numbers and the lowest of them are now excluded, or you can say x and f(x) are the same etc. In the end there is no deeper truth here just the results of various completely arbitrary definitions.
- jjgreen 4y ago
  Infinity is not a number It depends on what you think a number is. Most people who think about it agree a number is the name that we give to equinumerate sets, so two eggs and two ducks are equinumerate, we can give a bijection between these sets; they have the same property, "twoness" and we abstract twoness to the number 2. If so, then infinity is a number, it this the number-ness of the set {1, 2, 3, ... }
  - quchen 4y ago
    > It depends on what you think a number is. Let’s not mix up teminology and semantics. What a number here is is quite clear, we’re all talking about relatively standard math, the standard axiom of choice, and not some opinion on numbers. Sure, you can also say a planet is a mammal »depending on what you think a mammal is«, but that doesn’t lead to any sort of fruitful discussion.
    - jjgreen 4y ago
      So what would you say a number is if not a name for the equivalences of set bijections? Genuinely interested, what is 2?
  - vcxy 4y ago
    There is no bijection between the natural numbers and the power set of the natural numbers. When talking about bijections to study the sizes of sets, there is clearly not just one infinity. Also consider the extended real line, this makes infinity a perfectly good number as well in a different way. My point is that infinity is certainly not an individual number. It represents quite a few concepts, all of which have some number like qualities.
kybernetikos 4y ago
> 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: If it's possible to construct the set at all, then there is by definition no function that can be described in a finite number of symbols that can select an element from the set (since if a finitely describable function can define a member of the set, it shouldn't be in the set - you'd define the element as being the result of the function). I don't know what the scholarly view is on relying on functions that cannot be defined in any human language, including mathematics. I would intuitively lean towards not allowing them in proofs, but perhaps they're useful mathematically? Another interesting aspect - these are numbers, so presumably there is a smallest one, but identifying that is definitionally ruled out too, since 'smallest element in the set of numbers indescribable in a finite sequence of symbols', is itself a finite sequence of symbols.
- syzarian 4y ago
  Consider the interval (0, 1). This set of real numbers contains no smallest element. It is not true that all sets of real numbers have or should have a least element. It is a property of the standard model of the nonzero integers that all subsets have a least element. It should be noted that there are models of ZFC in which each real number is definable. You may be interested in reading the top answer on this mathoverflow.net question: https://mathoverflow.net/questions/44102/is-the-analysis-as-taught-in-universities-in-fact-the-analysis-of-definable-numb https://mathoverflow.net/questions/44102/is-the-analysis-as-...
  - deleted 4y ago
    [deleted]
- hackandthink 4y ago
  "The well-ordering theorem together with Zorn's lemma are the most important mathematical statements that are equivalent to the axiom of choice" This is all crazy stuff, but it would be consistent: No axiom of choice -> no well-ordering -> no smallest number.
kazinator 4y ago
Let's pin it down! To choose an element from every one of a set of sets, we must describe the method of choice as a halting algorithm executable by a Turing Machine.

JackFr 4y ago

I'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 ago
The 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.
- lisper 4y ago
  > The point of my example is to show that the functions can exist even if their domain includes "indescribable" numbers. But that is not at issue. What is at issue is whether or not a function exists whose domain is an (infinite) set of indescribable numbers and whose range is a member of the set. The existence of such a function is far less clear. Of course you can postulate the existence of such a function. But you can also postulate the existence of an oracle for the halting problem. My gut tells me that these two ideas have a lot in common.
  - boole1854 4y ago
    Remember that I am not here trying to argue for the truth of the AC; I'm arguing against the author's argument. The author's argument, as I read it, relies on an intuition that "choosing" an element that is not-finitely-describable is problematic. However, the mathematical meaning of "choosing", in the context of the AC, is a statement about the mathematical existence of a certain function. To respond to the author's intuition requires only showing that not-finitely-describable domains are not a "problem" for the existence of functions. Maybe it is difficult to "choose", in some natural language sense, an input to f(x) = x + 1 such that the output x + 1 is a real number (e.g., you can't write down such an input one digit at a time on a piece of paper, even an infinitely long piece of paper). But this does not mean it is problematic for the function to exist in the mathematical sense.
    - lisper 4y ago
      FYI, I am the author. > Remember that I am not here trying to argue for the truth of the AC; I'm arguing against the author's argument. Yep, I get that. > The author's argument, as I read it, relies on an intuition that "choosing" an element that is not-finitely-describable is problematic. Not quite. Choosing an element from a set where all of the members are not-finitely-describable is problematic. > However, the mathematical meaning of "choosing", in the context of the AC, is a statement about the mathematical existence of a certain function. Yep, I get that. > To respond to the author's intuition requires only showing that not-finitely-describable domains are not a "problem" for the existence of functions. No, you would have to show that defining a function on this particular set is not a problem. Note that this is not the same thing as defining a function on elements of this set. That is obviously not a problem. But defining a (non-trivial) function on the set itself is.
jvanderbot 4y ago
Like f(x) = 5?
- yaakov34 4y ago
  Wouldn't work, since 5 is not a member of the set of indescribable numbers. I am still not sure that the original example is good, since serious difficulties with the axiom of choice have to do with infinite collections of sets, especially uncountably infinite, not with choosing a member of a single difficult-to-describe set. But you can't handle these non-describable numbers very easily.
  - davrosthedalek 4y ago
    That's fine. The point is that the x is also not in the set of indescribable numbers (because you have described it with f(x)=5), assuming f is describable.
  - deleted 4y ago
    [deleted]
- davrosthedalek 4y ago
  The problem is that for every finite description of f, the x that fulfills f(x)=5 is not in the set of numbers than cannot be described by a finite set of symbols. (I assume here that there is only one solution of f(x)=5)

ketzu 4y ago

I wonder if the set of undescribable numbers is well defined at all. It seems to run into the same problem as the "minimum un-interesting number is interesting" as a function chosing a number from that set would be a finite description of that number, removing it from the set. (This already happens if you could select a finite subset of those numbers, as finite numbers could be ordered and you could just select the minimum.) edit: Hm... thinking about it. The finitely-many-symbols argument also only holds if you consider finitely many interpretations of those symbols and if there actually are only finitely many symbols.

mckeed 4y ago
That's the point though, right? Without Choice, there need be no way to select a number or subset from the set, so there's no paradox.
hilbertseries 4y ago
https://en.m.wikipedia.org/wiki/Computable_number https://en.m.wikipedia.org/wiki/Computable_number
- mannerheim 4y ago
  There are uncomputable numbers which can still be defined. https://en.wikipedia.org/wiki/Chaitin%27s_constant https://en.wikipedia.org/wiki/Chaitin%27s_constant
  - deleted 4y ago
    [deleted]
  - Beldin 4y ago
    See also this Numberphile video on numbers, including algebraic, computable, transcendental, and talking about numbers beyond those. https://m.youtube.com/watch?v=5TkIe60y2GI https://m.youtube.com/watch?v=5TkIe60y2GI
LegionMammal978 4y ago
It's not too mind-boggling: we can describe the set as a whole without any issues, we just can't uniquely describe any particular number in the set. That doesn't stop us from generalizing over all numbers in the set, or even over all numbers in a describable subset, such as "the set of all undescribable primes".

Retric 4y ago

f(x) = x + 1 is insufficiently defined here. It’s easy to pretend math is some universal language but it’s really several mutually exclusive languages. Infinity is not a number. You can pretend it is and there are several ways to build a mathematical system around such a choice, but it isn’t inherently correct. So in your example f(x) may no longer include negative infinity and there is no paradox, it may include multiple infinite numbers and the lowest of them are now excluded, or you can say x and f(x) are the same etc. In the end there is no deeper truth here just the results of various completely arbitrary definitions.

jjgreen 4y ago
Infinity is not a number It depends on what you think a number is. Most people who think about it agree a number is the name that we give to equinumerate sets, so two eggs and two ducks are equinumerate, we can give a bijection between these sets; they have the same property, "twoness" and we abstract twoness to the number 2. If so, then infinity is a number, it this the number-ness of the set {1, 2, 3, ... }
- quchen 4y ago
  > It depends on what you think a number is. Let’s not mix up teminology and semantics. What a number here is is quite clear, we’re all talking about relatively standard math, the standard axiom of choice, and not some opinion on numbers. Sure, you can also say a planet is a mammal »depending on what you think a mammal is«, but that doesn’t lead to any sort of fruitful discussion.
  - jjgreen 4y ago
    So what would you say a number is if not a name for the equivalences of set bijections? Genuinely interested, what is 2?
- vcxy 4y ago
  There is no bijection between the natural numbers and the power set of the natural numbers. When talking about bijections to study the sizes of sets, there is clearly not just one infinity. Also consider the extended real line, this makes infinity a perfectly good number as well in a different way. My point is that infinity is certainly not an individual number. It represents quite a few concepts, all of which have some number like qualities.

kybernetikos 4y ago

> 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: If it's possible to construct the set at all, then there is by definition no function that can be described in a finite number of symbols that can select an element from the set (since if a finitely describable function can define a member of the set, it shouldn't be in the set - you'd define the element as being the result of the function). I don't know what the scholarly view is on relying on functions that cannot be defined in any human language, including mathematics. I would intuitively lean towards not allowing them in proofs, but perhaps they're useful mathematically? Another interesting aspect - these are numbers, so presumably there is a smallest one, but identifying that is definitionally ruled out too, since 'smallest element in the set of numbers indescribable in a finite sequence of symbols', is itself a finite sequence of symbols.

syzarian 4y ago
Consider the interval (0, 1). This set of real numbers contains no smallest element. It is not true that all sets of real numbers have or should have a least element. It is a property of the standard model of the nonzero integers that all subsets have a least element. It should be noted that there are models of ZFC in which each real number is definable. You may be interested in reading the top answer on this mathoverflow.net question: https://mathoverflow.net/questions/44102/is-the-analysis-as-taught-in-universities-in-fact-the-analysis-of-definable-numb https://mathoverflow.net/questions/44102/is-the-analysis-as-...
- deleted 4y ago
  [deleted]
hackandthink 4y ago
"The well-ordering theorem together with Zorn's lemma are the most important mathematical statements that are equivalent to the axiom of choice" This is all crazy stuff, but it would be consistent: No axiom of choice -> no well-ordering -> no smallest number.

kazinator 4y ago

Let's pin it down! To choose an element from every one of a set of sets, we must describe the method of choice as a halting algorithm executable by a Turing Machine.