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)

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)

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

Abstract The paper is an attempt to interpret Imre Lakatos's methodology of scientific research programmes (MSRP) on the basis of his mathematical methodology, the method of proofs and refutations (MPR). After sketching MSRP and MPR and analysing their relationship to Popper's and Poly a's work, I argue that MSRP was originally conceived as a methodology in the same sense as MPR. The most conspicuous difference between the two, namely that MSRP is fundamentally backward?looking, whereas MPR is primarily forward?looking, (...) is due to the fact that Lakatos could not carry out his project in the full sense. I also explain why he could not. (shrink)

In this paper I will develop a lambda-term calculus, lambda-2Int, for a bi-intuitionistic logic and discuss its implications for the notions of sense and denotation of derivations in a bilateralist setting. Thus, I will use the Curry-Howard correspondence, which has been well-established between the simply typed lambda-calculus and natural deduction systems for intuitionistic logic, and apply it to a bilateralist proof system displaying two derivability relations, one for proving and one for refuting. The basis will be the natural deduction system (...) of Wansing's bi-intuitionistic logic 2Int, which I will turn into a term-annotated form. Therefore, we need a type theory that extends to a two-sorted typed lambda-calculus. I will present such a term-annotated proof system for 2Int and prove a Dualization Theorem relating proofs and refutations in this system. On the basis of these formal results I will argue that this gives us interesting insights into questions about sense and denotation as well as synonymy and identity of proofs from a bilateralist point of view. (shrink)

This paper considers a topos-theoretic structure for the interpretation of co-constructive logic for proofs and refutations following Trafford :22–40, 2015). It is notoriously tricky to define a proof-theoretic semantics for logics that adequately represent constructivity over proofs and refutations. By developing abstractions of elementary topoi, we consider an elementary topos as structure for proofs, and complement topos as structure for refutation. In doing so, it is possible to consider a dialogue structure between these topoi, and (...) also control their relation such that classical logic is simulated where proofs and refutations are conclusive. (shrink)

Dans son influent Proofs and Refutations (Preuves et Réfutations), Lakatos introduit les méthodes de preuves et de réfutations en discutant l’histoire et le développement de la formule V — E+F = 2 d’Euler pour les polyèdres en 3 dimensions. Lakatos croyait, en effet, que l’histoire du polyèdre présentait un bon exemple pour sa philosophie et sa méthodologie des mathématiques, incluant la géométrie. Le présent travail met l’accent sur les propriétés mathématiques et topologiques qui sont incorporées dans l’approche méthodologique (...) de Lakatos. Pour chaque exemple et contre-exemple utilisé par Lakatos, nous présenterons brièvement sa contrepartie topologique, ce qui nous permettra de présenter les fondations et les motivations mathématiques derrière sa philosophie de la méthodologie des mathématiques et finalement, par ce fait même, nous développerons certaines intuitions sur le fonctionnement de ses notions d’heuristique négative et d’heuristique positive. (shrink)

Dans son influent Proofs and Refutations (Preuves et Réfutations), Lakatos introduit les méthodes de preuves et de réfutations en discutant l’histoire et le développement de la formule V — E+F = 2 d’Euler pour les polyèdres en 3 dimensions. Lakatos croyait, en effet, que l’histoire du polyèdre présentait un bon exemple pour sa philosophie et sa méthodologie des mathématiques, incluant la géométrie. Le présent travail met l’accent sur les propriétés mathématiques et topologiques qui sont incorporées dans l’approche méthodologique (...) de Lakatos. Pour chaque exemple et contre-exemple utilisé par Lakatos, nous présenterons brièvement sa contrepartie topologique, ce qui nous permettra de présenter les fondations et les motivations mathématiques derrière sa philosophie de la méthodologie des mathématiques et finalement, par ce fait même, nous développerons certaines intuitions sur le fonctionnement de ses notions d’heuristique négative et d’heuristique positive. (shrink)

In this paper we study the method of refutation rules in the modal logic K4. We introduce refutation rules with certain normal forms that provide a new syntactic decision procedure for this logic. As corollaries we obtain such results for the following important extensions: S4, the provability logic G, and Grzegorczyk''s logic. We also show that tree-type models can be constructed from syntactic refutations of this kind.

In this paper we study the method of refutation rules in the modal logic K4. We introduce refutation rules with certain normal forms that provide a new syntactic decision procedure for this logic. As corollaries we obtain such results for the following important extensions: S4, the provability logic G, and Grzegorczyk's logic. We also show that tree-type models can be constructed from syntactic refutations of this kind.

