Natural deduction (for short: nd-) calculi have not been used systematically as a basis for automated theorem proving in classical logic. To remove objective obstacles to their use we describe (1) a method that allows to give semantic proofs of normal form theorems for nd-calculi and (2) a framework that allows to search directly for normal nd-proofs. Thus, one can try to answer the question: How do we bridge the gap between claims and assumptions in heuristically motivated ways? This informal (...) question motivates the formulation of intercalation calculi. Ic-calculi are the technical underpinnings for (1) and (2), and our paper focuses on their detailed presentation and meta-mathematical investigation in the case of classical predicate logic. As a central theme emerges the connection between restricted forms of nd-proofs and (strategies for) proof search: normal forms are not obtained by removing local "detours", but rather by constructing proofs that directly reflect proof-strategic considerations. That theme warrants further investigation. (shrink)

In the present paper, we prove the normalization theorem and the consistency of the first-order classical logic with disjunctive syllogism. First, we propose the natural deduction system SCD for classical propositional logic having rules for conjunction, implication, negation, and disjunction. The rules for disjunctive syllogism are regarded as the rules for disjunction. After we prove the normalization theorem and the consistency of SCD, we extend SCD to the system SPCD for the first-order classical logic with disjunctive syllogism. It can be (...) shown that SPCD is conservative extension to SCD. Then, the normalization theorem and the consistency of SPCD are given. (shrink)

This brief note corrects an error in one of the reduction steps in my paper 'Normalisation for Bilateral Classical Logic with some Philosophical Remarks' published in the Journal of Applied Logics 8/2 (2021): 531-556.

In this dissertation, we shall investigate whether Tennant's criterion for paradoxicality(TCP) can be a correct criterion for genuine paradoxes and whether the requirement of a normal derivation(RND) can be a proof-theoretic solution to the paradoxes. Tennant’s criterion has two types of counterexamples. The one is a case which raises the problem of overgeneration that TCP makes a paradoxical derivation non-paradoxical. The other is one which generates the problem of undergeneration that TCP renders a non-paradoxical derivation paradoxical. Chapter 2 deals with (...) the problem of undergeneration and Chapter 3 concerns the problem of overgeneration. Chapter 2 discusses that Tenant’s diagnosis of the counterexample which applies CR−rule and causes the undergeneration problem is not correct and presents a solution to the problem of undergeneration. Chapter 3 argues that Tennant’s diagnosis of the counterexample raising the overgeneration problem is wrong and provides a solution to the problem. Finally, Chapter 4 addresses what should be explicated in order for RND to be a proof-theoretic solution to the paradoxes. (shrink)

In this short paper I note that a key metatheorem does not hold for the bilateralist inferential framework: harmony does not entail consistency. I conclude that the requirement of harmony will not suffice for a bilateralist to maintain a proof theoretic account of classical logic. I conclude that a proof theoretic account of meaning based on the bilateralist framework has no natural way of distinguishing legitimate definitional inference rules from illegitimate ones (such as those for tonk). Finally, as an appendix (...) to the main argument, I propose an alternative non-bilateral formal solution to the problem of providing a proof-theoretic account of classical logic. (shrink)

Gentzen's systems of natural deduction and sequent calculus were byproducts in his program of proving the consistency of arithmetic and analysis. It is suggested that the central component in his results on logical calculi was the use of a tree form for derivations. It allows the composition of derivations and the permutation of the order of application of rules, with a full control over the structure of derivations as a result. Recently found documents shed new light on the discovery of (...) these calculi. In particular, Gentzen set up five different forms of natural calculi and gave a detailed proof of normalization for intuitionistic natural deduction. An early handwritten manuscript of his thesis shows that a direct translation from natural deduction to the axiomatic logic of Hilbert and Ackermann was, in addition to the influence of Paul Hertz, the second component in the discovery of sequent calculus. A system intermediate between the sequent calculus LI and axiomatic logic, denoted LIG in unpublished sources, is implicit in Gentzen's published thesis of 1934—35. The calculus has half rules, half “groundsequents,” and does not allow full cut elimination. Nevertheless, a translation from LI to LIG in the published thesis gives a subformula property for a complete class of derivations in LIG. After the thesis, Gentzen continued to work on variants of sequent calculi for ten more years, in the hope to find a consistency proof for arithmetic within an intuitionistic calculus. (shrink)

