2.7 Proof by contradiction

Proof by contradiction is a powerful mathematical technique that indirectly proves a statement by assuming its opposite and showing it leads to a logical impossibility. This method relies on the principle of non-contradiction and the law of excluded middle, forming a cornerstone of mathematical reasoning.

This approach is particularly useful for proving non-existence or uniqueness claims, often leading to elegant solutions for complex problems. It enhances critical thinking skills by requiring careful analysis of assumptions and their implications, demonstrating the power of logical deduction in mathematics.

Definition and purpose

• Proof by contradiction forms a cornerstone of mathematical reasoning used to establish the truth of a statement indirectly
• Demonstrates the power of logical deduction in mathematics by exploring the consequences of assuming a statement is false
• Enhances critical thinking skills essential for mathematicians by requiring careful analysis of assumptions and implications

Concept of contradiction

Top images from around the web for Concept of contradiction

• 

  elementary number theory - Understanding the proof of "$\sqrt{2}$ is irrational" by ... View original

  Is this image relevant?

• 

  Reductio ad absurdum – Wikipédia View original

  Is this image relevant?

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  elementary number theory - Understanding the proof of "$\sqrt{2}$ is irrational" by ... View original

  Is this image relevant?

• 

  Reductio ad absurdum – Wikipédia View original

  Is this image relevant?

1 of 3

Top images from around the web for Concept of contradiction

• 

  elementary number theory - Understanding the proof of "$\sqrt{2}$ is irrational" by ... View original

  Is this image relevant?

• 

  Reductio ad absurdum – Wikipédia View original

  Is this image relevant?

• 

  Propositional Logic Proof using I.P. or C.P or rules of inference - Mathematics Stack Exchange View original

  Is this image relevant?

• 

  elementary number theory - Understanding the proof of "$\sqrt{2}$ is irrational" by ... View original

  Is this image relevant?

• 

  Reductio ad absurdum – Wikipédia View original

  Is this image relevant?

1 of 3

• Involves assuming the opposite of what we want to prove leads to a logical impossibility
• Relies on the principle of non-contradiction in classical logic where a statement and its negation cannot both be true
• Utilizes reductio ad absurdum technique to show that assuming the negation of a proposition results in a contradiction
• Often employed when direct proofs prove challenging or impossible

Logical foundations

• Based on the law of excluded middle which states a proposition must be either true or false, with no third option
• Employs propositional logic to construct valid arguments and identify contradictions
• Requires understanding of logical connectives (and, or, not) and their truth tables
• Builds upon the concept of logical implication (if-then statements) to derive contradictions

Structure of proof

Steps in contradiction proof

• Begin by clearly stating the proposition to be proved
• Assume the negation of the proposition is true
• Derive logical consequences from this assumption using valid deductive reasoning
• Identify a contradiction between the derived consequences and known mathematical facts
• Conclude that the original assumption must be false, therefore the proposition is true
• Ensure each step in the proof is rigorously justified and logically sound

Assumption of falsehood

• Temporarily accept the opposite of what we aim to prove as true
• Explore the implications of this assumption through a series of logical deductions
• Seek to uncover inconsistencies or impossibilities that arise from the assumption
• Requires careful consideration of the precise negation of the original statement
• May involve working with inequalities, set complements, or logical negations depending on the proposition

Common applications

Number theory proofs

• Prove the irrationality of certain numbers (√2, √3, etc.)
• Demonstrate the infinitude of prime numbers
• Establish properties of divisibility and factorization
• Prove the existence or non-existence of solutions to Diophantine equations
• Verify conjectures about number sequences or patterns

Geometry proofs

• Establish the impossibility of certain geometric constructions (trisecting an angle with compass and straightedge)
• Prove the existence of unique geometric objects or configurations
• Demonstrate properties of parallel lines and angles
• Verify theorems about triangles, circles, and other geometric shapes
• Prove the uniqueness of certain geometric transformations or symmetries

Examples of famous proofs

Irrationality of square root 2

• Assume √2 is rational, expressed as a fraction a/b in lowest terms
• Square both sides: 2 = a²/b²
• Multiply by b²: 2b² = a²
• Conclude a² is even, so a must be even
• Express a as 2k, substitute: 2b² = (2k)² = 4k²
• Simplify: b² = 2k²
• Conclude b² is even, so b must be even
• Contradiction: a and b cannot both be even if fraction is in lowest terms
• Therefore, √2 must be irrational

