Mathematical Proof

Mathematical diagrams are frequently used in contemporary mathematics. They are, however, widely seen as not contributing to the justificatory force of proofs: they are considered to be either mere illustrations or shorthand for non-diagrammatic expressions. Moreover, when they are used inferentially, they are seen as threatening the reliability of proofs. In this paper, I examine certain examples of diagrams that resist this type of dismissive characterization. By presenting two diagrammatic proofs, one from topology and one from algebra, I show that (...) diagrams form genuine notational systems, and I argue that this explains why they can play a role in the inferential structure of proofs without undermining their reliability. I then consider whether diagrams can be essential to the proofs in which they appear. (shrink)

Criteria of acceptability for mathematical proofs are field-dependent. In topology, though not in most other domains, it is sometimes acceptable to appeal to visual intuition to support inferential steps. In previous work :829–842, 2014; Lolli, Panza, Venturi From logic to practice, Springer, Berlin, 2015; Larvor Mathematical cultures, Springer, Berlin, 2016) my co-author and I aimed at spelling out how topological proofs work on their own terms, without appealing to formal proofs which might be associated with them. In this article, I (...) address two criticisms that have been raised in Tatton-Brown against our approach: that it leads to a form of relativism according to which validity is equated with social agreement and that it implies an antiformalizability thesis according to which it is not the case that all rigorous mathematical proofs can be formalized. I reject both criticisms and suggest that our previous case studies provide insight into the plausibility of two related but quite different theses. (shrink)

While there exists in the wild a process to derive the laws of physics ---namely, the practice of science--- such does not currently benefit from a purely formal construction. This lack necessarily leads to obscurities in the development of physics. It is our present purpose to formalize the process within a purely mathematical background that will eliminate these obscurities. The first step in the program will be to eliminate all ambiguities from our language. To do so, we will express arbitrary (...) experiments using Turing complete languages and halting programs. A listing of such experiments is recursively enumerable and, if understood as an incremental contribution to knowledge, then serves as a formulation of mathematics that models the practice of science entirely. In turn this formulation leads to a definition of the observer as the probability space over all experiments in nature, and physics as the solution to an optimization problem on the production of a message from said space; interpreted, physics defines a circumscription on the participation of the observer in nature. Finally, we discuss our model of the observer and the relation to physics, in the context of a comprehensive theory of reality. (shrink)

Volume II deals with philosophy of mathematics and general philosophy of science. In discussing theoretical entities, the notion of antirealism formulated in Volume I is further elaborated: Contrary to what is usually attributed to antirealism or idealism, the author does not claim that theoretical entities do not really exist, but rather that their existence is not independent of the possibility to know about them.

The deviation of mathematical proof—proof in mathematical practice—from the ideal of formal proof—proof in formal logic—has led many philosophers of mathematics to reconsider the commonly accepted view according to which the notion of formal proof provides an accurate descriptive account of mathematical proof. This, in turn, has motivated a search for alternative accounts of mathematical proof purporting to be more faithful to the reality of mathematical practice. Yet, in order to develop and evaluate such alternative accounts, it appears as a (...) necessary prerequisite to first possess a clear picture of what the deviation of mathematical proof from formal proof consists in. The present work aims to contribute building such a picture by investigating the relation between the elementary steps of deduction constituting the two types of proofs—mathematical inference and logical inference. Many claims have been made in the literature regarding the relation between mathematical inference and logical inference, most of them stating that the former is lacking properties that are constitutive of the latter. Such differentiating claims are, however, usually put forward without a clear conception of the properties occurring in them, and are generally considered to be immediately justified by our direct acquaintance, or phenomenological experience, with the two types of inferences. The present study purports to advance our understanding of the relation between mathematical inference and logical inference by developing a detailed philosophical analysis of the differentiating claims, that is, an analysis of the meaning of the differentiating claims—through the properties that occur in them—as well as the reasons that support them. To this end, we provide at the outset a representative list of the different properties of logical inference that have occurred in the differentiating claims, and we notice that they all boil down to the three properties of formality, generality, and mechanicality. For each one of these properties, our analysis proceeds in two steps: we first provide precise conceptual characterizations of the different ways logical inference has been said to be formal, general, and mechanical, in the philosophical and logical literature on formal proof; we then examine why mathematical inference does not appear to be formal, general, and mechanical, for the different variations of these notions identified. Our study results in a precise conceptual apparatus for expressing and discussing the properties differentiating mathematical inference from logical inference, and provides a first inventory of the various reasons supporting the observations of those differences. The differentiating claims constitute thus a set of data that any philosophical account of mathematical inference and proof purporting to be more faithful to mathematical practice ought to be able to accommodate and explain. (shrink)

