Mathematics
Proof by Deduction
Proof by deduction is a method of establishing the truth of a mathematical statement by logically deriving it from a set of known premises or axioms. It involves a step-by-step reasoning process, where each step follows logically from the previous ones, leading to a conclusive proof of the statement's validity. This method is fundamental to mathematical reasoning and formal logic.
Written by Perlego with AI-assistance
Related key terms
1 of 5
11 Key excerpts on "Proof by Deduction"
- Olga Moreira(Author)
- 2023(Publication Date)
- Arcler Press(Publisher)
There are two universally recognized proving methods namely deduction and induction (Kögce et al., 2010; Miyazaki, 2000). Deduction method of proof involves several methods encompassing direct proof, proof by contraposition, and proof by contradiction (Baki, 2008; Moralı et al., 2006). Deduction method in mathematics begins with a general statement or hypothesis and examines the possibilities to reach a specific logical conclusion (Morris, 2002). Induction method is generally used by 8th grade students or secondary school students because they have already learned to prove numerical or geometrical proposition (Miyazaki, 2000). These two methods are based on the types of reasoning used by someone in carrying out a proving process, of which each respectively refers to deductive reasoning and inductive reasoning. Deductive reasoning is unique because it is a process of deducing conclusions from known information (premise) based on formal logic rules, where the conclusions must come from information provided and do not need to validate them with experiments (Ayalon & Even, 2008). Whereas, Christou and Papageorgiou (2007) conveyed that inductive reasoning is a reasoning process from specific premises or observations to reach a general conclusion or an overall rule. Of those two, deductive reasoning, which is used in a deductive proof, is considered the preferred tool in many mathematical communities to verify mathematical statements and demonstrate universality. Therefore, Ayalon and Even (2008) argued that deductive reasoning is often used as a synonym for mathematical thinking. Deductive or Inductive? Prospective Teachers’ Preference of Proof ... 171 Knowledge of mathematical proof is considered as one essential component of subject matters (Shulman, 1986) in which mathematics teachers must acquire. Jones (1997) argued that teachers will have an extremely secured subject knowledge base of mathematical proof if they teach it accurately and confidently.
eBook - PDFDiscrete Mathematics
Proofs, Structures and Applications, Third Edition
- Rowan Garnier, John Taylor(Authors)
- 2009(Publication Date)
- CRC Press(Publisher)
It may, however, strengthen our belief that this is so and encourage us to search for a valid proof. Making judgements about facts on the basis of observation is known as inductive reasoning . The type of reasoning where a conclusion is drawn by logical inference is called deductive reasoning . For mathematicians, the latter is the only form of reasoning which is acceptable in a proof. 2.2 Axioms and Axiom Systems To understand more fully what is meant by a proof, formal or informal, we need to look briefly at the nature of modern mathematics. Most mathematicians would agree that their subject has as its mode of operation what is known as the ‘axiomatic method’. The use of the axiomatic method was introduced by Euclid in about 300 BC (although the modern view of the nature of axioms differs in important ways from Euclid’s). A mathematical theory, such as set theory, number theory, group theory or whatever, consists of various components of which the most important are the following: 1. Undefined terms. 2. Axioms. 3. Definitions. 4. Theorems. 5. Proofs. 52 Mathematical Proof Of these, you probably have a reasonable idea of what we mean by 3, 4 and 5. That we need to have undefined terms in mathematics may come as a surprise, but a little reflection should indicate why these are necessary. Suppose we wish to write the definitive work on, say, set theory. Where do we begin? The obvious starting point is to say precisely what a set is, so we begin: Definition 1: A set is . . . —what? The problem is that, if we attempt to define ‘set’, we need to do so in terms of something else (a collection, perhaps?), but now the ‘something else’ is undefined. If we try to define the something else, we have to do so in terms of something else again, but then the ‘something else again’ is undefined, and so on.
eBook - PDFThe Other Mathematics
Language and Logic in Egyptian and in General
- Leo Depuydt(Author)
- 2008(Publication Date)
- Gorgias Press(Publisher)
Whitehead (1897: vi), who worked prominently in both logic and mathematics, describes deductive reasoning as follows: Mathematical reasoning is deductive in the sense that it is based upon definitions which … need only the test of self-consistency. Thus no external verification of definitions is required in mathematics, as long as it is considered merely as mathematics. 0.7.3 Axiomatic observations of reality Obviously, a chain of deductive inferences must have a beginning—some-thing has got to be first. It is also obvious that the first step cannot follow from a previous step, precisely because it is the first. Instead, the first step is rooted in reality or observable fact: it is a general observation about reality that seems so overwhelmingly obvious that we cannot possibly deny it. Such first steps are called axioms or postulates. They cannot be proven. One just accepts them because they seem so clear. The first step of a deductive chain of reasoning is therefore itself not deductive. If logic and mathematics are the same in both being deductive, how do they differ? It is said above that deductive chains of thought are rooted in general observations about reality. These observations are unprovable axi-oms. Logic and mathematics therefore both begin with a clear, hard look at reality around us. The aim is to make observations that are so obvious that we cannot possibly deny them. Indeed, we cannot count on proof to accept them. They are impossible to prove. Because logic and mathematics are 16 T HE O THER M ATHEMATICS identical in being deductive, the difference between the two must lie in the first step. Logic and mathematics begin with different types of observations about reality, but both types of first step set into motion deductive chains of thought in which reality is left behind. The chains are developed by a rigor-ous, internal consistency called deduction.
eBook - PDF- Charles Roberts(Author)
- 2014(Publication Date)
- Chapman and Hall/CRC(Publisher)
Chapter 2 Deductive Mathematical Systems and Proofs This chapter is devoted to the study of deductive mathematical systems and elementary proof techniques. In Section 2.1, we define deductive mathe-matical systems and discuss the Euclidean and non-Euclidean geometries, the system of natural numbers, and the system of integers. In Section 2.2, basic techniques for proving conditional statements such as direct proof, proof by contraposition, proof by contradiction, and proof by cases are presented. We also discuss proving biconditional statements, proving a statement by contra-diction, and proving statements which contain quantifiers. Next, we present some well-known mathematical conjectures and show how to prove and dis-prove conjectures. And finally, we define and examine the system of rational numbers and the system of real numbers. 2.1 Deductive Mathematical Systems A deductive mathematical system (an axiomatic theory) consists of the following six elements: 1. An underlying language—English, in our case. 2. A deductive logic system—which we introduced in Chapter 1. 3. A list of undefined terms. 4. A list of formally defined technical terms, called definitions. 5. A list of statements which are assumed to be true, called postulates or axioms. 6. A list of deduced statements, called theorems. If, on one of the first days of class, we were to ask beginning geometry stu-dents the definition of a “point,” we would receive several responses. Among those responses we would most likely find: “A point is the intersection of two lines.” If a little later in the class, we ask the same students to define a “line,” we would probably receive one or both of these responses: “A line is the shortest distance between two points.” “A line is determined by two 61
eBook - PDFLógos and Máthma 2
Studies in the Philosophy of Logic and Mathematics
- Roman Murawski(Author)
- 2020(Publication Date)
- Peter Lang Group(Publisher)
It seems to be connected with Aristotle’s view that a proposition is demonstrated (proved to be true) by showing that it is a logical consequence of propositions already known to be true. Demonstration was conceived here of as a deduction whose premises are known to be true, and a deduction was conceived of as a chaining of immediate inferences. It should be noted that Euclid’s approach (connected with Platonic idealism) to the problem of the development of mathematics and the justification of its state- ments (which found its fulfilment in the Euclidean paradigm), i.e. justification by deduction (by proofs) from explicitly stated axioms and postulates, was not the only approach and method which was used in the ancient Greek (and later). The In fact, the discussion about the truth of mathematical statements started already with the discovery of non-Euclidean geometries, but the conviction of the truth of mathematical theses dominated. Historical remarks other one (call it heuristic) was connected with Democritus’ materialism. It was ap- plied, e.g., by Archimedes who used in his mathematical works not only deduction but any methods, such as intuition or even experiments (not only mental ones) to solve problems. One can see this, e.g., in his considerations concerning the calcu- lation of the volume of a sphere using cylinder with two excavated cones or in his quadrature of the parable. Though the Euclidean approach won and dominated in the history, one should note that it formed rather an ideal and not the real scientific practice of mathemati- cians. In fact rigorous, deductive mathematics was rather a rare phenomenon. On the contrary, intuition and heuristic reasoning were the animating forces of math- ematical research practice.
eBook - PDF- John Taylor, Rowan Garnier(Authors)
- 2016(Publication Date)
- Chapman and Hall/CRC(Publisher)
Chapter 4 The Structure of Mathematical Proofs 4.1 Introduction In this chapter we introduce the key features of mathematical proof. It is very hard, some would say impossible, to define precisely what is meant by a mathematical proof as mathematicians themselves write them. The notion of proof in certain logical systems may be defined quite precisely, but this does not really describe what mathematicians do when constructing their proofs. The following professional mathematician’s definition of proof, given by Slomson [11], serves as a useful starting point. A mathematical proof is a correct and convincing mathematical argument. Whether an argument is correct is a matter of logic: the conclusion must be a logical consequence of the premises. What counts as convincing will vary from person to person, and has changed with time. In the following sections we will explain some of the general features that make a ‘correct and convincing mathematical argument’. We will begin by returning to the work we began in section 1.5 and looking at some example proofs in rather more detail than is usual. From this we will extract some gen-eral features that are common to most mathematical proofs and so develop an informal framework for constructing proofs. In particular, we will explore the deductive method that is at the heart of mathematical reasoning. We will also consider how we approach universally quantified propositional functions of the form ∀ x • P ( x ) where the universe for x is infinite. Returning to Slomson’s requirement that a proof must be convincing, we will also discuss what knowl-edge the proof writer may assume the proof reader possesses. In section 4.4, we describe the method of direct proof which underpins most mathematical proofs. Our discussion in these sections will be geared towards developing an understanding of the principal features of mathematical proofs as they are usually written.
eBook - PDFHandbook of Mathematical Induction
Theory and Applications
- David S. Gunderson(Author)
- 2014(Publication Date)
- Chapman and Hall/CRC(Publisher)
Another type of induction is more reliable: Mathematical induction is a form of reasoning that proves , without a doubt, some particular rule or pattern, usually infinite. The process of mathematical induction uses two steps. The first step is the “base step”: some simple cases are established. The second step is called 1 2 Chapter 1. What is mathematical induction? the “induction step”, and usually involves showing that an arbitrary large example follows logically from a slightly smaller pattern. Observations or patterns proved by mathematical induction share the veracity or assurance of those statements proved by deductive logic. The validity of a proof by mathematical induction follows from basic axioms regarding positive integers (see Chapter 2 for more on the foundations of the theory). In its most basic form, mathematical induction, abbreviated “MI”, is a proof technique used to prove the truth of statements regarding the positive integers. (The statements themselves are rarely discovered using mathematical induction.) In this chapter, mathematical induction is only briefly introduced, with later chapters spelling out a more formal presentation. It is easy to get excited about introducing the proof technique called “mathemat-ical induction”, especially since no mathematical aptitude or training is necessary to understand the underlying concept. With only very little high school algebra (and sometimes none at all!), mathematical induction enables a student to quickly prove hundreds of fascinating results. What more can a teacher ask for—an easy to understand technique complete with an amazing array of consequences! 1.2 An informal introduction to mathematical induc-tion To demonstrate the claim that no mathematical sophistication is necessary to com-prehend the idea of mathematical induction, let me share an anecdote. When my daughter Christine decided to keep a stray cat as a pet, the two of them soon be-came inseparable—until it was time to go to bed.
eBook - PDF- Hugh G. Gauch, Jr(Authors)
- 2012(Publication Date)
- Cambridge University Press(Publisher)
But inductive arguments admit of degrees of strength. One inductive argument might support its conclusion with a very high probability, whereas another might be rather weak. The contrast between deduction’s certainties and induction’s probabilities can easily be overdrawn, however, as if to imply that induction is second-rate logic compared with deduction. Representing certain truth by a probability of 1 and certain falsehood by 0, an inductive conclusion can have any probability from 0 to 1, including values arbitrarily close to 1 representing certainty of truth (or 0 representing certainty of falsehood). Given abundant evidence, induction can deliver practical certainties, although it cannot deliver absolute certainties. Third and finally, deduction typically reasons from the general to the spe- cific, whereas induction reasons in the opposite direction, from specific cases to general conclusions. That distinction was prominent in Aristotle’s view of sci- entific method (Losee 2001:5–8) and remains prominent in today’s dictionary definitions. For instance, the Oxford English Dictionary defines “deduction” as “inference by reasoning from generals to particulars,” and it defines “induction” as “The process of inferring a general law or principle from the observation of particular instances.” Deduction reasons from a given model to expected data, whereas induction reasons from actual data to an inferred model, as depicted in Figure 7.1. As encountered in typical scientific reasoning, the “generals” and “partic- ulars” of deduction and induction have different natures and locations. The general models or theories exist in a scientist’s mind, whereas the particular instances pertain to physical objects or events that have been observed. Often, Historical perspective on deduction 115 Deduction and Induction Given Model Inferred Model Expected Data Deduction Induction Actual Data Figure 7.1 The opposite reasoning directions of deduction and induction.
- Kenneth E. Hummel(Author)
- 2018(Publication Date)
- Chapman and Hall/CRC(Publisher)
In fact, the example in Chapter 5 regarding the primeness of n 2 — n + 41 illustrates that this type of inductive reasoning is unsatisfac-tory for proving mathematical assertions. On the other hand, inductive reasoning serves a very important role in mathematics. It may be used to test a given hypothesis. If a case can be found for which the assertion is false, the entire assertion, as stated, is invalid. If such a case cannot be found, an attempt to devise a deduc-tive proof can be initiated. The deductive proof will then guarantee the validity of the assertion. If such a proof cannot be constructed, further inductive experimentation may be in order. Frequently, inductive proce-dures help the mathematician decide upon the proper hypotheses and/or conclusion to have in the assertion and may even suggest a means of proving the theorem. When all the particular examples fit the assertion, a deductive proof may be attempted. The Principle of Mathematical Induction: Let us turn to a specific example. We will be dealing with natu-ral numbers, i.e., N = {1, 2, 3, 4, ... }, so we assume various algebraic properties have been established for N such as closure, associativity, and 79 80 Introductory Concepts for Abstract Mathematics commutativity for + and multiplication. Suppose we wish to find a for-mula for the sum 2 + 4 + 6 + • • • + 2n. This expression represents the sum of the even natural numbers up to and including the nth even natural number. Now 2n is the n th even natural number. This is interpreted as follows: when the first value of n is used, i.e., n = 1, 2n denotes the first even natural number. The first term is 2.1 = 2. The second even natural number is 2n = 2 • 2 = 4 with n = 2. The third even natural number is 2 • 3 = 6. Proceeding down the list, the seventeenth even natural number is 2 • 17 = 34. Here are five such sums. 2 = 2 2+4 = 6 2+4+6 = 12 2+4 +6+8 = 20 2 +4 +6 +8 +10 = 30.
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Library Press(Publisher)
________________________ WORLD TECHNOLOGIES ________________________ Chapter 8 Mathematical Proof Methods Mathematical induction An informal description of mathematical induction can be illustrated by reference to the sequential effect of falling dominoes. Mathematical induction is a method of mathematical proof typically used to establish that a given statement is true of all natural numbers (non-negative integers). It is done by proving that the first statement in the infinite sequence of statements is true, and then proving that if any one statement in the infinite sequence of statements is true, then so is the next one. ________________________ WORLD TECHNOLOGIES ________________________ The method can be extended to prove statements about more general well-founded structures, such as trees; this generalization, known as structural induction, is used in mathematical logic and computer science. Mathematical induction in this extended sense is closely related to recursion. Mathematical induction should not be misconstrued as a form of inductive reasoning, which is considered non-rigorous in mathematics. In fact, mathematical induction is a form of rigorous deductive reasoning. History In 370 BC, Plato's Parmenides may have contained an early example of an implicit inductive proof. The earliest implicit traces of mathematical induction can be found in Euclid's proof that the number of primes is infinite and in Bhaskara's cyclic method. An opposite iterated technique, counting down rather than up, is found in the Sorites paradox, where one argued that if 1,000,000 grains of sand formed a heap, and removing one grain from a heap left it a heap, then a single grain of sand (or even no grains) forms a heap. An implicit proof by mathematical induction for arithmetic sequences was introduced in the al-Fakhri written by al-Karaji around 1000 AD, who used it to prove the binomial theorem and properties of Pascal's triangle.
eBook - PDF- Yannai A. Gonczarowski, Noam Nisan(Authors)
- 2022(Publication Date)
- Cambridge University Press(Publisher)
For now, we are happy with using “regular” mathematics (or programming) to prove claims regarding our formal syntactic propositional-logic proofs (or equivalently, the corresponding Proof objects). 5.1 Using Lemmas Recall that each of our formal proofs has a well-defined set of inference rules that it can use, and each step (line) in the proof is confined to applying one of these rules. In “regular” mathematics we often abstract away a subargument as a lemma, prove the lemma once, and from that point allow ourselves to continue using the lemma as an additional inference rule without needing to reprove it every time that we use it in some other proof. In fact, the way that mathematics progresses is exactly by proving a richer and richer set of lemmas and theorems, all of them to be used “as inference rules” later on at will. This seems to be such 69 70 Working with Proofs a basic element of mathematical reasoning, that one may well expect such a capability of proving lemmas and then using them to be an integral part of our definition of formal proofs (just as high-level programming languages have, as an integral part of the definition of the language, the ability to implement and then use functions and methods). As we will now see, we do not need to define this capability, and in fact having the capability of defining lemmas is only for the human convenience of writing proofs, while our formal proofs can mimic this ability without having it be part of the definition. (To some extent, this is similar to machine languages often not having any notion of a procedure or function call, and yet being able to implement that functionality when higher-level languages are compiled into such machine languages.) The functions that you are asked to implement in this section are contained in the file propositions/proofs.py. The first thing that we have to verify is that if some lemma is proven, then specializations of that lemma can also be proven.
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
