Search

We provide a non-Gentzen, though fully syntactical, cut-elimination algorithm for classical propositional logic. The designed procedure is implemented on GS 4 , the one-sided version of Kleene's sequent system G 4 . The algorithm here proposed proves to be more 'dexterous' than other, more traditional, Gentzen-style techniques as the size of proofs decreases at each step of reduction. As a corollary result, we show that analyticity always guarantees minimality of the size of GS 4 -proofs. [ABSTRACT FROM AUTHOR]

We present a series of proof systems for exact entailment (i.e., relevant truthmaker preservation from premises to conclusion) and prove soundness and completeness. Using the proof systems, we observe that exact entailment is hyperintensional not only in the sense of Cresswell, but also in the sense recently proposed by Odintsov and Wansing. [ABSTRACT FROM AUTHOR]

We present a syntactical cut-elimination proof for an extended sequent calculus covering the classical modal logics in the K, D, T, K4, D4 and S4 spectrum. We design the systems uniformly since they all share the same set of rules. Different logics are obtained by "tuning" a single parameter, namely a constraint on the applicability of the cut rule and on the (left and right, respectively) rules for □ and ♢. Starting points for this research are 2-sequents and indexed-based calculi (sequents and tableaux). By extending and modifying existing proposals, we show how to achieve a syntactical proof of the cut-elimination theorem that is as close as possible to the one for first-order classical logic. In doing this, we implicitly show how small is the proof-theoretical distance between classical logic and the systems under consideration. [ABSTRACT FROM AUTHOR]

In this paper we will consider the existing notions of bilateralism in the context of proof-theoretic semantics and propose, based on our understanding of bilateralism, an extension to logical multilateralism. This approach differs from what has been proposed under this name before in that we do not consider multiple speech acts as the core of such a theory but rather multiple consequence relations. We will argue that for this aim the most beneficial proof-theoretical realization is to use sequent calculi with multiple sequent arrows satisfying some specific conditions, which we will lay out in this paper. We will unfold our ideas with the help of a case study in logical tetralateralism and present an extension of Almukdad and Nelson's propositional constructive four-valued logic by unary operations of meaningfulness and nonsensicality. We will argue that in sequent calculi with multiple sequent arrows it is possible to maintain certain features that are desirable if we assume an understanding of the meaning of connectives in the spirit of proof-theoretic semantics. The use of multiple sequent arrows will be justified by the presence of congruentiality-breaking unary connectives. [ABSTRACT FROM AUTHOR]

Residuated basic logic (RBL) is the logic of residuated basic algebras, which constitutes a conservative extension of basic propositional logic (BPL). The basic implication is a residual of a non-associative binary operator in RBL. The conservativity is shown by relational semantics. A Gentzen-style sequent calculus GRBL , which is an extension of the distributive full non-associative Lambek calculus, is established for residuated basic logic. The calculus GRBL admits the mix-elimination, subformula, and disjunction properties. Moreover, the class of all residuated basic algebras has the finite embeddability property. The consequence relation of GRBL is decidable. [ABSTRACT FROM AUTHOR]

In this paper we use proof-theoretic methods, specifically sequent calculi, admissibility of cut within them and the resultant subformula property, to examine a range of philosophically-motivated deontic logics. We show that for all of those logics it is a (meta)theorem that the Special Hume Thesis holds, namely that no purely normative conclusion follows non-trivially from purely descriptive premises (nor vice versa). In addition to its interest on its own, this also illustrates one way in which proof theory sheds light on philosophically substantial questions. [ABSTRACT FROM AUTHOR]

The cut-free single-succedent Gentzen sequent calculus GK t for the minimal tense logic K t is introduced. This sequent calculus satisfies the displaying property. The proof proceeds in terms of a Kolmogorov translation and three intermediate sequent systems. Finally, we show that tense logics axiomatized by strictly positive implication have cut-free Gentzen sequent calculi uniformly. [ABSTRACT FROM AUTHOR]

