Cut-free completeness for modular hypersequent calculi for modal logics K, T, and D

Forthcoming in The Review of Symbolic Logic.

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.

DOI:10.1017/S1755020320000180

Download preprint

rhsmlt

Cut elimination and normalization for generalized single and multi-conclusion sequent and natural deduction calculi

Forthcoming in The Review of Symbolic Logic.

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.

DOI: 10.1017/S1755020320000015

Download preprint

gencalcs

The significance of the Curry-Howard isomorphism

In Gabriele M. Mras, Paul Weingartner & Bernhard Ritter (eds.), Philosophy of Logic and Mathematics. Proceedings of the 41st International Ludwig Wittgenstein Symposium. Berlin: De Gruyter. pp. 313-326 (2019)

The Curry-Howard isomorphism is a proof-theoretic result that establishes a connection between derivations in natural deduction and terms in typed lambda calculus. It is an important proof-theoretic result, but also underlies the development of type systems for programming languages. This fact suggests a potential importance of the result for a philosophy of code.

DOI 10.1515/9783110657883-018

Embargoed until November 2020. Please email for offprint.

Book cover

Sets, Logic, Computation. An Open Introduction to Metalogic

Sets, Logic, Computation is an introductory textbook on metalogic. It covers naive set theory, first-order logic, sequent calculus and natural deduction, the completeness, compactness, and Löwenheim-Skolem theorems, Turing machines, and the undecidability of the halting problem and of first-order logic. The audience is undergraduate students with some background in formal logic, e.g., what is covered by forall x.

LINK

Book cover

forall x: Calgary. An Introduction to Formal Logic

forall x: Calgary is a full-featured textbook on formal logic. It covers key notions of logic such as consequence and validity of arguments, the syntax of truth-functional propositional logic TFL and truth-table semantics, the syntax of first-order (predicate) logic FOL with identity (first-order interpretations), translating (formalizing) English in TFL and FOL, and Fitch-style natural deduction proof systems for both TFL and FOL. It also deals with some advanced topics such as truth-functional completeness. Exercises with solutions are available. It is provided in PDF (for screen reading, printing, and a special version for dyslexics) and in LaTeX source code.

LINK

Rumfitt on truth-grounds, negation, and vagueness

Philosophical Studies 175 (2018) 2079–2089

In The Boundary Stones of Thought (2015), Rumfitt defends classical logic against challenges from intuitionistic mathematics and vagueness, using a semantics of pre-topologies on possibilities, and a topological semantics on predicates, respectively. These semantics are suggestive but the characterizations of negation face difficulties that may undermine their usefulness in Rumfitt’s project.

DOI: 10.1007/s11098-018-1114-7

Preprint

Semantics and Proof Theory of the Epsilon Calculus

In Logic and Its Applications. ICLA 2017, edited by Sujata Ghosh and Sanjiva Prasad, 27–47. LNCS 10119. Berlin, Heidelberg: Springer.

The epsilon operator is a term-forming operator which replaces quantifiers in ordinary predicate logic. The application of this undervalued formalism has been hampered by the absence of well-behaved proof systems on the one hand, and accessible presentations of its theory on the other. One significant early result for the original axiomatic proof system for the 𝜀-calculus is the first epsilon theorem, for which a proof is sketched. The system itself is discussed, also relative to possible semantic interpretations. The problems facing the development of proof-theoretically well-behaved systems are outlined.

DOI 10.1007/978-3-662-54069-5_4
Preprint

Natural Deduction for the Sheffer Stroke and Peirce’s Arrow (And Any Other Truth-Functional Connective)

Richard Zach, “Natural Deduction for the Sheffer Stroke and Peirce’s Arrow (and any Other Truth-Functional Connective),” Journal of Philosophical Logic 45(2) (2016), pp. 183–197.

Methods available for the axiomatization of arbitrary finite-valued logics can be applied to obtain sound and complete intelim rules for all truth-functional connectives of classical logic including the Sheffer stroke (NAND) and Peirce’s arrow (NOR). The restriction to a single conclusion in standard systems of natural deduction requires the introduction of additional rules to make the resulting systems complete; these rules are nevertheless still simple and correspond straightforwardly to the classical absurdity rule. Omitting these rules results in systems for intuitionistic versions of the connectives in question.

DOI: 10.1007/s10992-015-9370-x

Preprint on arXiv (with errata)

Carnap’s Early Metatheory: Scope and Limits

Georg Schiemer, Richard Zach, and Erich Reck. 2017. “Carnap’s Early Metatheory: Scope and Limits,” Synthese 194(1), 33–65

In his Untersuchungen zur allgemeinen Axiomatik (1928) and Abriss der Logistik (1929), Rudolf Carnap attempted to formulate the metatheory of axiomatic theories within a single, fully interpreted type-theoretic framework and to investigate a number of meta-logical notions in it, such as those of model, consequence, consistency, completeness, and decidability. These attempts were largely unsuccessful, also in his own considered judgment. A detailed assessment of Carnap’s attempt shows, nevertheless, that his approach is much less confused and hopeless than it has often been made out to be. By providing such a reassessment, the paper contributes to a reevaluation of Carnap’s contributions to the development of modern logic.

DOI: 10.1007/s11229-015-0877-z

Preprint on arXiv

Heinrich Behmann’s 1921 lecture on the decision problem and the algebra of logic

Paolo Mancosu and Richard Zach. “Heinrich Behmann’s 1921 lecture on the decision problem and the algebra of logic,” Bulletin of Symbolic Logic 21 (2015), 164–187

