Hyperlogic is a hyperintensional system designed to regiment metalogical claims (e.g., “Intuitionistic logic is correct” or “The law of excluded middle holds”) into the object language, including within embedded environments such as attitude reports and counterfactuals. This paper is the first of a two-part series exploring the logic of hyperlogic. This part presents a minimal logic of hyperlogic and proves its completeness. It consists of two interdefined axiomatic systems: one for classical consequence (truth preservation under a classical interpretation of the (...) connectives) and one for “universal” consequence (truth preservation under any interpretation). The sequel to this paper explores stronger logics that are sound and complete over various restricted classes of models as well as languages with hyperintensional operators. (shrink)

We propose a new sequent calculus for bi intuitionistic logic which sits somewhere between display calculi and traditional sequent calculi by using nested sequents. Our calculus enjoys a simple (purely syntactic) cut elimination proof as do display calculi. But it has an easily derivable variant calculus which is amenable to automated proof search as are (some) traditional sequent calculi. We first present the initial calculus and its cut elimination proof. We then present the derived calculus, and then present a proof (...) search strategy which allows it to be used for automated proof search. We prove that this search strategy is terminating and complete by showing how it can be used to mimic derivations obtained from an existing calculus GBiInt for bi intuitionistic logic. As far as we know, our new calculus is the first sequent calculus for bi intuitionistic logic which uses no semantic additions like labels, which has a purely syntactic cut elimination proof, and which can be used naturally for backwards proof search. Keywords: Bi-intuitionistic logic, display calculi, proof search. (shrink)

In this paper we explain our pretense account of truth-talk and apply it in a diagnosis and treatment of the Liar Paradox. We begin by assuming that some form of deflationism is the correct approach to the topic of truth. We then briefly motivate the idea that all T-deflationists should endorse a fictionalist view of truth-talk, and, after distinguishing pretense-involving fictionalism (PIF) from error- theoretic fictionalism (ETF), explain the merits of the former over the latter. After presenting the basic framework (...) of our PIF account of truth-talk, we demonstrate a few advantages it offers over T-deflationist accounts that do not explicitly acknowledge pretense at work in the discourse. In turning to the Liar Paradox, we explain how the quasi-anaphoric functioning that our account attributes to truth-talk provides a diagnosis of the Liar Paradox (and other instances of semantic pathology) as having no content—in the sense of not specifying any of what we call M-conditions. At the same time, however, we vindicate the intuition that we can understand liar sentences, thereby avoiding one standard objection to “meaningless strategy” responses to the Liar Paradox. With this diagnosis in place, we then, by way of treatment, introduce a new predicate, ‘semantically defective’, and show how the explanation we give for its application allows for a consistent, yet revenge-immune, (dis)solution of the Liar Paradox, and semantic pathology generally. (shrink)

Labelled sequent calculi are provided for a wide class of normal modal systems using truth values as labels. The rules for formula constructors are common to all modal systems. For each modal system, specific rules for truth values are provided that reflect the envisaged properties of the accessibility relation. Both local and global reasoning are supported. Strong completeness is proved for a natural two-sorted algebraic semantics. As a corollary, strong completeness is also obtained over general Kripke semantics. A duality result (...) is established between the category of sober algebras and the category of general Kripke structures. A simple enrichment of the proposed sequent calculi is proved to be complete over standard Kripke structures. The calculi are shown to be analytic in a useful sense. (shrink)

This book provides a detailed exposition of one of the most practical and popular methods of proving theorems in logic, called Natural Deduction. It is presented both historically and systematically. Also some combinations with other known proof methods are explored. The initial part of the book deals with Classical Logic, whereas the rest is concerned with systems for several forms of Modal Logics, one of the most important branches of modern logic, which has wide applicability.

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 proofs, 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)

A new combined temporal logic called synchronized linear-time temporal logic (SLTL) is introduced as a Gentzen-type sequent calculus. SLTL can represent the n -Cartesian product of the set of natural numbers. The cut-elimination and completeness theorems for SLTL are proved. Moreover, a display sequent calculus δ SLTL is defined.

It is shown that the constructive four-valued logic N4 can be faithfully embedded into the modal logic S4. This embedding is used to obtain complete, cut-free display sequent calculi for N4 and C4, the modal logic of consistency over N4. C4 is a natural monotonic base system for semantics-based non-monotonic reasoning.