The paper provides a proof theoretic characterization of the Russellian theory of definite descriptions (RDD) as characterized by Kalish, Montague and Mar (KMM). To this effect three sequent calculi are introduced: LKID0, LKID1 and LKID2. LKID0 is an auxiliary system which is easily shown to be equivalent to KMM. The main research is devoted to LKID1 and LKID2. The former is simpler in the sense of having smaller number of rules and, after small change, satisfies cut elimination but fails to satisfy the subformula property. In LKID2 an additional analysis of different kinds of identities leads to proliferation of rules but yields the subformula property. This refined proof theoretic analysis leading to fully analytic calculus with constructive proof of cut elimination is the main contribution of the paper. [ABSTRACT FROM AUTHOR]

In a recent paper, Negri and Pavlović (Studia Logica 1–35, 2020) have formulated a decidable sequent calculus for the logic of agency, specifically for a deliberative see-to-it-that modality, or dstit. In that paper the adequacy of the system is demonstrated by showing the derivability of the axiomatization of dstit from Belnap et al. (Facing the future: agents and choices in our indeterminist world. Oxford University Press, Oxford, 2001). And while the influence of the latter book on the study of logics of agency cannot be overstated, we note that this is not the only axiomatization of that modality available. In fact, an earlier (and arguably purer) one was offered in Xu (J Philosophical Logic 27(5):505–552, 1998). In this article we fill this lacuna by proving that this alternative axiomatization is likewise readily derivable in the system of Negri and Pavlović (Studia Logica 1–35, 2020). [ABSTRACT FROM AUTHOR]

Williamson argues for the contention that substructural logics are 'ill-suited to acting as background logics for science'. That contention, if true, would be very important, but it is refutable, given what is already known about certain substructural logics. Classical Core Logic is a substructural logic, for it eschews the structural rules of Thinning and Cut and has Reflexivity as its only structural rule. Yet it suffices for classical mathematics, and it furnishes all the proofs and disproofs one needs for the hypothetico-deductive method in science. We explain exactly what Classical Core Logic is, why it is a substructural logic par excellence , and what the basic requirements would be for a logic to be 'suited to acting as [a] background logic for science'. We also explain how Classical Core Logic meets all these requirements. We end by examining Williamson's argument in order to expose where its error lies. [ABSTRACT FROM AUTHOR]

We show that the replacement rule of the sequent calculi ${\bf G3[mic]}^= $ in [8] can be replaced by the simpler rule in which one of the principal formulae is not repeated in the premiss. [ABSTRACT FROM AUTHOR]

We present a sequent calculus with the Henkin constants in the place of the free variables. By disposing of the eigenvariable condition, we obtained a proof system with a strong locality property—the validity of each inference step depends only on its active formulas, not its context. Our major outcomes are: the cut elimination via a non-Gentzen-style algorithm without resorting to regularization and the elimination of Skolem functions with linear increase in the proof length for a subclass of derivations with cuts. [ABSTRACT FROM AUTHOR]

In Schwichtenberg (Studies in logic and the foundations of mathematics, vol 90, Elsevier, pp 867–895, 1977), Schwichtenberg fine-tuned Tait's technique (Tait in The syntax and semantics of infinitary languages, Springer, pp 204–236, 1968) so as to provide a simplified version of Gentzen's original cut-elimination procedure for first-order classical logic (Gallier in Logic for computer science: foundations of automatic theorem proving, Courier Dover Publications, London, 2015). In this note we show that, limited to the case of classical propositional logic, the Tait–Schwichtenberg algorithm allows for a further simplification. The procedure offered here is implemented on Kleene's sequent system G4 (Kleene in Mathematical logic, Wiley, New York, 1967; Smullyan in First-order logic, Courier corporation, London, 1995). The specific formulation of the logical rules for G4 allows us to provide bounds on the height of cut-free proofs just in terms of the logical complexity of their end-sequent. [ABSTRACT FROM AUTHOR]

One proof-theoretic approach to equality in quantificational logic treats equality as a logical connective: in particular, term equality can be given both left and right introduction rules in a sequent calculus proof system. We present a particular example of this approach to equality in a first-order logic setting in which there are no predicate symbols (apart from equality). After we illustrate some interesting applications of this logic, we show that provability in this logic is undecidable. [ABSTRACT FROM AUTHOR]

