Nonconstructive proof

In mathematics, a nonconstructive proof, as opposed to a constructive proof, is a mathematical proof that purports to demonstrate the existence of something, but does not reveal how to construct it. Many nonconstructive proofs assume the non-existence of the thing whose existence is required to be proven, and deduce a contradiction. The non-existence of the thing has therefore been shown to be logically impossible, and yet an actual example of the thing has not been found. The term "pure existence proof" is often used as a synonym for "nonconstructive proof", where "pure" means that the proof just shows existence and yields nothing else. See existence theorem.

Nearly every proof which invokes the axiom of choice is nonconstructive in nature because this axiom is fundamentally nonconstructive. The same can be said for proofs invoking König's lemma. According to the philosophical viewpoint of constructivism, nonconstructive proofs constitute a different kind of proof from constructive proofs. Typically, supporters of this view deny that pure existence can be usefully characterized as "existence" at all: accordingly, a non-constructive proof is instead seen as "refuting the impossibility" of a mathematical object's existence, a strictly weaker statement.

An example of a nonconstructive proof

An example is the following proof of the theorem "There exist irrational numbers $a$ and $b$ such that $a^{b}$ is rational."

• Recall that ${\sqrt {2}}$ is irrational, and 2 is rational. Consider the number $q={\sqrt {2}}^{\sqrt {2}}$. Either it is rational or it is irrational.

• If $q$ is rational, then the theorem is true, with $a$ and $b$ both being ${\sqrt {2}}$.

• If $q$ is irrational, then the theorem is true, with $a$ being ${\sqrt {2}}^{\sqrt {2}}$ and $b$ being ${\sqrt {2}}$, since

$\left({\sqrt {2}}^{\sqrt {2}}\right)^{\sqrt {2}}={\sqrt {2}}^{({\sqrt {2}}\cdot {\sqrt {2}})}={\sqrt {2}}^{2}=2.$

Since we do not know values for $a$ and $b$ (because we do not know whether q is irrational), this proof is nonconstructive. The statement "Either q is rational or it is irrational", from the above proof, is an instance of the law of excluded middle, which is not valid within a constructive proof. On the other hand, a constructive proof of the same theorem would give an actual example, such as ${\sqrt {2}}^{\log _{2}9}=3$ with ${\sqrt {2}}$ and $\log _{2}{9}$ being irrational numbers according to unique factorization, and 3 of course being rational.