An intutive counterexample to the axiom of choice | Hacker News Reader

An intutive counterexample to the axiom of choice

blog.rongarret.info

101 pointslisper255 comments

The thread this post is continuing: https://news.ycombinator.com/item?id=34484011

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'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)

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.

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.

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

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.

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

Question: While the standard construction of the set for Banach-Tarski requires AOC, is it proven that without AOC, Banach-Tarksi isn't true?

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

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

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

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

Can you give an example in which these two things are different?

I'm not sure I understand what you are asking. One is a description of a procedure and the other is a description of a number so obviously these are two different things.

When you say "Any number can easily be described by x" aren't you already using Choice? And doesn't "let x be one of those numbers from the set of numbers that cannot be described with finite symbols" seem a bit like a paradox?

How do you feel about this example?

https://www.solipsys.co.uk/new/APointAgainstTheAxiomOfChoice...

> you can get most of math with Axiom of Countable Choice

Wait, I think you just made me realise that my intuition for AoC is wrong and actually matches AoCC instead, and that I'd never stopped to consider that the collection of sets you're choosing from could be uncountable. If that's correct, that explains so much.

I don't think you can get the Hahn-Banach theorem with just countable choice. So you have to re-do a whole lot of functional analysis that depends on it.

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

How 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?

That'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)

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

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

An axiom has to be consistent with other axioms (that is, adding it doesn't introduce a contradiction).

That would let me derive your mother's phone number. https://xkcd.com/704/

It's different because there's nothing that says such a choice function _cannot_ exist (short of an axiom that says explicitly so).

> The OP's argument seems to be just that you cannot always construct a choice function.

No, the argument is that if you cannot describe the choice then you have a problem. My argument does not assume anything about the choice function, it's merely an informal observation about its output.

So the statement "let x be an element of y" is already problematic?

If so, your problem is not with the axiom of choice.

Edit: "Not being able to describe the choice a choice function makes" and "not being able to construct it" are really the same thing.

> So the statement "let x be an element of y" is already problematic?

Hm, good point. No, that's not the problem because that's just the same as saying "let x be an undefinable number". The problematic statement is (I think -- I need to think about this some more) "let f be a choice function on (infinite) sets of undefinable numbers". If x=f(S) that is not the same as "let x be an undefinable number" unless S is the set of ALL undefinable numbers, which it need not be.

You're right that there's a problem with 'Let f be a choice function on...', but that's the problem the axiom of choice solves. Sure, it's non-constructive; you don't know much about f, just that it exists and f(s) is in s (for all sets s that are subsets of S).

The question is specifically what weird undefinable numbers have to do with anything; why those are specifically a problem.

Let S be the set of all non-finitely defined real numbers.

Let (Sn) be the sequence of sets such that Sn = {s in S : n-1 < s < n}

Am I allowed to say "let s1 be an element of S1"? Or "s2 an element of S2"? (Note that we don't need the axiom of choice to get a choice function for this sequence; I can easily construct one; does that change anything?).

> I can easily construct one; does that change anything?)

I don't think so. The way you have constructed the Sn's allows you to re-use a choice function for one set for all the other sets. But I don't think this is possible in general.

This is the thing that makes it hard. If you don't impose some sort of structure on the Sn's then I think you will have a very hard time constructing a choice function for them. That's the whole point. If you want a choice function for such sets in general you have to just assume that one exists without being able to actually exhibit one. Your assumption may be mathematically valid (because AoC is consistent with ZF), but I submit that a reasonable person might find it a little hinky.

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

Yeah, 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!

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

Thanks 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)?

> Is this only a problem for infinite sets (of sets to pick from)?

I've edited this a lot, but it might still depend on the AoC if you can construct such a function in general, my ideas didn't work (e.g. two complex infinite sets per set are already hard)

> 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)?

With no constraints on the function this is the AoC.

These 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?"

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

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

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

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

It's normally assumed that the number of symbols is finite.

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

The set of all sets of natural numbers is uncountable, but the set of all finite sets of natural numbers, is countable.

True, that's why I haven't used 'finite' in my comment.

Apparently I've missed that the parent referred to the finite collections and in fact was wrong making my previous comment misplaced. Thanks for pointing it out :)

