Algorithmic correspondence and canonicity for non-distributive logics

We extend the theory of unified correspondence to a broad class of logics with algebraic semantics given by varieties of normal lattice expansions (LEs), also known as ‘lattices with operators’. Specifically, we introduce a syntactic definition of the class of Sahlqvist formulas and inequalities which applies uniformly to each LE-signature and is given purely in terms of the order-theoretic properties of the algebraic interpretations of the logical connectives. We also introduce the algorithm ALBA, parametric in each LE-setting, which effectively computes first-order correspondents of LE-inequalities, and is guaranteed to succeed on a wide class of inequalities (the so-called inductive inequalities) which significantly extend the Sahlqvist class. Further, we show that every inequality on which ALBA succeeds is canonical. Projecting these results on specific signatures yields state-of-the-art correspondence and canonicity theory for many well known modal expansions of classical and intuitionistic logic and for substructural logics, from classical poly-modal logics to (bi-)intuitionistic modal logics to the Lambek calculus and its extensions, the Lambek-Grishin calculus, orthologic, the logic of (not necessarily distributive) De Morgan lattices, and the multiplicative-additive fragment of linear logic.     

Algorithmic correspondence and canonicity for distributive modal logic

We define the algorithm ALBA for the language of the same distributive modal logic (DML) for which a Sahlqvist theorem was proved by Gehrke, Nagahashi, and Venema. Successful executions of ALBA compute the local first-order correspondents of input DML inequalities, and also guarantee their canonicity. The class of inequalities on which ALBA is successful is strictly larger than the newly introduced class of inductive inequalities, which in its turn properly extends the Sahlqvist inequalities of Gehrke et al. Evidence is given to the effect that, as their name suggests, inductive inequalities are the distributive counterparts of the inductive formulas of Goranko and Vakarelov in the classical setting.     

Some Connections between Topological and Modal Logic

We study modal logics based on neighbourhood semantics using methods and theorems having their origin in topological model theory. We thus obtain general results concerning completeness of modal logics based on neighbourhood semantics as well as the relationship between neighbourhood and Kripke semantics. We also give a new proof for a known interpolation result of modal logic using an interpolation theorem of topological model theory.     

The bounded proof property via step algebras and step frames

The paper introduces semantic and algorithmic methods for establishing a variant of the analytic subformula property (called ‘the bounded proof property’, bpp) for modal propositional logics. The bpp is much weaker property than full cut-elimination, but it is nevertheless sufficient for establishing decidability results. Our methodology originated from tools and techniques developed on one side within the algebraic/coalgebraic literature dealing with free algebra constructions and on the other side from classical correspondence theory in modal logic. As such, our approach is orthogonal to recent literature based on proof-theoretic methods and, in a way, complements it.     

Canonical extensions of double quasioperator algebras: An algebraic perspective on duality for certain algebras with binary operations

The context for this paper is a class of distributive lattice expansions, called double quasioperator algebras (DQAs). The distinctive feature of these algebras is that their operations preserve or reverse both join and meet in each coordinate. Algebras of this type provide algebraic semantics for certain non-classical propositional logics. In particular, MV-algebras, which model the ?ukasiewicz infinite-valued logic, are DQAs.Varieties of DQAs are here studied through their canonical extensions. A variety of this type having additional operations of arity at least 2 may fail to be canonical; it is already known, for example, that the variety of MV-algebras is not. Non-canonicity occurs when basic operations have two distinct canonical extensions and both are necessary to capture the structure of the original algebra. This obstruction to canonicity is different in nature from that customarily found in other settings. A generalized notion of canonicity is introduced which is shown to circumvent the problem. In addition, generalized canonicity allows one to capture on the canonical extensions of DQAs the algebraic operations in such a way that the laws that these obey may be translated into first-order conditions on suitable frames. This correspondence may be seen as the algebraic component of duality, in a way which is made precise.In many cases of interest, binary residuated operations are present. An operation h which, coordinatewise, preserves ∨ and 0 lifts to an operation which is residuated, even when h is not. If h also preserves binary meet then the upper adjoints behave in a functional way on the frames.     

Frame definability in finitely valued modal logics

