Hacker News Reader

> ... then that person rejects the Axiom of Choice.

You're looking at it from a philosophical perspective where people care about whether the axiom is "true" or not. Other approaches to mathematics don't care, because they view its value not in some metaphysical notion of truth but in utility. They might say: this proof requires the axiom of choice and that proof doesn't, without assigning either one any value beyond utility (where utility might be, in some case, just their intellectual edification). I think this is what the article is trying to drive at as well. We can't "accept" or "reject" the axiom of choice based on some philosophical grounds, because those philosophical grounds would need to involve infinities [1], which, themselves, are not philosophical but mathematical. We either choose to use it or not based not on where we come from but on where we want to go.

[1]: The view that mathematical philosophy could be derived from core basic principles outside of mathematics was called Logicism, and was favoured by Bertrand Russell. Unfortunately, mathematical systems without some mathematical (i.e. non-"logical") axioms are quite limited, and almost all of them include at least one mathematical axiom, usually one that is equivalent to the existence of the natural numbers.

>they view its value not in some metaphysical notion of truth but in utility.

Isn’t this a philosophical perspective?

It is a perspective in the philosophy of mathematics that rejects the idea that all of mathematics is necessarily anchored in philosophical truths beyond itself.

> It is a perspective in the philosophy of mathematics

So it is a philosophical perspective…?

Of course. I think you may have misread my original comment, which compared two philosophical perspectives on mathematics, one philosophical perspective that views mathematics as an expression of some truth beyond mathematics, and another philosophical perspective that sees mathematics as a tool to achieve some ends.

> not in some metaphysical notion of truth but in utility.

So one is not metaphysical because it is a tool to achieve ends?

(Sorry, if I come across as argumentative, I don’t mean to. I’m genuinely just curious.)

It is a metaphysical statement about whether metaphysics is important in this instant, rather than being dispensed with in favor of something useful. It's picking a particular metaphysics rather than being bogged down in the meta-metaphysical question of the necessity of metaphysics.

Or at least, that's the way I read it. The question of the value of metaphysics is an open one, which easily comes to dominate other questions if allowed to. I think the OP is saying, "I'm going to make a metaphysical commitment, and let other people worry about whether doing so is good metaphysics." (And there's good reason to think that it isn't -- but it's unclear whether that matters, or should matter.)

Yeah, I misread. Thanks for helping me understand!

For some reason you keep skipping the qualifiers in what I write. It does not say "some metaphysical notion" but "some metaphysical notion of truth". In other words, what matters isn't whether an axiom is "true" or not in some way that is external to mathematics, but what use could be made of that axiom. You did the same above; I didn't write "from a philosophical perspective" but "from a philosophical perspective where ..."

> For some reason you keep skipping the qualifiers in what I write.

My apologies, but I think I’ve understood where I misread your comment. Thanks for being patient!

> Unfortunately, mathematical systems without some mathematical (i.e. non-"logical") axioms are quite limited

What's an example without any axioms? It doesn't seem like you can do anything without say ∀x: x=x (which I believe is reciprocal identity.)

I think Russell would consider that a logical axiom, and it commonly is an axiom of predicate logic with equality. BTW, by "logic", he didn't mean just a specific set of familiar axioms, but any axiom which could be considered "obviously true" and didn't involve numbers specifically. https://en.wikipedia.org/wiki/Logicism

I think in the last example, you need "the set of all integers, except 0, and all their reciprocals", otherwise the answer is well-defined.

One of the many reasons for defining the natural numbers to begin at 1. I didn't even notice they said integers and thought they said naturals.

Is that not the axiom of finite choice, which holds in ZF set theory without AC?

How is it finite? Integers are infinite.

It's Countable Choice, and of course the essence of Countability (why it's our favorite cardinality) is that almost all of our intuition about finite numbers can be correctly applied to countable infinities.

Uncountable Choice (a set for every Real number, a choice from every set) is where thing ago off the rails and ZF looks substantially different from ZFC.

Can't you get countable choice with zf? Countable means there is a bijection to the naturals, so you can always pick the element that corresponds with 0.

No: https://en.wikipedia.org/wiki/Axiom_of_countable_choice

How do you choose the bijection?

The algorithm that executes an element from the set of all algorithms one at a time until an algorithm succeeds to select an element from a set will work on any set and itself?

   a = the algorithm
   A = set of all selection algorithms
   b = any set

   def a(x):
       while True:
           f = a(A) # you have to select an algorithm from the set of selection algorithms
           result = f(x)
           if result is None:
             A = A - f # set of all selection algorithms without f
             continue
           else:
             return result

   a(b) #will always return a result or not terminate for any choice of b?

