A modified Young double-slit experiment proposed by Wootters and Zurek is considered in which a system P of parallel plates covered with a photographic emulsion has been set up in the region where we would normally expect the central interference fringes. Because under certain conditions P makes it possible to conclude with much more than50% certainty through which of the two slits each particular photon passed, the relevant interference pattern becomes blurred. It is proved that this implies a retroactive effect (...) because the setup of P and the interaction of photons with P appear to influence the momentum transferred to the photons by the edges of the slits at an earlier stage of the experiment. (shrink)

We present sound and complete sequent calculi for the modal mu-calculus with converse modalities, aka two-way modal mu-calculus. Notably, we introduce a cyclic proof system wherein proofs can be represented as finite trees with back-edges, i.e., finite graphs. The sequent calculi incorporate ordinal annotations and structural rules for managing them. Soundness is proved with relative ease as is the case for the modal mu-calculus with explicit ordinals. The main ingredients in the proof of completeness are isolating a class (...) of non-wellfounded proofs with sequents of bounded size, called slim proofs, and a counter-model construction that shows slimness suffices to capture all validities. Slim proofs are further transformed into cyclic proofs by means of re-assigning ordinal annotations. (shrink)

This comprehensive monograph is a cornerstone in the area of mathematical logic and related fields. Focusing on Gentzen-type proof theory, the book presents a detailed overview of creative works by the author and other 20th-century logicians that includes applications of proof theory to logic as well as other areas of mathematics. 1975 edition.

In this paper we describe a novel approach to defining an ontologically fundamental notion of co-presentness that does not go against the tenets of relativity theory. We survey the possible reactions to the problem of the present in relativity theory, introducing a terminological distinction between a static role of the present, which is served by the relation of simultaneity, and a dynamic role of the present, with the corresponding relation of co-presentness. We argue that both of these relations need to (...) be equivalence relations, but they need not coincide. Simultaneity, the sharing of a temporal coordinate, need not have fundamental ontological import, so that a relativizing strategy with respect to simultaneity seems promising. The notion of co-presentness, on the other hand, does have ontological import, and can therefore not be relativized to an observer or to an arbitrarily chosen frame. We argue that a formal representation of indeterminism can provide the structure needed to anchor the relation of co-presentness, and that this addition is in fact congenial to the notion of dynamic time as requiring real change. The resulting picture is one of an extended dynamic present, implying a formal distinction between static simultaneity and dynamic co-presentness. After working out the basics of our approach in the simpler framework of branching time, we provide our full analysis in the framework of branching space-times, which allows for a formal definition of modal correlations. The spatial extension of the dynamic present can reach as far as the modal correlations do. In the limit, the dynamic present could extend across a maximal space-like hypersurface. (shrink)

This book continues from where the authors' previous book, Structural Proof Theory, ended. It presents an extension of the methods of analysis of proofs in pure logic to elementary axiomatic systems and to what is known as philosophical logic. A self-contained brief introduction to the proof theory of pure logic is included that serves both the mathematically and philosophically oriented reader. The method is built up gradually, with examples drawn from theories of order, lattice theory and elementary geometry. (...) The aim is, in each of the examples, to help the reader grasp the combinatorial behaviour of an axiom system, which typically leads to decidability results. The last part presents, as an application and extension of all that precedes it, a proof-theoretical approach to the Kripke semantics of modal and related logics, with a great number of new results, providing essential reading for mathematical and philosophical logicians. (shrink)

An introduction to writing proofs, presented through compelling mathematical statements with interesting elementary proofs. This book offers an introduction to the art and craft of proof-writing. The author, a leading research mathematician, presents a series of engaging and compelling mathematical statements with interesting elementary proofs. These proofs capture a wide range of topics, including number theory, combinatorics, graph theory, the theory of games, geometry, infinity, order theory, and real analysis. The goal is to show students and aspiring mathematicians how (...) to write proofs with elegance and precision. (shrink)

Now in so far as it is recognized that the constituents of the environment are not present inside the body in the same way as they are present outside it, to that extent they are bound, the moment they are inside it, to become something essentially different from the environment.