In this study, new sequent calculi for a minimal quantum logic (MQL) are discussed that involve an implication. The sequent calculus GO for MQL was established by Nishimura, and it is complete with respect to ortho-models (O-models). As GO does not contain implications, this study adopts the strict implication and constructs two new sequent calculi GOI1 and GOI2 as the expansions of GO. Both GOI1 and GOI2 are complete with respect to the O-models. In this study, the completeness and decidability theorems for these new systems are proven. Furthermore, some details pertaining to new rules and the strict implication are discussed. [ABSTRACT FROM AUTHOR]

We investigate a recent proposal for modal hypersequent calculi. The interpretation of relational hypersequents incorporates an accessibility relation along the hypersequent. These systems give the same interpretation of hypersequents as Lellman's linear nested sequents, but were developed independently by Restall for S5 and extended to other normal modal logics by Parisi. The resulting systems obey Došen's principle: the modal rules are the same across different modal logics. Different modal systems only differ in the presence or absence of external structural rules. With the exception of S5, the systems are modular in the sense that different structural rules capture different properties of the accessibility relation. We provide the first direct semantical cut-free completeness proofs for K, T, and D, and show how this method fails in the case of B and S4. [ABSTRACT FROM AUTHOR]

We study various extensions of Gentzen's sequent calculus obtained by adding rules for equality. One of them is singled out as particularly natural and shown to satisfy full cut elimination, namely, also atomic cuts can be eliminated. Furthermore we tell apart the extensions that satisfy full cut elimination from those that do not and establish a strengthened form of the nonlenghtening property of Lifschitz and Orevkov. [ABSTRACT FROM AUTHOR]

Any set of truth-functional connectives has sequent calculus rules that can be generated systematically from the truth tables of the connectives. Such a sequent calculus gives rise to a multi-conclusion natural deduction system and to a version of Parigot's free deduction. The elimination rules are "general," but can be systematically simplified. Cut-elimination and normalization hold. Restriction to a single formula in the succedent yields intuitionistic versions of these systems. The rules also yield generalized lambda calculi providing proof terms for natural deduction proofs as in the Curry–Howard isomorphism. Addition of an indirect proof rule yields classical single-conclusion versions of these systems. Gentzen's standard systems arise as special cases. [ABSTRACT FROM AUTHOR]

Free logics is a family of first-order logics which came about as a result of examining the existence assumptions of classical logic. What those assumptions are varies, but the central ones are that (i) the domain of interpretation is not empty, (ii) every name denotes exactly one object in the domain and (iii) the quantifiers have existential import. Free logics usually reject the claim that names need to denote in (ii), and of the systems considered in this paper, the positive free logic concedes that some atomic formulas containing non-denoting names (namely self-identity) are true, while negative free logic rejects even the latter claim. Inclusive logics, which reject (i), are likewise considered. These logics have complex and varied axiomatizations and semantics, and the goal of this paper is to present an orderly examination of the various systems and their mutual relations. This is done by first offering a formalization, using sequent calculi which possess all the desired structural properties of a good proof system, including admissibility of contraction and cut, while streamlining free logics in a way no other approach has. We then present a simple and unified system of abstract semantics, which allows for a straightforward demonstration of the meta-theoretical properties, and offers insights into the relationship between different logics (free and classical). The final part of this paper is dedicated to extending the system with modalities by using a labeled sequent calculus, and here we are again able to map out the different approaches and their mutual relations using the same framework. [ABSTRACT FROM AUTHOR]

