Sara Negri

A unified Gentzen-style proof-theoretic framework for until-free propositional linear-time temporal logic and its intuitionistic variant is introduced. The framework unifies Gentzen-style single-succedent sequent calculi and natural deduction systems for both the classical and intuitionistic versions of these temporal logics. Theorems establishing the equivalence between the proposed sequent calculi and natural deduction systems are proved. Furthermore, the cut-elimination theorems for the proposed sequent calculi and the normalization theorems for the proposed natural deduction systems are established.

This study introduces Gentzen-style natural deduction systems for Gurevich logic, Nelson logic, intuitionistic logic, classical logic, and modal logic. Gurevich logic is an extended constructive three-valued logic obtained from intuitionistic logic by adding strong negation, and Nelson logic is the intuitionistic-negation-less fragment of Gurevich logic. The proposed natural deduction systems are constructed in a modular manner based on primitive rules for negation, that is, rules of explosion, of negation introduction, and of excluded middle. Theorems for equivalence between these natural deduction systems and the corresponding previously proposed cut-free Gentzen-style sequent calculi are proved. Moreover, normalization theorems for the proposed natural deduction systems are proved.

First, G0-style sequent calculi for extended Belnap–Dunn and intuitionistic logics, including Nelson and Gurevich logics, are introduced. A theorem establishing the equivalence between G0- and G3-style sequent calculi for these logics is then presented, and the cut-elimination theorem for these G0-style calculi is obtained as a result. Next, natural deduction systems with general elimination rules are introduced for these logics, and a full normalization theorem for these natural deduction systems is proved. This proof is achieved using bi-directional translations between the proposed G0-style sequent calculi and the natural deduction systems with general elimination rules.

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.

Ever since antiquity, attempts have been made at defining knowledge through belief augmented by additional properties such as truth and justification. These characterizations have been challenged by Gettier counterexamples and their variants. A modern proposal, what is known as defeasibility theory, characterizes knowledge through stability under revision of beliefs on the basis of true or arbitrary information. A formal investigation of such a proposal calls for the methods of dynamic epistemic logic: well developed semantic approaches to dynamic epistemic logic have been given through the plausibility models, but a corresponding proof theory is still in its infancy. We shall recast plausibility models in terms of more general neighbourhood models and develop on their basis complete proof systems. An inferential treatment of epistemic and doxastic notions such as safe belief will give a new way to study their relationships; among these, the characterization of knowledge as belief stable under arbitrary revision will be grounded through formal labelled sequent calculus derivations.

Anti-realist epistemic conceptions of truth imply what is called the knowability principle: All truths are possibly known. The principle can be formalized in a bimodal propositional logic, with an alethic modality ${\diamondsuit}$ and an epistemic modality ${\mathcal{K}}$, by the axiom scheme ${A \supset \diamondsuit \mathcal{K} A}$. The use of classical logic and minimal assumptions about the two modalities lead to the paradoxical conclusion that all truths are known, ${A \supset \mathcal{K} A}$. A Gentzen-style reconstruction of the Church–Fitch paradox is presented following a labelled approach to sequent calculi. First, a cut-free system for classical bimodal logic is introduced as the logical basis for the Church–Fitch paradox and the relationships between ${\mathcal {K}}$ and ${\diamondsuit}$ are taken into account. Afterwards, by exploiting the structural properties of the system, in particular cut elimination, the semantic frame conditions that correspond to KP are determined and added in the form of a block of nonlogical inference rules. Within this new system for classical and intuitionistic “knowability logic”, it is possible to give a satisfactory cut-free reconstruction of the Church–Fitch derivation and to confirm that OP is only classically derivable, but neither intuitionistically derivable nor intuitionistically admissible. Finally, it is shown that in classical knowability logic, the Church–Fitch derivation is nothing else but a fallacy and does not represent a real threat for anti-realism.

In a fragment entitled Elementa Nova Matheseos Universalis Leibniz writes “the mathesis [...] shall deliver the method through which things that are conceivable can be exactly determined”; in another fragment he takes the mathesis to be “the science of all things that are conceivable.” Leibniz considers all mathematical disciplines as branches of the mathesis and conceives the mathesis as a general science of forms applicable not only to magnitudes but to every object that exists in our imagination, i.e. that is possible at least in principle. As a general science of forms the mathesis investigates possible relations between “arbitrary objects”. It is an abstract theory of combinations and relations among objects whatsoever. In 1810 the mathematician and philosopher Bernard Bolzano published a booklet entitled Contributions to a Better-Grounded Presentation of Mathematics. There is, according to him, a certain objective connection among the truths that are germane to a certain homogeneous field of objects: some truths are the “reasons” of others, and the latter are “consequences” of the former. The reason-consequence relation seems to be the counterpart of causality at the level of a relation between true propositions. Arigorous proof is characterized in this context as a proof that shows the reason of the proposition that is to be proven. Requirements imposed on rigorous proofs seem to anticipate normalization results in current proof theory. The contributors of Mathesis Universalis, Computability and Proof, leading experts in the fields of computer science, mathematics, logic and philosophy, show the evolution of these and related ideas exploring topics in proof theory, computability theory, intuitionistic logic, constructivism and reverse mathematics, delving deeply into a contextual examination of the relationship between mathematical rigor and demands for simplification.

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.

