We discuss the interpolation property on some important families of non classical logics, such as intuitionistic, modal, fuzzy, and linear logics. A special paragraph is devoted to a generalization of the interpolation property, uniform interpolation.

This paper studies a combined system of intuitionistic and classical propositional logic from proof-theoretic viewpoints. Based on the semantic treatment of Humberstone (J Philos Log 8:171–196, 1979) and del Cerro and Herzig (Frontiers of combining systems: FroCoS, Springer, 1996), a sequent calculus \(\textsf{G}(\textbf{C}+\textbf{J})\) is proposed. An approximate idea of obtaining \(\textsf{G}(\textbf{C}+\textbf{J})\) is adding rules for classical implication on top of the intuitionistic multi-succedent sequent calculus by Maehara (Nagoya Math J 7:45–64, 1954). However, in the semantic treatment, some formulas do not (...) satisfy heredity, which leads to the necessity of a restriction on the right rule for intuitionistic implication to keep the soundness of the calculus. The calculus \(\textsf{G}(\textbf{C}+\textbf{J})\) enjoys cut elimination and Craig interpolation, whose detailed proofs are described in this paper. Cut elimination enables us to show the decidability of this combination both directly and syntactically. This paper also employs a canonical model argument to establish the strong completeness of Hilbert system \(\mathbf {C+J}\) proposed by del Cerro and Herzig (Frontiers of combining systems: FroCoS, Springer, 1996). (shrink)

The main result proves Lyndon’s and Craig’s interpolation properties for the logic of strict implication ${\textsf{F}}$, with a purely syntactical method. A cut-free G3-style sequent calculus $ {\textsf{GF}} $ and its single-succedent variant $ \textsf{GF}_{\textsf{s}} $ are introduced. $ {\textsf{GF}} $ can be extended to a G3-variant of the sequent calculus GBPC3 for Visser’s basic logic. Also a simple syntactic proof of known embedding result of $ {\textsf{F}} $ into $ {\textsf{K}} $ is provided. An extension of $ {\textsf{F}} $, (...) namely $ \textsf{FD}, $ is considered as well. (shrink)

In recent years, the logic of questions and dependencies has been investigated in the closely related frameworks of inquisitive logic and dependence logic. These investigations have assumed classical logic as the background logic of statements, and added formulas expressing questions and dependencies to this classical core. In this paper, we broaden the scope of these investigations by studying questions and dependency in the context of intuitionistic logic. We propose an intuitionistic team semantics, where teams are embedded within intuitionistic Kripke models. (...) The associated logic is a conservative extension of intuitionistic logic with questions and dependence formulas. We establish a number of results about this logic, including a normal form result, a completeness result, and translations to classical inquisitive logic and modal dependence logic. (shrink)

This paper is concerned with notions of consequence. On the one hand, we study admissible consequence, specifically for substitutions of Σ 1 0 -sentences over Heyting arithmetic . On the other hand, we study preservativity relations. The notion of preservativity of sentences over a given theory is a dual of the notion of conservativity of formulas over a given theory. We show that admissible consequence for Σ 1 0 -substitutions over HA coincides with NNIL -preservativity over intuitionistic propositional logic . (...) Here NNIL is the class of propositional formulas with no nestings of implications to the left . The identical embedding of IPC -derivability into a consequence relation has in many cases a left adjoint. The main tool of the present paper will be an algorithm to compute this left adjoint in the case of NNIL -preservativity. In the last section, we employ the methods developed in the paper to give a characterization the closed fragment of the provability logic of HA. (shrink)

This paper is concerned with the logical structure of arithmetical theories. We survey results concerning logics and admissible rules of constructive arithmetical theories. We prove a new theorem: the admissible propositional rules of Heyting Arithmetic are the same as the admissible propositional rules of Intuitionistic Propositional Logic. We provide some further insights concerning predicate logical admissible rules for arithmetical theories.

