Main Page | See live article | Alphabetical index

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

Example

The contrast between a constructive proof and a nonconstructive proof is illustrated by the case of transcendental numbers (real or complex numbers that are not algebraic numbers). As Hardy & Wright (1979) say :-

It is not immediately apparent that there are any transcendental numbers ... We may distinguish three different problems. The first is that of proving the existence of transcendental numbers (without necessarily providing a specimen). The second is that of giving an example of a transcendental number by a construction specially designed for the purpose. The third, which is much more difficult, is that of proving that some number given independently ... is transcendental.

The existence of transcendental numbers can be proved by the following argument. The set of algebraic numbers is countable, whereas the set of real numbers is uncountable, therefore there must be some real numbers which are not algebraic numbers. These numbers are transcendental by definition. This is a nonconstructive proof.

For a constructive proof of the existence of transcendental numbers, we need a method of creating them. This is more difficult than simply proving that they exist. The mathematical constants e and &pi are natural candidates for transcendental numbers, but it is very difficult to prove that they are in fact transcendental. The first numbers that could be proved to be transcendental were described by Joseph Liouville who found a method for creating a infinite class of transcendental numbers called Liouville numbers.


References