PROOF by CONTRADICTION - DISCRETE MATHEMATICS

Summary

In this discrete mathematics video, the presenter introduces proof by contradiction, a powerful method for proving statements. They demonstrate its use in proving that the square root of two is irrational, by assuming the contrary and reaching a contradiction. The presenter also explores a novel set theory example, showing that the intersection of set A minus B and set B minus A is the empty set. The video encourages viewers to practice these methods, which are crucial for solving proofs in discrete mathematics.

Takeaways

• 🔢 Proof by contradiction is a powerful method in discrete mathematics for proving statements.
• 🎯 The structure of a proof by contradiction involves assuming the opposite of the statement to be true, finding a contradiction, and concluding the original statement must be true.
• 📐 An example used in the script is proving that the square root of 2 (√2) is irrational, which is difficult to prove directly but straightforward using contradiction.
• 🤔 The assumption that √2 is rational leads to the conclusion that it can be expressed as a fraction a/b in lowest terms, where a and b have no common factors other than 1.
• 🔄 By algebraic manipulation, squaring both sides of the equation leads to a contradiction, showing that a must be even, and by extension, b must also be even, which contradicts the initial assumption.
• 📚 The script explains that if both a and b are even, the fraction can be reduced, contradicting the assumption that it's in lowest terms.
• 🧩 Another example provided is a proof involving set theory, specifically showing that A - B ∩ B - A is equal to the empty set using contradiction.
• 🚫 The contradiction arises when assuming there is an element x in the set A - B ∩ B - A, which leads to x being both in and not in A and B simultaneously.
• 🔄 The script suggests that proof by contradiction can be easier than using set laws directly, although both methods can be valid.
• 📝 The importance of being careful with assumptions in proofs is highlighted, as not all assumptions may be easy to fully articulate.
• 📅 The script mentions that these concepts will be useful for the second midterm in discrete math, which can be found on trove tutor.com.

Q & A

What is the main topic of the video?

The main topic of the video is 'Proof by Contradiction', a method used in discrete mathematics to prove statements by assuming the opposite and finding a contradiction.

How does the proof by contradiction work?

In proof by contradiction, one assumes the opposite of the statement to be true, then through logical steps, finds a contradiction, thereby proving the original statement must be true.

What is an example of a proof by contradiction discussed in the video?

The video discusses proving that the square root of 2 is irrational as an example of a proof by contradiction.

Why is proving the irrationality of the square root of 2 difficult with a direct proof?

Proving the irrationality of the square root of 2 is difficult with a direct proof because it would require defining irrationality and showing that the square root of 2 does not fit that definition.

What assumption is made to start the proof that the square root of 2 is irrational?

The assumption made is that the square root of 2 is rational, which is the opposite of the statement to be proven.

What algebraic manipulation is done in the proof that the square root of 2 is irrational?

The proof involves squaring both sides of the equation to derive a contradiction, leading to the conclusion that the square root of 2 must be irrational.

What is the conclusion of the proof regarding the rationality of the square root of 2?

The conclusion is that the square root of 2 is not rational, as assuming it is rational leads to a contradiction.

What is another example of proof by contradiction discussed in the video?

Another example is proving that the set A \ B ∩ V \ A is equal to the empty set.

How does the video suggest approaching the proof that A \ B ∩ V \ A is equal to the empty set?

The video suggests using proof by contradiction by assuming the set is not empty and then finding a contradiction.

What is the final conclusion of the proof regarding the set A \ B ∩ V \ A?

The final conclusion is that the set A \ B ∩ V \ A must be the empty set, as assuming otherwise leads to a contradiction.

What advice does the video give for using proof by contradiction?

The video advises that proof by contradiction can be a powerful tool, and one should consider it when direct proofs or contrapositive proofs are not feasible.