Algebraic Kripke Sheaf Semantics for Non-Classical Predicate Logics

In so-called Kripke-type models, each sentence is assigned either to true or to false at each possible world. In this setting, every possible world has the two-valued Boolean algebra as the set of truth values. Instead, we take a collection of algebras each of which is attached to a world as the set of truth values at the world, and obtain an extended semantics based on the traditional Kripke-type semantics, which we call here the algebraic Kripke semantics. We introduce algebraic Kripke sheaf semantics for super-intuitionistic and modal predicate logics, and discuss some basic properties. We can state the Gödel-McKinsey-Tarski translation theorem within this semantics. Further, we show new results on super-intuitionistic predicate logics. We prove that there exists a continuum of super-intuitionistic predicate logics each of which has both of the disjunction and existence properties and moreover the same propositional fragment as the intuitionistic logic.     

Kripke Bundle Semantics and C-set Semantics

Kripke bundle [3] and C-set semantics [1] [2] are known as semantics which generalize standard Kripke semantics. In [3] and in [1], [2] it is shown that Kripke bundle and C-set semantics are stronger than standard Kripke semantics. Also it is true that C-set semantics for superintuitionistic logics is stronger than Kripke bundle semantics [5].In this paper, we show that Q-S4.1 is not Kripke bundle complete via C-set models. As a corollary we can give a simple proof showing that C-set semantics for modal logics are stronger than Kripke bundle semantics.     

A Kripke Semantics for the Logic of Gelfand Quantales

Gelfand quantales are complete unital quantales with an involution, *, satisfying the property that for any element a, if a b a for all b, then a a* a = a. A Hilbert-style axiom system is given for a propositional logic, called Gelfand Logic, which is sound and complete with respect to Gelfand quantales. A Kripke semantics is presented for which the soundness and completeness of Gelfand logic is shown. The completeness theorem relies on a Stone style representation theorem for complete lattices. A Rasiowa/Sikorski style semantic tableau system is also presented with the property that if all branches of a tableau are closed, then the formula in question is a theorem of Gelfand Logic. An open branch in a completed tableaux guarantees the existence of an Kripke model in which the formula is not valid; hence it is not a theorem of Gelfand Logic.     

The Finite Model Property for the Implicational Fragment of IPC Without Exchange and Contraction

The aim of this paper is to show that the implicational fragment BKof the intuitionistic propositional calculus (IPC) without the rules of exchange and contraction has the finite model property with respect to the quasivariety of left residuation algebras (its equivalent algebraic semantics). It follows that the variety generated by all left residuation algebras is generated by the finite left residuation algebras. We also establish that BKhas the finite model property with respect to a class of structures that constitute a Kripke-style relational semantics for it. The results settle a question of Ono and Komori [OK85]. This revised version was published online in June 2006 with corrections to the Cover Date.     

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     

Admissibility of Cut in <Emphasis Type="Italic">LC</Emphasis> with Fixed Point Combinator

The fixed point combinator (Y) is an important non-proper combinator, which is defhable from a combinatorially complete base. This combinator guarantees that recursive equations have a solution. Structurally free logics (LC) turn combinators into formulas and replace structural rules by combinatory ones. This paper introduces the fixed point and the dual fixed point combinator into structurally free logics. The admissibility of (multiple) cut in the resulting calculus is not provable by a simple adaptation of the similar proof for LC with proper combinators. The novelty of our proof—beyond proving the cut for a newly extended calculus–is that we add a fourth induction to the by-and-large Gentzen-style proof. Presented by Robert Goldblatt     

Algebras and Matrices for Annotated Logics

We study the matrices, reduced matrices and algebras associated to the systems SA_T of structural annotated logics. In previous papers, these systems were proven algebraizable in the finitary case and the class of matrices analyzed here was proven to be a matrix semantics for them.We prove that the equivalent algebraic semantics associated with the systems SA_T are proper quasivarieties, we describe the reduced matrices, the subdirectly irreducible algebras and we give a general decomposition theorem. As a consequence we obtain a decision procedure for these logics.     

The Basic Constructive Logic for a Weak Sense of Consistency defined with a Propositional Falsity Constant

The logic B_Kc1 is the basic constructive logic in the ternaryrelational semantics (without a set of designated points) adequateto consistency understood as the absence of the negation ofany theorem. Negation is introduced in B_Kc1 with a negationconnective. The aim of this paper is to define the logic B_Kc1F.In this logic negation is introduced via a propositional falsityconstant. We prove that B_Kc1 and B_Kc1F are definitionally equivalent.     

Semantics for Dual and Symmetric Combinatory Calculi

We define dual and symmetric combinatory calculi (inequational and equational ones), and prove their consistency. Then, we introduce algebraic and set theoretical– relational and operational – semantics, and prove soundness and completeness. We analyze the relationship between these logics, and argue that inequational dual logics are the best suited to model computation.     

Algebraic Semantics for Deductive Systems

The notion of an algebraic semantics of a deductive system was proposed in [3], and a preliminary study was begun. The focus of [3] was the definition and investigation of algebraizable deductive systems, i.e., the deductive systems that possess an equivalent algebraic semantics. The present paper explores the more general property of possessing an algebraic semantics. While a deductive system can have at most one equivalent algebraic semantics, it may have numerous different algebraic semantics. All of these give rise to an algebraic completeness theorem for the deductive system, but their algebraic properties, unlike those of equivalent algebraic semantics, need not reflect the metalogical properties of the deductive system. Many deductive systems that don't have an equivalent algebraic semantics do possess an algebraic semantics; examples of these phenomena are provided. It is shown that all extensions of a deductive system that possesses an algebraic semantics themselves possess an algebraic semantics. Necessary conditions for the existence of an algebraic semantics are given, and an example of a protoalgebraic deductive system that does not have an algebraic semantics is provided. The mono-unary deductive systems possessing an algebraic semantics are characterized. Finally, weak conditions on a deductive system are formulated that guarantee the existence of an algebraic semantics. These conditions are used to show that various classes of non-algebraizable deductive systems of modal logic, relevance logic and linear logic do possess an algebraic semantics.     

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