Classical Non-Associative Lambek Calculus

We introduce non-associative linear logic, which may be seen as the classical version of the non-associative Lambek calculus. We define its sequent calculus, its theory of proof-nets, for which we give a correctness criterion and a sequentialization theorem, and we show proof search in it is polynomial.     

Gaifman's theorem on categorial grammars revisited

The equivalence of (classical) categorial grammars and context-free grammars, proved by Gaifman [4], is a very basic result of the theory of formal grammars (an essentially equivalent result is known as the Greibach normal form theorem [1], [14]). We analyse the contents of Gaifman's theorem within the framework of structure and type transformations. We give a new proof of this theorem which relies on the algebra of phrase structures and exhibit a possibility to justify the key construction used in Gaifman's proof by means of the Lambek calculus of syntactic types [15].     

Algebraization, Parametrized Local Deduction Theorem and Interpolation for Substructural Logics over FL

Substructural logics have received a lot of attention in recent years from the communities of both logic and algebra. We discuss the algebraization of substructural logics over the full Lambek calculus and their connections to residuated lattices, and establish a weak form of the deduction theorem that is known as parametrized local deduction theorem. Finally, we study certain interpolation properties and explain how they imply the amalgamation property for certain varieties of residuated lattices. Dedicated to the memory of Willem Johannes Blok     

On the Logic of β-pregroups

In this paper we concentrate mainly on the notion of β-pregroups, which are pregroups (first introduced by Lambek [18] in 1999) enriched with modality operators. β-pregroups were first proposed by Fadda [11] in 2001. The motivation to introduce them was to limit (locally) the associativity in the calculus considered. In this paper we present this new calculus in the form of a rewriting system, prove the very important feature of this system - that in a given derivation the non-expanding rules must always proceed non-contracting ones in order the derivation to be minimal (normalization theorem). We also propose a sequent system for this calculus and prove the cut elimination theorem for it. As an illustration we show how to use β-pregroups for linguistical applications. Special Issue Categorial Grammars and Pregroups Edited by Wojciech Buszkowski and Anne Preller     

On decidable consequence operators

The main theorem says that a consequence operator is an effective part of the consequence operator for the classical prepositional calculus iff it is a consequence operator for a logic satisfying the compactness theorem, and in which every finitely axiomatizable theory is decidable.     

Subformula semantics for strong negation systems

We present a semantics for strong negation systems on the basis of the subformula property of the sequent calculus. The new models, called subformula models, are constructed as a special class of canonical Kripke models for providing the way from the cut-elimination theorem to model-theoretic results. This semantics is more intuitive than the standard Kripke semantics for strong negation systems.     

The Normal-Form Decision Method in the Combined Calculus

The original decision criterion and method of the combined calculus, presented by D. Hilbert and W. Ackermann, and applied by later logicians, are illuminating, but also go seriously awry and lead the universality and preciseness of the combined calculus to be damaged. The main error is that they confuse the two levels of the combined calculus in the course of calculating. This paper aims to resolve the problem through dividing the levels of the combined calculus, introducing a mixed operation mode, and therefore finding a normal-form decision method approximated by that in sentential logic. Finally, this paper provides a more precise proof of Hauber’s theorem by using the normal-form decision method of the combined calculus.     

Fuzzy Logic and Arithmetical Hierarchy,II

A very simple many-valued predicate calculus is presented; a completeness theorem is proved and the arithmetical complexity of some notions concerning provability is determined.     

Uniform Interpolation and Propositional Quantifiers in Modal Logics

We investigate uniform interpolants in propositional modal logics from the proof-theoretical point of view. Our approach is adopted from Pitts’ proof of uniform interpolationin intuitionistic propositional logic [15]. The method is based on a simulation of certain quantifiers ranging over propositional variables and uses a terminating sequent calculus for which structural rules are admissible. We shall present such a proof of the uniform interpolation theorem for normal modal logics K and T. It provides an explicit algorithm constructing the interpolants. Presented by Heinrich Wansing     

On the Proof-Theory of two Formalisations of Modal First-Order Logic

We introduce a Gentzen-style modal predicate logic and prove the cut-elimination theorem for it. This sequent calculus of cut-free proofs is chosen as a proxy to develop the proof-theory of the logics introduced in [14, 15, 4]. We present syntactic proofs for all the metatheoretical results that were proved model-theoretically in loc. cit. and moreover prove that the form of weak reflection proved in these papers is as strong as possible.     

A Sequent Calculus for a Negative Free Logic

This article presents a sequent calculus for a negative free logic with identity, called N. The main theorem (in part 1) is the admissibility of the Cut-rule. The second part of this essay is devoted to proofs of soundness, compactness and completeness of N relative to a standard semantics for negative free logic.     

A Mixed λ-calculus

The aim of this paper is to define a λ-calculus typed in aMixed (commutative and non-commutative) Intuitionistic Linear Logic. The terms of such a calculus are the labelling of proofs of a linear intuitionistic mixed natural deduction NILL, which is based on the non-commutative linear multiplicative sequent calculus MNL [RuetAbrusci 99]. This linear λ-calculus involves three linear arrows: two directional arrows and a nondirectional one (the usual linear arrow). Moreover, the -terms are provided with seriesparallel orders on free variables. We prove a normalization theorem which explicitly gives the behaviour of the order during the normalization procedure. Special Issue Categorial Grammars and Pregroups Edited by Wojciech Buszkowski and Anne Preller     

A Predicate Logical Extension of a Subintuitionistic Propositional Logic