Heinrich Behmann (1891–1970) obtained his Habilitation under David Hilbert in Göttingen in 1921 with a thesis on the decision problem. In his thesis, he solved—independently of Löwenheim and Skolem’s earlier work—the decision problem for monadic second-order logic in a framework that combined elements of the algebra of logic and the newer axiomatic approach to logic then being developed in Göttingen. In a talk given in 1921, he outlined this solution, but also presented important programmatic remarks on the significance of the decision problem and of decision procedures more generally. The text of this talk as well as a partial English translation are included.

DOI: 10.1017/bsl.2015.10.

arXiv Preprint

Vagueness, Logic and Use: Four Experimental Studies on Vagueness

Mind and Language 26 (2011) 540–573
(with Phil Serchuk and Ian Hargreaves)

Although arguments for and against competing theories of vagueness often appeal to claims about the use of vague predicates by ordinary speakers, such claims are rarely tested. An exception is Bonini et al. (1999), who report empirical results on the use of vague predicates by Italian speakers, and take the results to count in favor of epistemicism. Yet several methodological difficulties mar their experiments; we outline these problems and devise revised experiments that do not show the same results. We then describe three additional empirical studies that investigate further claims in the literature on vagueness: the hypothesis that speakers confuse ‘P‘ with ‘definitely P‘, the relative persuasiveness of different formulations of the inductive premise of the Sorites, and the interaction of vague predicates with three different forms of negation.

DOI: 10.1111/j.1468-0017.2011.01430.x

Preprint

The Development of Mathematical Logic from Russell to Tarski: 1900-1935

Leila Haaparanta, ed., The History of Modern Logic. New York and Oxford: Oxford University Press, 2009, pp. 318-471 (with Paolo Mancosu and Calixto Badesa)

Reprinted in Paolo Mancosu, The Adventure of Reason. Interplay Between Philosophy of Mathematics and Mathematical Logic, 1900-1940. Oxford: Oxford University press, 2010

The period from 1900 to 1935 was particularly fruitful and important for the development of logic and logical metatheory. This survey is organized along eight “itineraries” concentrating on historically and conceptually linked strands in this development. Itinerary I deals with the evolution of conceptions of axiomatics. Itinerary II centers on the logical work of Bertrand Russell. Itinerary III presents the development of set theory from Zermelo onward. Itinerary IV discusses the contributions of the algebra of logic tradition, in particular, Löwenheim and Skolem. Itinerary V surveys the work in logic connected to the Hilbert school, and itinerary V deals specifically with consistency proofs and metamathematics, including the incompleteness theorems. Itinerary VII traces the development of intuitionistic and many-valued logics. Itinerary VIII surveys the development of semantical notions from the early work on axiomatics up to Tarski’s work on truth.

DOI: 10.1093/acprof:oso/9780195137316.003.0029

Preprint

Table of Contents

Continue reading

Effective Finite-Valued Approximations of General Propositional Logics

Avron, Arnon; Dershowitz, Nachum; Rabinovich, Alexander (Eds.). Pillars of Computer Science: Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday. Lecture Notes in Computer Science 4800. Berlin: Springer, 2008. 107-129
(with Matthias Baaz)

Propositional logics in general, considered as a set of sentences, can be undecidable even if they have “nice” representations, e.g., are given by a calculus. Even decidable propositional logics can be computationally complex (e.g., already intuitionistic logic is PSPACE-complete). On the other hand, finite-valued logics are computationally relatively simple—at worst NP. Moreover, finite-valued semantics are simple, and general methods for theorem proving exist. This raises the question to what extent and under what circumstances propositional logics represented in various ways can be approximated by finite-valued logics. It is shown that the minimal m-valued logic for  which a given calculus is strongly sound can be calculated. It is also investigated under which conditions propositional logics can be characterized as the intersection of (effectively given) sequences of finite-valued logics.

DOI: 10.1007/978-3-540-78127-1_7

 

First-order Gödel logics

Annals of Pure and Applied Logic 147 (2007) 23-47 (with Matthias Baaz and Norbert Preining)

First-order Gödel logics are a family of finite- or infinite-valued logics where the sets of truth values V are closed subsets of [0,1] containing both 0 and 1. Different such sets V in general determine different Gödel logics GV (sets of those formulas which evaluate to 1 in every interpretation into V). It is shown that GV is axiomatizable iff V is finite, V is uncountable with 0 isolated in V, or every neighborhood of 0 in V is uncountable. Complete axiomatizations for each of these cases are given. The r.e. prenex, negation-free, and existential fragments of all first-order Gödel logics are also characterized.

DOI: 10.1016/j.apal.2007.03.001

Preprint

Kurt Gödel and computability theory

Logical Approaches to Computational Barriers Second Conference on Computability in Europe, CiE 2006, Swansea. Proceedings. LNCS 3988 (Springer, Berlin, 2006) 575-583

Although Kurt Gödel does not figure prominently in the history of computabilty theory, he exerted a significant influence on some of the founders of the field, both through his published work and through personal interaction. In particular, Gödel’s 1931 paper on incompleteness and the methods developed therein were important for the early development of recursive function theory and the lambda calculus at the hands of Church, Kleene, and Rosser. Church and his students studied Gödel 1931, and Gödel taught a seminar at Princeton in 1934. Seen in the historical context, Gödel was an important catalyst for the emergence of computability theory in the mid 1930s.

DOI:10.1007/11780342_59

Preprint