10.1.3. Indirect Proof Methods

However, it turns out that it is not always possible to directly prove that p → q is true and for situations like that, we need to have mechanisms which are indirect, we still want to prove p → q but not based on the direct proof method and there are various proof mechanisms under this category of indirect proof.

In mathematics, proving statements requires different methods. If a direct approach proves too complicated or is impossible, we often resort to indirect proofs. These alternative methods allow us to validate a proposition's truth (p → q) without the straightforward assumption of p leading directly to q. Instead of trying to prove p leading directly to q, we explore how we can prove the opposite scenario or use logical relationships.

Imagine trying to find a path from your house to a park. If the path is blocked (the direct proof), you might instead find out that the park is accessible through another route (indirect proof). Even though the initial route doesn’t work, it doesn’t mean you can’t still reach your goal through an alternative way.

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.

In proof by contraposition, instead of proving the implication directly, we prove a logically equivalent statement: if the conclusion (q) is false, then the premise (p) must also be false. This is valid because if p → q holds, then ¬q → ¬p must also hold. For example, to prove that if 3n + 2 is odd, then n is odd, we can instead show that if n is even, then 3n + 2 is even, which makes proving the original statement easier.

Consider a situation where you need to show that a person is a parent if they have children. Instead of directly proving this, you could show that if someone is not a parent (negation of q), then they can’t have children (negation of p). It takes the burden off directly proving the initial statement and instead verifies the truth indirectly.

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.

A vacuous proof occurs when the initial condition (p) is false. In these cases, the implication p → q does not depend on the truth of q—it's considered true. For example, if we claim 'if n > 1, then n² > n' and we check n = 0 (where the condition is false), the implication holds regardless of whether the conclusion is true or false. Therefore, we declare the statement true due to vacuity.

Think of it like a game that states 'if it rains, then the picnic is canceled.' If it doesn't rain at all, the statement is still true, even if we would have enjoyed the picnic. So, the truth of the statement doesn’t rely on what happens in real life when it doesn’t rain—it remains valid because the initial condition (it raining) was false.

We can prove p → q even by contradiction method, which is an indirect proof method for proving p → q and this is based on the idea that p → q is logically equivalent to p conjunction ¬ q → F.

In a proof by contradiction, we assume both p is true and q is false (¬q). We then explore the logical implications of this scenario. If we arrive at a contradiction, then our assumption must be incorrect, and we conclude that q must indeed be true. For instance, if we tried to prove that if 3n + 2 is odd, then n is also odd, we assume n is even and leading us to conclude that 3n + 2 cannot be both odd and even—the contradiction shows our assumption was wrong.

Consider a situation at a party where someone claims 'if I win a prize, then I will be happy.' To use proof by contradiction, we could assume they win (p is true) but then see them upset (q is false). If we can conclude that they can’t both win and be unhappy, it contradicts our earlier assumption, suggesting they must be happy if they won.

--