Abstract Proofs and Refutations is Lakatos's masterpiece. This article investigates some of its central themes, in particular: the nature of proofs ('Proofs do not prove, they improve'); the nature of definitions (real, not nominal); and the consequences of all this for ontology (platonism vs Popper's World Three).

One of the most fundamental questions in the philosophy of mathematics concerns the relation between truth and formal proof. The position according to which the two concepts are the same is called deflationism, and the opposing viewpoint substantialism. In an important result of mathematical logic, Kurt Gödel proved in his first incompleteness theorem that all consistent formal systems containing arithmetic include sentences that can neither be proved nor disproved within that system. However, such undecidable Gödel sentences can be established to (...) be true once we expand the formal system with Alfred Tarski s semantical theory of truth, as shown by Stewart Shapiro and Jeffrey Ketland in their semantical arguments for the substantiality of truth. According to them, in Gödel sentences we have an explicit case of true but unprovable sentences, and hence deflationism is refuted. -/- Against that, Neil Tennant has shown that instead of Tarskian truth we can expand the formal system with a soundness principle, according to which all provable sentences are assertable, and the assertability of Gödel sentences follows. This way, the relevant question is not whether we can establish the truth of Gödel sentences, but whether Tarskian truth is a more plausible expansion than a soundness principle. In this work I will argue that this problem is best approached once we think of mathematics as the full human phenomenon, and not just consisting of formal systems. When pre-formal mathematical thinking is included in our account, we see that Tarskian truth is in fact not an expansion at all. I claim that what proof is to formal mathematics, truth is to pre-formal thinking, and the Tarskian account of semantical truth mirrors this relation accurately. -/- However, the introduction of pre-formal mathematics is vulnerable to the deflationist counterargument that while existing in practice, pre-formal thinking could still be philosophically superfluous if it does not refer to anything objective. Against this, I argue that all truly deflationist philosophical theories lead to arbitrariness of mathematics. In all other philosophical accounts of mathematics there is room for a reference of the pre-formal mathematics, and the expansion of Tarkian truth can be made naturally. Hence, if we reject the arbitrariness of mathematics, I argue in this work, we must accept the substantiality of truth. Related subjects such as neo-Fregeanism will also be covered, and shown not to change the need for Tarskian truth. -/- The only remaining route for the deflationist is to change the underlying logic so that our formal languages can include their own truth predicates, which Tarski showed to be impossible for classical first-order languages. With such logics we would have no need to expand the formal systems, and the above argument would fail. From the alternative approaches, in this work I focus mostly on the Independence Friendly (IF) logic of Jaakko Hintikka and Gabriel Sandu. Hintikka has claimed that an IF language can include its own adequate truth predicate. I argue that while this is indeed the case, we cannot recognize the truth predicate as such within the same IF language, and the need for Tarskian truth remains. In addition to IF logic, also second-order logic and Saul Kripke s approach using Kleenean logic will be shown to fail in a similar fashion. (shrink)

Imre Lakatos’ Proofs and Refutations is a book well known to those who work in the philosophy of mathematics, though it is perhaps not widely referred to. Its general thrust is out of tenor with the foundationalist perspective that has dominated work in the philosophy of mathematics since the early years of the 20th century. It seems to us, though, that the book contains striking insights into the nature of proof, and the purpose of this paper is to (...) explore and apply some of these. (shrink)

