10.1. Discrete Mathematics

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 introduction, the instructor outlines the focus of the lecture, which is on proof strategies in mathematics. A proof is a logical argument that demonstrates the truth of a mathematical statement. Here, we will learn both direct and indirect methods. Direct proofs involve directly showing that a statement is true, while indirect proofs include techniques like proof by contrapositive, vacuous proof, and proof by contradiction. Each of these methods serves different situations depending on the statement being proven.

Imagine you are a detective trying to prove a suspect's guilt. A direct proof is like finding a suspect with fingerprints on the crime scene, directly showing guilt. In contrast, an indirect proof might involve ruling out other suspects to establish that the only remaining one must be guilty.

So several forms 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 discusses the type of statements we frequently prove in discrete mathematics. These statements usually take the form of implications that are universally quantified, meaning they apply to all elements in a certain set (like all integers). An example would be proving that if an integer x has a certain property (like being odd), then it must also have another property (like its square being odd). This sets the stage for understanding how to approach these proof types.

Think of this as a rule for a game: "For every player in the game, if they score a goal, then their team wins." To prove this, you need to show the rule holds for all players, similar to how universal quantification works.

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.

The direct proof method involves assuming that a given premise (p) is true and logically deducing that the conclusion (q) also is true. This method is straightforward and provides a clear path from premise to conclusion. For example, if we want to prove that if n is an odd integer then n^2 is also odd, we start by assuming n is odd and show how squaring it preserves the 'odd' property.

Consider this like completing a puzzle where you start with a known piece (the premise) and find another piece that fits perfectly (the conclusion). If you know the first piece is blue, and every blue piece has a specific shape, you can directly show that it fits in that part of the puzzle.

However, it turns out that it is not always possible to directly prove that p → q is true. 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.

This section explains that sometimes direct proof isn't possible due to complexity or ambiguity in the statements. In such cases, indirect proof methods must be used. The lecture will cover these methods, which help prove implications through alternative logical pathways rather than a direct approach.

Imagine trying to find a shortcut. If the direct road is blocked or too complicated, you might take a series of detours that, while indirect, still lead you to your destination. Similarly, indirect proof methods help navigate through complex mathematical proofs.

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...

This chunk describes the method of proof by contraposition, which proves p → q by showing ¬q → ¬p instead. This method relies on the logical equivalence between these two statements; if the original statement is true, then the contrapositive must also be true. For example, to prove that if 3n + 2 is odd then n is odd, one could instead prove that if n is even, then 3n + 2 is even.

Think of it like a detective proving someone's innocence by showing that if they weren't at the crime scene, the evidence couldn't point to them. By using the opposite scenario, you can still confirm the initial claim.

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, making the implication p → q automatically true regardless of the truth of q. For example, in the statement "If n > 1, then n^2 > n", if we plug in n = 0 (which is not greater than 1), the implication holds true even though q may be false because the premise was false.

It's like saying, 'If pigs can fly, then I can swim.' Since pigs can’t fly, this statement is always considered true, no matter how good or bad the swimming skills may be!

We can prove p → q even by contradiction method, which is an indirect proof method for proving p → q...

In a proof by contradiction, we assume p is true and q is false, then show that this results in a contradiction. This effectively demonstrates that q must be true if p is true. This method is particularly powerful because it allows us to explore what happens if our conclusion does not hold, leading to an impossible situation.

Imagine a debate where one debater claims something impossible. If they say, 'If I am tall, then I can walk through that door,' but they get stuck in the doorway establishes that their claim about being tall must be false.

--