Off-campus access
Using PhilPapers from home?
Click here to configure this browser for off-campus access.
- Mateja Jamnik, Alan Bundy & Ian Green (1999). On Automating Diagrammatic Proofs of Arithmetic Arguments. Journal of Logic, Language and Information 8 (3):297-321.Theorems in automated theorem proving are usually proved by formal logical proofs. However, there is a subset of problems which humans can prove by the use of geometric operations on diagrams, so called diagrammatic proofs. Insight is often more clearly perceived in these proofs than in the corresponding algebraic proofs; they capture an intuitive notion of truthfulness that humans find easy to see and understand. We are investigating and automating such diagrammatic reasoning about mathematical theorems. Concrete, rather than general diagrams are used to prove particular concrete instances of the universally quantified theorem. The diagrammatic proof is captured by the use of geometric operations on the diagram. These operations are the inference steps of the proof. An abstracted schematic proof of the universally quantified theorem is induced from these proof instances. The constructive -rule provides the mathematical basis for this step from schematic proofs to theoremhood. In this way we avoid the difficulty of treating a general case in a diagram. One method of confirming that the abstraction of the schematic proof from the proof instances is sound is proving the correctness of schematic proofs in the meta-theory of diagrams. These ideas have been implemented in the system, called Diamond, which is presented here.Reading list | Discuss | Edit | Categorize |My bibliography
| Export citation | Other links: springerlink.com dx.doi.org | Scholar | At my library 
Similar books and articles
We consider small-weight Cutting Planes (CP * ) proofs; that is, Cutting Planes (CP) proofs with coefficients up to $\operatorname{Poly}(n)$ . We use the well known lower bounds for monotone complexity to prove an exponential lower bound for the length of CP * proofs, for a family of tautologies based on the clique function. Because Resolution is a special case of small-weight CP, our method also gives a new and simpler exponential lower bound for Resolution. We also prove the following two theorems: (1) Tree-like CP * proofs cannot polynomially simulate non-tree-like CP * proofs. (2) Tree-like (CP * proofs and Bounded-depth-Frege proofs cannot polynomially simulate each other. Our proofs also work for some generalizations of the CP * proof system. In particular, they work for CP * with a deduction rule, and also for any proof system that allows any formula with small communication complexity, and any set of sound rules of inference.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Other links: jstor.org | Scholar | At my library | More options ...
| | Other links: jstor.org | Scholar | At my library | More options ... We describe a general method how to construct from a propositional proof system P a possibly much stronger proof system iP. The system iP operates with exponentially long P-proofs described "implicitly" by polynomial size circuits. As an example we prove that proof system iEF, implicit EF, corresponds to bounded arithmetic theory $V_{2}^{1}$ and hence, in particular, polynomially simulates the quantified propositional calculus G and the $\pi_{1}^{b}-consequences$ of $S_{2}^{1}$ proved with one use of exponentiation. Furthermore, the soundness of iEF is not provable in $S_{2}^{1}$ . An iteration of the construction yields a proof system corresponding to $T_{2} + Exp$ and, in principle, to much stronger theories.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Other links: projecteuclid.org jstor.org dx.doi.org | Scholar | At my library | More options ...
| | Other links: projecteuclid.org jstor.org dx.doi.org | Scholar | At my library | More options ... Modern formal accounts of the constructive nature of elementary geometry do not aim to capture the intuitive or concrete character of geometrical construction. In line with the general abstract approach of modern axiomatics, nothing is presumed of the objects that a geometric construction produces. This study explores the possibility of a formal account of geometric construction where the basic geometric objects are understood from the outset to possess certain spatial properties. The discussion is centered around Eu , a recently developed formal system of proof (presented in Mumma (Synthese 175:255–287, 2010 )) within which Euclid’s diagrammatic proofs can be represented.
No categories
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Other links: dx.doi.org | Scholar | At my library | More options ...
| | Other links: dx.doi.org | Scholar | At my library | More options ... From ancient times to the present, the discovery and presentation of new proofs of previously established theorems has been a salient feature of mathematical practice. Why? What purposes are served by such endeavors? And how do mathematicians judge whether two proofs of the same theorem are essentially different? Consideration of such questions illuminates the roles that proofs play in the validation and communication of mathematical knowledge and raises issues that have yet to be resolved by mathematical logicians. The Appendix, in which several proofs of the Fundamental Theorem of Arithmetic are compared, provides a miniature case study.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Scholar | At my library | More options ...
| | Scholar | At my library | More options ... The automatic verification of large parts of mathematics has been an aim of many mathematicians from Leibniz to Hilbert. While Gödel's first incompleteness theorem showed that no computer program could automatically prove certain true theorems in mathematics, the advent of electronic computers and sophisticated software means in practice there are many quite effective systems for automated reasoning that can be used for checking mathematical proofs. This book describes the use of a computer program to check the proofs of several celebrated theorems in metamathematics including those of Gödel and Church-Rosser. The computer verification using the Boyer-Moore theorem prover yields precise and rigorous proofs of these difficult theorems. It also demonstrates the range and power of automated proof checking technology. The mechanization of metamathematics itself has important implications for automated reasoning, because metatheorems can be applied as labor-saving devices to simplify proof construction.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Scholar | At my library | More options ...
| | Scholar | At my library | More options ... 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.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Scholar | At my library | More options ...
| | Scholar | At my library | More options ... This article puts forward the notion of “evolving diagram” as an important case of mathematical diagram. An evolving diagram combines, through a dynamic graphical enrichment, the representation of an object and the representation of a piece of reasoning based on the representation of that object. Evolving diagrams can be illustrated in particular with category-theoretic diagrams (hereafter “diagrams*”) in the context of “sketch theory,” a branch of modern category theory. It is argued that sketch theory provides a diagrammatic* theory of diagrams*, that it helps to overcome the rivalry between set theory and category theory as a general semantical framework, and that it suggests a more flexible understanding of the opposition between formal proofs and diagrammatic reasoning. Thus, the aim of the paper is twofold. First, it claims that diagrams* provide a clear example of evolving diagrams, and shed light on them as a general phenomenon. Second, in return, it uses sketches, understood as evolving diagrams, to show how diagrams* in general should be re-evaluated positively.
No categories
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Other links: dx.doi.org | Scholar | At my library | More options ...
| | Other links: dx.doi.org | Scholar | At my library | More options ... 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.
No categories
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Other links: andrew.cmu.edu springerlink.com repository.cmu.edu jstor.org | Scholar | At my library | More options ...
| | Other links: andrew.cmu.edu springerlink.com repository.cmu.edu jstor.org | Scholar | At my library | More options ... This paper is concerned with real proofs as opposed to formal proofs, and specifically with the ultimate reason of real proofs (`Why Proof?') and with the notion of real proof (`What is a Proof?').
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Other links: w3.uniroma1.it | Scholar | At my library | More options ...
| | Other links: w3.uniroma1.it | Scholar | At my library | More options ... Recent accounts of the role of diagrams in mathematical reasoning take a Platonic line, according to which the proof depends on the similarity between the perceived shape of the diagram and the shape of the abstract object. This approach is unable to explain proofs which share the same diagram in spite of drawing conclusions about different figures. Saccheri’s use of the bi-rectangular isosceles quadrilateral in Euclides Vindicatus provides three such proofs. By forsaking abstract objects it is possible to give a natural explanation of Saccheri’s proofs as well as standard geometric proofs and even number-theoretic proofs.
Reading list
| Discuss | Edit | Categorize | My bibliography | Export citation | Scholar | At my library | More options ...
| | Scholar | At my library | More options ... Discussion of Mateja Jamnik , Alan Bundy & Ian Green, On automating diagrammatic proofs of arithmetic arguments
 Back
All discussions
Start a new thread
|
There are no threads in this forum |
Nothing in this forum yet.
