Proof Theory

This paper surveys the common approach to quantification and generalised quantification in formal linguistics and philosophy of language. We point out how this general setting departs from empirical linguistic data, and give some hints for a different view based on proof theory, which on many aspects gets closer to the language itself. We stress the importance of Hilbert's oper- ator epsilon and tau for, respectively, existential and universal quantifications. Indeed, these operators help a lot to construct semantic representation close to (...) natural language, in particular with quantified noun phrases as individual terms. We also define guidelines for the design of the proof rules corresponding to generalised quantifiers. (shrink)

Reverse mathematics studies which subsystems of second order arithmetic are equivalent to key theorems of ordinary, non-set-theoretic mathematics. The main philosophical application of reverse mathematics proposed thus far is foundational analysis, which explores the limits of different foundations for mathematics in a formally precise manner. This paper gives a detailed account of the motivations and methodology of foundational analysis, which have heretofore been largely left implicit in the practice. It then shows how this account can be fruitfully applied in the (...) evaluation of major foundational approaches by a careful examination of two case studies: a partial realization of Hilbert’s program due to Simpson [1988], and predicativism in the extended form due to Feferman and Schütte. -/- Shore [2010, 2013] proposes that equivalences in reverse mathematics be proved in the same way as inequivalences, namely by considering only omega-models of the systems in question. Shore refers to this approach as computational reverse mathematics. This paper shows that despite some attractive features, computational reverse mathematics is inappropriate for foundational analysis, for two major reasons. Firstly, the computable entailment relation employed in computational reverse mathematics does not preserve justification for the foundational programs above. Secondly, computable entailment is a Pi-1-1 complete relation, and hence employing it commits one to theoretical resources which outstrip those available within any foundational approach that is proof-theoretically weaker than Pi-1-1-CA0. (shrink)

While non-classical theories of truth that take truth to be transparent have some obvious advantages over any classical theory that evidently must take it as non-transparent, several authors have recently argued that there's also a big disadvantage of non-classical theories as compared to their “external” classical counterparts: proof-theoretic strength. While conceding the relevance of this, the paper argues that there is a natural way to beef up extant internal theories so as to remove their proof-theoretic disadvantage. It is suggested that (...) the resulting internal theories should seem preferable to their external counterparts. (shrink)

The paper begins with a conceptual discussion of Michael Dummett's proof-theoretic justification of deduction or proof-theoretic semantics, which is based on what we might call Gentzen's thesis: 'the introductions constitute, so to speak, the "definitions" of the symbols concerned, and the eliminations are in the end only consequences thereof, which could be expressed thus: In the elimination of a symbol, the formula in question, whose outer symbol it concerns, may only "be used as that which it means on the basis (...) of the introduction of this symbol".' The intuitive philosophical content of Dummett's notions of harmony and stability is that harmony obtains if the grounds for asserting a proposition match the consequences of accepting it, and stability obtains if the converse also holds. Rules of inference define the meanings of a logical constant they govern if and only if they are stable. Gentzen observed that 'it should be possible to establish on the basis of certain requirements that the elimination rules are functions of the corresponding introduction rules.' One of the objectives of this paper is to specify such a function: I will specify a process by which it is possible to determine the elimination rules of logical constants from their introduction rules, and conversely, to determine the introduction rules from the elimination rules. I'll give the general forms of rules of inference and generalised reduction procedures for the normalisation of deduction. I'll give a formally precise characterisations of harmony and stability and show that deductions in logics that contain only constants governed by stable rules always normalise. (shrink)

This paper describes a decision procedure for disjunctions of conjunctions of anti-prenex normal forms of pure first-order logic (FOLDNFs) that do not contain V within the scope of quantifiers. The disjuncts of these FOLDNFs are equivalent to prenex normal forms whose quantifier-free parts are conjunctions of atomic and negated atomic formulae (= Herbrand formulae). In contrast to the usual algorithms for Herbrand formulae, neither skolemization nor unification algorithms with function symbols are applied. Instead, a procedure is described that rests on (...) nothing but equivalence transformations within pure first-order logic (FOL). This procedure involves the application of a calculus for negative normal forms (the NNF-calculus) with A -||- A & A (= &I) as the sole rule that increases the complexity of given FOLDNFs. The described algorithm illustrates how, in the case of Herbrand formulae, decision problems can be solved through a systematic search for proofs that reduce the number of applications of the rule &I to a minimum in the NNF-calculus. In the case of Herbrand formulae, it is even possible to entirely abstain from applying &I. Finally, it is shown how the described procedure can be used within an optimized general search for proofs of contradiction and what kind of questions arise for a &I-minimal proof strategy in the case of a general search for proofs of contradiction. (shrink)

