Relational semantics for full linear logic

Relational semantics, given by Kripke frames, play an essential role in the study of modal and intuitionistic logic. In [4] it is shown that the theory of relational semantics is also available in the more general setting of substructural logic, at least in an algebraic guise. Building on these ideas, in [5] a type of frames is described which generalise Kripke frames and provide semantics for substructural logics in a purely relational form.In this paper we study full linear logic from an algebraic point of view. The main additional hurdle is the exponential. We analyse this operation algebraically and use canonical extensions to obtain relational semantics. Thus, we extend the work in [4], [5] and use their approach to obtain relational semantics for full linear logic. Hereby we illustrate the strength of using canonical extension to retrieve relational semantics: it allows a modular and uniform treatment of additional operations and axioms.Traditionally, so-called phase semantics are used as models for (provability in) linear logic [8]. These have the drawback that, contrary to our approach, they do not allow a modular treatment of additional axioms. However, the two approaches are related, as we will explain.     

Algebraization of quantifier logics,an introductory overview

This paper is an introduction: in particular, to algebras of relations of various ranks, and in general, to the part of algebraic logic algebraizing quantifier logics. The paper has a survey character, too. The most frequently used algebras like cylindric-, relation-, polyadic-, and quasi-polyadic algebras are carefully introduced and intuitively explained for the nonspecialist. Their variants, connections with logic, abstract model theory, and further algebraic logics are also reviewed. Efforts were made to make the review part relatively comprehensive. In some directions we tried to give an overview of the most recent results and research trends, too.Research supported by Hungarian National Foundation for Scientific Research grant No. 1810.     

Sequent-systems and groupoid models. I

The purpose of this paper is to connect the proof theory and the model theory of a family of propositional logics weaker than Heyting's. This family includes systems analogous to the Lambek calculus of syntactic categories, systems of relevant logic, systems related toBCK algebras, and, finally, Johansson's and Heyting's logic. First, sequent-systems are given for these logics, and cut-elimination results are proved. In these sequent-systems the rules for the logical operations are never changed: all changes are made in the structural rules. Next, Hubert-style formulations are given for these logics, and algebraic completeness results are demonstrated with respect to residuated lattice-ordered groupoids. Finally, model structures related to relevant model structures (of Urquhart, Fine, Routley, Meyer, and Maksimova) are given for our logics. These model structures are based on groupoids parallel to the sequent-systems. This paper lays the ground for a kind of correspondence theory for axioms of logics with implication weaker than Heyting's, a correspondence theory analogous to the correspondence theory for modal axioms of normal modal logics.The first part of the paper, which follows, contains the first two sections, which deal with sequent-systems and Hubert-formulations. The second part, due to appear in the next issue of this journal, will contain the third section, which deals with groupoid models.     

Representation of interlaced trilattices

Trilattices are algebraic structures introduced ten years ago into logic with the aim to provide a uniform framework for the notions of constructive truth and constructive falsity. In more recent years, trilattices have been used to introduce a number of many-valued systems that generalize the Belnap–Dunn logic of first-degree entailment, proposed as logics of how several computers connected together in a network should think in order to deal with incomplete and possibly contradictory information. The aim of the present work is to develop a first purely algebraic study of trilattices, focusing in particular on the problem of representing certain subclasses of trilattices as special products of bilattices. This approach allows to extend the known representation results for interlaced bilattices to the setting of trilattices and to reduce many algebraic problems concerning these new structures to the better-known framework of lattice theory.     

An Admissible Semantics for Propositionally Quantified Relevant Logics

The Routley-Meyer relational semantics for relevant logics is extended to give a sound and complete model theory for many propositionally quantified relevant logics (and some non-relevant ones). This involves a restriction on which sets of worlds are admissible as propositions, and an interpretation of propositional quantification that makes ∀ pA true when there is some true admissible proposition that entails all p-instantiations of A. It is also shown that without the admissibility qualification many of the systems considered are semantically incomplete, including all those that are sub-logics of the quantified version of Anderson and Belnap’s system E of entailment, extended by the mingle axiom and the Ackermann constant t. The incompleteness proof involves an algebraic semantics based on atomless complete Boolean algebras.     

Displaying and Deciding Substructural Logics 1: Logics with Contraposition

Many logics in the relevant family can be given a proof theory in the style of Belnap's display logic (Belnap, 1982). However, as originally given, the proof theory is essentially more expressive than the logics they seek to model. In this paper, we consider a modified proof theory which more closely models relevant logics. In addition, we use this proof theory to show decidability for a large range of substructural logics.     

