10.1.1. Proof Strategies-I

Hello everyone, welcome to the first part of proof strategies. The plan for this lecture is as follows we will introduce various proof strategies that we will be encountering in this course namely direct proofs and we will see some forms of indirect proof namely the proof by contrapositive, vacuous proof and proof by contradiction.

In this section, we introduce the topic of proof strategies in mathematics. Proof strategies are methods used to demonstrate the validity of statements or theorems. The lecturer outlines that the session will cover both direct and indirect proof methods. This indicates that there are various approaches to proving mathematical statements, catering to different types of problems and situations.

Think of proof strategies like tools in a toolbox; just as you wouldn’t use a hammer for every job, different mathematical statements require different proof methods. For example, if you need to tighten a screw, you would use a screwdriver, just as you would choose an indirect proof for certain statements that can’t be easily proven directly.

So several form of theorems often involved a statement of the form, you have to prove an implication, which is universally quantified, say you have to prove statement of the form that for all integers x, if x satisfies some property then it has this condition or this extra property and so on.

This chunk explains that many theorems require proving statements that hold for all elements in a given set—these are known as universally quantified implications. The general structure of these statements is that for any integer x that satisfies a certain property P, it must also satisfy another property Q. The importance of this statement lies in the fact that proving one implies the other can sometimes be challenging.

Consider the statement "For all fruits in a bowl, if it is an apple, then it is red." Here, instead of checking every apple one by one, we can use a general understanding of apples to show this idea. Just like in mathematics, proving that all apples (x) meet the criteria (if they are apples then they are red) is efficient.

So now our goal will be to see various proof mechanisms for proving statements of the form p → q where both p and q are propositions. So we will start with the direct proof method as the name suggests it is direct because in this proof method we start assuming that my premise p is true and logically I show that my conclusion also will be true.

A direct proof is a straightforward way to prove that if proposition P is true, then proposition Q must also be true. It involves making logical deductions directly from the assumption. For example, if we want to prove that if n is an odd integer then n² is odd, we would start by assuming n is odd and show that this leads to the conclusion that n² is also odd, following logically from our assumption.

Imagine you're trying to prove that if the lights are on (P), then the room is bright (Q). In direct proof, you simply examine the light switch: if it's on, the room logically must be bright, thereby proving the implication directly.

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. So for instance if I want to prove the statement that for all integers n, if 3n+2 is odd then n is odd.

In some cases, a direct proof isn’t feasible. Therefore, mathematicians use indirect methods to validate implications when direct proof fails. Examples of such methods include proof by contraposition, proof by contradiction, and vacuous proofs. Each of these strategies offers a way to establish the truth of an implication without direct verification.

Think of trying to determine if a specific product is sold out in a store. If you can't find any directly (direct proof), you might ask if there’s evidence (like signs or staff information) that show it’s out of stock (indirect proof). Therefore, even without direct proof, you can still reach a conclusion.

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.

Proof by contraposition involves proving that if the conclusion is false (negation of q), then the premise must also be false (negation of p). This is valid because a conditional statement p → q is logically equivalent to ¬q → ¬p. For example, if we want to prove if 3n + 2 is odd then n is odd, we can instead prove that if n is even (negation of q), then 3n + 2 must be even (negation of p).

Imagine you’re trying to ensure that if I don't have my keys (¬q), then I can't unlock my door (¬p). By showing that if I indeed lack my keys, I can’t unlock the door, you effectively prove that if I can unlock the door (p), I must have the keys (q).

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 premise p is false; in such cases, the implication p → q is considered true regardless of the truth value of q. This method is useful for establishing the truth of statements when the premise is inherently false. An example is a statement like 'If 0 is greater than 1, then 0² is greater than 0.' Since the premise is false, the overall statement is true, although the conclusion might be false.

Think about a situation where you say, "If pigs fly, then the sky is purple." Since pigs cannot fly, this statement is considered true regardless of whether or not the sky is actually purple. The truth of the implication relies solely on the false premise.

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.

Proof by contradiction involves assuming that p is true, and q is false, leading to a logical contradiction. If reaching a contradiction occurs, it indicates that the assumption is false; hence, p must indeed lead to q being true. This method is highly effective in various mathematical scenarios where direct proof or other indirect proofs seem cumbersome.

Imagine claiming that every teenager has a bank account. If you assume that a teenager doesn’t have a bank account and show this leads to a contradiction (e.g., they are receiving money for their birthday), you will prove that indeed teenagers must have bank accounts.

--