Comment by boole1854 | Hacker News Reader

Comment by boole1854 | Hacker News Reader

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.

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.

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.

https://en.m.wikipedia.org/wiki/Computable_number

There are uncomputable numbers which can still be defined.

https://en.wikipedia.org/wiki/Chaitin%27s_constant

See also this Numberphile video on numbers, including algebraic, computable, transcendental, and talking about numbers beyond those.

https://m.youtube.com/watch?v=5TkIe60y2GI

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".

> we can describe the set as a whole without any issues

But it does not mean the set is well defined. The description is not necessarily clear an unambigious. It might not be consistent under the generalizations we come up with.

> "the set of all undescribable primes"

Interesting example, because the set is trivially empty under the assumption that we can describe any finite natural number by writing down its decimal expansion. (Based on that you can either argue that the primes are a subset of the natural numbers or that the primes are countable.)

I see no reason to believe that "undescribable" is a well defined property so far.

> But it does not mean the set is well defined. The description is not necessarily clear an unambigious. It might not be consistent under the generalizations we come up with.

Well, obviously such a set must be defined relative to whatever system you're using to describe the numbers. But once you have it, you can simply declare that a number is in your set if and only if there does not exist a finite description in your system of choice. (In other words, you enumerate the countable many finite descriptions in your system, put them in the set, then define the new set as the complement.) How is that ambiguous?

> Interesting example, because the set is trivially empty under the assumption that we can describe any finite natural number by writing down its decimal expansion. (Based on that you can either argue that the primes are a subset of the natural numbers or that the primes are countable.)

Whoops, you're right, all integers are describable. Perhaps I should amend that to "the set of all undescribable real numbers with a prime integer part", or something along those lines.

> you can simply declare that a number is in your set if and only if there does not exist a finite description in your system of choice.

The problem I see is that we do not have such a rigurous system and instead can introduce new notation, and how we decide on the notation may change the contents of the set of undescribable numbers. If there is no ambiguity, because we are using a very limited description language that can not be extended, we may be too restrictive in the language so the set becomes meaningless, e.g., because we could describe a number within it outside of the system which represents a trivial choice function.

Well, typically, I'd say, "A proposition P(x) of first order logic describes a particular number iff, for all numbers x and y such that P(x) and P(y) are true, x = y." Then, your system of description is exactly as powerful as your system of logical axioms. But I think you're correct in that you can construct a number where it's undecidable whether it has such a description. That doesn't mean that the set of undescribable numbers is ill-defined (relative to your axiom system): it just means that you can't always answer whether it contains that number.

I think the resolution is along the lines of this:

* ZFC does not have a unique model that satisfies the axioms.

* Each of those models have different "undescribable numbers" with different properties.

But it was a long time I touched model theory, and it was just an optional extra course at uni.

https://en.wikipedia.org/wiki/Model_theory

To me, the expression "The set of undescribable numbers" is meaningless. While discussing plausible-sounding, but meaningless, linguistic constructs like this, we descend to the intellectual level of chatGPT. My conjecture is that one can design a prompt to chatGPT such that the output would become a decent PhD thesis with no internal contradictions, but a complete BS otherwise.

I think if we take "description of a number" to mean "ZF formula that uniquely picks out that number", then that cannot be defined, because a formula picks out a number when it is true for that number and false for all others, but by Tarski[0], the truth predicate cannot be defined inside the logic itself. So "the set of all numbers which cannot be described" cannot be talked about using ZF.

However, there is a way around it, by taking as axiom that ZF is consistent, choosing some model M of ZF, and then talking about the set S of numbers inside M that cannot be described.

[0] https://en.wikipedia.org/wiki/Tarski%27s_undefinability_theo...

Bingo. The issue here is that ZF and ZFC are both first order theories. They can only talk about things that can be defined within them, not things that cannot be defined within them. The wiki article talks about that where it says:

