The classical satisfiability problem (SAT) is used as a natural and general tool to express and solve combinatorial problems that are in NP. We postulate that provability for implicational intuitionistic propositional logic (IIPC) can serve as a similar natural tool to express problems in Pspace. We demonstrate it by proving two essential results concerning the system. One is a natural reduction from full IPC (with all connectives) to implicational formulas of order three. Another result is a convenient interpretation in terms (...) of simple alternating automata. Additionally, we distinguish some natural subclasses of IIPC corresponding to the complexity classes NP and co-NP. (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).

We formulate Hilbert’s epsilon calculus in the context of expansion proofs. This leads to a simplified proof of the epsilon theorems by disposing of the need for prenexification, Skolemisation, and their respective inverse transformations. We observe that the natural notion of cut in the epsilon calculus is associative.

The meaning of a formula built out of proof-functional connectives depends in an essential way upon the intensional aspect of the proofs of the component subformulas. We study three such connectives, strong equivalence (where the two directions of the equivalence are established by mutually inverse maps), strong conjunction (where the two components of the conjunction are established by the same proof) and relevant implication (where the implication is established by an identity map). For each of these connectives we give a (...) type assignment system, a realizability semantics, and a completeness theorem. This form of completeness implies the semantic completeness of the type assignment system. (shrink)

A terminating sequent calculus for intuitionistic propositional logic is obtained by modifying the R $\supset $ rule of the labelled sequent calculus $\mathbf {G3I}$. This is done by adding a variant of the principle of a fortiori in the left-hand side of the premiss of the rule. In the resulting calculus, called ${\mathbf {G3I}}_{\mathbf {t}}$, derivability of any given sequent is directly decidable by root-first proof search, without any extra device such as loop-checking. In the negative case, the failed proof (...) search gives a finite countermodel to the sequent on a reflexive, transitive, and Noetherian Kripke frame. As a byproduct, a direct proof of faithfulness of the embedding of intuitionistic logic into Grzegorcyk logic is obtained. (shrink)

We present a sequent calculus for the Grzegorczyk modal logic$\mathsf {Grz}$allowing cyclic and other non-well-founded proofs and obtain the cut-elimination theorem for it by constructing a continuous cut-elimination mapping acting on these proofs. As an application, we establish the Lyndon interpolation property for the logic$\mathsf {Grz}$proof-theoretically.

In his earlyContributions to a Better-Grounded Presentation of Mathematics Bernard Bolzano tries to characterizerigorous proofs.Rigorousis,prima facie, any proof that indicates the grounds for its conclusion. Bolzano lists a number of methodological constraints all rigorous proofs should comply with, and tests them systematically against a specific collection of elementary inference schemata that, according to him, are evidently of ground-consequence-kind. This paper intends to give a detailed and critical account of the fragmentary logic of theContributions, and to point out as well some (...) difficulties Bolzano’s attempt runs into, notably as to his methodological ban on ‘kind crossing’. (shrink)

An original family of labelled sequent calculi $\mathsf {G3IL}^{\star }$ for classical interpretability logics is presented, modularly designed on the basis of Verbrugge semantics (a.k.a. generalised Veltman semantics) for those logics. We prove that each of our calculi enjoys excellent structural properties, namely, admissibility of weakening, contraction and, more relevantly, cut. A complexity measure of the cut is defined by extending the notion of range previously introduced by Negri w.r.t. a labelled sequent calculus for Gödel–Löb provability logic, and a cut-elimination (...) algorithm is discussed in detail. To our knowledge, this is the most extensive and structurally well-behaving class of analytic proof systems for modal logics of interpretability currently available in the literature. (shrink)

We present systems of Natural Deduction based on Strict Implication for the main normal modal logics between K and S5. In this work we consider Strict Implication as the main modal operator, and establish a natural correspondence between Strict Implication and strict subproofs.

Originating from work in operations research the cutting plane refutation systemCP is an extension of resolution, where unsatisfiable propositional logic formulas in conjunctive normal form are recognized by showing the non-existence of boolean solutions to associated families of linear inequalities. Polynomial sizeCP proofs are given for the undirecteds-t connectivity principle. The subsystemsCP q ofCP, forq≥2, are shown to be polynomially equivalent toCP, thus answering problem 19 from the list of open problems of [8]. We present a normal form theorem forCP (...) 2-proofs and thereby for arbitraryCP-proofs. As a corollary, we show that the coefficients and constant terms in arbitrary cutting plane proofs may be exponentially bounded by the number of steps in the proof, at the cost of an at most polynomial increase in the number of steps in the proof. The extensionCPLE +, introduced in [9] and there shown top-simulate Frege systems, is proved to be polynomially equivalent to Frege systems. Lastly, since linear inequalities are related to threshold gates, we introduce a new threshold logic and prove a completeness theorem. (shrink)

