“Now, in calm weather, to swim in the open ocean is as easy to the practised swimmer as to ride in a spring-carriage ashore. But the awful lonesomeness is intolerable. The intense concentration of self in the middle of such a heartless immensity, my God! who can tell it? Mark, how when sailors in a dead calm bathe in the open sea—mark how closely they hug their ship and only coast along her sides.” (Herman Melville, Moby Dick, Chapter 94).

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

Philosophers who regard some mathematical proofs as explaining why theorems hold, and others as merely proving that they do hold, disagree sharply about the explanatory value of proofs by mathematical induction. I offer an argument that aims to resolve this conflict of intuitions without making any controversial presuppositions about what mathematical explanations would be.

This text is an outgrowth of notes prepared by J. Y. Girard for a course at the University of Paris VII. It deals with the mathematical background of the application to computer science of aspects of logic (namely the correspondence between proposition & types). Combined with the conceptual perspectives of Girard's ideas, this sheds light on both the traditional logic material & its prospective applications to computer science. The book covers a very active & exciting research area, & it will (...) be essential reading for all those working in logic & computer science. (shrink)

In this paper I show that proofs by contradiction were a serious problem in seventeenth century mathematics and philosophy. Their status was put into question and positive mathematical developments emerged from such reflections. I analyse how mathematics, logic, and epistemology are intertwined in the issue at hand. The mathematical part describes Cavalieri's and Guldin's mathematical programmes of providing a development of parts of geometry free of proofs by contradiction. The logical part shows how the traditional Aristotelean doctrine that (...) perfect demonstrations are causal demonstrations influenced the reflection on proofs by contradiction. The main protagonist of this part is Wallis. Finally, I analyse some epistemological developments arising from the Cartesian tradition. In particular, I look at Arnauld's programme of providing an epistemologically motivated reformulation of Geometry free of proofs by contradiction. The conclusion explains in which sense these epistemological reflections can be compared with those informing contemporary intuitionism. (shrink)

Propositional proof complexity is the study of the sizes of propositional proofs, and more generally, the resources necessary to certify propositional tautologies. Questions about proof sizes have connections with computational complexity, theories of arithmetic, and satisfiability algorithms. This is article includes a broad survey of the field, and a technical exposition of some recently developed techniques for proving lower bounds on proof sizes.

Cook and Reckhow defined a propositional formulation of the pigeonhole principle. This paper shows that there are Frege proofs of this propositional pigeonhole principle of polynomial size. This together with a result of Haken gives another proof of Urquhart's theorem that Frege systems have an exponential speedup over resolution. We also discuss connections to provability in theories of bounded arithmetic.

This volume is dedicated to Prof. Dag Prawitz and his outstanding contributions to philosophical and mathematical logic. Prawitz's eminent contributions to structural proof theory, or general proof theory, as he calls it, and inference-based meaning theories have been extremely influential in the development of modern proof theory and anti-realistic semantics. In particular, Prawitz is the main author on natural deduction in addition to Gerhard Gentzen, who defined natural deduction in his PhD thesis published in 1934. The book opens with an (...) introductory paper that surveys Prawitz's numerous contributions to proof theory and proof-theoretic semantics and puts his work into a somewhat broader perspective, both historically and systematically. Chapters include either in-depth studies of certain aspects of Dag Prawitz's work or address open research problems that are concerned with core issues in structural proof theory and range from philosophical essays to papers of a mathematical nature. Investigations into the necessity of thought and the theory of grounds and computational justifications as well as an examination of Prawitz's conception of the validity of inferences in the light of three “dogmas of proof-theoretic semantics” are included. More formal papers deal with the constructive behaviour of fragments of classical logic and fragments of the modal logic S4 among other topics. In addition, there are chapters about inversion principles, normalization of proofs, and the notion of proof-theoretic harmony and other areas of a more mathematical persuasion. Dag Prawitz also writes a chapter in which he explains his current views on the epistemic dimension of proofs and addresses the question why some inferences succeed in conferring evidence on their conclusions when applied to premises for which one already possesses evidence. (shrink)

We give examples of calculi that extend Gentzen’s sequent calculusLKby unsound quantifier inferences in such a way that derivations lead only to true sequents, and proofs therein are nonelementarily shorter thanLK-proofs.

