Proof by Deduction

6 Key excerpts on "Proof by Deduction"

• 

  eBook - ePub

  Introduction to Logic

  and to the Methodology of Deductive Sciences

  • Alfred Tarski(Author)
  • 2013(Publication Date)
  • Dover Publications

    (Publisher)

  *Through the postulates of formalization the formal character of mathematics is enhanced considerably. Already at an earlier stage in the development of the deductive method we were, in the construction of a mathematical discipline, supposed to disregard the meanings of all expressions specific to this discipline, and we were to behave as if the places of these expressions were taken by variables void of any independent meaning. But, at least, to the logical concepts we were permitted to ascribe their customary meanings. In this connection, the axioms and theorems of a mathematical discipline could be treated, if not as sentences, then at least as sentential functions, that is, as expressions having the grammatical form of sentences and expressing certain properties of things or relations among things. To derive a theorem from accepted axioms (or from theorems previously proved) was the same as to show convincingly that all things satisfying the axioms also satisfy the theorem in question; mathematical proofs did not altogether differ very much from considerations of everyday life. Now, however, the meanings of all expressions encountered in the given discipline are to be disregarded without exception, and we are supposed to behave in the task of constructing a deductive theory as if its sentences were configurations of signs void of any content; each proof will now consist in subjecting axioms or previously proved theorems to a series of purely external transformations.*

  In the light of modern requirements, logic becomes the basis of the mathematical sciences in a much more thorough sense than it used to be. We may no longer be satisfied with the conviction that—due to our innate or acquired capacity for correct thinking—our argumentations are in accordance with the rules of logic. In order to give a complete proof of a theorem it is necessary to apply the transformations prescribed by the rules of proof not only to the statements of the theory with which we are concerned, but also to those of logic (and other preceding theories); and for this purpose we have to have a complete list of all logical laws at our disposal that are applied in the proofs.

  It is only by virtue of the development of deductive logic that, theoretically at least, we are today in a position to present every mathematical discipline in formalized form. In practice, however, this still involves considerable complications; a gain in exactitude and methodological correctness is accompanied by a loss in clarity and intelligibility. The whole problem, after all, is fairly new, the relevant investigations are not yet definitely concluded, and there is reason to hope that their further pursuance will eventually bring about essential simplifications. It would therefore be premature to comply fully at the present time, in a popular presentation of any part of mathematics, with the postulates of formalization. In particular, it would be far from sensible to demand that the proofs of theorems in an ordinary textbook of some mathematical discipline be given in complete form; one should, however, expect the author of a textbook to be intuitively certain that all his proofs can be brought into that form, and even to carry his considerations to a point from which a reader who has some practice in deductive thinking and sufficient knowledge of contemporary logic would be able to fill the remaining gaps without much difficulty.

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Concepts of Proof in Mathematics, Philosophy, and Computer Science

  • Dieter Probst, Peter Schuster(Authors)
  • 2016(Publication Date)
  • De Gruyter

    (Publisher)

  ⊥ so that the terms in a derivation are as in the direct case. With a bounded number of terms, there is a bounded number of distinct formulas. The number of possible consecutive steps of inference in a loop-free derivation, i.e., the height of a branch in a derivation tree, is bounded by the number of distinct formulas and we have:

  Theorem 4 (Word problem for Aristotle’ s deductive logic). The derivability of a formula P from given formulas Γ used as assumptions is decidable .

  3The issue of Aristotle’ s underlying logic

  3.1From rules to axioms

  When the study of logic was revived in the mid-nineteenth century, Aristotle’ s logic was interpreted as a logic of classes. Venn diagrams showed easily what its basic forms of inference amounted to. These diagrams can be equally well used to model monadic predicate logic, and the latter in turn gives one interpretation of Aristotle’ s logic.

  We have followed Corcoran and Smiley and taken Aristotle’ s logic simply as a system of rules of inference. Such rules stand on their own feet without any underlying logical interpretation. On the other hand, proof systems based on rules can be turned into systems that use axioms and maybe just one or two rules. Today’ s predicate logic was born, in the hands of Frege and Russell, as precisely such an axiomatic system of logic. The formulation as a system of rules of proof was found by Gentzen in the 1930s.

  Frege and Russell followed a trend of the time of axiomatizing logic as a branch of mathematics, similarly to axiomatizations of geometry and arithmetic. Many such axiomatizations can be turned, in perfect analogy to Gentzen’ s work in pure logic, into systems of rules. In the other direction, systems of rules can be turned into axiomatic systems. An example, close to Aristotle’ s system of rules, illustrates this correspondence: The theory of equality consists of a two-place relation over a given domain of elements a , b , c

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Becoming the Math Teacher You Wish You'd Had

  Ideas and Strategies from Vibrant Classrooms

  • Tracy Johnston Zager(Author)
  • 2023(Publication Date)
  • Routledge

    (Publisher)

  11 Mathematicians Prove

  DOI: 10.4324/9781032680637-11

  A proof should be an epiphany from the gods, not a coded message from the Pentagon.

  —Paul Lockhart, A Mathematician’s Lament

  What Is Proof?

  Proof has multiple meanings to mathematicians, and those meanings have evolved over time. The most formal usages emphasize objective, airtight, written arguments in which each step follows logically from the one before it, yielding deductive certainty. While modern mathematicians certainly strive for flawless arguments, many have pushed back against traditional, formal definitions, arguing they are reductive and do not convey the essence, experience, or reality of what mathematicians do. For example, Ian Stewart wrote:

  A proof, they tell us, is a finite sequence of logical deductions that begins with either axioms or previously proved results and leads to a conclusion, known as a theorem ... This definition of “proof” is all very well, but it is rather like defining a symphony as “a sequence of notes of varying pitch and duration, beginning with the first note and ending with the last.” Something is missing. Moreover, hardly anybody ever writes a proof the way the logic books describe. (2006, 89)

  After wondering about a richer, fuller description, Stewart decided on this one:

  A proof is a story. It is a story told by mathematicians to mathematicians, expressed in their common language ... If a proof is a story, then a memorable proof must tell a ripping yarn ... When I can really feel the power of a mathematical storyline, something happens in my mind that I can never forget. (2006, 89-94)

  Oxford mathematician Marcus du Sautoy explained proofs using a different analogy, but with a similarly enticing description of the audience’s experience:

  A successful proof is like a set of signposts that allow all subsequent mathematicians to make the same journey. Readers of the proof will experience the same exciting realization as its author that this path allows them to reach the distant peak. Very often a proof will not seek to dot every i and cross every t, just as a story does not present every detail of a character’s life. It is a description of the journey and not necessarily the re-enactment of every step. The arguments that mathematicians provide as proofs are designed to create a rush in the mind of the reader. (2015)

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Mathematics For Primary Teachers

  • Valsa Koshy, Ron Casey, Paul Ernest(Authors)
  • 2014(Publication Date)
  • Routledge

    (Publisher)

  Chapter 8 Mathematical proof

  DOI: 10.4324/9780203984062-10

  In the previous chapter the distinction was made between a sample and a population. A central problem for statisticians is that of devising ways of thinking which guard against ‘jumping to conclusions’ and attributing to a whole population what has been found out about a sample, without a scientific word of caution about the confidence you can legitimately have in such conclusions. In many respects, this is also a central, and much neglected, concern within mathematics. Remember the definitions of the universal and existential quantifiers in Chapter 4 , Section 5. Their use is in emphasising the difference between cases of something being true for all possibilities and something being true for just some possibilities. In this chapter the notion and strategies of proof will be explored. The appreciation of what is involved in designing your own proofs and following the proofs of others will, it is hoped, be enhanced by contrasting proof with strategies of provision of partial evidence for generalisations. The citing of particular examples, the use of diagrams to support general arguments, the contrast between deduction and induction and the process of searching for exceptions to either disprove a generalisation or impose a limitation on it will provide the backdrop to the presentation of mathematical proof.

  8.1 The role of induction

  The phrase ‘jumping to conclusions’ suggests the procedure of concluding that something is true of a large group of things on the basis of believing it is true of a smaller group of things and that such a procedure is flawed or unjustified. Before considering mathematical examples, let us reflect on what is involved in a few non-mathematical cases of our beliefs.

  ‘Night follows day’ is something we believe because of our past experience of days of living. The fact that we have not experienced future days to confirm that day will be followed by night does not undermine our belief. We are justified in our belief because our thinking conforms to the process of induction. Someone who did not share our belief would be thought of as rather peculiar, to say the least. Learning from science that our planet Earth rotates on its axis once every twenty-four hours explains how the position where we live is exposed to sunlight for part of the day and cut off from sunlight for part of the day. This scientific knowledge supports our belief that ‘night follows day’; it justifies our inductive step in saying something about days we have not lived on the basis of our experience of days we have lived through. In mathematical language, the illustration just considered amounts to making a statement beginning with ‘for all’ on the basis of a statement beginning with ‘for some’. Remind yourselves about the use of the universal quantifier, ∀, and the existential quantifier, ∃. However, a statement containing these quantifiers, with ‘x

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Truth-Functional Logic

  • J. A. Faris(Author)
  • 2019(Publication Date)
  • Routledge

    (Publisher)

  Chapter FourTHE DEDUCTIVE METHOD

  1. Introduction.

  What we are here calling the deductive method involves the construction, in accordance with certain rules, of sequences of formulae. The formulae which make up a sequence are to be known as lines of the sequence. Each sequence so constructed we call a formal deduction. If the rules are properly chosen each deduction constructed in accordance with them is a source of information about the validity of one or more arguments or argument forms. Many different sets of rules may be adopted and each such set may be known as a deductive system. We will begin by setting out a set of three rules with reference to which the main principles underlying the deductive method can be explained.

  Our first rule which may be called the premiss rule is: (R1) Any formula may be written as a line of a sequence and marked as a premiss. Rules (R2) and (R3) are known respectively as modus tollens and modus tollendo ponens. (R2) If formulae P⊃Q and ~Q occur earlier in the sequence then ~P may be written as a new line. (R3) If formulae PvQ and ~P occur earlier in the sequence then Q may be written as a new line.

  The letters P, Q which occur in these rules represent either propositions or propositional forms. Thus a sequence constructed in accordance with them may be either a sequence of propositions or a sequence of propositional forms. Suppose it is a sequence of propositions; then if we take any line l, the fact that we have constructed the sequence down to l enables us to know (i) that if all the lines used as premisses are true then l is also true, and (ii) that the argument which has for its premisses all the lines which have been marked as premisses in our sequence and as conclusion the line l

  Sign up to read

  Learn more about book
