The Axiom of Choice is Not Controversial

[-]speck14477h74

Now, where did the weirdness come from here. Well, to me it seems clear that really it came from the fact that the reals can be built out of a bunch of shifted rational numbers, right? But everyone agrees about that.

I do not think everyone agrees about that! I think that people who reject AoC would say "sure, any real number can be a shifted rational, but not all of them, there's just no reasonable procedure which does this for the entire set at once."

[-]Dalcy2h*50

My understanding is that yes, axiom of choice (or more generally non-constructive methods) is convenient and it "works", and if you naively take definitions and concepts from those realm and see what results / properties hold when removing the axiom of choice (or only use constructive methods), many of the important results / properties no longer hold (as you mentioned: Tychonoff, existence of basis, ... ).

But it is often the case that you can redevelop these concepts in a choice-free / constructive context in such a way that it captures the spirit of what those definitions and concepts originally intended to capture, and yes it is harder this way, but 1) doing so often lets one recover the "morally correct" equivalent of those results / properties that do in fact hold in this context, and more importantly, 2) doing so has a lot of conceptual value.

For example, equivalent definitions become non-equivalent (such as finiteness; trying to do computable analysis and make sense of the intermediate value theorem in this context leads to new ideas like locale theory, abstract stone duality, overtness (dual of compactness, which is trivial classically), etc) where each has different and new interpretation, and the role of computability and approximation is made explicit which requires bringing in new / additional mathematical structures, etc. Also, many classical theorems have their choice-free / constructive equivalent, eg Tychonoff's theorem for locales (arbitrary coproduct of compact frames is compact - no axiom of choice required to prove!) - and all of this gives us new and sometimes deep insight about the concept that would have been overlooked in the classical realm^[1].

To put it differently: Choice turns structure into property. Without choice, we can instead treat those structure as additional data. This lets various theorems re-emerge, often in many non-equivalent forms - and this is good.

^{^}
I have only heard of these examples (I am not at all familiar with them) in the context of constructive / computable analysis, but I expect this to be a lesson that holds broadly throughout mathematics (and more narrowly: that it is possible to come up with a "morally correct" choice-free equivalent of the theory that in its current form crucially depends on choice, and that this gives new conceptual insights), and this not having been done already for some subject X is more of an issue of lack-of-mathematician-years put into it.

[-]tailcalled3h20

From a computationalist semantics perspective, the axiom of choice asserts that every nondeterministic function can nondeterministically be turned into a deterministic function. When the input space has decidable equality (as in countable choice), that is easy to imagine, as one can gradually generate the function, using an associative list as a cache to ensure that the answers will be consistent. However, when the input space doesn't have decidable equality, this approach doesn't work, and the axiom of choice cannot be interpreted computationally.

Many of the "pathologies" when rejecting choice have similar computational problems as choice does, so bringing them up doesn't really disrupt this argument.

[-]tailcalled2h20

Many of the "pathologies" when rejecting choice have similar computational problems as choice does, so bringing them up doesn't really disrupt this argument.

Example: Let P be some proposition. Theorem: If every vector space has a basis, then . Proof: Define a vector space $V = Q / \sim$ where $x \sim y ⟺ P$ . Let $B$ be a basis over $V$ . Express $1 = \sum_{i = 1}^{n} b_{i} c_{i}$ in this basis. If $n \geq 1$ , we have a basis element $b_{i} ≁ 0$ , and thus $\neg P$ . Otherwise, we know $1 \sim 0$ and thus $P$ .

^{^}

Although this is debatable, the axioms of power-set and infinity aren’t that constructive.

^{^}

N.B. on consistency-strength grounds, ZF is consistent iff ZFC is consistent, so there’s no grounds to reject on the grounds of trying to reduce consistency-strength requirements.

^{^}

Or the history of the philosophy of maths — take your pick.

^{^}

Which means, very simply, there is no way to assign to the collection of subsets of G a function μ such that μ(G) = 1 and for any subset of the group A and any element g in the group, μ(A) = μ(gA). For example, for finite groups it is easy to see that they’re amenable, for each subset A, you just take μ(A) = |A|/|G| (the size of A divided by the size of G).

^{^}

Not in the sense that more groups are provably non-amenable, in the sense that fewer groups are provably amenable.

^{^}

Note that you need at least 3 dimensions here, since in 2 dimensions there’s “not enough space” for the free group to be realised.

^{^}

A+4 here is just the set of every element in A plus 4. So if our original set was [0,1] our new set would be [4,5].

^{^}

That is, there is no number that is in A and in B. A and B are entirely “disjoint.”

^{^}

Exercise left to the reader, but you can take it on faith if you prefer!

^{^}

Note for pedants: disjoint sets.

^{^}

Note, this is not quite right. It only occurs in Solovay's model for countable infinities, but does occur for uncountable infinities and for certain sets (not the integers, since they have an ordering which allows us to make a choice, the linked post is incorrect about that claim).

LESSWRONG
LW

LESSWRONG
LW

20

The Axiom of Choice is Not Controversial

20

20

Why do people reject the Axiom of Choice?

Why paradoxes are not that bad

Banach-Tarski Paradox

Vitali sets

Why we should keep the axiom of choice?