Fine and Kripke extended S5, S4, S4.2 and such to produce propositionally quantified systems , , : given a Kripke frame, the quantifiers range over all the sets of possible worlds. is decidable and, as Fine and Kripke showed, many of the other systems are recursively isomorphic to second-order logic. In the present paper I consider the propositionally quantified system that arises from the topological semantics for S4, rather than from the Kripke semantics. The topological system, which I dub , (...) is strictly weaker than its Kripkean counterpart. I prove here that second-order arithmetic can be recursively embedded in . In the course of the investigation, I also sketch a proof of Fine's and Kripke's results that the Kripkean system is recursively isomorphic to second-order logic. (shrink)

Rybakov (1984a) proved that the admissible rules of IPC are decidable. We give a proof of the same theorem, using the same core idea, but couched in the many notions that have been developed in the mean time. In particular, we illustrate how the argument can be interpreted as using refinements of the notions of exactness and extendibility.

This volume is dedicated to Prof. Dag Prawitz and his outstanding contributions to philosophical and mathematical logic. Prawitz's eminent contributions to structural proof theory, or general proof theory, as he calls it, and inference-based meaning theories have been extremely influential in the development of modern proof theory and anti-realistic semantics. In particular, Prawitz is the main author on natural deduction in addition to Gerhard Gentzen, who defined natural deduction in his PhD thesis published in 1934. The book opens with an (...) introductory paper that surveys Prawitz's numerous contributions to proof theory and proof-theoretic semantics and puts his work into a somewhat broader perspective, both historically and systematically. Chapters include either in-depth studies of certain aspects of Dag Prawitz's work or address open research problems that are concerned with core issues in structural proof theory and range from philosophical essays to papers of a mathematical nature. Investigations into the necessity of thought and the theory of grounds and computational justifications as well as an examination of Prawitz's conception of the validity of inferences in the light of three “dogmas of proof-theoretic semantics” are included. More formal papers deal with the constructive behaviour of fragments of classical logic and fragments of the modal logic S4 among other topics. In addition, there are chapters about inversion principles, normalization of p roofs, and the notion of proof-theoretic harmony and other areas of a more mathematical persuasion. Dag Prawitz also writes a chapter in which he explains his current views on the epistemic dimension of proofs and addresses the question why some inferences succeed in conferring evidence on their conclusions when applied to premises for which one already possesses evidence. (shrink)

This paper is concerned with notions of consequence. On the one hand, we study admissible consequence, specifically for substitutions of Σ 1 0 -sentences over Heyting arithmetic . On the other hand, we study preservativity relations. The notion of preservativity of sentences over a given theory is a dual of the notion of conservativity of formulas over a given theory. We show that admissible consequence for Σ 1 0 -substitutions over HA coincides with NNIL -preservativity over intuitionistic propositional logic . (...) Here NNIL is the class of propositional formulas with no nestings of implications to the left . The identical embedding of IPC -derivability into a consequence relation has in many cases a left adjoint. The main tool of the present paper will be an algorithm to compute this left adjoint in the case of NNIL -preservativity. In the last section, we employ the methods developed in the paper to give a characterization the closed fragment of the provability logic of HA. (shrink)

We give alternative characterizations of exact, extendible and projective formulas in intuitionistic propositional calculus IPC in terms of n-universal models. From these characterizations we derive a new syntactic description of all extendible formulas of IPC in two variables. For the formulas in two variables we also give an alternative proof of Ghilardi’s theorem that every extendible formula is projective.

We study finitely generated free Heyting algebras from a topological and from a model theoretic point of view. We review Bellissima’s representation of the finitely generated free Heyting algebra; we prove that it yields an embedding in the profinite completion, which is also the completion with respect to a naturally defined metric. We give an algebraic interpretation of the Kripke model used by Bellissima as the principal ideal spectrum and show it to be first order interpretable in the Heyting algebra, (...) from which several model theoretic and algebraic properties are derived. In particular, we prove that a free finitely generated Heyting algebra has only one set of free generators, which is definable in it. As a consequence its automorphism group is the permutation group over its generators. (shrink)

