Mathematics Foundations/2.5 Contradiction and Contraposition

Contradiction and Contraposition Introduction Contradiction and contraposition are powerful proof techniques in mathematical logic. While direct proofs proceed from assumptions to conclusions, these methods provide alternative approaches that can be more effective for certain types of problems. Proof by Contradiction A proof by contradiction (also called reductio ad absurdum) is a technique where we assume the opposite of what we want to prove, and then show that this assumption leads to a logical contradiction. Since mathematics cannot contain contradictions, our initial assumption must be false, thus proving our original statement. Steps in a Proof by Contradiction 1. Assume the negation of the statement to be proved 2. Derive logical consequences until a contradiction is reached 3. Conclude that the original statement must be true Example: Irrationality of √2 Theorem: is irrational. Proof: We proceed by contradiction. Assume is rational. Then where and are integers with no common factors and . Squaring both sides: Multiplying by : This means is even, which implies is even (since the square of an odd number is odd). So for some integer . Substituting: Dividing by 2: This means is even, which implies is even. But now we have both and are even, contradicting our assumption that they have no common factors. Therefore, cannot be rational. ∎ Proof by Contraposition Contraposition is based on the logical equivalence between a conditional statement and its contrapositive. For a statement of the form "if P, then Q" (denoted ), the contrapositive is "if not Q, then not P" (denoted ). Logical Equivalence The truth table below demonstrates that a statement and its contrapositive are logically equivalent: + Truth Table for Conditional and Contrapositive P Q P ⇒ Q ¬Q ¬P ¬Q ⇒ ¬P T T T F F T T F F T F F F T T F T T F F T T T T Steps in a Proof by Contraposition 1. Restate the original statement "if P, then Q" as its contrapositive "if not Q, then not P" 2. Prove the contrapositive directly 3. Conclude that the original statement must be true Example: Properties of Even and Odd Numbers Theorem: If is even, then is even. Proof by Contraposition: We prove the contrapositive: "If is not even, then is not even." If is not even, then is odd, so for some integer . Then Since is an integer, is of the form for some integer , making odd. Therefore, is not even, completing the proof of the contrapositive. By the logical equivalence of a statement and its contrapositive, we have proven that if is even, then is even. ∎ Comparison and Usage The following table compares when to use contradiction versus contraposition: + When to Use Each Method Method Best Used When Approach Contradiction The negation leads to a clear impossibility Assume statement is false, derive contradiction Contraposition The contrapositive is easier to prove directly Prove "if not Q, then not P" instead of "if P, then Q" Exercises 1. Prove by contradiction that there is no largest prime number. 2. Prove by contraposition: "If , then or ." 3. Determine whether contradiction or contraposition would be more appropriate for proving: "If is a perfect square, then is either divisible by 4 or leaves remainder 1 when divided by 4." 4. Prove by contradiction that is irrational. 5. Prove by contraposition: "If is odd, then both and are odd."