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

Free Preprint from 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


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


Table of Contents

Introduction 1
Itinerary I: Metatheoretical Properties of Axiomatic Systems 3
1.1 Introduction 3
1.2 Peano’s school on the logical structure of theories 4
1.3 Hilbert on axiomatization 8
1.4 Completeness and categoricity in the work of Veblen and Huntington 10
1.5 Truth in a structure 12
Itinerary II: Bertrand Russell’s Mathematical Logic 15
2.1 From the Paris congress to the Principles of Mathematics 1900–1903 15
2.2 Russell and Poincare on predicativity 19
2.3 On Denoting 21
2.4 Russell’s ramified type theory 22
2.5 The logic of Principia 25
2.6 Further developments 26
Itinerary III: Zermelo’s Axiomatization of Set Theory and Related Foundational Issues 29
3.1 The debate on the axiom of choice 29
3.2 Zermelo’s axiomatization of set theory 32
3.3 The discussion on the notion of “definit” 35
3.4 Metatheoretical studies of Zermelo’s axiomatization 38
Itinerary IV: The Theory of Relatives and Löwenheim’s Theorem 41
4.1 Theory of relatives and model theory 41
4.2 The logic of relatives 44
4.3 Löwenheim’s theorem 46
4.4 Skolem’s first versions of Löwenheim’s theorem 56
Itinerary V: Logic in the Hilbert School 59
5.1 Early lectures on logic 59
5.2 The completeness of propositional logic 60
5.3 Consistency and completeness 61
5.4 Axioms and inference rules 66
5.5 Grundzüge der theoretischen Logik 70
5.6 The decision problem 71
5.6.1 The decision problem in the tradition of algebra of logic 72
5.6.2 Work on the decision problem after 1920 73
5.7 Combinatory logic and ?-calculus 74
5.8 Structural inference: Hertz and Gentzen 76
Itinerary VI: Proof Theory and Arithmetic 81
6.1 Hilbert’s Program for consistency proofs 81
6.2 Consistency proofs for weak fragments of arithmetic 82
6.3 Ackermann and von Neumann on epsilon substitution 87
6.4 Herbrand’s Theorem 92
6.5 Kurt Gödel and the incompleteness theorems 94
Itinerary VII: Intuitionism and Many-valued Logics 99
7.1 Intuitionistic logic 99
7.1.1 Brouwer’s philosophy of mathematics 99
7.1.2 Brouwer on the excluded middle 101
7.1.3 The logic of negation 102
7.1.4 Kolmogorov 103
7.1.5 The debate on intuitionist logic 106
7.1.6 The formalization and interpretation of intuitionistic logic 108
7.1.7 Gödel’s contributions to the metatheory of intuitionistic logic 110
7.2 Many-valued logics 111
Itinerary VIII: Semantics and Model-theoretic Notions 117
8.1 Background 117
8.1.1 The algebra of logic tradition 117
8.1.2 Terminological variations (systems of objects, models, and structures) 118
8.1.3 Interpretations for propositional logic 119
8.2 Consistency and independence for propositional logic 120
8.3 Post’s contributions to the metatheory of the propositional calculus 123
8.4 Semantical completeness of first-order logic 124
8.5 Models of first order logic 129
8.6 Completeness and categoricity 130
8.7 Tarski’s definition of truth 134
Notes 141
Bibliography 149
Index of Citations 175


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

Tableaux for reasoning about atomic updates

Logic for Programming, Artificial Intelligence, and Reasoning. 8th International Conference, LPAR 2001. Proceedings, LNAI 2250. (Springer, Berlin, 2001) 639-653
(with Christian G. Fermüller and Georg Moser)

A simple model of dynamic databases is studied from a modal logic perspecitve. A state \(\alpha\) of a database is an atomic update of a state \(\beta\) if at most one atomic statement is evaluated differently in \(\alpha\) compared to \(\beta\). The corresponding restriction on Kripke-like structures yields so-called update logics. These logics are studied also in a many-valued context. Adequate tableau calculi are given.

DOI: 10.1007/3-540-45653-8_44


Approximating propositional calculi by finite-valued logics


24th International Symposium on Multiple Valued Logic. Boston. Proceedings (IEEE Press, Los Alamitos, 1994) 257-263
(with Matthias Baaz)


The problem of approximating a propositional calculus is to find many-valued logics which are sound for the calculus (i.e., all theorems of the calculus are tautologies) with as few tautologies as possible. This has potential applications for representing (computationally complex) logics used in AI by (computationally easy) many-valued logics. It is investigated how far this method can be carried using (1) one or (2) an infinite sequence of many-valued logics. It is shown that the optimal candidate matrices for (1) can be computed from the calculus.

DOI: 10.1109/ISMVL.1994.302193


Note: An extended version is available on arXiv:math.LO/0203204

Characterization of the axiomatizable prenex fragments of first-order Gödel logics

In: 33rd International Symposium on Multiple-valued Logic. Proceedings. Tokyo, May 16-19, 2003 (IEEE Computer Society Press, 2003) 175-180 (with Matthias Baaz and Norbert Preining)

The prenex fragments of first-order infinite-valued Gödel logics are classified. It is shown that the prenex Gödel logics characterized by finite and by uncountable subsets of [0, 1] are axiomatizable, and that the prenex fragments of all countably infinite Gödel logics are not axiomatizable.

DOI 10.1109/ISMVL.2003.1201403


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