Proof by contrapositive pdf

Notes on proof by contrapositive and proof by contradiction. Proof by induction principle of mathematical induction. Please let me know if you use book of proof in your classes and i will update the adoptions list. The second proposition is called the contrapositive of the rst proposition. Whenever a conditional statement is true, its contrapositive is also true and vice versa. Proof by contrapositive proof by contrapositive takes advantage of the logical equivalence between p implies q and not q implies not p. So this is a valuable technique which you should use sparingly. Basic proof techniques washington university in st. By the closure property, we know b is an integer, so we see that 3jn2. Chapter 17 proof by contradiction university of illinois. This is really a special case of proof by contrapositive where your \if is all of mathematics, and your \then is the statement you are trying to prove. Proof by contraposition often times, in order to show p. We prove the proposition p by contradiction by proving an implication of the form. The basic concept is that proof by contrapositive relies on the fact that p.

The method of proof by contraposition is based on the logical equivalence between a statement and its contrapositive. Our goal is to get to the point where we can do the contrapositive mentally. Based on the assumption that p is not true, conclude something impossible. But there are proofs of implications by contradiction that cannot be directly rephrased into proofs by contraposition. To show that pn holds for all natural numbers n, it su ces to establish the following. Assuming the logic is sound, the only option is that the assumption that p is not true is incorrect. By saying that the two propositions are equivalent we mean that. The basic concept is that proof by contrapositive relies on the. Proof by contradiction relies on the simple fact that if the given theorem p is true, then. Four basic proof techniques used in mathematics youtube. Discrete mathematics proof by contraposition thetrevtutor. Some problems have structures that make it more obvious to try induction or contradiction. To prove that p is true, assume that p is not true. Contrapositivesupposenj12,sothereisaninteger c forwhich 12.

A proof of the proposition of the form x px is called an existence proof sometimes, we can find an element s, called a witness, such that ps is true this type of existence proof is constructive sometimes, we may have nonconstructive existence proof, where we do not find the witness 20. Using proof by contradiction vs proof of the contrapositive. However, today we want try another approach that works well here and in other important cases where a contrapositive proof may not. Using a fitchstyle natural deduction proof editor and checker associated with forall x. To that end, assume x and y are not both odd, meaning that either x is even or y is even. That is, the arbitrary x is part of the antecedent. For a computer scientist, some of the most important things to prove are the correctness of programs and systemswhether a program or system does what its supposed to.

In that proof we needed to show that a statement p. It is very important to realize that these two implications are not logically equivalent. In this post i will cover the third method for proving theorems. Use the method of contrapositive proof to prove the following. I am looking more for a set of guidelines or intuitions or heuristics that might suggest that trying to use the contrapositive to prove the mathematical statement might be a good idea. Converses, contrapositives and proof by the contrapositive. A conditional statement consists of two parts, a hypothesis in the if clause and a conclusion in the then clause. Prove that if x2 xy is odd, then x is odd and y is even. In order for 4 to divide n2 3, n cannot not be an integer. If p leads to a contradiction, then p cant be true, and therefore p must be true.

This proof method is used when, in order to prove that px. Discrete mathematics proof by contraposition youtube. On my journey to improve my mathematical rigour i have covered direct proofs and proof by contradiction. Mat231 transition to higher math proof by contradiction fall 2014 3 12. This textbook is designed to help students acquire this essential skill, by developing a working knowledge of. For any set a, the empty set is an element of the power set of a. The proves the contrapositive of the original proposition. We prove the implication p q indirectly by proving the contrapositive. We can also assume x is odd, else we are in case 1. Converse, inverse, contrapositive given an ifthen statement if p, then q, we can create three related statements. Notice that we are not trying to show that p infers q as that would be the same as to say q infers p. Contrapositive supposenj12,sothereisaninteger c forwhich 12.

In mathematics, proof by contrapositive, or proof by contraposition, is a rule of inference used in proofs, where one infers a conditional statement from its contrapositive. Proof by contradiction a proof by contradiction is a proof that works as follows. Rather our aim is to show, usually through a direct argument, that the contrapositive statement is true. However, in a proof by contradiction, we assume that p is true and q is false and arrive at some sort of illogical statement such as 12. If not b then not a o if it is raining, the sidewalk is wet. The empty set is a subset of a, hence it is an element of the power set of a. Then, the book moves on to standard proof techniques. The purpose of this technique is often to get a starting situation to work with. Reading up on different methods for proving things i realized that a contrapositive proof is a really clever thing to used and often a better way to prove things than a proof by contradiction. While weve seen that its possible for a statement to be true while its converse is false, it turns out that the contrapositive is better behaved. The creative commons license allows you to freely use or share the books pdf, in full or in part.