In this paper we study frame definability in finitely valued modal logics and establish two main results via suitable translations: (1) in finitely valued modal logics one cannot define more classes of frames than are already definable in classical modal logic (cf. [27, Thm. 8]), and (2) a large family of finitely valued modal logics define exactly the same classes of frames as classical modal logic (including modal logics based on finite Heyting and MV-algebras, or even BL-algebras). In this way one may observe, for example, that the celebrated Goldblatt–Thomason theorem applies immediately to these logics. In particular, we obtain the central result from [26] with a much simpler proof and answer one of the open questions left in that paper. Moreover, the proposed translations allow us to determine the computational complexity of a big class of finitely valued modal logics.     

Sequent Systems for Negative Modalities

Non-classical negations may fail to be contradictory-forming operators in more than one way, and they often fail also to respect fundamental meta-logical properties such as the replacement property. Such drawbacks are witnessed by intricate semantics and proof systems, whose philosophical interpretations and computational properties are found wanting. In this paper we investigate congruential non-classical negations that live inside very natural systems of normal modal logics over complete distributive lattices; these logics are further enriched by adjustment connectives that may be used for handling reasoning under uncertainty caused by inconsistency or undeterminedness. Using such straightforward semantics, we study the classes of frames characterized by seriality, reflexivity, functionality, symmetry, transitivity, and some combinations thereof, and discuss what they reveal about sub-classical properties of negation. To the logics thereby characterized we apply a general mechanism that allows one to endow them with analytic ordinary sequent systems, most of which are even cut-free. We also investigate the exact circumstances that allow for classical negation to be explicitly defined inside our logics.     

The Gödel-McKinsey-Tarski embedding for infinitary intuitionistic logic and its extensions

The Gödel-McKinsey-Tarski embedding allows to view intuitionistic logic through the lenses of modal logic. In this work, an extension of the modal embedding to infinitary intuitionistic logic is introduced. First, a neighborhood semantics for a family of axiomatically presented infinitary modal logics is given and soundness and completeness are proved via the method of canonical models. The semantics is then exploited to obtain a labelled sequent calculus with good structural properties. Next, soundness and faithfulness of the embedding are established by transfinite induction on the height of derivations: the proof is obtained directly without resorting to non-constructive principles. Finally, the modal embedding is employed in order to relate classical, intuitionistic and modal derivability in infinitary logic extended with axioms.     

On intuitionistic modal and tense logics and their classical companion logics: Topological semantics and bisimulations

We take the well-known intuitionistic modal logic of Fischer Servi with semantics in bi-relational Kripke frames, and give the natural extension to topological Kripke frames. Fischer Servi’s two interaction conditions relating the intuitionistic pre-order (or partial-order) with the modal accessibility relation generalize to the requirement that the relation and its inverse be lower semi-continuous with respect to the topology. We then investigate the notion of topological bisimulation relations between topological Kripke frames, as introduced by Aiello and van Benthem, and show that their topology-preserving conditions are equivalent to the properties that the inverse relation and the relation are lower semi-continuous with respect to the topologies on the two models. The first main result is that this notion of topological bisimulation yields semantic preservation w.r.t. topological Kripke models for both intuitionistic tense logics, and for their classical companion multi-modal logics in the setting of the Gödel translation. After giving canonical topological Kripke models for the Hilbert-style axiomatizations of the Fischer Servi logic and its classical companion logic, we use the canonical model in a second main result to characterize a Hennessy–Milner class of topological models between any pair of which there is a maximal topological bisimulation that preserve the intuitionistic semantics.     

Polymodal Lattices and Polymodal Logic

A polymodal lattice is a distributive lattice carrying an n-place operator preserving top elements and certain finite meets. After exploring some of the basic properties of such structures, we investigate their freely generated instances and apply the results to the corresponding logical systems — polymodal logics — which constitute natural generalizations of the usual systems of modal logic familiar from the literature. We conclude by formulating an extension of Kripke semantics to classical polymodal logic and proving soundness and completeness theorems. Mathematics Subject Classification: 03G10, 06D99, 03B45.     

Axiomatizations of team logics

