[fmap]

The point is that there is one ordering in which every subset of real numbers has a minimum.

For the rational numbers, this is not difficult, since we can enumerate the rational numbers. As the ordering we could then pick "a <= b" if the index of "a" in the enumeration is less than the index of "b". The least element of any set of rational numbers is then the rational number with the least index in that set.

However, the real numbers are uncountable. Tricks like this cannot work.

----

The real culprit is the axiom of excluded middle, which confounds the notions of existence and embodiment. Under classical logic it may be proven that P = NP, even though no algorithm actually exists. This already happened for certain graph problems... (=> Graph minor theorem, moving from minor-closed graph property to finite set of excluded minors is essentially non-constructive.)

Without excluded middle, the axiom of choice is exactly as trivial as it sounds: Given a non-empty set, give me an element in that set. In order to show that a set is non-empty you need to give enough information to construct an element in that set. So the proof contains the information to validate the "axiom".

With excluded middle, the proof that a set is non-empty doesn't contain enough information to pick an element from that set. So adding both excluded middle and choice takes you into an axiomatic system whose connection with the real world is rather tenuous.

----

The article is spot on: Not only is mathematics a designed system, but the analogy between programming languages and logic is perfect in view of the Curry-Howard correspondence. Elevating Zermelo-Fraenkel set theory is like insisting that your software project has to be built using Turing machines. After all, everything else is just encoding. There is a huge design space in logics as well as in programming languages. For instance, you can do physics in the setting of synthetic differential geometry and work without preconditions and use theorems which are literally impossible in ZFC.

A soundness proof for a new logic is, by the way, the logical equivalent of building a compiler. :)

[DominikPeters]

Careful, the axiom of choice doesn't state that non-empty sets contain an element (this is a triviality). Rather (an equivalent of) it states that the Cartesian product of non-empty sets is non-empty. If we take a product of finitely many such sets, then we can prove it, but we need the axiom of choice for the infinite case.

The reason is intuitively clear: in order to prove that the infinite product is non-empty, we need to produce an infinitely long vector. Well, since the individual sets are non-empty, we can just for each set choose an element and put it in the vector. But this takes infinitely many steps! and that's not allowed in mathematics. The axiom of choice is a way of collapsing infinitely many steps into 1 invocation of the axiom (so 1 step, so finitely many steps). Not too much to do with excluded middle.

[fmap]

There are many classically equivalent formulations of the axiom of choice, the one I gave is just the one I like best. :)

But you are right, the devil is in the details, so let me spell it out precisely:

The axiom states that for every set X, there is a function

  \epsilon : P(X)/{\empty} -> X

If you want to restrict yourself to first-order logic, then you have to encode the function \epsilon (e.g. as a functional relation, where relations are in turn encoded as sets of ordered pairs, which are in turn encoded with Kuratowsky's construction). Set theorists like first-order logic and this encoding overhead is the reason why it's not the standard definition, even though it's arguably what the axiom is trying to express(1,2). Apart from that the statements are (classically) equivalent:

To go from the higher-order version to the cartesian product, note that the cartesian product of an I-indexed family of sets is a set of functions f from I to the union of all X_i's, such that f(i) \in X_i for all i. Let (X_i)_{i\in I} be an I-indexed family of sets, all of which are non-empty, then (i -> \epsilon(X_i)) is in the cartesian product of the X_i's, where we use \epsilon for the union of all X_i's. The reason we couldn't build that element without AC is precisely that we have no way of selecting exacly one element from each X_i, even though we know that they are non-empty.

In the other direction we can use Zermelo's well-ordering theorem to construct a well-order on X. We define \epsilon to pick out the minimum with respect to this order.

(1) This really is what the axiom of choice was meant to express. If you can read German, you can refer to Zermelo's own work:

  https://eudml.org/doc/158167

Under point 2 in this paper, Zermelo assumes that there is such a choice function on a given set and from this he derives the well-ordering of that set.

(2) Another example of the drawbacks of working with a first-order axiomatization is the axiom of regularity. The idea we want to express is that there are no infinitely descending element chains ("every set is well-founded"), but expressing this in first-order logic leads to a convoluted statement which obscures the simple idea... and is also not a correct encoding of this idea in intuitionistic logic!

[mm_aa]

Is there any effect on our thinking that comes from HoTT? I heard this is exactly the kind of problems it tries to solve.