> Informally, the theorem says that the concept of truth of first-order arithmetic statements cannot be defined by a formula in first-order arithmetic. This implies a major limitation on the scope of "self-representation". It is possible to define a formula True(n){\displaystyle True(n)} whose extension is T∗,{\displaystyle T^{*},} but only by drawing on a metalanguage whose expressive power goes beyond that of L.L. For example, a truth predicate for first-order arithmetic can be defined in second-order arithmetic. However, this formula would only be able to define a truth predicate for formulas in the original language L.L. To define a truth predicate for the metalanguage would require a still higher metametalanguage, and so on.

> 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.

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-...

"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.

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.

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.

> 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.

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.

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.

I just don’t see what describability, or as jiggawatts calls it, naming, has to do with AC. AC is built upon an indexed set[1]. That way you can just reference the index. It seems extremely contrived to me to argue that being finitely nameable has any bearing on underlying mathematical principle, nothing about any form of infinity is relatable to the physical confines of this universe, of which language is a member, but the concept of infinite is very useful.

[1]https://en.wikipedia.org/wiki/Axiom_of_choice

> I just don’t see what describability, or as jiggawatts calls it, naming, has to do with AC.

It doesn't have anything to do with AoC per se, it has to do (I claim) with people's intuitions about AoC. Specifically, an infinite set of arbitrary subsets of the set of indescribable reals is something for which a reasonable person might be a tad suspicious about postulating the existence of a choice function.

There are models of ZFC in which every real number is definable. You may be interested in the top answer at this mathoverflow.net question:

https://mathoverflow.net/questions/44102/is-the-analysis-as-...

That is very interesting (have an upvote!) but I don't see how it invalidates my argument. If every real is definable then the set of non-definable reals is empty and AoC does not apply at all.

The notion of countable and not countable does have some nuance. In the models that every real is definable that model, from within, believes it is uncountable since there is no bijection with a countable set from within that model. However, from the outside that model is countable.

The point is there is a lot of nuance and no matter what one believes regarding choice there will be unintuitive results. For instance, when the axiom of choice fails you can have an infinite set with not countably infinite subset. The reals can be a countable union of countable sets. There is a set that can be partitioned into strictly more equivalence classes than the original set has elements, and a function whose domain is strictly smaller than its range. In fact, this is the case in all known models.

We need to be careful with the language here. It's not true that there are models of ZFC where the real numbers are actually definable. What's true is there are models of ZFC where what is considered a "real number" from within that model is always definable (but will not be definable within that model). However, those sets do not form the actual real numbers, they are simply sets that from within the model satisfy a given definition of the reals without actually being the reals.

A similar result is that there are models of the reals in ZFC that are countable, even though the reals are not countable. How can this be? Well it's similar to the above argument, those models do not represent the actual real numbers.

All this means is that it's not possible to categorically define real numbers in first order ZFC. Any axiomatic definition of the reals in first order ZFC will have some models that satisfy those axioms but are not actually real numbers.

I’m not a logician or set theorist. I studied commutative algebra and, naturally, accept the axiom of choice. When you say, ”the actual reals” I think you mean the standard notion of a real number that we all are used to using. But those models that we are talking about are models of the axioms of the reals. So, they are the actual real numbers as far as that model is concerned, right?

You got it, absolutely. So yes there are models where as far as the model is concerned there is a set that satisfies the axioms of real numbers, and furthermore all elements of that set are actually definable (but not definable from within that model), but that set is not the standard notion of real numbers. It's just that it's impossible to provide a set of axioms that defines the real numbers and only the real numbers (in first order logic), so for any definition of the real numbers you end up with a model that will satisfy that definition but doesn't actually model the "standard notion of real numbers".

The reason I brought this up is because when you said that there are models of ZFC where every real is definable, those reals are only definable from outside of the model. From within that model there are still undefinable reals and hence I don't think it matters too much to the point lisper is making.

Maybe to put it another way, there is no model of the reals where within that model all reals are definable, and hence lisper's point stands.