We give a direct, purely arithmetical and elementary proof of the strong normalization of the cut-elimination procedure for full (i.e., in presence of all the usual connectives) classical natural deduction.

Prawitz observed that Russell’s paradox in naive set theory yields a derivation of absurdity whose reduction sequence loops. Building on this observation, and based on numerous examples, Tennant claimed that this looping feature, or more generally, the fact that derivations of absurdity do not normalize, is characteristic of the paradoxes. Striking results by Ekman show that looping reduction sequences are already obtained in minimal propositional logic, when certain reduction steps, which are prima facie plausible, are considered in addition to the (...) standard ones. This shows that the notion of reduction is in need of clarification. Referring to the notion of identity of proofs in general proof theory, we argue that reduction steps should not merely remove redundancies, but must respect the identity of proofs. Consequentially, we propose to modify Tennant’s paradoxicality test by basing it on this refined notion of reduction. (shrink)

I examine Paul Boghossian's recent attempt to argue for scepticism about logical rules. I argue that certain rule- and proof-theoretic considerations can avert such scepticism. Boghossian's 'Tonk Argument' seeks to justify the rule of tonk-introduction by using the rule itself. The argument is subjected here to more detailed proof-theoretic scrutiny than Boghossian undertook. Its sole axiom, the so-called Meaning Postulate for tonk, is shown to be false or devoid of content. It is also shown that the rules of Disquotation and (...) of Semantic Ascent cannot be derived for sentences with tonk dominant. These considerations deprive Boghossian's scepticism of its support. (shrink)

I examine Paul Boghossian's recent attempt to argue for scepticism about logical rules. I argue that certain rule- and proof-theoretic considerations can avert such scepticism. Boghossian's 'Tonk Argument' seeks to justify the rule of tonk-introduction by using the rule itself. The argument is subjected here to more detailed proof-theoretic scrutiny than Boghossian undertook. Its sole axiom, the so-called Meaning Postulate for tonk, is shown to be false or devoid of content. It is also shown that the rules of Disquotation and (...) of Semantic Ascent cannot be derived for sentences with tonk dominant. These considerations deprive Boghossian's scepticism of its support. (shrink)

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

It is often said that in a purely formal perspective, intuitionistic logic has no obvious advantage to deal with the liar-type paradoxes. In this paper, we will argue that the standard intuitionistic natural deduction systems are vulnerable to the liar-type paradoxes in the sense that the acceptance of the liar-type sentences results in inference to absurdity (⊥). The result shows that the restriction of the Double Negation Elimination (DNE) fails to block the inference to ⊥. It is, however, not the (...) problem of the intuitionistic approaches to the liar-type paradoxes but the lack of expressive power of the standard intuitionistic natural deduction system. We introduce a meta-level negation for a given system and a meta-level absurdity, ⋏, to the intuitionistic system. We shall show that in the system, the inference to ⊥ is not given without the assumption that the system is complete. Moreover, we consider the Double Meta-Level Negation Elimination rules (DMNE) which implicitly assume the completeness of the system. Then, the restriction of DMNE can rule out the inference to ⊥. (shrink)

Natural deduction systems for classical, intuitionistic and modal logics were deeply investigated by Prawitz [D. Prawitz, Natural Deduction: A Proof-theoretical Study, in: Stockholm Studies in Philosophy, vol. 3, Almqvist and Wiksell, Stockholm, 1965. Reprinted at: Dover Publications, Dover Books on Mathematics, 2006] from a proof-theoretical perspective. Prawitz proved weak normalization for classical logic only for a language without logical or, there exists and with a restricted application of reduction ad absurdum. Reduction steps related to logical or, there exists and classical (...) negation bring about many problems solved only rather recently. For classical S5 modal logic, Prawitz defined a normalizable system, but for a language without logical or, there exists, ◊ and, for a propositional language without ◊, Medeiros [M.da P.N. Medeiros, A new S4 classical modal logic in natural deduction, Journal of Symbolic Logic 71 799–809] presented a normalizable system for classical S4. We can mention many cut-free Gentzen systems for S4, S5 and K45/K45D, some normalizable natural deduction systems for intuitionistic modal logics and one more for full classical S4, but not for full classical S5. Here our focus is on the definition of a classical and normalizable natural deduction system for S5, taking not only □ and ◊ as primitive symbols, but also all connectives and quantifiers, including classical negation, disjunction and the existential quantifier. The normalization procedure is based on the strategy proposed by Massi [C.D.B. Massi, Provas de normalizaçaõ para a lógica clássica, Ph.D. Thesis, Departamento de Filosofia, UNICAMP, Campinas, 1990] and Pereira and Massi [L.C. Pereira, C.D.B. Massi, Normalização para a lógica clássica, in: O que nos faz pensar, Cadernos de Filosofia da PUC-RJ, vol. 2, 1990, pp. 49–53] for first-order classical logic to cope with the combined use of classical negation, disjunction and the existential quantifier. Here we extend such results to deal with □ and ◊ too. The elimination rule for ◊ uses the notions of connection and of essentially modal formulas already proposed by Prawitz for the introduction of □. Beyond weak normalization, we also prove the subformula property for full S5. (shrink)

