Module 08: Indirect Proofs
Indirect Proof: Contrapositive
An indirect proof allows us to establish the truth of a statement by proving a logically equivalent reformulation. One common technique is the contrapositive proof. This approach begins by rewriting an implication of the form P(x) → Q(x) into its contrapositive: ~Q(x) → ~P(x). The quantifiers and variables remain unchanged; only the predicate expressions are transformed. Note that this is just applying our logical equivalence rule p → q ≡ ~q → ~p. As always, we can replace a subexpression with a logically equivalent one.
To carry out a contrapositive proof, first state that this method is being used, then restate the original implication in contrapositive form. From there, proceed with a direct proof of the contrapositive. Remember that the negation of the original conclusion becomes the new assumption, and the negation of the original hypothesis becomes the goal to prove. All rules of direct proof still apply.
|
For any two integers x and y, if x*y is even, then x or y is even. |
|
Proof:
We prove this by contrapositive: For any two integers x and y, if x and y are odd, then x*y is odd. ◼ |
|
Notice that the original form of this statement is hard to prove directly. We know that x * y = 2k for some integer k (since the product is even), but it's not clear how to proceed from there. Trying to define k = (x * y) / 2 introduces a division that might not result in an integer, which makes the argument harder to manage. Also, the conclusion involves an OR: either x is even or y is even. This adds complexity. Which one is even? Maybe both, maybe only one. But remember, an OR statement is true if at least one part is true. So, focusing on just one side might not help and could even lead to a false trail. All of this suggests that an indirect proof is a better approach. Specifically, we can use the contrapositive, which is logically equivalent to the original statement but often easier to prove. The contrapositive of "If x * y is even, then x is even or y is even" is "If x and y are both odd, then x * y is odd." Not only is our assumption now better, making statements about the individual variables, not the product, but due to De Morgan's law, the OR operator is now an AND operator. Sometimes it can be tricky to take the contrapositive of an English statement. You may find ithelpful to convert partly or completely into logic to help you take the contrapositive. This version is much easier to prove directly. We can use the definition of odd numbers: |
Indirect Proof: Contradiction
Another form of indirect proof is proof by contradiction. This method involves assuming the negation of the entire statement, including its quantifiers, and showing that this assumption leads to a logical contradiction. If a contradiction arises, the original statement must be true. This proof works from the negation of the theorem statement to an inherently false statement (contradiction). Do not try to use or assume the original theorem!
To apply this technique, negate the original statement completely. Recall that the negation of a universal quantifier is an existential quantifier, and vice versa. Use logical equivalences to simplify complex negations. The contradiction reached should not rely on a rewording of the conclusion but rather lead to something demonstrably false. For example, to prove ∀x ∈ D, ∃y ∈ D, P(x) ⋀ Q(y) using a contradiction, we would negate it and assume ∃x ∈ D, ∀y ∈ D, ~P(x) ⋁ ~Q(y) using De Morgan's.
|
√2 is irrational |
|
Proof:
We prove this by contradiction: Assume √2 is rational ◼ |
|
This problem is very simple on the surface, but that simplicity limits our options. We can't make any strong assumptions, and we don't have a concrete definition of "irrational" to work with; we only know it means "not rational." That doesn't give us much to directly build on. Using cases doesn't help either; there's no general variable ranging over all integers that we can divide or test in different situations. Because of that, using indirect proof is the best strategy here. Specifically, we'll use proof by contradiction. We assume the opposite of what we want to prove: that the number in question is rational. Now we have a precise definition to work with: a rational number can be written as a reduced fraction x/y, where x and y are integers with no common factor (other than 1), and y is not 0. This assumption becomes the starting point of our proof. Our goal is to show that this assumption leads to something impossible, a contradiction. The contradiction doesn't have to directly oppose the original claim (irrationality); it just needs to clash with The hint in the problem suggests a useful direction: try to simplify the expression by squaring it. This often helps when square roots are involved. Doing so might lead us to conclude that both x and y must be even. At first glance, that doesn't seem contradictory, but it actually is. If both x and y are even, then they share a common factor of 2, which contradicts our original assumption that the fraction is in lowest terms. This contradiction means our assumption that the number is rational must be false. Therefore, the number is irrational. |
Note that although we may have an existential quantifier after the negation, we cannot pick values for the variables. First, because a contradiction proof is not followed by a direct proof, we are not trying to get to the conclusion; we are trying to get to something false. Second, because those values do not exist! This is because we are not trying to prove the negated conclusion, we are assuming it. When we assume an existential, we know it is true for some value, but we do not know which one. Be careful to recognize that your negated conclusion is an assumption, not a theorem you're trying to prove.
|
For any two integers x and y, if x*y is even, then x or y is even. |
|
Proof:
We prove this by contradiction: Assume there are two integers x and y, such that x*y is even, and x and y are odd. ◼ |
|
In this case, one might be tempted to choose specific values for x and y, since our assumption (in a proof by contradiction) uses existential quantifiers; we're assuming there exist two integers x and y such that x * y is even, but both x and y are odd. But do such numbers actually exist? Can two odd integers multiply to give an even product? The answer is no. And that's exactly the point. Such a pair of numbers cannot exist, because the statement is false. And that's the core idea of a contradiction: we assume something that leads to a false conclusion, proving that the assumption must be wrong. Also, notice how the algebraic steps in this contradiction proof are almost identical to those in the contrapositive version. This is common; a proof by contrapositive and a proof by contradiction often look very similar in structure and reasoning. The main difference is in the logical framing: contradiction assumes the original statement is true and then denies the conclusion, while contrapositive directly proves an equivalent but logically reversed version of the original statement. |
Hints
- Always attempt a direct proof first, as it is often simpler.
- Try an indirect proof when the negation leads to a more manageable expression (e.g., making irrational numbers appear rational).
- For a direct proof, the final step is your conclusion that matches the original statement.
- For an indirect proof with contrapositive, the last step is your conclusion in the contrapositive statement that matches the negation of the hypothesis of the original statement. Remember that a contrapositive is always followed by a direct proof.
- For an indirect proof with contradiction, the last step is an absurdity, something false. In this proof, you should assume the negation of your statement in the first steps and conclude something false. It is never followed by a direct proof.
- Sometimes after completing an indirect proof, you can also use the insight you gained from completing that proof start over and write a clearer, simpler direct proof.
Read More
Epp, Susanna. Discrete Mathematics with Applications.
5th edition: 4.7 and 4.8
4th edition: 4.6 and 4.7
3rd edition: 3.6 and 3.7