'Numbers and Proofs' presents a gentle introduction to the notion of proof to give the reader an understanding of how to decipher others' proofs as well as construct their own. Useful methods of proof are illustrated in the context of studying problems concerning mainly numbers (real, rational, complex and integers). An indispensable guide to all students of mathematics. Each proof is preceded by a discussion which is intended to show the reader the kind of thoughts they might (...) have before any attempt proof is made. Established proofs which the student is in a better position to follow then follow. Presented in the author's entertaining and informal style, and written to reflect the changing profile of students entering universities, this book will prove essential reading for all seeking an introduction to the notion of proof as well as giving a definitive guide to the more common forms. Stressing the importance of backing up "truths" found through experimentation, with logically sound and watertight arguments, it provides an ideal bridge to more complex undergraduate maths. (shrink)

Sequent calculi constitute an interesting and important category of proof systems. They are much less known than axiomatic systems or natural deduction systems are, and they are much less known than they should be. Sequent calculi were designed as a theoretical framework for investigations of logical consequence, and they live up to the expectations completely as an abundant source of meta-logical results. The goal of this book is to provide a fairly comprehensive view of sequent calculi -- including a (...) wide range of variations. The focus is on sequent calculi for various non-classical logics, from intuitionistic logic to relevance logic, through linear and modal logics. A particular version of sequent calculi, the so-called consecution calculi, have seen important new developments in the last decade or so. The invention of new consecution calculi for various relevance logics allowed the last major open problem in the area of relevance logic to be solved positively: pure ticket entailment is decidable. An exposition of this result is included in chapter 9 together with further new decidability results (for less famous systems). A series of other results that were obtained by J. M. Dunn and me, or by me in the last decade or so, are also presented in various places in the book. Some of these results are slightly improved in their current presentation. Obviously, many calculi and several important theorems are not new. They are included here to ensure the completeness of the picture; their original formulations may be found in the referenced publications. This book contains very little about semantics, in general, and about the semantics of non-classical logic in particular. (shrink)

Proofs and countermodels are the two sides of completeness proofs, but, in general, failure to find one does not automatically give the other. The limitation is encountered also for decidable non-classical logics in traditional completeness proofs based on Henkin’s method of maximal consistent sets of formulas. A method is presented that makes it possible to establish completeness in a direct way: For any given sequent either a proof in the given logical system or a countermodel in the corresponding frame (...) class is found. The method is a synthesis of a generation of calculi with internalized relational semantics, a Tait–Schütte–Takeuti style completeness proof, and procedures to finitize the countermodel construction. Finitizations for intuitionistic propositional logic are obtained through the search for a minimal derivation, through pruning of infinite branches in search trees by means of a suitable syntactic counterpart of semantic filtration, or through a proof-theoretic embedding into an appropriate provability logic. A number of examples illustrates the method, its subtleties, challenges, and present scope. (shrink)

The Four-Colour Theorem (4CT) proof, presented to the mathematical community in a pair of papers by Appel and Haken in the late 1970's, provoked a series of philosophical debates. Many conceptual points of these disputes still require some elucidation. After a brief presentation of the main ideas of Appel and Haken’s procedure for the proof and a reconstruction of Thomas Tymoczko’s argument for the novelty of 4CT’s proof, we shall formulate some questions regarding the connections between (...) the points raised by Tymoczko and some Wittgensteinian topics in the philosophy of mathematics such as the importance of the surveyability as a criterion for distinguishing mathematical proofs from empirical experiments. Our aim is to show that the “characteristic Wittgensteinian invention” (Mühlhölzer 2006) – the strong distinction between proofs and experiments – can shed some light in the conceptual confusions surrounding the Four-Colour Theorem. (shrink)

The idea of proof-theoretic validity originated in the work of Gentzen, when he suggested that the meaning of each logical expression was encapsulated in its introduction-rules. The idea was developed by Prawitz and Dummett, but came under attack by Prior under the soubriquet 'analytic validity'. Logical truths and logical consequences are deemed analytically valid by virtue of following, in a way which the present chapter clarifies, from the meaning of the logical constants. But different logics are based on different (...) rules, confer different meanings and so validate different theorems and consequences, some of which are arguably not true or valid at all. It seems to follow that some analytic statements are in fact false. The moral is that we must be careful what rules we adopt and what meanings we use our rules to determine. (shrink)

Proof Theory of Modal Logic is devoted to a thorough study of proof systems for modal logics, that is, logics of necessity, possibility, knowledge, belief, time, computations etc. It contains many new technical results and presentations of novel proof procedures. The volume is of immense importance for the interdisciplinary fields of logic, knowledge representation, and automated deduction.

