Enrol to start learning
Reading is open to everyone. Enrolling is free, and it is what unlocks the audio lessons, practice tests and progress tracking.
10.1.3.3. Proof by Contradiction
Learn content
Interactive Audio Lesson
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
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.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
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.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
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.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
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.
Overview
Short Summary
Proof by contradiction is a method that shows the truth of an implication by assuming the contrary leads to a false conclusion.
Medium Summary
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.
Detailed Summary
Proof by Contradiction
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.
Key Methods Explained:
- Proof by Contradiction: This involves assuming both p (premise) is true and ¬q (negation of conclusion) is true, and demonstrating that this assumption leads to a logical contradiction.
- Proof by Contrapositive: This technique proves p → q by validating ¬q → ¬p, highlighting the equivalency between direct implications and their contrapositives.
- Vacuous Proof: A statement of the form p → q holds true if p is false, regardless of the truth of q.
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.
Reference YouTube Videos
Audio Book
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountWe can prove p → q even by contradiction method, which is an indirect proof method for proving p → q and this is based on the idea that p → q is logically equivalent to p conjunction ¬q → F. You can easily verify that you can draw the truth table of p → q and you can draw the truth table of this RHS expression and both the truth tables are same.
Detailed Explanation
Proof by contradiction is a method where we assume that the statement we want to disprove is true and try to reach a contradiction. We note that the implication (p → q) is logically equivalent to the conjunction of p and the negation of q (p ∧ ¬q) leading to a false statement (F). This means if assuming p to be true and q to be false leads to a contradiction, then we must conclude that q is true when p is true.
Examples & Analogies
Imagine a light bulb that either works (true) or doesn’t work (false). If you assume the light bulb does not work when it’s plugged in (p is true), but then find out it is actually working (q must be true), you’ve reached a contradiction. Thus, your original assumption is wrong, implying that when it’s plugged in, it must be working.
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountSo if I want to prove this statement that if 3n + 2 is odd then n is odd, we had already proved it by proof by contrapositive but let’s see a proof by contradiction method. So this part is your p part; this part is your q part.
Detailed Explanation
To demonstrate this proof, we start with our premise: assume 3n + 2 is odd (p) and simultaneously assume n is even (¬q). Under this assumption, we check if we can derive a contradiction. We calculate that if n is even, we can express it as 2k, leading to 3n + 2 being even, which contradicts the assumption that it is odd. Therefore, both assumptions cannot hold, demonstrating n must be odd when 3n + 2 is odd.
Examples & Analogies
Think of a classroom rule: if a student is on time (p), they can attend class (q). Now, if you assume a student shows up late (¬q), you find out that, regardless of being on time, they can't be considered punctual. Thus, you’ve created a contradiction; that implies they couldn’t have been late if they were allowed to attend, showcasing you need to be on time (p) to be in class (q).
Unlock the audio lesson
The script is above and free to read. A free account plays it back, in the voice you pick.
Create a free accountSo you can see that how do we get a contradiction here? We started with the premise 3n + 2 to be odd and we assumed n to be even based on these two premises or these two statements, I come to the conclusion that 3n + 2 is even.
Detailed Explanation
In the final part of the proof, we derive that our assumptions lead to a situation where 3n + 2 is simultaneously odd and even. This scenario cannot happen in logical terms, as a statement and its negation cannot both be true at the same time. Thus, the conclusion confirms the correctness of the original implication p → q, indicating that if 3n + 2 is odd, then n must be odd as well.
Examples & Analogies
Imagine a coin that you flipped supposedly shows heads if it’s not a tails coin. The contradictory assumption that it can show both one side and the other fails, helping you realize that there’s no possible way it can be both heads and tails simultaneously. This forms the basis of contradiction, cementing your result and validating your conclusion.
--
Key concepts
Core takeaways and short definitions to help you quickly recall the key ideas from this section.
- Proof by Contradiction:
A method of proving that a statement is true by demonstrating that its negation leads to a logically impossible situation.
- Contrapositive:
The equivalence between the implication p → q and its contrapositive ¬q → ¬p, which can be used to prove the original statement.
- Vacuous Truth:
A situation in which an implication is considered true because its hypothesis is false.
Examples
Step-by-step examples to apply the section's ideas and test your understanding.
Example of Proof by Contradiction: To show that if 3n + 2 is odd, then n must be odd, we assume that n is even and show it leads to a contradiction.
Vacuous Example: The statement 'If 0 > 1, then 0^2 > 0' is vacuously true since the premise (0 > 1) is false.
Memory aids
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.
Flash Cards
Glossary
Proof by Contradiction
A proof technique that assumes the negation of what one seeks to prove, leads to a contradiction, thus confirming the original statement.
Contrapositive
The statement formed by negating both the hypothesis and the conclusion of an implication, and reversing them.
Vacuous Proof
A proof that shows an implication is true by establishing that the premise is false.