The book, which stepwise develops successively more powerful logical and grammatical systems, covers an unusually broad range of material.

Type-logical semantics studies linguistic meaning with the help of the theory of types. The latter originated with Russell as an answer to the paradoxes, but has the additional virtue that it is very close to ordinary language. In fact, type theory is so much more similar to language than predicate logic is, that adopting it as a vehicle of representation can overcome the mismatches between grammatical form and predicate logical form that were observed by Frege and Russell. (...) The grammatical forms of ordinary language sentences consequently may be taken to be much less misleading than logicians in the first half of the 20th century often thought them to be. This was realized by Richard Montague, who used the theory of types to translate fragments of ordinary language into a logical language. Semantics is commonly divided into lexical semantics, which studies the meaning of words, and compositional semantics, which studies the way in which complex phrases obtain a meaning from their constituents. The strength of type-logical semantics lies with the latter, but type-logical theories can be combined with many competing hypotheses about lexical meaning, provided these hypotheses are expressed using the language of type theory. (shrink)

In this paper, we study some classes of logical structures from the universal logic standpoint, viz., those of the Tarski- and the Lindenbaum-types. The characterization theorems for the Tarski- and two of the four different Lindenbaum-type logical structures have been proved as well. The separations between the five classes of logical structures, viz., the four Lindenbaum-types and the Tarski-type have been established via examples. Finally, we study the logical structures that are of both Tarski- and a Lindenbaum- (...) class='Hi'>type, show their separations, and end with characterization, adequacy, minimality, and representation theorems for one of the Tarski–Lindenbaum-type logical structures. (shrink)

We discuss the logic of pregroups, introduced by Lambek [34], and its connections with other type logics and formal grammars. The paper contains some new ideas and results: the cut-elimination theorem and a normalization theorem for an extended system of this logic, its P-TIME decidability, its interpretation in L1, and a general construction of (preordered) bilinear algebras and pregroups whose universe is an arbitrary monoid.

The paper presents a simple format for typed logics with states by adding a function for register update to standard typed lambda calculus. It is shown that universal validity of equality for this extended language is decidable . This system is next extended to a full fledged typed dynamic logic, and it is illustrated how the resulting format allows for very simple and intuitive representations of dynamic semantics for natural language and denotational semantics for imperative programming. The proposal is (...) compared with some alternative approaches to formulating typed versions of dynamic logics. (shrink)

Beyond any doubt the pragmatical-based improvements introduced in the rules of inference during the process of refinement of a legal expert system may be efficient but they hardly will be capable to provide a point of reference for a more general correctness measure. During the refinement of KBSLEX the debate of the Theory of Legal Argument has contributed to illuminate the point suggesting that the modeling of legal reasoning and legal decision making should be grounded on a logical approach but (...) without limiting itself to the tools of the classical logic. (shrink)

(2) Type Logical Grammar (Moortgat & Oehrle 1994, Morrill 1994. Moortgat 1996): i. Grammar as a deductive system; variant of linear logic; two deductive rules for each type constructor (=; n; ): elimination ( modus ponens) and introduction ( rule of conditional proof).

ABSTRACT Backwards-looking operators Saarinen, E. [1979. “Backwards-Looking Operators in Tense Logic and in Natural Language.” In Essays on Mathematical and Philosophical Logic, edited by J. Hintikka, I. Niiniluoto, and E. Saarinen, 341–367. Dordrecht: Reidel] that have the material in their scope depend on higher intensional operators, are known to increase the expressivity of some intensional languages and have thus played a central role in debates about approaches to intensionality in terms of implicit parameters vs. variables explicitly quantifying over (...) them. The current contribution takes a look at these operators from a type-logical perspective. It is shown that extending Gallin's translation from intensional type logic to two-sorted type theory so as to include a version of Yanovich's backwards-looking operators, does not increase the expressive power of formulae with exclusively intensional parameters. The result, which makes use of a theorem by Zimmermann : 65–77]), is illustrated by pertinent examples from the literature. The paper closes by indicating alternative strategies of incorporating backwards-looking operators. (shrink)

For each regular cardinal κ, we set up three systems of infinitary type logic, in which the length of the types and the length of the typed syntactical constructs are $\Sigma _{}$, the global system $\text{g}\Sigma _{}$ and the τ-system $\tau \Sigma _{}$. A full cut elimination theorem is proved for the local systems, and about the τ-systems we prove that they admit cut-free proofs for sequents in the τ-free language common to the local and global systems. These (...) two results follow from semantic completeness proofs. Thus every sequent provable in a global system has a cut-free proof in the corresponding τ-systems. It is, however, an open question whether the global systems in themselves admit cut elimination. (shrink)

