Over the past half-century, formal, machine-executable proofs have been developed for an impressive range of mathematical theorems. Formalists argue that such proofs should be seen as providing the fully worked out proofs of which mathematicians’ proofs are sketches. Nonformalists argue that this conception of the relationship of formal to informal proofs cannot explain the fact that formal proofs lack essential virtues enjoyed by mathematicians’ proofs, the fact, for example, that (...) class='Hi'>formal proofs are not convincing and lack the explanatory power of their informal counterparts. Formal proofs do not yield mathematical insight or understanding, and they are not fruitful in the way that informal proofs can be, for instance, in suggesting novel approaches to old problems. And yet, there is a clear sense in which the formalist is right: Formal proofs do seem to make explicit what is otherwise taken for granted in the mathematician’s reasoning. Very recent work uncovers the source of the dilemma by showing that rigor does not entail formalism insofar as rigor, unlike formalism, is compatible with contentfulness. Mathematical proofs, were they to be recast in a Leibnizian language, at once a characteristica and a calculus, would be, or could be made to be, completely gap-free and hence machine checkable. Because as so recast they would be grounded in mathematical ideas, they would not be machine executable. It is on just this basis that a compelling account can be given of the fact that formal proofs are mostly irrelevant to mathematicians in their practice. (shrink)

I develop the decision-theoretic approach to quantum probability, originally proposed by David Deutsch, into a mathematically rigorous proof of the Born rule in (Everett-interpreted) quantum mechanics. I sketch the argument informally, then prove it formally, and lastly consider a number of proposed ``counter-examples'' to show exactly which premises of the argument they violate. (This is a preliminary version of a chapter to appear --- under the title ``How to prove the Born Rule'' --- in Saunders, Barrett, Kent and Wallace, "Many (...) worlds? Everett, quantum theory and reality", forthcoming from Oxford University Press.). (shrink)

Purity is known as an ideal of proof that restricts a proof to notions belonging to the ‘content’ of the theorem. In this paper, our main interest is to develop a conception of purity for formal (natural deduction) proofs. We develop two new notions of purity: one based on an ontological notion of the content of a theorem, and one based on the notions of surrogate ontological content and structural content. From there, we characterize which (classical) first-order natural (...) deduction proofs of a mathematical theorem are pure. Formal proofs that refer to the ontological content of a theorem will be called ‘fully ontologically pure’. Formal proofs that refer to a surrogate ontological content of a theorem will be called ‘secondarily ontologically pure’, because they preserve the structural content of a theorem. We will use interpretations between theories to develop a proof-theoretic criterion that guarantees secondary ontological purity for formal proofs. (shrink)

When modeling informal proofs like that of Euclid’s Elements using a sound logical system, we go from proofs seen as somewhat unrigorous – even having gaps to be filled – to rigorous proofs. However, metalogic grounds the soundness of our logical system, and proofs in metalogic are not like formal proofs and look suspiciously like the informal proofs. This brings about what I am calling here the groundedness problem: how can we decide with (...) certainty that our metalogical proofs are rigorous and sustain our logical system? In this paper, I will expose this problem. I will not try to solve it here. (shrink)

The article presents a formalization of Thomas Aquinas proof for the indestructibility of the human soul. The author of the formalization—the first of its kind in the history of philosophy—is Father Joseph Maria Bocheński. The presentation involves no more than updating the logical symbolism used and accompanies the logical formulae with ordinary language paraphrases in order to ease the reader’s understanding of the formulae. “The fundamental idea of the Thomist proof is of utmost simplicity: things which are destructible are destructible (...) either per se or per accidens; but the human soul is destructible neither per se nor per accidens: therefore the human soul is not destructible”. Bochenski’s words required him to devote considerable effort for the sake of precision of the symbolic language that would be maximally adequate to Thomas’ discourse. Moreover, I have thought it necessary to provide an ample commentary to the traditional and contemporary semantical presuppositions of Aquinas philosophical anthropology in light of Bocheński’s interpretation thereof. (shrink)

Wilfred Sieg. “Church's Thesis”, “Consistency”, “Formalization”, “Proof Theory”: Dictionary Entries.

