Harmonising natural deduction

Prawitz proved a theorem, formalising ‘harmony’ in Natural Deduction systems, which showed that, corresponding to any deduction there is one to the same effect but in which no formula occurrence is both the consequence of an application of an introduction rule and major premise of an application of the related elimination rule. As Gentzen ordered the rules, certain rules in Classical Logic had to be excepted, but if we see the appropriate rules instead as rules for Contradiction, then we can extend the theorem to the classical case. Properly arranged there is a thoroughgoing ‘harmony’, in the classical rules. Indeed, as we shall see, they are, all together, far more ‘harmonious’ in the general sense than has been commonly observed. As this paper will show, the appearance of disharmony has only arisen because of the illogical way in which natural deduction rules for Classical Logic have been presented.     

Free Semantics

Free Semantics is based on normalized natural deduction for the weak relevant logic DW and its near neighbours. This is motivated by the fact that in the determination of validity in truth-functional semantics, natural deduction is normally used. Due to normalization, the logic is decidable and hence the semantics can also be used to construct counter-models for invalid formulae. The logic DW is motivated as an entailment logic just weaker than the logic MC of meaning containment. DW is the logic focussed upon, but the results extend to MC. The semantics is called ‘free semantics’ since it is disjunctively and existentially free in that no disjunctive or existential witnesses are produced, unlike in truth-functional semantics. Such ‘witnesses’ are only assumed in generality and are not necessarily actual. The paper sets up the free semantics in a truth-functional style and gives a natural deduction interpetation of the meta-logical connectives. We then set out a familiar tableau-style system, but based on natural deduction proof rather than truth-functional semantics. A proof of soundness and completeness is given for a reductio system, which is a transform of the tableau system. The reductio system has positive and negative rules in place of the elimination and introduction rules of Brady’s normalized natural deduction system for DW. The elimination-introduction turning points become closures of threads of proof, which are at the points of contradiction for the reductio system.     

The Classification of Propositional Calculi

We discuss Smirnovs problem of finding a common background for classifying implicational logics. We formulate and solve the problem of extending, in an appropriate way, an implicational fragment H of the intuitionistic propositional logic to an implicational fragment TV of the classical propositional logic. As a result we obtain logical constructions having the form of Boolean lattices whose elements are implicational logics. In this way, whole classes of new logics can be obtained. We also consider the transition from implicational logics to full logics. On the base of the lattices constructed, we formulate the main classification principles for propositional logics.     

Deduction theorems for weak implicational logics

The standard deduction theorem or introduction rule for implication, for classical logic is also valid for intuitionistic logic, but just as with predicate logic, other rules of inference have to be restricted if the theorem is to hold for weaker implicational logics.In this paper we look in detail at special cases of the Gentzen rule for and show that various subsets of these in effect constitute deduction theorems determining all the theorems of many well known as well as not well known implicational logics. In particular systems of rules are given which are equivalent to the relevance logics E,R, T, P-W and P-W-I.     

Expressive Power and Incompleteness of Propositional Logics

Natural deduction systems were motivated by the desire to define the meaning of each connective by specifying how it is introduced and eliminated from inference. In one sense, this attempt fails, for it is well known that propositional logic rules (however formulated) underdetermine the classical truth tables. Natural deduction rules are too weak to enforce the intended readings of the connectives; they allow non-standard models. Two reactions to this phenomenon appear in the literature. One is to try to restore the standard readings, for example by adopting sequent rules with multiple conclusions. Another is to explore what readings the natural deduction rules do enforce. When the notion of a model of a rule is generalized, it is found that natural deduction rules express “intuitionistic” readings of their connectives. A third approach is presented here. The intuitionistic readings emerge when models of rules are defined globally, but the notion of a local model of a rule is also natural. Using this benchmark, natural deduction rules enforce exactly the classical readings of the connectives, while this is not true of axiomatic systems. This vindicates the historical motivation for natural deduction rules. One odd consequence of using the local model benchmark is that some systems of propositional logic are not complete for the semantics that their rules express. Parallels are drawn with incompleteness results in modal logic to help make sense of this.     

Types of \mathsf{I} -Free Hereditary Right Maximal Terms

The implicational fragment of the relevance logic “ticket entailment” is closely related to the so-called hereditary right maximal terms. I prove that the terms that need to be considered as inhabitants of the types which are theorems of T_→ are in normal form and built in all but one case from and only. As a tool in the proof ordered term rewriting systems are introduced. Based on the main theorem I define FIT_→ – a Fitch-style calculus (related to FT_→) for the implicational fragment of ticket entailment.     

Identical Twins,Deduction Theorems,and Pattern Functions: Exploring the Implicative BCSK Fragment of S5