Poincaré and Prawitz have both developed an account of how one can acquire knowledge through reasoning by mathematical induction. Surprisingly, their two accounts are very close to each other: both consider that what underlies reasoning by mathematical induction is a certain chain of inferences by modus ponens ‘moving along’, so to speak, the well-ordered structure of the natural numbers. Yet, Poincaré’s central point is that such a chain of inferences is not sufficient to account for the knowledge acquisition of the (...) universal propositions that constitute the conclusions of inferences by mathematical induction, as this process would require to draw an infinite number of inferences. In this paper, we propose to examine Poincaré’s point—that we will call the closure issue—in the context of Prawitz’s framework where inferences are represented as operations on grounds. We shall see that the closure issue is a challenge that also faces Prawitz’s own account of mathematical induction and which points out to an epistemic gap that the chain of modus ponens cannot bridge. One way to address the challenge is to introduce suitable additional inferential operations that would allow to fill the gap. We will end the paper by sketching such a possible solution. (shrink)

A look at Wittgenstein's comments on the incompleteness theorem with an inter-pretation that is consistent with what Gödel proved.

Ordinary mathematical proofs—to be distinguished from formal derivations—are the locus of mathematical knowledge. Their epistemic content goes way beyond what is summarised in the form of theorems. Objections are raised against the formalist thesis that every mainstream informal proof can be formalised in some first-order formal system. Foundationalism is at the heart of Hilbert's program and calls for methods of formal logic to prove consistency. On the other hand, ‘systemic cohesiveness’, as proposed here, seeks to explicate why mathematical knowledge is (...) coherent (in an informal sense) and places the problem of reliability within the province of the philosophy of mathematics. (shrink)

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)

This book is part of a major project undertaken by the Centre for Studies in Civilizations , being one of a total of ninety-six planned volumes. The author is a statistician and computer scientist by training, who has concentrated on historical matters for the last ten years or so. The book has very ambitious aims, proposing an alternative philosophy of mathematics and a deviant history of the calculus. Throughout, there is an emphasis on the need to combine history and philosophy (...) of mathematics, especially in order to evaluate properly the history of mathematics in India, in particular the history of the calculus.The pivotal goals of the book are to oppose the Eurocentric account of the history of science in general and mathematics in particular; to avoid the usual philosophical idea of the centrality of proof for mathematical knowledge, in favour of the traditional Indian notion of pramāṇa [validation] encompassing empirical elements and emphasizing calculation; to analyze the thousand-year-long development of infinite series in India, starting in the fifth century; and to show ‘how and why the calculus was imported into Europe’ from about 1500. The result is a picture in which inputs from the Indian subcontinent and epistemology are the driving forces of the history of mathematics, as people in the European subcontinent struggle to adopt new calculation techniques from the East in spite of Western philosophico-religious biases . Thus, a ‘first math war’ involved the algorismus de numero indorum, adopted for practical reasons, which forced Europeans to modify their epistemology of number and quantities. A ‘second math war’ revolved around infinite series and the calculus, since the background of Western epistemology created ‘spurious difficulties’ about infinities and infinitesimals, partially resolved with theories of real numbers. And a ‘third math war’ is …. (shrink)

There's Something about Gödel is a bargain: two books in one. The first half is a gentle but rigorous introduction to the incompleteness theorems for the mathematically uninitiated. The second is a survey of the philosophical, psychological, and sociological consequences people have attempted to derive from the theorems, some of them quite fantastical.The first part, which stays close to Gödel's original proofs, strikes a nice balance, giving enough details that the reader understands what is going on in the proofs, without (...) giving so many that the reader feels overburdened. Perhaps he skimps too much on details, as when he decides not to explain how to convert recursive definitions into explicit ones. Also, I wish he had talked about Löb's theorem. But these are small complaints.The second half discusses a sampling of what one reads about Gödel's theorems in philosophy journals and in the popular press, and here Berto often finds himself exasperated, especially by …. (shrink)

We explore aspects of an experimental approach to mathematical proof, most notably number crunching, or the verification of subsequent particular cases of universal propositions. Since the rise of the computer age, this technique has indeed conquered practice, although it implies the abandonment of the ideal of absolute certainty. It seems that also in mathematical research, the qualitative criterion of effectiveness, i.e. to reach one’s goals, gets increasingly balanced against the quantitative one of efficiency, i.e. to minimize one’s means/ends ratio. Our (...) story will lead to the consideration of some limit cases, opening up the possibility of proofs of infinite length being surveyed in a finite time. By means of example, this should show that mathematical practice in vital aspects depends upon what the actual world is like. (shrink)

