Proofs and Refutations is essential reading for all those interested in the methodology, the philosophy and the history of mathematics. Much of the book takes the form of a discussion between a teacher and his students. They propose various solutions to some mathematical problems and investigate the strengths and weaknesses of these solutions. Their discussion (which mirrors certain real developments in the history of mathematics) raises some philosophical problems and some problems about the nature of mathematical discovery or creativity. (...) Imre Lakatos is concerned throughout to combat the classical picture of mathematical development as a steady accumulation of established truths. He shows that mathematics grows instead through a richer, more dramatic process of the successive improvement of creative hypotheses by attempts to 'prove' them and by criticism of these attempts: the logic of proofs and refutations. (shrink)
Many philosophers are sceptical about the power of philosophy to refute commonsensical claims. They look at the famous attempts and judge them inconclusive. I prove that even if those famous attempts are failures, there are alternative successful philosophical proofs against commonsensical claims. After presenting the proofs I briefly comment on their significance.
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)
Let Con↾x denote the finite consistency statement “there are no proofs of contradiction in T with ≤x symbols.” For a large class of natural theories T, Pudlák has shown that the lengths of the shortest proofs of Con↾n in the theory T itself are bounded by a polynomial in n. At the same time he conjectures that T does not have polynomial proofs of the finite consistency statements Con)↾n. In contrast, we show that Peano arithmetic has polynomial (...)proofs of Con)↾n, where Con∗ is the slow consistency statement for Peano arithmetic, introduced by S.-D. Friedman, Rathjen, and Weiermann. We also obtain a new proof of the result that the usual consistency statement Con is equivalent to ε0 iterations of slow consistency. Our argument is proof-theoretic, whereas previous investigations of slow consistency relied on nonstandard models of arithmetic. (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)
Our aim is to express in exact terms the old idea of solving problems by pure questioning. We consider the problem of derivability: "Is A derivable from Δ by classical propositional logic?". We develop a calculus of questions E*; a proof (called a Socratic proof) is a sequence of questions ending with a question whose affirmative answer is, in a sense, evident. The calculus is sound and complete with respect to classical propositional logic. A Socratic proof in E* can be (...) transformed into a Gentzen-style proof in some sequent calculi. Next we develop a calculus of questions E**; Socratic proofs in E** can be transformed into analytic tableaux. We show that Socratic proofs can be grounded in Inferential Erotetic Logic. After a slight modification, the analyzed systems can also be viewed as hypersequent calculi. (shrink)
Mathematicians judge proofs to possess, or lack, a variety of different qualities, including, for example, explanatory power, depth, purity, beauty and fit. Philosophers of mathematical practice have begun to investigate the nature of such qualities. However, mathematicians frequently draw attention to another desirable proof quality: being motivated. Intuitively, motivated proofs contain no "puzzling" steps, but they have received little further analysis. In this paper, I begin a philosophical investigation into motivated proofs. I suggest that a proof is (...) motivated if and only if mathematicians can identify (i) the tasks each step is intended to perform; and (ii) where each step could have reasonably come from. I argue that motivated proofs promote understanding, convey new mathematical resources and stimulate new discoveries. They thus have significant epistemic benefits and directly contribute to the efficient dissemination and advancement of mathematical knowledge. Given their benefits, I also discuss the more practical matter of how we can produce motivated proofs. Finally I consider the relationship between motivated proofs and proofs which are explanatory, beautiful and fitting. (shrink)
In a series of papers, Don Fallis points out that although mathematicians are generally unwilling to accept merely probabilistic proofs, they do accept proofs that are incomplete, long and complicated, or partly carried out by computers. He argues that there are no epistemic grounds on which probabilistic proofs can be rejected while these other proofs are accepted. I defend the practice by presenting a property I call ‘transferability’, which probabilistic proofs lack and acceptable proofs (...) have. I also consider what this says about the similarities between mathematics and, on the one hand natural sciences, and on the other hand philosophy. (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.
The central debate of natural theology among medieval Muslims and Jews concerned whether or not the world was eternal. Opinions divided sharply on this issue because the outcome bore directly on God's relationship with the world: eternity implies a deity bereft of will, while a world with a beginning leads to the contrasting picture of a deity possessed of will. In this exhaustive study of medieval Islamic and Jewish arguments for eternity, creation, and the existence of God, Herbert Davidson provides (...) a systematic classification of the proofs, analyzes and explains them, and traces their sources in Greek philosophy. Throughout the study, Davidson tries to take into account every argument of a philosophical character, disregarding only those arguments that rest entirely on religious faith or which fall below a minimal level of plausibility. (shrink)
Different natural deduction proof systems for intuitionistic and classical logic —and related logical systems—differ in fundamental properties while sharing significant family resemblances. These differences become quite stark when it comes to the structural rules of contraction and weakening. In this paper, I show how Gentzen and Jaśkowski’s natural deduction systems differ in fine structure. I also motivate directed proof nets as another natural deduction system which shares some of the design features of Genzen and Jaśkowski’s systems, but which differs again (...) in its treatment of the structural rules, and has a range of virtues absent from traditional natural deduction systems. (shrink)
Miller, D., G. Nadathur, F. Pfenning and A. Scedrov, Uniform proofs as a foundation for logic programming, Annals of Pure and Applied Logic 51 125–157. A proof-theoretic characterization of logical languages that form suitable bases for Prolog-like programming languages is provided. This characterization is based on the principle that the declarative meaning of a logic program, provided by provability in a logical system, should coincide with its operational meaning, provided by interpreting logical connectives as simple and fixed search instructions. (...) The operational semantics is formalized by the identification of a class of cut-free sequent proofs called uniform proofs. A uniform proof is one that can be found by a goal-directed search that respects the interpretation of the logical connectives as search instructions. The concept of a uniform proof is used to define the notion of an abstract logic programming language, and it is shown that first-order and higher-order Horn clauses with classical provability are examples of such a language. Horn clauses are then generalized to hereditary Harrop formulas and it is shown that first-order and higher-order versions of this new class of formulas are also abstract logic programming languages if the inference rules are those of either intuitionistic or minimal logic. The programming language significance of the various generalizations to first-order Horn clauses is briefly discussed. (shrink)
This paper concerns the relation between a proof’s beauty and its explanatory power – that is, its capacity to go beyond proving a given theorem to explaining why that theorem holds. Explanatory power and beauty are among the many virtues that mathematicians value and seek in various proofs, and it is important to come to a better understanding of the relations among these virtues. Mathematical practice has long recognized that certain proofs but not others have explanatory power, and (...) this paper offers an account of what makes a proof explanatory. This account is motivated by a wide range of examples drawn from mathematical practice, and the account proposed here is compared to other accounts in the literature. The concept of a proof that explains is closely intertwined with other important concepts, such as a brute force proof, a mathematical coincidence, unification in mathematics, and natural properties. Ultimately, this paper concludes that the features of a proof that would contribute to its explanatory power would also contribute to its beauty, but that these two virtues are not the same; a beautiful proof need not be explanatory. (shrink)
In this article we provide wellordering proofs for metapredicative systems of explicit mathematics and admissible set theory featuring suitable axioms about the Mahloness of the underlying universe of discourse. In particular, it is shown that in the corresponding theories EMA of explicit mathematics and KPm 0 of admissible set theory, transfinite induction along initial segments of the ordinal φω00, for φ being a ternary Veblen function, is derivable. This reveals that the upper bounds given for these two systems in (...) the paper Jager and Strahm  are indeed sharp. (shrink)
We give two proofs of strong normalisation for second order classical natural deduction. The first one is an adaptation of the method of reducibility candidates introduced in  for second order intuitionistic natural deduction; the extension to the classical case requires in particular a simplification of the notion of reducibility candidate. The second one is a reduction to the intuitionistic case, using a Kolmogorov translation.
This paper develops a new proof method for two propositional paraconsistent logics: the propositional part of Batens' weak paraconsistent logic CLuN and Schütte's maximally paraconsistent logic Φv. Proofs are de.ned as certain sequences of questions. The method is grounded in Inferential Erotetic Logic.
We argue that Descartes’s theistic proofs in the ’Meditations’ are much simpler and straightforward than they are traditionally taken to be. In particular, we show how the causal argument of the "Third Meditation" depends on the intuitively innocent principle that nothing comes from nothing, and not on the more controversial principle that the objective reality of an idea must have a cause with at least as much formal reality. We also demonstrate that the so-called ontological "argument" of the "Fifth (...) Meditation" is best understood not as a formal proof but as an axiom, revealed as self-evident by analytic meditation. (shrink)
Algebraic proofs of the cut-elimination theorems for classical and intuitionistic logic are presented, and are used to show how one can sometimes extract a constructive proof and an algorithm from a proof that is nonconstructive. A variation of the double-negation translation is also discussed: if ϕ is provable classically, then ¬(¬ϕ)nf is provable in minimal logic, where θnf denotes the negation-normal form of θ. The translation is used to show that cut-elimination theorems for classical logic can be viewed as (...) special cases of the cut-elimination theorems for intuitionistic logic. (shrink)
First-order logic is formalized by means of tools taken from the logic of questions. A calculus of questions which is a counterpart of the Pure Calculus of Quantifiers is presented. A direct proof of completeness of the calculus is given.
By formalizing Berry's paradox, Vopěnka, Chaitin, Boolos and others proved the incompleteness theorems without using the diagonal argument. In this paper, we shall examine these proofs closely and show their relationships. Firstly, we shall show that we can use the diagonal argument for proofs of the incompleteness theorems based on Berry's paradox. Then, we shall show that an extension of Boolos' proof can be considered as a special case of Chaitin's proof by defining a suitable Kolmogorov complexity. We (...) shall show also that Vopěnka's proof can be reformulated in arithmetic by using the arithmetized completeness theorem. (shrink)
Proofs and Refutations is essential reading for all those interested in the methodology, the philosophy and the history of mathematics. Much of the book takes the form of a discussion between a teacher and his students. They propose various solutions to some mathematical problems and investigate the strengths and weaknesses of these solutions. Their discussion raises some philosophical problems and some problems about the nature of mathematical discovery or creativity. Imre Lakatos is concerned throughout to combat the classical picture (...) of mathematical development as a steady accumulation of established truths. He shows that mathematics grows instead through a richer, more dramatic process of the successive improvement of creative hypotheses by attempts to 'prove' them and by criticism of these attempts: the logic of proofs and refutations. (shrink)
In different papers, Carnielli, W. & Rodrigues, A., Carnielli, W. Coniglio, M. & Rodrigues, A. and Rodrigues & Carnielli, present two logics motivated by the idea of capturing contradictions as conflicting evidence. The first logic is called BLE and the second—that is a conservative extension of BLE—is named LETJ. Roughly, BLE and LETJ are two non-classical logics in which the Laws of Explosion and Excluded Middle are not admissible. LETJ is built on top of BLE. Moreover, LETJ is a Logic (...) of Formal Inconsistency. This means that there is an operator that, roughly speaking, identifies a formula as having classical behavior. Both systems are motivated by the idea that there are different conditions for accepting or rejecting a sentence of our natural language. So, there are some special introduction and elimination rules in the theory that are capturing different conditions of use. Rodrigues & Carnielli’s paper has an interesting and challenging idea. According to them, BLE and LETJ are incompatible with dialetheia. It seems to show that these paraconsistent logics cannot be interpreted using truth-conditions that allow true contradictions. In short, BLE and LETJ talk about conflicting evidence avoiding to talk about gluts. I am going to argue against this point of view. Basically, I will firstly offer a new interpretation of BLE and LETJ that is compatible with dialetheia. The background of my position is to reject the one canonical interpretation thesis: the idea according to which a logical system has one standard interpretation. Then, I will secondly show that there is no logical basis to fix that Rodrigues & Carnielli’s interpretation is the canonical way to establish the content of logical notions of BLE and LETJ. Furthermore, the system LETJ captures inside classical logic. Then, I am also going to use this technical result to offer some further doubts about the one canonical interpretation thesis. (shrink)
Everyone appreciates a clever mathematical picture, but the prevailing attitude is one of scepticism: diagrams, illustrations, and pictures prove nothing; they are psychologically important and heuristically useful, but only a traditional verbal/symbolic proof provides genuine evidence for a purported theorem. Like some other recent writers (Barwise and Etchemendy ; Shin ; and Giaquinto ) I take a different view and argue, from historical considerations and some striking examples, for a positive evidential role for pictures in mathematics.
The aim of this paper is to provide epistemic reasons for investigating the notions of informal rigour and informal provability. I argue that the standard view of mathematical proof and rigour yields an implausible account of mathematical knowledge, and falls short of explaining the success of mathematical practice. I conclude that careful consideration of mathematical practice urges us to pursue a theory of informal provability.
The set of 60 real rays in four dimensions derived from the vertices of a 600-cell is shown to possess numerous subsets of rays and bases that provide basis-critical parity proofs of the Bell-Kochen-Specker (BKS) theorem (a basis-critical proof is one that fails if even a single basis is deleted from it). The proofs vary considerably in size, with the smallest having 26 rays and 13 bases and the largest 60 rays and 41 bases. There are at least (...) 90 basic types of proofs, with each coming in a number of geometrically distinct varieties. The replicas of all the proofs under the symmetries of the 600-cell yield a total of almost a hundred million parity proofs of the BKS theorem. The proofs are all very transparent and take no more than simple counting to verify. A few of the proofs are exhibited, both in tabular form as well as in the form of MMP hypergraphs that assist in their visualization. A survey of the proofs is given, simple procedures for generating some of them are described and their applications are discussed. It is shown that all four-dimensional parity proofs of the BKS theorem can be turned into experimental disproofs of noncontextuality. (shrink)
Most philosophers still tend to believe that mathematics is basically about producing formal proofs. A consequence of this view is that some aspects of mathematical practice are entirely lost from view. My contention is that it is precisely in those aspects that similarities can be found between practices in the exact sciences and in mathematics. Hence, if we are looking for a (more) unified treatment of science and mathematics it is necessary to incorporate these elements into our view of (...) what mathematics is about. As a helpful tool I introduce the notion of a mathematical argument as a more liberalized version of the notion of mathematical proof. (shrink)
“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).
The Tractatus contains twodifferent proofs of the Grundgedanke, or thenonreferentiality of logical constants. In thispaper, I explicate the first proof in TLP 5.4s andreconstruct the less explicitly stated second proof. My explication of the first proof shows it to beelegant but based on an invalid inference. In myreconstruction of the second proof, the main argumentis that the sign of a logical constant does not denotebecause it possesses the punctuation-mark-nature. Andit possesses the punctuation-mark-nature because,given the analyticity thesis in TLP 5, (...) one canestablish for everyday language an adequate symbolismwith N as the sole fundamental operation such that itssign is a bar indicating merely the order and scope ofits application. (shrink)
The small, the tiny, and the infinitesimal have been the object of both fascination and vilification for millenia. One of the most vitriolic reviews in mathematics was that written by Errett Bishop about Keisler’s book Elementary Calculus: an Infinitesimal Approach. In this skit we investigate both the argument itself, and some of its roots in Bishop George Berkeley’s criticism of Leibnizian and Newtonian Calculus. We also explore some of the consequences to students for whom the infinitesimal approach is congenial. The (...) casual mathematical reader may be satisfied to read the text of the five act play, whereas the others may wish to delve into the 130 footnotes, some of which contain elucidation of the mathematics or comments on the history. (shrink)
Inductive characterizations of the sets of terms, the subset of strongly normalizing terms and normal forms are studied in order to reprove weak and strong normalization for the simply-typed λ-calculus and for an extension by sum types with permutative conversions. The analogous treatment of a new system with generalized applications inspired by generalized elimination rules in natural deduction, advocated by von Plato, shows the flexibility of the approach which does not use the strong computability/candidate style à la Tait and Girard. (...) It is also shown that the extension of the system with permutative conversions by η-rules is still strongly normalizing, and likewise for an extension of the system of generalized applications by a rule of ``immediate simplification''. By introducing an infinitely branching inductive rule the method even extends to Gödel's T. (shrink)
According to a main idea of Gentzen the meanings of the logical constants are reflected by the introduction rules in his system of natural deduction. This idea is here understood as saying roughly that a closed argument ending with an introduction is valid provided that its immediate subarguments are valid and that other closed arguments are justified to the extent that they can be brought to introduction form. One main part of the paper is devoted to the exact development of (...) this notion. Another main part of the paper is concerned with a modification of this notion as it occurs in Michael Dummett’s book The Logical Basis of Metaphysics. The two notions are compared and there is a discussion of how they fare as a foundation for a theory of meaning. It is noted that Dummett’s notion has a simpler structure, but it is argued that it is less appropriate for the foundation of a theory of meaning, because the possession of a valid argument for a sentence in Dummett’s sense is not enough to be warranted to assert the sentence. (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.
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)
The aim I am pursuing here is to describe some general aspects of mathematical proofs. In my view, a mathematical proof is a warrant to assert a non-tautological statement which claims that certain objects (possibly a certain object) enjoy a certain property. Because it is proved, such a statement is a mathematical theorem. In my view, in order to understand the nature of a mathematical proof it is necessary to understand the nature of mathematical objects. If we understand them (...) as external entities whose 'existence' is independent of us and if we think that their enjoying certain properties is a fact, then we should argue that a theorem is a statement that claims that this fact occurs. If we also maintain that a mathematical proof is internal to a mathematical theory, then it becomes very difficult indeed to explain how a proof can be a warrant for such a statement. This is the essential content of a dilemma set forth by P. Benacerraf (cf. Benacerraf 1973). Such a dilemma, however, is dissolved if we understand mathematical objects as internal constructions of mathematical theories and think that they enjoy certain properties just because a mathematical theorem claims that they enjoy them. (shrink)