A proof-theoretical analysis of elementary theories of order relations is effected through the formulation of order axioms as mathematical rules added to contraction-free sequent calculus. Among the results obtained are proof-theoretical formulations of conservativity theorems corresponding to Szpilrajn’s theorem on the extension of a partial order into a linear one. Decidability of the theories of partial and linear order for quantifier-free sequents is shown by giving terminating methods of proof-search.

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

A proof-theoretical treatment of collectively accepted group beliefs is presented through a multi-agent sequent system for an axiomatization of the logic of acceptance. The system is based on a labelled sequent calculus for propositional multi-agent epistemic logic with labels that correspond to possible worlds and a notation for internalized accessibility relations between worlds. The system is contraction- and cut-free. Extensions of the basic system are considered, in particular with rules that allow the possibility of operative members or legislators. Completeness with respect to the underlying Kripke semantics follows from a general direct and uniform argument for labelled sequent calculi extended with mathematical rules for frame properties. As an example of the use of the calculus we present an analysis of the discursive dilemma.

Various sources in the literature claim that the deduction theorem does not hold for normal modal or epistemic logic, whereas others present versions of the deduction theorem for several normal modal systems. It is shown here that the apparent problem arises from an objectionable notion of derivability from assumptions in an axiomatic system. When a traditional Hilbert-type system of axiomatic logic is generalized into a system for derivations from assumptions, the necessitation rule has to be modified in a way that restricts its use to cases in which the premiss does not depend on assumptions. This restriction is entirely analogous to the restriction of the rule of universal generalization of first-order logic. A necessitation rule with this restriction permits a proof of the deduction theorem in its usual formulation. Other suggestions presented in the literature to deal with the problem are reviewed, and the present solution is argued to be preferable to the other alternatives. A contraction-and cut-free sequent calculus equivalent to the Hubert system for basic modal logic shows the standard failure argument untenable by proving the underivability of DA from A

The contraction-free sequent calculus G4 for intuitionistic logic is extended by rules following a general rule-scheme for nonlogical axioms. Admissibility of structural rules for these extensions is proved in a direct way by induction on derivations. This method permits the representation of various applied logics as complete, contraction- and cut-free sequent calculus systems with some restrictions on the nature of the derivations. As specific examples, intuitionistic theories of apartness and order are treated.

A constructivisation of the cut-elimination proof for sequent calculi for classical, intuitionistic and minimal infinitary logics with geometric rules—given in earlier work by the second author—is presented. This is achieved through a procedure where the non-constructive transfinite induction on the commutative sum of ordinals is replaced by two instances of Brouwer’s Bar Induction. The proof of admissibility of the structural rules is made ordinal-free by introducing a new well-founded relation based on a notion of embeddability of derivations. Additionally, conservativity for classical over intuitionistic/minimal logic for the seven (finitary) Glivenko sequent classes is here shown to hold also for the corresponding infinitary classes.

Large portions of mathematics such as algebra and geometry can be formalized using first-order axiomatizations. In many cases it is even possible to use a very well-behaved class of first-order axioms, namely, what are called coherent or geometric implications. Such class of axioms can be translated to inference rules that can be added to a sequent calculus while preserving its structural properties. In this work, this fundamental result is extended to their infinitary generalizations as extensions of sequent calculi for both classical and intuitionistic infinitary logic. As an application, a simple proof of the infinitary Barr’s theorem without the axioms of choice is shown.

This paper provides a proof-theoretic study of quantified non-normal modal logics. It introduces labelled sequent calculi based on neighbourhood semantics for the first-order extension, with both varying and constant domains, of monotone NNML, and studies the role of the Barcan formulas in these calculi. It will be shown that the calculi introduced have good structural properties: invertibility of the rules, height-preserving admissibility of weakening and contraction and syntactic cut elimination. It will also be shown that each of the calculi introduced is sound and complete with respect to the appropriate class of neighbourhood frames. In particular, the completeness proof constructs a formal derivation for derivable sequents and a countermodel for non-derivable ones, and gives a semantic proof of the admissibility of cut.

The logic of Conditional Beliefs 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 forCDLis defined in terms of neighbourhood models, a multi-agent generalisation of Lewis’ spheres models, and it is shown that the axiomatization ofCDLis 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 forCDLis 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.

Stone representation theorems are a central ingredient in the metatheory of philosophical logics and are used to establish modal embedding results in a general but indirect and non-constructive way. Their use in logical embeddings will be reviewed and it will be shown how they can be circumvented in favour of direct and constructive arguments through the methods of analytic proof theory, and how the intensional part of the representation results can be recovered from the syntactic proof of those embeddings. Analytic methods will also be used to establish the embedding of subintuitionistic logics into the corresponding modal logics. Finally, proof-theoretic embeddings will be interpreted as a reduction of classes of word problems.