Revision of Impossibility and nonexistence front page from Sat, 27/12/2008 - 00:14

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

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

Parent article

What kind of problem am I trying to solve?