Free logics is a family of first-order logics which came about as a result of examining the existence assumptions of classical logic. What those assumptions are varies, but the central ones are that (i) the domain of interpretation is not empty, (ii) every name denotes exactly one object in the domain and (iii) the quantifiers have existential import. Free logics usually reject the claim that names need to denote in (ii), and of the systems considered in this paper, the positive free logic concedes that some atomic formulas containing non-denoting names (namely self-identity) are true, while negative free logic rejects even the latter claim. Inclusive logics, which reject (i), are likewise considered. These logics have complex and varied axiomatizations and semantics, and the goal of this paper is to present an orderly examination of the various systems and their mutual relations. This is done by first offering a formalization, using sequent calculi which possess all the desired structural properties of a good proof system, including admissibility of contraction and cut, while streamlining free logics in a way no other approach has. We then present a simple and unified system of abstract semantics, which allows for a straightforward demonstration of the meta-theoretical properties, and offers insights into the relationship between different logics (free and classical). The final part of this paper is dedicated to extending the system with modalities by using a labeled sequent calculus, and here we are again able to map out the different approaches and their mutual relations using the same framework. [ABSTRACT FROM AUTHOR]

This note shows that the permutation instructions presented by Zardini (2011) for eliminating cuts on universally quantified formulas in the sequent calculus for the noncontractive theory of truth IKTω are inadequate. To that purpose the note presents a derivation in the sequent calculus for IKTω ending with an application of cut on a universally quantified formula which the permutation instructions cannot deal with. The counterexample is of the kind that leaves open the question whether cut can be shown to be eliminable in the sequent calculus for IKTω with an alternative strategy. [ABSTRACT FROM AUTHOR]

We present an embedding of the Lambek–Grishin calculus into an extension of the nonassociative Lambek calculus with negation. The embedding is based on the De Morgan interpretation of the dual Grishin connectives. [ABSTRACT FROM AUTHOR]

A modified subformula property for the modal logic KD with the additional axiom □ ◊(A ∨ B) ⊃ □ ◊ A ∨ □ ◊B is shown. A new modification of the notion of subformula is proposed for this purpose. This modification forms a natural extension of our former one on which modified subformula property for the modal logics K5, K5D and S4.2 has been shown ([2] and [4]). The finite model property as well as decidability for the logic follows from this. [ABSTRACT FROM AUTHOR]

We upgrade [3] to a complete proof of the conjecture NP = PSPACE that is known as one of the fundamental open problems in the mathematical theory of computational complexity; this proof is based on [2]. Since minimal propositional logic is known to be PSPACE complete, while PSPACE to include NP, it suffices to show that every valid purely implicational formula ρ has a proof whose weight (= total number of symbols) and time complexity of the provability involved are both polynomial in the weight of ρ. As is [3], we use proof theoretic approach. Recall that in [3] we considered any valid ρ in question that had (by the definition of validity) a “short” tree-like proof π in the Hudelmaier-style cutfree sequent calculus for minimal logic. The “shortness” means that the height of π and the total weight of different formulas occurring in it are both polynomial in the weight of ρ. However, the size (= total number of nodes), and hence also the weight, of π could be exponential in that of ρ. To overcome this trouble we embedded π into Prawitz’s proof system of natural deductions containing single formulas, instead of sequents. As in π, the height and the total weight of different formulas of the resulting tree-like natural deduction ∂1 were polynomial, although the size of ∂1 still could be exponential, in the weight of ρ. In our next, crucial move, ∂1 was deterministically compressed into a “small”, although multipremise, dag-like deduction ∂ whose horizontal levels contained only mutually different formulas, which made the whole weight polynomial in that of ρ. However, ∂ required a more complicated verification of the underlying provability of ρ. In this paper we present a nondeterministic compression of ∂ into a desired standard dag-like deduction ∂0 that deterministically proves ρ in time and space polynomial in the weight of ρ.2 Together with [3] this completes the proof of NP = PSPACE. Natural deductions are essential for our proof. Tree-to-dag horizontal compression of π merging equal sequents, instead of formulas, is (possible but) not sufficient, since the total number of different sequents in π might be exponential in the weight of ρ – even assuming that all formulas occurring in sequents are subformulas of ρ. On the other hand, we need Hudelmaier’s cutfree sequent calculus in order to control both the height and total weight of different formulas of the initial tree-like proof π, since standard Prawitz’s normalization although providing natural deductions with the subformula property does not preserve polynomial heights. It is not clear yet if we can omit references to π even in the proof of the weaker result NP = coNP. [ABSTRACT FROM AUTHOR]

