Main Page | See live article | Alphabetical index

Nonconstructive proof

In mathematics, a nonconstructive proof, is a mathematical proof that purports to demonstrate the existence of something, but which does not say 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.

Some examples of nonconstructive proofs

An example is the following proof of the theorem "There exist irrational numbers and such that is rational."

A constructive proof of this theorem would leave us knowing values for and .

Since we don't know this (because we don't know wheter is irrational), this proof is nonconstructive. (The statement "Either 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.)

Another example of a nonconstructive theorem is John Nash's proof that the game of Hex is a first-player win.

Practically every proof which invokes the axiom of choice is nonconstructive in nature because this axiom is nonconstructive at heart.

According to the philosophical viewpoint of mathematical constructivism, nonconstructive proofs are invalid. Supporters of this view claim that something can only be said to exist if an example can be constructed.

This article is a stub. You can help Wikipedia by fixing it.