A two-stage procedure is described which induces type-logical grammar lexicons from sentences annotated with skeletal terms of the simply typed lambda calculus. First, a generalized formulae-as-types correspondence is exploited to obtain all the type-logical proofs of the sample sentences from their lambda terms. The resulting lexicons are then optimally unified. The first stage constitutes the semantic bootstrapping (Pinker, Language Learnability and Language Development, Harvard University Press, 1984), while the unification procedure of Buszkowski and Penn represents a first attempt (...) at structure-dependent distributional learning of the syntactic and semantic categories. This effort extends earlier induction procedures (Buszkowski and Penn, 1990, Studia Logica 49, 431–454; Kanazawa, 1998, CSLI Publications and the European Association for Logic, Language and Information) for classical categorial grammar to at first the non-associative Lambek calculus, and then to a large class of type logics enriched by modal operators and structural rules. (shrink)

A two-stage procedure is described which induces type-logical grammar lexicons from sentences annotated with skeletal terms of the simply typed lambda calculus. First, a generalized formulae-as-types correspondence is exploited to obtain all the type-logical proofs of the sample sentences from their lambda terms. The resulting lexicons are then optimally unified. The first stage constitutes the semantic bootstrapping (Pinker, Language Learnability and Language Development, Harvard University Press, 1984), while the unification procedure of Buszkowski and Penn represents a first attempt (...) at structure-dependent distributional learning of the syntactic and semantic categories. This effort extends earlier induction procedures (Buszkowski and Penn, 1990, Studia Logica 49, 431–454; Kanazawa, 1998, CSLI Publications and the European Association for Logic, Language and Information) for classical categorial grammar to at first the non-associative Lambek calculus, and then to a large class of type logics enriched by modal operators and structural rules. (shrink)

This paper explores proof-theoretic aspects of hybrid type-logical grammars, a logic combining Lambek grammars with lambda grammars. We prove some basic properties of the calculus, such as normalisation and the subformula property and also present both a sequent and a proof net calculus for hybrid type-logical grammars. In addition to clarifying the logical foundations of hybrid type-logical grammars, the current study opens the way to variants and extensions of the original system, including but not limited to (...) a non-associative version and a multimodal version incorporating structural rules and unary modes. (shrink)

Glue semantics is a theory of the syntax–semantics interface according to which the syntactic structure of a sentence produces premises in a fragment of linear logic, and the semantic interpretation of the sentence correspond to the proof derivable from those premises. This paper describes how Glue can be connected to a Minimalist syntactic theory and compares the result with the more mainstream approach to the syntax–semantics interface in Minimalism, according to which the input to semantic interpretation is a syntactic (...) structure derived by covert movement operations. I argue that the Glue approach has advantages that make it worth exploring. (shrink)