The paper studies a cluster of systems for fully disquotational truth based on the restriction of initial sequents. Unlike well-known alternative approaches, such systems display both a simple and intuitive model theory and remarkable proof-theoretic properties. We start by showing that, due to a strong form of invertibility of the truth rules, cut is eliminable in the systems via a standard strategy supplemented by a suitable measure of the number of applications of truth rules to formulas in derivations. Next, we (...) notice that cut remains eliminable when suitable arithmetical axioms are added to the system. Finally, we establish a direct link between cut-free derivability in infinitary formulations of the systems considered and fixed-point semantics. Noticeably, unlike what happens with other background logics, such links are established without imposing any restriction to the premisses of the truth rules. (shrink)

Some such as Dean (2014) suggest that Montague's paradox requires the necessitation rule, and that the use of the rule in such a context is contentious. But here, I show that the paradox arises independently of the necessitation rule. A derivation of the paradox is given in modal system T without deploying necessitation; a necessitation-free derivation is also formulated in a significantly weaker system.

This paper considers Rumfitt’s bilateral classical logic (BCL), which is proposed to counter Dummett’s challenge to classical logic. First, agreeing with several authors, we argue that Rumfitt’s notion of harmony, used to justify logical rules by a purely proof theoretical manner, is not sufficient to justify coordination rules in BCL purely proof-theoretically. For the central part of this paper, we propose a notion of proof-theoretical validity similar to Prawitz for BCL and proves that BCL is sound and complete respect to (...) this notion of validity. The major difficulty in defining validity for BCL is that validity of positive +A appears to depend on negative −A, and vice versa. Thus, the straightforward inductive definition does not work because of this circular dependance. However, Knaster-Tarski’s fixed point theorem can resolve this circularity. Finally, we discuss the philosophical relevance of our work, in particular, the impact of the use of fixed point theorem and the issue of decidability. (shrink)

To appear in the Proceedings of Logic Colloquium 2006. (32 pages).

Data involving epistemic modals suggest that some classically valid argument forms, such as reductio, are invalid in natural language reasoning as they lead to modal collapses. We adduce further data showing that the classical argument forms governing the existential quantifier are similarly defective, as they lead to a de re–de dicto collapse. We observe a similar problem for disjunction. But if the classical argument forms for negation, disjunction and existential quantification are invalid, what are the correct forms that govern the (...) use of these items? Our diagnosis is that epistemic modals interfere with hypothetical reasoning. We present a modal first-order logic and model theory that characterizes hypothetical reasoning with epistemic modals in a principled manner. One upshot is a sound and complete natural deduction system for reasoning with epistemic modals in first-order logic. (shrink)

According to Schroeder-Heister 2018, proof-theoretic semantics is ‘an alternative to truth-condition semantics. It is based on the fundamental assumption that the central notion in terms of which meanings are assigned to certain expressions of our language, in particular to logical constants, is that of proof rather than truth. In this sense proof-theoretic semantics is semantics in terms of proof. Proof-theoretic semantics also means the semantics of proofs, i.e. the semantics of entities which describe how we arrive at certain assertions given (...) certain assumptions.' This text advocates that proof-theoretic semantics, as described above, was an approach to semantical issues in logic that appeared in mainstream philosophical literature at least a couple of centuries before the tradition of general proof theory (cf. Prawitz 1971) came into being. This is done by means of an interpretive analysis of Kant’s 1762 essay Die falsche Spitzfindigkeit der vier syllogistischen Figuren, in which two theses are argued: first, that the issue of justifying the logical validity of inferences is approached by Kant in this text, in a strong sense, in terms of proofs; and second, that the purpose of his effort is to establish a point concerning the semantical equivalence between certain distinct valid inferences. (shrink)

