Editing Proof by contradiction (section)

==Examples of refutations by contradiction==

The following examples are commonly referred to as proofs by contradiction, but formally employ refutation by contradiction (and therefore are intuitionistically valid).<ref>{{cite journal |title=Five stages of accepting constructive mathematics |last=Bauer |first=Andrej |date=2017 |journal=Bulletin of the American Mathematical Society |volume=54 |issue=3 |pages=481–498 |doi=10.1090/bull/1556 |doi-access=free }}</ref>

===Infinitude of primes===

Let us take a second look at [[Euclid's theorem]] – Book IX, Proposition 20:<ref name="mathcs_clarku_edu" />

: Prime numbers are more than any assigned multitude of prime numbers.

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 theorem#Euclid's proof|Euclid's proof]] applies refutation by contradiction at one step, as follows.

Given any finite list of prime numbers <math>p_1, \ldots, p_n</math>, it will be shown that at least one additional prime number not in this list exists. Let <math>P = p_1 \cdot p_2 \cdots p_n</math> be the product of all the listed primes and <math>p</math> a [[prime factor]] of <math>P + 1</math>, possibly <math>P + 1</math> itself. We claim that <math>p</math> is not in the given list of primes. Suppose to the contrary that it were (an application of refutation by contradiction). Then <math>p</math> would divide both <math>P</math> and  <math>P + 1</math>, therefore also their difference, which is <math>1</math>. This gives a contradiction, since no prime number divides 1.

===Irrationality of the square root of 2===

The classic [[Square root of 2#Proof by infinite descent|proof that the square root of 2 is irrational]] is a refutation by contradiction.<ref>{{cite web|url=http://www.math.utah.edu/~pa/math/q1.html|title=Why is the square root of 2 irrational?|last=Alfeld|first=Peter|date=16 August 1996|work=Understanding Mathematics, a study guide|publisher=Department of Mathematics, University of Utah|access-date=6 February 2013}}</ref>
Indeed, we set out to prove the negation ''¬ ∃ a, b ∈ <math>\mathbb{N}</math> . a/b = {{sqrt|2}}'' by assuming that there exist natural numbers ''a'' and ''b'' whose ratio is the square root of two, and derive a contradiction.

===Proof by infinite descent===

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

* Assume that there is a smallest object with the desired property.
* Demonstrate that an even smaller object with the desired property exists, thereby deriving a contradiction.

Such a proof is again a refutation by contradiction. A typical example is the proof of the proposition "there is no smallest positive rational number": assume there is a smallest positive rational number ''q'' and derive a contradiction by observing that {{sfrac|''q''|2}} is even smaller than ''q'' and still positive.

===Russell's paradox===

[[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.