Logic is traditionally considered to be a purely syntactic discipline, at least in principle. However, prof. David Isles has shown that this ideal is not yet met in traditional logic. Semantic residue is present in the assumption that the domain of a variable should be fixed in advance of a derivation, and also in the notion that a numerical notation must refer to a number rather than be considered a mathematical object in and of itself. Based on his work, the (...) central question of this thesis is what kind of logic, if any, results from removing this semantic residue from traditional logic.We differ from traditional logic in two significant ways. The first is that the assumption that a numerical notation must refer to a number is denied. Numerical notations are considered as mathematical objects in their own right, related to each other by means of rewrite rules. The traditional notion of reference is then replaced by the notion of reduction (by means of the rewrite rules) to a normal form. Two numerical notations that reduce to the same normal form would traditionally be considered identical, as they would refer to the same number, and hence they would be interchangeable salva veritate. In the new system, called Buridan-Volpin (BV), the numerical notations themselves are the elements of the domains of variables, and two numerical notations that reduce to the same normal form need not be interchangeable salva veritate, except when they are syntactically identical (i.e., have the same Gödel number).The second is that we do away with the assumption that the domains of variables need to be fixed in advance of a derivation. Instead we focus on what is needed to guarantee preservation of truth in every step of a derivation. These conditions on the domains of the variables, accumulated in the course of a derivation, are combined in a reference grammar. Whereas traditionally a derivation is considered valid when the conclusion follows from the premisses by way of the derivation rules (and possibly axioms), in the BV system a derivation must meet the extra condition that no inconsistency occurs within the reference grammar. For if the reference grammar were to give rise to inconsistency (i.e., it would be impossible to assign domains to all the variables without breaking at least one of the conditions placed on them in the reference grammar), there is no longer a guarantee that truth has been preserved in every step of the derivation, and hence the truth of the conclusion is not guaranteed by the derivation.In Chapter 2 the BV system is introduced in some formal detail. Chapter 3 gives some examples of derivations, notably totality of addition, multiplication and exponentiation, as well as a lemma needed for the proof of Euclid’s Theorem. These examples, taken from prof. Isles’ First-Order Reasoning and Primitive Recursive Natural Number Notations, show that there is a real proof-theoretical difference between traditional logic and the BV system. Here we also find the first major point of departure between myself and prof. Isles, centered on the notion of inheritance of conditions in the reference grammar by way of lemmata. These different points of view are best illustrated in the sections on the totality of exponentiation and on Euclid’s Lemma: prof. Isles maintains that the proof of totality of exponentiation is not BV valid, while I maintain that it is. But I do agree with him that the traditional proof of Euclid’s Lemma is not BV valid. Chapter 6 also expands the arguments for my choice in this matter.Now that it has been shown that there is a difference between traditional logic and BV, the properties of BV need to be examined. In Chapter 4 we give a proof of Cut-elimination for BV minus induction and the subformula property for BV, which allows us to prove the consistency of BV minus induction. We also expand on the reasons for excluding induction. In Chapter 5 we consider in detail the proof of a finite analog to the Löwenheim–Skolem theorem given by prof. Isles in his article with the same title. He proves that under certain conditions it is always possible, given the existence of a (possibly uncountable) model for a derivation, to give a finite model for this derivation. The system he considers deviates from BV as considered in this thesis in two significant ways: it does not contain the induction rule and the domains contain numbers instead of numerical notations. We then go on to show that it is possible to extend the result to include induction, in the sense that the existence of a possibly uncountable model for a derivation guarantees the existence of a model that is at most countable. We also consider the complications that arise from taking numerical expressions instead of numbers as the elements of domains.Finally, in Chapter 6 we consider the philosophical consequences of the BV system, informed by the formal results from the previous chapters. In particular we discuss the relation between reduction and reference, the status of reference grammars, the notion of induction and its function within BV, and some brief considerations on the consequences of the BV system for the discussion regarding nominalism and realism with regard to mathematical objects. The object of the chapter is twofold. On the one hand applying the formal results to philosophical questions, on the other hand arguing that BV is not just a theoretically acceptable alternative to traditional logic, but is in fact deserving of further development and research into its properties. The latter will probably appeal most to those of a nominalist and/or finitist bent.Abstract prepared by Harrie de Swart and Sven Storms.E-mail:[email protected]:https://research.tilburguniversity.edu/files/6170 1294/Storms_The_Buridan_Volpin_04_05_2022.pdf. (shrink)