In the first chapter, we discuss Dummett’s idea that the notion of truth arises from the one of the correctness of an assertion. We argue that, in a first-order language, the need of defining truth in terms of the notion of satisfaction, which is yielded by the presence of quantifiers, is structurally analogous to the need of a notion of truth as distinct from the one of correctness of an assertion. In the light of the analogy between predicates in Frege (...) and open formulas in Tarksi, we concentrate on the semantic status of predicates. We register a dual attitude of Dummett towards Frege’s ascription of reference to predicates. On the one it is needed to endow quantifiers with their appropriate meaning. On the other hand, the introduction of concepts, as semantic correlate of predicates, smuggles a realist flavor in the overall semantic picture. In concluding the excursus (and with it the chapter), we stress Dummett’s will of developing a semantic picture free from this realist trait. In the second chapter, we present the idea of a proof-theoretic semantics. As for Frege true sentences denotes the truth-value True, so here closed' (i.e. categorical) valid argumentations denotes proofs. If a language contains implication-like operators, in order to characterize the condition of validity of a closed argumentation one has to introduce a notion of validity applying to ‘open’ (i.e. hypothetical) argumentations. We argue that this problem is analogous to the one posed by quantifiers in Frege-Tarksi’s style semantics. That is, implication forces one to introduce notion of validity for argumentations, which is more substantial than the correctness of the assertion of their conclusions. As we saw, the corresponding claim in the truth-based approach—that quantifiers require one to introduce a notion of truth, which is more substantial than the one of an assertion being correct—was the source of realism. Hence, Dummett proposes to reduce the semantic contribution of open argumentations to the one of their ‘closed instances’. In the truth-based perspective, this would correspond to the denial of the need of introducing concepts as the semantic correlates of predicates. We argue that Dummett’s fear, that an irreducible notion of function (represented by the need of ascribing validity to open argumentations) would lead to realism, turns out to be ill-founded. In the third chapter, we discuss the role played by the notion of truth in the anti-realist account. The notion of truth is what the anti-realist needs to cope with the so-called paradox of deduction. The analysis of the paradox yields to distinguishing between the truth of a sentence and the truth of a sentence being recognized. In terms of these conceptual couple, we reconsider the relationship between truth and assertion in an anti-realist perspective. Grounds are provided for a thesis (which was already advanced in chapter two), according to which the notion of the assertion of a sentence being correct is primarily connected only with the canonical means of establishing a sentence. The possibility of establishing a sentence by indirect means is conceptually dependent on the practice of establishing logical relationship of dependence among sentences. That is, the notion of a closed valid non-canonical argumentation is of any theoretical relevance only in presence of a notion of validity applying to open argumentations. In the fourth chapter, we discuss the possibility of characterizing in the proof-theoretic-semantics a notion of refutation. We develop an original characterization of refutations starting from an informal inductive specification of the condition of refutations of logically complex sentences. A sub-structural logic, called dual-intuitionistic logic, stands to this notion in the same relationship in which intuitionistic logic stands to the notion of proof so far consdered. All notions developed in chapter 2 have their corresponding (dual) ones in the framework developed. In particular, the distinctions canonical/non-canonical and closed/open argumentations. In the refutation based perspective, elimination rules have priority over introductions and the (only) assumption over the (many) conclusions. In the conclusions, we indicate the ingredients that an anti-realist approach to meaning should incorporate, in order to avoid the difficulties we registered. The core of an alternative view is a different conception of the relationship between categorical and hypothetical notions, in which the validity of open argumentations is not reduced to that of their instances, but rather it is directly defined. As a limit case, one would get a notion of validity applying to closed argumentations. (shrink)

Definitions I presented in a previous article as part of a semantic approach in epistemology assumed that the concept of derivability from standard logic held across all mathematical and scientific disciplines. The present article argues that this assumption is not true for quantum mechanics (QM) by showing that concepts of validity applicable to proofs in mathematics and in classical mechanics are inapplicable to proofs in QM. Because semantic epistemology must include this important theory, revision is necessary. The one (...) I propose also extends semantic epistemology beyond the ‘hard’ sciences. The article ends by presenting and then refuting some responses QM theorists might make to my arguments. (shrink)

The second edition of the Critique of Pure Reason contains several major and myriad minor emendations. The revision of the mode of presentation is apparent in four sections of the Critique: the Aesthetic; the Doctrine of the Concepts of the Understanding; the Principles of Pure Understanding; and ‘the paralogisms advanced against rational psychology’ . A new refutation of psychological idealism begins at B274. Perhaps most importantly, a new Preface frames the Critique.

Proofs of Prophecy and the Refutation of the Ismāʿīliyya: The Kitāb Ithbāt nubuwwat al-nabī by the Zaydī al-Muʾayyad bi-llāh al-Hārūnī. By Eva-Maria Lika. Worlds of Islam, vol. 9. Berlin: de Gruyter, 2018. Pp. vii + 177, 152. $149.99, €129.95, £106.99.

Luca Castagnoli, Ancient Self-Refutation. The Logic and History of the Self- Refutation Argument from Democritus to Augustine, Cambridge: Cambridge University Press 2010, pp. XX+394. Hardback, ISBN 9780521896313. In his book Ancient Self-Refutation L. Castagnoli rightly observes that selfrefutation is not falsification; it overturns the act of assertion but does not prove that the content of the act is false. He argues against the widely spread belief that Sextus Empiricus accepted the self-refutation of his own expressions. Castagnoli also claims that Sextus (...) was effective in answering to the self-refutation charge. The achievement of the book is the discovery that in passages where Sextus seems to embrace the selfrefutation of his expressions (PH 1.14-15), he does not use the term peritropé, technical for self-refutation, but the term perigraphé, which means self-bracketing. Selfbracketing is weakening one’s own thesis, but not overturning it. Castagnoli claims that Sextus embraces the self-bracketing of his expressions, but never accepts their selfrefutation. However, Castagnoli is not right in saying that self-refutation is a shameful mistake for everybody. The mature skeptic cannot even think that self-refutation is wrong, because it would be a dogmatic view. Sextus seems to accept self-refutation at the end of Against the Logicians, where he presents the argument against proof and the metaphor of the ladder (M 8.480-1). Regardless of Sextus’ declarations, we have reason to think that he does not avoid self-refutation in a pragmatic sense. Self-bracketing of his position is not a consistent dialectical strategy, as Castagnoli writes, but the end of a rational discussion. Sextus avoids absolute self-refutation (we cannot falsify what he suggests), but he is unable to avoid pragmatic self-refutation (there is no way to assert his position without contradiction). This is the case even if Sextus refuses to assert his position. (shrink)