The completeness of the modal logic S4 for all topological spaces as well as for the real line , the n-dimensional Euclidean space and the segment etc. was proved by McKinsey and Tarski in 1944. Several simplified proofs contain gaps. A new proof presented here combines the ideas published later by G. Mints and M. Aiello, J. van Benthem, G. Bezhanishvili with a further simplification. The proof strategy is to embed a finite rooted Kripke structure for S4 into (...) a subspace of the Cantor space which in turn encodes . This provides an open and continuous map from onto the topological space corresponding to . The completeness follows as S4 is complete with respect to the class of all finite rooted Kripke structures. (shrink)

The paper presents a proof-theoretic semantics (PTS) for a fragment of natural language, providing an alternative to the traditional model-theoretic (Montagovian) semantics (MTS), whereby meanings are truth-condition (in arbitrary models). Instead, meanings are taken as derivability-conditions in a dedicated natural-deduction (ND) proof-system. This semantics is effective (algorithmically decidable), adhering to the meaning as use paradigm, not suffering from several of the criticisms formulated by philosophers of language against MTS as a theory of meaning. In particular, Dummett’s manifestation argument (...) does not obtain, and assertions are always warranted, having grounds of assertion. The proof system is shown to satisfy Dummett’s harmony property, justifying the ND rules as meaning conferring. The semantics is suitable for incorporation into computational linguistics grammars, formulated in type-logical grammar. (shrink)

Proof complexity is a rich subject drawing on methods from logic, combinatorics, algebra and computer science. This self-contained book presents the basic concepts, classical results, current state of the art and possible future directions in the field. It stresses a view of proof complexity as a whole entity rather than a collection of various topics held together loosely by a few notions, and it favors more generalizable statements. Lower bounds for lengths of proofs, often regarded as the key (...) issue in proof complexity, are of course covered in detail. However, upper bounds are not neglected: this book also explores the relations between bounded arithmetic theories and proof systems and how they can be used to prove upper bounds on lengths of proofs and simulations among proof systems. It goes on to discuss topics that transcend specific proof systems, allowing for deeper understanding of the fundamental problems of the subject. (shrink)

