Proof by Contradiction

Proof by contradiction is a method of mathematical proof in which the negation of a proposed statement is temporarily assumed and shown to lead to a contradiction. In classical logic, this establishes the original statement. The method is widely used in mathematics and formal logic, and is often called reductio ad absurdum or indirect proof, although those expressions can also describe broader forms of reasoning that refute assumptions through impossible consequences. (forallx.openlogicproject.org)

Logical structure

Let $P$ be the proposition to be proved, and let $\Gamma$ represent the accepted premises, such as axioms, definitions, and previously established results. The argument has the following structure:

1. Temporarily assume $\neg P$.
2. Apply valid rules of inference to $\Gamma$ and this assumption.
3. Derive a contradiction, represented by $\bot$.
4. Discharge the assumption $\neg P$ and conclude $P$.

In natural deduction, the classical rule can be expressed as

Here $\vdash$ means “is derivable from.” Discharging an assumption means that the final conclusion no longer depends on that temporary assumption, although it may still depend on the premises in $\Gamma$. (forallx.openlogicproject.org)

A contradiction may consist of a statement $Q$ and its negation $\neg Q$, or an impossibility such as $0=1$ under ordinary arithmetic assumptions. It need not directly concern $P$: any genuine contradiction derived within the argument suffices. An unexpected or implausible consequence alone is not a logical contradiction. (forallx.openlogicproject.org)

Negation and related proof methods

Correctly negating the target statement is essential. For a conditional theorem $A\rightarrow B$, its classical negation is $A\land\neg B$. A contradiction proof therefore assumes both that the hypothesis holds and that the conclusion fails. For a universally quantified statement $\forall x\,R(x)$, the negation is $\exists x\,\neg R(x)$: there is a counterexample. Negating an existence claim gives $\neg\exists x\,R(x)$, equivalently $\forall x\,\neg R(x)$. These distinctions connect the method with first-order logic. (web.stanford.edu)

Proof by contraposition is related but different. To prove $A\rightarrow B$, contraposition establishes $\neg B\rightarrow\neg A$. A contradiction proof instead assumes $A\land\neg B$ and derives impossibility. Some arguments admit either presentation, but their stated goals and temporary assumptions differ. A direct proof proceeds from the hypotheses to the conclusion without assuming the conclusion’s negation. (web.stanford.edu)

Irrationality of the square root of two

A standard example proves that $\sqrt2$ is an irrational number. Suppose instead that it is a rational number. Then

where $a,b$ are positive integers with no common factor greater than one. Squaring gives

Thus $a^2$ is even, so $a$ is even: the square of an odd integer is odd. Write $a=2k$. Substitution yields

so $b$ is also even. Consequently, $a$ and $b$ share the factor two, contradicting the choice of a fraction in lowest terms. The rationality assumption is therefore false. The lowest-terms condition is indispensable to this particular proof: merely finding an unreduced fraction would not be contradictory. (web.stanford.edu)

Infinitely many primes

Another familiar example comes from number theory. Suppose there are only finitely many prime numbers, listed as $p_1,\ldots,p_n$, and form

Because $N>1$, it has a prime divisor $q$. None of the listed primes divides $N$, since division by any $p_i$ leaves remainder one. Hence $q$ is absent from the supposedly complete list, a contradiction. Importantly, the argument does not require $N$ itself to be prime. (euclids-elements.org)

This is a contradiction-style presentation of the result associated with Euclid. Proposition IX.20 of Euclid’s Elements establishes that prime numbers exceed any assigned finite collection. Its argument can also be understood constructively as producing a prime outside a given collection, rather than initially assuming that all primes have been listed. (euclids-elements.org)

Classical and intuitionistic foundations

The general classical method involves double-negation elimination. Deriving $\bot$ from $\neg P$ first establishes $\neg\neg P$; classical logic then permits the inference to $P$. Over intuitionistic logic, unrestricted double-negation elimination and the law of excluded middle, $P\lor\neg P$, are equivalent as principles governing all propositions. (plato.stanford.edu)

Intuitionistic logic does not accept that final inference unrestrictedly. It nevertheless accepts proving a negation by assuming $P$ and deriving a contradiction, thereby establishing $\neg P$. Thus constructive reasoning does not prohibit every argument involving contradiction. The irrationality proof above establishes the negative claim that no rational representation exists and does not require unrestricted elimination of double negation. (plato.stanford.edu)

Formal use and limitations

In formal proofs, assumption scope matters: conclusions obtained inside a temporary subproof cannot simply be carried outside it without an appropriate inference rule. Contradiction rules make this bookkeeping explicit and distinguish a legitimate reductio from an argument that silently retains its rejected assumption. (forallx.openlogicproject.org)

A contradiction also concerns the premises collectively. If the background premises already entail impossibility, deriving a contradiction after adding $\neg P$ does not independently establish that the background theory is sound. Classical logic permits arbitrary conclusions from contradictory premises. Paraconsistent logic rejects this unrestricted principle, so classical contradiction rules cannot automatically be transferred unchanged to every logical system. (plato.stanford.edu)