In a recent paper S. McCall adds another link to a chain of attempts to enlist Gödel’s incompleteness result as an argument for the thesis that human reasoning cannot be construed as being carried out by a computer.1 McCall’s paper is undermined by a technical oversight. My concern however is not with the technical point. The argument from Gödel’s result to the no-computer thesis can be made without following McCall’s route; it is then straighter and more forceful. Yet the argument (...) fails in an interesting and revealing way. And it leaves a remainder: if some computer does in fact simulate all our mathematical reasoning, then, in principle, we cannot fully grasp how it works. Gödel’s result also points out a certain essential limitation of self-reflection. The resulting picture parallels, not accidentally, Davidson’s view of psychology, as a science that in principle must remain “imprecise”, not fully spelt out. What is intended here by “fully grasp”, and how all this is related to self-reflection, will become clear at the end of this comment. (shrink)

In this programmatic paper we renew the well-known question “What is a proof?”. Starting from the challenge of the mathematical community by computer assisted theorem provers we discuss in the first part how the experiences from examinations of proofs can help to sharpen the question. In the second part we have a look to the new challenge given by “big proofs”.

In a note appended to the translation of “On consistency and completeness” (), Gödel reexamined the problem of the unprovability of consistency. Gödel here focuses on an alternative means of expressing the consistency of a formal system, in terms of what would now be called a ‘reflection principle’, roughly, the assertion that a formula of a certain class is provable in the system only if it is true. Gödel suggests that it is this alternative means of expressing consistency that we (...) should be interested in from a foundational point of view, and he gives a result that shows certain reflection principles to be underivable in extensions of elementary number theory under conditions significantly weaker than the Hilbert-Bernays derivability conditions. In this paper I shall discuss the background to Gödel's result and the foundational significance he claims for it. Along the way, I shall present a new proof of the result which places it in an even more general context than the one considered by Gödel in the 1960s. (shrink)

We present two proof systems for first-order logic with identity and without function symbols. The first one is an extension of the Rasiowa-Sikorski system with the rules for identity. This system is a validity checker. The rules of this system preserve and reflect validity of disjunctions of their premises and conclusions. The other is a Tableau system, which is an unsatisfiability checker. Its rules preserve and reflect unsatisfiability of conjunctions of their premises and conclusions. We show that the two systems (...) are dual to each other. The duality is expressed in a formal way which enables us to define a transformation of proofs in one of the systems into the proofs of the other. (shrink)

The concept of proof can be studied from many different perspectives. Many types of proofs have been developed throughout history such as apodictic, dialectical, formal, constructive and non-constructive proofs, proofs by visualisation, assumption-based proofs, computer-generated proofs, etc. In this paper, we develop Goguen’s general concept of proof-events and the methodology of algebraic semiotics, in order to define the concept of mathematical style, which characterizes the proofs produced by different cultures, schools or scholars. In our view, style can be defined as (...) a semiotic meta-code that depends on the underlying mode of signification (semiosis), the selected code and the underlying semiotic space and determines the individual mode of integration (selection, combination, blending) into a narrative structure (proof). Finally, we examine certain historical types of styles of mathematical proofs, to elucidate our viewpoint. (shrink)

We argue that Gödel's completeness theorem is equivalent to completability of consistent theories, and Gödel's incompleteness theorem is equivalent to the fact that this completion is not constructive, in the sense that there are some consistent and recursively enumerable theories which cannot be extended to any complete and consistent and recursively enumerable theory. Though any consistent and decidable theory can be extended to a complete and consistent and decidable theory. Thus deduction and consistency are not decidable in logic, and an (...) analogue of Rice's Theorem holds for recursively enumerable theories: all the non-trivial properties of them are undecidable. (shrink)

Bolzano was the first to establish an explicit distinction between the deductive methods that allow us to recognise the certainty of a given truth and those that provide its objective ground. His conception of the relation between what we, in this paper, call "subjective consequence", i.e., the relation from epistemic reason to consequence and "objective consequence", i.e., grounding however allows for an interpretation according to which Bolzano advocates an "explicativist" conception of proof: proofs par excellence are those that reflect the (...) objective order of grounding. In this paper, we expose the problems involved by such a conception and argue in favour of a more rigorous demarcation between the ontological and the epistemological concern in the elaboration of a theory of demonstration. (shrink)

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

