Proof Theory for Reasoning with Euler Diagrams: A Logic Translation and Normalization

Proof-theoretical notions and techniques, developed on the basis of sentential/symbolic representations of formal proofs, are applied to Euler diagrams. A translation of an Euler diagrammatic system into a natural deduction system is given, and the soundness and faithfulness of the translation are proved. Some consequences of the translation are discussed in view of the notion of free ride, which is mainly discussed in the literature of cognitive science as an account of inferential efficacy of diagrams. The translation enables us to formalize and analyze free ride in terms of proof theory. The notion of normal form of Euler diagrammatic proofs is investigated, and a normalization theorem is proved. Some consequences of the theorem are further discussed: in particular, an analysis of the structure of normal diagrammatic proofs; a diagrammatic counterpart of the usual subformula property; and a characterization of diagrammatic proofs compared with natural deduction proofs.     

Mathematical Method and Proof

On a traditional view, the primary role of a mathematical proof is to warrant the truth of the resulting theorem. This view fails to explain why it is very often the case that a new proof of a theorem is deemed important. Three case studies from elementary arithmetic show, informally, that there are many criteria by which ordinary proofs are valued. I argue that at least some of these criteria depend on the methods of inference the proofs employ, and that standard models of formal deduction are not well-equipped to support such evaluations. I discuss a model of proof that is used in the automated deduction community, and show that this model does better in that respect.     

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.     

Frege on Indirect Proof

Frege's account of indirect proof has been thought to be problematic. This thought seems to rest on the supposition that some notion of logical consequence – which Frege did not have – is indispensable for a satisfactory account of indirect proof. It is not so. Frege's account is no less workable than the account predominant today. Indeed, Frege's account may be best understood as a restatement of the latter, although from a higher order point of view. I argue that this ascent is motivated by Frege's conception of logic.     

Truth Values and Proof Theory

I present an account of truth values for classical logic, intuitionistic logic, and the modal logic S5, in which truth values are not a fundamental category from which the logic is defined, but rather, an idealisation of more fundamental logical features in the proof theory for each system. The result is not a new set of semantic structures, but a new understanding of how the existing semantic structures may be understood in terms of a more fundamental notion of logical consequence.     

The Justification of the Logical Laws Revisited

The proof-theoretic analysis of logical semantics undermines the received view of proof theory as being concerned with symbols devoid of meaning, and of model theory as the sole branch of logical theory entitled to access the realm of semantics. The basic tenet of proof-theoretic semantics is that meaning is given by some rules of proofs, in terms of which all logical laws can be justified and the notion of logical consequence explained. In this paper an attempt will be made to unravel some aspects of the issue and to show that this justification as it stands is untenable, for it relies on a formalistic conception of meaning and fails to recognise the fundamental distinction between semantic definitions and rules of inference. It is also briefly suggested that the profound connection between meaning and proofs should be approached by first reconsidering our very notion of proof.     

Knowledge of proofs

If proofs are nothing more than truth makers, then there is no force in the standard argument against classical logic (there is no guarantee that there is either a proof forA or a proof fornot A). The standard intuitionistic conception of a mathematical proof is stronger: there are epistemic constraints on proofs. But the idea that proofs must be recognizable as such by us, with our actual capacities, is incompatible with the standard intuitionistic explanations of the meanings of the logical constants. Proofs are to be recognizable in principle, not necessarily in practice, as shown in section 1. Section 2 considers unknowable propositions of the kind involved in Fitch's paradox:p and it will never be known thatp. It is argued that the intuitionist faces a dilemma: give up strongly entrenched common sense intuitions about such unknowable propositions, or give up verificationism. The third section considers one attempt to save intuitionism while partly giving up verificationism: keep the idea that a proposition is true iff there is a proof (verification) of it, and reject the idea that proofs must be recognizable in principle. It is argued that this move will have the effect that some standard reasons against classical semantics will be effective also against intuitionism. This is the case with Dummett's meaning theoretical argument. At the same time the basic reason for regarding proofs as more than mere truth makers is lost.I am much indebted for comments to Lars Bergström, Per Martin-Löf, Wlodek Rabinowicz, Fredrik Stjernberg, Dag Westerståhl and Tim Williamson. I owe even more to the many seminars about truth and meaning, led by Dag Prawitz, at the philosophy department of Stockholm University. These were especially intense in the mideighties, when I was a graduate student.     

