What is the Axiom of Choice?

https://jaydaigle.net/blog/what-is-the-axiom-of-choice/

by luu • 5 years ago

182 167 5 years ago

My favourite statement of the Axiom of Choice, from AlienAtSystem via https://www.irregularwebcomic.net/4035.html :

As there are infinitely many sets, instead of going through them manually, you have to find an algorithm [to select an item from each set]. So Person A tells the other player an algorithm to select an element. Then that other player finds a set where the algorithm fails.
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."
Then maybe you say: "Take the smallest element, or if it does not have that, take the largest." Then I say "One of my sets is all integers, which has neither". Then maybe you add: "If it has neither, take the element closest to 0 (in case of tie, take the larger one)". Then I say: "What about the set of all integers and all their reciprocals? It doesn't have an element closest to 0 either."
When Person A gives up and says: "Look, there's some algorithm that does it, right, why do I have to recite it manually?", then that person has taken the Axiom of Choice. If they say "Okay, fine, you win, there's no algorithm you can't find a counterexample to", then that person rejects the Axiom of Choice.

jleahy• 5 years ago

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

lupire• 5 years ago

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.

richardwhiuk• 5 years ago

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.

eeegnu2• 5 years ago

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.

coldtea2• 5 years ago

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

Filligree• 5 years ago

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

YetAnotherNick• 5 years ago

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.

wizzwizz4• 5 years ago

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

pron5• 5 years ago

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

cannabis_sam5• 5 years ago

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

Isn’t this a philosophical perspective?

eeegnu2• 5 years ago

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

shadowlight12• 5 years ago

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.

rocqua3• 5 years ago

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.

Avshalom• 5 years ago

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.

shadowlight12• 5 years ago

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)

ketralnis• 5 years ago

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.

jaydaigle5• 5 years ago

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.

ASalazarMX3• 5 years ago

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.

ColinWright8• 5 years ago

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.

twic7• 5 years ago

So here are a few things that don’t cause controversy:
* If we have one set, we can definitely pick an element from it.

Can we? How?

The point of a set is that it doesn't distinguish between its elements in any way. It's not ordered, there is no special element, etc. So how can you pick one element from a set?

If you pick a total ordering over the elements in the set, then you can easily pick the smallest, or largest. But that's not picking an element from a set, it's picking an element from a specific ordering of that set! You can't do that without coming up with an actual ordering!

Is picking an element from a single finite set something you can build using ZF? Or is it another, less controversial, axiom? What do constructivists think about this? Is there a flavour of mathematics where this axiom is not assumed? What are the consequences of that?

siraben5• 5 years ago

Is picking an element from a single finite set something you can build using ZF?

In ZF it's tautological by the axiom of regularity[0]. If you have a non-empty set X, there is an element y such that y ∈ X and X and y are disjoint.

[0] https://en.wikipedia.org/wiki/Axiom_of_regularity

twic7• 5 years ago

It seems to me that there is a huge difference between "a set X must have an element y" and "given a set X, you can get an element y".

If set theorists do not make that distinction, then that is the answer to my question!

bschne2• 5 years ago

I know next to nothing about set theory, but. If you have a single set, you must know its elements or some rule that defines its elements. You can then just pick an arbitrary element that is part of the set at will and let that be your choice.

Since it's just one set and not a collection of sets, you don't need some general rule that will give you a well-defined element from each set in your collection.

Am I missing something?

veltas4• 5 years ago

I think you can already pick an element.

But what does it mean to pick an element infinitely many times? You have to be very careful about your assumptions there, an inductive proof would only prove you can pick an arbitrarily large number of such elements. To say that you can make a set picking one element each from a infinite collection of sets, even countably infinite, is something you cannot prove inductively. It requires another axiom.

And admitting this axiom suddenly paradoxes like Banach-Tarski are possible.

dandanua2• 5 years ago

The example of equivalence classes of sequences from the article (in the problem with hats) is very demonstrative. If I give you a class somehow – how are you gonna pick an element from it?

twic7• 5 years ago

But how do you pick that one element? Remember, a set does not distinguish between its elements. So if you're going to pick one, you need to introduce some method to do that. Do mathematicians consider "just pick an arbitrary element" sufficient?

If so, why can't you do that to fully order any set? Just pick an arbitrary element - that's the smallest one. Now take the original set minus that element, and repeat. Bingo, an ordering!