Obviously there's problems with this because I'm not a mathematician and I'm just making stuff up off the top of my head. But would any one who's an expert care to explain what's the issue with the above?

I'm looking at it and such an algorithm is defined in terms of itself (like a factorial, which is legal) and may never terminate (which also legal because an algorithm selecting the smallest number from all sets that only contain positive numbers will never terminate either).

Wait but then if you look at the code it provably will never terminate because A does not shrink as it recurses.

I think that such an algorithm, if the order of algorirthms tried is random, is almost surely (so with probability 1) never going to terminate.

Moreover, you'd probably want to limit the tries to algorithms that terminate. But that brings you into the halting problem.

You can run a countably infinite sequence of algorithms in parallel and stop when one of them terminates without running into the halting problem. Say you have a set of algorithms, numbered 1, 2, 3, ... and each algorithm consists of a sequence of instructions (with jumps and gotos), where each instruction takes a finite amount of time to run. The algorithm is as follows: run the first instruction for algorithm 1, then the next instruction for algorithm 1, then the instruction for algorithm 2, then 1 again, then 2, then 3, then 1, 2, 3, and 4, and you can see the pattern now. If any of them reaches the halt instruction halt. Even if all but one of these algorithms runs forever, you'll still eventually halt when that one algorithm completes. I believe this approach is called dove tailing

Can you iterate through a set without * selection *? I'm confused about this part. It seems to me in order to use an algorithm from the set of all algorithms you need to invoke the axiom itself.

I think us programmers think in terms of time. But in math there is no time so whether you do things in parallel or procedural is irrelevant. That's why you can discuss infinities in math.

> It seems to me in order to use an algorithm from the set of all algorithms you need to invoke the axiom itself.

Nope, you don't need the axiom of choice to define the sequence of all algorithms. The axiom of choice allows you to order any arbitrary set, but you don't need it for things you can construct an explicit order for, like the natural numbers. In the case of all algorithms, it's somewhat straightforward to construct the set of all of them. You can construct the sequence of all strings, right? You can construct them as "", "a", "b", "c", ... "y", "z", "aa", "ab", ... "ay", "az", "ba", "bb", ... Now, pick a programming language, like C. Given any valid string, you can determine if it is a valid C program in finite time, and if so you can convert it into a set of instructions to use in the dove-tailing procedure in finite time. Take the list of all strings in the manner described above. For each one interpret it as a C program, or if it's got invalid syntax interpret it as a program that immediately halts. Now you've got an enumerable sequence of algorithms. Since C is Turing complete you'll find every single algorithm in that sequence. There will be a ton of duplicates (for whatever notion of equivalence you want to use) but all the algorithms will be there, and in a well-defined order that you can enumerate through.

>Nope, you don't need the axiom of choice to define the sequence of all algorithms.

No. I'm saying selecting an algorithm out of the set of all algorithms.

I'm not saying defining the set of all algorithms.

Putting the set of all algorithms in an order is quite easy. Like the comment above suggests. Just put them in alphabetical / lexicographical order.

Then you don't need to "randomly pick" an algorithm. You just start with the first algorithm in the sequence, and keep going.

As my retort to that common mentioned, he is wrong.

That is still random. You are arbitrarily picking an encoding, (English) in this case. Why not a Russian programming language or Chinese? How did you *select* your encoding out of the set of all encodings?

The act of assigning order to an unordered set is arbitrary. ABC order is a made up concept. It's not numerical, it's an arbitrary language and an arbitrary order that's a by product of human culture. Thus invoking this is at it's essence invoking the axiom of choice. You are arbitrarily selecting an algorithm.

I think you're misunderstanding the axiom of choice, focusing too much on the literal word "choice". Sure, that ABC order is arbitrary, but so are most mathematical constructions! How did I "select" that encoding? By defining it! By your definition of the axiom of choice, literally defining any set at all (besides the null set and the set of natural numbers, which are defined in their own axioms) would require invoking the axiom of choice.

You only need the axiom of choice if you need to pick an element out of a set WITHOUT SPECIFYING which one you are picking. And sometimes not even then. For instance, if you want to prove all elements in a set have a certain property, often you will see proofs take the form "pick an element of that set, assume it doesn't have this property, then by X, Y, and Z we have a contradiction, thus all elements have that property". That doesn't involve the axiom of choice at all, even though a straight reading of that statement makes it sounds like we are making a choice. In truth that proof is saying we can do this with every single element of that set, so you aren't really making a "choice". You only need the axiom of choice when you are, say, stating the existence of a function without defining what that function is. For an example of an actual invocation of the axiom of choice, check out the proof sketch in the wikipedia article on Zorn's Lemma: https://en.wikipedia.org/wiki/Zorn%27s_lemma .

