PROOF by CONTRADICTION - DISCRETE MATHEMATICS

TrevTutor
18 May 201509:35

Summary

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

Outlines

plate

Cette section est réservée aux utilisateurs payants. Améliorez votre compte pour accéder à cette section.

Améliorer maintenant

Mindmap

plate

Cette section est réservée aux utilisateurs payants. Améliorez votre compte pour accéder à cette section.

Améliorer maintenant

Keywords

plate

Cette section est réservée aux utilisateurs payants. Améliorez votre compte pour accéder à cette section.

Améliorer maintenant

Highlights

plate

Cette section est réservée aux utilisateurs payants. Améliorez votre compte pour accéder à cette section.

Améliorer maintenant

Transcripts

plate

Cette section est réservée aux utilisateurs payants. Améliorez votre compte pour accéder à cette section.

Améliorer maintenant
Rate This
★
★
★
★
★

5.0 / 5 (0 votes)

Étiquettes Connexes
Proof by ContradictionDiscrete MathRational NumbersIrrationalitySet TheoryAlgebraic ManipulationLogical ProofsMathematical ConceptsEducational ContentMath Tutorial
Besoin d'un résumé en anglais ?