|logic||category theory||type theory|
|true||terminal object/(-2)-truncated object||h-level 0-type/unit type|
|false||initial object||empty type|
|proposition||(-1)-truncated object||h-level 1-type/h-prop|
|cut elimination for implication||counit for hom-tensor adjunction||beta reduction|
|introduction rule for implication||unit for hom-tensor adjunction||eta conversion|
|disjunction||coproduct ((-1)-truncation of)||sum type (bracket type of)|
|implication||internal hom||function type|
|negation||internal hom into initial object||function type into empty type|
|universal quantification||dependent product||dependent product type|
|existential quantification||dependent sum ((-1)-truncation of)||dependent sum type (bracket type of)|
|equivalence||path space object||identity type|
|equivalence class||quotient||quotient type|
|induction||colimit||inductive type, W-type, M-type|
|higher induction||higher colimit||higher inductive type|
|completely presented set||discrete object/0-truncated object||h-level 2-type/preset/h-set|
|set||internal 0-groupoid||Bishop set/setoid|
|universe||object classifier||type of types|
|modality||closure operator monad||modal type theory, monad (in computer science)|
|linear logic||(symmetric, closed) monoidal category||linear type theory/quantum computation|
|proof net||string diagram||quantum circuit|
|(absence of) contraction rule||(absence of) diagonal||no-cloning theorem|
Systems of formal logic, such as type theory, try to transform expressions into a canonical form which then serves as the end result of the given computation or deduction. A formal system is said to enjoy canonicity if every expression reduced to canonical form.
More precisely, in type theory, a term belonging to some type is said to be of canonical form if it is explicitly built up using the constructors of that type. A canonical form is in particular a normal form? (one not admitting any reductions), but the converse need not hold.
A type theory is said to enjoy canonicity if every term computes to a canonical form. This is held to be an important meta-theoretic property of type theory, especially considered as a programming language or as a computational foundation for mathematics.
Adding axioms to type theory, such as the principle of excluded middle or the usual version of the univalence axiom, can destroy canonicity. The axioms result in “stuck terms” which are not of canonical form, yet neither can they be “computed” any further.
For instance, if we assume the law of excluded middle, then we can build a term which is or according as the Goldbach conjecture is true or false. Clearly this term doesn’t “compute”, but neither is it of canonical form (a numeral).
Similarly, using the univalence axiom, we can obtain a term corresponding to the automorphism of which adds one to every even number and subtracts one from every odd number. Then the term also has type , but doesn’t “compute” because the computer gets “stuck” on the univalence term.
It is conjectured that univalence, unlike excluded middle, can be given a “computational” interpretation while preserving canonicity. Some partial progress towards this can be found here.