Propositions as [Types]

Propositions as [Types], Steve Awodey and Adrej Bauer.

Image factorizations in regular categories are stable under pullbacks, so they model a natural modal operator in dependent type theory. This unary type constructor [A] has turned up previously in a syntactic form as a way of erasing computational content, and formalizing a notion of proof irrelevance. Indeed, semantically, the notion of a support is sometimes used as surrogate proposition asserting inhabitation of an indexed family.

We give rules for bracket types in dependent type theory and provide complete semantics using regular categories. We show that dependent type theory with the unit type, strong extensional equality types, strong dependent sums, and bracket types is the internal type theory of regular categories, in the same way that the usual dependent type theory with dependent sums and products is the internal type theory of locally cartesian closed categories.

We also show how to interpret first-order logic in type theory with brackets, and we make use of the translation to compare type theory with logic. Specifically, we show that the propositions-as-types interpretation is complete with respect to a certain fragment of intuitionistic first-order logic. As a consequence, a modified double-negation translation into type theory (without bracket types) is complete for all of classical first-order logic.

I figure I should say a few words about why proof irrelevance is an interesting idea. In math, you often want to consider elements of a certain type that have certain properties -- for example, you might want the set of satisfiable boolean formulas as part of a proof as a hypothesis of a theorem.

The way you might represent this in dependent type theory is by giving a pair, consisting of a formula and a satisfying assignment. You might write this as sigma f:Formula. assignment(f). The trouble is that the elements of this type really have more information than the subset contains; in addition to having formulas, you also have the assignments. So if you wanted to write a function that took values of this type computed satisfying assignments, then you could do it in constant time by just returning the second component of the pair, the evidence that it was satisfiable. This is not what you want, if your goal was to show that you could compute the satisfying assignment to a satisfiable formula.

One way of addressing this problem is to treat the second component of the pair as a proof irrelevant type. The basic idea is that for each type A, you make up a new type [A] which has either zero or one inhabitants, depending on whether A has any inhabitants or not. This means that you cannot make any computational use of data of type [A], because it doesn't have any structure to it. So if your solver receives a value of type sigma f:Formula. [assignment(f)], then you know that the formula is satisfiable, but you don't know what it is, because the second component is a bracket type. This means that your function will actually have to do the real work you intended.

I should also add that this is an old idea in type theory; this is the paper that made it clear to me.

(Thanks to Bob Harper for suggesting clarifications to my comments.)

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Another reason proof irrelevance is important

In a dependent type theory, the terms embedded in types are compared for equality when determining whether two types are equal. Suppose you have a type family A indexed by a term of type sigma f:Formula. assignment(f). The terms

t1 = (Or (Var "x") (Var "y"), [("x", true), ("y", false)])
t2 = (Or (Var "x") (Var "y"), [("x", false), ("y", true)])

are two different terms of this type because they have different satisfying assignments (where I'm treating Formula as some sort of datatype with constructors Or and Var and assignment(f) as a (string * bool) list where the strings are the variables in the formula f). However, note that the first components of these two pairs are the same formula.

Because these terms have different satisfying assignments, the types A t1 and A t2 are considered to be different types. This may not always be what you want; for example, we can't apply a function of type A t1 -> B to a term of type A t2.

Instead, we might want types indexed by "formulas that are known to be satisfiable", without the proof that the formula is in fact satisfiable contributing to the equality of these terms. By using proof irrelevance as Neel suggested, you can capture this notion of equality.

Please use a newer link to the paper

My god, where did you find this old URL? I should take it down, as it is quite obsolete. The paper should be retrieved from If someone can change the link in the title of the post, I would be grateful.

I fixed the link.

I fixed the link.