Categories for Types (Cambridge Mathematical Textbooks)

✍ Scribed by Roy L. Crole

• Publisher: Cambridge University Press
• Year: 1994
• Tongue: English
• Leaves: 355
• Edition: 1
• Category: Library

✦ Synopsis

This 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.

✦ Table of Contents

Contents
Preface
Advice for the Reader
1 Order, Lattices and Domains
1.1 Introduction
1.2 Ordered Sets
1.3 Basic Lattice Theory
1.4 Boolean and Heyting Lattices
1.5 Elementary Domain Theory
1.6 Further Exercises
1.7 Pointers to the Literature
2 A Category Theory Primer
2.1 Introduction
2.2 Categories and Examples
2.3 Functors and Examples
2.4 Natural Transformations and Examples
2.5 Isomorphisms and Equivalences
2.6 Products and Coproducts
2.7 The Yoneda Lemma
2.8 Cartesian Closed Categories
2.9 Monies, Equalisers, Pullbacks and their Duals
2.10 Adjunctions
2.11 Limits and Colimits
2.12 Strict Indexed Categories
2.13 Further Exercises
2.14 Pointers to the Literature
3 Algebraic Type Theory
3.1 Introduction
3.2 Definition of the Syntax
3.3 Algebraic Theories
3.4 Motivating a Categorical Semantics
3.5 Categorical Semantics
3.6 Categorical Models and the Soundness Theorem
3.7 Categories of Models
3.8 Classifying Category of an Algebraic Theory
3.9 The Categorical Type Theory Correspondence
3.10 Further Exercises
3.11 Pointers to the Literature
4 Functional Type Theory
4.1 Introduction
4.2 Definition of the Syntax
4.3 Ax-Theories
4.4 Deriving a Categorical Semantics
4.5 Categorical Semantics
4.6 Categorical Models and the Soundness Theorem
4.7 Categories of Models
4.8 Classifying Category of a λ×-Theory
4.9 The Categorical Type Theory Correspondence
4.10 Categorical Gluing
4.11 Further Exercises
4.12 Pointers to the Literature
5 Polymorphic Functional Type Theory
5.1 Introduction
5.2 The Syntax and Equations of 2λ×-Theories
5.3 Deriving a Categorical Semantics
5.4 Categorical Semantics and Soundness Theorems
5.5 A PER Model
5.6 A Domain Model
5.7 Classifying Hyperdoctrine of a 2λ×-Theory
5.8 Categorical Type Theory Correspondence
5.9 Pointers to the Literature
6 Higher Order Polymorphism
6.1 Introduction
6.2 The Syntax and Equations of ωλ×-Theories
6.3 Categorical Semantics and Soundness Theorems
6.4 A PER Model
6.5 A Domain Model
6.6 Classifying Hyperdoctrine of an ωλ×-Theory
6.7 Categorical Type Theory Correspondence
6.8 Pointers to the Literature
Bibliography
Index