![]() |
Quick description
One of the first things we learn in mathematical logic is that circular arguments are invalid; if a proof of a statement uses that statement
(either explicitly or implicitly) as one of the hypotheses, then no conclusion can be drawn. And, indeed, if circular reasoning was allowed, then one could easily "prove" any statement one wished, since any statement
can be deduced from itself in a trivial fashion.
However, suppose one was able to obtain a non-trivial deduction of the form : one where the hypothesis
is somehow combined with some other deep facts in order to return, in a somewhat unexpected manner, back to
again (or something very close to
). Then, in many cases, one can convert this circular (and hence invalid) logical argument into a rigorous one that can actually be used to derive
unconditionally, provided that one can also verify some sort of "base case", and provided one has some sort of "continuity". Here are some general instances of this idea:
-
Suppose one has a statement
that depends on a natural number parameter. If one takes
as a hypothesis and then deduces
as a conclusion, nothing useful can be drawn from this; but if instead one takes
as a hypothesis and somehow manages to deduce
as a conclusion, then (providing one can also verify a base case such as
or
), one can now use mathematical induction to rigorously and unconditionally conclude
for all
.
-
A well-known variant is the principle of strong induction: if, for each
, one can deduce
assuming that
is true for all
, then this is not a circular deduction, but is in fact strong enough to establish
for all
(provided that
ranges in a well-ordered set, such as the natural numbers).
-
Suppose one has a continuous function
, and one wishes to establish the bound
for all
and some given
. If one was only able to establish the bound
at each
assuming the bound
, then no conclusion can be drawn. If however, one was able to establish the bound
assuming the bound
at that value of
, then (assuming one can also verify
for at least one "base" value of
) one can show that
for all
unconditionally, since if
exceeded
anywhere then by the intermediate value theorem we would have
for at least one value of
, a contradiction. (Alternatively, one can argue that the set
is open, closed, and non-empty, and thus must equal all of the connected interval
). Clearly one can replace
by any other connected set here.
-
There is also a "strong induction" version of the previous trick: if, for each
one can prove
assuming that
for all
, then
in fact holds for all
. Again, one can replace
by other connected intervals (though for intervals containing
, one needs a base case to get started).
-
There is nothing special about the factor of
here. Even an epsilon gain over the trivial implication
, say to
, makes all the difference between a useless implication and a highly useful one.
-
If one wants to show some sort of "exact" statement
, and one has discovered some sort of "non-trivial" implication of the form
, then no conclusion can initially be drawn; but if however this non-trivial implication can be perturbed to something like
for all
, where
is some "approximate" version of
, and one can already show that
(say) is true, then this implies that
is true for arbitrarily small
, which can sometimes be used to recover the original statement
(cf. "create an epsilon of room").
-
Again, there is nothing special about
in the previous scheme: any implication of the form
would work, so long as
is bounded away from zero whenever
is bounded away from zero.
This type of idea is particularly common in nonlinear PDE, where it goes by such names as the "bootstrap argument", "the continuity method", and "the method of a priori estimates": if one wants to achieve some task, such as construct a solution to a given PDE problem with some bounds, assume that such a solution exists already, and use the assumed bounds to deduce slightly better bounds on the solution. In many cases, such an "a priori estimate" can be bootstrapped (by exploiting some continuity properties of the solution or the PDE) into a rigorous and unconditional existence argument.
Prerequisites
Combinatorics, partial differential equations
Example 1
(Stability of a particle in a potential well; more suggestions welcome)
Example 2
(Density increment arguments and energy increment arguments. Once again, Roth's theorem is the poster child...)
General discussion
Some related discussion is at this Google Buzz comment of Terence Tao, and this MathOverflow post by David Feldman.