In this volume, Lambek and Scott reconcile two different viewpoints of the foundations of mathematics, namely mathematical logic and category theory. In Part I, they show that typed lambda-calculi, a formulation of higher-order logic, and cartesian closed categories, are essentially the same. Part II demonstrates that another formulation of higher-order logic, (intuitionistic) type theories, is closely related to topos theory. Part III is devoted to recursive functions. Numerous applications of the close relationship between traditional logic and the algebraic language of category theory are given. The authors have included an introduction to category theory and develop the necessary logic as required, making the book essentially self-contained. Detailed historical references are provided throughout, and each section concludeds with a set of exercises.
Author(s): J. Lambek, P. J. Scott
Series: Cambridge Studies in Advanced Mathematics 7
Publisher: Cambridge University Press
Year: 1988
Language: English
Pages: 301
Contents......Page 3
Preface......Page 5
0. Introduction to Category Theory......Page 9
Introduction......Page 11
1. Categories and functors......Page 12
2. Natural transformations......Page 16
3. Adjoint functors......Page 20
4. Equivalence of categories......Page 24
5. Limits in categories......Page 27
6. Triples......Page 35
7. Examples of cartesian closed categories......Page 43
I. Cartesian Closed Categories and λ-Calculus......Page 47
Introduction......Page 49
Historical perspective......Page 50
1. Propositional calculus as a deductive system......Page 55
2. The deduction theorem......Page 58
3. Cartesian closed categories equationally presented......Page 60
4. Free cartesian closed categories generated by graphs......Page 63
5. Polynomial categories......Page 65
6. Functional completeness of cartesian closed categories......Page 67
7. Polynomials and Kleisli categories......Page 70
8. Cartesian closed categories with coproducts......Page 73
9. Natural number objects in cartesian closed categories......Page 76
10. Typed λ-calculi......Page 80
11. The cartesian closed category generated by a typed λ-calculus......Page 85
12. The decision problem for equality......Page 89
13. The Church-Rosser theorem for bounded terms......Page 92
14. All terms are bounded......Page 96
15. C-monoids......Page 101
16. C-monoids and cartesian closed categories......Page 106
17. C-monoids and untyped λ-calculus......Page 109
18. A construction by Dana Scott......Page 115
Historical comments......Page 122
II. Type Theory and Toposes......Page 129
Introduction......Page 131
Historical perspective......Page 132
1. Intuitionistic type theory......Page 136
2. Type theory based on equality......Page 141
3. The internal language of a topos......Page 147
4. Peano's rules in a topos......Page 153
5. The internal language at work......Page 156
6. The internal language at work II......Page 161
7. Choice and the Boolean axiom......Page 168
8. Topos semantics......Page 172
9. Topos semantics in functor categories......Page 177
10. Sheaf categories and their semantics......Page 185
11. Three categories associated with a type theory......Page 194
12. The topos generated by a type theory......Page 197
13. The topos generated by the internal language......Page 201
14. The internal language of the topos generated......Page 204
15. Toposes with canonical subobjects......Page 208
16. Applications of the adjoint functor between toposes and type theories......Page 213
17. Completeness of higher order logic with choice rule......Page 220
18. Sheaf representation of toposes......Page 225
19. Completeness without assuming the rule of choice......Page 231
20. Some basic intuitionistic principles......Page 234
21. Further intuitionistic principles......Page 239
22. The Freyd cover of a topos......Page 245
Historical comments......Page 252
III. Representing Numerical Function in various Categories......Page 259
1. Recurvise functions......Page 261
2. Representing numerical functions in cartesian closed categories......Page 265
3. Representing numerical functions in toposes......Page 272
4. Representing numrical function in C-monoids......Page 279
Historical comments......Page 285
Bibliography......Page 287
Author Index......Page 297
Subject Index......Page 299