Infinite primes

• Assume there are finitely many primes: p₁, p₂, ..., pₙ
• Construct a new number N = (p₁ × p₂ × ... × pₙ) + 1
• N is either prime or not prime
• If N is prime, it's larger than all primes in the list, contradicting the assumption
• If N is not prime, it has a prime factor not in the list (as dividing by any prime in the list leaves remainder 1)
• In both cases, we find a prime not in the original finite list
• Contradiction: the assumption of finitely many primes must be false
• Therefore, there are infinitely many primes

Strengths and limitations

Power of indirect reasoning

• Allows proving statements that may be difficult or impossible to demonstrate directly
• Particularly useful for establishing non-existence or uniqueness claims
• Provides a systematic approach to explore logical consequences of assumptions
• Often leads to elegant and concise proofs for complex mathematical statements
• Enhances understanding of the underlying logical structure of mathematical concepts

Potential pitfalls

• Risk of circular reasoning if not carefully constructed
• May not provide constructive information about why a statement is true
• Can be less intuitive or harder to follow than direct proofs for some readers
• Requires precise formulation of the negation of the original statement
• May lead to unnecessarily complex arguments if a simpler direct proof exists

Comparison with other methods

Direct proof vs contradiction

• Direct proofs proceed from known facts to the desired conclusion
• Contradiction proofs assume the negation and derive an impossibility
• Direct proofs often provide more insight into why a statement is true
• Contradiction can be more powerful for proving negative or universal statements
• Direct proofs typically follow a more linear logical path
• Contradiction proofs may involve more complex logical structures

Contraposition vs contradiction

• Contraposition proves "if P, then Q" by showing "if not Q, then not P"
• Contradiction assumes "P and not Q" to derive a logical impossibility
• Contraposition maintains a direct logical flow, while contradiction explores consequences of an assumption
• Both methods rely on the logical equivalence of a statement and its contrapositive
• Contraposition often leads to more straightforward proofs for conditional statements
• Contradiction can be more versatile for a wider range of mathematical propositions

Historical development

Ancient Greek contributions

• Originated with early Greek mathematicians and philosophers
• Zeno of Elea (c. 490-430 BCE) used contradiction in his famous paradoxes
• Euclid (c. 300 BCE) employed proof by contradiction in his Elements
• Aristotle (384-322 BCE) formalized the law of non-contradiction in logic
• Pythagoras (c. 570-495 BCE) and his followers likely used contradiction to prove irrationality of √2

Modern refinements

• Development of formal logic in 19th and 20th centuries enhanced rigor of contradiction proofs
• Georg Cantor (1845-1918) used contradiction to prove uncountability of real numbers
• Kurt Gödel (1906-1978) employed contradiction in his incompleteness theorems
• Intuitionistic logic challenged universal acceptance of proof by contradiction
• Computational proof assistants now aid in verifying complex contradiction arguments

Practical problem-solving

Identifying contradictory scenarios

• Analyze problem statements to recognize potential contradictions
• Look for mutually exclusive conditions or properties
• Consider extreme cases or boundary conditions that may lead to contradictions
• Examine the logical structure of given information for inconsistencies
• Develop intuition for recognizing situations where indirect reasoning may be effective

Constructing effective arguments

• Clearly state the proposition to be proved at the outset
• Formulate a precise negation of the proposition
• Develop a logical chain of deductions from the negated assumption
• Identify key steps that lead to the contradiction
• Ensure each logical inference is justified and clearly explained
• Conclude by explicitly stating how the contradiction proves the original proposition

Advanced techniques

Double contradiction

• Involves assuming the negation of two related statements simultaneously
• Used to prove equivalence between two seemingly different propositions
• Requires careful analysis of the logical relationships between multiple statements
• Often employed in more complex mathematical arguments or abstract algebra
• Can lead to powerful results by exploring multiple contradictory scenarios

Proof by infinite descent

• Special form of contradiction used primarily in number theory
• Assumes existence of a smallest positive integer with a certain property
• Shows that a smaller positive integer with the same property must exist
• Contradicts the assumption of a smallest such integer
• Particularly useful for proving non-existence of certain types of numbers or solutions
• Employed in famous proofs like Fermat's method of infinite descent