Type Theory and Formal Proof
An Introduction

A gentle introduction for graduate students and researchers in the art of formalizing mathematics on the basis of type theory.

Rob Nederpelt (Author), Herman Geuvers (Author)

9781107036505, Cambridge University Press

Hardback, published 6 November 2014

466 pages, 35 b/w illus. 125 exercises
25.4 x 17.3 x 2.8 cm, 0.98 kg

Type theory is a fast-evolving field at the crossroads of logic, computer science and mathematics. This gentle step-by-step introduction is ideal for graduate students and researchers who need to understand the ins and outs of the mathematical machinery, the role of logical rules therein, the essential contribution of definitions and the decisive nature of well-structured proofs. The authors begin with untyped lambda calculus and proceed to several fundamental type systems, including the well-known and powerful Calculus of Constructions. The book also covers the essence of proof checking and proof development, and the use of dependent type theory to formalise mathematics. The only prerequisite is a basic knowledge of undergraduate mathematics. Carefully chosen examples illustrate the theory throughout. Each chapter ends with a summary of the content, some historical context, suggestions for further reading and a selection of exercises to help readers familiarise themselves with the material.

Foreword
Preface
Acknowledgements
Greek alphabet
1. Untyped lambda calculus
2. Simply typed lambda calculus
3. Second order typed lambda calculus
4. Types dependent on types
5. Types dependent on terms
6. The Calculus of Constructions
7. The encoding of logical notions in ?C
8. Definitions
9. Extension of ?C with definitions
10. Rules and properties of ?D
11. Flag-style natural deduction in ?D
12. Mathematics in ?D: a first attempt
13. Sets and subsets
14. Numbers and arithmetic in ?D
15. An elaborated example
16. Further perspectives
Appendix A. Logic in ?D
Appendix B. Arithmetical axioms, definitions and lemmas
Appendix C. Two complete example proofs in ?D
Appendix D. Derivation rules for ?D
References
Index of names
Index of technical notions
Index of defined constants
Index of subjects.

Subject Areas: Computer architecture & logic design [UYF], Programming & scripting languages: general [UMX], Computing & information technology [U], Mathematical logic [PBCD], Mathematics [PB]