Type theory is a fast-evolving field at the crossroads of logic, computer science and mathematics. This gentle step-by-step introduction is ideal for graduate students and researchers who need to understand the ins and outs of the mathematical machinery, the role of logical rules therein, the essential contribution of definitions and the decisive nature of well-structured proofs. The authors begin with untyped lambda calculus and proceed to several fundamental type systems culminating in the well-known and powerful Calculus of Constructions. The (...) book also covers the essence of proof checking and proof development, and the use of dependent type theory to formalize mathematics. The only prerequisites are a good knowledge of undergraduate algebra and analysis. Carefully chosen examples illustrate the theory throughout. Each chapter ends with a summary of the content, some historical context, suggestions for further reading and a selection of exercises to help readers familiarize themselves with the material. (shrink)

What seem to be Kurt Gödel’s first notes on logic, an exercise notebook of 84 pages, contains formal proofs in higher-order arithmetic and set theory. The choice of these topics is clearly suggested by their inclusion in Hilbert and Ackermann’s logic book of 1928, the Grundzüge der theoretischen Logik. Such proofs are notoriously hard to construct within axiomatic logic. Gödel takes without further ado into use a linear system of natural deduction for the full language of higher-order (...) logic, with formal derivations closer to one hundred steps in length and up to four nested temporary assumptions with their scope indicated by vertical intermittent lines. (shrink)

Derivationists, those wishing to explain the correctness and rigour of informal proofs in terms of associated formal proofs, are generally held to be supported by the success of the project of translating informal proofs into computer-checkable formal counterparts. I argue, however, that this project is a false friend for the derivationists because there are too many different associated formal proofs for each informal proof, leading to a serious worry of overgeneration. I press this (...) worry primarily against Azzouni's derivation-indicator account, but conclude that overgeneration is a major obstacle to a successful account of informal proofs in this direction. (shrink)

Let ℸ be the set of Gödel numbers Gn of function symbols f such that PRA ⊢ and let γ be the function such that equation imageWe prove: The r. e. set ℸ is m-complete; the function γ is not primitive recursive in any class of functions {f1, f2, ⃛} so long as each fi has a recursive upper bound. This implies that γ is not primitive recursive in ℸ although it is recursive in ℸ.

This paper studies internal (or intra-)mathematical explanations, namely those proofs of mathematical theorems that seem to explain the theorem they prove. The goal of the paper is a rigorous analysis of these explanations. This will be done in two steps. First, we will show how to move from informal proofs of mathematical theorems to a formal presentation that involves proof trees, together with a decomposition of their elements; secondly we will show that those mathematical proofs that (...) are regarded as having explanatory power all display an increase of conceptual complexity from the assumptions to the conclusion. (shrink)

Not focusing on the history of classical logic, this book provides discussions and quotes central passages on its origins and development, namely from a philosophical perspective. Not being a book in mathematical logic, it takes formal logic from an essentially mathematical perspective. Biased towards a computational approach, with SAT and VAL as its backbone, this is an introduction to logic that covers essential aspects of the three branches of logic, to wit, philosophical, mathematical, and computational.

This paper attempts to look at the contemporary mathematical practice through the lenses of the distributed cognition approach. The ubiquitous use of personal computers and the internet as a key attribute of the digital society is interpreted here as a means to achieve a more effective distribution of the human cognitive activity. The major challenge that determines the transformation of mathematical practice is identified as ‘the problem of complexity’. The computer-assisted complete formalization of mathematical proofs as a current tendency (...) is viewed as one of the strands along which the mathematical community responds to the challenge. It is shown that this tendency gives live to the project calling to revisit and rebuild the very foundations of mathematics to secure more effective communication and thus guarantee the reliability of contemporary mathematics. (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)

Proof requires a dialogue between agents to clarify obscure inference steps, fill gaps, or reveal implicit assumptions in a purported proof. Hence, argumentation is an integral component of the discovery process for mathematical proofs. This work presents how argumentation theories can be applied to describe specific informal features in the development of proof-events. The concept of proof-event was coined by Goguen who described mathematical proof as a public social event that takes place in space and time. This new meta-methodological (...) concept is designed to cover not only “traditional” formal proofs but all kinds of proofs and inference steps, including incomplete or purported proofs. Our approach attempts to make proof-events more comprehensive to express the complete trajectory of a mathematical proof-event until the ultimate validation of the proving outcome. Thus, we advance an extended version of proof-event calculus which is built on argumentation theories designed to capture the internal and external structure of collaborative mathematical practice and highlight the relationship between proof, human reasoning, and cognitive processes. In addition, another area in which argumentation can make a significant contribution is dealing with the defeasible knowledge of the Web which is a product of its open and ubiquitous nature. This approach seems to be sufficient for the presentation of Web-based proving processes as manifested in the case of the Mini-Polymath 4 project. (shrink)