Though pictures are often used to present mathematical arguments, they are not typically thought to be an acceptable means for presenting mathematical arguments rigorously. With respect to the proofs in the Elements in particular, the received view is that Euclid's reliance on geometric diagrams undermines his efforts to develop a gap-free deductive theory. The central difficulty concerns the generality of the theory. How can inferences made from a particular diagrams license general mathematical results? After surveying the history behind the received (...) view, this essay provides a contrary analysis by introducing a formal account of Euclid's proofs, termed Eu. Eu solves the puzzle of generality surrounding Euclid's arguments. It specifies what diagrams Euclid's diagrams are, in a precise formal sense, and defines generality-preserving proof rules in terms of them. After the central principles behind the formalization are laid out, its implications with respect to the question of what does and does not constitute a genuine picture proof are explored. (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.

The proof theory of many-valued systems has not been investigated to an extent comparable to the work done on axiomatizatbility of many-valued logics. Proof theory requires appropriate formalisms, such as sequent calculus, natural deduction, and tableaux for classical (and intuitionistic) logic. One particular method for systematically obtaining calculi for all finite-valued logics was invented independently by several researchers, with slight variations in design and presentation. The main aim of this report is to develop the proof theory (...) of finite-valued first order logics in a general way, and to present some of the more important results in this area. In Systems covered are the resolution calculus, sequent calculus, tableaux, and natural deduction. This report is actually a template, from which all results can be specialized to particular logics. (shrink)

We present a setting in which the search for a proof of B or a refutation of B can be carried out simultaneously: in contrast, the usual approach in automated deduction views proving B or proving ¬B as two, possibly unrelated, activities. Our approach to proof and refutation is described as a two-player game in which each player follows the same rules. A winning strategy translates to a proof of the formula and a counter-winning strategy translates to (...) a refutation of the formula. The game is described for multiplicative and additive linear logic . A game theoretic treatment of the multiplicative connectives is intricate and our approach to it involves two important ingredients. First, labeled graph structures are used to represent positions in a game and, second, the game playing must deal with the failure of a given player and with an appropriate resumption of play. This latter ingredient accounts for the fact that neither player might win. (shrink)

Mathematical proofs generally allow for various levels of detail and conciseness, such that they can be adapted for a particular audience or purpose. Using automated reasoning approaches for teaching proof construction in mathematics presupposes that the step size of proofs in such a system is appropriate within the teaching context. This work proposes a framework that supports the granularity analysis of mathematical proofs, to be used in the automated assessment of students' proof attempts and for the presentation (...) of hints and solutions at a suitable pace. Models for granularity are represented by classifiers, which can be generated by hand or inferred from a corpus of sample judgments via machine-learning techniques. This latter procedure is studied by modeling granularity judgments from four experts. The results provide support for the granularity of assertion-level proofs but also illustrate a degree of subjectivity in assessing step size. (shrink)

This article investigates the proof theory of the Quantified Argument Calculus as developed and systematically studied by Hanoch Ben-Yami [3, 4]. Ben-Yami makes use of natural deduction, we, however, have chosen a sequent calculus presentation, which allows for the proofs of a multitude of significant meta-theoretic results with minor modifications to the Gentzen’s original framework, i.e., LK. As will be made clear in course of the article LK-Quarc will enjoy cut elimination and its corollaries.

This paper is the second part of the syntactic demonstration of the Arithmetical Completeness of the modal system G, the first part of which is presented in [9]. Given a sequent S so that ⊢GL-LIN S, ⊬G S, and given its characteristic formula H = char(S), which expresses the non G-provability of S, we construct a canonical proof-tree T of ~ H in GL-LIN, the height of which is the distance d(S, G) of S from G. T is the (...) syntactic countermodel of S with respect to Gand is a tool of general interest in Provability Logic, that allows some classification in the set of the arithmetical interpretations. (shrink)

We present a proof for a conjecture previously formulated by Dzhafarov et al.. The conjecture specifies a measure for the degree of contextuality and a criterion for contextuality in a broad class of quantum systems. This class includes Leggett–Garg, EPR/Bell, and Klyachko–Can–Binicioglu–Shumovsky type systems as special cases. In a system of this class certain physical properties \ are measured in pairs \ \); every property enters in precisely two such pairs; and each measurement outcome is a binary random variable. (...) Denoting the measurement outcomes for a property \ in the two pairs it enters by \ and \, the pair of measurement outcomes for \ \) is \ \). Contextuality is defined as follows: one computes the minimal possible value \ for the sum of \ ) that is allowed by the individual distributions of \ and \; one computes the minimal possible value \ for the sum of \ across all possible couplings of the entire set of random variables \ in the system; and the system is considered contextual if \ ). This definition has its justification in the general approach dubbed Contextuality-by-Default, and it allows for measurement errors and signaling among the measured properties. The conjecture proved in this paper specifies the value of \ in terms of the distributions of the measurement outcomes \ \). (shrink)

We present a survey of proof theory in the USSR beginning with the paper by Kolmogorov [1925] and ending (mostly) in 1969; the last two sections deal with work done by A. A. Markov and N. A. Shanin in the early seventies, providing a kind of effective interpretation of negative arithmetic formulas. The material is arranged in chronological order and subdivided according to topics of investigation. The exposition is more detailed when the work is little known in the West (...) or the original presentation can be improved using notions or results which appeared later. This includes such topics as Novikov's cut-elimination method (regular formulas) and Maslov's inverse method for the predicate logic. (shrink)

This paper is the first of a series of three articles that present the syntactic proof of the PA-completeness of the modal system G, by introducing suitable proof-theoretic objects, which also have an independent interest. We start from the syntactic PA-completeness of modal system GL-LIN, previously obtained in [7], [8], and so we assume to be working on modal sequents S which are GL-LIN-theorems. If S is not a G-theorem we define here a notion of syntactic metric d(S, (...) G): we calculate a canonical characteristic fomula H of S (char(S)) so that ⊢G ∼ H → (∼S) and ⊢GL-LIN ∼ H, and the complexity σ of ∼ H gives the distance d(S, G) of S from G. Then, in order to produce the whole completeness proof as an induction on this d(S, G), we introduce the tree-interpretation of a modal sequent Q into PA, that sends the letters of Q into PA-formulas describing the properties of a GL-LIN-proof P of Q: It is also a d(*, G)-metric linked interpretation, since it will be applied to a proof-tree T of ∼ H with H = char(S) and σ(∼ H) = d(S, G). (shrink)