In this paper, a family of paraconsistent propositional logics with constructive negation, constructive implication, and constructive co-implication is introduced. Although some fragments of these logics are known from the literature and although these logics emerge quite naturally, it seems that none of them has been considered so far. A relational possible worlds semantics as well as sound and complete display sequent calculi for the logics under consideration are presented.

We introduce necessary and sufficient conditions for a (single-conclusion) sequent calculus to admit (reductive) cut-elimination. Our conditions are formulated both syntactically and semantically.

In this paper we elaborate a conception of entailment based on what we call the Ackermann principle, which explicates valid entailment through a logical connection between sentences depending on their informational content. We reconstruct Dunn’s informational semantics for entailment on the basis of Restall’s approach, with assertion and denial as two independent speech acts, by introducing the notion of a ‘position description’. We show how the machinery of position descriptions can effectively be used to define the positive and the negative (...) information carried by sentences of a given language and to present a formalized version of the Ackermann principle as an inclusion relationship between the informational contents of the conclusions and the premises of a valid entailment. Being so interpreted, the entailment relation exhibits certain properties, including the property of transitivity. Whereas properties such as Anderson and Belnap’s variable sharing property or Parry’s proscriptive principle are normally presented as imposing a relevance requirement on valid entailment, the suggested formalization of the Ackermann principle supports all of Gentzen’s structural rules, including weakening, a rule that is normally given up in sequent-style proof systems for relevance logics. In this way we propose an Ackermann-inspired explication of the nature of entailment as a relation between the informational contents of sentences. (shrink)

The interpretation of implications as rules motivates a different left-introduction schema for implication in the sequent calculus, which is conceptually more basic than the implication-left schema proposed by Gentzen. Corresponding to results obtained for systems with higher-level rules, it enjoys the subformula property and cut elimination in a weak form.

We introduce a sequent calculus B for a new logic, named basic logic. The aim of basic logic is to find a structure in the space of logics. Classical, intuitionistic, quantum and non-modal linear logics, are all obtained as extensions in a uniform way and in a single framework. We isolate three properties, which characterize B positively: reflection, symmetry and visibility. A logical constant obeys to the principle of reflection if it is characterized semantically by an equation binding it with (...) a metalinguistic link between assertions, and if its syntactic inference rules are obtained by solving that equation. All connectives of basic logic satisfy reflection. To the control of weakening and contraction of linear logic, basic logic adds a strict control of contexts, by requiring that all active formulae in all rules are isolated, that is visible. From visibility, cut-elimination follows. The full, geometric symmetry of basic logic induces known symmetries of its extensions, and adds a symmetry among them, producing the structure of a cube. (shrink)

We introduce a sequent calculusBfor a new logic, named basic logic. The aim of basic logic is to find a structure in the space of logics. Classical, intuitionistic. quantum and non-modal linear logics, are all obtained as extensions in a uniform way and in a single framework. We isolate three properties, which characterizeBpositively: reflection, symmetry and visibility.A logical constant obeys to the principle of reflection if it is characterized semantically by an equation binding it with a metalinguistic link between assertions, (...) and if its syntactic inference rules are obtained by solving that equation. All connectives of basic logic satisfy reflection.To the control of weakening and contraction of linear logic, basic logic adds a strict control of contexts, by requiring that all active formulae in all rules are isolated, that is visible. From visibility, cut-elimination follows. The full, geometric symmetry of basic logic induces known symmetries of its extensions, and adds a symmetry among them, producing the structure of a cube. (shrink)

In some logics, anything whatsoever follows from a contradiction; call these logics explosive. Paraconsistent logics are logics that are not explosive. Paraconsistent logics have a long and fruitful history, and no doubt a long and fruitful future. To give some sense of the situation, I’ll spend Section 1 exploring exactly what it takes for a logic to be paraconsistent. It will emerge that there is considerable open texture to the idea. In Section 2, I’ll give some examples of techniques for (...) developing paraconsistent logics. In Section 3, I’ll discuss what seem to me to be some promising applications of certain paraconsistent logics. In fact, however, I don’t think there’s all that much to the concept ‘paraconsistent’ itself; the collection of paraconsistent logics is far too heterogenous to be very productively dealt with under a single label. Perhaps that will emerge as we go. (shrink)

