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.1. Using Proof by Contradiction for Single Proposition
Learn content
Interactive Audio Lesson
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Today, we're going to explore proof by contradiction, a powerful tool in mathematics. Can anyone explain what they think this method involves?
I think it means assuming a statement is wrong and seeing if it leads to a contradiction?
Exactly! By assuming the opposite of what we want to prove, we can arrive at a contradiction, which allows us to affirm the original statement. Let’s solidify this with an example: if I wanted to prove that 'if p then q' is true, I assume that p is true but q is false. What would that entail?
It sounds like we would show something doesn’t add up, right?
Precisely! If we derive a logical inconsistency from our assumption, that shows our original implication must hold. So, let’s summarize: proof by contradiction involves assuming the negation and finding that it leads to an unfounded conclusion.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Now, let’s look at a concrete example: proving that √2 is irrational. How might we start this proof?
We could assume it is rational, right? Like, say it can be expressed as a fraction a/b?
Correct! So we assume √2 = a/b. Then we derive conclusions based on this assumption. What would we do next?
We’ll square both sides to show a² = 2b², then we can argue about the properties of a and b.
Exactly! From here, we notice that if a² is even, then a must also be even. How does that affect our assumptions about a and b?
If a is even, then, by substitution, b must also be even, which contradicts our initial statement that a/b is in simplest form.
Very well! This contradiction verifies that our assumption of √2 being rational is false, hence proving it is irrational. Remember, contradictions validate our original assertion.
Unlock the classroom podcast
The transcript is free to read. A free account plays the conversation back.
Why do you think proof by contradiction is a useful method in mathematics?
Because it gives us a way to prove statements that might be difficult to show directly?
Exactly! Some statements can be quite complex, making a direct proof cumbersome or impossible. By proving the opposite leads to a fallacy, we can effectively establish our statement's validity.
Are there situations where proof by contradiction wouldn’t be effective?
Good question! While contradiction is powerful, it may not always provide the most efficient path for certain problems. It’s essential to evaluate the best proof method based on context. Let’s recap today’s session!
It seems like contradiction can really help clarify difficult proofs.
Exactly! Proof by contradiction is a valuable technique, especially in establishing truths that are otherwise ambiguous. Keep practicing these methods!
Overview
Short Summary
This section explains the proof by contradiction method for establishing the truth of a single proposition.
Medium Summary
In this section, we explore the proof by contradiction technique, demonstrating its effectiveness in proving the validity of a given proposition by assuming its negation leads to a contradiction.
Detailed Summary
Using Proof by Contradiction for Single Proposition
Proof by contradiction is a powerful method used in mathematics to establish the truth of a proposition. The core idea revolves around assuming that the proposition in question is false and demonstrating that this assumption leads to a logical contradiction. In simpler terms, if assuming a statement is false forces us to conclude both that the statement is true and not true simultaneously, we can conclude that the original statement must indeed be true.
The logic follows that if we assert a proposition p and find that its negation (¬p) leads us to falsehood (F), we validate that p cannot be false. For example, consider the statement "√2 is irrational." By assuming the opposite—that √2 is rational—and deriving contradictions through logical deductions, we can effectively argue that √2 must be irrational. Thus, this proof method not only applies to implications but can also be skillfully used to validate individual propositions.
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 accountIt turns out that we can use the proof by contradiction method even to prove that a single proposition p is true, we use proof by contradiction in the previous slide to prove the truth of an implication namely p → q, but you can use the proof by contradiction method even to prove that a statement a single statement p is true.
Detailed Explanation
The proof by contradiction method is a powerful tool in mathematics. Instead of proving a statement directly, we first assume that the statement is false. If we can show that this assumption leads to a contradiction—a situation that cannot logically occur—then we conclude that our original statement must be true. This method allows us to explore the consequences of assuming the negation of our desired conclusion.
Examples & Analogies
Imagine you're trying to prove that a specific road leads to a town. Instead of going to the town directly, you assume the road does not lead there. As you follow the road, you find that it meets other roads that all eventually reach the town, which creates a contradiction. This contradiction indicates that your assumption was wrong, and therefore, the road must indeed lead to that town.
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 accountThis is based on the following idea: this is based on the idea that negation of p implies conjunction of r and negation of r is logically equivalent to ¬ p → F that means your goal is to show p is true.
Detailed Explanation
In proofs by contradiction, we focus on the negation of the statement we wish to prove. If we denote the statement we want to prove as p, asserting 'p is true,' we examine what occurs when we assume '¬p' (the negation of p) is true. If from this assumption, we can evoke statements that lead to a contradiction (like showing r and ¬r both hold), it indicates that the assumption that ¬p must be incorrect, confirming that p is indeed true.
Examples & Analogies
Think of a scenario where someone claims there are no apples left in the basket. You decide to prove them wrong by assuming no apples are present (¬p). If you then open the basket and find apples (proving r), but also discover those same apples contradicting another statement (¬r), you arrive at a contradiction. Since both cannot be true, the original claim that there are no apples must be false—indicating there are indeed apples!
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 let us see how this proof method is applicable to prove that √2 is irrational, so what I do here: is this is the statement p that I want to prove, my proposition p which I want to prove here is that √2 is irrational, I assume a negation of that, that means on contrary I assume that the √2 is rational that means I am now assuming negation p is true and based on that I have to come to a false conclusion.
Detailed Explanation
To use proof by contradiction to show that √2 is irrational, we assume the opposite: that √2 is rational. According to the definition of rational numbers, it can be expressed as a fraction a/b, where a and b are integers with no common factors. Squaring both sides leads to the conclusion that both numbers must be even, which implies that they share a common factor of 2, contradicting our stipulation that a and b had no common factors. Thus, our assumption that √2 is rational must be false, confirming that √2 is indeed irrational.
Examples & Analogies
Consider a magician claiming to perform a trick where they pull a rabbit out of an empty hat. You start off by assuming that the hat is empty (¬p). But upon checking, you not only find a rabbit (r) but also that the hat contains other surprises, which contradict the overall illusion (¬r). In conclusion, the assumption that the hat was empty leads to an impossibility, proving that there must be something hidden inside—the rabbit demonstrates that rationality can produce unexpected results!
--
Key concepts
Core takeaways and short definitions to help you quickly recall the key ideas from this section.
- Proof by Contradiction:
Assume that the proposition is false and derive contradictions.
- Negation:
A fundamental aspect of logical reasoning where the opposite of a statement is considered.
- Logical Consistency:
Understanding that two contradictory statements cannot be true at the same time, forming the basis for contradictions.
Examples
Step-by-step examples to apply the section's ideas and test your understanding.
To show that √2 is irrational, we assume the contrary and reach a conclusion where both a/b is rational and not rational, illustrating contradiction.
If we assert a statement such as 'All swans are white' and find a black swan, the contradiction confirms the falseness of the initial assertion.
Memory aids
If what you assume brings you strife, a contradiction ends the strife. Assume it’s false, then take a look, if it leads to nonsense, the proof's in the book.
Imagine a detective assuming a suspect is innocent, but every clue leads to their guilt. The conclusion contradicts the assumption, proving they are indeed guilty.
C.A.L.M. - Contradict Assume Leads Misleading. This helps to remember the steps of assuming negation in proofs.
Flash Cards
Glossary
Proof by Contradiction
A proof technique that assumes the negation of a statement and shows that this assumption leads to a contradiction.
Negation
The opposite of a statement, typically denoted by ¬p, which alters the truth value of the original proposition.
Logical Contradiction
A situation in which two or more propositions cannot be true at the same time.
Rational Number
A number that can be expressed as a fraction of two integers.