Proof by contradiction

Definition

Proof by contradiction is a mathematical proof technique where one assumes the opposite of what is to be proven, shows that this assumption leads to a contradiction, and thus concludes that the original statement must be true. This method relies on the principle that if an assumption leads to an impossibility, then the assumption itself must be false. It's a powerful tool in various areas of logic and mathematics, especially in establishing results that involve self-reference or undecidability.

5 Must Know Facts For Your Next Test

1. Proof by contradiction often involves assuming that a statement is false and deriving a logical inconsistency or contradiction from that assumption.
2. This technique is widely used in proving theorems in number theory, such as demonstrating that the square root of 2 is irrational.
3. The First Incompleteness Theorem employs proof by contradiction to show that there are true statements in formal systems that cannot be proven within those systems.
4. Self-reference and diagonalization arguments heavily utilize proof by contradiction, particularly when demonstrating the limits of formal proofs and computability.
5. Proof by contradiction is rooted in classical logic but can also appear in various forms within intuitionistic logic, though its acceptance may differ.

Review Questions

• How does proof by contradiction help in establishing the validity of the First Incompleteness Theorem?
  • In the First Incompleteness Theorem, proof by contradiction is pivotal as it assumes that every true statement can be proven within a consistent formal system. By deriving a contradiction from this assumption—showing that there exists at least one true statement that cannot be proven—the theorem illustrates that not all truths are accessible through formal proofs, emphasizing limitations within such systems.
• In what ways does self-reference play a critical role in the effectiveness of proof by contradiction?
  • Self-reference enhances proof by contradiction's effectiveness because it allows for statements about themselves, leading to paradoxes. For example, using diagonalization, one can construct a statement that asserts its own unprovability. Assuming this statement is provable leads to contradictions, thereby confirming its unprovable nature and illustrating deeper truths about formal systems and their limitations.
• Evaluate how proof by contradiction contrasts with direct proof methods and discuss its implications in formal systems.
  • Proof by contradiction contrasts with direct proof methods as it relies on disproving an assumption rather than directly establishing a truth through logical progression. This difference highlights key implications for formal systems: while direct proofs provide constructive evidence for a statement's validity, proof by contradiction reveals inherent limitations and undecidable propositions. The interplay between these methods shapes our understanding of mathematical logic and underscores the complexity of proving foundational truths.

Related terms

Contrapositive: The contrapositive of a statement is formed by negating both the hypothesis and the conclusion and swapping them. It is logically equivalent to the original statement.

Logical Consistency: A set of statements is logically consistent if there is no contradiction among them; meaning, they can all be true at the same time.

Direct Proof: A direct proof demonstrates the truth of a statement by a straightforward chain of logical deductions from accepted axioms and previously established results.