Understood. I wasn’t trying to address lisper’s directly as such. My poorly stated goal was to point out that intuition regarding uncountable sets is shaky at best. There are weird results regardless of one’s views because of nonstandard models.

Intuitively I would argue the definition of indescribability is loaded with semantics that can sprinkle paradoxes at will. A set from my perspective has at least two interfaces, one to populate it and one to query it. By making the population interface “indescribable” you get an “indescribable” method to query. Worst case you start from a describable superset of the indescribable one and test the “indescribable “ set population method to get you an indescribable set member. Which makes the indescribable actually describable in terms of this process. “?” on this whole statement, late night intuition from an indescribably bad at math sleepy guy.

> one to populate it and one to query it

I'm not a math expert, but "populating" a set strikes me as an imperative programming mindset. In math, I understand a set more like a function returning a boolean that indicates membership. If the contents of the set change, then it's just a new set.

Yeah, this. A set does not have "two interfaces", it only has one: a membership function that takes an object and returns a boolean indicating if the object is a member of the set or not. Note that this function need not be computable, only well-defined.

Is the membership function not equivalent to what I describe above on the query side? My difference is that I am making explicit that the set needs to be populated. The uttering of a set of “indescribable “ objects does not a set give you. That membership function works both inwards and outwards.

This concept of "population" doesn't really seem to be consistent with my understanding of a set.

Set A is the set of all widgets that have a frozz. The existence of Set A doesn't imply that there exists a widget that has a frozz. Perhaps the existence of such a widget is an open question. But the set is perfectly well defined.

Right. The set of all integers which are both even and odd is a well-defined set. It just happens to be empty. The set of all counter-examples to the Goldbach conjecture is a well-defined set. We don't know if it's empty or not.

If I don’t know what frozz is, is the set well defined? Maybe in form, but not in essences. Lisper’s example in sibling comment is indeed well formed, but I know that if I get a counter-example to the conjecture it will pass the population interface and become part of the set. Therefore, I don’t see how we differ comparing simple membership with population and query. My feeling is we disagree over an ex nihilo vs procedural emergence of sets.

The nature of the elements of the set does not matter, since the existence of a choice function on the set A guarantees the existence of a choice function on the set B as soon as there is a bijection between A and B. Thus, no matters how counter-intuitive or unnatural one finds the elements of a set, or whether they model physical reality, what matters for the axiom of choice is whether one can construct a bijection with a set that has a known choice function.

By the way, it is worth keeping in mind how Gödel proved the consistency of the axiom of choice. Roughly speaking, the steps are: start with a model of ZF, build from it an inner model where all sets are definable (in a sense) in terms of ordinals, that model (called the "constructible universe") satisfies the axiom of choice. In other words, the axiom of choice holds as soon as you assume that all sets are constructible.

> as soon as there is a bijection between A and B

OK, but how are you going to construct a bijection from an arbitrary infinite set of undefinable numbers onto a set with a choice function without the AoC?

It seems like the validity of what you're saying is intertwined with the axiom itself. You're going from a comment about the domain (the domain includes indescribable elements) to a comment about specific arguments (arguments may be indescribable).

Ultimately, you're saying that if we have an indescribable x, then x+1 is conditionally describable (to abuse terminology). But I think that just sidesteps the question. Even then, if we're taking a computability lens, then indescribable(x) implies indescribable(x+1), which would seem to imply that applying your function to indescribable x's is a moot point.

The fact that your function is finitely describable even though we can't describe each of its applications is admittedly a mindfuck.

Like f(x) = 5?

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.

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.

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)

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.

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.

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, ... }

> 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.

So what would you say a number is if not a name for the equivalences of set bijections? Genuinely interested, what is 2?

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.

Indeed, but when people say "infinity is not a number" they generally mean ℵ₀, and that is (in my view) as much a (cardinal) number as 2. Once you have that established, then you go on to discuss the higher ℵs and the continuum hypothesis ...