This article investigates Charles Peirce's development of logical calculi for classical propositional logic in 1880–1896. Peirce's 1880 work on the algebra of logic resulted in a successful calculus for Boolean algebra. This calculus, denoted by PC, is here presented as a sequent calculus and not as a natural deduction system. It is shown that Peirce's aim was to present PC as a sequent calculus. The law of distributivity, which Peirce states in 1880, is proved using Peirce's Rule, which is a residuation, in PC. The transitional systems of the algebra of the copula that Peirce develops since 1880 paved the way to the 1896 graphical system of the alpha graphs. It is shown how the rules of the alpha system reinterpret Boolean algebras, answering Peirce's statement that logical graphs supply a new system of fundamental assumptions to logical algebra. A proof-theoretic analysis is given for the connection between PC and the alpha system. [ABSTRACT FROM AUTHOR]

We show that if the structural rules are admissible over a set R of atomic rules, then they are admissible in the sequent calculus obtained by adding the rules in R to the multisuccedent minimal and intuitionistic G 3 calculi as well as to the classical one. Two applications to pure logic and to the sequent calculus with equality are presented. [ABSTRACT FROM AUTHOR]

On a bilateralist reading, sequents are interpreted as statements to the effect that, given the assertion of the antecedent it is incoherent to deny the succedent. This interpretation goes against its own ecumenical ambitions, endowing Cut with a meaning very close to that of tertium non datur and thus rendering it intuitionistically unpalatable. This paper explores a top-down route for arguing that, even intuitionistically, a prohibition to deny is as strong as a licence to assert. [ABSTRACT FROM AUTHOR]

We employ some of the machinery developed in previous work to investigate the inferential and memory functions of quantum-like neural networks. We set up a logical apparatus to implement this in the form of a Gentzen sequent calculus which codifies some of the combinatory rules for the state spaces of the neuronal networks introduced earlier. We discuss memory storage in this context and along the way find formal proof that synchronicity promotes binding and storage. These results lead to an algorithmic fragment in calculus that simulates the memory function known as pattern completion. This claim is tested by noting that the failure of certain steps in the algorithm leads to memory deficits essentially identical to those found in such pathologies as Alzheimer's dementia, schizophrenia, and certain forms of autism. Moreover, a specific "power-of-two" wiring architecture and computational logic, which have been postulated and observed across many brain circuits, emerge spontaneously from our model. We draw conclusions concerning the possible nature of such mental processes qua computations. [ABSTRACT FROM AUTHOR]

This article investigates the proof theory of the Quantified Argument Calculus (Quarc) as developed and systematically studied by Hanoch Ben-Yami [3, 4]. Ben-Yami makes use of natural deduction (Suppes-Lemmon style), we, however, have chosen a sequent calculus presentation, which allows for the proofs of a multitude of significant meta-theoretic results with minor modifications to the Gentzen's original framework, i.e., LK. As will be made clear in course of the article LK-Quarc will enjoy cut elimination and its corollaries (including subformula property and thus consistency). [ABSTRACT FROM AUTHOR]

This paper studies the complexity of constant depth propositional proofs in the cedent and sequent calculus. We discuss the relationships between the size of tree-like proofs, the size of dag-like proofs, and the heights of proofs. The main result is to correct a proof construction in an earlier paper about transformations from proofs with polylogarithmic height and constantly many formulas per cedent. [ABSTRACT FROM AUTHOR]

An exact truthmaker for A is a state which, as well as guaranteeing A 's truth, is wholly relevant to it. States with parts irrelevant to whether A is true do not count as exact truthmakers for A. Giving semantics in this way produces a very unusual consequence relation, on which conjunctions do not entail their conjuncts. This feature makes the resulting logic highly unusual. In this paper, we set out formal semantics for exact truthmaking and characterise the resulting notion of entailment, showing that it is compact and decidable. We then investigate the effect of various restrictions on the semantics. We also formulate a sequent-style proof system for exact entailment and give soundness and completeness results. [ABSTRACT FROM AUTHOR]