Harmony and Autonomy in Classical Logic

Michael Dummett and Dag Prawitz have argued that a constructivist theory of meaning depends on explicating the meaning of logical constants in terms of the theory of valid inference, imposing a constraint of harmony on acceptable connectives. They argue further that classical logic, in particular, classical negation, breaks these constraints, so that classical negation, if a cogent notion at all, has a meaning going beyond what can be exhibited in its inferential use.I argue that Dummett gives a mistaken elaboration of the notion of harmony, an idea stemming from a remark of Gerhard Gentzen"s. The introduction-rules are autonomous if they are taken fully to specify the meaning of the logical constants, and the rules are harmonious if the elimination-rule draws its conclusion from just the grounds stated in the introduction-rule. The key to harmony in classical logic then lies in strengthening the theory of the conditional so that the positive logic contains the full classical theory of the conditional. This is achieved by allowing parametric formulae in the natural deduction proofs, a form of multiple-conclusion logic.     

On the Proof-theoretic Foundation of General Definition Theory

A general definition theory should serve as a foundation for the mathematical study of definitional structures. The central notion of such a theory is a precise explication of the intuitively given notion of a definitional structure. The purpose of this paper is to discuss the proof theory of partial inductive definitions as a foundation for this kind of a more general definition theory. Among the examples discussed is a suggestion for a more abstract definition of lambda-terms (derivations in natural deduction) that could provide a basis for a more systematic definitional approach to general proof theory.     

Radical anti-realism, Wittgenstein and the length of proofs

After sketching an argument for radical anti-realism that does not appeal to human limitations but polynomial-time computability in its definition of feasibility, I revisit an argument by Wittgenstein on the surveyability of proofs, and then examine the consequences of its application to the notion of canonical proof in contemporary proof-theoretical-semantics.     

Cut-Elimination and a Permutation-Free Sequent Calculus for Intuitionistic Logic

We describe a sequent calculus, based on work of Herbelin, of which the cut-free derivations are in 1-1 correspondence with the normal natural deduction proofs of intuitionistic logic. We present a simple proof of Herbelin's strong cut-elimination theorem for the calculus, using the recursive path ordering theorem of Dershowitz.     

The Significance of Semantic Realism

This paper is concerned with the relationship between the metaphysical doctrine of realism about the external world and semantic realism, as characterised by Michael Dummett. I argue that Dummett's conception of the relationship is flawed, and that Crispin Wright's account of the relationship, although designed to avoid the problems which beset Dummett's, nevertheless fails for similar reasons. I then aim to show that despite the fact that Dummett and Wright both fail to give a plausible account of the relationship between semantic realism and the metaphysical doctrine of realism, the semantic issue and the metaphysical issue are importantly related. I outline the precise sense in which the evaluation of semantic realism is relevant to the evaluation of realism about the external world, a sense overlooked by opponents of Dummett, such as Simon Blackburn and Michael Devitt. I finish with some brief remarks on metaphysics, semantics, and the nature of philosophy, and suggest that Dummett's arguments against semantic realism can retain their relevance to metaphysical debate even if we reject Dummett's idea that the theory of meaning is thefoundation of all philosophy.     

An Operational Logic of Proofs with Positive and Negative Information

The logic of proofs was introduced by Artemov in order to analize the formalization of the concept of proof rather than the concept of provability. In this context, some operations on proofs play a very important role. In this paper, we investigate some very natural operations, paying attention not only to positive information, but also to negative information (i.e. information saying that something cannot be a proof). We give a formalization for a fragment of such a logic of proofs, and we prove that our fragment is complete and decidable.     

Translations Between Gentzen–Prawitz and Jaśkowski–Fitch Natural Deduction Proofs

Two common forms of natural deduction proof systems are found in the Gentzen–Prawitz and Ja?kowski–Fitch systems. In this paper, I provide translations between proofs in these systems, pointing out the ways in which the translations highlight the structural rules implicit in the systems. These translations work for classical, intuitionistic, and minimal logic. I then provide translations for classical S4 proofs.

     

How to think about informal proofs

It is argued in this study that (i) progress in the philosophy of mathematical practice requires a general positive account of informal proof; (ii) the best candidate is to think of informal proofs as arguments that depend on their matter as well as their logical form; (iii) articulating the dependency of informal inferences on their content requires a redefinition of logic as the general study of inferential actions; (iv) it is a decisive advantage of this conception of logic that it accommodates the many mathematical proofs that include actions on objects other than propositions; (v) this conception of logic permits the articulation of project-sized tasks for the philosophy of mathematical practice, thereby supplying a partial characterisation of normal research in the field.     

