On the strength of theorems

[Reprinted from a Google Buzz article from Sep 5, 2010.]

The early twentieth century philosopher Ludwig Wittgenstein famously argued that every mathematical theorem was a tautology, and thus all such theorems contained a trivial amount of content. There is a grain of truth to this; when a difficult mathematical problem is finally solved, it is often the case that the solution does make the original problem look significantly easier than had previously thought to be the case. Indeed, one could take the counter-intuitive point of view that progress in mathematics can be measured by how much of the subject has been made trivial (or at least easier to understand than previously).

On the other hand, there is a definite sense that some mathematical theorems are “stronger” than others, even if from a strictly logical point of view they are all “just” tautologies. For instance a theorem can be considered strong because its conclusions are strong, because its hypotheses (or the underlying axiom system used in the proof) are weak, or for some combination of the two reasons.

More generally, what makes a theorem strong? This is not a precise, well-defined concept. But one way to measure the strength of the theorem is to test it against a class of questions and problems that the theorem is intended to assist with solving. For instance, one might gauge the strength of a theorem in analytic number theory by the size of the error terms it can give on various number-theoretic quantities; one might similarly gauge the strength of a theorem in PDE by how large a class of initial data the theorem is applicable to, and how much control one obtains on the solution as a consequence; and so forth.

All other things being equal, universal statements such as “P(x) is true for all x” are stronger than existential statements such as “P(x) is true for some x”, assuming of course that one is quantifying over a non-empty space. There are also statements of intermediate strength, such as “P(x) is true for many x”, or “P(x) is true for almost every x”. In a similar vein, statements about special types of objects (e.g. special functions) are usually not as strong as analogous statements about general types of objects (e.g. arbitrary functions in a given function space), again assuming that all other things are equal. (In practice, there is usually a tradeoff: to obtain more general statements, one has to weaken the conclusion, so that it neither result becomes clearly stronger than the other.)

Asymptotic statements (e.g. statements that only have content when some parameter such as n is “sufficiently large”, or in the limit n→∞) are usually not as strong as non-asymptotic statements (which have content for every fixed choice of parameter n). Again, this is assuming that all other things are equal. In a similar vein, approximate statements (e.g. estimates) are not as strong as exact statements, if all other things are equal.

Statements about “easy” or well-understood objects are usually not as strong as statements about “difficult” or poorly understood objects. For instance, statements about solutions to equations over the reals tend to be significantly weaker (and easier to prove) than their counterparts concerning equations over the integers; results about linear operators are similarly weaker than their counterparts concerning nonlinear operators; statements concerning arithmetic functions that are sensitive to prime factorisation (such as the Mobius or von Mangoldt functions) are usually stronger than analogous statements about non-arithmetic functions (such as the logarithm function); and so forth.

When trying to read and understand a long and complicated proof, one useful thing to do is to look at the strength of various key statements inside the argument, and focus on those portions of the argument where the strength of the statements increases significantly (for instance, if statements that previously held only for one value of n, now became amplified to hold for many values of n). Such amplifications often contain an essential trick or idea which powers the entire argument, and understanding these crucial steps often brings one much closer to understanding the argument as a whole. (By the same token, if the proof ends up being flawed, it is quite likely that at least one of these flaws will be associated with a step where statements became unexpectedly stronger by a suspiciously significant amount, and so one can use the strength of such statements as a way to quickly locate flaws in a dubious argument.)

The notion of strength of a statement need not be absolute, but may depend on the context. For instance, suppose one is trying to read a convoluted argument that is claiming a statement which is true in all dimensions n. If the proof proceeds by induction on this dimension, then it is useful to adopt the perspective that any statement in dimension n should be considered “stronger” than a statement in dimension n-1, even if the latter statement would ordinarily be considered the stronger statement if the dimensions were equal. With this perspective, one is then motivated to focus on the passages in the argument where statements in dimension n-1 are somehow converted to statements in dimension n; such passages are often the key to understanding the overall strategy of the argument.