Constructive Proof

In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object. This is in contrast to a non-constructive proof (also known as an existence proof or pure existence theorem) which proves the existence of a particular kind of object without providing an example.

Some non-constructive proofs show that if a certain proposition is false, a contradiction ensues; consequently the proposition must be true (proof by contradiction). However, the principle of explosion (ex falso quodlibet) has been accepted in some varieties of constructive mathematics, including intuitionism.

Constructivism is a mathematical philosophy that rejects all but constructive proofs in mathematics. This leads to a restriction on the proof methods allowed (prototypically, the law of the excluded middle is not accepted) and a different meaning of terminology (for example, the term "or" has a stronger meaning in constructive mathematics than in classical).

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 and Gérard Huet's Calculus of Constructions.