Professional Courses
Industry-relevant training in Business, Technology, and Design to help professionals and graduates upskill for real-world careers.
Categories
Interactive Games
Fun, engaging games to boost memory, math fluency, typing speed, and English skills—perfect for learners of all ages.
Typing
Memory
Math
English Adventures
Knowledge
Enroll to start learning
You’ve not yet enrolled in this course. Please enroll for free to listen to audio lessons, classroom podcasts and take practice test.
Interactive Audio Lesson
Listen to a student-teacher conversation explaining the topic in a relatable way.
Introduction to Proof by Contradiction
Unlock Audio Lesson
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.
Contrapositive Proof
Unlock Audio Lesson
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.
Vacuous Proof
Unlock Audio Lesson
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.
Revisiting Proof by Contradiction
Unlock Audio Lesson
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.
Introduction & Overview
Read a summary of the section's main ideas. Choose from Basic, Medium, or Detailed.
Quick Overview
Standard
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
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.
Youtube Videos
Audio Book
Dive deep into the subject with an immersive audiobook experience.
Understanding Proof by Contradiction
Unlock Audio Book
Signup and Enroll to the course for listening the Audio Book
We 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.
Applying Proof by Contradiction
Unlock Audio Book
Signup and Enroll to the course for listening the Audio Book
So 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).
Conclusion of Proof by Contradiction
Unlock Audio Book
Signup and Enroll to the course for listening the Audio Book
So 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.
Definitions & Key Concepts
Learn essential terms and foundational ideas that form the basis of the topic.
Key Concepts
-
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 & Real-Life Applications
See how the concepts apply in real-world scenarios to understand their practical implications.
Examples
-
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
Use mnemonics, acronyms, or visual cues to help remember key information more easily.
🎵 Rhymes Time
-
When you contradict, to find what's true, assume the false, then check what's new.
📖 Fascinating Stories
-
Imagine a detective who assumes the suspect is innocent, but every clue leads to contradictions, proving their guilt.
🧠 Other Memory Gems
-
Remember 'PROOF': 'Premise, Reverse, Observe, Outcome, Find contradiction' for proof by contradiction.
🎯 Super Acronyms
CAVe
- Contradiction
- Assumption
- Validity
- Example - a way to remember different aspects of contradictions.
Flash Cards
Review key concepts with flashcards.
Glossary of Terms
Review the Definitions for terms.
-
Term: Proof by Contradiction
Definition:
A proof technique that assumes the negation of what one seeks to prove, leads to a contradiction, thus confirming the original statement.
-
Term: Contrapositive
Definition:
The statement formed by negating both the hypothesis and the conclusion of an implication, and reversing them.
-
Term: Vacuous Proof
Definition:
A proof that shows an implication is true by establishing that the premise is false.