Categories for TypesThis textbook explains the basic principles of categorical type theory and the techniques used to derive categorical semantics for specific type theories. It introduces the reader to ordered set theory, lattices and domains, and this material provides plenty of examples for an introduction to category theory, which covers categories, functors, natural transformations, the Yoneda lemma, cartesian closed categories, limits, adjunctions and indexed categories. Four kinds of formal system are considered in detail, namely algebraic, functional, polymorphic functional, and higher order polymorphic functional type theory. For each of these the categorical semantics are derived and results about the type systems are proved categorically. Issues of soundness and completeness are also considered. Aimed at advanced undergraduates and beginning graduates, this book will be of interest to theoretical computer scientists, logicians and mathematicians specializing in category theory. |
Contents
Order Lattices and Domains | 1 |
8 | 60 |
Algebraic Type Theory | 120 |
Functional Type Theory | 154 |
Polymorphic Functional Type Theory | 201 |
Higher Order Polymorphism | 275 |
Bibliography | 315 |
Other editions - View all
Common terms and phrases
algebraic theory arity Ax-theory axioms bijection binary product bool Boolean lattice cartesian closed category categorical semantics category theory category with finite Cl(Th classifying category commutes compact elements complete lattice continuous function dcpo define a functor definition diagram directed colimits DISCUSSION e-p pair equation-in-context equations equivalence example EXERCISE finite products function f function symbol functional type theory functor F give given ground type homomorphism implies interpret judgement left adjoint Lemma M₁ monic monotone function morphism f natural isomorphism natural numbers natural transformation notation operator Polymorphism poset preorder preserves finite PROOF Proposition proved terms raw term raw types right adjoint satisfies Scott domain Sgtm signature specified structure Suppose syntax terminal object Th(C Theorem theory Th type theory type variables underlying set unique morphism verify wcpos write