10.1.3.1. Proof by Contraposition

The idea behind proof by contraposition is the following: your goal is to prove the validity or the fact that p → q is true we do that by instead showing that negation of q → negation of p is true and why this is a valid proof method because we know that p → q is logically equivalent to ¬ q → ¬ p that means both p → q as well as ¬ q → ¬ p takes the same truth value.

Proof by contraposition is a method used in logic and mathematics to prove implications. It relies on the logical equivalence between the implication itself (p → q) and its contrapositive (¬q → ¬p). This means that if we can prove that if q is false (¬q) then p must also be false (¬p), we have successfully shown that p → q is true. The two statements are considered to have the same truth value, which is why this method works.

Imagine you're trying to prove that if it rains, the ground is wet (p → q). Instead of directly proving that whenever it rains the ground gets wet, you could show that if the ground is not wet (¬q), then it couldn't have rained (¬p). This provides a different angle to verify the original assertion.

Let us take the same example which we discuss in the last slide we want to prove that if 3n + 2 is odd then n is odd for every integer n... If we can prove that then that is equivalent to proving our initial original implication.

In this example, we want to prove that if the expression 3n + 2 is odd (p), then n itself is odd (q). To do this by contraposition, we first express the negation of q, which is that n is even, and the negation of p, which is that 3n + 2 is even. The aim here is to show that if n is even (¬q), then 3n + 2 will also be even (¬p). By choosing an arbitrary even integer n, represented as 2k, we can substitute it into the equation and verify that 3(2k) + 2 results in an even value. This completes the proof.

Consider this like a rule that says if you go outside without an umbrella, you're going to get wet if it rains. Instead of showing that you got wet when it rained, you're showing that if you did not get wet, it couldn't have rained. This logical reasoning helps reinforce your original assertion.

So now you can see the proof is so convenient. There is another indirect proof method for proving p → q, which is called vacuous proof and this is based on the idea that your implication p → q is always true if p is false irrespective of what is q, q could be true q could be a false it does not matter if your premise p is false then definitely p → q will be true.

After implementing proof by contraposition, we recognize its convenience in proofs, especially when direct proof is complex. The methodology confirms that proving the contrapositive yields the same result. Additionally, we mention the vacuous proof, which posits that if the premise (p) is false, the implication p → q is automatically true, thus providing a secondary method of proving statements.

Think of a school rule that states if a student is suspended, then they cannot attend classes. If no student is suspended (p is false), the rule holds true regardless of whether someone attends or not, because the situation where the rule applies never happened, much like a statement that says all unicorns are mythical creatures, which is true because there are no unicorns to begin with.

--