We show that (contrary to the parallel case of intuitionistic logic, see [7], [4]) there does not exist a translation fromS42 (the propositional modal systemS4 enriched with propositional quantifiers) intoS4 that preserves provability and reduces to identity for Boolean connectives and.

Rybakov proved that the admissible rules of $\mathsf {IPC}$ are decidable. We give a proof of the same theorem, using the same core idea, but couched in the many notions that have been developed in the mean time. In particular, we illustrate how the argument can be interpreted as using refinements of the notions of exactness and extendibility.

We give a syntactic translation from first-order intuitionistic predicate logic into second-order intuitionistic propositional logic IPC2. The translation covers the full set of logical connectives ∧, ∨, →, ⊥, ∀, and ∃, extending our previous work, which studied the significantly simpler case of the universal-implicational fragment of predicate logic. As corollaries of our approach, we obtain simple proofs of nondefinability of ∃ from the propositional connectives and nondefinability of ∀ from ∃ in the second-order intuitionistic propositional logic. We also show (...) that the ∀-free fragment of IPC2 is undecidable. (shrink)

A method is presented that connects the existence of uniform interpolants to the existence of certain sequent calculi. This method is applied to several modal logics and is shown to cover known results from the literature, such as the existence of uniform interpolants for the modal logic \. New is the result that \ has uniform interpolation. The results imply that for modal logics \ and \, which are known not to have uniform interpolation, certain sequent calculi cannot exist.

Proof-theoretic methods are developed for subsystems of Johansson’s logic obtained by extending the positive fragment of intuitionistic logic with weak negations. These methods are exploited to establish properties of the logical systems. In particular, cut-free complete sequent calculi are introduced and used to provide a proof of the fact that the systems satisfy the Craig interpolation property. Alternative versions of the calculi are later obtained by means of an appropriate loop-checking history mechanism. Termination of the new calculi is proved, and (...) used to conclude that the considered logical systems are PSPACE-complete. (shrink)

Explicit description of maps definable by formulæ of the second order intuitionistic propositional calculus is given on two classes of linear Heyting algebras—the dense ones and the ones which possess successors. As a consequence, it is shown that over these classes every formula is equivalent to a quantifier free formula in the dense case, and to a formula with quantifiers confined to the applications of the successor in the second case.

Given the frequency of human error, it seems rational to believe that some of our own rational beliefs are false. This is the axiom of epistemic modesty. Unfortunately, using standard propositional quantification, and the usual relational semantics, this axiom is semantically inconsistent with a common logic for rational belief, namely KD45. Here we explore two alternative semantics for KD45 and the axiom of epistemic modesty. The first uses the usual relational semantics and bisimulation quantifiers. The second uses a topological semantics (...) and standard propositional quantification. We show the two different semantics validate many of the same formulas, though we do not know whether they validate exactly the same formulas. Along the way we address various philosophical concerns. (shrink)

We introduce and investigate the notion of uniform Lyndon interpolation property which is a strengthening of both uniform interpolation property and Lyndon interpolation property. We prove several propositional modal logics including \, \, \ and \ enjoy ULIP. Our proofs are modifications of Visser’s proofs of uniform interpolation property using layered bisimulations Gödel’96, logical foundations of mathematics, computer science and physics—Kurt Gödel’s legacy, Springer, Berlin, 1996). Also we give a new upper bound on the complexity of uniform interpolants for \ (...) and \. (shrink)

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.

Roelcke non-precompactness, simplicity, and non-amenability of the automorphism group of the Fraïssé limit of finite Heyting algebras are proved among others.

