Michael Shulman
definitional equality for 2-logic

It is convenient, in stating the type rules and working in the type system, to have a notion of equality for objects of categories. For instance, we would like to say that from objects x:Ax:A and y:By:B we can construct a pair x,y:A×B\langle x,y\rangle:A\times B such that π 1(x,y)\pi_1(\langle x,y\rangle) and π 2(x,y)\pi_2(\langle x,y\rangle) are equal to xx and yy respectively. Even if, in some desired 2-categorical models, they are only canonically isomorphic, carrying around all those canonical isomorphisms in the type theory is exceptionally tedious.

It turns out to cause no problems if we have a notion of equality for objects of categories, as long as that notion of equality is not a proposition but rather a separate kind of syntactic or definitional judgment about terms. This distinction is well-known in intensional type theory. We will write \equiv for this definitional equality and reserve == for propositional equality. Note that propositional equality applies only to terms of a SetSet type, while definitional equality applies, a priori, to terms of any type. However, any two terms of a PropProp type are necessarily equal, and for terms of a SetSet type we can expect propositional and definitional equality to agree; thus definitional equality is really only a new thing for terms of a CatCat type.

One important distinction between definitional and propositional equality is that definitional equality can never be a hypothesis, i.e. it can never appear on the left of a \vdash. It should be viewed more as a “computation rule” defining the behavior of certain term-forming operations.

However, because we have types dependent on terms, we also need to allow definitional equality between types. That is, if B(x)B(x) is a type dependent on xx and xyx\equiv y, then we should have B(x)B(y)B(x)\equiv B(y). Again, this is not a problem as long as such equality of types is not a proposition but merely a syntactic/definitional statement.

Revised on May 29, 2012 22:04:00 by Andrew Stacey? (129.241.15.200)