_Philosophy of Mathematics_ is an excellent introductory text. This student friendly book discusses the great philosophers and the importance of mathematics to their thought. It includes the following topics: * the mathematical image * platonism * picture-proofs * applied mathematics * Hilbert and Godel * knots and nations * definitions * picture-proofs and Wittgenstein * computation, proof and conjecture. The book is ideal for courses on philosophy of mathematics and logic.

Machine generated contents note: Prologue: Hilbert's Last Problem; 1. Introduction; Part I. Proof Systems Based on Natural Deduction: 2. Rules of proof: natural deduction; 3. Axiomatic systems; 4. Order and lattice theory; 5. Theories with existence axioms; Part II. Proof Systems Based on Sequent Calculus: 6. Rules of proof: sequent calculus; 7. Linear order; Part III. Proof Systems for Geometric Theories: 8. Geometric theories; 9. Classical and intuitionistic axiomatics; 10. Proof analysis in elementary geometry; Part IV. Proof Systems for Nonclassical (...) Logics: 11. Modal logic; 12. Quantified modal logic, provability logic, and so on; Bibliography; Index of names; Index of subjects. (shrink)

A layman's guide to the mechanics of Gödel's proof together with a lucid discussion of the issues which it raises. Includes an essay discussing the significance of Gödel's work in the light of Wittgenstein's criticisms.

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)

Berto’s highly readable and lucid guide introduces students and the interested reader to Gödel’s celebrated _Incompleteness Theorem_, and discusses some of the most famous - and infamous - claims arising from Gödel's arguments. Offers a clear understanding of this difficult subject by presenting each of the key steps of the _Theorem_ in separate chapters Discusses interpretations of the _Theorem_ made by celebrated contemporary thinkers Sheds light on the wider extra-mathematical and philosophical implications of Gödel’s theories Written in an accessible, non-technical (...) style. (shrink)

These questions arise from any attempt to discover an epistemology for mathematics. This collection of essays considers various questions concerning the nature of justification in mathematics and possible sources of that justification. Among these are the question of whether mathematical justification is _a priori_ or _a posteriori_ in character, whether logical and mathematical differ, and if formalization plays a significant role in mathematical justification.

Slides for the second tutorial on Gödel's incompleteness theorems, held at UniLog 5 Summer School, Istanbul, June 24, 2015.

Slides for the third tutorial on Gödel's incompleteness theorems, held at UniLog 5 Summer School, Istanbul, June 24, 2015.

Many mathematicians have cited depth as an important value in their research. However, there is no single widely accepted account of mathematical depth. This article is an attempt to bridge this gap. The strategy is to begin with a discussion of Szemerédi's theorem, which says that each subset of the natural numbers that is sufficiently dense contains an arithmetical progression of arbitrary length. This theorem has been judged deep by many mathematicians, and so makes for a good case on which (...) to focus in analyzing mathematical depth. After introducing the theorem, four accounts of mathematical depth will be considered. (shrink)

The logician Kurt Gödel published a paper in 1931 formulating what have come to be known as his 'incompleteness theorems', which prove, among other things, that within any formal system with resources sufficient to code arithmetic, questions exist which are neither provable nor disprovable on the basis of the axioms which define the system. These are among the most celebrated results in logic today. In this volume, leading philosophers and mathematicians assess important aspects of Gödel's work on the foundations and (...) philosophy of mathematics. Their essays explore almost every aspect of Godel's intellectual legacy including his concepts of intuition and analyticity, the Completeness Theorem, the set-theoretic multiverse, and the state of mathematical logic today. This groundbreaking volume will be invaluable to students, historians, logicians and philosophers of mathematics who wish to understand the current thinking on these issues. (shrink)

Proof-theoretic reflection principles are schemas which attempt to express the soundness of arithmetical theories within their own language, e.g., ${\mathtt{{Prov}_{\mathsf {PA}} \rightarrow \varphi }}$ can be understood to assert that any statement provable in Peano arithmetic is true. It has been repeatedly suggested that justification for such principles follows directly from acceptance of an arithmetical theory $\mathsf {T}$ or indirectly in virtue of their derivability in certain truth-theoretic extensions thereof. This paper challenges this consensus by exploring relationships between reflection principles (...) and principles of mathematical and transfinite induction as well as the status of the latter with respect to various foundational characterizations of number theory. (shrink)