When studying sequent calculi, proof theorists often have to prove properties about the systems, whether to show that they are "well-behaved", amenable to automated proof search, complete with respect to another system, consistent, among other reasons. These proofs usually involve many very similar cases, which leads to authors rarely writing them in full detail, only pointing to one or two more complicated cases. Moreover, the amount of details makes them more error-prone for humans. Computers, on the other hand, are very good at handling details and repetitiveness. In this work we have formalized textbook proofs of the meta-theory of sequent calculi for linear logic in Abella. Using the infrastructure developed, the proofs can be easily adapted to other substructural logics. We implemented rules as clauses in an intuitive and straightforward way, similar to logic programming, using operations on multisets for the explicit contexts. Although the proofs are quite big, they use only elementary reasoning principles, which makes the proof techniques fairly portable to other formal reasoning systems. [ABSTRACT FROM AUTHOR]

This paper contends that Stoic logic (i.e. Stoic analysis) deserves more attention from contemporary logicians. It sets out how, compared with contemporary propositional calculi, Stoic analysis is closest to methods of backward proof search for Gentzen-inspired substructural sequent logics, as they have been developed in logic programming and structural proof theory, and produces its proof search calculus in tree form. It shows how multiple similarities to Gentzen sequent systems combine with intriguing dissimilarities that may enrich contemporary discussion. Much of Stoic logic appears surprisingly modern: a recursively formulated syntax with some truth-functional propositional operators; analogues to cut rules, axiom schemata and Gentzen's negation-introduction rules; an implicit variable-sharing principle and deliberate rejection of Thinning and avoidance of paradoxes of implication. These latter features mark the system out as a relevance logic, where the absence of duals for its left and right introduction rules puts it in the vicinity of McCall's connexive logic. Methodologically, the choice of meticulously formulated meta-logical rules in lieu of axiom and inference schemata absorbs some structural rules and results in an economical, precise and elegant system that values decidability over completeness. [ABSTRACT FROM AUTHOR]

For a long time, intersection types have been admired for their surprising ability to complete the simply typed lambda calculus. Intersection types are an example of an implicit typing feature which can describe program behavior without manifesting itself within the syntax of a program. Dual to intersections, union types are another implicit typing feature which extends the completeness property of intersection types in the lambda calculus to full-fledged programming languages. However, the formalization of union types can easily break other desirable meta-theoretical properties of the type system. But why should unions be troublesome when their dual, intersections, are not? We look at the issues surrounding the design of type systems for both intersection and union types through the lens of duality by formalizing them within the symmetric language of the classical sequent calculus. In order to formulate type systems which have all of our properties of interest—soundness, completeness, and type safety—we also look at the impact of evaluation strategy on typing. As a result, we present two dual type systems—one for call-by-value and one for call-by-name evaluation—which have all three properties. We also consider the possibility of classical non-deterministic evaluation, for which there is a choice between two different systems depending on which properties are desired: a full type system which is complete, and a simplified type system which is sound and type safe. [ABSTRACT FROM AUTHOR]

We develop multi-conclusion nested sequent calculi for the fifteen logics of the intuitionistic modal cube between IK and IS5. The proof of cut-free completeness for all logics is provided both syntactically via a Maehara-style translation and semantically by constructing an infinite birelational countermodel from a failed proof search. Interestingly, the Maehara-style translation for proving soundness syntactically fails due to the hierarchical structure of nested sequents. Consequently, we only provide the semantic proof of soundness. The countermodel construction used to prove completeness required a completely novel approach to deal with two independent sources of non-termination in the proof search present in the case of transitive and Euclidean logics. [ABSTRACT FROM AUTHOR]

In previous work by Baaz and Iemhoff, a Gentzen calculus for intuitionistic logic with existence predicate is presented that satisfies partial cut elimination and Craig's interpolation property; it is also conjectured that interpolation fails for the implication-free fragment. In this paper an equivalent calculus is introduced that satisfies full cut elimination and allows a direct proof of interpolation via Maehara's lemma. In this way, it is possible to obtain much simpler interpolants and to better understand and (partly) overcome the failure of interpolation for the implication-free fragment. [ABSTRACT FROM AUTHOR]