Sequent-systems and groupoid models. II

The purpose of this paper is to connect the proof theory and the model theory of a family of prepositional logics weaker than Heyting's. This family includes systems analogous to the Lambek calculus of syntactic categories, systems of relevant logic, systems related to BCK algebras, and, finally, Johansson's and Heyting's logic. First, sequent-systems are given for these logics, and cut-elimination results are proved. In these sequent-systems the rules for the logical operations are never changed: all changes are made in the structural rules. Next, Hilbert-style formulations are given for these logics, and algebraic completeness results are demonstrated with respect to residuated lattice-ordered groupoids. Finally, model structures related to relevant model structures (of Urquhart, Fine, Routley, Meyer, and Maksimova) are given for our logics. These model structures are based on groupoids parallel to the sequent-systems. This paper lays the ground for a kind of correspondence theory for axioms of logics with implication weaker than Heyting's, a correspondence theory analogous to the correspondence theory for modal axioms of normal modal logics.Below is the sequel to the first part of the paper, which appeared in the previous issue of this journal (vol. 47 (1988), pp. 353–386). The first part contained sections on sequent-systems and Hilbert-formulations, and here is the third section on groupoid models. This second part is meant to be read in conjunction with the first part.     

Meeting strength in substructural logics

This paper contributes to the theory of hybrid substructural logics, i.e. weak logics given by a Gentzen-style proof theory in which there is only alimited possibility to use structural rules. Following the literture, we use an operator to mark formulas to which the extra structural rules may be applied. New in our approach is that we do not see this as a modality, but rather as themeet of the marked formula with a special typeQ. In this way we can make the specific structural behaviour of marked formulas more explicit.The main motivation for our approach is that we can provide a nice, intuitive semantics for hybrid substructural logics. Soundness and completeness for this semantics are proved; besides this we consider some proof-theoretical aspects like cut-elimination and embeddings of the strong system in the hybrid one.Presented byMelvin Fitting     

A general possible worlds framework for reasoning about knowledge and belief

In this paper non-normal worlds semantics is presented as a basic, general, and unifying approach to epistemic logic. The semantical framework of non-normal worlds is compared to the model theories of several logics for knowledge and belief that were recently developed in Artificial Intelligence (AI). It is shown that every model for implicit and explicit belief (Levesque), for awareness, general awareness, and local reasoning (Fagin and Halpern), and for awareness and principles (van der Hoek and Meyer) induces a non-normal worlds model validating precisely the same formulas (of the language in question).     

Crawley Completions of Residuated Lattices and Algebraic Completeness of Substructural Predicate Logics

This paper discusses Crawley completions of residuated lattices. While MacNeille completions have been studied recently in relation to logic, Crawley completions (i.e. complete ideal completions), which are another kind of regular completions, have not been discussed much in this relation while many important algebraic works on Crawley completions had been done until the end of the 70’s. In this paper, basic algebraic properties of ideal completions and Crawley completions of residuated lattices are studied first in their conncetion with the join infinite distributivity and Heyting implication. Then some results on algebraic completeness and conservativity of Heyting implication in substructural predicate logics are obtained as their consequences.     

Three arguments for humility

Ramseyan humility is the thesis that we cannot know which properties realize the roles specified by the laws of completed physics. Lewis seems to offer a sceptical argument for this conclusion. Humean fundamental properties can be permuted as to their causal roles and distribution throughout spacetime, yielding alternative possible worlds with the same fundamental structure as actuality, but at which the totality of available evidence is the same. On the assumption that empirical knowledge requires evidence, we cannot know which of these worlds is actual. However, Lewis also appeals to a range of familiar semantic principles when framing his argument, which leads some authors to suppose that he can also plausibly be interpreted as offering a purely semantic argument for humility in addition. In this paper I grant that these arguments are Lewisian, but argue that Lewis is also committed to a theory of mind that licenses a purely metaphysical argument for humility based on the idea that mental properties supervene on fundamental structure. Given that knowing which x is the F requires knowing that a is the F, the supposition that we could come to know which properties actually occupy the fundamental roles entails differences in mental properties between worlds with the same fundamental structure, violating supervenience. Humility follows right away, without any further epistemic or semantic principles. This argument is immune to almost every way of rebutting the sceptical and semantic arguments; conversely, almost every way of rebutting the metaphysical argument tells equally against the others.     

Modal translations in substructural logics

