Tricki
a repository of mathematical know-how

Impossibility and nonexistence front page

Quick description

An important class of mathematical theorems is the class of impossibility results. At first, it might seem that proving impossibility is itself impossible, or at least very difficult, because one has to rule out every conceivable way that something might be done. However, the techniques below have shown themselves to be very useful for doing just that.

General discussion

It may seem strange to have a separate category of proofs of nonexistence, since any statement of the form "There does not exist X such that P(X)" is equivalent to the statement "For every X, it is not the case that P(X)". However, there are some nonexistence statements that are more naturally thought of as starting "There does not exist" than "For every". For example, it would be strange to rephrase "There is no bijection between \mathbb{N} and \mathbb{R}" as "For every function f from \mathbb{N} to \mathbb{R}, f is not a bijection." And one can even say why it is strange: it is because there isn't a neat way to define the property of not being a bijection without using the word "not". (It can be done of course, but the result just isn't as natural as saying that f is not a bijection.)

Invariants Quick description ( One often wants to prove that two objects X and Y are not equivalent, according to some notion of equivalence. Frequently this amounts to showing that there is no function of a certain kind (such as a structure-preserving bijection, say) from X to Y. It is usually difficult to obtain a contradiction directly from the assumption that such a function exists, but what one can often do instead is find an invariant, that is, a function \phi defined on objects of the general type of X and Y such that \phi(X)=\phi(X') whenever X and X' are equivalent, and \phi(X)\ne\phi(Y). A closely related use of invariants is to show that one object cannot be transformed into another by means of a certain procedure. )

Diagonal arguments Quick description ( Cantor's diagonal argument is a famous proof that shows that there is no surjection from the natural numbers to the real numbers. But there are many other results that have been proved by diagonal-type arguments, such as Turing's proof of the insolubility of the halting problem. So Cantor's argument can now be seen as a useful general technique rather than a one-off. )

Models in which a statement is false Quick description ( How does one prove that a given statement cannot be proved in a certain way? One of the best ways is to construct a model, which is a mathematical structure with the following properties: (i) in it one can give an interpretation of the statement in question; (ii) in it one can also interpret all proofs of the particular kind in question, and if they are valid proofs then they are valid in the model; (iii) the (interpreted) statement is false in the model. This is a very important technique in set theory, but also in mathematics in general. )

Brute force Quick description ( It's not the most aesthetically pleasing method, but some nonexistence results can be proved by means of an exhaustive search for examples. For instance, the nonexistence of a projective plane of order 10 was proved this way. In more interesting cases, it is not obvious in advance that a finite search will suffice: one has to work to reduce the problem to a finite search. )