existence proof ⇝

non-constructive proof


(Or "existence proof") A proof that something exists that does not provide an example of that thing or a method for finding an example. (A constructive proof does provide such an example or method).

For example, for any pair of finite real numbers n < 0 and p > 0 there exists a real number 0 < k < 1 such that

 f(k) = (1-k)*n + k*p = 0.

A non-constructive proof might proceed by observing that as k changes continuously from 0 to 1, f(k) changes continuously from n to p and, since they lie either side of zero, f(k) must pass through zero for some intermediate value of k. This proof does not tell us what that value of k is, only that it exists.

Cantor's proof that the real numbers are uncountable can be thought of as a non-constructive proof that irrational numbers exist. There are existence theorems with no known constructive proof.

Last updated: 2014-08-23

Nearby terms:

non-algorithmic procedurenon-constructive proofnondeterminism

Try this search on Wikipedia, Wiktionary, Google, OneLook.