Proof and Disproof in Formal Logic is a lively and entertaining introduction to formal logic providing an excellent insight into how a simple logic works. Formal logic allows you to check a logical claim without considering what the claim means. This highly abstracted idea is an essential and practical part of computer science. The idea of a formal system-a collection of rules and axioms, which define a universe of logical proofs-is what gives us programming languages (...) and modern-day programming. This book concentrates on using logic as a tool: making and using formal proofs and disproofs of particular logical claims. The logic it uses-natural deduction-is very small and very simple; working with it helps you see how large mathematical universes can be built on small foundations. The book is divided into four parts: Part I "Basics" gives an introduction to formal logic with a short history of logic and explanations of some technical words. Part II "Formal Syntactic Proof" show you how to do calculations in a formal system where you are guided by shapes and never need to think about meaning. Your experiments are aided by Jape, which can operate as both inquisitor and oracle. Part III "Formal Semantic Disproof" shows you how to construct mathematical counterexamples to shoe that proof is impossible. Jape can check the counterexamples you build. Part IV " Program Specification and Proof" describes how to apply your logical understanding to a real computer science problem, the accurate description and verification of programs. Jape helps, as far as arithmetic allows. Aimed at undergraduates and graduates in computer science, logic, mathematics and philosophy, the text includes reference to and exercises based on the computer software package Jape, an interactive teaching and research tool designed and hosted by the author that is freely available on the web. (shrink)

The prime number theorem, established by Hadamard and de la Vallée Poussin independently in 1896, asserts that the density of primes in the positive integers is asymptotic to 1/ln x. Whereas their proofs made serious use of the methods of complex analysis, elementary proofs were provided by Selberg and Erdos in 1948. We describe a formally verified version of Selberg's proof, obtained using the Isabelle proof assistant.

Many mathematicians and philosophers of mathematics believe some proofs contain elements extraneous to what is being proved. In this paper I discuss extraneousness generally, and then consider a specific proposal for measuring extraneousness syntactically. This specific proposal uses Gentzen's cut-elimination theorem. I argue that the proposal fails, and that we should be skeptical about the usefulness of syntactic extraneousness measures.

The mathematical proof is the most important form of justification in mathematics. It is not, however, the only kind of justification for mathematical propositions. The existence of other forms, some of very significant strength, places a question mark over the prominence given to proof within mathematics. This collection of essays, by leading figures working within the philosophy of mathematics, is a response to the challenge of understanding the nature and role of the proof.

We propose a novel, ontological approach to studying mathematical propositions and proofs. By “ontological approach” we refer to the study of the categories of beings or concepts that, in their practice, mathematicians isolate as fruitful for the advancement of their scientific activity (like discovering and proving theorems, formulating conjectures, and providing explanations). We do so by developing what we call a “formal ontology” of proofs using semantic modeling tools (like RDF and OWL) developed by the computer science (...) community. In this article, (i) we describe this new approach and, (ii) to provide an example, we apply it to the problem of the identity of proofs. We also describe open issues and further applications of this approach (for example, the study of purity of methods). We lay some foundations to investigate rigorously and at large scale intellectual moves and attitudes that underpin the advancement of mathematics through cognitive means (carving out investigationally valuable concepts and techniques) and social means (like communication, collaboration, revision, and criticism of specific categories, inferential patterns, and levels of analysis). Our approach complements other types of analysis of proofs such as reconstruction in a deductive system and examination through a proof-assistant. (shrink)

In this section, we apply the notions obtained above to a famous historical example of a false proof. Our goal is to demonstrate that this proof shows a sufficient degree of distinctiveness for a formalization in a Naproche-like system and hence that automatic checking could indeed have contributed in this case to the development of mathematics. This example further demonstrates that even incomplete distinctivication can be sufficient for automatic checking and that actual mistakes may occur already in the margin between (...) the degree of distinctiveness necessary for formalization and complete distinctiveness. (shrink)