Substructural logics are logics obtained from a sequent formulation of intuitionistic or classical logic by rejecting some structural rules. The substructural logics considered here are linear logic, relevant logic and BCK logic. It is proved that first-order variants of these logics with an intuitionistic negation can be embedded by modal translations into S40type extensions of these logics with a classical, involutive, negation. Related embeddings via translations like the double-negation translation are also considered. Embeddings into analogues of S4 are obtained with the help of cut climination for sequent formulations of our substructural logics and their modal extensions. These results are proved for systems with equality too.     

BRING BACK THE MAGIC

Abstract:  Magical ersatzism is the view that possible worlds are primitive abstract entities. In On the Plurality of Worlds , David Lewis presented what appeared to many to be a devastating argument against magical ersatzism. In this paper, I show that Lewis' central argument does not succeed. Magical ersatzism remains a viable theory of possible worlds.     

On S

The sentential logic S extends classical logic by an implication-like connective. The logic was first presented by Chellas as the smallest system modelled by contraining the Stalnaker-Lewis semantics for counterfactual conditionals such that the conditional is effectively evaluated as in the ternary relations semantics for relevant logics. The resulting logic occupies a key position among modal and substructural logics. We prove completeness results and study conditions for proceeding from one family of logics to another.We are grateful to Peter Apostoli, Kosta Doen, and anonymous referees for their comments on an earlier version of this paper. A.F.'s work has been supported by a grant from the Volkswagen-Stiftung.Presented byJan Zygmunt     

Transfers between Logics and their Applications

In this paper, logics are conceived as two-sorted first-order structures, and we argue that this broad definition encompasses a wide class of logics with theoretical interest as well as interest from the point of view of applications. The language, concepts and methods of model theory can thus be used to describe the relationship between logics through morphisms of structures called transfers. This leads to a formal framework for studying several properties of abstract logics and their attributes such as consequence operator, syntactical structure, and internal transformations. In particular, we treat Belief Revision Systems (BRS) as our main example, defining the Wide Belief Revision Systems (WBRS's). This generalization allows us to define BRS's in an abstract setting for classical and non-standard logics. We also show how the concept of translation between logics can be obtained as a particular case of transfers.     

Equational Bases for Joins of Residuated-lattice Varieties

Given a positive universal formula in the language of residuated lattices, we construct a recursive basis of equations for a variety, such that a subdirectly irreducible residuated lattice is in the variety exactly when it satisfies the positive universal formula. We use this correspondence to prove, among other things, that the join of two finitely based varieties of commutative residuated lattices is also finitely based. This implies that the intersection of two finitely axiomatized substructural logics over FL ⁺ is also finitely axiomatized. Finally, we give examples of cases where the join of two varieties is their Cartesian product.     

Proper Semantics for Substructural Logics,from a Stalker Theoretic Point of View

We study filters in residuated structures that are associated with congruence relations (which we call -filters), and develop a semantical theory for general substructural logics based on the notion of primeness for those filters. We first generalize Stone’s sheaf representation theorem to general substructural logics and then define the primeness of -filters as being “points” (or stalkers) of the space, the spectrum, on which the representing sheaf is defined. Prime FL-filters will turn out to coincide with truth sets under various well known semantics for certain substructural logics. We also investigate which structural rules are needed to interpret each connective in terms of prime -filters in the same way as in Kripke or Routley-Meyer semantics. We may consider that the set of the structural rules that each connective needs in this sense reflects the difficulty of giving the meaning of the connective. A surprising discovery is that connectives , ⅋ of linear logic are linearly ordered in terms of the difficulty in this sense. Presented by Wojciech Buszkowski     

A finite model theorem for the propositional μ-calculus

We prove a finite model theorem and infinitary completeness result for the propositional -calculus. The construction establishes a link between finite model theorems for propositional program logics and the theory of well-quasi-orders.Supported by NSF grant DCR-8602663     

Algebraic Aspects of Cut Elimination

We will give here a purely algebraic proof of the cut elimination theorem for various sequent systems. Our basic idea is to introduce mathematical structures, called Gentzen structures, for a given sequent system without cut, and then to show the completeness of the sequent system without cut with respect to the class of algebras for the sequent system with cut, by using the quasi-completion of these Gentzen structures. It is shown that the quasi-completion is a generalization of the MacNeille completion. Moreover, the finite model property is obtained for many cases, by modifying our completeness proof. This is an algebraic presentation of the proof of the finite model property discussed by Lafont [12] and Okada-Terui [17].