Читать книгу Formal Semantics in Modern Type Theories - Stergios Chatzikyriakidis - Страница 8

Type theories are computational logical systems that were originally developed for the foundations of mathematics. At the beginning of the 20th Century, Russell (1903) developed the theory of types to solve a foundational problem of mathematics exposed as a number of well-known paradoxical contradictions in Cantor’s naive set theory that are related to self-reference. Some researchers, including Russell himself, attributed such paradoxes to “vicious circles” in formations of logical formulae (“impredicativity”, in a technical jargon), which is what Russell’s Ramified Theory of Types (Whitehead and Russell 1925) was designed to circumvent.

However, Ramsey (1926) pointed out that it was the logical paradoxes such as Russell’s paradox, not the semantic paradoxes such as Liar’s paradox, that can (and should) be avoided in formulations of logical calculi and that Russell had mixed up these two kinds of paradoxes, leading to complications and problems in his ramified theory of types. As Ramsey argued, although impredicativity in formula formations is circular, it is not vicious. Based on this, Ramsey suggested¹ that the ramified theory of types can be “simplified” into Simple Type Theory, which was later formally formulated by Church (1940) using the λ-notation and used by Montague (1973) in his Intensional Logic (IL) to study the formal semantics of natural language.

The early developments of type theory, including those by Russell and Ramsey as mentioned above, were driven by the search for foundational languages for classical mathematics. In the 1970s, various logicians, notably Feferman, Friedman, Martin-Löf and Myhill, among others, studied foundational languages for constructive rather than classical mathematics. Besides other systems, Martin-Löf’s type theory (Martin-Löf 1975, 1984) stood out with several new ground-breaking concepts that were not present in traditional logical systems. It adopts the notions of context, judgment and definitional equality, and introduces powerful typing mechanisms such as dependent types, inductive types and type universes. It also makes use of the principle of propositions as types, also called the Curry–Howard correspondence (Curry and Feys 1958; Howard 1980), to incorporate an embedded logic in the type system. These features have not only made Martin-Löf’s type theory a very interesting candidate for the foundation of constructive mathematics but, more importantly, opened up new avenues to study dependent type theories as attractive foundational languages for various other applications such as computer-assisted reasoning and linguistic semantics.

In particular, the study of Martin-Löf’s type theory, together with that of Church’s simple type theory, has led to the development of a family of (intensional) type theories that we call MTTs,² including Martin-Löf’s predicative type theory (Martin-Löf 1975; Nordström et al. 1990) and the impredicative type theories such as the Calculus of Constructions (Coquand and Huet 1988) and the Unifying Theory of dependent Types (UTT) (Luo 1994). In computer science, MTTs have been implemented in proof assistants, computer systems for formal proof development, such as Agda (2008), Coq (2010) and Lego/Plastic (Luo and Pollack 1992; Callaghan and Luo 2001), and used in applications to formalization of mathematics and verification of programs.

It is worth remarking that, although formalizing constructive mathematics motivated the early development of dependent type theory, it is not true that MTTs can only be employed constructively. Put in another way, powerful typing is not monopolized by constructive mathematics or constructive reasoning; instead, it can be used in much wider applications such as linguistic semantics: the MTT-semantics to be studied in this book is one such example.³