Nproof by contrapositive pdf

In mathematic logic, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by contraposition. In that proof we needed to show that a statement p. Discussion the rst two methods of proof, the \trivial proof and the \vacuous proof are certainly the easiest when they work. 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. Copious examples of proofs 19 rewrite it in each of the three forms and prove each. Contrapositive definition of contrapositive by merriamwebster. Using a fitchstyle natural deduction proof editor and checker associated with forall x. P is true, and often that is enough to produce a contradiction. We now introduce a third method of proof, called proof by contra diction. The basic concept is that proof by contrapositive relies on the fact that p. Contrapositive examples the infinite series module. The law of contrapositive says that a conditional statement is logically equivalent to its contrapositive. A proof by contradiction is a method of proving a statement by assuming the hypothesis to be true and conclusion to be false, and then deriving a contradiction.

The proof began with the assumption that p was false, that is that. The method of proof by contraposition is based on the logical equivalence between a statement and its contrapositive. You can prove this by looking at their truth tables. The proves the contrapositive of the original proposition. Set theory proof with contrapositive mathematics stack. I figured the best way to prove that is the contrapositive, i. Assuming the logic is sound, the only option is that the assumption that p is not true is incorrect. And an example of how even i screw up basic algebra at times.

Contrapositive proof example proposition suppose n 2z. Setting up proof by contrapositive katherine stange, spring 2018 for each theorem, set up the form of a proof by contrapositive. Notes on proof by contrapositive and proof by contradiction. Calgary remix, i can proceed as follows line 1 is the premise. The statement \a implies b can be written symbolically.

Each implication implies its contrapositive, even intuitionistically. Contrapositivesupposen j 12,sothereisanintegerc forwhich 12. By the closure property, we know b is an integer, so we see that 3jn2. So, to prove if p, then q by the method of contrapositive means to prove if. Assume q and then use the rules of inference, axioms, definitions. A proof by contraposition contrapositive is a direct proof of the contrapositive of a statement. Bc is a province belonging to canada, as shown in the diagram. Before we prove this, lets look at some examples and see if we can see a pattern. For instance, suppose we want to prove if mathamath, then mathbmath. The negation of a statement simply involves the insertion of the word not at the proper part of the statement. The statement \a implies b can be written symbolically as \a b. Mathematical proofmethods of proofproof by contrapositive.

A direct proof, but starting with the contrapositive equivalence. At first sight these two concepts, the contrapositive and the reductio ad absurdum proof by contradiction might appear to be very similar. 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. Chapter 6 proof by contradiction mcgill university. Unlike the method of trivial proof, this method may be applied to any implication. The contrapositive of the statement has its antecedent and consequent inverted and flipped. Within aristotelean logic, the difference is that a contrapositive is a categorical, rather than a hypothetical. The contrapositive method is a direct proof of q p. Mathematicalwriting 107 proposition suppose a, b2z andn n. What are the converse, contrapositive, and inverse. In fact, the contrapositive is true because the original statement is true. I will assume that x is odd and y is even without loss of generality, since x and y are commutative.

Sometimes youll be asked to prove a claim thats not in a good form for a direct proof. By denition, the reverse of an implication means the same as the original implicationitself. In line 3, in order to ultimately arrive at a contradiction, i. 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. Jul 06, 2017 a proof by contradiction is a method of proving a statement by assuming the hypothesis to be true and conclusion to be false, and then deriving a contradiction. Like direct proof, the technique of contrapositive proof is used to prove conditional statements of the form if p, then q. 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. Proof by contrapositive july 12, 2012 so far weve practiced some di erent techniques for writing proofs.

That is, write the rst sentence or two of the proof that is, the assumptions, and the last sentence of the proof that is, the conclusion. Converses, contrapositives and proof by the contrapositive. To prove a statement of the form \if a, then b, do the following. Proof by contradiction a proof by contradiction is a proof that works as follows. It is very important to realize that these two implications are not logically equivalent. Notice that we did not alert the reader that we are doing a proof of the contrapositive. Obviously i cant make use of the cpl within its own proof.