Kurt Gödel wrote (1964, p. 272), after he had read Husserl, that the notion of objectivity raises a question: “the question of the objective existence of the objects of mathematical intuition (which, incidentally, is an exact replica of the question of the objective existence of the outer world)”. This “exact replica” brings to mind the close analogy Husserl saw between our intuition of essences in Wesensschau and of physical objects in perception. What is it like to experience a mathematical proving (...) process? What is the ontological status of a mathematical proof? Can computer assisted provers output a proof? Taking a naturalized world account, I will assess the relationship between mathematics, the physical world and consciousness by introducing a significant conceptual distinction between proving and proof. I will propose that proving is a phenomenological conscious experience. This experience involves a combination of what Kurt Gödel called intuition, and what Husserl called intentionality. In contrast, proof is a function of that process — the mathematical phenomenon — that objectively self-presents a property in the world, and that results from a spatiotemporal unity being subject to the exact laws of nature. In this essay, I apply phenomenology to mathematical proving as a performance of consciousness, that is, a lived experience expressed and formalized in language, in which there is the possibility of formulating intersubjectively shareable meanings. (shrink)

This article provides the proof-theoretic analysis of the transfinitely iterated fixed point theories $\widehat{ID}_\alpha and \widehat{ID}_{<\alpha};$ the exact proof-theoretic ordinals of these systems are presented.

__Language Proof and Logic_ is available as a physical book with the software included on CD and as a downloadable package of software plus the book in PDF format. The all-electronic version is available from Openproof at ggweb.stanford.edu._ The textbook/software package covers first-order language in a method appropriate for first and second courses in logic. An on-line grading services instantly grades solutions to hundred of computer exercises. It is designed to be used by philosophy instructors teaching a logic course (...) to undergraduates in philosophy, computer science, mathematics, and linguistics. Introductory material is presented in a systematic and accessible fashion. Advanced chapters include proofs of soundness and completeness for propositional and predicate logic, as well as an accessible sketch of Godel's first incompleteness theorem. The book is appropriate for a wide range of courses, from first logic courses for undergraduates to a first graduate logic course. The software package includes four programs: Tarski's World 5.0, a new version of the popular program that teaches the basic first-order language and its semantics; Fitch, a natural deduction proof environment for giving and checking first-order proofs; Boole, a program that facilitates the construction and checking of truth tables and related notions ; Submit, a program that allows students to submit exercises done with the above programs to the Grade Grinder, the automatic grading service. Grade reports are returned to the student and, if requested, to the student's instructor, eliminating the need for tedious checking of homework. All programs are available for Windows, Macintosh and Linux systems. Instructors do not need to use the programs themselves in order to be able to take advantage of their pedagogical value. More about the software can be found at lpl.stanford.edu. The price of a new text/software package includes one Registration ID, which must be used each time work is submitted to the grading service. Once activated, the Registration ID is not transferable. (shrink)

Tetravalent modal logic (TML) was introduced by Font and Rius in 2000. It is an expansion of the Belnap-Dunn four-valued logic FOUR, a logical system that is well-known for the many applications found in several fields. Besides, TML is the logic that preserves degrees of truth with respect to Monteiro’s tetravalent modal algebras. Among other things, Font and Rius showed that TML has a strongly adequate sequent system, but unfortunately this system does not enjoy the cut-elimination property. However, in a (...) previous work we presented a sequent system for TML with the cut-elimination property. Besides, in this same work, it was also presented a sound and complete natural deduction system for this logic. In the present article we continue with the study of TML under a proof-theoretic perspective. In the first place, we show that the natural deduction system that we introduced before admits a normalization theorem. In the second place, taking advantage of the contrapositive implication for the tetravalent modal algebras introduced by A. V. Figallo and P. Landini, we define a decidable tableau system adequate to check validity in the logic TML. Finally, we provide a sound and complete tableau system for TML in the original language. These two tableau systems constitute new (proof-theoretic) decision procedures for checking validity in the variety of tetravalent modal algebras. (shrink)

We present some proof-theoretic results for the normal modal logic whose characteristic axiom is \. We present a sequent system for this logic and a hypersequent system for its first-order form and show that these are equivalent to Hilbert-style axiomatizations. We show that the question of validity for these logics reduces to that of classical tautologyhood and first-order logical truth, respectively. We close by proving equivalences with a Fitch-style proof system for revision theory.