The purpose of this paper is to present a formalization of the language, semantics and axiomatization of justification logic in Coq. We present proofs in a natural deduction style derived from the axiomatic approach of justification logic. Additionally, we present possible world semantics in Coq based on Fitting models to formalize the semantic satisfaction of formulas. As an important result, with this implementation, it is possible to give a proof of soundness for $\mathsf{L}\mathsf{P}$ with respect to Fitting models.

In Arai it is shown that an ordinal \\) is an upper bound for the proof-theoretic ordinal of a set theory \\). In this paper we show that a second order arithmetic \ proves the wellfoundedness up to \\) for each N. It is easy to interpret \ in \\).

In this paper we explore the following question: how weak can a logic be for Rosser's essential undecidability result to be provable for a weak arithmetical theory? It is well known that Robinson's Q is essentially undecidable in intuitionistic logic, and P. Hajek proved it in the fuzzy logic BL for Grzegorczyk's variant of Q which interprets the arithmetic operations as non-total non-functional relations. We present a proof of essential undecidability in a much weaker substructural logic and for a much (...) weaker arithmetic theory, a version of Robinson's R (with arithmetic operations also interpreted as mere relations). Our result is based on a structural version of the undecidability argument introduced by Kleene and we show that it goes well beyond the scope of the Boolean, intuitionistic, or fuzzy logic. (shrink)

In this paper, we present two variants of Peirce’s Triadic Logic within a language containing only conjunction, disjunction, and negation. The peculiarity of our systems is that conjunction and disjunction are interpreted by means of Peirce’s mysterious binary operations Ψ and Φ from his ‘Logical Notebook’. We show that semantic conditions that can be extracted from the definitions of Ψ and Φ agree (in some sense) with the traditional view on the semantic conditions of conjunction and disjunction. Thus, we support (...) the conjecture that Peirce’s special interest in these operations is due to the fact that he interpreted them as conjunction and disjunction, respectively. We also show that one of our systems may serve as a suitable base for an interesting implicative expansion, namely the connexive three-valued logic by Cooper. Sound and complete natural deduction calculi are presented for all systems examined in this paper. (shrink)

In derivations of a sequent system, $\mathcal{L}\mathcal{J}$, and a natural deduction system, $\mathcal{N}\mathcal{J}$, the trails of formulae and the subformula property based on these trails will be defined. The derivations of $\mathcal{N}\mathcal{J}$ and $\mathcal{L}\mathcal{J}$ will be connected by the map $g$, and it will be proved the following: an $\mathcal{N}\mathcal{J}$-derivation is normal $\Longleftrightarrow $ it has the subformula property based on trails $\Longleftrightarrow $ its $g$-image in $\mathcal{L}\mathcal{J}$ is without maximum cuts $\Longrightarrow $ that $g$-image has the subformula property based (...) on trails. In $\mathcal{L}\mathcal{J}$-derivations, another type of cuts, sub-cuts, will be introduced, and it will be proved the following: all cuts of an $\mathcal{L}\mathcal{J}$-derivation are sub-cuts $\Longleftrightarrow $ it has the subformula property based on trails. (shrink)

This paper clarifies, revises, and extends the account of the transmission of truthmakers by core proofs that was set out in chap. 9 of Tennant. Brauer provided two kinds of example making clear the need for this. Unlike Brouwer’s counterexamples to excluded middle, the examples of Brauer that we are dealing with here establish the need for appeals to excluded middle when applying, to the problem of truthmaker-transmission, the already classical metalinguistic theory of model-relative evaluations.

Logical inferentialism maintains that the formal rules of inference fix the meanings of the logical terms. The categoricity problem points out to the fact that the standard formalizations of classical logic do not uniquely determine the intended meanings of its logical terms, i.e., these formalizations are not categorical. This means that there are different interpretations of the logical terms that are consistent with the relation of logical derivability in a logical calculus. In the case of the quantificational logic, the categoricity (...) problem is generated by the finite nature of the standard calculi and one direction in which it can be solved is to strengthen the deductive systems by adding infinite rules (such as the ω-rule), i.e., to construct a full formalization. Another main direction is to provide a natural semantics for the standard rules of inference, i.e., a semantics for which these rules are categorical. My aim in this paper is to analyze some recent approaches for solving the categoricity problem and to argue that a logical inferentialist should accept the infinite rules of inference for the first order quantifiers, since our use of the expressions “all” and “there is” leads us beyond the concrete and finite reasoning, and human beings do sometimes employ infinite rules of inference in their reasoning. (shrink)