I argue that Kant's refutation of Mendelssohn's proof of the immortality of the soul also refutes his own proof of the permanence of material substance. To evade this result, Kant would have had to rely on premises that can only be established empirically. This difficulty brings up deep and disturbing difficulties with Kant's theory of matter and body in his Metaphysical Foundations of Natural Science and suggests that his early Physical Monadology offered a better account, one he was constrained by (...) later commitments to abandon to the detriment of the coherence of his matter theory. (shrink)

A Frege proof systemFis any standard system of prepositional calculus, e.g., a Hilbert style system based on finitely many axiom schemes and inference rules. An Extended Frege systemEFis obtained fromFas follows. AnEF-sequence is a sequence of formulas ψ1, …, ψκsuch that eachψiis either an axiom ofF, inferred from previous ψuand ψv by modus ponens or of the formq↔ φ, whereqis an atom occurring neither in φ nor in any of ψ1,…,ψi−1. Suchq↔ φ, is called an extension axiom andqa new extension (...) atom. AnEF-proof is anyEF-sequence whose last formula does not contain any extension atom. In [12], S. A. Cook and R. Reckhow proved that the pigeonhole principlePHPhas a simple polynomial sizeEF-proof and conjectured thatPHPdoes not admit polynomial sizeF-proof. In [5], S. R. Buss refuted this conjecture by furnishing polynomial sizeF-proof forPHP. Since then the important separation problem of polynomial sizeFand polynomial sizeEFhas not shown any progress.In [11], S. A. Cook introduced the systemPV, a free variable equational logic whose provable functional equalities are ‘polynomial time verifiable’ and showed that the metamathematics ofFandEFcan be developed inPVand the soundness ofEFproved inPV. In [3], S. R. Buss introduced the first order systemand showed thatis essentially a conservative extension ofPV. There he also introduced a second order system. (shrink)

A Frege proof systemFis any standard system of prepositional calculus, e.g., a Hilbert style system based on finitely many axiom schemes and inference rules. An Extended Frege systemEFis obtained fromFas follows. AnEF-sequence is a sequence of formulas ψ1, …, ψκsuch that eachψiis either an axiom ofF, inferred from previous ψuand ψv by modus ponens or of the formq↔ φ, whereqis an atom occurring neither in φ nor in any of ψ1,…,ψi−1. Suchq↔ φ, is called an extension axiom andqa new extension (...) atom. AnEF-proof is anyEF-sequence whose last formula does not contain any extension atom. In [12], S. A. Cook and R. Reckhow proved that the pigeonhole principlePHPhas a simple polynomial sizeEF-proof and conjectured thatPHPdoes not admit polynomial sizeF-proof. In [5], S. R. Buss refuted this conjecture by furnishing polynomial sizeF-proof forPHP. Since then the important separation problem of polynomial sizeFand polynomial sizeEFhas not shown any progress.In [11], S. A. Cook introduced the systemPV, a free variable equational logic whose provable functional equalities are ‘polynomial time verifiable’ and showed that the metamathematics ofFandEFcan be developed inPVand the soundness ofEFproved inPV. In [3], S. R. Buss introduced the first order systemand showed thatis essentially a conservative extension ofPV. There he also introduced a second order system. (shrink)

In our previous work we proved the conjecture NP = PSPACE by advanced proof theoretic methods that combined Hudelmaier’s cut-free sequent calculus for minimal logic with the horizontal compressing in the corresponding minimal Prawitz-style natural deduction. In this Addendum we show how to prove a weaker result NP = coNP without referring to HSC. The underlying idea is to omit full minimal logic and compress only “naive” normal tree-like ND refutations of the existence of Hamiltonian cycles in given non-Hamiltonian (...) graphs, since the Hamiltonian graph problem in NPcomplete. Thus, loosely speaking, the proof of NP = coNP can be obtained by HSC-elimination from our proof of NP = PSPACE. (shrink)

