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

Esta sección está disponible solo para usuarios con suscripción. Por favor, mejora tu plan para acceder a esta parte.

Mejorar ahora

Mindmap

plate

Esta sección está disponible solo para usuarios con suscripción. Por favor, mejora tu plan para acceder a esta parte.

Mejorar ahora

Keywords

plate

Esta sección está disponible solo para usuarios con suscripción. Por favor, mejora tu plan para acceder a esta parte.

Mejorar ahora

Highlights

plate

Esta sección está disponible solo para usuarios con suscripción. Por favor, mejora tu plan para acceder a esta parte.

Mejorar ahora

Transcripts

plate

Esta sección está disponible solo para usuarios con suscripción. Por favor, mejora tu plan para acceder a esta parte.

Mejorar ahora
Rate This

5.0 / 5 (0 votes)

Etiquetas Relacionadas
Proof by ContradictionDiscrete MathRational NumbersIrrationalitySet TheoryAlgebraic ManipulationLogical ProofsMathematical ConceptsEducational ContentMath Tutorial
¿Necesitas un resumen en inglés?