In this paper we introduce a new natural deduction system for the logic of lattices, and a number of extensions of lattice logic with different negation connectives. We provide the class of natural deduction proofs with both a standard inductive definition and a global graph-theoretical criterion for correctness, and we show how normalisation in this system corresponds to cut elimination in the sequent calculus for lattice logic. This natural deduction system is inspired both by Shoesmith and Smiley's multiple conclusion systems (...) for classical logic and Girard's proofnets for linear logic. (shrink)

Different natural deduction proof systems for intuitionistic and classical logic —and related logical systems—differ in fundamental properties while sharing significant family resemblances. These differences become quite stark when it comes to the structural rules of contraction and weakening. In this paper, I show how Gentzen and Jaśkowski’s natural deduction systems differ in fine structure. I also motivate directed proof nets as another natural deduction system which shares some of the design features of Genzen and Jaśkowski’s systems, but which differs again (...) in its treatment of the structural rules, and has a range of virtues absent from traditional natural deduction systems. (shrink)

Many logics in the relevant family can be given a proof theory in the style of Belnap's display logic. 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.

his paper provides a sound and complete axiomatisation for constant domain modal logics without Boolean negation. This is a simpler case of the difficult problem of providing a sound and complete axiomatisation for constant-domain quantified relevant logics, which can be seen as a kind of modal logic with a two-place modal operator, the relevant conditional. The completeness proof is adapted from a proof for classical modal predicate logic (I follow James Garson’s 1984 presentation of the completeness proof quite closely), but (...) with an important twist, to do with the absence of Boolean negation. (shrink)

Sufficient conditions for first-order-based sequent calculi to admit cut elimination by a Schütte–Tait style cut elimination proof are established. The worst case complexity of the cut elimination is analysed. The obtained upper bound is parameterized by a quantity related to the calculus. The conditions are general enough to be satisfied by a wide class of sequent calculi encompassing, among others, some sequent calculi presentations for the first order and the propositional versions of classical and intuitionistic logic, classical and intuitionistic modal (...) logic S4, and classical and intuitionistic linear logic and some of its fragments. Moreover the conditions are such that there is an algorithm for checking if they are satisfied by a sequent calculus. (shrink)

In this paper we introduce and compare four different syntactic methods for generating sequent calculi for the main systems of modal logic: the multiple sequents method, the higher-arity sequents method, the tree-hypersequents method and the display method. More precisely we show how the first three methods can all be translated in the fourth one. This result sheds new light on these generalisations of the sequent calculus and raises issues that will be examined in the last section.

Dans la philosophie de Hintikka la notion d'analyticité occupe une place particulière ; plus précisément, le philosophe finnois distingue deux notions d'analyticité : l'une qui est basée sur la notion d'information, l'autre sur la notion de preuve. Alors que ces deux notions ont été largement utilisées pour étudier la logique propositionnelle et la logique du premier ordre, aucun travail n'a été développé pour la logique modale. Cet article se propose de combler cette lacune et ainsi d'examiner l'analyticité des validités de (...) la logique modale. (shrink)

Dans la philosophie de Hintikka la notion d'analyticité occupe une place particulière (e.g., [Hintikka 1973], [Hintikka 2007]) ; plus précisément, le philosophe finnois distingue deux notions d'analyticité : l'une qui est basée sur la notion d'information, l'autre sur la notion de preuve. Alors que ces deux notions ont été largement utilisées pour étudier la logique propositionnelle et la logique du premier ordre, aucun travail n'a été développé pour la logique modale. Cet article se propose de combler cette lacune et ainsi (...) d'examiner l'analyticité des validités de la logique modale. (shrink)

ABSTRACTMonoidal logics were introduced as a foundational framework to analyze the proof theory of logical systems. Inspired by Lambek's seminal work in categorical logic, the objective is to defin...

Monoidal logics were introduced as a foundational framework to analyse the proof theory of deontic logic. Building on Lambek’s work in categorical logic, logical systems are defined as deductive systems, that is, as collections of equivalence classes of proofs satisfying specific rules and axiom schemata. This approach enables the classification of deductive systems with respect to their categorical structure. When looking at their proof theory, however, one can see that there are similarities between monoidal and substructural logics. The purpose of (...) the present paper is to address this issue and highlight the differences between these two approaches. We argue that monoidal logics provide a more flexible foundational framework that enables a finer analysis of the relationship between negation and other logical connectives. We show that the elimination of double negation is independent from the de Morgan dualities, that monoidal deductive systems are not necessarily weakly distributive and that deduc... (shrink)