Deduction: Automated Logic presents the broad topic of automated deductive reasoning in a concise and comprehensive manner. This book features broad coverage of deductive methods on the level of propositional and first-order logic, the strategic aspects of automated deduction, the applications of deduction mechanisms to a range of different areas, and their realization in concrete systems. This book can be used both by readers seeking a broad survey of the area, and by those requiring a reference for more detailed analysis (...) on individual topics. It is an invaluable text for students of artificial intelligence, cognitive science, and theorum- proving at the advanced undergraduate and graduate level. Intended for readers who wish to become familiar with the area as a whole, or with selected topics, in a relatively short time Serves as a reference book for consultation on individual topics Contains one of the most comprehensive collections of different deduction mechanisms which has ever appeared in a single book, all presented in a uniform framework Contains extensive references and exercises Thoroughly cross-referenced. (shrink)

For the past 25 years the CADE conference has been the major forum for the presentation of new results in automated deduction. This volume contains the papers and system descriptions selected for the 17th International Conference on Automated Deduction, CADE-17, held June 17-20, 2000,at Carnegie Mellon University, Pittsburgh, Pennsylvania. Fifty-three research papers and twenty system descriptions were submitted by researchers from?fteen countries. Each submission was reviewed by at least three reviewers. Twenty-four research papers and?fteen system descriptions were accepted. The accepted (...) papers cover a variety of topics related to t- orem proving and its applications such as proof carrying code, cryptographic protocol veri?cation, model checking, cooperating decision procedures, program veri?cation, and resolution theorem proving. The program also included three invited lectures: “High-level veri?cation using theorem proving and formalized mathematics” by John Harrison, “Sc- able Knowledge Representation and Reasoning Systems” by Henry Kautz, and “Connecting Bits with Floating-Point Numbers: Model Checking and Theorem Proving in Practice” by Carl Seger.s or full papers of these talks are included in this volume.In addition to the accepted papers, system descriptions, andinvited talks, this volumecontains one page summaries of four tutorials and?ve workshops held in conjunction with CADE-17. (shrink)

This book constitutes the refereed proceedings of the 16th International Conference on Automated Deduction, CADE-16, held in Trento, Italy in July 1999 as part of FLoC'99. The 21 revised full papers presented were carefully reviewed and selected from a total of 83 submissions. Also included are 15 system descriptions and two invited full papers. The book addresses all current issues in automated deduction and theorem proving, ranging from logical foundations to deduction systems design and evaluation.

This book constitutes the refereed proceedings of the 15th International Conference on Automated Deduction, CADE-15, held in Lindau, Germany, in July 1998. The volume presents three invited contributions together with 25 revised full papers and 10 revised system descriptions; these were selected from a total of 120 submissions. The papers address all current issues in automated deduction and theorem proving based on resolution, superposition, model generation and elimination, or connection tableau calculus, in first-order, higher-order, intuitionistic, or modal logics, and describe (...) applications to geometry, computer algebra, or reactive systems. (shrink)

This book constitutes the strictly refereed proceedings of the 14th International Conference on Automated Deduction, CADE-14, held in Townsville, North Queensland, Australia, in July 1997. The volume presents 25 revised full papers selected from a total of 87 submissions; also included are 17 system descriptions and two invited contributions. The papers cover a wide range of current issues in the area including resolution, term rewriting, unification theory, induction, high-order logics, nonstandard logics, AI methods, and applications to software verification, geometry, and (...) social science. (shrink)

This book constitutes the refereed proceedings of the 13th International Conference on Automated Deduction, CADE-13, held in July/August 1996 in New Brunswick, NJ, USA, as part of FLoC '96. The volume presents 46 revised regular papers selected from a total of 114 submissions in this category; also included are 15 selected system descriptions and abstracts of two invited talks. The CADE conferences are the major forum for the presentation of new results in all aspects of automated deduction. Therefore, the volume (...) is a timely report on the state-of-the-art in the area. (shrink)

This volume presents the proceedings of the First International Static Analysis Symposium, held in Namur, Belgium in September 1994. The proceedings comprise 25 full refereed papers selected from 70 submissions as well as four invited contributions by Charles Consel, Saumya K. Debray, Thomas W. Getzinger, and Nicolas Halbwachs. The papers address static analysis aspects for various programming paradigms and cover the following topics: generic algorithms for fixpoint computations; program optimization, transformation and verification; strictness-related analyses; type-based analyses and type inference; dependency (...) analyses and abstract domain construction. (shrink)

This volume contains the reviewed papers presented at the 12th International Conference on Automated Deduction held at Nancy, France in June/July 1994. The 67 papers presented were selected from 177 submissions and document many of the most important research results in automated deduction since CADE-11 was held in June 1992. The volume is organized in chapters on heuristics, resolution systems, induction, controlling resolutions, ATP problems, unification, LP applications, special-purpose provers, rewrite rule termination, ATP efficiency, AC unification, higher-order theorem proving, natural (...) systems, problem sets, and system descriptions. (shrink)