In any sort of type theory, there are a bunch of rules for constructing derivations of typing judgments such as $x:A,\; y:B(x) \;\vdash\; z:C(x,y)$. (I intend to include also judgments of the form $B:\mathrm{Type}$.) It's certainly possible to get to the same typing judgment using different derivations; for instance I could introduce an unnecessary variable with weakening, then substitute any term for that variable. But it feels as though such a derivation should be "$\beta$-equivalent" to a derivation which omits the unnecessary variable and substitution. So my question is:


*Is there a tractable (e.g. inductively generated) equivalence relation on derivations under which all derivations of the same typing judgment become equivalent?*


Although I want the answer to be yes, I suspect that it is no, because derivations are a lot like proofs, and I know that at least in intuitionistic logic, there can be multiple "essentially distinct" proofs of a given statement. If so, could it be true for some restricted class of type theories? Can one quantify its falsity?




---


**Edit:** Apparently there was a lot of room for misinterpretation of this question! To clarify: I was only talking about type theories in which inhabitation of types is witnessed by a specified term, as in the example typing judgment I gave above. (If you think of types as propositions and terms as proofs, then the question becomes "are all ways to derive a given proof-term equivalent?" But I don't generally tend to think of types only in that way.) Neel's answer seems to say: yes, as long as the type theory satisfies cut-elimination. Whether or not a given type can be inhabited by multiple distinct terms (e.g. one proposition can admit multiple distinct proofs) is a different question.


**Edit 2:** Maybe if I explain the origin of my question, it will make clearer what I was asking. When trying to define a semantics of DTT in a locally cartesian closed category, it seems to me that the natural approach is to define the interpretation of each type and term inductively using the corresponding categorical constructions, as in D4.4 of *Sketches of an Elephant*. Unfortunately, this doesn't quite work, because for instance substitition is "strict" in type theory, but pullback is only up to isomorphism in a category.


It seems that the standard way to deal with this is to first strictify the pullbacks in the lccc, e.g. by replacing its codomain fibration by a split one and maybe some additional data (people talk about "comprehension categories" and suchlike). However, looking at the direct construction that doesn't work, it seems to me that it can be interpreted meaningfully as an inductive construction acting not on types+terms, but rather on *derivations* of typing judgments. If that's right, it seems like one could then get a meaningful interpretation of type theory in an lccc by proving that any two derivations of the same typing judgment produce canonically *isomorphic* interpretations in the lccc. But that would require a notion of equivalence between derivations which is tractable (so that one can show that any equivalence of derivations gives an isomorphism in the lccc) and under which all derivations can be shown to be equivalent; hence my question.



Can a typing judgment admit essentially different derivations?
This property is called "coherence", and no, it doesn't always hold. 


Establishing this property holds for a given semantics of proofs is a proof obligation. An example of when it doesn't arises with coercive subtyping -- if the diagrams corresponding to possible coercions do not all commute, then the semantics is not coherent, in that the meaning of a term depends critically on its typing derivation. If all you have is the term and knowledge that it has a typing derivation, you can't tell what it means, necessarily.


For a proof-theoretic characterization, the thing to look for is a cut-elimination theorem. One way of reading the cut-elimination theorem is precisely that it says that eliminating intro/elim and elim/intro pairs (i.e., $\beta$ and $\eta$ equations) induces a genuine equivalence relation on proofs. 


However, we can still have essentially different proofs. For example, $x : A \land A \vdash \pi\_1(x) : A$ and $x : A \land A \vdash \pi\_2(x) : A$ are two different proofs that $A$ and $A$ entails $A$. However, cut-elimination guarantees that the addition of proof terms does make the typing derivations unique -- any proof of this entailment must be equal to one or the other, since every proof is equivalent to a cut-free proof, and these are the only two cut-free proofs, and the proof terms let us distinguish the two possibilities.


EDIT: There must be a treatment of this subject in somebody's book (Barendregt?), but I don't know off-hand, since I learned it via osmosis. Probably the best reference I can point you at is Jan Schwinghammer's paper ["Coherence of Subsumption for Monadic Types"](http://www.ps.uni-saarland.de/Publications/documents/Schwinghammer_Coherence_09.pdf), which nicely illustrates the idea, and whose references also contain pointers to the best available literature. 


Noam quite rightly points out that you might actually be interested in the case where all derivations of a judgement are equivalent. (This possibility honestly hadn't even occurred to me, since I'm too intuitionistically contaminated.) The keyword to search for in this case is "proof irrelevance", and I recommend Awodey and Bauer's paper ["Propositions as [Types]"](http://logcom.oxfordjournals.org/content/14/4/447.abstract).


EDIT 2: When cut-elimination holds, then the derivations of a calculus *with proof terms* become equivalent. If you don't have proof terms, then you can't guarantee equivalence of derivations. 


For example, suppose we erased the proof terms from the derivation above, so that we simply had the judgment $A \land A \vdash A$. In this case, even if we know that this judgment holds, we still don't know whether the proof used the left or the right $A$, which are the two intrinsically different derivations of the same judgment. On the other hand, if we have proof terms, then we have a judgment $x : A \land A \vdash e : A$. In this case, the derivation does bebgcome unique, because now we can $\beta\eta$-normalize $e$ and just check whether it is equal to $\pi\_1(x)$ or $\pi\_2(x)$. 


This is why lambda-calculus expressions are called "proof terms": these terms are evidence to establish which proof you meant.


To connect this back with proof irrelevance, a type is "proof irrelevant" when all the proof terms of that type are equivalent. That is, if $\Gamma \vdash e : A$ and $\Gamma \vdash e' : A$, then we know that the two derivations are equivalent, regardless of $e$ and $e'$. For example, the unit type $1$ is proof irrelevant, since every term in it is equivalent to the unit value $\left<\right>$. 


