# How to prove existence of solutions without constructing one?

For some problems, it is difficult to get an explicit solution. But it is very good if we can prove there do exist some solutions though we can't find them. Is it possible to prove existence of solutions without constructing one? Can you show some examples? Many thanks.

Edit: Thanks everyone. Of course, it is the best if we can find one or all solutions to a problem. But it is not always easy. Then a non-constructive proof may also be very meaningful. Here is an example. In 1991, it was proved that a multiple layer perceptron neural network is a universal function approximator. But the proof is not constructive. However, it is of great importance for at least control community as people can try to use neural network to approximate any nonlinear systems without worrying about the theoretical foundation. What I am interested is whether there are any general methods for non-constructive existence proof.

-
We can always find them if they exist, but its not always easy. – user1708 Apr 11 '11 at 6:38
Prove that not everything isn't one. – quanta Apr 11 '11 at 6:54
Also it depends what you mean by 'construct' and 'exists'. Also, any non-computable number will do – user1708 Apr 11 '11 at 6:57
When one deals with infinite set, Zorn Lemma is a very powerful tool to prove that certain sets exists. The existence of a basis in an infinite dimensional vector space is such an example. And while one can give a constructive proof, it is also easy to prove non-constructively that every field has an algebraic closure. – N. S. Apr 12 '11 at 3:29

Here is a typical example of a non-constructive existence proof:

We want to prove that there exists a rational number $x^y$ such that both $x$ and $y$ are irrational. A way to do this is first to let $x=y=\sqrt 2$ (because we know that $\sqrt 2$ is irrational). If $\sqrt 2 ^{\sqrt 2}$ is rational, we have have a rational number on the desired form. On the other hand, if $\sqrt 2 ^{\sqrt 2}$ is irrational, let $x=\sqrt 2 ^{\sqrt 2}$ and $y=\sqrt 2$. Then $x^y=(\sqrt 2 ^{\sqrt 2})^{\sqrt 2} = \sqrt 2^2 = 2$, which is obviously rational.

We have proven that there exists a rational number $x^y$ such that both $x$ and $y$ are irrational. Either with $x=y=\sqrt 2$ or $x=\sqrt 2 ^{\sqrt 2}, y= \sqrt 2$, but we don't know which.

Edit:
Trying to generalize this idea. Suppose you want to prove a proposition. Find a set of cases such that only one of the cases has to be true for the proposition to be true. A constructive proof would be to find a specific case that is true. For a non-constructive proof, it is enough show that it is not possible that all the cases are false.

-
Thanks. Both the example and the general non-constructive proof strategy you give are good. – Shiyu Apr 11 '11 at 15:45

A very common technique is by counting and comparing cardinalities. For example, one can prove that transcendental numbers must exist by noting that there is a countable number of algebraic numbers (since there is a countable number of polynomials), but the reals are uncountable by Cantor's argument. This shows that most numbers are transcendental without producing a single one of them.

-
Maybe not such a good example, because Cantor's argument provides a constructive way to get a real number that is not in a given sequence of real numbers. – Robert Israel Apr 11 '11 at 8:13
On a related note: Gowers has a nice discussion of Cantor's argument on his blog. – t.b. Apr 11 '11 at 8:20
@Alex: Noted and thanks. – Shiyu Apr 11 '11 at 16:03
@Robert I guess it depends on what you mean by "constructive". The number you get this way will usually not be a computable number: en.wikipedia.org/wiki/Computable_number#Properties. – Alex B. Apr 12 '11 at 4:12
@Alex: It certainly seems computable to me. Why do you say it isn't? – Robert Israel Apr 12 '11 at 5:06

The Intermediate Value Theorem is a nice tool to prove that solutions to many type of equations exists, without being able to solve them.

It is used for example to show that any polynomial of odd degree with real coefficients has a real solution (which is a critical step in the proof of Fundamental Theorem of Algebra), or to prove that equations of the type:

$$x=\cos(x)$$ have solutions.

-

The http://en.wikipedia.org/wiki/Green%E2%80%93Tao_theorem states that there exists arbitrarily long arithmetic progressions in the primes, but does not provide a method to construct them.

-
Thanks for the example. – Shiyu Apr 11 '11 at 15:55

Proofs by contradiction often work in these cases. For instance, if you were to assume that $\sin(3x)$=$x^3-\pi$ has no solutions, then $\sin(3x)-x^3+\pi$ is never zero. Thus, the reciprocal of this function is defined for all real numbers, which you may then be able to prove is impossible giving you a contradiction.

The intermediate value theorem also helps when dealing with continuous functions. For the example above, it is enough to find $x_1$ and $x_2$ such that $\sin(3x_1)-x_1^3+\pi>0$ and $\sin(3x_2)-x_2^3+\pi<0$. (Take $x_1$ and $x_2$ to be 0 and 2 respectively for example). This implies that there is a solution to the original equation lying between 0 and 2.

-
Noted. Thanks Joe. The example is good. Proof by contradict might be a quite general method. – Shiyu Apr 11 '11 at 15:48
Use $\backslash\sin$. – Did Apr 11 '11 at 16:15

The probabilistic method can sometimes be used to prove the existence of a structure with certain properties. You put a probability measure on the set of all structures, that is, define "random structure" in a meaningful way. Then if your properties hold with non-zero probability, you have existence!

The Wikipedia link above gives two concrete examples from combinatorics.

-

I believe that the contradiction is the only possible method to prove an existence without constructing a method to find the solution. That's why proofs by contradiction are called "non-constructive".

On the other hand, it's not always good to know the existence of a solution without knowing how to obtain it. A nice example is the following theorem: if $x_n\leq x_{n+1}$ and $x_{n}\leq a$ for all $x\geq 0$ then $\exists\lim\limits_{n\to\infty}x_n = x\leq a$. It's a nice theorem but if you would like to calculate bounds on $x-x_n$ it tells nothing to you how to do it.

-
This is actually a good example of an existence theorem that can be proved non-constructively without using contradiction. In this case, if you are defining the real numbers via Dedekind cuts, consider the Dedekind cut $\{A,B\}$ where A is the set of all rationals $r$ such that some $x_n > r$, and B is the set of all rationals $s$ such that all $x_n \le s$. Then that Dedekind cut corresponds to your $x$. – Robert Israel Apr 11 '11 at 8:05
This "construction" is non-constructive because, even though you may be able to construct each $x_n$ individually, there may be no way to tell whether there exists any $x_n > r$. – Robert Israel Apr 11 '11 at 8:24
Why the downvote, could you please comment? – Ilya Apr 11 '11 at 10:14
Thanks Gortaur and Robert: Noted. Thanks for the example and comments. By the way, I didn't downvote your answer. – Shiyu Apr 11 '11 at 15:54
I haven't meant that it's you :) just seen that somebody downvoted it. With regards to the meaningful non-constructive proofs. I certainly do agree with you, but I've just proved that on iterative procedure has a limit function (since it is monotonic sequence), but it is very difficult to find strict bounds which are in fact of the most importance. – Ilya Apr 11 '11 at 15:58

The game of Hex gives a good example. First one can prove it cannot draw, so it must be either a first or second player win. Assume it is a second player win. Let the first player make a random move, then follow the second player strategy. If the strategy requires a move where the random move is, take another random move. As an extra move can only be an asset, the first player can win, contradicting our second player win assumption. This gives no information on what the strategy is.

-

The Implicit Function Theorem is another example of such a technique. There are plenty of examples of the Implicit Function Theorem in action, although some of the concrete examples seem a bit artificial.

-