100 years of Zermelo's axiom of choice: What was the problem with it? (2006)

Yeah, it's important to think of these axioms as choosing the rules of the game, rather than what intuitively makes sense. The real question is if playing the game produces useful results.

How is it different from using ZF as a meta-theory to study ZF(C)? Is there anything special about category theory vis-à-vis ZF as a meta-theory? You're not arguing about ontology or the nature of truth, because you've picked category theory as your ontology just like you could pick ZF or ZFC.

Doesn't "continuous" make all the difference here? AC doesn't contain a comparable limitation, so the analogy doesn't work that week.

I wish that I had specific suggestions.

My overall wish that more people understood why, in intuitionist mathematics, uncountable means "self-referential" and not "more". No infinite set can have "more" elements than any other, because all things that exist are things that can be written down. And therefore there is a single countable list that includes all things that might possibly have any mathematical existence at all. Anything not on that list does not truly exist.

(By internet coincidence, I recently wrote https://math.stackexchange.com/questions/5074503/can-pa-prov... which ends with the beginning of the construction of that list, starting with the Peano axioms. https://news.ycombinator.com/item?id=44269822 is about that answer.)

Of course Formalists simply write down some axioms, start constructing proofs, and don't worry about what it really means. In what sense do uncountable hordes of real numbers that can never be specified in any way, truly exist? It doesn't matter. These are the axioms that we chose, and that is the statement that we came up with.

I have no idea of whether there is a way to formalize or prove the following idea. If there is, it would be good to mechanize it.

All notions about uncountable sets being larger than countable ones, require separating the notion of truth from the reasoning required to establish that truth.

Really cool post! This is an awesome idea and I'd love to see more of these. :-)

Maybe these won't be the kind of thing you are looking for, but here are some gems that would be cool to see formalized, some of which I've been meaning to do myself someday:

- There are many parts of the book "A Course in Constructive Algebra" (Mines, Richman, Ruitenburg) worthy of being formalized, but even just the discussion of "omniscience principles" in the first chapter would be cool.

- I absolutely love Sierpinski's book "Cardinal and Ordinal Numbers", and although I'm not sure it would be considered a book of "intuitionistic mathematics", he is careful enough about pointing out where he uses AoC for parts of his book to be suitable for consideration. The results and exercises in VI.5 "Axiom of choice for finite sets" are probably my favorite in the whole book and would be awesome to see formalized.

- Tarski's Theorem about Choice: https://en.wikipedia.org/wiki/Tarski%27s_theorem_about_choic..., particularly from Tarski's original paper (though it is in French).

- I am not sure about a historical article/source for this one, but formalization of some results about Dedekind-finite and Dedekind-infinite sets (https://en.wikipedia.org/wiki/Dedekind-infinite_set) could be really fun. I find these to be very counterintuitive.

I would suggest Bishop’s Constructive Analysis.

And a plug: I have a formalisation of models of constructive set theory in Homotopy Type Theory here: https://git.app.uib.no/hott/hott-set-theory

That sounds about correct. The naïve interpretation of AC that interprets ∃ as Σ and ∀ as Π amounts to the trivial fact that Π distributes over Σ, which has little to do with any choice principle. If you instead interpret it in setoids, as Martin-Löf does, then the function you get should be extensional with respect to the relevant setoid structures, which is where the power of the axiom comes from.

The modern view on this is homotopy type theory, where types themselves are intrinsically seen as ∞-groupoids (a higher analogue of setoids) and ∃ is interpreted as a propositionally truncated Σ-type (see chapter 3 of the HoTT book). In this setting the axiom of choice says that for any set X, (∀ (x : X). ∥ P x ∥) → ∥ ∀ (x : X). P x ∥ (see section 3.8).

Note that from the perspective of homotopy type theory, Zermelo's axiom of choice is too strong: it is equivalent to global choice (for all types A, ∥ A ∥ → A), which is inconsistent with univalence.

> Disassemble a pea into a finite number of pieces. Then reassemble those pieces to create the sun.

"Finite number of pieces" is a tricky thing. It's a finite number of pieces, sure, but each of those pieces is made of an uncountably infinite number of pieces. Banach-Tarski is a clever way of sweeping an infinite number of dust bunnies under the rug until just the right moment, when it reveals all infinitely many of them in the shape of a pea and claims to have just created them, when in reality, they were actually there all along, hiding under the rug.

For me, Banach-Tarski is just an another version of Hilbert's Hotel, but with uncountable infinities instead of countable ones. Once you accept, in your heart, that infinity is real and is equally deserving of your love and respect as finite natural numbers, then the paradoxicalness of Banach-Tarski melts away.

Essentially the axiom of choice allows for 3-d sets that do not preserve their volume upon rotation/movement.

Such sets, of cause, cannot be constructed or even described as their description will contain infinite number of steps.

Can you really reassemble them into something bigger or just into more copies of the same size?

The number of pieces is finite, but each piece consists of an infinite number of scattered points:

> However, the pieces themselves are not "solids" in the traditional sense, but infinite scatterings of points.

The single most best definition I know is what is on the wiki[0]:

> A choice function (also called selector or selection) is a function f, defined on a collection X of nonempty sets, such that for every set A in X, f(A) is an element of A. With this concept, the axiom can be stated:

> Axiom—For any set X of nonempty sets, there exists a choice function f that is defined on X and maps each set of X to an element of that set.

I like this definition because IMO it is simple, close to the name of the axiom, and you might want to use it in this form, that is, having a set of sets, and taking a choice function on them.

To understand its importance and the controversies around it, you'll need some examples and counterexamples how truthness and provability and knowability (regarding structures, numbers, metamathematics) interact; also what are the views of the majority of working mathematicians and people in other fields using mathematics.

[0] : https://en.wikipedia.org/wiki/Axiom_of_choice#Statement

The Cartesian product of nonempty sets is nonempty.

This is obvious!, you might say — obviously we can just pick one element from each set and be done with it. But the statement that we can pick an element from each set is the axiom of choice.

Note that it's not necessarily simple to pick an element from a set. For instance, how would one pick an element from the set of uncomputable numbers? A human cannot describe said element, by definition. The axiom of choice says it's possible anyway.

The axiom of choice allows you to make infinitely many arbitrary choices.

You don't need the axiom of choice to make finitely many arbitrary choices. Let's say you have a pile of indistinguishable socks in front of you. You want to pick two of them. Well -- assuming that there are at least two of them to pick -- you can pick one, and then you can pick one from what remains. If something exists, you can pick one of it, that's permitted by the laws of logic; and if you need to do that multiple times, well, obviously you can just do it multiple times. But if you need to do it infinitely many times, well, the laws of logic aren't enough to support that.

You also don't need the axiom of choice if the choices aren't arbitrary, but rather are given by some rule you can specify. There's a famous analogy used by Russell to illustrate this. Suppose you have set in front of you an infinite array of pairs of socks, and you want to pick one sock from each pair. Then you need the axiom of choice to do that. But suppose, instead, it were an infinite array of pairs of shoes. Then you don't need the axiom of choice! Because you can say, I will always pick the left one. That's a rule according to which the choice is made, so you don't need the axiom of choice. You only need the axiom of choice when the choices have some arbitrary element to them, where there isn't a rule you can specify that gets things down to just a single possibility. (Isn't the choice of left over right making an arbitrary choice? In a sense, yeah, but it's only making a single arbitrary choice!)

(The axiom that lets you do this, btw, is the axiom of separation. Or, perhaps in rare instances, the axiom of replacement, but the axiom of replacement is generally irrelevant in normal mathematics.)

So that's what the axiom of choice does. Without it, you can only make finitely many arbitrary choices, or infinitely many specified choices. If you need to make infinitely many choices, but you don't have a rule to do it by, you need axiom of choice.

[Edit: Given the article, I should note that I'm describing the role of the axiom of choice in ordinary mathematics, rather than its role in constructive mathematics. I know little about the latter.]

Often it's easy to construct a family of sets representing something of interest. For example, we like to define integration initially as a finite process of breaking the integrand's domain into pieces, computing their area, and summing.

To compute the contribution of some piece indexed i, we measure the size of its domain, call it the area Ai, and then evaluate the integrand, f, at some point xi within that domain, then the contribution is Ai * f(xi).

Summing all of these across i produces a finite approximation of the integral. Then we take a limit on this process, breaking the domain into larger and larger families of sets with smaller and smaller areas. At the limit, we have the integral.

This process seems intuitive, but it contains an application of the axiom of choice---in the limit, we have an infinite number of subsets of our domain and we still have to pick a representative xi for each one to evaluate the integrand at.

It's quite obvious how to pick an arbitrary representative from each set in a finite family of sets: you just go through one-by-one picking an element.

But this argument breaks down for an infinite family. Going one-by-one will never complete. We need to be able to select these representative xis "all at once". And the Axiom of Choice asserts that this is possible.

(Note: I'm being fast-and-loose, but the nature of the argument is correct. This doesn't prove integration demands AoC or anything like that, just shows how this one sketch of an argument would. Specifically, integration normally avoids AoC because we can constructively specify our choice function - for example, picking the lexicographically smallest point within each axis-aligned rectangular cell. Generalize to something like Monte Carlo integration, however...)

Somehow the existing answers don't satisfy me, so here's my attempt. The essence of it is really simple.

The axiom is an obviously true statement: if you have a bag of beans, you can somehow take one bean out of it, without specifying, how do you choose the exact bean. Obvious, right? And that's really it, informally this is the axiom of choice: we are stating that we can somehow always do that, even if there are infinitely many beans and infinitely many bags, and the result of your work may be a collection of infinitely many beans.

Now, what's the "problem"? If you look closer, what I've just said is equivalent to saying we can well-order[0] any set of elements, which must make you uncomfortable: you may be ok with the idea that in principle you can order infinitely many particles of sand (after all, there are just ℕ of them), but how the fuck do you order water (assuming it's like ℝ — there are no molecules and you can divide every drop infinitely many times)?

This is both why we have it — ℝ seems like a useful concept so far; and the source of all notorious "paradoxes" related to it — if you can somehow order water, you may as well be able to reorder details of a sphere in a way to construct 2 spheres of the same size.

[0] https://en.wikipedia.org/wiki/Well-ordering_theorem

Bertrand Russell coined an analogy: for any (even infinite) collection of pairs of shoes, one can pick out the left shoe from each pair to obtain an appropriate collection (i.e. set) of shoes; this makes it possible to define a choice function directly. For an infinite collection of pairs of socks (assumed to have no distinguishing features such as being a left sock rather than a right sock), there is no obvious way to make a function that forms a set out of selecting one sock from each pair without invoking the axiom of choice.

(From Wikipedia but I’ve always found it good)

Not like 5, but High-school Geometry.

If you remember Geometry, there are two ways to prove something:

- By making it (constructing)

- By contradiction (reductio ad absurdum)

During the late 1800s to early 1900s, when math was becoming more formalized, a group of mathematicians had issues with the second method.

From their point of view if you can’t show how to make it, then you’ve not proven that it exists.

Now it turns out that indirect proofs like contradiction requires the law of excluded middle: If something isn’t true, then it must be false (or vice versa).

It turns out that AoC is needed/implied, for the law of excluded middle; hence the objection to AoC; and enables these non-constructive proofs.

https://en.m.wikipedia.org/wiki/Law_of_excluded_middle

Another AoC proof: Prove that an irrational number to a irrational power can be rational.

sqrt(2)^sqrt(2) : If rational, then done.

Else (sqrt(2)^sqrt(2))^sqrt(2) = 2.

QED (and non-constructive).

If you have a set of sets, you can pick one element from each set to construct another set.

This is provable if everything’s finite, but not if you’re dealing with things with bigger cardinalities like the real numbers.

Thanks! The source code is set in Fabrizio Schiavi’s amazing PragmataPro.

https://fsd.it/shop/fonts/pragmatapro/

https://github.com/fabrizioschiavi/pragmatapro

Axioms should capture the rules we can assume without justification.

But in most cases we want them to reflect the rules of the real world in the sense that statements derived from those axioms reflect our observations. That part (reflect observations) can be separated by many levels of abstractions, etc. I would not try visualizing general statements on Lie algebras or spectral theorems, but those abstractions serve the same goal -- help derive conclusions that apply in the real world. My 2c.