In a modular approach, we lift Hilbert-style proof systems for propositional, modal and first-order logic to generalized systems for their respective team-based extensions. We obtain sound and complete axiomatizations for the dependence-free fragment FO(～) of Väänänen's first-order team logic TL, for propositional team logic PTL, quantified propositional team logic QPTL, modal team logic MTL, and for the corresponding logics of dependence, independence, inclusion and exclusion.As a crucial step in the completeness proof, we show that the above logics admit, in a particular sense, a semantics-preserving elimination of modalities and quantifiers from formulas.     

Fibered universal algebra for first-order logics

We extend Lawvere-Pitts prop-categories (aka. hyperdoctrines) to develop a general framework for providing fibered algebraic semantics for general first-order logics. This framework includes a natural notion of substitution, which allows first-order logics to be considered as structural closure operators just as propositional logics are in abstract algebraic logic. We then establish an extension of the homomorphism theorem from universal algebra for generalized prop-categories and characterize two natural closure operators on the prop-categorical semantics. The first closes a class of structures (which are interpreted as morphisms of prop-categories) under the satisfaction of their common first-order theory and the second closes a class of prop-categories under their associated first-order consequence. It turns out that these closure operators have characterizations that closely mirror Birkhoff's characterization of the closure of a class of algebras under the satisfaction of their common equational theory and Blok and Jónsson's characterization of closure under equational consequence, respectively. These algebraic characterizations of the first-order closure operators are unique to the prop-categorical semantics. They do not have analogues, for example, in the Tarskian semantics for classical first-order logic. The prop-categories we consider are much more general than traditional intuitionistic prop-categories or triposes (i.e., topos representing indexed partially ordered sets). Nonetheless, to the best of our knowledge, our results are new, even when restricted to these special classes of prop-categories.     

Some Multi-Conclusion Modal Paralogics

I give a systematic presentation of a fairly large family of multiple-conclusion modal logics that are paraconsistent and/or paracomplete. After providing motivation for studying such systems, I present semantics and tableau-style proof theories for them. The proof theories are shown to be sound and complete with respect to the semantics. I then show how the “standard” systems of classical, single-conclusion modal logics fit into the framework constructed.     

Reasoning about proof and knowledge

In previous work [15], we presented a hierarchy of classical modal systems, along with algebraic semantics, for the reasoning about intuitionistic truth, belief and knowledge. Deviating from Gödel's interpretation of IPC in S4, our modal systems contain IPC in the way established in [13]. The modal operator can be viewed as a predicate for intuitionistic truth, i.e. proof. Epistemic principles are partially adopted from Intuitionistic Epistemic Logic IEL [4]. In the present paper, we show that the S5-style systems of our hierarchy correspond to an extended Brouwer–Heyting–Kolmogorov interpretation and are complete w.r.t. a relational semantics based on intuitionistic general frames. In this sense, our S5-style logics are adequate and complete systems for the reasoning about proof combined with belief or knowledge. The proposed relational semantics is a uniform framework in which also IEL can be modeled. Verification-based intuitionistic knowledge formalized in IEL turns out to be a special case of the kind of knowledge described by our S5-style systems.     

Modal characterisation theorems over special classes of frames

We investigate model theoretic characterisations of the expressive power of modal logics in terms of bisimulation invariance. The paradigmatic result of this kind is van Benthem’s theorem, which says that a first-order formula is invariant under bisimulation if, and only if, it is equivalent to a formula of basic modal logic. The present investigation primarily concerns ramifications for specific classes of structures. We study in particular model classes defined through conditions on the underlying frames, with a focus on frame classes that play a major role in modal correspondence theory and often correspond to typical application domains of modal logics. Classical model theoretic arguments do not apply to many of the most interesting classes-for instance, rooted frames, finite rooted frames, finite transitive frames, well-founded transitive frames, finite equivalence frames-as these are not elementary. Instead we develop and extend the game-based analysis (first-order Ehrenfeucht-Fraïssé versus bisimulation games) over such classes and provide bisimulation preserving model constructions within these classes. Over most of the classes considered, we obtain finite model theory analogues of the classically expected characterisations, with new proofs also for the classical setting. The class of transitive frames is a notable exception, with a marked difference between the classical and the finite model theory of bisimulation invariant first-order properties. Over the class of all finite transitive frames in particular, we find that monadic second-order logic is no more expressive than first-order as far as bisimulation invariant properties are concerned — though both are more expressive here than basic modal logic. We obtain ramifications of the de Jongh-Sambin theorem and a new and specific analogue of the Janin-Walukiewicz characterisation of bisimulation invariant monadic second-order for finite transitive frames.     