In this paper, we present another case study in the general project of proof mining which means the logical analysis of prima facie non-effective proofs with the aim of extracting new computationally relevant data. We use techniques based on monotone functional interpretation developed in Kohlenbach , Oxford University Press, Oxford, 1996, pp. 225–260) to analyze Cheney's simplification 189) of Jackson's original proof 320) of the uniqueness of the best L1-approximation of continuous functions fC[0,1] by polynomials pPn of degree (...) n. Cheney's proof is non-effective in the sense that it is based on classical logic and on the non-computational principle WKL . The result of our analysis provides the first effective uniform modulus of uniqueness . Moreover, the extracted modulus has the optimal ε-dependency as follows from Kroó 331). The paper also describes how the uniform modulus of uniqueness can be used to compute the best L1-approximations of a fixed fC[0,1] with arbitrary precision. The second author uses this result to give a complexity upper bound on the computation of the best L1-approximation in Oliva 66–77). (shrink)

The present article provides an analysis of the existing proof systems for dynamic epistemic logic from the viewpoint of proof-theoretic semantics. Dynamic epistemic logic is one of the best known members of a family of logical systems that have been successfully applied to diverse scientific disciplines, but the proof-theoretic treatment of which presents many difficulties. After an illustration of the proof-theoretic semantic principles most relevant to the treatment of logical connectives, we turn to illustrating the main (...) features of display calculi, a proof-theoretic paradigm that has been successfully employed to give a proof-theoretic semantic account of modal and substructural logics. Then, we review some of the most significant proposals of proof systems for dynamic epistemic logics, and we critically reflect on them in the light of the previously introduced proof-theoretic semantic principles. The contributions of the present article include a generalization of Belnap's cut-elimination metatheorem for display calculi, and a revised version of the display-style calculus D.EAK. We verify that the revised version satisfies the previously mentioned proof-theoretic semantic principles, and show that it enjoys cut-elimination as a consequence of the generalized metatheorem. (shrink)

In this paper I shall present a method for proving determinacy from large cardinals which, in many cases, seems to yield optimal results. One of the main applications extends theorems of Martin, Steel and Woodin about determinacy within the projective hierarchy. The method can also be used to give a new proof of Woodin's theorem about determinacy in L.The reason we look for optimal determinacy proofs is not only vanity. Such proofs serve to tighten the connection between large cardinals (...) and descriptive set theory, letting us bring our knowledge of one subject to bear on the other, and thus increasing our understanding of both. A classic example of this is the Harrington-Martin proof that -determinacy implies -determinacy. This is an example of a transfer theorem, which assumes a certain determinacy hypothesis and proves a stronger one. While the statement of the theorem makes no mention of large cardinals, its proof goes through 0#, first proving that-determinacy ⇒ 0# exists,and then that0# exists ⇒ -determinacyMore recent examples of the connection between large cardinals and descriptive set theory include Steel's proof thatADL ⇒ HODL ⊨ GCH,see [9], and several results of Woodin about models of AD+, a strengthening of the axiom of determinacy AD which Woodin has introduced. These proofs not only use large cardinals, but also reveal a deep, structural connection between descriptive set theoretic notions and notions related to large cardinals. (shrink)

In this study, the author compares several proofs of the compactness theorem for propositional logic with countably many atomic sentences. He thereby takes some steps towards a systematic philosophical study of the compactness theorem. He also presents some data and morals for the theory of mathematical explanation. [The author is not responsible for the horrific mathematical typo in the second sentence.].

We present novel proof systems for various FDE-based modal logics. Among the systems considered are a number of Belnapian modal logics introduced in Odintsov & Wansing and Odintsov & Wansing, as well as the modal logic KN4 with strong implication introduced in Goble. In particular, we provide a Hilbert-style axiom system for the logic $BK^{\square - } $ and characterize the logic BK as an axiomatic extension of the system $BK^{FS} $. For KN4 we provide both an FDE-style axiom (...) system and a decidable sequent calculus for which a contraction elimination and a cut elimination result are shown. (shrink)

A general method for generating contraction- and cut-free sequent calculi for a large family of normal modal logics is presented. The method covers all modal logics characterized by Kripke frames determined by universal or geometric properties and it can be extended to treat also Gödel-Löb provability logic. The calculi provide direct decision methods through terminating proof search. Syntactic proofs of modal undefinability results are obtained in the form of conservativity theorems.