(Though it is now known that many pronouns once lumped under ”bound variables” are in fact referential indefinites or other phenomena better accounted for in a DRT-like view of referents, there remain many true instances of sentenceinternally bound anaphora: this talk concerns only the latter.) Almost all versions of categorial grammar (CG) are differentiated from other syntactic theories in treating a multi-argument verb as an Ò-place predicate phrase (PrdP) that combines with a NP or other argument to yield a (Ò-1)-place (...) PrdP (which, if (n–1) 1, then combines with another argument to yield a ´Ò ¾µ-place PrdP, until a sentence (0-place PrdP) results) – a ”curried function” account of argument structure. (In CG, Ú ÔÜ ÒÔ · ÒÔ Üµ. A number of CG analyses of Ú Ô bound anaphora (Bach & Partee 1980, Chierchia 1988, Szabolcsi 1992, Jacobson 1991, Dowty 1993, Jacobson 1999), though otherwise diverse, have in common that they treat anaphoric binding as a process that affects (only) a predicate phrase (PrdP) — usually (finite or non-finite) Ú Ô, else ÚÔ ÒÔ — by binding an internal pronoun, i.e. ”binding at the VP level”; semantically, this is usually indicated ´Üµ . The result of this binding is that the next argument the.. (shrink)

The paper presents Property Theory with Curry Typing where the language of terms and well-formed formulæ are joined by a language of types. In addition to supporting fine-grained intensionality, the basic theory is essentially first-order, so that implementations using the theory can apply standard first-order theorem proving techniques. The paper sketches a system of tableau rules that implement the theory. Some extensions to the type theory are discussed, including type polymorphism, which provides a useful analysis of conjunctive terms. (...) Such terms can be given a single polymorphic type that expresses the fact that they can conjoin phrases of any one type, yielding an expression of the same type. (shrink)

The paper presents Property Theory with Curry Typing (PTCT) where the language of terms and well-formed formulæ are joined by a language of types. In addition to supporting fine-grained intensionality, the basic theory is essentially first-order, so that implementations using the theory can apply standard first-order theorem proving techniques. The paper sketches a system of tableau rules that implement the theory. Some extensions to the type theory are discussed, including type polymorphism, which provides a useful analysis of conjunctive (...) terms. Such terms can be given a single polymorphic type that expresses the fact that they can conjoin phrases of any one type, yielding an expression of the same type. (shrink)

A method is described for inducing a type-logical grammar from a sample of bare sentence trees which are annotated by lambda terms, called term-labelled trees . Any type logic from a permitted class of multimodal logics may be specified for use with the procedure, which induces the lexicon of the grammar including the grammatical categories. A first stage of semantic bootstrapping is performed, which induces a general form lexicon from the sample of term-labelled trees using Fulop’s (J (...) Log Lang Inf 14(1):49–86, 2005) procedure. Next we present a two-stage procedure for performing distributional learning by unifying the lexical types that are initially discovered. The first structural unification algorithm in essence unifies the initial family of sets of types so that the resulting grammar will generate all term-labelled trees that follow the usage patterns evident from the learning sample. Further altering the lexical categories to generate a recursively extended language can be accomplished by a second unification. The combined unification algorithm is shown to yield a new type-logical lexicon that extends the learning sample to a possibly infinite (and possibly context-sensitive) language in a principled fashion. Finally, the complete learning strategy is analyzed from the perspective of algorithmic learning theory; the range of the procedure is shown to be a class of term-labelled tree languages which is finitely learnable from good examples (Lange et al in Algorithmic learning theory, Vol 872 of lecture notes in artificial intelligence, Springer, Berlin, pp 423–437), and so is identifiable in the limit as a corollary. (shrink)

Zero pronominals challenge Type Logical Grammar in two ways. One, TLG displays a linear resource management regime for semantic composition, meaning that pronominals call for special treatment if they want to do resource multiplication. Two, as a grammar of lexicalism, TLG applies to phonologically realized lexical entries only, illegitimating the phonetically null items during syntactic derivation. Jägor extends the inventory of category-forming connectives of TLG by a third kind of implication that creates categories of anaphoric items and solves the (...) first problem above. This article goes a step further to tackle the second one. In order to formalize the constructions with zero pronominals, we design a ternary category A B C and include the latter into Jägor’s system. The proposed system is proof-theoretically well-behaved. It is complete, sound, and decidable. More importantly, zero pronominals of various forms can be derived in the system. (shrink)

Using the programming-language concept of continuations, we propose a new, multimodal analysis of quantification in Type Logical Grammar. Our approach provides a geometric view of in-situ quantification in terms of graphs, and motivates the limited use of empty antecedents in derivations. Just as continuations are the tool of choice for reasoning about evaluation order and side effects in programming languages, our system provides a principled, type-logical way to model evaluation order and side effects in natural language. We illustrate (...) with an improved account of quantificational binding, weak crossover, wh-questions, superiority, and polarity licensing. (shrink)

We formulate a Curry-typed logic with fine-grained intensionality within Turner’s typed predicate logic. This allows for an elegant presentation of a theory that corresponds to Fox and Lappin’s property theory with curry typing, but without the need for a federation of languages. We then consider how the fine-grained intensionality of this theory can be given an operational interpretation. This interpretation suggests itself as expressions in the theory can be viewed as terms in the untyped lambda-calculus, which provides a (...) model of computation. (shrink)

In the literature there are at least two main formal structures to deal with situations of interactive epistemology: Kripke models and type spaces. As shown in many papers :149–225, 1999; Battigalli and Siniscalchi in J Econ Theory 106:356–391, 2002; Klein and Pacuit in Stud Log 102:297–319, 2014; Lorini in J Philos Log 42:863–904, 2013), both these frameworks can be used to express epistemic conditions for solution concepts in game theory. The main result of this paper is a formal comparison (...) between the two and a statement of semantic equivalence with respect to two different logical systems: a doxastic logic for belief and an epistemic–doxastic logic for belief and knowledge. Moreover, a sound and complete axiomatization of these logics with respect to the two equivalent Kripke semantics and type spaces semantics is provided. Finally, a probabilistic extension of the result is also presented. A further result of the paper is a study of the relationship between the epistemic–doxastic logic for belief and knowledge and the logic STIT by Belnap and colleagues. (shrink)