We present an approach in which ancient Greek mathematical proofs by Hippocrates of Chios and Euclid are addressed as a form of (guided) intentional reasoning. Schematically, in a proof, we start with a sentence that works as a premise; this sentence is followed by another, the conclusion of what we might take to be an inferential step. That goes on until the last conclusion is reached. Guided by the text, we go through small inferential steps; in each one, we (...) go through an autonomous reasoning process linking the premise to the conclusion. The reasoning process is accompanied by a metareasoning process. Metareasoning gives rise to a feeling-knowing of correctness. In each step/cycle of the proof, we have a feeling-knowing of correctness. Overall, we reach a feeling of correctness for the whole proof. We suggest that this approach allows us to address the issues of how a proof functions, for us, as an enabler to ascertain the correctness of its argument and how we ascertain this correctness. (shrink)

Some thirty years ago, two proposals were made concerning criteria for identity of proofs. Prawitz proposed to analyze identity of proofs in terms of the equivalence relation based on reduction to normal form in natural deduction. Lambek worked on a normalization proposal analogous to Prawitz's, based on reduction to cut-free form in sequent systems, but he also suggested understanding identity of proofs in terms of an equivalence relation based on generality, two derivations having the same generality if (...) after generalizing maximally the rules involved in them they yield the same premises and conclusions up to a renaming of variables. These two proposals proved to be extensionally equivalent only for limited fragments of logic. The normalization proposal stands behind very successful applications of the typed lambda calculus and of category theory in the proof theory of intuitionistic logic. In classical logic, however, it did not fare well. The generality proposal was rather neglected in logic, though related matters were much studied in pure category theory in connection with coherence problems, and there are also links to low-dimensional topology and linear algebra. This proposal seems more promising than the other one for the general proof theory of classical logic. (shrink)

A new semantics is presented for the logic of proofs (LP), [1, 2], based on the intuition that it is a logic of explicit knowledge. This semantics is used to give new proofs of several basic results concerning LP. In particular, the realization of S4 into LP is established in a way that carefully examines and explicates the role of the + operator. Finally connections are made with the conventional approach, via soundness and completeness results.

This book presents reverse mathematics to a general mathematical audience for the first time. Reverse mathematics is a new field that answers some old questions. In the two thousand years that mathematicians have been deriving theorems from axioms, it has often been asked: which axioms are needed to prove a given theorem? Only in the last two hundred years have some of these questions been answered, and only in the last forty years has a systematic approach been developed. In Reverse (...) Mathematics, John Stillwell gives a representative view of this field, emphasizing basic analysis--finding the "right axioms" to prove fundamental theorems--and giving a novel approach to logic. Stillwell introduces reverse mathematics historically, describing the two developments that made reverse mathematics possible, both involving the idea of arithmetization. The first was the nineteenth-century project of arithmetizing analysis, which aimed to define all concepts of analysis in terms of natural numbers and sets of natural numbers. The second was the twentieth-century arithmetization of logic and computation. Thus arithmetic in some sense underlies analysis, logic, and computation. Reverse mathematics exploits this insight by viewing analysis as arithmetic extended by axioms about the existence of infinite sets. Remarkably, only a small number of axioms are needed for reverse mathematics, and, for each basic theorem of analysis, Stillwell finds the "right axiom" to prove it. By using a minimum of mathematical logic in a well-motivated way, Reverse Mathematics will engage advanced undergraduates and all mathematicians interested in the foundations of mathematics. (shrink)

Proofs are central, and unique, to mathematics. They establish the truth of theorems and provide us with the most secure knowledge we can possess. It is thus perhaps unsurprising that philosophers once thought that the only value proofs have lies in establishing the truth of theorems. However, such a view is inconsistent with mathematical practice. If a proof’s only value is to show a theorem is true, then mathematicians would have no reason to reprove the same theorem in (...) different ways, yet this is a practice they frequently engage in. This suggests that proofs can have a wide variety of values. My purpose in this chapter is to provide a survey of some of them. I will discuss how proofs can have practical value, for example, by helping mathematicians to make new discoveries or learn new mathematical tools, and how they can have abstract value, for example, by being beautiful or explanatory. I will also explore the relationships between different proof values. (shrink)

Partial consistency statements can be expressed as polynomial-size propositional formulas. Frege proof systems have polynomial-size partial self-consistency proofs. Frege proof systems have polynomial-size proofs of partial consistency of extended Frege proof systems if and only if Frege proof systems polynomially simulate extended Frege proof systems. We give a new proof of Reckhow's theorem that any two Frege proof systems p-simulate each other. The proofs depend on polynomial size propositional formulas defining the truth of propositional formulas. These are (...) already known to exist since the Boolean formula value problem is in alternating logarithmic time; this paper presents a proof of this fact based on a construction which is somewhat simpler than the prior proofs of Buss and of Buss-Cook- Gupta-Ramachandran. (shrink)