We recapitulate (Section 1) some basic details of the system of implicative BCSK logic, which has two primitive binary implicational connectives, and which can be viewed as a certain fragment of the modal logic S5. From this modal perspective we review (Section 2) some results according to which the pure sublogic in either of these connectives (i.e., each considered without the other) is an exact replica of the material implication fragment of classical propositional logic. In Sections 3 and 5 we show that for the pure logic of one of these implicational connectives two – in general distinct – consequence relations (global and local) definable in the Kripke semantics for modal logic turn out to coincide, though this is not so for the pure logic of the other connective, and that there is an intimate relation between formulas constructed by means of the former connective and the local consequence relation. (Corollary 5.8. This, as we show in an Appendix, is connected to the fact that the ‘propositional operations’ associated with both of our implicational connectives are close to being what R. Quackenbush has called pattern functions.) Between these discussions Section 4 examines some of the replacement-of-equivalents properties of the two connectives, relative to these consequence relations, and Section 6 closes with some observations about the metaphor of identical twins as applied to such pairs of connectives.     

Peirce’s Philosophy of Mathematical Education: Fostering Reasoning Abilities for Mathematical Inquiry

I articulate Charles S. Peirce’s philosophy of mathematical education as related to his conception of mathematics, the nature of its method of inquiry, and especially, the reasoning abilities required for mathematical inquiry. The main thesis is that Peirce’s philosophy of mathematical education primarily aims at fostering the development of the students’ semeiotic abilities of imagination, concentration, and generalization required for conducting mathematical inquiry by way of experimentation upon diagrams. This involves an emphasis on the relation between theory and practice and between mathematics and other fields including the arts and sciences. For achieving its goals, the article is divided in three sections. First, I expound Peirce’s philosophical account of mathematical reasoning. Second, I illustrate this account by way of a geometrical example, placing special emphasis on its relation to mathematical education. Finally, I put forth some Peircean philosophical principles for mathematical education.     

Algorithmic Proof Methods and Cut Elimination for Implicational Logics Part I: Modal Implication

In this work we develop goal-directed deduction methods for the implicational fragment of several modal logics. We give sound and complete procedures for strict implication of K, T, K4, S4, K5, K45, KB, KTB, S5, G and for some intuitionistic variants. In order to achieve a uniform and concise presentation, we first develop our methods in the framework of Labelled Deductive Systems [Gabbay 96]. The proof systems we present are strongly analytical and satisfy a basic property of cut admissibility. We then show that for most of the systems under consideration the labelling mechanism can be avoided by choosing an appropriate way of structuring theories. One peculiar feature of our proof systems is the use of restart rules which allow to re-ask the original goal of a deduction. In case of K, K4, S4 and G, we can eliminate such a rule, without loosing completeness. In all the other cases, by dropping such a rule, we get an intuitionistic variant of each system. The present results are part of a larger project of a goal directed proof theory for non-classical logics; the purpose of this project is to show that most implicational logics stem from slight variations of a unique deduction method, and from different ways of structuring theories. Moreover, the proof systems we present follow the logic programming style of deduction and seem promising for proof search [Gabbay and Reyle 84, Miller et al. 91].     

NORMAL DERIVATIONS AND SEQUENT DERIVATIONS

The well-known picture that sequent derivations without cuts and normal derivations “are the same” will be changed. Sequent derivations without maximum cuts (i.e. special cuts which correspond to maximum segments from natural deduction) will be considered. It will be shown that the natural deduction image of a sequent derivation without maximum cuts is a normal derivation, and the sequent image of a normal derivation is a derivation without maximum cuts. The main consequence of that property will be that sequent derivations without maximum cuts and normal derivations “are the same”.     

Verificationists Versus Realists: The Battle Over Knowability

Verificationism is the doctrine stating that all truths are knowable. Fitch’s knowability paradox, however, demonstrates that the verificationist claim (all truths are knowable) leads to “epistemic collapse”, i.e., everything which is true is (actually) known. The aim of this article is to investigate whether or not verificationism can be saved from the effects of Fitch’s paradox. First, I will examine different strategies used to resolve Fitch’s paradox, such as Edgington’s and Kvanvig’s modal strategy, Dummett’s and Tennant’s restriction strategy, Beall’s paraconsistent strategy, and Williamson’s intuitionistic strategy. After considering these strategies I will propose a solution that remains within the scope of classical logic. This solution is based on the introduction of a truth operator. Though this solution avoids the shortcomings of the non-standard (intuitionistic) solution, it has its own problems. Truth, on this approach, is not closed under the rule of conjunction-introduction. I will conclude that verificationism is defensible, though only at a rather great expense.     