Maybe you can? Maybe it's only infinite sets where this doesn't work?

skissane• 5 years ago

Let me give a more concrete example. Take the set of uncomputable real numbers. You can write out a formal definition of that set, you can prove that it is infinite and uncountable. But you can't produce any element of it. So you can't actually pick an arbitrary element of it, since you can't know what any of the elements are. Is there even any general rule you can use to pick out a single element? – you can't pick the smallest or largest element, since for every element there will be a smaller or larger one; nor can you pick the element closest to zero, since for every element there will be one closer to zero, and zero itself is not an element.

I suppose, if one had a Turing machine with an oracle for the halting problem, it could produce some elements of this set. And then you could ask, what is the shortest program which generates an element of this set. And then if you had multiple shortest programs, you could order them lexicographically. So that's a way you could pick out a single element in principle, even though it is impossible in practice.

Another example would be the set of numbers that are first-order undefinable. (Meaning, numbers for which there does not exist any sentence in first-order logic which is true only for that number). There is no way using first-order logic to pick out a unique element of that set. But I suppose there is some number which is second-order definable but not first-order definable, and hence we could use a sentence of second order logic to uniquely locate a member of the set of first-order undefinable numbers.

As a generalisation – you can define a set such that you can't pick out any individual member of it using certain resources. But it seems like there is always some way to pick out a unique member of such a set using more resources (a higher Turing degree, higher order logic, etc). Can you define a set so you can't pick out an individual member of it no matter how much resources you use? I think the answer to that is "no".

nnamtr• 5 years ago

All formulas and statements are expressed in first-order logic. It has no such phrase as "pick". But picking (in the axiom of choice) means: Finding a function that maps every set to an element of this set.

What is a function: It's a set of tuples where every tuple (x, y) means: x is mapped to y. Of course there must be exactly one tuple for every "x".

(Tuples btw are usually a short notion for {{x}, {x,y}}. They exist always by the axiom of pairing. By the axiom of extensionalty, they fulfill the universal property of pairs, i.e. (x, y) = (z, w) iff x = z and y = w.)

Assume x is a single nonempty set. Picking means: Finding a function {x} -> x. But this is easy: ∃y(yϵx) because x is nonempty, and then we can build our function, which consists just of the single tuple (x, y).

It also works for finite sets of sets since you can do it manually n times, the formula just gets longer.

twic7• 5 years ago

Okay so if x is {potato, tomato}, what is the tuple for x, and how did you decide that?

edflsafoiewq• 5 years ago

Constructively, a proof that a set is inhabited is exactly an element of that set, so if we know the set is inhabited we can just pick that element.

OTOH, if we only know the set is non-empty we cannot pick an element from it. Because assume we could. Let P be a truth value and let S={x in {1} | P}. From not not P, prove S is non-empty, so by assumption we can pick an element of it, so it is inhabited. If it is inhabited, then P. We've just proved P from not not P.

siraben5• 5 years ago

Somewhat not well known among all mathematical circles, but Diaconescu's theorem states that the law of the excluded middle follows from the axiom of choice[0]. This means if you wish to work in constructive mathematics (which has great overlap with computer science), not only you must not take LEM as given but also not take choice as given.

There is much to say—mathematically, computationally and philosophically—on the axiom of choice and its variants (countable choice, dependent choice) and subtle interactions with other axioms.[1][2][3]