In the present paper, the Fregean conception of proof-theoretic semantics that I developed elsewhere will be revised so as to better reflect the different roles played by open and closed derivations. I will argue that such a conception can deliver a semantic analysis of languages containing paradoxical expressions provided some of its basic tenets are liberalized. In particular, the notion of function underlying the Brouwer–Heyting–Kolmogorov explanation of implication should be understood as admitting functions to be partial. As argued in (...) previous work, the correctness of an inference rule should not be defined in terms of transmission of provability, but rather should be grounded on weaker principles, which I show that are motivated by consideration about the content of the inversion principle. In the conclusion, I briefly address the issue of compositionality, arguing that the violation of compositionality induced by paradoxes are no worse than others that are regarded, at least by Dummett, as wholly unproblematic. (shrink)

The axiomatic presentation of modal systems and the standard formulations of natural deduction and sequent calculus for modal logic are reviewed, together with the difficulties that emerge with these approaches. Generalizations of standard proof systems are then presented. These include, among others, display calculi, hypersequents, and labelled systems, with the latter surveyed from a closer perspective.

The article presents a full proof‐theoretic semantics for natural deduction based on an extended inversion principle: the elimination rule for an operator q may invert the introduction rule for q, but also vice versa, the introduction rule for a connective q may invert the elimination rule for q. Such an inversion—extending Prawitz' concept of inversion—gives the following theorem: Inversion for two rules of operator q (intro rule, elim rule) exists iff a reduction of a maximum formula for q exists. (...) The inversion theorem is specified to two logics, Lambek calculus (LC) and intuitionistic linear logic (ILL), with four propositional connectives: two multiplicatives (implication and conjunction) and two additives (conjunction and disjunction), with two quantifiers and two modals. LC is defined by using elimination rules by composition. ILL is defined by using usual general elimination rules. Elimination rules by composition are an exciting alternative to general elimination rules; in some cases, they do not need permutations. (shrink)

Mathematicians do not claim to know a proposition unless they think they possess a proof of it. For all their confidence in the truth of a proposition with weighty non-deductive support, they maintain that, strictly speaking, the proposition remains unknown until such time as someone has proved it. This article challenges this conception of knowledge, which is quasi-universal within mathematics. We present four arguments to the effect that non-deductive evidence can yield knowledge of a mathematical proposition. We also show (...) that some of what mathematicians take to be deductive knowledge is in fact non-deductive. 1 Introduction2 Why It Might Matter3 Two Further Examples and Preliminaries4 An Exclusive Epistemic Virtue of Proof?5 Analyses of Knowledge6 The Inductive Basis of Deduction7 Physical to Mathematical Linkages8 Conclusion. (shrink)

The present paper aims to show that the reconstruction of the formal framework of the proofs in Pr. An. 1.15, as proposed by Malink and Rosen 2013 (‘Proof by Assumption of the Possible in Prior Analytics 1.15’, Mind, 122, 953-85) is due to affront a double impasse. Malink and Rosen argue convincingly that Aristotle operates with two different modal frameworks, one as found in the system of modal logic presented in Prior Analytics 1.3 and 8-22, and one occurring in (...) many of Aristotle’s works, such as the Physics, De Caelo and the Metaphysics. However, they misconstrue the latter framework. More precisely, they misconstrue the domain of significance of what they call the ‘Principle of Necessitation’. As a consequence, bringing the two frameworks into one results into a contradictory modal logic. On the other hand, if the Principle of Necessitation is rectified, the proofs put forward by Malink and Rosen in the same paper are no longer available. (shrink)

In this study, several proofs of the compactness theorem for propositional logic with countably many atomic sentences are compared. Thereby some steps are taken towards a systematic philosophical study of the compactness theorem. In addition, some related data and morals for the theory of mathematical explanation are presented.

