Semantics of type theory. Correctness, completeness and independence results. With a foreword by Martin Wirsing

From MaRDI portal





This monograph is a typical logic book, illustrating perfectly the triad consisting of a language, its intended semantics and a system of inference for this language which better be correct with respect to the given semantics and (if possible) also complete. It is a non-standard in the sense that each partner in this triad represents a highly specialised topic in one of the more active research areas in constructive semantics: type theories and their (possibly non-extensional) models. Type theories are popular on behalf of the well-known Curry-Howard interpretation which relates objects in some types (called propositional types) with a proof for the corresponding proposition; moreover this isomorphism yields constructive proofs from which in principle algorithms solving (constructively proven) existence problems may be obtained. So much for the ideological motivation. In the field several type theories have become prominent. The oldest approach is to be found in the Automath project of N. G. de Bruijn, but that one has several disadvantages. Martin Löf of type theory, Coquand's calculus of constructions and Cardelli's polymorphic lambda calculus are more appropriate approaches but requirements for further improvements remain. In the area of semantic interpretation one is faced with the challenge posed by the Girard paradox which shows that for type theories which are set up in a too liberal framework each type becomes inhabitated, and consequently under the Curry-Howard propositions as types reading only inconsistent theories may be interpreted. Once one starts applying the required restraints in order to escape from this paradox one faces the loss of constructions one does want to include for reasons of applicability. In this area of contradicting requirements the author of this monograph has presented a type theory which subsumes the three systems mentioned above and he has presented a semantics for which this calculus is sound. The semantics is based on the older framework of contextual categories introduced already in 1978 by John Cartmell. The main improvement consists of extending this model by a proper notion of product (products, also called dependent types represent one of the major concepts in all prominent type theories). Along the way the author also includes a useful notion of sum-types in his framework. There exists a corresponding sort of term model for this calculus which fits in this framework of doctrines of constructions, which can be invoked for showing some independence results in the next to final chapter of the monograph. Evidently in this area the author is not the only active worker; therefore it is useful to see that the final section reports on related work by others. This monograph is based on the Ph.D. thesis of the author completed in 1988; the monograph appeared in 1991, so by now, given the intensity of research in this field (which is rather outside the active interests of your reviewer) further results in this field must have appeared. The last references in the bibliography refer to papers to appear in 1991. Notwithstanding the case which can be made for the usefulness of type theories for computer science in general I consider this monograph to be one for the few specialists in the field. The material is highly abstract and the computational intuition is hard to obtain if not completely buried under the categories and the commutative diagrams.




Cited in
(69)








This page was built for publication: Semantics of type theory. Correctness, completeness and independence results. With a foreword by Martin Wirsing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5286647)