Formal Semantics in Modern Type Theories. Stergios Chatzikyriakidis

      1

      Type Theories and Semantic Studies

      The long history of the study of semantics has produced a number of theories of meaning. For example, the referential theory adopts a Platonic viewpoint and proposes that meanings are entities in the world; the internalist theory, such as that held by Chomsky, suggests that meanings are concepts in our minds, and the use theory, which is closely related to Wittgenstein’s slogan of “meaning is use”, advocates that meanings are embodied in the ways that language is used in social practice. Besides being very interesting themselves, these philosophical theories have had a profound impact on the ways in which researchers think of and approach formal semantics. For example, many semanticists have been influenced by the referential theory of meaning and believed that formal semantics should be model-theoretic (see, for instance, Portner (2005)), following Tarski’s ideas in model theory for logical systems and Montague’s ideas in set-theoretical semantics for natural language (Montague 1974). On the other hand, the use theory of meaning has convinced many others and has been substantially developed more recently, both by philosophers such as Dummett (1991) and Brandom (1994, 2000) on meaning theories in general and by logicians such as Gentzen (1935), Prawitz (1973, 1974) and Martin-Löf (1984, 1996) on proof-theoretic semantics for logical systems in particular.

This book studies formal semantics in modern type theories (MTT-semantics for short). We contend that MTT-semantics is both model-theoretic and proof-theoretic, a thesis that was first proposed by the second author in Luo (2014) and further elaborated in Luo (2019a), and will be explicated in this book. For natural language, both model-theoretic and proof-theoretic semantics have their own advantages and disadvantages, and it is not easy to imagine how one can combine them in a single semantic framework: in fact, up to now this has never been attempted, let alone done. We argue that MTT-semantics is the first framework with both characteristics: being model-theoretic, it provides powerful mechanisms to capture semantics for a wide range of linguistic features, and being proof-theoretic, it has a solid meaning-theoretic foundation and can be directly implemented by means of the current proof technology to support computer-assisted reasoning in natural language. This gives MTT-semantics unprecedented advantages over other semantic frameworks.

      In this chapter, we shall start with a brief account of the historical development of type theory for the study of the foundations of mathematics – the simple type theory for classical mathematics and dependent (modern) type theories for constructive mathematics. Simple type theory was employed by Montague and his followers as an intermediate language for the study of model-theoretic semantics of natural language, where set theory is taken as the foundational language. In MTT-semantics, on the other hand, modern type theories (MTTs) are themselves foundational languages. The new logical concepts and rich typing mechanisms in MTTs make them adequate to serve as foundational languages for formal semantics. We shall introduce MTT-semantics briefly, which will be developed further in the book, and summarize its advantages.

1.1. Historical development of type theories

      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.³