From my experience most mathematicians accept the axiom of choice (or an equivalent statement such as Zorn's lemma[4][5] or Teichmüller-Tukey[6]) because of its pervasiveness and usefulness in many areas of math, such as completeness of first-order logic, existence of a basis of any vector space, showing products of compact topological spaces are compact, and more.

[0] Diaconescu's theorem https://en.wikipedia.org/wiki/Diaconescu%27s_theorem

[1] Exposition of choice, LEM, etc. in Coq http://adam.chlipala.net/cpdt/html/Universes.html

[2] Choice vs. countable choice https://mathoverflow.net/questions/22990/choice-vs-countable...

[3] Martin-Löf on choice https://raw.githubusercontent.com/michaelt/martin-lof/master...

[4] Zorn's lemma https://en.wikipedia.org/wiki/Zorn%27s_lemma

[5] How to use Zorn's lemma https://gowers.wordpress.com/2008/08/12/how-to-use-zorns-lem...

[6] Teichmüller–Tukey lemma https://en.wikipedia.org/wiki/Teichm%C3%BCller%E2%80%93Tukey...

veltas4• 5 years ago

Why does AoC implying LEM mean you can't use LEM in constructive maths?

EDIT: misread

siraben5• 5 years ago

I said that if you don't want to use LEM in constructive maths you must also give up AOC, since AOC -> LEM.

reuben364• 5 years ago

Constructive mathematics by it's nature does not use LEM. The idea is that proof of existance must be done by construction of the object in question. LEM implies DNE, which means existance can be shown by showing non-existance is not the case.

EDIT: Apologies, misunderstood.

The_suffocated• 5 years ago

Is the existence of basis in every vector space really useful? I think in analysis, people mostly work with Schauder basis rather than Hamel basis. I am not aware of any important result that uses the existence of Hamel basis in an infinite-dimensional vector space. This is not a criticism about your comment, but an honest question.

jerf3• 5 years ago

Unsurprisingly, I'm biased in the direction of the Computer Science flavor of mathematics, which leads me to say: Of course the Axiom of Choice is useful. Why wouldn't an axiom that allows you to wave your hand and produce infinite amounts of information that you have no mechanism to produce any of be useful? Of course it's useful to invoke infinite amounts of information from thin air. Indeed, uncountably infinite amounts of information, or any aleph-X you please amounts of information.

I agree and understand that it's not a matter of "right" or "wrong", but I do find myself looking a bit askance at "proofs" of statements in which a mathematician writes the equivalent of a few kilobytes of proof statements (in a suitable encoding), which has to be paired with an infinite number of unknowable bits, which the mathematician is not only incapable of providing in practice but often incapable of providing even in theory, to be "true". Mathematicians often claim to find the axiom aesthetic; I find it to be quite the contrary. When you look at proofs from an information-theoretic point of view, the Axiom of Choice is literally an infinitely-sized wart on the side of any proof that uses it.

lalaithion• 5 years ago

This isn't necessarily true; you can also limit which sets are valid sets in a way that guarantees that choosing an element from these sets is well defined. For example, the Axiom of Constructibility basically limits which sets exist, in a way that allows you to always use the Axiom of Choice because your sets have a specific fine grained structure you can use to well-order them.

For example, if I were to require "all sets are finite", then the Axiom of Choice is trivial. The Axiom of Constructibility still allows infinite sets (and even uncountable sets), but it's still limited enough that the Axiom of Choice holds.

You can almost think of it as requiring all sets to have source code, and then just alphabetizing the source code in order to pick a set.

myWindoonn2• 5 years ago

Confused about this. Isn't the comp-sci perspective to use the effective topos and computable partial functions? In that case, LEM fails and so must AOC; instead, we have Markov's Principle.

jaydaigle5• 5 years ago

My take on this is that the axiom of choice allows you to produce infinite amounts of information, if and only if you start with infinite amounts of input.

Think about how much information is involved in presenting an infinite collection of sets! When I say even something as simple as "Let x be a real number" I'm already invoking infinitely many bits of information. Things have already gotten weird, you just haven't noticed because we've hidden it.

The axiom of choice is saying something like, okay, we somehow have this infinite pile of information sitting around; now we're allowed to interact with it. And if you don't like that, your problem might be with the infinite amount of information we started with. (Or it might not; yes-choice and no-choice are both totally valid positions.)

But in practice it doesn't matter that much because you never actually do start with infinite amounts of information, and so you don't need an infinite-amounts-of-information processor. But if we have finite amounts of information that we're pretending are infinite to simplify things, we can also process the finite amounts of information and pretend we're processing infinite information.

mxwsn• 5 years ago

I am not a fan of the axiom of choice, and open-minded about truth values beyond true and false. So I'm really curious about the progress of constructive mathematics, regarding proving known results with non-ZNF axioms, and maybe establishing some more "intuitively satisfying" (whatever that may mean) results where ZNF gives subjectively bogus results like Banach-Tarski?

rwallace• 5 years ago

A lot of people blame Banach-Tarski on the axiom of choice. I disagree. I think it's in essence just a variant of the Hilbert hotel, with the axiom of choice merely serving as part of the machinery for this manifestation. In other words, it's just a counterintuitive but true consequence of the nature of infinity. As such, I think any mathematical system that acknowledges infinity, is going to have such counterintuitive results.

PaulHoule2• 5 years ago

I don’t believe it.

Steve Wolfram should grow some balls and say he doesn’t believe it either.

soVeryTired• 5 years ago

I don’t think it’s a question of ‘belief’. AOC is logically independent of the other ZF axioms: you may find it aesthetically ugly (a viewpoint I’m sympathetic to). But you can’t disbelieve it any more than you can disbelieve Euclid’s parallel postulate.

naveen993• 5 years ago

Interestingly politicians (like AOC) are also independent of logic.

PaulHoule2• 5 years ago

But I don't have to use it, or I can deprecate it.

Particularly I think those "real" numbers are phony compared to the integers and rationals. (At least the latter have names)

xiaodai• 5 years ago

What's yellow and equivalent to the Axiom of Choice? Zorn's lemon

nixpulvis10• 5 years ago

Best quote so far:

If we have infinitely many pairs of shoes we don’t need the axiom of choice, since we can just take the left shoe from each pair; but if we have infinitely many pairs of socks, we do need the axiom of choice.

- Bertrand Russell

So randomness seems like a good fit for "choice" here, no? Or maybe call it ambivalence, or indifference. If the objects are truly unidentifiable, can it possibly matter which one you choose?

As the argument surely goes...

lmm• 5 years ago

The original statement of the axiom I heard was "it's possible to make an infinite number of arbitrary choices" - I think that's a good word for what you're getting at. Of course it doesn't matter which you choose - the axiom doesn't tell you anything about which you can choose - but whether you can choose at all is important. E.g. Hilbert's basis theorem relies on the idea that given an infinite-dimensional space you can always "start somewhere" - it doesn't matter specifically where, but it matters that you can pick a specific point in the space to start from.

(The first journal he submitted it to rejected the paper with the comment "this is not mathematics, this is theology")

nixpulvis10• 5 years ago

The axiom of arbitrarity has an interesting ring to it... slightly avoiding the theological connotation, while being a bit bleak.

Anyway, I hope they gave him a Ph.D for that comment, lolol.

Oh and yikes, did Hilbert just bring roots of polynomials into the mix?

siraben5• 5 years ago

So randomness seems like a good fit for "choice" here, no?

The axiom of choice is exactly the thing that tells us that we can make "random" choices. The way set theory works is that you have axioms to talk about intuitions of sets. So you might say that such a reasonable intuition is that we can make "make unlimited random choices", but this is exactly the axiom of choice!

It's not about a choice from an infinity but an infinity of choices.

Ostrogodsky• 5 years ago

I have always thought that Mr Russell is wrong with that cheeky quote. With the socks you also dont need the AOC. Why? because if you have a pair of identical socks (I think that was what Russell had in mind) then effectively you have a set of cardinality 1.If the socks are different, choose the lightest, if there is a tie between them choose the longest, and so on,if for all the tests the socks are tied declare them the same and back to point 1.

This is my preferred quote about the AOC:

The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?

Jerry Bona. https://en.wikipedia.org/wiki/Jerry_L._Bona

naveen993• 5 years ago

Atoms are able to select which indistinguishable electrons will fill the lowest energy orbitals.

nixpulvis10• 5 years ago

Or might this imply that the electrons are actually distinguishable in some way? Or maybe I should re-phrase; could each electron actually have some (possibly hidden) identity?

comicjk• 5 years ago

I don't think they do. The electrons are indistinguishable - there is no "which" and no need for selection.

shadowgovt5• 5 years ago

It can definitely matter---if I mutate one of the socks and the mutation doesn't show up on the other, I've got a problem if I'm assuming equivalence is equality.

I suspect that's key to why the axiom of choice has to be an axiom (and how this may pop up from time-to-time in the realm of computer science problems).

nixpulvis10• 5 years ago

How can you mutate it if you can't select it?

patrickthebold• 5 years ago

My favorite quote:

The Axiom of Choice is obviously true, the well-ordering principle obviously false, and who can tell about Zorn's lemma?

[1]https://en.wikipedia.org/wiki/Jerry_L._Bona#Quotes

jodrellblank2• 5 years ago

Why can't we take the left sock from each pair?

bmm6o• 5 years ago

Because there isn't a left/ right distinction with socks.

ColinWright8• 5 years ago

Less comprehensive, more specific:

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

Also submitted as a separate item:

https://news.ycombinator.com/item?id=27855143

Broadly (and as this article explains), AC says that given any collection of non-empty sets, you're allowed to "choose" a set that contains one thing from each of them. In set theory terms, the "product" of non-empty sets is non-empty.

This has some uncomfortable consequences.

rssoconnor2• 5 years ago

To build upon the "Just relax" section: by Shoenfield's absoluteness theorem[1], if ZFC proves some Sigma^1_3 statement, then ZF also proves it. In particular, the Axiom of Choice has no arithmetic consequences, and thus has no effect on number theory, nor what you are able to prove about the correctness of any particular algorithm, etc.

[1] https://en.wikipedia.org/wiki/Absoluteness#Shoenfield's_abso...

jaydaigle5• 5 years ago

This is super cool and I wish I'd known about it before writing the piece; I'd have been comfortable being a lot more muscular in the conclusion. This seems like it makes precise my suggestion that the axiom of choice only matters for aggressively infinite and unphysical statements.

hsn9154• 5 years ago

Why is it only a problem when you have to choose from an infinite amount of sets? Why isn't the problem that you can get an infinite number of sets in the first place?

Twisol• 5 years ago

If you allow yourself the infinite set of the natural numbers, you can pretty easily get an infinite set of sets. For instance, for every natural N, take the set of naturals less than N. Or greater than N, if you'd like an infinite set of infinite sets.

As the article notes, these particular infinite families are easy to produce a choice function for: just take the least element of each set. But not all infinite families have enough determined structure for that kind of rule.

If we tried to make it impossible to construct an infinite family of sets, we'd have to disallow relatively reasonable families like the ones I described above. Those are pretty useful, though, so it makes sense to address the problem further downstream.

(I suppose another avenue is to try to isolate the features that make the above families "reasonable" and others unreasonable, so that only reasonable families can be constructed. That seems somewhat fraught, though.)

hsn9154• 5 years ago

What's wrong with just choosing a random set element?

tel• 5 years ago

It happens regularly when, surprise, you deal with infinities in some other place.

A good, fairly intuitive example is integration where, I think, it's common to prove convergence using AoC in the multidimensional case.

More or less, you want to integrate a function over, say, a square. We'll do it with a generalization of the Riemann sum by arbitrarily dividing up that square into little squares, measuring the function at one place in each square, multiplying the areas by those measurements, and summing.

Then we take that process to its infinite limit. We have to be smart here, but we end up with an infinite set of contiguous pieces of our original square. Or, an infinite set of sets. We'd like to measure our function once from each of those pieces, so we need to choose one point from each piece. Which is easily dispatched with AoC.

(In 1-dimensional integration, each subdivision of the domain has a total ordering, so you don't necessarily need AoC. Technically my example of a square also has a total ordering, so we could get away with not using AoC, but as you start to twist coordinates in the domain space more and more you can imagine places where seeking out an ordering of the space might be challenging. But no matter, AoC still works!)

ColinWright8• 5 years ago

Consider all the "real" numbers x that are in the range 0 <= x < 1. We can talk about what the real number are separately, but you can think of them as being infinite decimals starting with "zero point ...". We consider two decimals to represent the same number if one ends with all 9s and the other is identical except for the last non-nine number, and has "n+1" in that place, then all zeros. So these decimal sequences represent the same number:

  0.35578439999999999999...
  0.35578440000000000000...

OK, now say that two of these numbers are related, they are in the same family, if their difference is a rational number. So these numbers are all related:

  0.35578440000000000000...
  0.45578440000000000000...
  0.85578440000000000000...
  0.35578233333333333333...

... and so on. These number are all in the same family. We can show that if a is related to b, and b is related to c, then a is related to c ... being in the same family is transitive.

There are infinitely many families.

Now suppose that there is a council meeting, and every family needs to send one representative. To do so you need to choose one number from each family, and it's not clear how to do that. I invite you to try to think of a rule that works for all families.

So to choose one number from each family we need the Axiom of Choice.

hsn9154• 5 years ago

I understand the idea that real numbers are uncountable infinite. (there's an infinite number of real numbers between any two random real numbers).

My question is: why is it problematic only when you have to choose?

I mean, what's wrong with choosing a random element from every set? Why do you need a rule?

Where is the "problem"?

rssoconnor2• 5 years ago

If you have a finite number of non-empty sets you can construct a choice function by induction. Of course induction won't get you beyond a finite amount of sets.

CompMan411• 5 years ago

Veritasium describes a similar situation (not the AOC); a hotel that has infinite rooms and what happens when an infinite number of buses each with an infinite number of guests pulls up.

https://youtu.be/OxGsU8oIWjY

jkhdigital2• 5 years ago

Similarly, if we could prove the axiom of choice from the ZF axioms, we would have to either accept it as true, or completely rework all the foundations of math.

And the footnote following this statement:

At the beginning of the 20th century, Bertrand Russell and others found deep contradictions in the naive version of set theory in use at the time, and the ZF axioms were developed to avoid those problems. But we’d rather avoid doing it again.

My understanding is that the “constructive” mathematicians objected strenuously to these proposed foundational “solutions”. It’s starting to look like they may have been on to something, as there is an ongoing effort (since 2013 at least) to recast the foundations in a manner that accommodates both traditional and intuitionistic approaches.

Short anecdote to confirm that this might gain traction: I’m a comp sci PhD student (focus on cryptography) and just yesterday I met with a math professor to ask her to serve on my advising committee. I had some brief run-ins with Homotopy Type Theory (the proposed “new foundations”) and was hoping she might be familiar with it—as it turns out, some of her own students had recently convinced her to start a weekly jam session where they gradually work through the HoTT textbook. She invited me to join them and I eagerly accepted :-)

hebrox• 5 years ago

Is this [1] perhaps the book you’ll work through?

[1] https://homotopytypetheory.org/book/

jkhdigital2• 5 years ago

Yes, exactly. She actually had a physical copy of it

dandanua2• 5 years ago

To me, the Axiom of Choice is absolutely natural – if we can pick one element of a set then we surely can pick elements from a collection of sets, who cares that this collection can be infinite.

The problem with this axiom is that it can't be formally proven from ZF axioms. But there are a lot of other natural things that can't be proven in ZF. For example, the consistency of ZF can't be proven in ZF due to Godel's incompleteness.

shadowgovt5• 5 years ago

Is there a missing "deterministically" in the axiom of choice statement?

I can imagine the common-sense "Of course you can choose one element" assumption breaks down if we add the constraint that you need to in some way be able to have another actor choose the same element. Because for an uncountably-infinite-sized set of uncountably-infinite-sized sets, perhaps there is no way to label individual elements such that if I choose A, someone else can also choose A (how will we know they're the same A?).

thethimble• 5 years ago

Ah this is super helpful. I’m here stuck thinking “just pick any element at random”. Needing to have deterministically consistent pickings from infinite sets makes the problem clear and much more interesting.

shadowgovt5• 5 years ago

I think that's why the "infinite socks vs. infinite shoes" are mentioned---because the socks are equivalent so you can't tell by the 'label' which one you grabbed.

jaydaigle5• 5 years ago

But what does "picking at random" mean? If you think it's obvious that you can just make infinitely many random choices at the same time, you're endorsing the axiom of choice.

(If you think you can make one random choice at a time, you're endorsing the axiom of finite choice, which is just true. Determinism doesn't matter here, but "at the same time" matters a lot.)

shadowgovt5• 5 years ago

Excellent! That's the piece of the puzzle I was missing. Thank you!

antonzabirko3• 5 years ago

Let’s assume there is a first person in the line, so it’s not infinite in both directions; you have infinitely many people in front of you, but only finitely many behind

Is this even possible? One of the premises in the article. Won't it be infinity backwards for the nth person?

magneticnorth2• 5 years ago

They're just describing a set of people you could consider ordered by positive integers. The first person has no one behind them, the nth person has n-1 people behind them

antonzabirko3• 5 years ago

But how can that hold when you're approaching infinity? It would only apply to sets finite in both directions.

bvoq• 5 years ago

Really good article.

You don’t have to explain how you’re choosing elements. We’ll just assume you can make it work somehow.

Very interesting remark. The way I think about it now after reading your article is: If you prove something with the axiom of choice, all you need to do is provide an ordering to get practical results from it. If you fail to do so, oh well.

That being said, I don't think you need R (the reals) for practical applications, countably infinite sets like IQ (intervals over Q) are enough and the well-ordering rule doesn't seem paradoxical anymore (countably infinite sets can be ordered as there is a bijection to N).

Example: Pi can be approximated arbitrarily close with a lower and upper bound on Q. The functions used to derive the lower and upper bound with arbitrary precision (also a number in Q) are Pi in this sense

iammisc• 5 years ago

Interesting article... The derivative problem is particularly enlightening I think. A derivative is a limit. Thus the answer you get for a derivative is also a limit.

For example, if you have the real speed of a car at every point in time as well as the position, then nominally, in infinite world, the speed is just the derivative of the position curve.

But if you are in finite world, then the derivative curve in infinite world is the limit of the speed curve (and note that limit does not mean upper bound).. it just is a useful tool for reasoning what will happen if you take a more fine grained set of measurements.

For some fineness of measurement, there will be a point at which your observed speed curve is always within epsilon of the ideal one.

Good article

dwheeler• 5 years ago

It's interesting to look at how people have handled the axiom of choice in Metamath, since the axiom of choice has long had some controversy.

Metamath lets you state your axioms, then show that proofs build from their axioms. Each such collection of axioms & proofs is called a "database". There are Metamath databases that build on intuitionistic logic <http://us.metamath.org/ileuni/mmil.html> and New Foundations <http://us.metamath.org/nfeuni/mmnf.html> among others.

The largest Metamath database by far uses ZFC (Zermelo-Fraenkel Set Theory with the Axiom of Choice). That's the Metamath Proof Exporer (MPE) database: <http://us.metamath.org/mpeuni/mmset.html>. But even in that database, it's avoided where possible. Its conventions say, "We prefer proofs that depend on fewer and/or weaker axioms, even if the proofs are longer. In particular, we prefer proofs that do not use the axiom of choice where such proofs can be found. The axiom of choice is widely accepted, and ZFC is the most commonly-accepted fundamental set of axioms for mathematics. However, there have been and still are some lingering controversies about the Axiom of Choice. Therefore, where a proof does not require the axiom of choice, we prefer that proof instead. E.g., our proof of the Schroeder-Bernstein Theorem (sbth) does not use the axiom of choice. In some cases, the weaker axiom of countable choice (ax-cc) or axiom of dependent choice (ax-dc) can be used instead." <http://us.metamath.org/mpeuni/conventions.html>

dkarl• 5 years ago

The article leans pretty hard on the hat problem to show that the Axiom of Choice has intuitively unacceptable consequences, but I don't see why the solution is so "ridiculous," as they put it. Here's one "intuitive" way of looking at the problem: every person in the line sees an infinite number of hats in front of them, but not the finite number behind them. Intuitively, they see 100% of the information in the problem. The amount of information each of them can see is infinite, and the amount they can't see is finite. Is it so strange then that they only make a finite number of wrong guesses, and an infinite number of correct ones?

I think the article artfully uses a framing of the problem that hides the inherent, inexorable alienness of infinite sets under a familiar-seeming surface just long enough for it to come bursting out in the solution. It's a trick of timing. If your brain lingers on the problem long enough, you realize that the problem itself violates our ordinary intuitions, independent of the solution. The idea of an infinite number of people agreeing on and memorizing representative members of R^N from each equivalence class and then determining the relevant equivalence class by reading an infinite number of real numbers from an infinite number of hats is completely fantastical. How could any solution to this problem not be nuts?

More to the point, if the problem is presented without a bonkers framing that already violates our intuition, is the solution from the Axiom of Choice still counterintuitive? I didn't find it to be so when I first encountered it in class. Maybe the intuitiveness depends entirely on the metaphor used to bring intuition to bear.

jaydaigle5• 5 years ago

I'd agree with this entirely, honestly. (Including the sleight-of-hand I'm engaging in to make things seem exactly the right amount of weird; see footnote 14.)

Infinity is so weird that it's really hard to agree on what infinity "should" look like. And the axiom of choice only matters in situations where the weirdness of infinity really kicks in.

So yeah, some people look at the whole list of AoC equivalents and think they all seem pretty reasonable. And other people look at the list and think none of them seem that plausible. And a lot of us are split, and find some of the claims obviously true and others obviously false.

One of my goals in this piece was to try to let everyone see both sides of this: why you might find the axiom compelling and why you might find it troubling. And then to offer a pragmatic resolution at the end, which is basically another take on what you just said.

What is the Axiom of Choice?

Related Stories