For more than 60 years, Jim Lambek has been a profoundly inspirational mathematician, with groundbreaking contributions to algebra, category theory, linguistics, theoretical physics, logic and proof theory. This Festschrift was put together on the occasion of his 90th birthday. The papers in it give a good picture of the multiple research areas where the impact of Jim Lambek's work can be felt. The volume includes contributions by prominent researchers and by their students, showing how Jim Lambek's ideas keep inspiring (...) upcoming generations of scholars. (shrink)

This paper is about omitting types in logic of metric structures introduced by Ben Yaacov, Berenstein, Henson and Usvyatsov. While a complete type is omissible in some model of a countable complete...

This paper explores the relation between the philosophical idea that logic is a science studying logical forms, and a mathematical feature of logical systems called the principle of uniform substitution, which is often regarded as a technical counterpart of the philosophical idea. We argue that at least in one interesting sense the principle of uniform substitution does not capture adequately the requirement that logic is a matter of form and that logical truths are formal truths. We show that (...) some specific logical expressions can produce propositions of different kinds and the resulting diversity of informational types can lead to a justified failure of uniform substitution without undermining the view that logic is a purely formal discipline. (shrink)

Gentzen-type sequent calculi GBD+, GBDe, GBD1, and GBD2 are respectively introduced for De and Omori’s axiomatic extensions BD+, BDe, BD1, and BD2 of Belnap–Dunn logic by adding classical negation. These calculi are constructed based on a small modification of the original characteristic axiom scheme for negated implication. Theorems for syntactically and semantically embedding these calculi into a Gentzen-type sequent calculus LK for classical logic are proved. The cut-elimination, decidability, and completeness theorems for these calculi are obtained (...) using these embedding theorems. Similar results excluding cut-elimination results are also obtained for alternative Gentzen-type sequent calculi gBD+, gBDe, gBD1, and gBD2 for BD+, BDe, BD1, and BD2, respectively. These alternative calculi are constructed based on the original characteristic axiom scheme for negated implication. (shrink)

In historical discussions of twentieth-century logic, it is typically assumed that model theory emerged within the tradition that adopted first-order logic as the standard framework. Work within the type-theoretic tradition, in the style ofPrincipia Mathematica, tends to be downplayed or ignored in this connection. Indeed, the shift from type theory to first-order logic is sometimes seen as involving a radical break that first made possible the rise of modern model theory. While comparing several early attempts (...) to develop the semantics of axiomatic theories in the 1930s, by two proponents of the type-theoretic tradition and two proponents of the first-order tradition, we argue that, instead, the move from type theory to first-order logic is better understood as a gradual transformation, and further, that the contributions to semantics made in the type-theoretic tradition should be seen as central to the evolution of model theory. (shrink)

We construct a 2-equivalence \(\mathfrak {CohTheory}^{op }\simeq \mathfrak {TypeSpaceFunc}\). Here \(\mathfrak {CohTheory}\) is the 2-category of positive theories and \(\mathfrak {TypeSpaceFunc}\) is the 2-category of type space functors. We give a precise definition of interpretations for positive logic, which will be the 1-cells in \(\mathfrak {CohTheory}\). The 2-cells are definable homomorphisms. The 2-equivalence restricts to a duality of categories, making precise the philosophy that a theory is ‘the same’ as the collection of its type spaces (i.e. its (...) type space functor). In characterising those functors that arise as type space functors, we find that they are specific instances of (coherent) hyperdoctrines. This connects two different schools of thought on the logical structure of a theory. The key ingredient, the Deligne completeness theorem, arises from topos theory, where positive theories have been studied under the name of coherent theories. (shrink)