Various natural deduction formulations of classical, minimal, intuitionist, and intermediate propositional and first-order logics are presented and investigated with respect to satisfaction of the separation and subformula properties. The technique employed is, for the most part, semantic, based on general versions of the Lindenbaum and Lindenbaum–Henkin constructions. Careful attention is paid to which properties of theories result in the presence of which rules of inference, and to restrictions on the sets of formulas to which the rules may be employed, restrictions (...) determined by the formulas occurring as premises and conclusion of the invalid inference for which a counterexample is to be constructed. We obtain an elegant formulation of classical propositional logic with the subformula property and a singularly inelegant formulation of classical first-order logic with the subformula property, the latter, unfortunately, not a product of the strategy otherwise used throughout the article. Along the way, we arrive at an optimal strengthening of the subformula results for classical first-order logic obtained as consequences of normalization theorems by Dag Prawitz and Gunnar Stålmarck. (shrink)

A normalization procedure is given for classical natural deduction with the standard rule of indirect proof applied to arbitrary formulas. For normal derivability and the subformula property, it is sufficient to permute down instances of indirect proof whenever they have been used for concluding a major premiss of an elimination rule. The result applies even to natural deduction for classical modal logic.

We study how to postpone the application of the reductio ad absurdum rule ) in classical natural deduction. This technique is connected with two normalization strategies for classical logic, due to Prawitz and Seldin, respectively. We introduce a variant of Seldin’s strategy for the postponement of \, which induces a negative translation from classical to intuitionistic and minimal logic. Through this translation, Glivenko’s theorem from classical to intuitionistic and minimal logic is proven.

This paper studies a new classical natural deduction system, presented as a typed calculus named View the MathML sourceλ̲μlet. It is designed to be isomorphic to Curien and Herbelinʼs View the MathML sourceλ¯μμ˜-calculus, both at the level of proofs and reduction, and the isomorphism is based on the correct correspondence between cut in sequent calculus, and substitution in natural deduction. It is a combination of Parigotʼs λμ-calculus with the idea of “coercion calculus” due to Cervesato and Pfenning, accommodating let-expressions in (...) a surprising way: they expand Parigotʼs syntactic class of named terms.This calculus and the mentioned isomorphism Θ offer three missing components of the proof theory of classical logic: a canonical natural deduction system; a robust process of “read-back” of calculi in the sequent calculus format into natural deduction syntax; a formalization of the usual semantics of the View the MathML sourceλ¯μμ˜-calculus, that explains co-terms and cuts as, respectively, contexts and hole-filling instructions. View the MathML sourceλ̲μlet is not yet another classical calculus, but rather a canonical reflection in natural deduction of the impeccable treatment of classical logic by sequent calculus; and Θ provides the “read-back” map and the formalized semantics, based on the precise notions of context and “hole-expression” provided by View the MathML sourceλ̲μlet.We use “read-back” to achieve a precise connection with Parigotʼs λμ, and to derive λ-calculi for call-by-value combining control and let-expressions in a logically founded way. Finally, the semantics Θ, when fully developed, can be inverted at each syntactic category. This development gives us license to see sequent calculus as the semantics of natural deduction; and uncovers a new syntactic concept in View the MathML sourceλ¯μμ˜ , with which one can give a new definition of η-reduction. (shrink)

Termination for classical natural deduction is difficult in the presence of commuting/permutative conversions for disjunction. An approach based on reducibility candidates is presented that uses non-strictly positive inductive definitions.It covers second-order universal quantification and also the extension of the logic with fixed points of non-strictly positive operators, which appears to be a new result.Finally, the relation to Parigot’s strictly positive inductive definition of his set of reducibility candidates and to his notion of generalized reducibility candidates is explained.