This thesis is about the nature of proofs in mathematics as it is practiced, contrasting the informal proofs found in practice with formal proofs in formal systems. In the first chapter I present a new argument against the Formalist-Reductionist view that informal proofs are justified as rigorous and correct by corresponding to formal counterparts. The second chapter builds on this to reject arguments from Gödel's paradox and incompleteness theorems to the claim that mathematics is inherently inconsistent, basing my objections on (...) the complexities of the process of formalisation. Chapter 3 looks into the relationship between proofs and the development of the mathematical concepts that feature in them. I deploy Waismann's notion of open texture in the case of mathematical concepts, and discuss both Lakatos and Kneebone's dialectical philosophies of mathematics. I then argue that we can apply work from conceptual engineering to the relationship between formal and informal mathematics. The fourth chapter argues for the importance of mathematical knowledge-how and emphasises the primary role of the activity of proving in securing mathematical knowledge. In the final chapter I develop an account of mathematical knowledge based on virtue epistemology, which I argue provides a better view of proofs and mathematical rigour. (shrink)

In proof-theoretic semantics, model-theoretic validity is replaced by proof-theoretic validity. Validity of formulae is defined inductively from a base giving the validity of atoms using inductive clauses derived from proof-theoretic rules. A key aim is to show completeness of the proof rules without any requirement for formal models. Establishing this for propositional intuitionistic logic raises some technical and conceptual issues. We relate Sandqvist’s (complete) base-extension semantics of intuitionistic propositional logic to categorical proof theory in presheaves, (...) reconstructing categorically the soundness and completeness arguments, thereby demonstrating the naturality of Sandqvist’s constructions. This naturality includes Sandqvist’s treatment of disjunction that is based on its second-order or elimination-rule presentation. These constructions embody not just validity, but certain forms of objects of justifications. This analysis is taken a step further by showing that from the perspective of validity, Sandqvist’s semantics can also be viewed as the natural disjunction in a category of sheaves. (shrink)

This paper presents proof that Buss's S22 can prove the consistency of a fragment of Cook and Urquhart's PV from which induction has been removed but substitution has been retained. This result improves Beckmann's result, which proves the consistency of such a system without substitution in bounded arithmetic S12. Our proof relies on the notion of "computation" of the terms of PV. In our work, we first prove that, in the system under consideration, if an equation is proved (...) and either its left- or right-hand side is computed, then there is a corresponding computation for its right- or left-hand side, respectively. By carefully computing the bound of the size of the computation, the proof of this theorem inside a bounded arithmetic is obtained, from which the consistency of the system is readily proven. This result apparently implies the separation of bounded arithmetic because Buss and Ignjatović stated that it is not possible to prove the consistency of a fragment of PV without induction but with substitution in Buss's S12. However, their proof actually shows that it is not possible to prove the consistency of the system, which is obtained by the addition of propositional logic and other axioms to a system such as ours. On the other hand, the system that we have considered is strictly equational, which is a property on which our proof relies. (shrink)

Classical proof forests are a proof formalism for first-order classical logic based on Herbrand’s Theorem and backtracking games in the style of Coquand. First described by Miller in a cut-free setting as an economical representation of first-order and higher-order classical proof, defining features of the forests are a strict focus on witnessing terms for quantifiers and the absence of inessential structure, or ‘bureaucracy’.This paper presents classical proof forests as a graphical proof formalism and investigates the (...) possibility of composing forests by cut-elimination. Cut-reduction steps take the form of a local rewrite relation that arises from the structure of the forests in a natural way. Yet reductions, which are significantly different from those of the sequent calculus, are combinatorially intricate and do not exclude the possibility of infinite reduction traces, of which an example is given.Cut-elimination, in the form of a weak normalisation theorem, is obtained using a modified version of the rewrite relation inspired by the game-theoretic interpretation of the forests. It is conjectured that the modified reduction relation is, in fact, strongly normalising. (shrink)

A famous theorem by van der Waerden states the following: Given any finite coloring of the integers, one color contains arbitrarily long arithmetic progressions. Equivalently, for every q,k, there is an N = N(q,k) such that for every q-coloring of an interval of length N one color contains a progression of length k. An obvious question is what is the growth rate of N = N(q,k). Some proofs, like van der Waerden's combinatorial argument, answer this question directly, while the topological (...) proof by Furstenberg and Weiss does not. We present an analysis of (Girard's variant of) Furstenberg and Weiss's proof based on monotone functional interpretation, both yielding bounds and providing a general illustration of proof mining in topological dynamics. The bounds do not improve previous results by Girard, but only—as is also revealed by the analysis—because the combinatorial proof and the topological dynamics proof in principle are identical. (shrink)

We present a general method for inserting proofs in Frege systems for classical logic that produces systems that can internalize their own proofs.