Existential definability of modal frame classes

We prove an existential analogue of the Goldblatt-Thomason Theorem which characterizes modal definability of elementary classes of Kripke frames using closure under model theoretic constructions. The less known version of the Goldblatt-Thomason Theorem gives general conditions, without the assumption of first-order definability, but uses non-standard constructions and algebraic semantics. We present a non-algebraic proof of this result and we prove an analogous characterization for an alternative notion of modal definability, in which a class is defined by formulas which are satisfiable under any valuation (the so-called existential validity). Continuing previous work in which model theoretic characterization for this type of definability of elementary classes was proved, we give an analogous general result without the assumption of the first-order definability. Furthermore, we outline relationships between sets of existentially valid formulas corresponding to several well-known modal logics.     

Modal Extensions of Sub-classical Logics for Recovering Classical Logic

In this paper we introduce non-normal modal extensions of the sub-classical logics CLoN, CluN and CLaN, in the same way that S0.5 ⁰ extends classical logic. The first modal system is both paraconsistent and paracomplete, while the second one is paraconsistent and the third is paracomplete. Despite being non-normal, these systems are sound and complete for a suitable Kripke semantics. We also show that these systems are appropriate for interpreting □ as “is provable in classical logic”. This allows us to recover the theorems of propositional classical logic within three sub-classical modal systems.     

Dung’s Argumentation is Essentially Equivalent to Classical Propositional Logic with the Peirce–Quine Dagger

In this paper we show that some versions of Dung’s abstract argumentation frames are equivalent to classical propositional logic. In fact, Dung’s attack relation is none other than the generalised Peirce–Quine dagger connective of classical logic which can generate the other connectives ?, ù, ú, ?{\neg, \wedge, \vee, \to} of classical logic. After establishing the above correspondence we offer variations of the Dung argumentation frames in parallel to variations of classical logic, such as resource logics, predicate logic, etc., etc., and create resource argumentation frames, predicate argumentation frames, etc., etc. We also offer the notion of logic proof as a geometrical walk along the nodes of a Dung network and thus we are able to offer a geometrical abstraction of the notion of inference based argumentation. Thus our paper is also a contribution to the question:     

Kripke‐style semantics for many‐valued logics

This paper deals with Kripke‐style semantics for many‐valued logics. We introduce various types of Kripke semantics, and we connect them with algebraic semantics. As for modal logics, we relate the axioms of logics extending MTL to properties of the Kripke frames in which they are valid. We show that in the propositional case most logics are complete but not strongly complete with respect to the corresponding class of complete Kripke frames, whereas in the predicate case there are important many‐valued logics like BL, ? and Π, which are not even complete with respect to the class of all predicate Kripke frames in which they are valid. Thus although very natural, Kripke semantics seems to be slightly less powerful than algebraic semantics. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Completeness for μ-calculi: A coalgebraic approach

We set up a generic framework for proving completeness results for variants of the modal mu-calculus, using tools from coalgebraic modal logic. We illustrate the method by proving two new completeness results: for the graded mu-calculus (which is equivalent to monadic second-order logic on the class of unranked tree models), and for the monotone modal mu-calculus.Besides these main applications, our result covers the Kozen–Walukiewicz completeness theorem for the standard modal mu-calculus, as well as the linear-time mu-calculus and modal fixpoint logics on ranked trees. Completeness of the linear-time mu-calculus is known, but the proof we obtain here is different and places the result under a common roof with Walukiewicz' result.Our approach combines insights from the theory of automata operating on potentially infinite objects, with methods from the categorical framework of coalgebra as a general theory of state-based evolving systems. At the interface of these theories lies the notion of a coalgebraic modal one-step language. One of our main contributions here is the introduction of the novel concept of a disjunctive basis for a modal one-step language. Generalizing earlier work, our main general result states that in case a coalgebraic modal logic admits such a disjunctive basis, then soundness and completeness at the one-step level transfer to the level of the full coalgebraic modal mu-calculus.