Internal Languages for Autonomous and ∗-Autonomous Categories

✍ Scribed by Thong-Wei Koh; C-H.Luke Ong

• Publisher: Elsevier Science
• Year: 1999
• Tongue: English
• Weight: 32 KB
• Volume: 29
• Category: Article
• ISSN: 1571-0661
• DOI: 10.1016/s1571-0661(05)80313-5

✦ Synopsis

We introduce a family of type theories as internal languages for autonomous (or symmetric monoidal closed) and * -autonomous categories, in the same sense that the simply-typed lambdacalculus with surjective pairing is the internal language for cartesian closed categories. The rules for the typing judgements are presented in the style of Gentzen's Sequent Calculus. A notable feature is the systematic treatment of naturality conditions by expressing the categorical composition, or cut in the type theory, by explicit substitution. We use let-constructs, one for each of the three type constructors tensor unit, tensor and linear function space, and a Parigot-style muabstraction to express the involutive negation. We show that the eight equality and three commutation congruence axioms of the * -autonomous type theory characterise * -autonomous categories exactly. More precisely we prove that there is a canonical interpretation of the ( * -autonomous) type theories in * -autonomous categories which is complete i.e. for any type theory, there is a model (i.e. * -autonomous category) whose theory is exactly that. The associated rewrite systems are all strongly normalising; modulo a simple notion of congruence, they are also confluent. As a corollary, we solve a Coherence Problem a la Lambek: the equality of maps in any * -autonomous category freely generated from a discrete graph is decidable.