Tricki
a repository of mathematical know-how

Prove the result for some cases and deduce it for the rest

Quick description

There are many statements beginning "for all" where the best approach is first to prove the result in a few cases and then to deduce it for everything else. Below are links to articles that discuss different techniques of this general kind. The distinctions between the techniques are not always clear cut.

  • Mathematical induction Quick description ( This is a classic example: to prove a property P(n) for all natural numbers n, establish the base case P(0) first, and then deduce each statement P(n) for n \geq 1 in turn from the preceding one P(n-1).)

  • Using generators and closure properties Quick description ( Suppose that X is some mathematical structure that is generated by some small subset K. (The meaning of "is generated by" depends on what sort of structure X is.) A useful method of proving statements of the form "Every element of X has property P" is to show that every element of K has property P and to show that anything you generate using elements that have property P also has property P. )

  • Prove the result on a dense subset and then prove that the set where the result holds is closed Quick description (A good way to prove that a result holds for all objects in a certain class is often to show that it holds for all objects of a certain simple kind, that objects of that simple kind are dense, and that the set of objects for which the result holds is closed. This technique is particularly useful when the objects in question are functions.)

  • Prove the result on a \delta-net first Quick description ( In probabilistic arguments, one sometimes wants to prove that it is possible for a statement to be true for every element of an infinite set, and one knows that for each element of the set a slightly stronger statement is true with probability at least 1-\epsilon for some very small \epsilon. If there is a natural metric on the set, one can sometimes achieve this by proving that the set contains a \delta-net of size N<\epsilon^{-1}, and also that if the stronger result holds for every element of a \delta-net, then the weaker result holds everywhere. )

  • Create an epsilon of room Quick description ( To prove an "endpoint" or "degenerate" statement P(0), first prove the non-degenerate statements P(\varepsilon) for all small \varepsilon > 0, then take limits as \varepsilon > 0 to recover the endpoint claim. )

  • Make use of special cases and transitivity Quick description ( If one is trying to prove that any two elements of some structure are equivalent in a certain way, it is often easiest not to prove this directly, but instead to prove that one particularly simple element is related to all the others and then exploit transitivity. )

  • Prove the result for a representative of each equivalence class Quick description ( Sometimes one can prove a result for every element of a set with an equivalence relation on it by proving the result for a representative of each equivalence class and proving that if the result is true for some element then it is true for all elements that are equivalent to that element. )

  • Establish an invariance principle first Quick description ( To prove a property P(x) for all x, first show that P(x) is equivalent to P(y) for all x, y in the desired parameter space. Then, one only needs to verify P(x) for a single x, which one can choose to make the verification as easy as possible.)

  • Use the continuity method Quick description ( If you can show that the set of parameters obeying a property P is non-empty, open, and closed, and the parameter space is connected, then P must be obeyed by all choices of the parameter. )

  • Use conservation laws and monotonicity formulae to obtain long-time control on solutions Quick description ( Suppose one has a solution to an evolution equation (such as a PDE) which one controls well at some initial time (e.g. t=0). To then establish control for much later (or much earlier) times t, one effective approach is to exploit a conservation law or monotonicity formula, which propagates control of some quantity at one time to control of a related quantity at other times.)

  • Do an extreme case first Quick description ( It often pays to first look at extreme cases when the parameter is very small (e.g. n=0) or very large (e.g. look at the asymptotic limit n \to \infty, holding other parameters fixed). If one can find a single method which works well for both extremes, then it is quite likely that it can also be extended to work for the intermediate cases as well. )