In this paper we present a general theory of normal forms, based on a categorial result for the free monoid construction. We shall use the theory mainly for proposictional modal logic, although it seems to have a wider range of applications. We shall formally represent normal forms as combinatorial objects, basically labelled trees and forests. This geometric conceptualization is implicit in and our approach will extend it to other cases and make it more direct: operations of a purely geometric and (...) combinatorial nature will be introduced in order to give a mathematical description of the basic logical/algebraic constructions .We begin by recalling the above-mentioned categorial construction: we need a careful inspection of it because in the various examples considered later we plan to deduce from it in a uniform way the normal forms and the description of finitely generated free algebras. This method always works whenever we can describe the category of algebras corresponding to the logic under consideration as a T-objects category. When this simple description seems not to be available, still the general theory might be of some interest, because a description of the category of algebras as a T-objects category plus equation is possible .The central part of the paper is more advanced and specific: we show how the general approach presented here can provide some insights even in the basic case of the modal system K. Section 4 contains a contribution to the theory of normal forms, namely the description of the uniform substitution. This result will enable us to give a duality theorem for the category of finitely generated free modal algebras and in Section 5 to provide a characterization of the collections of normal forms which happen to be normal forms for a logic, thus giving a description of the lattice of modal logics.Section 6 deals with some applications: we shall show how to use normal forms in order to prove for the modal system K the definability of higher-order propositional quantifiers and of the tense operator F .As to the prerequisites, the paper is almost self-contained. The reader is only assumed to have familiarity with standard techniques in algebraic logic ). Knowledge of the basic facts about adjoint functors is required too, see e.g. McLane or the appendix. (shrink)

In this paper we study the interpolation property in fragments of intuitionistic and propositional logic, using both proof theoretic and semantic techniques. We will also sketch some computational methods, based on the semantical techniques introduced, to obtain counterexamples in fragment where interpolation does not hold.

Under some assumptions on an equational theory S , we give a necessary and sufficient condition so that S admits a model completion. These assumptions are often met by the equational theories arising from logic. They say that the dual of the category of finitely presented S-algebras has some categorical stucture. The results of this paper combined with those of [7] show that all the 8 theories of amalgamable varieties of Heyting algebras [12] admit a model completion. Further applications to (...) varieties of modal algebras are given in [8]. (shrink)

We show that proofs in the intuitionistic propositional logic factor through interpolants-in this way we prove a stronger interpolation property than the usual one which gives only the existence of interpolants.Translating that to categorical terms, we show that Pushouts (bipushouts) of bicartesian closed categories have the interpolation property (Theorem 3.2).

I present a new syntactical method for proving the Interpolation Theorem for the implicational fragment of intuitionistic logic and its substructural subsystems. This method, like Prawitz’s, works on natural deductions rather than sequent derivations, and, unlike existing methods, always finds a ‘strongest’ interpolant under a certain restricted but reasonable notion of what counts as an ‘interpolant’.

We give alternative characterizations of exact, extendible and projective formulas in intuitionistic propositional calculus IPC in terms of n -universal models. From these characterizations we derive a new syntactic description of all extendible formulas of IPC in two variables. For the formulas in two variables we also give an alternative proof of Ghilardi’s theorem that every extendible formula is projective.

In this paper by using a model-theoretic approach, we prove Craig interpolation property for Formal Propositional Logic, FPL, Basic propositional logic, BPL and the uniform left-interpolation property for FPL. We also show that there are countably infinite extensions of FPL with the uniform interpolation property.

Necessary and sufficient conditions are presented for the (first-order) theory of a universal class of algebraic structures (algebras) to have a model completion, extending a characterization provided by Wheeler. For varieties of algebras that have equationally definable principal congruences and the compact intersection property, these conditions yield a more elegant characterization obtained (in a slightly more restricted setting) by Ghilardi and Zawadowski. Moreover, it is shown that under certain further assumptions on congruence lattices, the existence of a model completion implies (...) that the variety has equationally definable principal congruences. This result is then used to provide necessary and sufficient conditions for the existence of a model completion for theories of Hamiltonian varieties of pointed residuated lattices, a broad family of varieties that includes lattice-ordered abelian groups and MV-algebras. Notably, if the theory of a Hamiltonian variety of pointed residuated lattices has a model completion, it must have equationally definable principal congruences. In particular, the theories of lattice-ordered abelian groups and MV-algebras do not have a model completion, as first proved by Glass and Pierce, and Lacava, respectively. Finally, it is shown that certain varieties of pointed residuated lattices generated by their linearly ordered members, including lattice-ordered abelian groups and MV-algebras, can be extended with a binary operation to obtain theories that do have a model completion. (shrink)