• 

  eBook - ePub

  Philosophy of Mathematics

  Classic and Contemporary Studies

  • Ahmet Cevik(Author)
  • 2021(Publication Date)
  • Chapman and Hall/CRC

    (Publisher)

  modus tollens. Proposition (vi) states the transitivity property of propositional logic. For this, consider the statements “If I put ice in the glass, the water will spill over” and “if the water spills over, then the table gets wet”. From these two statements, we can conclude that “If I put ice in the glass, the table will get wet”. The explanation of the rest of the tautologies is left to the reader as an exercise.

  Now we introduce the methods of proof. Roughly defined, a logical/ mathematical proof consists of a finite sequence of propositions. When proving any statement, we have to start our argument with a statement and so we need initial assumptions. These assumptions are called axioms. According to Oxford English Dictionary, the word axiom refers to a statement or proposition which is regarded as being established, accepted, or self-evidently true. If we can deduce in finitely many steps, using the rules of inference, the desired statement from a given collection of axioms, then this sequence of propositions constitutes a proof of the desired statement. We give the formal definition as follows.

  Definition 2.2 Let S be a collection of propositions. If for any sequence of propositions

  B 1

  , … ,

  B n

  in S,

  (

  B 1

  ∧ … ∧

  B n

  ) → A

  is a tautology, then we say that SprovesA. In this case, the sequence

  B 1

  , … ,

  B n

  is a proof of A from S.

  Although mathematical proofs in daily practice are given in natural language, they all, in principle, can be seen formally as a sequence of propositions. Proving a theorem formally can be very tedious. Mathematicians do not prove theorems in the formal manner as formal proofs are in most cases used by computer programmes or formal axiomatic systems for verification and automation purposes. Fortunately, we do not need to worry about formal proofs in this book.

  2.2.1 Direct proof

  Sign up to read

  Learn more about book