Tricki

## Revision of Existence proofs from Thu, 18/12/2008 - 18:29

### Quick description

Many mathematical problems require one to prove that a mathematical object with certain properties exists. There are many different techniques for proving existence statements. This page briefly describes some of these and gives links to more detailed discussions.

### General discussion

Technique 1: off-the-shelf examples Brief summary ( Suppose that you are asked to prove that a mathematical object of a given kind (such as a prime number, or a group, or a function from the real numbers to the real numbers) exists with certain properties. The most obvious method is probably to look at familiar examples of that kind of mathematical object and see if one of them has the property in question. For example, does there exist a function from the reals to the reals that is non-constant, bounded, and infinitely differentiable? Most people would answer that question by having a thought such as, "Polynomials don't work, so what's the next simplest sort of function? I could try but that doesn't work either because it's unbounded. Ah, I could use or ." It is unlikely that you will be able to solve an unsolved existence problem by simply searching around for a known example that does the job for you, unless the difficulty lies in showing that the known example has the property you want. However, not all existence problems arise directly as unsolved problems. For instance, you might be thinking about another problem and realize that it would be helpful if you could prove a certain lemma of the form "For every there exists such that ..." Then you would be faced with a "mini-problem" of a kind that comes up a lot in research. You would not necessarily know in advance whether it was easy or hard, so it would be worth searching for an off-the-shelf construction of rather than starting from scratch. It also often happens that a non-trivial counterexample to one conjecture can be modified to disprove several others: it is worth getting to know the important counterexamples in your area in case you can use them for your own purposes in another context. )

Technique 2: building a bespoke example Brief summary ( Another very obvious idea for proving existence statements is to design examples specifically to have the properties that are being asked for. For instance, Euclid's proof that there are infinitely many primes does this: he assumes that there are finitely many primes and then designs the number not to be a multiple of any of those primes. )

Technique 3: making one mathematical structure out of another Brief summary ( There are many ways of building one kind of mathematical object out of another. For example, given a graph with vertices one can define an symmetric matrix by taking to be 1 if is an edge of and 0 otherwise. Or given a connected manifold one can define its fundamental group. Or given a group one can define its group algebra. The list of ways in which one object can be used in the construction of another is very long. )

Technique 4: universal examples with given properties Brief summary ( Suppose you are asked to prove that a mathematical object of a certain type can be found that satisfies some property . It quite often happens that there is a partial order on the given kinds of objects such that if is less than and has property , then so does . If that is the case, then one can look for objects that are maximal in this partial order. This observation leads to the notion of a universal construction. )

Technique 5: indirect proofs of existence

Technique 6: the probabilistic method Brief summary ( If you are trying to prove that an object of type exists with certain properties, and if those properties seem to force to be "spread about" and "unstructured", then a good method may well be to define a simple probability distribution on all objects of type and prove that there is a non-zero probability that a randomly chosen has the desired properties. )

Technique 7: cardinality, measure and category

### How do I decide which technique to use?

It is difficult to give a definitive answer to this question, but there are certainly features to look out for when one is trying to assess which style of proof is most likely to be suitable for a given existence problem. Looking for an example amongst a list of well-known constructions is usually best if you have only just come across the problem and have no evidence to suggest how hard it is. One can think of this as a preliminary test: if you don't come across an example, then the act of establishing that well-known examples don't work may at least provide a few clues about how to go about the proof.

If off-the-shelf examples don't solve your problem, what should you do next? Here are some questions that can help with the decision. Suppose that your problem is of the form "Does there exist an such that ?" Here is some type of mathematical object, like a field or an analytic function from to , and is some property that may or may not have. Then it can make a big difference if can be split up into several different properties. For example, returning to Euclid's proof that there are infinitely many primes, he assumes that the only primes are , and is faced with the question, "Does there exist such that is not a multiple of any prime?" If it were not fairly easy to come up with an example of such an (under the hypothesis that will thereby be contradicted), then it would be possible to exploit the fact that this property splits up into the properties " is not a multiple of " and prove the result as one proves the Chinese remainder theorem. The idea would be to start by finding a number that wasn't a multiple of and remember that adding any multiple of to it would give another non-multiple of . So if was a multiple of , one could add to it and the result would no longer be a multiple of since is not a factor of . To this new number one could add any multiple of and it would still not be a multiple of either or . So if was a multiple of one could add to it and the result would no longer be a multiple of , since is not a factor of . (This is a fairly deep fact, however.) And so on all the way up to . Of course, the usual proof of just exhibiting the number is simpler for this problem, but the fact that we can split the property up as a conjunction of several simpler properties does at least show that there is a way of solving the problem that doesn't need one to have that idea and just deals with the properties one by one. To summarize, you should ask yourself: does the property I am looking for split up as the conjunction of several simple properties?

If the answer is yes, then there are other very important questions you should ask. A very obvious one is: Do I have finitely many constraints or infinitely many? And a less obvious but perhaps more important one: Are the simple properties "loose constraints" on or "tight constraints" on ? And a closely related question: Does have many degrees of freedom or few?

Roughly speaking, a loose constraint is one that does not cut down by too much the space of all possibilities for . For example, if you are trying to find a sequence of integers that satisfies properties , and property requires that every term of the sequence beyond a certain point is at least as big as , then that is probably a loose constraint, since there is still a vast amount of flexibility in how you choose your sequence. (I say "probably" because it might conceivably be that in the presence of the other properties that the sequence is required to have, this property does hugely cut down the possibilities. But it is usually quite easy to recognise a loose constraint when you have one.) Having loose constraints is helpful if the object that you want to exist can be built up in stages. In the case of a sequence, it is obvious that this can be done: one builds up the sequence an element at a time. But it also applies to less clearly composite objects such as real numbers, which can be defined as limits of sequences. And as the discussion of Euclid's proof showed, even a positive integer can on occasion be built up in stages.

Sometimes one can prove that there is an object with many properties by proving that for every the set of objects that do not have property is small. If the sets are small enough in a suitable sense (that varies from problem to problem) then one may be able to show that their union cannot include all objects . If objects of type have finitely many degrees of freedom and one wants to find with finitely many properties , then one may be able to assign sizes to each set of objects without property and show that these sizes add up to less than the size of the set of all objects of type . This is how the probabilistic method works. If there is a countably infinite collection of properties, then one often tries to find a notion of smallness with the following two features: a countable union of small sets is small; the set of all objects of type is not small. Then if the set of all objects of type without property is small for each , it follows that there is some that has all the properties . Some common notions of smallness are |being countable, having measure zero, and being of the first category.

### Parent article

What kind of problem am I trying to solve?