In this method of proof, there is no contradiction to be found. This part of the paper explores the differences and similarities that exist between proof by contraposition and proof by contradiction. The literature refers to both methods as indirect methods of proof. In mathematic logic, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive. From rstorder logic we know that the implication p q is equivalent to. Some universities may require you to gain a continue reading.

Proofs using contrapositive and contradiction methods. In the contrapositive proof we are turning it around and. Copious examples of proofs 19 rewrite it in each of the three forms and prove each. To prove a statement of the form \if a, then b, do the following. Calgary remix, i can proceed as follows line 1 is the premise. The notion of proof by contradiction is often confused with the indirect method for proving an implication we discussed earlier. Conclusion that proof of the contrapositive proves the original statement example if a sum of two real numbers is less than 50, then at least one of the numbers is less than 25. Study at advanced higher maths level will provide excellent preparation for your studies when at university. Basic proof examples lisa oberbroeckling loyola university maryland fall 2015 note.

Proof by contrapositive o remember that the converse is not always true. Similarly, a statements converse and its inverse are always either both true or both false. Programs are notoriously buggy, and theres a growing community of researchers and practitioners trying to. Proof by contraposition rests on the fact that an implication q and its p contrapositive p q not implies not q p are two logically equivalent statements. There are four basic proof techniques to prove p q, where p is the hypothesis or set of hypotheses and q is the result. The underlying reasoning is that since a conditional statement is logically equivalent to its contrapositive, if the contrapositive is true, then the statement must also be true. In a constructive proof one attempts to demonstrate p q directly. Contrapositive proof example proposition suppose n 2z. Dec 24, 2014 we look at an indirect proof technique, proof by contraposition. A proof by contradiction is a proof that works as follows.

For all integers mand n, if the product of mand nis even, then mis even or nis even. Proof by contradiction can be applied to a much broader class of statements than proof by contraposition, which only works for implications. The proof began with the assumption that p was false, that is that. Converses, contrapositives and proof by the contrapositive the converse of the implication p q is the reverse implication q p. In line 2, i assume q and so start a subproof which is indented according to fitch notation. Logic and proof converse, inverse, and contrapositive. Mathematicalwriting 107 proposition suppose a, b2z andn n. For example, the assertion if it is my car, then it is red is equivalent to if that car is not red, then it is not mine. Since proof by contrapositive involves negating certain logical statements, one has to be careful. Writing a proof, trivial and vacuous proofs, direct proofs, proof by contrapositive, proof by cases, proof evaluations slideshare uses cookies to improve functionality and performance, and to provide you with relevant advertising. Since q2 is an integer and p2 2q2, we have that p2 is even.

The contrapositive proof goes the opposite way of the direct proof. A statement and its contrapositive are logically equivalent, in the sense that if the statement is true, then its contrapositive is true and vice versa. The primary reason is that an entire method of proof, called proof by contraposition, is based upon. Mathematical proofmethods of proofproof by contrapositive. We start with the language of propositional logic, where the rules for proofs are very straightforward. Sep 25, 2017 i this video i prove the statement the sum of two consecutive numbers is odd using direct proof, proof by contradiction, proof by induction and proof by contrapositive. Then x2 xy 2k2 2ky 22k2 ky is even since 2k2 ky 2z. We are showing that if q is false then p must be false. O the contrapositive is similar to the converse, but is always true.

Shorser the contrapositive of the statement \a b i. The statement \a implies b can be written symbolically. In fact proofs by contradiction are more general than indirect. We like to demonstrate that pn is true for all n 2n. These techniques will be useful in more advanced mathematics courses, as well as courses in statistics, computers science, and other areas. Contrapositivesupposen j 12,sothereisanintegerc forwhich 12. So, to prove if p, then q by the method of contrapositive means to prove if.

I so a divides any multiple of b i thus a divides bc, c an integer. The contrapositive method is a direct proof of q p. Chapter 6 proof by contradiction mcgill university. Proof by contradiction versus proof by contraposition. Since the negation of conclusion implies the negation of hypothesis. This is the simplest and easiest method of proof available to us.