Proof by contradiction

A mathematical proof employing proof by contradiction usually proceeds as follows:

In either case, we established P. It turns out that, conversely, proof by contradiction can be used to derive the law of excluded middle.

Refutation by contradiction applies only when the proposition to be proved is negated, whereas proof by contradiction may be applied to any proposition whatsoever.

The law of non-contradiction neither follows nor is implied by the principle of Proof by contradiction.

In intuitionistic logic proof by contradiction is not generally valid, although some particular instances can be derived. In contrast, proof of negation and principle of noncontradiction are both intuitionistically valid.

Brouwer–Heyting–Kolmogorov interpretation of proof by contradiction gives the following intuitionistic validity condition:

"If there is no method for establishing that a proposition is false, then there is a method for establishing that the proposition is true."
If in a triangle two angles equal one another, then the sides opposite the equal angles also equal one another.

The proof proceeds by assuming that the opposite angles are not equal, and derives a contradiction.

Depending on how we formally write the above statement, the usual proof takes either the form of a proof by contradiction or a refutation by contradiction. We present here the former, see below how the proof is done as refutation by contradiction.

We may read the statement as saying that for every finite list of primes, there is another prime not on that list, which is arguably closer to and in the same spirit as Euclid's original formulation. In this case Euclid's proof applies refutation by contradiction at one step, as follows.

Proof by infinite descent is a method of proof whereby a smallest object with desired property is shown not to exist as follows:

Russell's paradox, stated set-theoretically as "there is no set whose elements are precisely those sets that do not contain themselves", is a negated statement whose usual proof is a refutation by contradiction.