Constructive proof

Inmathematics,aconstructive proofis a method ofproofthat demonstrates the existence of amathematical objectby creating or providing a method for creating the object. This is in contrast to anon-constructive proof(also known as anexistence prooforpure existence theorem), which proves the existence of a particular kind of object without providing an example. For avoiding confusion with the stronger concept that follows, such a constructive proof is sometimes called aneffective proof.

Aconstructive proofmay also refer to the stronger concept of a proof that is valid inconstructive mathematics. Constructivismis a mathematical philosophy that rejects all proof methods that involve the existence of objects that are not explicitly built. This excludes, in particular, the use of thelaw of the excluded middle,theaxiom of infinity,and theaxiom of choice,and induces a different meaning for some terminology (for example, the term "or" has a stronger meaning in constructive mathematics than in classical).

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, theprinciple of explosion(ex falso quodlibet) has been accepted in some varieties of constructive mathematics, includingintuitionism.

Constructive proofs can be seen as defining certified mathematicalalgorithms:this idea is explored in theBrouwer–Heyting–Kolmogorov interpretationofconstructive logic,theCurry–Howard correspondencebetween proofs and programs, and such logical systems asPer Martin-Löf'sintuitionistic type theory,andThierry CoquandandGérard Huet'scalculus of constructions.

A historical example

Until the end of 19th century, all mathematical proofs were essentially constructive. The first non-constructive constructions appeared withGeorg Cantor’s theory ofinfinite sets,and the formal definition ofreal numbers.

The first use of non-constructive proofs for solving previously considered problems seems to beHilbert's NullstellensatzandHilbert's basis theorem.From a philosophical point of view, the former is especially interesting, as implying the existence of a well specified object.

The Nullstellensatz may be stated as follows: If$f_{1},\ldots,f_{k}$arepolynomialsinnindeterminates withcomplexcoefficients, which have no common complexzeros,then there are polynomials$g_{1},\ldots,g_{k}$such that

$f_{1}g_{1}+\ldots +f_{k}g_{k}=1.$

Such a non-constructive existence theorem was such a surprise for mathematicians of that time that one of them,Paul Gordan,wrote:"this is not mathematics, it is theology".

Twenty five years later,Grete Hermannprovided an algorithm for computing$g_{1},\ldots,g_{k},$which is not a constructive proof in the strong sense, as she used Hilbert's result. She proved that, if$g_{1},\ldots,g_{k}$exist, they can be found with degrees less than $2^{2^{n}}$.

This provides an algorithm, as the problem is reduced to solving asystem of linear equations,by considering as unknowns the finite number of coefficients of the$g_{i}.$

Examples

Non-constructive proofs

First consider the theorem that there are an infinitude ofprime numbers.Euclid'sproofis constructive. But a common way of simplifying Euclid's proof postulates that, contrary to the assertion in the theorem, there are only a finite number of them, in which case there is a largest one, denotedn.Then consider the numbern!+ 1 (1 + the product of the firstnnumbers). Either this number is prime, or all of its prime factors are greater thann.Without establishing a specific prime number, this proves that one exists that is greater thann,contrary to the original postulate.

Now consider the theorem "there existirrational numbers$a$and$b$such that$a^{b}$isrational."This theorem can be proven by using both a constructive proof, and a non-constructive proof.

The following 1953 proof by Dov Jarden has been widely used as an example of a non-constructive proof since at least 1970:

CURIOSA
339.A Simple Proof That a Power of an Irrational Number to an Irrational Exponent May Be Rational.
${\sqrt {2}}^{\sqrt {2}}$is either rational or irrational. If it is rational, our statement is proved. If it is irrational,$({\sqrt {2}}^{\sqrt {2}})^{\sqrt {2}}=2$proves our statement.
Dov Jarden Jerusalem

In a bit more detail:

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

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

As it turns out,${\sqrt {2}}^{\sqrt {2}}$is irrational because of theGelfond–Schneider theorem,but this fact is irrelevant to the correctness of the non-constructive proof.

