Proof by contraposition examples pdf

The sum of two even numbers is not always even that would mean that there are two even numbers out there in the world somewhere thatll give us an odd number when we add them. For instance, suppose we want to prove if mathamath, then mathbmath. Therefore, we have proven the result by contraposition. The literature refers to both methods as indirect methods of proof. Therefore, if you show that the contrapositive is true, you have also shown that the original statement is true. A proof by contraposition contrapositive is a direct proof of the contrapositive of a statement. In most of the following examples the underlying \theorem may be a fact that is well known to you. Often proof by contradiction has the form proposition p q.

Suppose a 2z, if a2 is not divisible by 4, then a is odd. Proof by contradiction relies on the simple fact that if the given theorem p is true, then. Using a fitchstyle natural deduction proof editor and checker associated with forall x. Moreover, i have found that these logical exercises make me a much more e ective debugger of. But there are proofs of implications by contradiction that cannot be directly rephrased into proofs by contraposition. Contrapositive examples the infinite series module. 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. Proof by contrapositive july 12, 2012 so far weve practiced some di erent techniques for writing proofs. Notes on proof by contrapositive and proof by contradiction. In a proof by contraposition both the starting point and the aim are clear. The primary reason is that an entire method of proof, called proof by contraposition, is based upon exactly this. For our next example, consider the following proposition concerninganintegerx. Similarly, a statements converse and its inverse are always either both true or both false. Logic and proof converse, inverse, and contrapositive.

I hadnt realized that i hadnt written it in the notes. Proof by contrapositive california state university, fresno. Since it is a rare occasion when we are able to get by with one of these two methods of proof, we turn to some we are more likely to need. In 1891, georg cantor assumed that there is a set t that contains every infinitelengt. Study at advanced higher maths level will provide excellent preparation for your studies when at university. Proofs using contrapositive and contradiction methods. 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. Think of this as \a is equivalent to b pssst, as long as we are using modulo n. A proof by contradiction induction cornell university. Notes on proof by contrapositive and proof by contradiction hyunyoung lee august 31, 2018 in this short lecture note, i will explain the di erence between proof by contrapositive and proof by contradiction, which seem to cause easily some confusions. We started with direct proofs, and then we moved on to proofs by contradiction and mathematical induction. The difference is that in a proof by contradiction, we have the extra assumption \pa\ to work with and in certain situations, it provides us with a more convenient way of arriving at a. Simon singh a proof is a sequence of logical statements, one implying another, which gives an explanation of why a given statement is true.

The proof of independence of ch by forcing is added. Likedirectproof,thetechniqueofcontrapositiveproofis. The method of contradiction is an example of an indirect proof. This video is part of a discrete math course taught at the university of cinc. Existence proof examples show that there is a positive integer that can be written as the sum of cubes of positive integers. In another sense this method is indirect because a proof by contraposition can usually be recast as a proof by contradiction fairly easily. 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 reason is that the proof setup involves assuming x,px, which as we know from section 2. The purpose in presenting them, however, is not to surprise you with new mathematical facts, but. 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. One of the most famous proofs of all time ironically, one that is incorrectly cited as an example of proof by contradiction1 is a proof by contraposition.

Proof by contradiction can be applied to a much broader class of statements than proof by contraposition, which only works for implications. We obtain the desired conclusion in both cases, so the original statement is true. In line 3, in order to ultimately arrive at a contradiction, i. 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. This new method is not limited to proving just conditional statements it can be used to prove any kind of statement whatsoever. Well need this method in chapter 20, when we cover the topic of uncountability. Proof by contrapositive proof by contrapositive takes advantage of the logical equivalence between p implies q and not q implies not p. Given integers a and b and an n 2n, we say that a and b are congruent modulo n if nja b. Sometimes youll be asked to prove a claim thats not in a good form for a direct proof. Proof by contraposition can be an e ective approach when a traditional direct proof is tricky, or it can be a di erent way to think about the substance of a problem. In this post i will cover the third method for proving theorems.

Chapter 9 contrapositiveproof wenowexamineanalternativetodirectproofcalledcontrapositive proof. There is an indication of a considerable simpli cation of my forcing treatment, by. Many of the statements we prove have the form p q which, when negated, has the form p. Proofs by contraposition and contradiction physics forums. Some universities may require you to gain a continue reading. The statement \a implies b can be written symbolically.

Discrete mathematics proof by contraposition youtube. Contradiction and contraposition carleton university. A proof by contraposition can be converted into a proof by contradiction by adding the assumption that the premise is true and then showing that there is a contradiction. However, contradiction proofs tend to be less convincing and harder to write than. Chapter 6 proof by contradiction we now introduce a third method of proof, called proof by contra diction. It is important to be extremely pedantic when interpreting a. This is apowerful prooftechnique that can be extremely useful in the right circumstances. On my journey to improve my mathematical rigour i have covered direct proofs and proof by contradiction. From this assumption, p 2 can be written in terms of a b, where a and b have no common factor. The proves the contrapositive of the original proposition, and so completes the proof. Examples of congruence 7 3 mod 2 since 7 3 4 is a multiple of 2. In this one, a direct proof would be awkward and quite di cult, so contrapositive is the way to go. Proof by contraposition examples kent state university. Mathematical writing the following list comes from our text.

The proof by contraposition method makes use of the equivalence p q q p to show that the conditional statement p q is true, we first assume q is true, and use. Homework statement a prove that if n is an integer and n 2 is a multiple of 3, then n is a multiple of 3. Shorser the contrapositive of the statement \a b i. One of several different ways to prove a statement in mathematics is proof by contradiction. Prove the following statement by contraposition if a product of two positive real numbers is greater than 100, then at. In this case, one might wonder why we have a proof by contradiction instead of a proof by contraposition since we end up with \\neg pa\ anyway. Moreover, i have found that these logical exercises make me a much more e ective debugger of code that involves conditional statements. This proof method is applied when the negation of the theorem statement is easier to be shown to lead to an absurd not true situation than proving the original theorem statement using a direct proof. We look at an indirect proof technique, proof by contraposition. To prove a statement p is true, we begin by assuming p false and show that this leads to a contradiction. Direct proofs proof by contraposition math berkeley. This is because it is easier to transforminformationabout xintoinformationabout7. To prove that p is true by contrapositive, we prove the following statement. In one sense this proof technique isnt really all that indirect.

Proof by contradiction this is an example of proof by contradiction. Chapter 17 proof by contradiction this chapter covers proofby contradiction. In a direct proof you start with the hypothesis of a statement. Calgary remix, i can proceed as follows line 1 is the premise.

Whenever a conditional statement is true, its contrapositive is also true and vice versa. Learn the definition of this method and observe how it is applied to proving a statements truth value. It is important to be extremely pedantic when interpreting a contraposition. Chapter 6 proof by contradiction mcgill university. You are probably familiar with at least a little canadian geography, and know that british columbia bc is a geographical area within canada. P is true, and often that is enough to produce a contradiction. 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. Prove, using contradiction, that at least one student must have received at least k marks in the exam. To prove that p q is false, find an example of where p is true. To illustrate, below is an example of a proof by contraposition. Squaring both sides, we get 2 a2b2 thus, a2 2b2, so a2 is even.