How to Perform a Proof by Contradiction: A Comprehensive Guide
Proof by contradiction is a powerful and widely used mathematical technique. It works by assuming the opposite of what you want to prove and demonstrating that this assumption leads to a logical contradiction. If a contradiction is reached, then the original statement must be true. This article provides a detailed step-by-step guide on how to perform a proof by contradiction.
Steps for Proof by Contradiction
State the Proposition
Clearly define the statement P that you want to prove. This step sets the context for your proof and ensures that everyone understands the statement in the same way.
Assume the Opposite
Assume that the proposition P is false. This means you will assume neg P, or the negation of P. By assuming the opposite, you aim to derive a contradiction from this assumption.
Use logical reasoning and previously established facts to derive consequences from the assumption neg P. This may involve definitions, theorems, or axioms relevant to your statement. It is crucial to build a logical and rigorous argument by connecting each step with the previous one.
Continue deriving consequences until you arrive at a contradiction. A contradiction is a statement that cannot be true, such as A and neg A. In the realm of mathematics, a common type of contradiction involves a statement that contradicts a well-known and accepted fact or a previously established theorem.
Since assuming neg P leads to a contradiction, you can conclude that the original proposition P must be true. This conclusion is a direct consequence of the logical steps you have taken and the contradiction you have reached.
Example: Proving That sqrt{2} is Irrational Using Proof by Contradiction
Proposition
To illustrate the proof by contradiction, let’s prove that sqrt{2} is irrational.
Assume the Opposite
Assume that sqrt{2} is rational. This means it can be expressed as a fraction frac{a}{b}, where a and b are integers with no common factors and b eq 0.
Starting from the assumption, we derive the following consequences:
sqrt{2} frac{a}{b} implies 2 frac{a^2}{b^2} implies a^2 2b^2
This implies a^2 is even, which means a must also be even, since the square of an odd number is odd.
Let a 2k for some integer k implies
a^2 4k^2 implies 4k^2 2b^2 implies 2k^2 b^2
This implies b^2 is even, so b must also be even.
Since both a and b are even, they have a common factor of 2, which contradicts the assumption that frac{a}{b} is in simplest form.
Thus, our assumption that sqrt{2} is rational must be false. Therefore sqrt{2} is irrational.
Conclusion
Proof by contradiction is a powerful tool in mathematics. It allows us to establish the truth of a statement by assuming the opposite and demonstrating that this assumption leads to a contradiction. This method is widely used in various fields of mathematics to prove a wide range of statements. Whether you are working on a complex proof in number theory or a simpler problem in logic, understanding and mastering proof by contradiction can greatly enhance your mathematical reasoning skills.