Compositionality,Relevance, and Peirce’s Logic of Existential Graphs

Charles S. Peirce’s pragmatist theory of logic teaches us to take the context of utterances as an indispensable logical notion without which there is no meaning. This is not a spat against compositionality per se , since it is possible to posit extra arguments to the meaning function that composes complex meaning. However, that method would be inappropriate for a realistic notion of the meaning of assertions. To accomplish a realistic notion of meaning (as opposed e.g. to algebraic meaning), Sperber and Wilson’s Relevance Theory (RT) may be applied in the spirit of Peirce’s Pragmatic Maxim (PM): the weighing of information depends on (i) the practical consequences of accommodating the chosen piece of information introduced in communication, and (ii) what will ensue in actually using that piece in further cycles of discourse. Peirce’s unpublished papers suggest a relevance-like approach to meaning. Contextual features influenced his logic of Existential Graphs (EG). Arguments are presented pro and con the view in which EGs endorse non-compositionality of meaning.     

On Permutation in Simplified Semantics

This note explains an error in Restall’s ‘Simplified Semantics for Relevant Logics (and some of their rivals)’ (Restall, J Philos Logic 22(5):481–511, 1993) concerning the modelling conditions for the axioms of assertion A → ((A → B) → B) (there called c6) and permutation (A → (B → C)) → (B → (A → C)) (there called c7). We show that the modelling conditions for assertion and permutation proposed in ‘Simplified Semantics’ overgenerate. In fact, they overgenerate so badly that the proposed semantics for the relevant logic R validate the rule of disjunctive syllogism. The semantics provides for no models of R in which the “base point” is inconsistent. This problem is not restricted to ‘Simplified Semantics.’ The techniques of that paper are used in Graham Priest’s textbook An Introduction to Non-Classical Logic (Priest, 2001), which is in wide circulation: it is important to find a solution. In this article, we explain this result, diagnose the mistake in ‘Simplified Semantics’ and propose two different corrections.     

Relevant implication and the weak deduction theorem

It is shown that the implicational fragment of Anderson and Belnap's R, i.e. Church's weak implicational calculus, is not uniquely characterized by MP (modus ponens), US (uniform substitution), and WDT (Church's weak deduction theorem). It is also shown that no unique logic is characterized by these, but that the addition of further rules results in the implicational fragment of R. A similar result for E is mentioned.I am grateful to the referees; their comments enabled me to correct a mistake and to clarify several passages.     

Notes on Constructive Negation

We put together several observations on constructive negation. First, Russell anticipated intuitionistic logic by clearly distinguishing propositional principles implying the law of the excluded middle from remaining valid principles. He stated what was later called Peirce’s law. This is important in connection with the method used later by Heyting for developing his axiomatization of intuitionistic logic. Second, a work by Dragalin and his students provides easy embeddings of classical arithmetic and analysis into intuitionistic negationless systems. In the last section, we present in some detail a stepwise construction of negation which essentially concluded the formation of the logical base of the Russian constructivist school. Markov’s own proof of Markov’s principle (different from later proofs by Friedman and Dragalin) is described.     

Vague Objects Without Ontically Indeterminate Identity

The supporter of vague objects has been long challenged by the following ‘Argument from Identity’: 1) if there are vague objects, then there is ontically indeterminate identity; 2) there is no ontically indeterminate identity; therefore, 3) there are no vague objects. Some supporters of vague objects have argued that 1) is false. Noonan (Analysis 68: 174–176, 2008) grants that 1) does not hold in general, but claims that ontically indeterminate identity is indeed implied by the assumption that there are vague objects of a certain special kind (i.e. vague objects*). One can therefore formulate a ‘New Argument from Identity’: 1′) if there are vague objects*, then there is ontically indeterminate identity; 2) there is no ontically indeterminate identity; therefore, 3′) there are no vague objects*. Noonan’s strategy is to argue that premiss 1′) is inescapable, and, as a consequence, that Evans’s alleged defence of 2) is a real challenge for any supporter of vague objects. I object that a supporter of vague objects who grants the validity of Evans’s argument allegedly in favour of 2) should reject premiss 1′). The threat of the New Argument from Identity is thus avoided.     

First-Order da Costa Logic

Priest (2009) formulates a propositional logic which, by employing the worldsemantics for intuitionist logic, has the same positive part but dualises the negation, to produce a paraconsistent logic which it calls ‘Da Costa Logic’. This paper extends matters to the first-order case. The paper establishes various connections between first order da Costa logic, da Costa’s own C_ω, and classical logic. Tableau and natural deductions systems are provided and proved sound and complete.     

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

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.