Product Design, Manufacturing & Innovation Resources
Home » Proof by Contradiction (reductio ad absurdum)

Proof by Contradiction (reductio ad absurdum)

-400
Scholar engaged in proof by contradiction in an ancient library setting.

(generated image for illustration only)

Proof by contradiction, or reductio ad absurdum, is a form of indirect proof. It establishes the truth of a proposition by showing that assuming the proposition to be false leads to a logical contradiction. To prove a proposition \(p\), one assumes its negation, \(\neg p\), and deduces a contradiction, such as \(q \land \neg q\), thereby concluding that \(p\) must be true.

The logical foundation for proof by contradiction is the law of non-contradiction, which states that a proposition cannot be both true and false, and the law of the excluded middle, which states that a proposition must be either true or false. The method begins by assuming the opposite of what one wants to prove. For example, to prove that the square root of 2 is irrational, one starts by assuming it is rational. If \(\sqrt{2}\) is rational, it can be expressed as a fraction \(a/b\) in lowest terms, where a and b are integers. This leads to \(2 = a^2/b^2\), or \(a^2 = 2b^2\). This implies \(a^2\) is even, which means \(a\) must also be even. So, \(a = 2k\) for some integer k. Substituting this back gives \((2k)^2 = 2b^2\), or \(4k^2 = 2b^2\), which simplifies to \(2k^2 = b^2\). This means \(b^2\) is even, and therefore \(b\) is also even. If both a and b are even, the fraction \(a/b\) was not in lowest terms, which contradicts the initial assumption. This contradiction forces the conclusion that the initial assumption—that \(\sqrt{2}\) is rational—must be false. This method is powerful but can be non-constructive, as it proves a statement is true without providing a direct example or construction.

UNESCO Nomenclature: 1201
– Logic

Type

Abstract System

Disruption

Foundational

Usage

Widespread Use

Precursors

  • Socratic method of Elenchus (cross-examination)
  • Eleatic school of philosophy (e.g., Zeno’s paradoxes)
  • Development of formal logic by Aristotle

Applications

  • Euclid’s proof of the infinitude of prime numbers
  • proof of the irrationality of the square root of 2
  • Cantor’s diagonal argument showing the uncountability of real numbers
  • proving the halting problem is undecidable in computer science

Patents:

NA

Potential Innovations Ideas

Due to scrapping bot traffic, currently more than 40k per day, this content is reserved to community members.
> Login < or > Register < (100% free) to access this, so as all other restricted content and tools.

Related to: contradiction, reductio ad absurdum, indirect proof, irrational numbers, logic, law of non-contradiction, negation, assumption, Cantor, halting problem.

Historical Context

Proof by Contradiction (reductio ad absurdum)

-300
-300
-300
-400
-550
1635
1650
1736
-300
-300
-350
-500
150
1640
1650

(if date is unknown or not relevant, e.g. "fluid mechanics", a rounded estimation of its notable emergence is provided)

Related Invention, Innovation & Technical Principles

Full size images and downloads are only available, 100% free, for registered members.

> Login <