Introduction to Higher-Order Categorical Logic (Cambridge Studies in Advanced Mathematics, Series Number 7)

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. Preface Part 0 Introduction to category theory Introduction to Part 0 1 Categories and functors 2 Natural transformations 3 Adjoint functors 4 Equivalence of categories 5 Limits in categories 6 Triples 7 Examples of cartesian closed categories Part I Cartesian closed categories and λ-calculus Introduction to Part I Historical perspective on Part I 1 Propositional calculus as a deductive system 2 The deduction theorem 3 Cartesian closed categories equationally presented 4 Free cartesian closed categories generated by graphs 5 Polynomial categories 6 Functional completeness of cartesian closed categories 7 Polynomials and Kleisli categories 8 Cartesian closed categories with coproducts 9 Natural numbers objects in cartesian closed categories 10 Typed λ-calculi 11 The cartesian closed category generated by a typed λ-calculus 12 The decision problem for equality 13 The Church-Rosser theorem for bounded terms 14 All terms are bounded 15 C-monoids 16 C-monoids and cartesian closed categories 17 C-monoids and untyped λ-calculus 18 A construction by Dana Scott Historical comments on Part I Part II Type theory and toposes Introduction to Part II Historical perspective on Part II 1 Intuitionistic type theory 2 Type theory based on equality 3 The internal language of a topos 4 Peano's rules in a topos 5 The internal language at work 6 The internal language at work II 7 Choice and the Boolean axiom 8 Topos semantics 9 Topos semantics in functor categories 10 Sheaf categories and their semantics 11 Three categories associated with a type theory 12 The topos generated by a type theory 13 The topos generated by the internal language 14 The internal language of the topos generated 15 Toposes with canonical subobjects 16 Applications of the adjoint functors between toposes and type theories 17 Completeness of higher order logic with choice rule 18 Sheaf representation of toposes 19 Completeness without assuming the rule of choice 20 Some basic intuitionistic principles 21 Further intuitionistic principles 22 The Freyd cover of a topos Historical comments on Part II Supplement to Section 17 Part III Representing numerical functions in various categories Introduction to Part III 1 Recursive functions 2 Representing numerical functions in cartesian closed categories 3 Representing numerical functions in toposes 4 Representing numerical functions in C-monoids Historical comments on Part III Bibliography Author index Subject index This work attempts to reconcile two different viewpoints of the foundations of mathematics, namely mathematical logic and category theory. It contains an introduction to category theory and a set of exercises which accompanies each section. In this book the authors 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. In Part II, it is demonstrated 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 concludes with a set of exercises. Thus it is well-suited for graduate courses and research in mathematics and logic. Researchers in theoretical computer science, artificial intelligence and mathematical linguistics will also find this an accessible introduction to a subject of increasing application to these disciplines In this book the authors reconcile two different viewpoints of the foundations of mathematics, namely mathematical logic and categony theony. In Part I, they show that typed lambda-calculi, a formulation of higher order logic, and cartesian closed categories are essentially the same. In Part II, it is demonstrated 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. In Part 0 we recall the basic background in category theory which may be required in later portions of this book.