There are countably many finite strings of a fixed, finite collection of symbols. That’s the point the author is making — it becomes more intuitively obvious that there might be trouble “choosing” when you design the set you’d like to choose from to consist solely of the “nameless” reals.

There are countably many finite collections of symbols.

There are uncountably many countable collections of symbols.

Edit:

The above is true if your symbols are countable. If they are uncountable, then obviously there are uncountable finite sets of your symbols (As the singleton sets are a subset, and those are uncountable).

> there are uncountably many finite collections of symbols

Only if there are uncountably many symbols. But this is a fair point. I'll need to define what I mean by "symbol" more clearly.

> But there are uncountably many finite collections of symbols.

As others have pointed out, that depends on how big the set of possible symptoms are.

If the set is finite, then there are a countable number of finite collections (the countable union of countable sets is still countable).

If the set is countably infinite, then there are still countably many finite collections.[1]

If the set is uncountably infinite, then you're right. However, the author is probably talking about all symbols known to humanity, which clearly is not only not uncountable, but it is finite.

[1] https://math.stackexchange.com/questions/200389/show-that-th...

There are uncountably many (countably) infinite collections of symbols from within a countably infinite set of possible symbols.

The set of finite subsets of a countably infinite set, is countably infinite.

There is a computable bijection between the set of natural numbers and the set of finite sequences of natural numbers.

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

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

You are going to love this:

How real are real numbers?

https://arxiv.org/abs/math/0411418

Real numbers are interesting and math is not about computation, counting or calculation.

math is not only about computation, counting or calculation.

Mathematicians 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 but you could write it in infinite time if God told you the digits.)

> Computer scientist don't accept noncomputable objects.

People who study computability certainly do, and I would think they count as computer scientists.

> Computer scientist don't accept noncomputable objects. Mathematicians do.

Computer scientists don't have a choice. And not all mathematicians do accept non-computable objects. Constructive and intuitionistic mathematics are two approaches that bring some questions (doubt?) of the continuum.

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

Just because you can create a definition, doesn't mean that definition names a thing. We can define "the set of all sets that do not contain themselves", but such a definition is nonsensical in that trying to apply it creates a contradiction. To me, the incomputability of Chaitin's constant seems very similar, except it's contradiction is buried inside the halting problem.

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

I 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

Seems to be quite subtle (proof theoretic strength and consistency strength)

(2) https://mathoverflow.net/questions/126002/interpretability-a...

I think “equiconsistent” just means that (one can prove that) if one is consistent, then the other is also consistent.

Doesn’t mean the collections of things they can prove can’t differ.

For a weak example, aiui, a formal system is equiconsistent with any conservative extension of it, but the conservative extension can (in the cases one would usually speak of) prove some statements that aren’t in the language of the original system.

Thanks, I'm not confused anymore.

You might want to check out the Gödel–Gentzen negative translation[0], which is an interpretation of classical logic in intuitionistic logic, which can be (somewhat inaccurately) summarized as "if P is provable in classical logic, then not not P is provable in intuitionistic logic".

[0] https://en.wikipedia.org/wiki/G%C3%B6del%E2%80%93Gentzen_neg...

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

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

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

How did God create universe?

Does your (non) answer imply that Universe doesn't exist?

This 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

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

I suspect that the resolution boils down to what it means to "describe" a number.

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

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

The set of uninteresting numbers is probably empty.

Please define "uninteresting" and "probably".

The standard mathematics teacher's response: I'll leave that as an exercise for the student.

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

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

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

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

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

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

I believe you are mistaken. This set of numbers is just the set of reals minus the countable infinity of finitely representable numbers. This set should still be densely ordered and so for any member that could be chosen from this set, there is an infinite number of elements closer to zero.

> But that set must have a member whose value is closest to zero.

Must it? Is there a real number closest to zero?

> But that set must have a member whose value is closest to zero.

Must it?

"Let x be the smallest element of the half-open interval (0, 1]" isn't really something that you can say *.

* Assuming the standard ordering of reals; sure you can say it's defined for some well-order, but then you require the Axiom of Choice anyway.

> But that set must have a member whose value is closest to zero

This is not true for real numbers with the usual "less-than" relation. In fact, considering real numbers, no open subset of R admits a lower member.