The goal of this paper is to propose correspondence analysis as a technique for generating the so-called erotetic (i.e. pertaining to the logic of questions) calculi which constitute the method of Socratic proofs by Andrzej Wisniewski. As we explain in the paper, in order to successfully design an erotetic calculus one needs invertible sequent-calculus-style rules. For this reason, the proposed correspondence analysis resulting in invertible rules can constitute a new foundation for the method of Socratic proofs. Correspondence analysis is Kooi and Tamminga's technique for designing proof systems. In this paper it is used to consider sequent calculi with non-branching (the only exception being the rule of cut), invertible rules for the negation fragment of classical propositional logic and its extensions by binary Boolean functions. [ABSTRACT FROM AUTHOR]

Dependent types are a key feature of the proof assistants based on the Curry-Howard isomorphism. It is well known that this correspondence can be extended to classical logic by enriching the language of proofs with control operators. However, they are known to misbehave in the presence of dependent types, unless dependencies are restricted to values. Moreover, while sequent calculi naturally support continuation-passing-style interpretations, there is no such presentation of a language with dependent types. The main achievement of this article is to give a sequent calculus presentation of a call-by-value language with a control operator and dependent types, and to justify its soundness through a continuation-passing-style translation. We start from the call-by-value version of the λμ˜μ-calculus. We design a minimal language with a value restriction and a type system that includes a list of explicit dependencies to maintain type safety. We then show how to relax the value restriction and introduce delimited continuations to directly prove the consistency by means of a continuation-passing-style translation. Finally, we relate our calculus to a similar system by Lepigre and present a methodology to transfer properties from this system to our own. [ABSTRACT FROM AUTHOR]

In 1952, S.C. Kleene introduced a Gentzen-type system G3 which is designed to be suitable for showing that the given sequents (and consequently the corresponding formulae) are unprovable in the intuitionistic logic. We show that some classes of predicate formulae are unprovable in the intuitionistic predicate calculus, using the system G3 and some properties of sequents that remain invariant throughout derivations in this system. The unprovability of certain formulae obtained by Kleene follows from our results as a corollary. [ABSTRACT FROM AUTHOR]

In this paper, I motivate a cut free sequent calculus for classical logic with first order quantification, allowing for singular terms free of existential import. Along the way, I motivate a criterion for rules designed to answer Prior's question about what distinguishes rules for logical concepts, like conjunction from apparently similar rules for putative concepts like Prior's tonk , and I show that the rules for the quantifiers—and the existence predicate—satisfy that condition. [ABSTRACT FROM AUTHOR]

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 K. New is the result that KD has uniform interpolation. The results imply that for modal logics K4 and S4, which are known not to have uniform interpolation, certain sequent calculi cannot exist. [ABSTRACT FROM AUTHOR]

Gentzen's approach to deductive systems, and Carnap's and Popper's treatment of probability in logic were two fruitful ideas that appeared in logic of the mid-twentieth century. By combining these two concepts, the notion of sentence probability, and the deduction relation formalized in the sequent calculus, we introduce the notion of 'probabilized sequent' Γ⊢abΔ with the intended meaning that "the probability of truthfulness of Γ⊢Δ belongs to the interval [a, b]". This method makes it possible to define a system of derivations based on 'axioms' of the form Γi⊢aibiΔi, obtained as a result of empirical research, and then infer conclusions of the form Γ⊢abΔ. We discuss the consistency, define the models, and prove the soundness and completeness for the defined probabilized sequent calculus. [ABSTRACT FROM AUTHOR]

