Proof by Contradiction

Definition

Proof by contradiction is a mathematical technique used to establish the truth of a statement by assuming the opposite of what you want to prove and showing that this assumption leads to a contradiction. This method is significant because it often allows mathematicians to prove results that are difficult or impossible to establish directly. It is a powerful tool for demonstrating the validity of various mathematical concepts and theorems.

5 Must Know Facts For Your Next Test

1. Proof by contradiction is often applied in mathematical proofs involving existential quantifiers, where you assume that an element does not exist and show that this leads to an impossible situation.
2. This technique can be particularly useful in proving theorems in number theory, such as the irrationality of certain numbers, including $$\sqrt{2}$$.
3. In this method, once a contradiction is reached, it confirms that the initial assumption must be false, thus validating the original statement.
4. Proof by contradiction relies heavily on the principle of the excluded middle, which states that for any proposition, either that proposition is true or its negation is true.
5. While proof by contradiction can be powerful, it's important to understand its limitations and ensure that all assumptions made during the proof are valid.

Review Questions

• How can proof by contradiction be applied in proving that a certain number is irrational?
  • Proof by contradiction can be effectively used to show that a number like $$\sqrt{2}$$ is irrational. You start by assuming the opposite, that $$\sqrt{2}$$ is rational, meaning it can be expressed as a fraction of two integers. Then, through logical reasoning, you derive that both integers must be even, which contradicts the assumption that they are in simplest form. This contradiction implies that the initial assumption was wrong, confirming that $$\sqrt{2}$$ is indeed irrational.
• Discuss how proof by contradiction relates to the concept of logical contradiction and provide an example.
  • Proof by contradiction directly involves the concept of logical contradiction, as it relies on demonstrating that assuming the negation of a statement leads to an impossible scenario. For example, if you want to prove that there are infinitely many prime numbers, you assume there are finitely many primes and consider their product plus one. This new number cannot be divisible by any of those primes, leading to a contradiction. Hence, it proves there must be infinitely many primes.
• Evaluate the effectiveness of proof by contradiction compared to direct proof and discuss scenarios where one might be preferred over the other.
  • Proof by contradiction can be more effective than direct proof in cases where direct reasoning becomes convoluted or overly complex. For instance, when dealing with statements involving infinite sets or properties of numbers, proof by contradiction often provides clearer insights into their truth. However, direct proofs are usually more straightforward and easier for readers to follow. Mathematicians may prefer one method over the other depending on the context: direct proofs are favored for simple statements while proof by contradiction shines in complex arguments where an assumption leads to an impossibility.

Related terms

Contrapositive: The contrapositive of a statement 'If P, then Q' is 'If not Q, then not P', which is logically equivalent to the original statement.

Logical Contradiction: A logical contradiction occurs when two or more statements are in direct opposition, meaning they cannot all be true at the same time.

Direct Proof: A direct proof establishes the truth of a statement by a straightforward chain of logical deductions from accepted premises or axioms.