In 1931, the young Kurt Gödel published his First Incompleteness Theorem, which tells us that, for any sufficiently rich theory of arithmetic, there are some arithmetical truths the theory cannot prove. This remarkable result is among the most intriguing in logic. Gödel also outlined an equally significant Second Incompleteness Theorem. How are these Theorems established, and why do they matter? Peter Smith answers these questions by presenting an unusual variety of proofs for the First Theorem, showing how to prove the (...) Second Theorem, and exploring a family of related results. The formal explanations are interwoven with discussions of the wider significance of the two Theorems. This book will be accessible to philosophy students with a limited formal background. It is equally suitable for mathematics students taking a first course in mathematical logic. (shrink)

Some theorists have developed formal approaches to truth that depend on counterexamples to the structural rules of contraction. Here, we study such approaches, with an eye to helping them respond to a certain kind of objection. We define a contractive relative of each noncontractive relation, for use in responding to the objection in question, and we explore one example: the contractive relative of multiplicative-additive affine logic with transparent truth, or MAALT. -/- .

Geometric theories are presented as contraction- and cut-free systems of sequent calculi with mathematical rules following a prescribed rule-scheme that extends the scheme given in Negri and von Plato. Examples include cut-free calculi for Robinson arithmetic and real closed fields. As an immediate consequence of cut elimination, it is shown that if a geometric implication is classically derivable from a geometric theory then it is intuitionistically derivable.

We group the existing variants of the familiar set-theoretical and truth-theoretical paradoxes into two classes: connective paradoxes, which can in principle be ascribed to the presence of a contracting connective of some sort, and structural paradoxes, where at most the faulty use of a structural inference rule can possibly be blamed. We impute the former to an equivocation over the meaning of logical constants, and the latter to an equivocation over the notion of consequence. Both equivocation sources are tightly related, (...) and can be cleared up by adopting a particular substructural logic in place of classical logic. We then argue that our perspective can be justified via an informational semantics of contraction-free substructural logics. (shrink)

Definitional and axiomatic theories of truth -- Objects of truth -- Tarski -- Truth and set theory -- Technical preliminaries -- Comparing axiomatic theories of truth -- Disquotation -- Classical compositional truth -- Hierarchies -- Typed and type-free theories of truth -- Reasons against typing -- Axioms and rules -- Axioms for type-free truth -- Classical symmetric truth -- Kripke-Feferman -- Axiomatizing Kripke's theory in partial logic -- Grounded truth -- Alternative evaluation schemata -- Disquotation -- Classical logic -- Deflationism (...) -- Reflection -- Ontological reduction -- Applying theories of truth. (shrink)

In recent years there has been a revitalised interest in non-classical solutions to the semantic paradoxes. In this paper I show that a number of logics are susceptible to a strengthened version of Curry's paradox. This can be adapted to provide a proof theoretic analysis of the omega-inconsistency in Lukasiewicz's continuum valued logic, allowing us to better evaluate which logics are suitable for a naïve truth theory. On this basis I identify two natural subsystems of Lukasiewicz logic which individually, but (...) not jointly, lack the problematic feature. (shrink)

This paper presents and defends a way to add a transparent truth predicate to classical logic, such that and A are everywhere intersubstitutable, where all T-biconditionals hold, and where truth can be made compositional. A key feature of our framework, called STTT (for Strict-Tolerant Transparent Truth), is that it supports a non-transitive relation of consequence. At the same time, it can be seen that the only failures of transitivity STTT allows for arise in paradoxical cases.

This article outlines what a formal theory of truth should be like, at least at first glance. As not all of the stated constraints can be satisfied at the same time, in view of notorious semantic paradoxes such as the Liar paradox, we consider the maximal consistent combinations of these desiderata and compare their relative advantages and disadvantages.

This introduction to the basic ideas of structural proof theory contains a thorough discussion and comparison of various types of formalization of first-order logic. Examples are given of several areas of application, namely: the metamathematics of pure first-order logic (intuitionistic as well as classical); the theory of logic programming; category theory; modal logic; linear logic; first-order arithmetic and second-order logic. In each case the aim is to illustrate the methods in relatively simple situations and then apply them elsewhere in much (...) more complex settings. There are numerous exercises throughout the text. In general, the only prerequisite is a standard course in first-order logic, making the book ideal for graduate students and beginning researchers in mathematical logic, theoretical computer science and artificial intelligence. For the new edition, many sections have been rewritten to improve clarity, new sections have been added on cut elimination, and solutions to selected exercises have been included. (shrink)

A unified answer is offered to two distinct fundamental questions: whether a nonclassical solution to the semantic paradoxes should be extended to other apparently similar paradoxes and whether a nonclassical logic should be expressed in a nonclassical metalanguage. The paper starts by reviewing a budget of paradoxes involving the logical properties of validity, inconsistency, and compatibility. The author’s favored substructural approach to naive truth is then presented and it is explained how that approach can be extended in a very natural (...) way so as to solve a certain paradox of validity. However, three individually decisive reasons are later provided for thinking that no approach adopting a classical metalanguage can adequately account for all the features involved in the paradoxes of logical properties. Consequently, the paper undertakes the task to do better, and, building on the system already developed, introduces a theory in a nonclassical metalanguage that expresses an adequate logic of naive truth and of some naive logical properties. (shrink)

