Hacker News Reader

Comment by jiggawatts | Hacker News Reader

The Axiom of choice has never felt completely self-evident to me. E.g.: what if you have sets where the elements are non-computable? How do you "choose" objects that cannot even be named?

Something like: "the set of all programs that cannot be proven to halt" and the like can be used to create pathological sets where the set itself obviously exists, but you cannot name any of the members.

Actually, an ever better example is: "The set of reals that are not the solution to any equation that can be written with a finite number of symbols." -- an infinite set that has no nameable members!

View on HN

> the set of all programs that cannot be proven to halt

That's easy: pick the TM which is minimal according to some lexicographic ordering on the specification of TM's. That's not computable (obviously) but it's perfectly well defined.

> The set of reals that are not the solution to any equation that can be written with a finite number of symbols

Yeah, that one is harder :-)

(I would simply say "The set of numbers that cannot be described by any finite number of symbols" in order to short-circuit arguments about what constitutes an "equation" and whether or not Chaitin's constant is the solution to some equation.)

Those are just subsets of R though (though I think your last example would take more work to make rigorous, if it's even possible).

The weirdness of the axiom of choice only really comes through when you consider bigger and bigger collections of sets.

For example:

- sets indexed by the natural numbers: S_1, S_2, ... It seems totally reasonable that you should be able to make a new set by picking something from the first set, something from the second set, etc

- sets indexed by continuous time (i.e. real numbers). Here it's a bit less 'obvious'. If I have sets S_t for _every_ time t > 0, can I really make choices 'fast' enough? What if the sets are so unstructured that I'm forced to stop and look at each set in turn to make my choice?

- sets indexed by the power set of the real numbers. If you weren't convinced that I'd struggle to pick elements of S_t for all t > 0, what if I had to make a choice for every _possible combination_ of real numbers, infinite or otherwise?

I feel like the last example demonstrates how powerful the full axiom of choice actually is.

NB - I'm a dilettante rather than an actual logician, so there may be mathematical inaccuracies here.

> Those are just subsets of R though (though I think your last example would take more work to make rigorous, if it's even possible).

You could form e.g. the non-algebraic reals, which is almost all of the reals.

> sets indexed by the power set of the real numbers. If you weren't convinced that I'd struggle to pick elements of S_t for all t > 0, what if I had to make a choice for every _possible combination_ of real numbers, infinite or otherwise?

To the extent to which you can form that indexed collection of sets in the first place, surely you can form a similarly indexed collection of elements of them the same way. How can you say you've formed a non-empty set if you can't select an element of it? If we permit ourselves to form this indexed collection "lazily", surely we can do the choice "lazily" as well. (Just my intuition about these things)

An alternative formulation of the axiom of choice: The cartesian product of a collection of non-empty sets is non-empty.

It sounds like you're adding an additional constraint though. By requesting all the members of each set to be able to be named, it seems like you're restricting the sets to be countable.

> E.g.: what if you have sets where the elements are non-computable?

That includes the unmodified real numbers.

I think your second set doesn't exist (exactly like the set of all sets doesn't exist) under the axiom of choice, for I can use the axiom of choice to select an element, hence giving it a name :). I took some liberty with the allowable names, of course.

You still have a point, though.

> Actually, an ever better example is: "The set of reals that are not the solution to any equation that can be written with a finite number of symbols." -- an infinite set that has no nameable members!

That's not a good example; the problem you're creating is due to sloppy use of language, not any cleverness in the definition.

All real numbers, and all numbers of any other variety, can be written with a finite number of symbols. That's what it means to give something a name.

> All real numbers, and all numbers of any other variety, can be written with a finite number of symbols.

This is false. In some sense, there exist numbers that can't be referred to. We can refer to the set of real numbers as a whole, but not some of the elements. https://en.wikipedia.org/wiki/Definable_real_number

But then there are issues with defining "definable numbers", which complicates things by a lot. https://mathoverflow.net/questions/44102/is-the-analysis-as-...

Apparently by “finite number of symbols” he means, for example, {0 1 2 3 4 5 6 7 8 9 .} but he allows the representation of a number to contain infinitely many of them.

> All real numbers, and all numbers of any other variety, can be written with a finite number of symbols. That's what it means to give something a name.

Counter-intuitively, this is not true.

The vast, vast majority of real numbers cannot be named, not even in principle. Their definitions would have to be infinitely long. Or to put it another way, no matter how close two named numbers are, there is an infinite number of reals in between them. If you say, okay, sure, but some of those might be named, then pick the two closest and then there is still an infinite number of other reals in between those two!

Another way to look at it is that the amount of information (measured in bits) between any two real numbers is literally infinite. If the reals were represented with binary digits, then a sequential subset of them would have a common finite prefix, and then all possible infinite bit strings would be the suffixes!

> The vast, vast majority of real numbers cannot be named, not even in principle. Their definitions would have to be infinitely long.

So what? That doesn't stop them from being named.

Usually definitions are considered to be finite. Otherwise yes you can just name a number by enumerating its decimals but what's the point.

Edit : actually does not even work, courtesy of the Chaitin's numbers

You're using "being named" in a very unusual sense. Most people would consider you not to have named something if you're literally never allowed to stop speaking (or writing) the name. Most reals "have infinitely long names" under your definition, and there is no finite time at which you've distinguished between reals with the same initial segment of "name", so really what's the use of the naming scheme at all?

(For a more compelling argument, the equality of real numbers is uncomputable, so it must be impossible to name them. If we could name them usefully, then we could determine equality by asking which ones had different names.)

> You're using "being named" in a very unusual sense.

No, I'm not.

> Most people would consider you not to have named something if you're literally never allowed to stop speaking (or writing) the name.

What's the connection? Names do not completely describe their referent. They're names. I know someone named Ko. Given that name, what can you tell me about Ko?

Naming a number in mathematics has different rules to assigning names to objects in the physical world.

You can "name" a number such as: "a positive number, that when multiplied by itself, the result is 2".

This is a finite statement that requires only a handful of 'bits' to represent, but it exactly and uniquely identifies the square root of two. If written with decimal digits, then the square root of two would require an infinite number of digits, but it can be defined ('named') with a finite number of bits.

It turns out that this is a rare property for real numbers. The vast majority do not have a shorthand name like this, only the infinitely long description exists.

What does naming have to do with AC though? This seems completely tangential to the axiom. It’s about the nature of sets, not the semantics of how you make the selection and reference it.

AC says: if there is a set of non-empty sets y with length x, I can construct a new set z of length x by taking a member from each set in y.

How does being able to name the constituents z or any member of y matter to the logic of the axiom?

This is all in response to a comment which basically said "why do people think AC is obvious - if you can't even name all elements of the set, why would you expect to be able to choose them". (Which is handwavy, of course, and leads to the wrong intuition about uncountable-but-well-ordered sets, and depending on how you look at it it may even lead you to conclude that you can't ever choose even a single element from an uncountable set.)

Honestly, I really am trying, but as far as I can see you are using the word "named" in a sense that allows most numbers to be called "0". I really can't see how your words make sense given any other definition. Is that correct?

That is essentially correct, and we actually do call many different numbers "0" in different contexts, but it's not necessary for any two numbers to share a name this way. You can give them all unique finite names with an infinitely large alphabet if you prefer.

You might consider that in the existing Chinese writing system, 口 and 囗 are distinct symbols.

It's true that any real number can be written with a finite number of symbols. In fact, I can write any real number x with exactly one symbol, namely x, if I define x to mean that particular real number.

Now if you fix a particular formal language for defining real numbers, with a finite alphabet, then the language only has countably many words, hence there are reals not definable in the language. But the notion of "definability" here is not independent of the choice of formal language.

So "choosing an undefinable real number" amounts to "choosing a real number not definable in L", where L is some fixed formal language---and this isn't particularly hard to imagine; given a specific L, you can probably quite concretely construct a real number not definable in L.

> All real numbers, and all numbers of any other variety, can be written with a finite number of symbols. That's what it means to give something a name.

This is untrue and not particularly hard to prove by contradiction.

Suppose every elements in R can be named by a finite number of symbols.

You can build a bijection between R and the names of its elements (by definition a name points to a unique element and if elements have multiple names, you can easily well order a finite number symbols by building a lexicographic order and only consider the smallest name).

Or, you can also easily build a bijection between a finite number of symbols and N. That's just an encoding like ASCII or UTF-8. Therefore, the set of names is countably infinite.

Yet R is uncountable (see Cantor's diagonal argument).

Therefore, by contradiction, there has to exist elements in R which can't be named by a finite number of symbols.

> Or, you can also easily build a bijection between a finite number of symbols and N. That's just an encoding like ASCII or UTF-8. Therefore, the set of names is countably infinite.

You've confused two different senses of "a finite number of symbols". The requirement is that it takes a finite number of symbols to write down any given number, not that it takes a finite number of symbols to write down every number at once. (Though in fact that also takes a finite number of symbols; it is the precise meaning of ℝ.)

Symbols are, in their simplest interpretation, bounded two-dimensional curves; there is no danger of running out of them before we run out of numbers.

Reply on news.ycombinator.com