3 ms·
A fairly good summary, though more material on the Curry-Howard Isomorphism would have been nice. Summary for the layperson: The Curry-Howard Isomorphism is a
by eli_gottlieb 11y ago
A fairly good summary, though more material on the Curry-Howard Isomorphism would have been nice.
Summary for the layperson:
The Curry-Howard Isomorphism is an exact syntactic correspondence between types for lambda calculi, propositions in intuitionistic logics, and objects in closed Cartesian categories.
A lambda calculus is a very small programming language built only out of functions. You start assigning "types" so that you can talk about total functions, which will always return.
Intuitionistic logic is just logic without the Law of the Excluded Middle (P \/ ~P), and in particular, it's a logic of constructive evidence in the form of proof. To assert X in intuitionistic logic, you must provide a proof which shows how to construct the object the proposition is about. If this sounds computational, it is: the Excluded Middle is false in intuitionistic logic because the Halting Problem is undecidable. For all computationally decidable problems, you can in fact prove the Excluded Middle for those problems by exhibiting the relevant decision algorithm.
Closed Cartesian categories... well, I don't actually know enough category theory to describe them. Sorry.
But anyway, what the Curry-Howard Isomorphism shows is that given any one of these things, I can turn it into all the others. A proof in intuitionistic logic can be turned into a program in typed lambda calculus, and the type of a lambda-calculus program can be turned into a proposition which that program proves. A program is also an arrow in a closed Cartesian category, and a type or proposition is an object.
But anyway, what happened is that Martin-Loef's Intuitionist Type Theory has always been hard to work with, because you have to pull all kinds of funny definitional tricks with equality. In fact, to prove equality in ITT, you have to show that two things must be the same by definition, tautologically, trivially identical. Proving nontrivial equalities gets very difficult, as anyone fed up with trying to do so in Coq can tell you.
What happened with Homotopy Type Theory? Well, they noticed that you could add another branch to the Isomorphism: programs are points, types are topological spaces. This isn't so surprising, because category theory has always been a bit topological. This gave them a notion of a formal system to work with, and they found a model for it (which proves the formal system is sound and consistent). They found that in this model, "equality is equivalent to equivalence" (Voevodsky's Univalence Axiom), or in other words, the kind of trivial equality one deals with in Coq is generalized as just a very low-dimensional instance of topological and categorical equivalence. They also found that equality could be defined as the existence of a path between two points -- two objects/proofs are equal precisely when they belong to the same "lump of rubber" in a topological space. Since paths can be nontrivial, "go around the hole in the donut" rather than just "go towards the other point in a straight line", this is a powerful tool -- homotopy theory becomes a part of the new foundational framework.
Moreover, since topology and homotopy theory deal with continuous objects, and in fact the definition of continuity in general, from the get go, this meant that they would need a lot less nasty "plumbing" to define things like the real numbers, and thus most of common maths, in a "more topological" foundations. The fact that the new system has computational content and submits itself to computer proof-checking via the Curry-Howard Isomorphism is icing on the cake.