Hacker News Reader

Comment by lisper | Hacker News Reader

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

View on HN

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.

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.

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?

Reply on news.ycombinator.com