The standard inferentialist approaches to modal logic tend to suffer from not being able to uniquely characterize the modal operators, require that introduction and elimination rules be interdefined, or rely on the introduction of possible-world like indexes into the object language itself. In this paper I introduce a hypersequent calculus that is flexible enough to capture many of the standard modal logics and does not suffer from the above problems. It is therefore an ideal candidate to underwrite an inferentialist theory (...) of meaning for modal operators. Here I treat specifically the modal logics K, D, T, S4, B, and S5. I show that the calculi are adequate for each set of models, and show that they meet a large set of criteria that are generally thought necessary for a calculus to underwrite a theory of meaning. (shrink)

I discuss paradoxes of implication in the setting of a proof-conditional theory of meaning for logical constants. I argue that a proper logic of implication should be not only relevant, but also constructive and nonmonotonic. This leads me to select as a plausible candidate LL, a fragment of linear logic that differs from R in that it rejects both contraction and distribution.

A method is presented for constructing natural deduction-style systems for propositional relevant logics. The method consists in first translating formulas of relevant logics into ternary relations, and then defining deduction rules for a corresponding logic of ternary relations. Proof systems of that form are given for various relevant logics. A class of algebras of ternary relations is introduced that provides a relation-algebraic semantics for relevant logics.

We present substructural negations, a family of negations classified in terms of structural rules of an extended kind of sequent calculus, display calculus. In considering the whole picture, we emphasize the duality of negation. Two types of negative modality, impossibility and unnecessity, are discussed and "self-dual" negations like Classical, De Morgan, or Ockham negation are redefined as the fusions of two negative modalities. We also consider how to identify, using intuitionistic and dual intuitionistic negations, two accessibility relations associated with impossibility (...) and unnecessity. (shrink)

A star-free relational semantics for relevant logic is presented together with a sound and complete sequent proof theory. It is an extension of the dualist approach to negation regarded as modality, according to which de Morgan negation in relevant logic is better understood as the confusion of two negative modalities. The present work shows a way to define them in terms of implication and a new connective, co-implication, which is modeled by respective ternary relations. The defined negations are confused by (...) a special constraint on ternary relation, called the generalized star postulate, which implies definability of the Routley star in the frame. The resultant logic is shown to be equivalent to the well-known relevant logic R. Thus it can be seen as a reconstruction of R in the dualist framework. (shrink)

We introduce a logic BI in which a multiplicative (or linear) and an additive (or intuitionistic) implication live side-by-side. The propositional version of BI arises from an analysis of the proof-theoretic relationship between conjunction and implication; it can be viewed as a merging of intuitionistic logic and multiplicative intuitionistic linear logic. The naturality of BI can be seen categorically: models of propositional BI's proofs are given by bicartesian doubly closed categories, i.e., categories which freely combine the semantics of propositional intuitionistic (...) logic and propositional multiplicative intuitionistic linear logic. The predicate version of BI includes, in addition to standard additive quantifiers, multiplicative (or intensional) quantifiers ∀ new and ∃ new which arise from observing restrictions on structural rules on the level of terms as well as propositions. We discuss computational interpretations, based on sharing, at both the propositional and predicate levels. (shrink)

The axiomatic presentation of modal systems and the standard formulations of natural deduction and sequent calculus for modal logic are reviewed, together with the difficulties that emerge with these approaches. Generalizations of standard proof systems are then presented. These include, among others, display calculi, hypersequents, and labelled systems, with the latter surveyed from a closer perspective.

In this paper we compare grammatical inference in the context of simple and of mixed Lambek systems. Simple Lambek systems are obtained by taking the logic of residuation for a family of multiplicative connectives /,,\, together with a package of structural postulates characterizing the resource management properties of the connective.Different choices for Associativity and Commutativity yield the familiar logics NL, L, NLP, LP. Semantically, a simple Lambek system is a unimodal logic: the connectives get a Kripke style interpretation in terms (...) of a single ternary accessibility relation modeling the notion of linguistic composition for each individual system.The simple systems earch have their virtues in linguistic analysis. But none of them in isolation provides a basis for a full theory of grammar. In the second part of the paper, we consider two types of mixed Lambek systems. (shrink)