The modal logic S4.2 is S4 with the additional axiom ◇□A ⊃ □◇A. In this article, the sequent calculus GS4.2 for this logic is presented, and by imposing an appropriate restriction on the application of the cut-rule, it is shown that, every GS4.2-provable sequent S has a GS4.2-proof such that every formula occurring in it is either a subformula of some formula in S, or the formula □¬□B or ¬□B, where □B occurs in the scope of some occurrence of □ in some formula of S. These are just the K5-subformulas of some formula in S which were introduced by us to show the modified subformula property for the modal logics K5 and K5D (Bull Sect Logic 30: 115{122, 2001). Some corollaries including the interpolation property for S4.2 follow from this. By slightly modifying the proof, the finite model property also follows. [ABSTRACT FROM AUTHOR]

Kooi and Tamminga's correspondence analysis is a technique for designing proof systems, mostly, natural deduction and sequent systems. In this paper it is used to generate sequent calculi with invertible rules, whose only branching rule is the rule of cut. The calculi pertain to classical propositional logic and any of its fragments that may be obtained from adding a set (sets) of rules characterizing a two-argument Boolean function(s) to the negation fragment of classical propositional logic. The properties of soundness and completeness of the calculi are demonstrated. The proof of completeness is conducted by Kalmár's method. Most of the presented sequent-calculus rules have been obtained automatically, by a rule-generating algorithm implemented in Python. Correctness of the algorithm is demonstrated. This automated approach allowed us to analyse thousands of possible rules' schemes, hundreds of rules corresponding to Boolean functions, and to find dozens of those invertible. Interestingly, the analysis revealed that the presented proof-theoretic framework provides a syntactic characteristics of such an important semantic property as functional completeness. [ABSTRACT FROM AUTHOR]

The logic of Conditional Beliefs (CDL) has been introduced by Board, Baltag, and Smets to reason about knowledge and revisable beliefs in a multi-agent setting. In this article both the semantics and the proof theory for this logic are studied. First, a natural semantics for CDL is defined in terms of neighbourhood models, a multi-agent generalisation of Lewis' spheres models, and it is shown that the axiomatization of CDL is sound and complete with respect to this semantics. Second, it is shown that the neighbourhood semantics is equivalent to the original one defined in terms of plausibility models, by means of a direct correspondence between the two types of models. On the basis of neighbourhood semantics, a labelled sequent calculus for CDL is obtained. The calculus has strong proof-theoretic properties, in particular admissibility of contraction and cut, and it provides a decision procedure for the logic. Furthermore, its semantic completeness is used to obtain a constructive proof of the finite model property of the logic. Finally, it is shown that other doxastic operators can be easily captured within neighbourhood semantics. This fact provides further evidence of the naturalness of neighbourhood semantics for the analysis of epistemic/doxastic notions. [ABSTRACT FROM AUTHOR]

Abstract Proof-theoretic method has been successfully used almost from the inception of interpolation properties to provide efficient constructive proofs thereof. Until recently, the method was limited to sequent calculi (and their notational variants), despite the richness of generalizations of sequent structures developed in structural proof theory in the meantime. In this paper, we provide a systematic and uniform account of the recent extension of this proof-theoretic method to hypersequents, nested sequents, and labelled sequents for normal modal logic. The method is presented in terms and notation easily adaptable to other similar formalisms, and interpolant transformations are stated for typical rule types rather than for individual rules. [ABSTRACT FROM AUTHOR]

In this study, some conservative extensions of paraconsistent quantum logic, such as Nelsonian, modal, infinitary and temporal, are investigated by extending a single‐antecedent/succedent sequent calculus PQL for paraconsistent quantum logic. A sequent calculus NQL, which is obtained from PQL by adding implication and co‐implication, is introduced as a variant of Nelson's paraconsistent four‐valued logic. Sequent calculi MPQL, IPQL and TPQL are introduced, respectively, as modal, infinitary and temporal extensions of PQL. The cut‐elimination and duality theorems for these calculi are proved, and some extended calculi including NQL and MPQL, as well as their fragments, are shown to be decidable. A theorem for embedding NQL into its negation‐free fragment and a theorem for embedding TPQL into IPQL are proved. [ABSTRACT FROM AUTHOR]

In several applications of sequent calculi going beyond pure logic, an introduction of suitably defined rules seems to be more profitable than addition of extra axiomatic sequents. A program of formalization of mathematical theories via rules of special sort was developed successfully by Negri and von Plato. In this paper a general theorem on possible ways of transforming axiomatic sequents into rules in sequent calculi is proved. We discuss its possible applications and provide some case studies for illustration. [ABSTRACT FROM AUTHOR]