紧缩论,证明与保守性

紧缩论者主张真谓词表达了一种逻辑概念,它的全部意义都体现在所有塔斯基式的T-语句中。Shapiro近来论证说,将紧缩论的公理添加到一阶皮亚诺算术公理系统(PA)中,在该扩张理论中能够证明PA的可靠性,并在此基础上证明PA的一致性,这表明紧缩论不具有保守性,因此真谓词不是紧缩的。本文论证,扩张理论预设了反射原则,这导致它推出了更多的东西,而反射原则是可证性谓词定义的推论,这才是造成扩张理论非保守性的真正根源。针对紧缩论的非保守性论证因此失效了。     

On the Conceptual Foundations of Anti-Realism

The central premise of Michael Dummett's global argument for anti-realism is the thesis that a speaker's grasp of the meaning of a declarative, indexical-free sentence must be manifested in her uses of that sentence. This enigmatic thesis has been the subject of a great deal of discussion, and something of a consensus has emerged about its content and justification. The received view is that the manifestation thesis expresses a behaviorist and reductive theory of meaning, essentially in agreement with Quine's view of language, and motivated by worries about the epistemology of communication. In the present paper I begin by arguing that this standard interpretation of the manifestation thesis is neither particularly faithful to Dummett's writings nor philosophically compelling. I then continue by reconstructing, from Dummett's texts, an account of the manifestation thesis, and of its justification, that differ sharply from the received view. On my reading, the thesis is motivated not epistemologically, but conceptually. I argue that connections among our conceptions of meaning, assertion, and justification lead to a conclusion about the metaphysics of meaning: we cannot form a clearly coherent conception of how two speakers can attach different meanings to a sentence without at the same time differing in what they count as justifying assertions made with that sentence. I conclude with some suggestions about how Dummett's argument for global anti-realism should be understood, given my account of the manifestation thesis. This revised version was published online in August 2006 with corrections to the Cover Date.     

Models of Deduction*

In standard model theory, deductions are not the things one models. But in general proof theory, in particular in categorial proof theory, one finds models of deductions, and the purpose here is to motivate a simple example of such models. This will be a model of deductions performed within an abstract context, where we do not have any particular logical constant, but something underlying all logical constants. In this context, deductions are represented by arrows in categories involved in a general adjoint situation. To motivate the notion of adjointness, one of the central notions of category theory, and of mathematics in general, it is first considered how some features of it occur in set-theoretical axioms and in the axioms of the lambda calculus. Next, it is explained how this notion arises in the context of deduction, where it characterizes logical constants. It is shown also how the categorial point of view suggests an analysis of propositional identity. The problem of propositional identity, i.e., the problem of identity of meaning for propositions, is no doubt a philosophical problem, but the spirit of the analysis proposed here will be rather mathematical. Finally, it is considered whether models of deductions can pretend to be a semantics. This question, which as so many questions having to do with meaning brings us to that wall that blocked linguists and philosophers during the whole of the twentieth century, is merely posed. At the very end, there is the example of a geometrical model of adjunction. Without pretending that it is a semantics, it is hoped that this model may prove illuminating and useful. *Since the text of this talk was written in 1999, the author has published several papers about related matters (see ‘Identity of proofs based on normalization and generality’, The Bulletin of Symbolic Logic 9 (2003), 477–503, corrected version available at: http://arXiv.org/math.LO/0208094; other titles are available in the same archive).     

Truth as an Epistemic Notion

What is the appropriate notion of truth for sentences whose meanings are understood in epistemic terms such as proof or ground for an assertion? It seems that the truth of such sentences has to be identified with the existence of proofs or grounds, and the main issue is whether this existence is to be understood in a temporal sense as meaning that we have actually found a proof or a ground, or if it could be taken in an abstract, tenseless sense. Would the latter alternative amount to realism with respect to proofs or grounds in a way that would be contrary to the supposedly anti-realistic standpoint underlying the epistemic understanding of linguistic expressions? Before discussing this question, I shall consider reasons for construing linguistic meaning epistemically and relations between such reasons and reasons for taking an anti-realist point of view towards the discourse in question.     

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.