A logic $\mathcal{L}$ is said to satisfy the descending chain condition, DCC, if any descending chain of formulas in $\mathcal{L}$ with ordering induced by $\vdash _{\mathcal{L}};$ eventually stops. In this short note, we first establish a general theorem, which states that if a propositional logic $\mathcal{L}$ satisfies both DCC and has the Craig Interpolation Property, CIP, then it satisfies the Uniform Interpolation Property, UIP, as well. As a result, by using the Nishimura lattice, we give a new simply proof of (...) uniform interpolation for $\textbf{IPL}_2$, the two-variable fragment of Intuitionistic Propositional Logic; and one-variable uniform interpolation for $\textbf{IPL}$. Also, we will see that the modal logics $\textbf{S}_4$ and $\textbf{K}_4$ do not satisfy atomic DCC. (shrink)

We show how mereotopological notions can be expressed by extending intuitionistic propositional logic with propositional quantification and a strong modal operator. We first prove completeness for the logics wrt Kripke models; then we trace the correspondence between Kripke models and topological spaces that have been enhanced with an explicit notion of expressible region. We show how some qualitative spatial notions can be expressed in topological terms. We use the semantical and topological results in order to show how in some extensions (...) of the logics it is possible to express connectedness, non-emptiness and a set of jointly exhaustive, pairwise disjoint, binary relations that play a significant role in qualitative spatial reasoning. (shrink)

The concept of “necessity of thought” plays a central role in Dag Prawitz’s essay “Logical Consequence from a Constructivist Point of View” (Prawitz 2005). The theme is later developed in various articles devoted to the notion of valid inference (Prawitz, 2009, forthcoming a, forthcoming b). In section 1 I explain how the notion of necessity of thought emerges from Prawitz’s analysis of logical consequence. I try to expound Prawitz’s views concerning the necessity of thought in sections 2, 3 and 4. (...) In sections 5 and 6 I discuss some problems arising with regard to Prawitz’s views. (shrink)

We investigate interpolation properties of many-valued propositional logics related to continuous t-norms. In case of failure of interpolation, we characterize the minimal interpolating extensions of the languages. For finite-valued logics, we count the number of interpolating extensions by Fibonacci sequences.

This paper provides a method to obtain terminating analytic calculi for a large class of intuitionistic modal logics. For a given logic L with a cut-free calculus G that is an extension of G3ip the method produces a terminating analytic calculus that is an extension of G4ip and equivalent to G. G4ip was introduced by Roy Dyckhoff in 1992 as a terminating analogue of the calculus G3ip for intuitionistic propositional logic. Thus this paper can be viewed as an extension of (...) Dyckhoff’s work to intuitionistic modal logic. (shrink)

We investigate degree of satisfiability questions in the context of Heyting algebras and intuitionistic logic. We classify all equations in one free variable with respect to finite satisfiability gap, and determine which common principles of classical logic in multiple free variables have finite satisfiability gap. In particular we prove that, in a finite non-Boolean Heyting algebra, the probability that a randomly chosen element satisfies $x \vee \neg x = \top $ is no larger than $\frac {2}{3}$. Finally, we generalize our (...) results to infinite Heyting algebras, and present their applications to point-set topology, black-box algebras, and the philosophy of logic. (shrink)

We show that Pitts' modeling of propositional quantification in intuitionistic logic (as the appropriate interpolants) does not coincide with the topological interpretation. This contrasts with the case of the monadic language and the interpretation over sufficiently regular topological spaces. We also point to the difference between the topological interpretation over sufficiently regular spaces and the interpretation of propositional quantifiers in Kripke models.