Loading the lesson
Loading the lesson
Search AllRounder.ai
Search the courses, subjects, tracks, games and features, or jump straight to a page.
Search the courses, subjects, tracks, games and features, or jump straight to a page.
Learn it your way
A short class with Sarah and her students. The other ways are under More.
Sign up free to listen. Transcripts are free to read.
Today, we’ll explore proof by contradiction. To start, can anyone explain what they think it means when we say a mathematical statement is proven by contradiction?
I think it means we assume the opposite of the statement and see if that leads to something impossible.
Exactly! By assuming the contrary, if we arrive at a contradiction, we confirm our original statement is true. We often use this for implications like p → q. Let's break down that process!
Can you give us an example of how that works?
Sure! For instance, if we want to prove that if 3n + 2 is odd, then n is odd, we could start by assuming n is even and see where that leads us.
Now, let's move on to proof by contrapositive. Can anyone tell me what it means?
I think it’s when we prove p → q by showing ¬q → ¬p instead?
Exactly right! This method relies on the fact that these two statements are logically equivalent. Can anyone give an example of how we might apply this?
If 3n + 2 is even, then n is even?
Great example! By proving this, you automatically prove the original implication. Always remember, if one is false, the other must be too.
Next, let’s talk about vacuous proofs. Do you know what it means for a statement to be vacuously true?
It sounds like it’s true because the premise is false?
That's right! If the premise is false, then the implication is true, regardless of whether the conclusion is true or false. For example, if we say 'If 0 > 1, then 0^2 > 0,' since 0 is not greater than 1, this statement is vacuously true.
Can you show us another example?
Absolutely! Consider the statement, 'If n is a negative integer, then n is greater than 1'. Since there are no negative integers greater than 1, this is also vacuously true.
Let’s revisit proof by contradiction with more depth. How would we prove that √2 is irrational using this method?
We would assume that it’s rational and could be expressed as a fraction?
Correct! By assuming it's rational and in lowest terms, we deduce that both numerator and denominator must be even, leading to a contradiction. What does this tell us?
That means√2 can't be rational!
Precisely! This is how contradiction helps us confirm truths in mathematics.
A method of proving that a statement is true by demonstrating that its negation leads to a logically impossible situation.
The equivalence between the implication p → q and its contrapositive ¬q → ¬p, which can be used to prove the original statement.
A situation in which an implication is considered true because its hypothesis is false.
When you contradict, to find what's true, assume the false, then check what's new.
Imagine a detective who assumes the suspect is innocent, but every clue leads to contradictions, proving their guilt.
Remember 'PROOF': 'Premise, Reverse, Observe, Outcome, Find contradiction' for proof by contradiction.
CAVe: Contradiction, Assumption, Validity, Example - a way to remember different aspects of contradictions.
Term
Proof by Contradiction
Click to flip
Term
Contrapositive
Click to flip
Term
Vacuous Truth
Click to flip
A proof technique that assumes the negation of what one seeks to prove, leads to a contradiction, thus confirming the original statement.
The statement formed by negating both the hypothesis and the conclusion of an implication, and reversing them.
A proof that shows an implication is true by establishing that the premise is false.
Proof by contradiction is a method that shows the truth of an implication by assuming the contrary leads to a false conclusion.
This section outlines proof by contradiction as an indirect method to establish the validity of implications. Key methods such as proof by contrapositive, vacuous proof, and proof by contradiction itself are discussed, along with examples illustrating how these techniques are applied in mathematical reasoning.
In this section, we explore proof by contradiction, an indirect proof method used to affirm the truth of statements of the form p → q. This technique is grounded in the principle that if assuming the opposite leads to a contradiction, then the statement must be true. We also discuss various indirect proof strategies: proof by contrapositive, vacuous proof, and proof by contradiction, particularly focusing on the nature of implication statements and their proofs.
An illustrative example demonstrated the process of using proof by contradiction to show that if 3n + 2 is odd, n must also be odd, effectively utilizing the assumption of n being even to arrive at a contradiction. The importance and applications of these techniques are tied to their utility in establishing broader implications in mathematical proofs.