We develop a predicate logical extension of a subintuitionistic propositional logic. Therefore a Hilbert type calculus and a Kripke type model are given. The propositional logic is formulated to axiomatize the idea of strategic weakening of Kripke's semantic for intuitionistic logic: dropping the semantical condition of heredity or persistence leads to a nonmonotonic model. On the syntactic side this leads to a certain restriction imposed on the deduction theorem. By means of a Henkin argument strong completeness is proved making use of predicate logical principles, which are only classically acceptable.     

The abstract variable-binding calculus

Theabstract variable binding calculus (VB-calculus) provides a formal frame-work encompassing such diverse variable-binding phenomena as lambda abstraction, Riemann integration, existential and universal quantification (in both classical and nonclassical logic), and various notions of generalized quantification that have been studied in abstract model theory. All axioms of the VB-calculus are in the form of equations, but like the lambda calculus it is not a true equational theory since substitution of terms for variables is restricted. A similar problem with the standard formalism of the first-order predicate logic led to the development of the theory of cylindric and polyadic Boolean algebras. We take the same course here and introduce the variety of polyadic VB-algebras as a pure equational form of the VB-calculus. In one of the main results of the paper we show that every locally finite polyadic VB-algebra of infinite dimension is isomorphic to a functional polyadic VB-algebra that is obtained from a model of the VB-calculus by a natural coordinatization process. This theorem is a generalization of the functional representation theorem for polyadic Boolean algebras given by P. Halmos. As an application of this theorem we present a strong completeness theorem for the VB-calculus. More precisely, we prove that, for every VB-theory T that is obtained by adjoining new equations to the axioms of the VB-calculus, there exists a model D such that _T s=t iff _D s=t. This result specializes to a completeness theorem for a number of familiar systems that can be formalized as VB-calculi. For example, the lambda calculus, the classical first-order predicate calculus, the theory of the generalized quantifierexists uncountably many and a fragment of Riemann integration.The work of the first author was supported in part by National Science Foundation Grant #DMS 8805870.     

The Craig interpolation theorem for prepositional logics with strong negation

This paper deals with, prepositional calculi with strong negation (N-logics) in which the Craig interpolation theorem holds. N-logics are defined to be axiomatic strengthenings of the intuitionistic calculus enriched with a unary connective called strong negation. There exists continuum of N-logics, but the Craig interpolation theorem holds only in 14 of them.     

A note on the proof theory the λII-calculus

The II-calculus, a theory of first-order dependent function types in Curry-Howard-de Bruijn correspondence with a fragment of minimal first-order logic, is defined as a system of (linearized) natural deduction. In this paper, we present a Gentzen-style sequent calculus for the II-calculus and prove the cut-elimination theorem.The cut-elimination result builds upon the existence of normal forms for the natural deduction system and can be considered to be analogous to a proof provided by Prawitz for first-order logic. The type-theoretic setting considered here elegantly illustrates the distinction between the processes of normalization in a natural deduction system and cut-elimination in a Gentzen-style sequent calculus.We consider an application of the cut-free calculus, via the subformula property, to proof-search in the II-calculus. For this application, the normalization result for the natural deduction calculus alone is inadequate, a (cut-free) calculus with the subformula property being required.This paper was written whilst the author was affiliated to the University of Edinburgh, Scotland, U.K. and revised for publication whilst he was affiliated to the University of Birmingham, England, U.K.Presented byDaniele Mundici     

Some Applications of Lawvere’s Fixpoint Theorem

The famous diagonal argument plays a prominent role in set theory as well as in the proof of undecidability results in computability theory and incompleteness results in metamathematics. Lawvere (1969) brings to light the common schema among them through a pretty neat fixpoint theorem which generalizes the diagonal argument behind Cantor’s theorem and characterizes self-reference explicitly in category theory. Not until Yanofsky (2003) rephrases Lawvere’s fixpoint theorem using sets and functions, Lawvere’s work has been overlooked by logicians. This paper will continue Yanofsky’s work, and show more applications of Lawvere’s fixpoint theorem to demonstrate the ubiquity of the theorem. For example, this paper will use it to construct uncomputable real number, unnameable real number, partial recursive but not potentially recursive function, Berry paradox, and fast growing Busy Beaver function. Many interesting lambda fixpoint combinators can also be fitted into this schema. Both Curry’s Y combinator and Turing’s Θ combinator follow from Lawvere’s theorem, as well as their call-by-value versions. At last, it can be shown that the lambda calculus version of the fixpoint lemma also fits Lawvere’s schema.     

Order-Dual Relational Semantics for Non-distributive Propositional Logics: A General Framework

The contribution of this paper lies with providing a systematically specified and intuitive interpretation pattern and delineating a class of relational structures (frames) and models providing a natural interpretation of logical operators on an underlying propositional calculus of Positive Lattice Logic (the logic of bounded lattices) and subsequently proving a generic completeness theorem for the related class of logics, sometimes collectively referred to as (non-distributive) Generalized Galois Logics (GGL’s).     

A modal sequent calculus for a fragment of arithmetic

Global properties of canonical derivability predicates (the standard example is Pr() in Peano Arithmetic) are studied here by means of a suitable propositional modal logic GL. A whole book [1] has appeared on GL and we refer to it for more information and a bibliography on GL. Here we propose a sequent calculus for GL and, by exhibiting a good proof procedure, prove that such calculus admits the elimination of cuts. Most of standard results on GL are then easy consequences: completeness, decidability, finite model property, interpolation and the fixed point theorem.The second author holds a grant from the Consiglio Nazionale delle Ricerche, gruppo G.N.S.A.G.A.