From the truth table, the columns of conditional statement and contrapositive statement are same. 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. Prove that every amount of postage of 12 cents or more can be formed using just 4cent and 5cent stamps. If q, then p that is, the contrapositive of hence, contrapositive of a statement is described as reversal and negation both the statements. You are probably familiar with at least a little canadian geography, and know that british columbia bc is a geographical area within canada. Instead of going from the assumptions and trying to derive the result, you start by assuming the result is false and show that this violates one of the assumptions.

Therefore, the contrapositive of a definition is always true. Before we define the converse, contrapositive, and inverse of a conditional statement, we need to examine the topic of negation. Since q2 is an integer and p2 2q2, we have that p2 is even. Proof contrapositive contrapositive statement if n is not. If three angles are equal in a triangle, then the triangle is an equilateral. The contrapositive of a conditional statement always has the same truth value as the original statement. The contrapositive is certainly true because the entire province of bc is a part of canada.

If p leads to a contradiction, then p cant be true, and therefore p must be true. Next lets prove that the composition of two injective functions is injective. Thus, the sum of any two consecutive numbers is odd. The proof by contrapositive begins with suppose x is even. A proof is a valid argument that establishes the truth of a theorem as the conclusion statements in a proof can include the axioms. In line 2, i assume q and so start a subproof which is indented according to fitch notation. Choose from 220 different sets of contrapositive flashcards on quizlet. Proof by contrapositive proof by contrapositive takes advantage of the logical equivalence between p implies q and not q implies not p. Hence, contrapositive of a statement is described as reversal and negation both the statements. Converses, contrapositives and proof by the contrapositive the converse of the implication p q is the reverse implication q p. Since proof by contrapositive involves negating certain logical statements, one has to be careful. Proof by contradiction often works well in proving statements of the form. A contradiction is a statement which is always false. Contrapositive supposenj12,sothereisaninteger c forwhich 12.

However, indirect methods such as proof by contradiction can also be used with contraposition, as, for example, in the proof of the irrationality of the square root of 2. The term transposition is reserved for hypotheticals, so. Some problems have structures that make it more obvious to try induction or contradiction. Contrapositive definition of contrapositive by merriam. Proof by contraposition is a method of proof which is not a. Contrapositive is a quite powerful method in proof. The contrapositive method allows us to use our algebraic skills in a straightforward way. That is, if and are injective functions, then the composition defined by is injective. Since the negation of conclusion implies the negation of hypothesis. Try not to think about this particular point too much.

In classical logic, an implication is logically equivalent to its contrapositive, and, moreover, its inverse is logically equivalent to its converse. The hypothesis is false, therefore the statement is vacuously true even though the conclusion is also false. For example, a total postage of 12 cents uses three 4cent stamps. We started with direct proofs, and then we moved on to proofs by contradiction and mathematical induction. So this is a valuable technique which you should use sparingly. Therefore, if you show that the contrapositive is true, you have also shown that the original statement is true. Learn contrapositive with free interactive flashcards. When to use the contrapositive to prove a statment. Sep 25, 2014 this video demonstrates a proof by contrapositive. 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.

Set theory proof with contrapositive mathematics stack exchange. This makes use of the logical law of contrapositive. Shorser the contrapositive of the statement \a b i. The method of contradiction is an example of an indirect proof. The reason is that the proof setup involves assuming x,px, which as we know from section 2. Contrapositive definition is a proposition or theorem formed by contradicting both the subject and predicate or both the hypothesis and conclusion of a given proposition or theorem and interchanging them. Nov 02, 2014 2 example questions using proof by contrapositive. As your example shows, the contrapositive of the categorical all a are b is the categorical all nonb are nona. The three forms are 1 direct if n2 is even, n is even. I attempted to show 1 independently before realizing that simply saying obviously, since a is a subset of b might be the best way to say it, though not the most formalrigorous.