We introduce a sequent system which is Gentzen algebraisable with orthomodular lattices as equivalent algebraic semantics, and therefore can be viewed as a calculus for orthomodular quantum logic. Its sequents are pairs of non-associative structures, formed via a structural connective whose algebraic interpretation is the Sasaki product on the left-hand side and its De Morgan dual on the right-hand side. It is a substructural calculus, because some of the standard structural sequent rules are restricted—by lifting all such restrictions, one recovers (...) a calculus for classical logic. (shrink)

The paper introduces a variant of connexive logic in which connexivity is extended from the interaction of negation with implication to the interaction of negation also with conjunction and disjunction. The logic is presented by two deductively equivalent methods: an axiomatic one and a natural-deduction one. Both are shown to be complete for a four-valued model theory.

Conventionalism about logic is the view that logical principles hold in virtue of some linguistic conventions. According to explicit conventionalism, these conventions have to be stipulated explicitly. Explicit conventionalism is subject to a famous criticism by Quine, who accused it of leading to an infinite regress. In response to the criticism, several authors have suggested reconstructing conventionalism as implicit in our linguistic behaviour. In this paper, drawing on a distinction from proof theory between derivable and admissible rules, I argue that (...) implicit conventionalism has not been stated in a sufficiently precise way, as it leaves open what one needs to say about admissible yet underivable rules. Moreover, it turns out that this challenge cannot be easily met, and that any attempt to meet the challenge makes conventionalism much less attractive a thesis. (shrink)

Substructural solutions to the semantic paradoxes have been broadly discussed in recent years. In particular, according to the non-transitive solution, we have to give up the metarule of Cut, whose role is to guarantee that the consequence relation is transitive. This concession—giving up a meta rule—allows us to maintain the entire consequence relation of classical logic. The non-transitive solution has been generalized in recent works into a hierarchy of logics where classicality is maintained at more and more metainferential levels. All (...) the logics in this hierarchy can accommodate a truth predicate, including the logic at the top of the hierarchy—known as CMω—which presumably maintains classicality at all levels. CMω has so far been accounted for exclusively in model-theoretic terms. Therefore, there remains an open question: how do we account for this logic in proof-theoretic terms? Can there be found a proof system that admits each and every classical principle—at all inferential levels—but nevertheless blocks the derivation of the liar? In the present paper, I solve this problem by providing such a proof system and establishing soundness and completeness results. Yet, I also argue that the outcome is philosophically unsatisfactory. In fact, I’m afraid that in light of my results this metainferential solution to the paradoxes can hardly be called a “solution,” let alone a good one. (shrink)

Minimally inconsistent LP (MiLP) is a nonmonotonic paraconsistent logic based on Graham Priest's logic of paradox (LP). Unlike LP, MiLP purports to recover, in consistent situations, all of classical reasoning. The present paper conducts a proof-theoretic analysis of MiLP. I highlight certain properties of this logic, introduce a simple sequent system for it, and establish soundness and completeness results. In addition, I show how to use my proof system in response to a criticism of this logic put forward by JC (...) Beall. (shrink)

In this paper we use proof-theoretic methods, specifically sequent calculi, admissibility of cut within them and the resultant subformula property, to examine a range of philosophically-motivated deontic logics. We show that for all of those logics it is a (meta)theorem that the Special Hume Thesis holds, namely that no purely normative conclusion follows non-trivially from purely descriptive premises (nor vice versa). In addition to its interest on its own, this also illustrates one way in which proof theory sheds light on (...) philosophically substantial questions. (shrink)

