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. The term "existence proof" is often used as a synonym for "nonconstructive proof", although this is not strictly accurate, as both constructive and nonconstructive proofs can be used to prove existence. See existence theorem.

Some examples of nonconstructive proofs

An example is the following proof of the theorem "There exist irrational numbers

a

and

b

such that

a^b

is rational."

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 it is rational, then the theorem is true, with $a$ and $b$ both being $\sqrt{2}$ .

If it is irrational, then the theorem is true, with $a$ being $\sqrt{2}^\sqrt{2}$ and $b$ being $\sqrt{2}$ , since

(\sqrt{2}^\sqrt{2})^\sqrt{2} = \sqrt{2}^{(\sqrt{2} \cdot \sqrt{2})} = \sqrt{2}^2 = 2

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

a

and

b

. Since we don't know this (because we don't know whether q is irrational), this proof is nonconstructive. (The statement "Either q 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.) (Side note: As it happens, one can prove that q is irrational using the Gelfond-Schneider theorem, proving the above theorem in a different manner and giving an actual example; however, as this is not done in the above proof, the above proof remains nonconstructive) Another example of a nonconstructive theorem is John Nash's proof, using the strategy-stealing argument, that the game of Hex is a first-player win. Nearly every proof which invokes the axiom of choice is nonconstructive in nature because this axiom is fundamentally nonconstructive. According to the philosophical viewpoint of constructivism, nonconstructive proofs constitute a different kind of proof from constructive proofs. Supporters of this view consider nonconstructive existence to be a weaker form of existence than its constructive counterpart. Some constructivists deny the validity of nonconstructive proof altogether.

<< Previous

Word Browser

Next >>

les baxter
audio system measurements
martin denny
toasted sandwich
monte cristo sandwich
croque monsieur
croque madame
ring magazine fights of the year
hetch hetchy valley
mornay sauce
erucic acid

otomo yoshihide
capstan
decolonization
know nothing movement
american party
sorrell booke
abb pierre
rating
christa ludwig
accessibility
final fight

e. howard hunt
iroha
pop culture in puerto rico
entropy (disambiguation)
luis de torres
nintendo 64dd
salman khan
lapu lapu
obscene phone call
cibola
list of topics in logic

kwai chung
aunus expedition
banyeres de mariola
bernard bolzano
curry programming language
adjoint representation
electric piano
baron audley
drax
viriat
midtown (manhattan)