We present a rooted hypersequent calculus for modal propositional logic S5. We show that all rules of this calculus are invertible and that the rules of weakening, contraction, and cut are admissible. Soundness and completeness are established as well.

Cut reductions are defined for a Kripke-style formulation of modal logic in terms of indexed systems of sequents. A detailed proof of the normalization (cutelimination) theorem is given. The proof is uniform for the propositional modal systems with all combinations of reflexivity, symmetry and transitivity for the accessibility relation. Some new transformations of derivations (compared to standard sequent formulations) are needed, and some additional properties are to be checked. The display formulations [1] of the systems considered can be presented as (...) encodings of Kripke-style formulations. (shrink)

In this paper we study proof procedures for some variants of first-order modal logics, where domains may be either cumulative or freely varying and terms may be either rigid or non-rigid, local or non-local. We define both ground and free variable tableau methods, parametric with respect to the variants of the considered logics. The treatment of each variant is equally simple and is based on the annotation of functional symbols by natural numbers, conveying some semantical information on the worlds where (...) they are meant to be interpreted.This paper is an extended version of a previous work where full proofs were not included. Proofs are in some points rather tricky and may help in understanding the reasons for some details in basic definitions. (shrink)

The aim of this paper is to introduce and explain display calculi for a variety of logics. We provide a survey of key results concerning such calculi, though we focus mainly on the global cut elimination theorem. Propositional, first-order, and modal display calculi are considered and their properties detailed.

There is a natural story about what logic is that sees it as tied up with two operations: a ‘throw things into a bag’ operation and a ‘closure’ operation. In a pair of recent papers, Jc Beall has fleshed out the account of logic this leaves us with in more detail. Using Beall’s exposition as a guide, this paper points out some problems with taking the second operation to be closure in the usual sense. After pointing out these problems, I (...) then turn to fixing them in a restricted case and modulo a few simplifying assumptions. In a followup paper, the simplifications and restrictions will be removed. (shrink)

A cut-free Gentzen sequent calculus for Ewald’s intuitionistic tense logic \ is established. By the proof-theoretic method, we prove that, for every set of strictly positive implications S, the classical tense logic \ is embedded into its intuitionistic analogue \ via Kolmogorov, Gödel–Genzten and Kuroda translations respectively. A sufficient and necessary condition for Glivenko type theorem in tense logics is established.

Restall :279–291, 2014) proposes a new, proof-theoretic, logical pluralism. This is in contrast to the model-theoretic pluralism he and Beall proposed in Beall and Restall :475–493, 2000) and in Beall and Restall. What I will show is that Restall has not described the conditions on being admissible to the proof-theoretic logical pluralism in such a way that relevance logic is one of the admissible logics. Though relevance logic is not hard to add formally, one critical component of Restall’s pluralism is (...) that the relevance logic that gets added must have connectives which mean the same thing as the connectives in the already admitted logic. This is what I will show is not possible. (shrink)

We study two logics of knowledge and belief stemming from the work of Stalnaker, omitting positive introspection for knowledge. The two systems are equivalent with positive introspection, but not without. We show that while the logic of beliefs remains unaffected by omitting introspection for knowledge in one system, it brings significant changes to the other. The resulting logic of belief is non-normal, and its complete axiomatization uses an infinite hierarchy of coherence constraints. We conclude by returning to the philosophical interpretation (...) underlying both models of belief, showing that neither is strong enough to support a probabilistic interpretation, nor an interpretation in terms of certainty or the “mental component” of knowledge. (shrink)

We study two logics of knowledge and belief stemming from the work of Stalnaker, omitting positive introspection for knowledge. The two systems are equivalent with positive introspection, but not without. We show that while the logic of beliefs remains unaffected by omitting introspection for knowledge in one system, it brings significant changes to the other. The resulting logic of belief is non-normal, and its complete axiomatization uses an infinite hierarchy of coherence constraints. We conclude by returning to the philosophical interpretation (...) underlying both models of belief, showing that neither is strong enough to support a probabilistic interpretation, nor an interpretation in terms of certainty or the “mental component” of knowledge. (shrink)