Within a weak subsystem of second-order arithmetic , that is -conservative over , we reformulate Kreisel's proof of the Second Incompleteness Theorem and Boolos' proof of the First Incompleteness Theorem.

Proofs 101: An Introduction to Formal Mathematics serves as an introduction to proofs for mathematics majors who have completed the calculus sequence (at least Calculus I and II) and Linear Algebra. It prepares students for the proofs they will need to analyse and write, the axiomatic nature of mathematics, and the rigors of upper-level mathematics courses. Basic number theory, relations, functions, cardinality, and set theory will provide the material for the proofs and lay the foundation (...) for a deeper understanding of mathematics, which students will need to carry with them throughout their future studies Features Designed to be teachable across a single semester Suitable as an undergraduate textbook for Introduction to Proofs or Transition to Advanced Mathematics courses A balanced variety of easy, moderate, and difficult exercises. (shrink)

Kant discovered a philosophical problem with mathematical proof. Despite being a priori , its methodology involves more than analytic truth. But what else is involved? This problem is widely taken to have been solved by Frege’s extension of logic beyond its restricted (and largely Aristotelian) form. Nevertheless, a successor problem remains: both traditional and contemporary (classical) mathematical proofs, although conforming to the norms of contemporary (classical) logic, never were, and still aren’t, executed by mathematicians in a way that transparently (...) reveals why these proofs—written in the vernacular to this very day—succeed in conforming to those norms. (shrink)

The heuristics and strategies presented in Lakatos' Proofs and Refutations are well-known. However they hardly present the whole story as many authors have shown. In this paper a recent, rather spectacular, event in the history of mathematics is examined to gather evidence for two new strategies. The first heuristic concerns the expectations mathematicians have that a statement will be proved using given methods. The second heuristic tries to make sense of the mathematicians' notion of the quality of a proof.

This paper explores the relationship between informal reasoning, creativity in mathematics, and problem solving. It underscores the importance of environments that promote interaction, hypothesis generation, examination, refutation, derivation of new solutions, drawing conclusions, and reasoning with others, as key factors in enhancing mathematical creativity. Drawing on argumentation logic, the paper proposes a novel approach to uncover specific characteristics in the development of formalized proving using “proof-events.” Argumentation logic can offer reasoning mechanisms that facilitate these environments. This paper proposes how argumentation (...) can be implemented to discover certain characteristics in the development of formalized proving with “proof-events”. The concept of a proof-event was introduced by Goguen who described mathematical proof as a multi-agent social event involving not only “classical” formal proofs, but also other informal proving actions such as deficient or alleged proofs. Argumentation is an integral component of the discovery process for a mathematical proof since a proof necessitates a dialogue between provers and interpreters to clarify and resolve gaps or assumptions. By formalizing proof-events through argumentation, this paper demonstrates how informal reasoning and conflicts arising during the proving process can be effectively simulated. The paper presents an extended version of the proof-events calculus, rooted in argumentation theories, and highlights the intricate relationships among proof, human reasoning, cognitive processes, creativity, and mathematical arguments. (shrink)

Suppose you attend a seminar where a mathematician presents a proof to some of his colleagues. Suppose further that what he is proving is an important mathematical statement Now the following happens: as the mathematician proceeds, his audience is amazed at first, then becomes angry and finally ends up disturbing the lecture (some walk out, some laugh, …). If in addition, you see that the proof he is presenting is formally speaking (nearly) correct, would you say you are witnessing an (...) extraordinary event in urgent need of explanation? Surely, your answer would be yes. But do events of this type actually occur? The matter of the fact is, yes, they do. This paper presents the details of such an event, suggests a possible explanation and examines its implications for our understanding of mathematical practice. (shrink)

To solve the probability problem of the Many Worlds Interpretation of Quantum Mechanics, D. Wallace has presented a formal proof of the Born rule via decision theory, as proposed by D. Deutsch. The idea is to get subjective probabilities from rational decisions related to quantum measurements, showing the non-probabilistic parts of the quantum formalism, plus some rational constraints, ensure the squared modulus of quantum amplitudes play the role of such probabilities. We provide a new presentation of Wallace’s proof, reorganized (...) to simplify some arguments, and analyze it from a formal perspective. Similarities with classical decision theory are made explicit, to clarify its structure and main ideas. A simpler notation is used, and details are filled in, making it easier to follow and verify. Some problems have been identified, and we suggest possible corrections. (shrink)