Gödel worried about this, and one of the lemmas leading up to their First Incompleteness theorem is that the encoding doesn't matter, as long as it's a bijection on valid algorithms. (Numbers which code for invalid algorithms, perhaps due to syntax errors, can be ignored.) Gödel also was the one who showed that such encodings are possible and useful in the first place, so the problem of arbitrary encodings started and ended with him.

You can phrase things like Gödel did. For any encoding of algorithms into natural numbers which is bijective (ignoring invalid syntax), enumerate the algorithms as 0, 1, 2, 3, ... using the bijection, and then run them in parallel by taking steps [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, ...] The user provides an encoding, without invoking the Axiom of Choice.

if the set of all selection algorithms is infinite you need the axiom of choice to guarantee that you can even select an algorithm from it.

Yeah I think that's the problem.

Can’t the algorithms be enumerated? For example, you could take their source code and sort them alphabetically.

This is the weird fuzzy part with math.

I can say arbitrary stuff like the set of all sets with positive numbers but when I say the set of all algorithms written in English and C++ suddenly I'm getting too specific. Where is the line drawn?

I’m not sure what you mean. There’s nothing too specific about that.

Your assuming all algorithms are defined in terms of English that's how you can order them alphabetically. English is an arbitrary language that comes from human culture. Same with a programming language. You are defining a set in terms of concepts that are cultural.

Algorithms themselves have no specific order. In order to define enumeration you must first start off by *selecting* which algorithm gets the first enumeration. This is a completely arbitrary choice.

No, I'm not assuming any particular encoding of an algorithm. I'm just assuming by "algorithm" you mean a computable function, and we know there are only countably many computable functions. This is not a cultural notion.

And yes, which particular encoding you decide to use is arbitrary, but the point is that you can enumerate the set of all algorithms, and thus you can select one without needing the axiom of choice.

Your own example used the word "alphabetical." So your example is false because it uses a "particular" encoding.

Try to select an algorithm out of the set of all algorithms without using an encoding. If you must use an encoding, please ensure that it's not a "particular" encoding.

You can't.

The point is all encodings in the known universe are "particular."

Additionally, to even use an encoding you have to *select* and encoding from the set of all encodings.

Yes, I chose one arbitrary method of enumeration. That’s not important to the point, which is that algorithms are enumerable and thus you don’t need the axiom of choice to select one out of the set of all algorithms.

Yes I know that's your point. I'm saying you can't enumerate algorithms without selecting an algorithm.

One way of selecting an algorithm is to select a way to encode the algorithms.

It's easy to see that this is true. You chose an arbitrary example above. Try to do the same without choosing anything arbitrary. You can't.

So to simplify basically the algorithm I wrote above is bad because it's in spirit equivalent to this:

  def a(x):
      return a(x)

The assertion that at least one selection algorithm succeeds without presenting that algorithm _is_ the axiom of choice.

By _assuming_ that program terminates, you are yourself taking the axiom of choice.

If it _does_ terminate, then it's not an axiom anymore it's a proof.

Yeah, this clarifies the logic. So because the algo above doesn't terminate it is not a proof.

The axiom of choice is an assumption that is neither known to be true or false.

ketralnis is right that this only terminates if an algorithm exists, so the claim that this terminates is equivalent to the axiom of choice.

But I'd also add that you can have a choice function that isn't an "algorithm". An algorithm, at least in the sense I'd generally interpret the word, has finitely many instructions and at most countably many steps. If we have uncountably infinitely many uncountably infinite sets, it is possible to have a choice function that can't be described in a finite algorithm.

Like, think about a well-ordering of the reals. If you believe the axiom of choice, then one exists. But you can't tell me what it is, because that would involve handing me infinite amounts of information. And similarly you can't write down an algorithm to produce it, without writing down infinite amounts of data.

> ketralnis is right that this only terminates if an algorithm exists, so the claim that this terminates is equivalent to the axiom of choice.

No my algorithm above will never terminate. There's a recursive call where the input never shrinks and it won't converge on a base case.

It's equivalent to saying

   def f(x):
       return f(x)

which is a pointless (but true) statement. The whole thing is distracting everyone.

Basically ketralnis is clarifying context which is sort of lost with my post. There's an axiom and do you believe in the axiom of not?

If the axiom can be proven then it is not an axiom. But a theorem. What I'm doing here is kind of pointless because we know it's an axiom by definition, the question is whether this axiom is valid or not. Attempting to prove the axiom is a a signal that I'm lacking clarity with the logic here.

Instructions for a Banach-Tarski theorem demo:

1. Find any solid object.

2. Divide that object in infinite, dimensionless fragments.