In historical discussions of twentieth-century logic, it is typically assumed that model theory emerged within the tradition that adopted first-order logic as the standard framework. Work within the type-theoretic tradition, in the style of Principia Mathematica, tends to be downplayed or ignored in this connection. Indeed, the shift from type theory to first-order logic is sometimes seen as involving a radical break that first made possible the rise of modern model theory. While comparing several early (...) attempts to develop the semantics of axiomatic theories in the 1930s, by two proponents of the type-theoretic tradition and two proponents of the first-order tradition, we argue that, instead, the move from type theory to first-order logic is better understood as a gradual transformation, and further, that the contributions to semantics made in the type-theoretic tradition should be seen as central to the evolution of model theory. (shrink)

We describe an infinitary logic for metric structures which is analogous to Lω1,ω. We show that this logic is capable of expressing several concepts from analysis that cannot be expressed in finitary continuous logic. Using topological methods, we prove an omitting types theorem for countable fragments of our infinitary logic. We use omitting types to prove a two-cardinal theorem, which yields a strengthening of a result of Ben Yaacov and Iovino concerning separable quotients of Banach spaces.

This introduction to mathematical logic starts with propositional calculus and first-order logic. Topics covered include syntax, semantics, soundness, completeness, independence, normal forms, vertical paths through negation normal formulas, compactness, Smullyan's Unifying Principle, natural deduction, cut-elimination, semantic tableaux, Skolemization, Herbrand's Theorem, unification, duality, interpolation, and definability. The last three chapters of the book provide an introduction to type theory (higher-order logic). It is shown how various mathematical concepts can be formalized in this very expressive formal language. This (...) expressive notation facilitates proofs of the classical incompleteness and undecidability theorems which are very elegant and easy to understand. The discussion of semantics makes clear the important distinction between standard and nonstandard models which is so important in understanding puzzling phenomena such as the incompleteness theorems and Skolem's Paradox about countable models of set theory. Some of the numerous exercises require giving formal proofs. A computer program called ETPS which is available from the web facilitates doing and checking such exercises. Audience: This volume will be of interest to mathematicians, computer scientists, and philosophers in universities, as well as to computer scientists in industry who wish to use higher-order logic for hardware and software specification and verification. (shrink)

In this paper we enrich the orthomodular structure by adding a modal operator, following a physical motivation. A logical system is developed, obtaining algebraic completeness and completeness with respect to a Kripkestyle semantic founded on Baer*-semigroups as in [22].

We prove an Omitting Types Theorem for certain algebraizable extensions of first order logic without equality studied in [SAI 00] and [SAY 04]. This is done by proving a representation theorem preserving given countable sets of infinite meets for certain reducts of ?- dimensional polyadic algebras, the so-called G polyadic algebras (Theorem 5). Here G is a special subsemigroup of (?, ? o) that specifies the signature of the algebras in question. We state and prove an independence result connecting (...) our representation theorem to Martin's axiom (Theorem 6). Also we show that the countable atomic G polyadic algebras are completely representable (Corollary 16) contrasting results on cylindric algebras. Several related results are surveyed. (shrink)

We define the paraconsistent supra-logic Pσ by a type-shift from the booleans o of propositional logic Po to the supra-booleans σ of the propositional type logic P obtained as the propositional fragment of the transfinite type theory Q defined by Peter Andrews (North-Holland Studies in Logic 1965) as a classical foundation of mathematics. The supra-logic is in a sense a propositional logic only, but since there is an infinite number of supra-booleans (...) and arithmetical operations are available for this and other types, virtually anything can be specified. The supra-logic is a generalization of Lukasiewicz's three-valued logic, with the intermediate value duplicated many times and ordered such that none of the copies of this value imply other ones, but it differs from Lukasiewicz's many-valued logics as well as from logics based on bilattices. There are several automated theorem provers for classical higher order logic (finite type theory) and it should be possible to modify these to our needs. (shrink)

In this article we deal with Glivenko type theorems for intuitionistic modal logics over Prior's MIPC. We examine the problems which appear in proving Glivenko type theorems when passing from the intuitionistic propositional logic Intto MIPC. As a result we obtain two different versions of Glivenko's theorem for logics over MIPC. Since MIPCcan be thought of as a one-variable fragment of the intuitionistic predicate logic Q-Int, one of the versions of Glivenko's theorem for logics over MIPCis (...) closely related to that for intermediate predicate logics obtained by Umezawa [27] and Gabbay [15]. Another one is rather surprising. (shrink)

John McCarthy, Stanford University Logical AI (artificial intelligence) is based on programs that represent facts about the world in languages of mathematical logic and decide what actions will achieve goals by logical reasoning. A lot has been accomplished with logic as is.