Nonconstructive proof

In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object with certain properties by creating or providing a method for creating such an object. This is in contrast to a nonconstructive proof (also known as an existence proof or pure existence theorem) which proves the existence of a mathematical object with certain properties, but does not provide a means of constructing an example.

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

Constructivism is the philosophy that rejects all but constructive proofs in mathematics. 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.

Constructive proofs can be seen as defining certified mathematical algorithms: this idea is explored in the Brouwer–Heyting–Kolmogorov interpretation of constructive logic, the Curry–Howard correspondence‎ between proofs and programs, and such logical systems as Per Martin-Löf's Intuitionistic Type Theory and Thierry Coquand's Calculus of Constructions.

Example

Consider the theorem "There exist irrational numbers $a$ and $b$ such that $a b$ is rational." This theorem can be proved via a constructive proof, or via a non-constructive proof.

A possible non-constructive proof proceeds as follows:

Recall that $\sqrt{2}$ is irrational, and 2 is rational. Consider the number $q = \sqrt{2}^{\sqrt2}$ . 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}^{\sqrt2}$ and $b$ being $\sqrt{2}$ , since

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

This proof is non-constructive because it relies on the statement "Either q is rational or it is irrational" — an instance of the law of excluded middle, which is not valid within a constructive proof. The non-constructive proof does not construct an example a and b; it merely gives a number of possibilities (in this case, two mutually exclusive possibilities) and shows that one of them — but does not show which one — must yield the desired example.

(It turns out that $\sqrt{2}^{\sqrt2}$ is irrational because of the Gelfond–Schneider theorem, but this fact is irrelevant to the correctness of the non-constructive proof.)

A constructive proof of the theorem would give an actual example, such as:

$a = \sqrt{2}\, , \quad b = \log_2 9\, , \quad a^b = 3\, .$

The square root of 2 is of course irrational, and 3 is of course rational. $log 29$ is also irrational: if it were equal to $m \over n$ , then, by the properties of logarithms, 9ⁿ would be equal to 2^m, but the former is odd, and the latter is even.

A more substantial example is the graph minor theorem. A consequence of this theorem is that a graph can be drawn on the torus if, and only if, none of its minors belong to a certain finite set of "forbidden minors". However, the proof of the existence of this finite set is not constructive, and the forbidden minors are not actually specified. They are still unknown.

Brouwerian counterexamples

In constructive mathematics, a theorem may be disproved by giving a counterexample, or a Brouwerian counterexample may be given to show that the theorem is essentially non-constructive. For example, if it can be shown constructively that a statement $P$ implies the law of excluded middle, then $P$ cannot be a constructive theorem.

A Brouwerian counterexample does not disprove a statement; it only shows that it is non-constructive. Since intuitionistic logic is consistent with classical logic, it is impossible to disprove non-constructive statements that are classically valid.

References

Hardy, G.H. & Wright, E.M. (1979) An Introduction to the Theory of Numbers (Fifth Edition). Oxford University Press. ISBN 0-19-853171-0 [Amazon-US | Amazon-UK]

Open source encyclopedia content modification information:

This page was last modified on 22 February 2010 at 12:49.

Authorship and Review

Open source encyclopedia content provided here is not reviewed directly by MedLibrary.org. Content is sourced directly from Wikipedia and is authored by an open community of volunteers. It is not produced by or in any way affiliated with MedLibrary.org.

Usage Guidelines

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Nonconstructive proof", which is available in its original form here:

http://en.wikipedia.org/w/index.php?title=Nonconstructive_proof

All material adapted used from Wikipedia is available under the terms of the GNU Free Documentation License. Wikipedia® itself is a registered trademark of the Wikimedia Foundation, Inc.

Nonconstructive proof -- Please Click to Return to Front Page