We give a proof-theoretic as well as a semantic characterization of a logic in the signature with conjunction, disjunction, negation, and the universal and existential quantifiers that we suggest has a certain fundamental status. We present a Fitch-style natural deduction system for the logic that contains only the introduction and elimination rules for the logical constants. From this starting point, if one adds the rule that Fitch called Reiteration, one obtains a proof system for intuitionistic logic in the given signature; (...) if instead of adding Reiteration, one adds the rule of Reductio ad Absurdum, one obtains a proof system for orthologic; by adding both Reiteration and Reductio, one obtains a proof system for classical logic. Arguably neither Reiteration nor Reductio is as intimately related to the meaning of the connectives as the introduction and elimination rules are, so the base logic we identify serves as a more fundamental starting point and common ground between proponents of intuitionistic logic, orthologic, and classical logic. The algebraic semantics for the logic we motivate proof-theoretically is based on bounded lattices equipped with what has been called a weak pseudocomplementation. We show that such lattice expansions are representable using a set together with a reflexive binary relation satisfying a simple first-order condition, which yields an elegant relational semantics for the logic. This builds on our previous study of representations of lattices with negations, which we extend and specialize for several types of negation in addition to weak pseudocomplementation; in an appendix, we further extend this representation to lattices with implications. Finally, we discuss adding to our logic a conditional obeying only introduction and elimination rules, interpreted as a modality using a family of accessibility relations. (shrink)

We present a method that generates two-sided sequent calculi for four-valued logics like "first degree entailment" (FDE). (We say that a logic is FDE-like if it has finitely many operators of finite arity, including negation, and if all of its operators are truth-functional over the four truth-values 'none', 'false', 'true', and 'both', where 'true' and 'both' are designated.) First, we show that for every n-ary operator * every truth table entry f*(x1,...,xn) = y can be characterized in terms of a (...) pair of sequent rules. Secondly, we use these sequent rules to build sequent calculi and prove their completeness. With the help of two simplification procedures we then show that the 2⋅4^n sequent rules that characterize an n-ary operator can be systematically reduced to at most four sequent rules. Thirdly, we use our method to investigate the proof-theoretical consequences of including intuitive truth-functional implications in FDE-like logics. (shrink)

We present a series of proof systems for exact entailment (i.e. relevant truthmaker preservation from premises to conclusion) and prove soundness and completeness. Using the proof systems, we observe that exact entailment is not only hyperintensional in the sense of Cresswell but also in the sense recently proposed by Odintsov and Wansing.

There is a Turing functional $\Phi $ taking $A^\prime $ to a theory $T_A$ whose complexity is exactly that of the jump of A, and which has the property that $A \leq _T B$ if and only if $T_A \trianglelefteq T_B$ in Keisler’s order. In fact, by more elaborate means and related theories, we may keep the complexity at the level of A without using the jump.

I show that the logic $\textsf {TJK}^{d+}$, one of the strongest logics currently known to support the naive theory of truth, is obtained from the Kripke semantics for constant domain intuitionistic logic by dropping the requirement that the accessibility relation is reflexive and only allowing reflexive worlds to serve as counterexamples to logical consequence. In addition, I provide a simplified natural deduction system for $\textsf {TJK}^{d+}$, in which a restricted form of conditional proof is used to establish conditionals.

Journal of Mathematical Logic, Ahead of Print. In mathematical logic there are two seemingly distinct kinds of principles called “reflection principles.” Semantic reflection principles assert that if a formula holds in the whole universe, then it holds in a set-sized model. Syntactic reflection principles assert that every provable sentence from some complexity class is true. In this paper, we study connections between these two kinds of reflection principles in the setting of second-order arithmetic. We prove that, for a large swathe (...) of theories, [math]-model reflection is equivalent to the claim that arbitrary iterations of uniform [math] reflection along countable well-orderings are [math]-sound. This result yields uniform ordinal analyzes of theories with strength between [math] and [math]. The main technical novelty of our analysis is the introduction of the notion of the proof-theoretic dilator of a theory [math], which is the operator on countable ordinals that maps the order-type of [math] to the proof-theoretic ordinal of [math]. We obtain precise results about the growth of proof-theoretic dilators as a function of provable [math]-model reflection. This approach enables us to simultaneously obtain not only [math], [math] and [math] ordinals but also reverse-mathematical theorems for well-ordering principles. (shrink)

We prove that the first-order logic of CZF is intuitionistic first-order logic. To do so, we introduce a new model of transfinite computation (Set Register Machines) and combine the resulting notion of realisability with Beth semantics. On the way, we also show that the propositional admissible rules of CZF are exactly those of intuitionistic propositional logic.

