[ex3xu]

As a layman I'm curious about the state of constructivist mathematics and intuitionism since the tragic passing of Vladimir Voevodsky in 2017. I recall reading about the Coq proof assistant, homotopy type theory, and univalent foundations with some interest, but I haven't been keeping up with any new developments -- is it still an active field of research?

I'm also curious if someone can weigh in on the fact that this paper by Martin-Löf finishes with a proof of the axiom of choice -- isn't that a bit of a controversial axiom? Does all of constructivist mathematics still depend on the axiom of choice to this day?

[mauricioc]

One exciting new development is "Cubical Type Theory: a constructive interpretation of the univalence axiom" [0], a constructive version of homotopy type theory.

The "axiom of choice" in this context is not really an axiom, just a provable theorem whose proof in this setting is given by Martin-Löf. The reason, I believe, is that constructive mathematics has a different meaning for the exists (∃) quantifier. In a constructive context, existence is "stronger" since you have to specify a witness of existence; this makes the hypothesis of the "axiom" of choice stronger, allowing for a proof.

Here's a stab at a very informal version of this. Suppose you have a set composed of "slices". The "axiom" of choice says that "IF for every slice (x in A) there exists a good element of that slice (y in B_x, and 'good' is defined by satisfying property C), THEN there exists a function which takes a slice and returns a good object of that slice." But the very definition of the (constructive) word "exists" in the hypothesis means you already have to specify, as input, a way of finding one good object of each slice. With this, finding a function that provides a good object of each slice is a tautology.

[0] https://arxiv.org/abs/1611.02108

[ex3xu]

Thank you, this helps my understanding.

[btilly]

Constructivist mathematics does not depend on the axiom of choice.

That said, when you only admit a universe of mathematical objects that admit of a finite construction, it is not unreasonable that you can have a computer program that, at least in principle, will enumerate all possible constructions and proofs of statements about them. Given that, you can create a construction which is literally for each set Y, the primary x in Y is the first x which in that enumeration a statement of the form "x is in Y" is proved.

This construction give a choice function of the kind that the Axiom of Choice says exists. However that said, the bizarre consequences of the Axiom of Choice that you find in classical set theory can't be proven for other reasons.

[ex3xu]

Thank you for the clarification. Following up on this, I found a blog post [0] that explains why you don't get bizarre consequences like the Banach-Tarski paradox this way:

> [The constructivist method] avoids the basic problem with the axiomatic problem. You can’t have something ridiculous like the set of all sets that don’t include themselves, because the only way to show that a set exists is to show a process to create it – and there’s no way to create a paradoxical set! You don’t get nonsense like [the Banach-Tarski paradox], because the division of the spherical topological space into the non-metric subspaces is impossible: you can’t show a process that produces it. In the world of intuitionism and constructivism, existence proofs that don’t produce concrete examples don’t exist!

[0]: http://www.goodmath.org/blog/2014/08/18/the-constructivist-r...

[hackermailman]

Read Robert Harper's blog for everything in the constructivist, type theory state of the art: https://existentialtype.wordpress.com/2018/01/15/popl-2018-t...

There's also the OPLSS lectures if you're interested: https://www.cs.uoregon.edu/research/summerschool/summer16/cu...

[intuitionist]

Martin-Löf has a whole paper on the axiom of choice in constructive mathematics: https://pdfs.semanticscholar.org/68d6/790cdbfda26cf71311e137...

[ukj]

For me (intuitively, conceptually and abstractly), the AC is just a particular case of Hilbert's Entscheidungsproblem.

It doesn't matter what the AC states. All that matters is that you interpret it as a proposition. And then it's sufficient to assume that some algorithm can be constructed, or some Oracle can be consulted to determine the truth-value of the proposition.

Like, for example. I can construct you an Oracle which evaluates the "Law" of Non-Contradiction as true.

https://repl.it/repls/GiftedHumiliatingProcess

This is the fundamental (only?) difference between mathematics and programming. Mathematics assumes pure functions.

[garmaine]

I think you have it backwards? From a mathematical perspective, the constructivist framework is defined as "provable without the axiom of choice." Constructivists are very concerned with avoiding the axiom of choice.

[ex3xu]

You're right. Wikipedia mentions that Voevodsky's model is considered to be non-constructive since it uses the axiom of choice in an ineliminable way.

> The problem of finding a constructive interpretation of the rules of the Martin-Löf type theory that in addition satisfies the univalence axiom and canonicity for natural numbers remains open. A partial solution is outlined in a paper by Marc Bezem, Thierry Coquand and Simon Huber[17] with the key remaining issue being the computational property of the eliminator for the identity types. The ideas of this paper are now being developed in several directions including the development of the cubical type theory.

I'm getting confused because Martin-Lof writes at the end of this paper:

> I shall construct an object of this type, an object which may at the same time be interpreted as a proof of the axiom of choice...

Thus (Az)((..tx)p(z(x)), (lx)q(z(x))) is the sought for proof of the axiom of choice.

[tines]

I'm confused then because the paper linked in the OP states:

> The true source of uncomputeable functions is not the axiom if choice (which is valid intuitionistically) but the law of the excluded middle and indirect proof [emphasis original]

[pfortuny]

It is choice in constructible mathematics: something “totally different” from “zf” choice. Existence means “can construct”, essentially. There are “less” things in constructible mathematics than in zf. This is a rough explanation.