This paper presents a sequent calculus for Inquisitive Propositional Logic obtained by expanding the sequent calculus g3ip for intuitionistic propositional logic with suitable rules for double negation elimination for atoms and the Split Property. A suitable rule for the Split Property is obtained by taking advantage of the connection between the truth-conditional fragment in Inquisitive Logic and Harrop formulas. The paper proves admissibility of cut for the sequent calculus and uses the sequent calculus to prove interpolation for Inquisitive Propositional Logic. (...) Interpolation is obtained using Maehara’s lemma. (shrink)

Natural Formalization proposes a concrete way of expanding proof theory from the meta-mathematical investigation of formal theories to an examination of “the concept of the specifically mathematical proof.” Formal proofs play a role for this examination in as much as they reflect the essential structure and systematic construction of mathematical proofs. We emphasize three crucial features of our formal inference mechanism: (1) the underlying logical calculus is built for reasoning with gaps and for providing strategic directions, (2) the mathematical frame (...) is a definitional extension of Zermelo–Fraenkel set theory and has a hierarchically organized structure of concepts and operations, and (3) the construction of formal proofs is deeply connected to the frame through rules for definitions and lemmas. To bring these general ideas to life, we examine, as a case study, proofs of the Cantor–Bernstein Theorem that do not appeal to the principle of choice. A thorough analysis of the multitude of “different” informal proofs seems to reduce them to exactly one. The natural formalization confirms that there is one proof, but that it comes in two variants due to Dedekind and Zermelo, respectively. In this way it enhances the conceptual understanding of the represented informal proofs. The formal, computational work is carried out with the proof search system AProS that serves as a proof assistant and implements the above inference mechanism; it can be fully inspected at (see link below). (shrink)

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. (shrink)

We show that Spector's “restricted” form of bar recursion is sufficient (over system T) to define Spector's search functional. This new result is then used to show that Spector's restricted form of bar recursion is in fact as general as the supposedly more general form of bar recursion. Given that these two forms of bar recursion correspond to the (explicitly controlled) iterated products of selection function and quantifiers, it follows that this iterated product of selection functions is T‐equivalent to the (...) corresponding iterated product of quantifiers. (shrink)

Isomorphism between formulae is defined with respect to categories formalizing equality of deductions in classical propositional logic and in the multiplicative fragment of classical linear propositional logic caught by proof nets. This equality is motivated by generality of deductions. Characterizations are given for pairs of isomorphic formulae, which lead to decision procedures for this isomorphism.

The class of all $\ast $ -continuous Kleene algebras, whose description includes an infinitary condition on the iteration operator, plays an important role in computer science. The complexity of reasoning in such algebras—ranging from the equational theory to the Horn one, with restricted fragments of the latter in between—was analyzed by Kozen (2002). This paper deals with similar problems for $\ast $ -continuous residuated Kleene lattices, also called $\ast $ -continuous action lattices, where the product operation is augmented by residuals. (...) We prove that, in the presence of residuals, the fragment of the corresponding Horn theory with $\ast $ -free hypotheses has the same complexity as the $\omega ^\omega $ iteration of the halting problem, and hence is properly hyperarithmetical. We also prove that if only commutativity conditions are allowed as hypotheses, then the complexity drops down to $\Pi ^0_1$ (i.e., the complement of the halting problem), which is the same as that for $\ast $ -continuous Kleene algebras. In fact, we get stronger upper bound results: the fragments under consideration are translated into suitable fragments of infinitary action logic with exponentiation, and our upper bounds are obtained for the latter ones. (shrink)

We present a proof system for a multimode and multimodal logic, which is based on our previous work on modal Martin-Löf type theory. The specification of modes, modalities, and implications between them is given as a mode theory, i.e., a small 2-category. The logic is extended to a lambda calculus, establishing a Curry–Howard correspondence.