> when people say "infinity is not a number" they generally mean aleph-0

Sure, maybe. I think saying "infinity is a number" is wrong regardless. I'm happy with aleph-0 being a number, and I'm happy with it having a label of infinity. I'm just not happy with treating infinity as a single thing. We're totally on the same page in every way that matters though. I'm also certainly with you on questioning Retric's comment for a number of reasons, haha.

edit: Actually...I'm not so sure they mean aleph-0. I think frequently they mean the infinity of the extended real line. Maybe it depends on the context of the conversation.

It's actually a great ice-breaker for first-year maths undergrads, when talking about limits or whatever drop in "... to infinity and beyond!", laughter follows, then say "You think I'm joking? Put down your pens ..." and informally outline the aleph hierarchy, then things get rather quiet.

Ahh I wish I had gotten the chance to interact with new math majors more often. In grad school most of my students were engineering majors. I'm not super likely to end up back in academia. My published research is...sparse. I have post-doc opportunity but it's not the greatest, and the route to life stability is not so clear. Are you a math professor?

No, a developer; I spent several years as applied maths researcher though, and UK universities love to use researchers as cheap lecturers (not that I'm complaining, rather enjoyed it).

Cool. I have a second interview for a software developer position at a quantum computing place this week. Hopefully I'll be following you into the field!

ℵ₀ [is] as much a (cardinal) number as 2

Note that this view is common but not universal: https://cs.nyu.edu/pipermail/fom/2023-January/023710.html

Your post doesn’t make sense mathematically. As a function from the reals to the reals the function f(x) = x+1 doesn’t “include negative infinity” (have no idea what that is supposed to mean). Negative infinity is not a real number and is not in the domain of the function or its range. If you think “infinity” (which one?) is not a number then do you believe there are no infinite ordinals? How do you justify the view that countably infinite ordinals don’t exist?

You are making assumptions, define the lowest real number.

There are well defined models of the real numbers. You don’t know enough mathematics to comment intelligently on this topic. What you wrote above makes no sense.

EDIT: There is no least real number under the standard ordering. There is a least real number for a given well ordering. If you are asking me to define a well ordering on the reals then your request question should have been stated differently.

You said models not model here, so you acknowledge there isn’t a single universal definition.

I’ve seen some truly bizarre definitions of the reals which are internally consistent and include things like the lowest possible number.

You don’t know enough set theory and model theory. Of course there are different models of the real numbers. There are non isomorphic models of the first 4 axioms of Euclidean geometry even. A given set of axioms can have lots of different models.

The widely accepted first order axioms of the natural numbers have nonstandard models. Of course each such model has an isomorphic initial segment. There are two things going on. There is the set of axioms and there are models for those axioms. I think in your usage: “define real number” corresponds to “give the axioms for the real numbers”. I’m not sure though.

Non standard models of arithmetic really takes me back. Anyway, axiom/models is the common terminology though I recall a rather long rant that postulate is better once you start talking about multiple incompatible systems.

Please consider that the poster telling you that you do not know enough to comment intelligently about this topic may be correct.

> Anyway, axiom/models is the common terminology though I recall a rather long rant that postulate is better once you start talking about multiple incompatible systems.

Model has a very specific definition in this area of mathematics. This sentence is nonsense.

I am describing an actual event with that sentence. Are you suggesting that someone can’t rant about such things?

The negative reals are an infinite set, that doesn't make "negative infinity" a real number though. Negativy infinity is a concept, that can be used in some math frameworks, but it is not defined within R.

See this exchange for details

https://math.stackexchange.com/questions/2812355/does-infini...

I am trying to allude to transfinite numbers and annoy mathematicians without losing a general audience, feel free to ignore such things.

> Infinity is not a number.

It's not a real number, true. But that has no bearing at all on the validity of f(x) = x + 1, since that function is well-defined with both its domain and its range as all real numbers and no others. You don't need infinity to be a number to define that function.

Reply on news.ycombinator.com