Constructive proofs

Aconstructiveproof of the theorem that a power of an irrational number to an irrational exponent may be rational gives an actual example, such as:

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

Thesquare root of 2is irrational, and 3 is rational.$\log _{2}9$is also irrational: if it were equal to$m \over n$,then, by the properties oflogarithms,9ⁿwould be equal to 2^m,but the former is odd, and the latter is even.

A more substantial example is thegraph minor theorem.A consequence of this theorem is that agraphcan be drawn on thetorusif, and only if, none of itsminorsbelong 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

Inconstructive mathematics,a statement may be disproved by giving acounterexample,as in classical mathematics. However, it is also possible to give aBrouwerian counterexampleto show that the statement is non-constructive.This sort of counterexample shows that the statement implies some principle that is known to be non-constructive. If it can be proved constructively that the statement implies some principle that is not constructively provable, then the statement itself cannot be constructively provable.

For example, a particular statement may be shown to imply the law of the excluded middle. An example of a Brouwerian counterexample of this type isDiaconescu's theorem,which shows that the fullaxiom of choiceis non-constructive in systems ofconstructive set theory,since the axiom of choice implies the law of excluded middle in such systems. The field ofconstructive reverse mathematicsdevelops this idea further by classifying various principles in terms of "how nonconstructive" they are, by showing they are equivalent to various fragments of the law of the excluded middle.

Brouwer also provided "weak" counterexamples.Such counterexamples do not disprove a statement, however; they only show that, at present, no constructive proof of the statement is known. One weak counterexample begins by taking some unsolved problem of mathematics, such asGoldbach's conjecture,which asks whether every even natural number larger than 4 is the sum of two primes. Define a sequencea(n) of rational numbers as follows:

$a(n)={\begin{cases}(1/2)^{n}&{\mbox{if every even natural number in the interval }}[4,n]{\mbox{ is the sum of two primes}},\\(1/2)^{k}&{\mbox{if }}k{\mbox{ is the least even natural number in the interval }}[4,n]{\mbox{ which is not the sum of two primes}}\end{cases}}$

For eachn,the value ofa(n) can be determined by exhaustive search, and soais a well defined sequence, constructively. Moreover, becauseais aCauchy sequencewith a fixed rate of convergence,aconverges to some real number α, according to the usual treatment of real numbers in constructive mathematics.

Several facts about the real number α can be proved constructively. However, based on the different meaning of the words in constructive mathematics, if there is a constructive proof that "α = 0 or α ≠ 0" then this would mean that there is a constructive proof of Goldbach's conjecture (in the former case) or a constructive proof that Goldbach's conjecture is false (in the latter case). Because no such proof is known, the quoted statement must also not have a known constructive proof. However, it is entirely possible that Goldbach's conjecture may have a constructive proof (as we do not know at present whether it does), in which case the quoted statement would have a constructive proof as well, albeit one that is unknown at present. The main practical use of weak counterexamples is to identify the "hardness" of a problem. For example, the counterexample just shown shows that the quoted statement is "at least as hard to prove" as Goldbach's conjecture. Weak counterexamples of this sort are often related to thelimited principle of omniscience.

See also

• Constructivism (philosophy of mathematics)
• Errett Bishop- author of the book "Foundations of Constructive Analysis".
• Existence theorem § 'Pure' existence results
• Non-constructive algorithm existence proofs
• Probabilistic method

Further reading

• J. Franklinand A. Daoud (2011)Proof in Mathematics: An Introduction.Kew Books,ISBN0-646-54509-4,ch. 4
• Hardy, G. H.&Wright, E. M.(1979)An Introduction to the Theory of Numbers(Fifth Edition). Oxford University Press.ISBN0-19-853171-0
• Anne Sjerp TroelstraandDirk van Dalen(1988) "Constructivism in Mathematics: Volume 1" Elsevier Science.ISBN978-0-444-70506-8

External links

• Weak counterexamplesby Mark van Atten, Stanford Encyclopedia of Philosophy