According to Zorn's lemma, there exist some order relation where your assertion is true, but I seem to remember from my math course a few (!) years ago that Zorn's lemma is equivalent to the axiom of choice.

According to the well-ordering theorem which is equivalent to the axiom of choice (and Zorn's lemma), you can well-order any set. That's usually when people start doubting the axiom of choice because, well, that's quite unintuitive. There is a joke about it which has already been posted here.

You can well order any set, but you need to have the "right" ordering to do so. As your parent is pointing out, the usual ordering on the reals is not a well ordering, and one cannot achieve a well ordering of the reals using that ordering.

This doesn't work for rational numbers either. Take any rational a/b, then 0 < a/(2b) < a/b is both closer to zero, and it is also a rational number.

It would at least require some careful setup to be coherent. Like you won't be able to define "the least positive integer that can't be uniquely described in fewer than fifteen words". Basically your language won't be consistent if it allows you to talk about things that can / can't be uniquely described in the language itself.

My disagreement about this post is: I don't see what it has to do with the axiom of choice. The only "choice" used here is that this nonempty set of non-describable numbers (if indeed we can define it at all) contains at least one element. That's a tautology and doesn't require choice.

Also, the author may be interested in Skolem's paradox: in particular, if the theory of the real numbers is consistent, then there must be a construction with only countably many reals, and so if I understand correctly, they would all be describable.

The definition of this set is contradictory, but not for the reason you've suggested. Rather, it is impossible to construct the set of numbers which can be defined by a finite string of symbols, due to Richard's paradox:

http://en.wikipedia.org/wiki/Richard's_paradox

Hence, it is also impossible to construct the complement of this set. In fact, Richard's "diagonal argument" chooses precisely the sort of number we ought not to be able to choose, according to the blog post (but again, this just shows the set is not well-defined).

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

Where is infinite information invoked?

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

Let's see if I can clear this up:

An equivalent way to phrase the Axiom of Choice is: there exists a function that takes in any non-empty set, and returns an element of that set.

IE, this exists: choose a :: NonEmptySet a -> a

That's it. All of this stuff about "take a choice from a countable number (IE, list) of sets" is fluff; once you have choose, you can make a function that takes in an Iterator (NonEmptySet a) and produces (NonEmptySet a), such that the output will contain every element.

oneFromEachSet :: Iterator (NonEmptySet a) -> NonEmptySet a

oneFromEachSet iter = NonEmptySet (choose (first iter)) <> (oneFromEachSet (rest iter))

Where '<>' is set union.

Does that fix your issue with an "infinite" number of choices? Or do you take issue with assuming 'choose' exists, now that it's a single function?

From a programmatic viewpoint that would be describing the axiom of countable choice, since such recursion can only occur countably infinite number of times.

Even if we ignore that by allowing for syntax where we fanout uncountably many times with each recursion, the construction as shown requires the collection of sets to be orderable, to be able to do have a "first", unless we are implementing first in terms of choose itself. (Alternatively one could also argue in terms of Axiom of Choice implying the well-ordering theorem, allowing up to pick a minimum via some such ordering (although you may need to use the choice function to pick one such ordering), but this won't fully help here anyway).

But even if you do that (implement iterator's first in terms of choose) it is not immediately obvious that you really have covered everything some full statements of the axiom of choice does. The axiom of choice is generally phased in terms of collections or families of sets, not sets of sets, but obviously the choose function takes in a set, not a more general family or collection.

It is easy enough to dismiss away certainly non-set collections of sets, like multisets of sets, since "choose" being a function will return the same value every time from a repeated input, and in the above formulation we are returning a set of results, so such duplicates won't matter. We could even handwave away a version where we return a multiset without too much trouble.

But the more expansive versions of the axiom of choice allow us to do something like "choose one element from each set in the class of non-empty sets." This is a real problem, as the "class of non-empty sets" is pretty well known to not be a set, and thus trying to implement iterator first in terms of it would not even be possible for that scenario.

"First" in this case was just getting the first element of the iterator, it wasn't related to choosing a value from the set.

The Axiom of Choice is equivalent to the following:

1) "For any set A, there exists a function from non-empty elements of the power set of A to elements of A."

Which is equivalent to:

2) "There exists a function that takes a non-empty set as input, and returns an element of that set"

2 -> 1, since we can take the function 2 defines, and use it to define the function from 1.

1 -> 2 since we can define 2 as such:

For a set A, take the power set of A. Then take the function that 1 claims exists. Use that function to get an element of A, since A is an element of its power set.

But back to your core point:

But I agree that Iterator is a bad fit for the axiom of choice, since we have an (uncountable) number of sets to pick from.

Here's a way to phrase it programmatically that allows for uncountable sets-of-sets:

The axiom of choice claims that given a set of non-empty sets, you can construct a new set which contains an element from each of the sets.

pickOneFromEach :: Set (NonEmptySet a) -> NonEmptySet a

If you have a function:

choose :: NonEmptySet a -> a

And a function:

map :: (a -> b) -> Set a -> Set b

then you can define pickOneFromEach as follows:

pickOneFromEach setOfSets = map choose setOfSets

AoC is a hacky shortcut. It gives right answers when it is supposed to, and wrong answers when they don't care.

(Most, non-constructivist) Mathematicians are comfortable with it, because they don't care that it contradicts physical reality, as long as it doesn't contradict itself. They aren't physicists.

On the flip side, physics don't care about being mathematically correct, as long their errors approximate reality.

"comfort" isn't really useful here. You say you don't toss it out, so what does your discomfort mean? Is there some result you refuse to believe? Or do you simply prefer to study non-AoC math? I like algebra. That doesn't mean I'm not "comfortable" with geometry existing.

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

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

For 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 ?

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

> the set of numbers that cannot be described using any finite collection of symbols

Not clear that this is a well-defined set.

It's probably not well-defined.

https://en.m.wikipedia.org/wiki/Richard's_paradox

A 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!

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

What'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?

Indeed, it works as long as the class of labels forms a set instead of a proper class.

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

What is the "smallest positive number" in the set {x | x in reals and 0 < x < 1}?

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

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

since 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"?

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

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

But 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

I'm late replying to this, but---you need the axiom of choice once you have a family of non-empty sets rather than a single non-empty set.

At some point you have to go into the formalism to really understand it. It's really about an interchange of quantifiers. If you have a non-empty set X that it is true that

[a] (exists x)(x in X)

If you have a family F of non-empty sets X then it is true that

[b] (forall X in F)(exists x)(x in X)

But to say that you have a choice function f for F is to say that

[c] (exists f)(forall X in F)(f(X) in X)

It turns out that the laws of first-order predicate logic and the axioms of ZF set theory do not allow you to come up with a formal proof that [b] implies [c]. You can try to find one, and you will fail. It's like the parallel postulate in Euclidean geometry. There is actually a proof that the axiom of choice is not provable from the other axioms, but it's a pretty deep result. Historically, there was quite a long time between when the set-theoretical foundations for mathematics were developed at the start of the 20th century, which is when mathematicians realized that the axiom of choice was a principle that needed justification, and when Paul Cohen proved that the axiom of choice wasn't provable from the other axioms, in the 1960s.

So if you believe that the implication from [b] to [c] is self-evident, you have to assume

[d] (forall X in F)(exists x)(x in X) => (exists f)(forall X in F)(f(X) in X)

as an axiom, which is the axiom of choice.

I think most people are inclined to agree that [d] is self-evident---that's why it's generally accepted as an axiom, with only a minority of people objecting. However, in the larger context of set theory it makes a lot of sense to minimize the amount of existential assumptions we are making. Historically, set theorists assumed that any set given by a definable formula would exist, but this lead to contradictions (Russell's paradox). So there's some reasonable paranoia about using additional axioms when we don't need to, in case it somehow leads to another inconsistency.

Sets are defined by their members. If you have a nonempty set, you must have defined a member when you proved it was nonempty. Take any convenient one.

This works for any finite or countable family, because you can repeat the process for each set, any set you can think of will be processed eventually.

But for an uncountable set, almost every set will never be processed, and almost every set is impossible to describe in finite time (per set!), unless you just assume that you can do it on one magical oracle bulk selection.

Is the correct way to see this is that logic has to be specified in a finite number of terms? For countable families there’s some sort of meta logic like “for the Nth element I induct to that”?

I believe to understand that idea (since it comes up in real analysis to some extent, basically acknowledging there isn’t really infinite sums except as limits of finite sums), but is there a specific sort of text that lays out this idea specifically?

Reaction: "Intuition" works about as well with the Axiom of Choice as it does with brain surgery, nuclear physics, and rocket science.

This 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?)

The author means finite sequence over finite alphabet, i.e. the finite collection of symbols does not refer to the alphabet.

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

The 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?

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

You 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?

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

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

Saying something doesn’t imply saying something about a denotable entity.

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

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

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

Oh hey Tel, do I remember you right from #haskell on Freenode? : - D

Not on there a ton, but yes!

That is called Diaconescu's theorem.

https://en.wikipedia.org/wiki/Diaconescu%27s_theorem

Thank you!

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.

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

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

I mean what you say is trivially true. Give me a number r in R. I will call that number h. That’s not really interesting.

It’s interesting only as a refutation of the original quote:

You’re misunderstanding the quote. It’s not saying that you can’t name any individual number. It’s saying that any scheme you can think of to name numbers involving a finite number of symbols will have numbers that can’t be expressed in that scheme.

That's right, we are talking about non computable numbers, so they can't actually be "specific".

Say you have a no computable number A (Chaitin's constant), and I have an uncomputable number B Chaitin's constant but the the trillionth digit is equall to the most common digit in the infinite decimal expansion of Chaitin's constant). How can you tell if they are the same or different? In general, you can't. So what does "specific" even mean?

I'm not sure if that's relevant. You're pointing out that ordering of the reals is not computable, which is true, but ordering of the computable numbers isn't even computable. This isn't relevant to whether a symbol in a computer algebra system can refer to a particular number (whether computable or not).

I 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/ThePointOfTheBanachTarskiTheo... https://news.ycombinator.com/item?id=34482226

[2] https://www.solipsys.co.uk/new/InDefenseOfTheAxiomOfChoice.h...

[3] https://www.solipsys.co.uk/new/APointAgainstTheAxiomOfChoice...

A variable name and the thing it points to are not the same thing. Symbols aren't numbers. They are a means to communicate numbers.

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

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

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

But 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

AoC 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?

I don't think we could talk about numbers that cannot be described by finitely many symbols (let alone a countably infinite number of symbols).

An 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?

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

Even 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?

Doesn’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!

The axiom of choice is not a definition or theorem or problem. It is an axiom. You either take it or leave it.

Perhaps 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?

The thing is, infinity is extremely useful for taking things to the extreme. The halting problem is a very good example: as you rightly point out, the halting problem is trivially decidable for any finite Turing machine. However, the core of the argument remains true, we just need to complicate it significantly if we want to remain within the realm of finite machines: instead of saying "there is no TM that can decide if any arbitrary TM halts", we need to say something like "there is no finite TM that can decide if any TM smaller than itself halts in an amount of time less than that TM". They are equivalent concepts on some level, but the second one is significantly more complex, and harder to prove (assuming you don't appeal to the infinite version, from which it easily follows).

That is, even if you seek to do maths on finite but unbounded sets, you will find mostly the same properties that infinite sets have, but you'll have a much harder time working with the concepts. It's true that there are some problems that infinite sets have that unbounded finite sets don't, but those may well be a worthy price to pay.

And either way, regardless of intuition, the logic is valid. The Banach-Tarski "paradox" is perfectly logically valid, though unintuitive. So, even if you could say that it's useless and a result that we should avoid having in our theories, you can't say that it's wrong, since it doesn't violate any rule of logic.

I can't really give a substantial response to your first argument, as I'm not certain about all the implications that you mention.

Your second argument, though, doesn't sound very convincing to me.

There are many possible consistent logical frameworks (perhaps an infinite amount of them? hah!) that are clearly not adequate for describing our universe. Or at least, they wouldn't make sense for us.

For a trivial (and perhaps stupid) example, consider an alternate universe where we decided to use a logical framework which can represent natural numbers, but where the digit "2" is represented as "9" and the digit "9" is represented as "7", etc. Let's say you have a 1-to-1 mapping from one digit to another, compared to our usual representation.

Or perhaps the mapping is a lot more complicated than that, and not just about digits, but about entire numbers.

Let's say we decided to do that, for no good reason. Or maybe there was a good reason at the time, but since then we have figured out that it doesn't make sense anymore.

Yes, you could do exactly the same math in this logical framework as we do in our usual ones, and no contradictions would arise.

However, would that really be a wise idea? Wouldn't that just lead to making unnecessary mistakes, sometimes even conceptual ones, when considering that we would be prone to confusing numbers in this system with the numbers that we use normally?

I think language is also important here, not just logical soundness. Especially if we want our intuitions to be helpful.

Just to bring this back to something less abstract again, I will just mention the following:

> However, the core of the argument remains true, we just need to complicate it significantly if we want to remain within the realm of finite machines: instead of saying "there is no TM that can decide if any arbitrary TM halts", we need to say something like "there is no finite TM that can decide if any TM smaller than itself halts in an amount of time less than that TM".

Well, I don't believe the core of the Halting problem to be true, and that's exactly the language problem that I'm talking about: confusing language leads us to making conceptual mistakes.

For example, time is not necessarily relevant here.

I could argue that what the Halting problem really demonstrates is that to analyze whether a finite-state machine (FSM) halts, you need to use an FSM that can have more state than the machine being analyzed (which is why it stops working if you believe you can have infinite state).

This FSM with more state would always be able to decide whether the other FSM halts in finite time, regardless of whether the other machine halts or whether it never does.

In fact, that's exactly what cycle-detection algorithms do, such as the tortoise and hare algorithm.

The biggest problem with finite sets is that most operations don't work nicely in finite sets.

For example, if we take the naturals to be a finite set, and arbitrarily define some number G that is the largest number, then common operations stop being commutative/associative/distributive (e.g. x-y+z is no longer equal to x+z-y, if x>G-z; or x×(y-z) ≠ x×y - y×z). Lots of simple equations stop having solutions at all. The finite rationals also get similar problems. Your models also have all these arbitrary parameters - the largest positive integer, the largest negative integer, the smallest fraction, the largest allowed amount of non-repeating digits in a decimal representation of a fraction - things like these become independent parameters, and can be arbitrarily chosen to be different.

> Well, I don't believe the core of the Halting problem to be true, and that's exactly the language problem that I'm talking about: confusing language leads us to making conceptual mistakes.

But it is - you still can't, in practice, construct a useful program that depends on solving the "finite halting problem", since you will need too much memory/time for anything but the most trivial of examples. If you don't beleive this, than it should be doable for you to create a program that checks whether P=NP if we limit it to programs that can run on, say, an 8086 processor and only use 16 KB of RAM, right?

> The biggest problem with finite sets is that most operations don't work nicely in finite sets.

I didn't necessarily mean to suggest that we should not work with infinite sets, only that perhaps we should not call them "sets" (so as to not confuse them with the finite ones), but rather something else, like "domains" or whatever.

So perhaps you could say that those commutative/associative operations are valid over the domain of natural numbers. But you couldn't say, "X" represents the cardinality of the set of natural numbers, because there's no such thing as the set of natural numbers.

Or, maybe the set of infinite natural numbers and infinite rationals makes sense but the set of real numbers doesn't (as they have different infinite properties?).

I don't know exactly what would be a better solution here, as I'm not a mathematician. I'm only trying to suggest that there might be a better solution than what we have right now, even if it would simply amount to just using different language and not necessarily changing the logical properties of the theory, so as to not arrive at confusing conclusions.

> But it is - you still can't, in practice, construct a useful program that depends on solving the "finite halting problem", since you will need too much memory/time for anything but the most trivial of examples.

But the decidability of the Halting problem is not actually a question of how long it takes for an algorithm to solve it, is it?

The decidability of a problem is a matter of whether it's actually possible at all to construct an algorithm that solves it, no matter how long the algorithm takes to solve it.

That is, whether this algorithm is computable and finishes in a finite amount of steps.

So I will say again that yes, the Halting problem is decidable, as long as you don't use an absurd model to answer the question (i.e. a model that does not represent anything that can possibly be built in our universe even in theory?).

The tortoise and hare algorithm solves the Halting problem for FSMs in a finite amount of time and it only needs twice the amount of storage as the underlying FSM that is being analyzed.

> If you don't beleive this, than it should be doable for you to create a program that checks whether P=NP if we limit it to programs that can run on, say, an 8086 processor and only use 16 KB of RAM, right?

The P=NP is a problem regarding the resources required during computation to solve a given problem, as far as I understand.

I am not entirely sure how exactly this relates to the decidability of the Halting problem when applied to finite-state machines, though.

I mean, it's clear that the currently-known algorithms that solve the Halting problem on FSMs, such as the tortoise and hare algorithm, in the worst case take a time to solve that is proportional to the cycle length of non-halting FSMs.

But also note that these currently-known cycle detection algorithms don't even try to analyze the FSM to decide whether it halts, except by testing their states for equality. This is due to the inherent definition of the cycle detection problem.

So they can definitely be made more efficient, perhaps for a large set of useful FSMs, even, as long as they would be allowed to inspect the FSM's state transition table. I'm not sure how efficient they could be, in theory.

I would be cautious in taking any computational complexity theory results at face value when we know that they use Turing machines as models, which can give you results that are the opposite of the results that apply to FSMs. But I'm not an expert and admittedly, I'm not entirely sure of what I'm talking about here.

Regardless, even if you can trust the computational complexity results, to me this is an entirely different question than the decidability of the Halting problem, which is a "yes/no" problem.

I agree that infinity doesn't exist in the universe, but this isn't a problem for mathematics. Mathematics isn't about what exists in the universe, it's about what exists in the realm of concepts. Some concepts are more interesting than others, sure. Cantor's work made it clear that infinite sets are pretty interesting.

The Flying Spaghetti Monster is also an interesting concept.

It can even be useful as a concept, in certain discussions/contexts.

Should we take the Flying Spaghetti Monster as a core axiom of our theories of physics?

Wouldn't this lead to us logically concluding for example, that there has to exist something else beyond the universe that we know about, even if this is not really true?

I mean, I know that I'm exaggerating and that the analogy is not necessarily very good.

But I'm also not entirely sure how different is the Flying Spaghetti Monster from the infinite objects that mathematicians talk about and that lead us to logically arrive at certain conclusions (that I would argue might not really be true, in terms of things we can understand).

I'm not saying that I'm right and that most mathematicians are wrong, necessarily. Perhaps it's just a linguistic issue, I don't know.

I 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))

But can't Chaitin's constant be described using a finite set of symbols, those symbols being in the set [achinost'] (at least, in English)?

Sure; a simple definition is at https://tromp.github.io/cl/Binary_lambda_calculus.html#Halti...

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

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

If you sort this set after you apply your transformation, what's the number that comes right after pi?

You can begin looking for it knowing just two facts: the last digit of pi, and the magnitude of that digit.

Easy!

[sarcasm]

This 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?

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

> Simply flip the digits over the decimal point, so 0.14159 become integer 95141

This sounds similar to an interesting (and often counter-intuitive) way of writing down numbers called 'p-adic numbers' (although that terminology usually requires 'p' to be prime; in your case you'd want the '10-adic' numbers, since you're using base-10)

See e.g. https://en.wikipedia.org/wiki/P-adic_number (here's a video specifically about 10-adic numbers https://www.youtube.com/watch?v=XXRwlo_MHnI )

“Flip around the decimal”… you haven’t accounted for irrational numbers. The reals are not countably infinite.

Even if they were, pi is not between zero and one, so would not appear in your list.

The rest of your argument is difficult to parse. If you’re interested in this kind of stuff though, I’d really recommend picking some good books on set theory and maybe number theory. Set theory in particular will cover a lot of what you’re talking about.

You can't flip irrationals over the decimal the way you described, because their decimals have infinitely many non-repeating values. You would end up with an infinite sequence of numbers, not a real number.

You mean there aren't infinity large integers? Hmm, that seems weird.

All integers are by definition finite. Positive integers are defined by S(S(S(...S(0)...))) a finite number of times, where S is the successor function. (And negatives in the obvious way.)

Where is 1⁄3? Is it before or after (pi - 3)?

We need to switch to the scheme that converts name/description to an integer for that. If you mean the repeating decimal, I don't know if it's before or after pi because I can't identify (name) their locations.

It's the same argument. If I can accept that there are more reals than reals with finite descriptions, why can't there be integers without finite descriptions/positions?

> If I can accept that there are more reals than reals with finite descriptions, why can't there be integers without finite descriptions/positions?

Because the integers are defined as the finite successors to the number 0 and their additive opposites. See, for instance, the construction section of: https://en.m.wikipedia.org/wiki/Integer

You can start talking about numbers that can't be constructed in this way, but then you've ceased to be talking about the integers.

Is the size of the set of integers an integer?

No, usually the cardinalities of infinite sets are represented by things called aleph numbers: https://en.m.wikipedia.org/wiki/Aleph_number.

But it isn't, in any case, an integer.

Thanks! That to me is the most useful response to my ramblings today!

I believe you are confusing rational for real numbers. Rational numbers really do map to the integers, but I believe I can "break" any purported isomorphism from reals to ints, by taking two adjacent ints and asking what number the midpoint between the corresponding reals map to.

Please be specific. I never said the mapping has nice properties regarding the ordering.

BTW I know rational numbers map to integers, and hence any length tuple can be mapped to integers by pairwise combining them in similar ways. But if any length tuple of integers can map to a single integer, why can't an infinitely long set of integers map to an integer? Like the string of digits in an irrational number represented as a decimal?

The problem with mapping the reals to the integers is that a list of real numbers is infinite in "two directions". Each real can be potentially described with an infinite number of digits, and you can have an infinite list of real numbers (i.e. infinite sequences of digits). This is, I believe, the basis for Cantor's diagonal argument, which is a quite beautiful proof of there being more reals than integers.

https://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

Your method is not a 1:1 mapping of reals to integers, because you can't even define the position of a single irrational number with your method. You don't know the final digit, so you don't know the leading digit in your system. You have absolutely no idea the ordering of literally any pair of irrational numbers in your system.

> It's position is as precise as your definition.

This wand-waving is actually transforming irrational numbers into rational numbers, and so means you are not actually working with irrational numbers. You can't just say "this works with all irrational numbers, like Pi, so long as we call Pi '3.14'."

Pi is not 3.14, so any mapping system that depends on you cutting off your precision at some finite number of digits is worthless.

>> Your method is not a 1:1 mapping of reals to integers, because you can't even define the position of a single irrational number with your method. You don't know the final digit, so you don't know the leading digit in your system. You have absolutely no idea the ordering of even a single irrational number in your system.

That is my point exactly. Why do we accept that there are real numbers that cannot be defined by a finite string of symbols, but there are no integers of that nature.

Getting back to the axiom of choice thing. How do you pick a specific item from one of those ill-defined sets that include numbers that don't have finite descriptions? How do you choose something you can't name? It's absurdity all the way down. ;-)

That did not seem in any way to be your point. You said

> I've never been convinced that there are more reals than integers

I'm explaining that your method of mapping reals to integers is flawed, and so does not prove that reals and integers have the same cardinality.

> Why do we accept that there are real numbers that cannot be defined by a finite string of symbols

We don't accept it. It's easy to prove that it's the case.

I think you are unfamiliar with how R is defined. The traditional definition of R is a completion of Q with respect to the metric |x-y| (getting all Cauchy sequences to converge). That's larger than infinite sequence of decimals.

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

Every integer has a finite number of numerals. Proof: by definition, each natural number is either 0 or a successor to 0. 0 is finite. And if n is a finite length, then n + 1 is a finite length. So by mathematical induction, all natural numbers have finite length. A similar argument covers the negative numbers, so all integers have finite lengths.

Since the decimal expansion of certain rational numbers are infinite (e.g., 1/3 = 0.333...), the strategy of mapping each number between 0 to 1 to an integer by flipping digits over the decimal point does not work for all rationals, let alone all reals.

Don't want to pile on too much, but my attempt at an explanation:

> Simply flip the digits over the decimal point, so 0.14159 become integer 95141

They key here is that both 0.14159 and 95141 contain a _finite_ number of symbols/digits. There are infinitely many numbers like this, but each of those numbers are themselves finite.

The decimal expansion of pi, OTOH, is _itself_ infinite. The decimal expansion of any irrational number is infinite. There are infinitely many of these things, each of which are themselves infinite.

This is the key thing that causes uncountability. Each of the numbers has infinitely many "parameters" that can be tweaked. If you try to produce an infinite (countable) list that contains all of these infinite numbers, I can always tweak a different parameter for each number in your list and be guaranteed to have produced a number that your list missed.

Reply on news.ycombinator.com