We present a sequent calculus for the Grzegorczyk modal logic$\mathsf {Grz}$allowing cyclic and other non-well-founded proofs and obtain the cut-elimination theorem for it by constructing a continuous cut-elimination mapping acting on these proofs. As an application, we establish the Lyndon interpolation property for the logic$\mathsf {Grz}$proof-theoretically.

The literature on mathematical explanation contains numerous examples of explanatory, and not so explanatory proofs. In this paper we report results of an empirical study aimed at investigating mathematicians’ notion of explanatoriness, and its relationship to accounts of mathematical explanation. Using a Comparative Judgement approach, we asked 38 mathematicians to assess the explanatory value of several proofs of the same proposition. We found an extremely high level of agreement among mathematicians, and some inconsistencies between their assessments and claims (...) in the literature regarding the explanatoriness of certain types of proofs. (shrink)

One of the central aims of the philosophical analysis of mathematical explanation is to determine how one can distinguish explanatory proofs from non-explanatory proofs. In this paper, I take a closer look at the current status of the debate, and what the challenges for the philosophical analysis of explanatory proofs are. In order to provide an answer to these challenges, I suggest we start from analysing the concept understanding. More precisely, I will defend four claims: understanding is (...) a condition for explanation, unificatory understanding is a type of explanatory understanding, unificatory understanding is valuable in mathematics, and mathematical proofs can contribute to unificatory understanding. As a result, in a context where the epistemic aim is to unify mathematical results, I argue it is fruitful to make a distinction between proofs based on their explanatory value. (shrink)

We give proofs of the effective monotone interpolation property for the system of modal logic K, and others, and the system IL of intuitionistic propositional logic. Hence we obtain exponential lower bounds on the number of proof-lines in those systems. The main results have been given in [P. Hrubeš, Lower bounds for modal logics, Journal of Symbolic Logic 72 941–958; P. Hrubeš, A lower bound for intuitionistic logic, Annals of Pure and Applied Logic 146 72–90]; here, we give considerably (...) simplified proofs, as well as some generalisations. (shrink)

Treatise on epistemology, presenting the Dvaita school in Hindu philosophy.

This note exploits back-and-forth characteristics to construct, using a single method, short proofs for ten classics of first-order and modal logic: interpolation theorems, preservation theorems, and Lindström's theorem.

Igor Agostini, La démonstration de l’existence de Dieu. Les conclusions des cinq voies de saint Thomas d’Aquin et la preuve a priori dans le thomisme du XVIIe siècle, The Age of Descartes / Descart...

In this paper individual proofs are integrated into provability logic. Systems of axioms for a logic with operators “A is provable” and “p is a proof of A” are introduced, provided with Kripke semantics and decision procedure. Completeness theorems with respect to the arithmetical interpretation are proved.

A structure which generalizes formulas by including substitution terms is used to represent proofs in classical logic. These structures, called expansion trees, can be most easily understood as describing a tautologous substitution instance of a theorem. They also provide a computationally useful representation of classical proofs as first-class values. As values they are compact and can easily be manipulated and transformed. For example, we present an explicit transformations between expansion tree proofs and cut-free sequential proofs. A (...) theorem prover which represents proofs using expansion trees can use this transformation to present its proofs in more human-readable form. Also a very simple computation on expansion trees can transform them into Craig-style linear reasoning and into interpolants when they exist. We have chosen a sublogic of the Simple Theory of Types for our classical logic because it elegantly represents substitutions at all finite types through the use of the typed -calculus. Since all the proof-theoretic results we shall study depend heavily on properties of substitutions, using this logic has allowed us to strengthen and extend prior results: we are able to prove a strengthen form of the firstorder interpolation theorem as well as provide a correct description of Skolem functions and the Herbrand Universe. The latter are not straightforward generalization of their first-order definitions. (shrink)

A common description of a mathematical proof is as a logically structured sequence of assertions, beginning from accepted premises and proceeding by standard inference rules to a conclusion. Does this description match the language of proofs as mathematicians write them in their research articles? In this chapter, we use methods from corpus linguistics to look at the prevalence of imperatives and instructions in mathematical preprints from the arXiv repository. We find thirteen verbs that are used most often to form (...) imperatives in proofs, and that these show up significantly more often within proofs than in the surrounding mathematical writing. We also show that there are many more verbs used to form a diverse selection of instructions in proofs. These findings are at odds with the view of proofs as sequences of assertions. Instead, we argue in favour of the recipe model of proofs: that proofs are like recipes, giving instructions for mathematical actions to be carried out. (shrink)