We develop and study the complexity of propositional proof systems of varying strength extending resolution by allowing it to operate with disjunctions of linear equations instead of clauses. We demonstrate polynomial-size refutations for hard tautologies like the pigeonhole principle, Tseitin graph tautologies and the clique-coloring tautologies in these proof systems. Using interpolation we establish an exponential-size lower bound on refutations in a certain, considerably strong, fragment of resolution over linear equations, as well as a general polynomial upper bound (...) on interpolants in this fragment.We then apply these results to extend and improve previous results on multilinear proofs , as studied in [Ran Raz, Iddo Tzameret, The strength of multilinear proofs. Comput. Complexity ]. Specifically, we show the following:• Proofs operating with depth-3 multilinear formulas polynomially simulate a certain, considerably strong, fragment of resolution over linear equations.• Proofs operating with depth-3 multilinear formulas admit polynomial-size refutations of the pigeonhole principle and Tseitin graph tautologies. The former improve over a previous result that established small multilinear proofs only for the functional pigeonhole principle. The latter are different from previous proofs, and apply to multilinear proofs of Tseitin mod p graph tautologies over any field of characteristic 0. We conclude by connecting resolution over linear equations with extensions of the cutting planes proof system. (shrink)

Luca Castagnoli, Ancient Self-Refutation. The Logic and History of the Self- Refutation Argument from Democritus to Augustine, Cambridge: Cambridge University Press 2010, pp. XX+394. Hardback, ISBN 9780521896313. -/- Abstract. In his book Ancient Self-Refutation L. Castagnoli rightly observes that selfrefutation is not falsification; it overturns the act of assertion but does not prove that the content of the act is false. He argues against the widely spread belief that Sextus Empiricus accepted the self-refutation of his own expressions. Castagnoli also claims (...) that Sextus was effective in answering to the self-refutation charge. The achievement of the book is the disperitropécovery that in passages where Sextus seems to embrace the selfrefutation of his expressions (PH 1.14-15), he does not use the term peritropé, technical for self-refutation, but the term perigraphé, which means self-bracketing. Selfbracketing is weakening one’s own thesis, but not overturning it. Castagnoli claims that Sextus embraces the self-bracketing of his expressions, but never accepts their selfrefutation. However, Castagnoli is not right in saying that self-refutation is a shameful mistake for everybody. The mature skeptic cannot even think that self-refutation is wrong, because it would be a dogmatic view. Sextus seems to accept self-refutation at the end of Against the Logicians, where he presents the argument against proof and the metaphor of the ladder (M 8.480-1). Regardless of Sextus’ declarations, we have reason to think that he does not avoid self-refutation in a pragmatic sense. Self-bracketing of his position is not a consistent dialectical strategy, as Castagnoli writes, but the end of a rational discussion. Sextus avoids absolute self-refutation (we cannot falsify what he suggests), but he is unable to avoid pragmatic self-refutation (there is no way to assert his position without contradiction). This is the case even if Sextus refuses to assert his position. (shrink)

In 2004 Atserias, Kolaitis, and Vardi proposed $\text {OBDD}$ -based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of an identically false $\text {OBDD}$ from $\text {OBDD}$ s representing clauses of the initial formula. All $\text {OBDD}$ s in such proofs have the same order of variables. We initiate the study of $\text {OBDD}$ based proof systems that additionally contain a rule that allows changing the order in $\text {OBDD}$ s. At first we consider a (...) proof system $\text {OBDD}$ that uses the conjunction rule and the rule that allows changing the order. We exponentially separate this proof system from $\text {OBDD}$ proof system that uses only the conjunction rule. We prove exponential lower bounds on the size of $\text {OBDD}$ refutations of Tseitin formulas and the pigeonhole principle. The first lower bound was previously unknown even for $\text {OBDD}$ proofs and the second one extends the result of Tveretina et al. from $\text {OBDD}$ to $\text {OBDD}$.In 2001 Aguirre and Vardi proposed an approach to the propositional satisfiability problem based on $\text {OBDD}$ s and symbolic quantifier elimination $ algorithms). We augment these algorithms with the operation of reordering of variables and call the new scheme $\text {OBDD}$ algorithms. We notice that there exists an $\text {OBDD}$ algorithm that solves satisfiable and unsatisfiable Tseitin formulas in polynomial time, but we show that there are formulas representing systems of linear equations over $\mathbb {F}_2$ that are hard for $\text {OBDD}$ algorithms. Our hard instances are satisfiable formulas representing systems of linear equations over $\mathbb {F}_2$ that correspond to checksum matrices of error correcting codes. (shrink)