In this paper, we define a class of dialogue games for Johansson’s minimal logic and prove that it corresponds to the validity of minimal logic. Many authors have stated similar results for intuitionistic and classical logic either with or without actually proving the correspondence. Rahman, Clerbout and Keiff [17] have already specified dialogues for minimal logic; however, they transformed it into Fitch-style natural deduction only. We propose a different specification for minimal logic with the proof of correspondence between the existence (...) of winning strategies for the Proponent in this class of games and the sequent calculus for minimal logic. (shrink)

Free logics are a family of first-order logics which came about as a result of examining the existence assumptions of classical logic. What those assumptions are varies, but the central ones are that the domain of interpretation is not empty, every name denotes exactly one object in the domain and the quantifiers have existential import. Free logics reject the claim that names need to denote in. Positive free logic concedes that some atomic formulas containing non-denoting names are true, negative free (...) logic treats them as uniformly false, and neutral free logic as taking a third value. There has been a renewed interest in analyzing proof theory of free logic in recent years, based on intuitionistic logic in Maffezioli and Orlandelli, 137–158 2019) as well as classical logic in Pavlović and Gratzl, there for the positive and negative variants. While the latter streamlines the presentation of free logics and offers a more unified approach to the variants under consideration, it does not cover neutral free logic, since there is some lack of both clear formal intuitions on the semantic status of formulas with empty names, as well as a satisfying account of the conditional in this context. We discuss extending the results to this third major variant of free logics. We present a series of G3 sequent calculi adapted from Fjellstad, 93–119 2017, Journal of Applied Non-Classical Logics, 30, 272–289 2020), which possess all the desired structural properties of a good proof system, including admissibility of contraction and all versions of the cut rule. At the same time, we maintain the unified approach to free logics and moreover argue that greater clarity of intuitions is achieved once neutral free logic is conceptualized as consisting of two sub-varieties. (shrink)

The paper’s novelty is in combining two comparatively new fields of research: non-transitive logic and the proof method of correspondence analysis. To be more detailed, in this paper the latter is adapted to Weir’s non-transitive trivalent logic \({\mathbf{NC}}_{\mathbf{3}}\). As a result, for each binary extension of \({\mathbf{NC}}_{\mathbf{3}}\), we present a sound and complete Lemmon-style natural deduction system. Last, but not least, we stress the fact that Avron and his co-authors’ general method of obtaining _n_-sequent proof systems for any _n_-valent logic (...) with deterministic or non-deterministic matrices is not applicable to \({\mathbf{NC}}_{\mathbf{3}}\) and its binary extensions. (shrink)

According to the analysis of concessive conditionals suggested by Crupi and Iacona, a concessive conditional \(p{{\,\mathrm{\hookrightarrow }\,}}q\) is adequately formalized as a conjunction of conditionals. This paper presents a sound and complete axiomatic system for concessive conditionals so understood. The soundness and completeness proofs that will be provided rely on a method that has been employed by Raidl, Iacona, and Crupi to prove the soundness and completeness of an analogous system for evidential conditionals.

We provide sufficient conditions for the existence of a conservative translation from a consequence system to another one. We analyze the problem in many settings, namely when the consequence systems are generated by a deductive calculus or by a logic system including both proof-theoretic and model-theoretic components. We also discuss reflection of several metaproperties with the objective of showing that conservative translations provide an alternative to proving such properties from scratch. We discuss soundness and completeness, disjunction property and metatheorem of (...) deduction among others. We provide several illustrations of conservative translations. (shrink)

summary of work in relevant in the Anderson– tradition.]; Mares Troestra, Anne, 1992, Lectures on , CSLI Publications [A quick, easy-to.

Many prominent writers on the philosophy of logic, including Michael Dummett, Dag Prawitz, Neil Tennant, have held that the introduction and elimination rules of a logical connective must be ‘in harmony ’ if the connective is to possess a sense. This Harmony Thesis has been used to justify the choice of logic: in particular, supposed violations of it by the classical rules for negation have been the basis for arguments for switching from classical to intuitionistic logic. The Thesis has also (...) had an influence on the philosophy of language: some prominent writers in that area, notably Dummett and Robert Brandom, have taken it to be a special case of a more general requirement that the grounds for asserting a statement must cohere with its consequences. This essay considers various ways of making the Harmony Thesis precise and scrutinizes the most influential arguments for it. The verdict is negative: all the extant arguments for the Thesis are weak, and no version of it is remotely plausible. (shrink)