3. Make as many copies as you want with the infinite fragments.

4. Reform the original object with the remaining fragments.

... I still have fragments please help.

I assume you're joking, but in case anyone thinks your description is accurate, it's wrong in a significant way.

Point (2) is fundamentally wrong in a critical way. The whole point of the Banach-Tarski Theorem is that you only have finitely many pieces. Of course these pieces are composed of infinitely many points, but it's a finite number of "pieces".

Others may find it amusing, sense of humour vary widely. Usually I just shrug and move on, but in the essence of this "joke" you've genuinely misrepresented the entire point.

I tried to joke about how real objects don't have an infinite number of surface points.

This theorem is often quoted as "mathematically-proven way to deconstruct a sphere and build two identical spheres", but this can't translate to reality in any way, it's an abstract thought exercise. Of course, "mathematically-proven way to deconstruct a sphere and build two identical spheres in your imagination" doesn't sound as cool.

For anyone still following, the theorem is perhaps best described like this:

We model spheres as collections of points, and given a collection of points there is a fairly obvious way to model the idea of moving that collection around in a way that reflects moving a physical object. The problem is, given a sphere, we can partition the points into six sets, move those sets around, and recombine them to give us two spheres the same size as the initial one. In a very real sense, in this model we can "cut up" a sphere, then rearrange the pieces to make two spheres. We've doubled our volume.

Clearly this is nonsense, and it shows the limitations of the model. But equally, it tells us something important about the maths we use every day to model buildings, bridges, fluid flow, and more.

All models are wrong, some models are useful. -- George E. P. Box

I would add:

Some things are nonsense, but sometimes the nonsense can tell us useful things about the way the models are wrong.

I don't know if anyone is still following, but thank you for being civil and instructive.

You're welcome, and thank you in return for the constructive dialogue ... it makes a refreshing change, and is very welcome.

Doubling the volume is not so weird, as long as you do not double the mass

But these are of uniform density, so you are doubling the mass as well. To some extent, that's the point of the theorem (and discussion).

For (any subset of)rational numbers there exist many simple algorithms to form an ordering. eg. Take the number is reduced for `(+/-)a/b`. A number is smaller if its `a+b` is smaller. In case of tie number is smaller if its `a` is smaller. Even in case of tie positive number is smaller.

I don't know the proof but there could be no algorithm like that for real numbers.

$<$ gives an ordering over the reals. It's an ordering with a first element that's the tricky bit.

>If you, for example say: "Take the smallest element", then I say "One of my sets is all negative integers, it doesn't have a smallest element."

Why would a set of "negative numbers" not have a smallest element?

Negative numbers are also ordered in a number line (-5 is smaller than -2 for example).

It's the set of all negative numbers. That doesn't have a smallest number, because negative infinity is not a number.

[3] (from OP) directly contradicts this, though I am also very confused why real numbers are somehow unorderable, while the integers are not. https://jaydaigle.net/blog/what-is-the-axiom-of-choice/#fn:3

The set of positive integers starts {1, 2, 3, …} and there are no positive integers smaller than 1. On the other hand the set of positive real numbers has no smallest element, since for any positive real number x, the number x/2 is smaller and still a positive real. It’s not that the reals are unorderable (they are most certainly ordered), it’s that certain subsets of the reals do not necessarily contain a minimum/maximum.

How does it contradict that? The set of negative integers does not have a least element, and neither does the set of negative reals. (But the former does have a greatest element (–1) while the latter doesn’t have that, either.)

Oh dear, I dropped the critical word "positive" from this in my reading. My bad.

> why real numbers are somehow unorderable

They are orderable ... For all x, y in R, either x >= y or x < y.

But R is not bounded (no inf, sup) and therefore has no minimum and no maximum.

What's the consequence of extending the reals with infinities, as my textbook for real analysis does?

That every closed set has a maximum and a minimum.

Relatedly, every set gets a supremum and an infumum. (The first two must be members of the set. The second two can lie outside the set).

Without the extension, you need to make an exception for unbounded sets with the above rules.

It's not just about ordering, but well-ordering. Which says not just that you can put them in order, but that you can put them in order with a first element (one that's always less than all of the others).

So you can have a set like "all real numbers greater than 0". It doesn't have an obvious first element, even though you can always compare any two numbers and say "this one is less than that one".

There may be a non-obvious first element, i.e. some strategy for picking a first element that applies to all sets. That's the Well-Ordering Principle. Which feels false to most mathematicians, but it's equivalent to the Axiom of Choice, which feels true.

This makes sense. I read the set being "all negative numbers" in the sense of a set of numbers all of which are negative, not in the sense "the set that has every negative number".