This paper concerns the relationship between transitivity of entailment, omega-inconsistency and nonstandard models of arithmetic. First, it provides a cut-free sequent calculus for non-transitive logic of truth STT based on Robinson Arithmetic and shows that this logic is omega-inconsistent. It then identifies the conditions in McGee for an omega-inconsistent logic as quantified standard deontic logic, presents a cut-free labelled sequent calculus for quantified standard deontic logic based on Robinson Arithmetic where the deontic modality is treated as a predicate, proves omega-inconsistency (...) and shows thus, pace Cobreros et al., that the result in McGee does not rely on transitivity. Finally, it also explains why the omega-inconsistent logics of truth in question do not require nonstandard models of arithmetic. (shrink)

At the centre of the traditional discussion of truth is the question of how truth is defined. Recent research, especially with the development of deflationist accounts of truth, has tended to take truth as an undefined primitive notion governed by axioms, while the liar paradox and cognate paradoxes pose problems for certain seemingly natural axioms for truth. In this book, Volker Halbach examines the most important axiomatizations of truth, explores their properties and shows how the logical results impinge on the (...) philosophical topics related to truth. In particular, he shows that the discussion on topics such as deflationism about truth depends on the solution of the paradoxes. His book is an invaluable survey of the logical background to the philosophical discussion of truth, and will be indispensable reading for any graduate or professional philosopher in theories of truth. (shrink)

The aim of this paper is to show that it’s not a good idea to have a theory of truth that is consistent but ω-inconsistent. In order to bring out this point, it is useful to consider a particular case: Yablo’s Paradox. In theories of truth without standard models, the introduction of the truth-predicate to a first order theory does not maintain the standard ontology. Firstly, I exhibit some conceptual problems that follow from so introducing it. Secondly, I show that (...) in second order theories with standard semantics the same procedure yields a theory that doesn’t have models. So, while having an ω- inconsistent theory is a bad thing, having an unsatisfiable theory of truth is actually worse. This casts doubts on whether the predicate in question is, after all, a truthpredicate for that language. Finally, I present some alternatives to prove an inconsistency adding plausible principles to certain theories of truth. (shrink)

In the tradition of substructural logics, it has been claimed for a long time that conjunction and inclusive disjunction are ambiguous:we should, in fact, distinguish between ‘lattice’ connectives (also called additive or extensional) and ‘group’ connectives (also called multiplicative or intensional). We argue that an analogous ambiguity affects the quantifiers. Moreover, we show how such a perspective could yield solutions for two well-known logical puzzles: McGee’s counterexample to modus ponens and the lottery paradox.

The concept of truth arguably plays a central role in many areas of philosophical theorizing. Yet, what seems to be one of the most fundamental principles governing that concept, i.e. the equivalence between P and , is inconsistent in full classical logic, as shown by the semantic paradoxes. I propose a new solution to those paradoxes, based on a principled revision of classical logic. Technically, the key idea consists in the rejection of the unrestricted validity of the structural principle of (...) contraction. I first motivate philosophically this idea with the metaphysical picture of the states-of-affairs expressed by paradoxical sentences as being distinctively . I then proceed to demonstrate that the theory of truth resulting from this metaphysical picture is, in many philosophically interesting respects, surprisingly stronger than most other theories of truth endorsing the equivalence between P and (for example, the theory vindicates the validity of the traditional laws of excluded middle and of non-contradiction, and also vindicates the traditional constraint of truth preservation on logical consequence). I conclude by proving a cutelimination theorem that shows the consistency of the theory. (shrink)

Substructural theories of truth are theories based on logics that do not include the full complement of usual structural rules. Existing substructural approaches fall into two main families: noncontractive approaches and nontransitive approaches. This paper provides a sketch of these families, and argues for two claims: first, that substructural theories are better-positioned than other theories to grapple with the truth-theoretic paradoxes, and second—more tentatively—that nontransitive approaches are in turn better-positioned than noncontractive approaches.

Rejecting structural contraction has been proposed as a strategy for escaping semantic paradoxes. The challenge for its advocates has been to make intuitive sense of how contraction might fail. I offer a way of doing so, based on a “naive” interpretation of the relation between structure and logical vocabulary in a sequent proof system. The naive interpretation of structure motivates the most common way of blaming Curry-style paradoxes on illicit contraction. By contrast, the naive interpretation will not as easily motivate (...) one recent noncontractive approach to the Liar paradox. (shrink)

A way is found to add axioms to sequent calculi that maintains the eliminability of cut, through the representation of axioms as rules of inference of a suitable form. By this method, the structural analysis of proofs is extended from pure logic to free-variable theories, covering all classical theories, and a wide class of constructive theories. All results are proved for systems in which also the rules of weakening and contraction can be eliminated. Applications include a system of predicate logic (...) with equality in which also cuts on the equality axioms are eliminated. (shrink)

This paper investigates how naive theories of truth fare with respect to a set of extremely plausible principles of restricted quantification. It is first shown that both nonsubstructural theories as well as certain substructural theories cannot validate all those principles. Then, pursuing further an approach to the semantic paradoxes that the author has defended elsewhere, the theory of restricted quantification available in a specific naive theory that rejects the structural property of contraction is explored. It is shown that the theory (...) validates all the principles in question, and it is argued that other prima facie plausible principles that the theory fails to validate are objectionable on independent grounds. (shrink)