Tricki
a repository of mathematical know-how

A non-trivial circular argument can often be usefully perturbed to a non-circular one

Note iconIncomplete This article is incomplete. This article is not a stub, but needs more concrete and interesting examples.

Quick description

One of the first things we learn in mathematical logic is that circular arguments are invalid; if a proof of a statement P uses that statement P (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 P can be deduced from itself in a trivial fashion.

However, suppose one was able to obtain a non-trivial deduction of the form P \implies P: one where the hypothesis P is somehow combined with some other deep facts in order to return, in a somewhat unexpected manner, back to P again (or something very close to P). 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 P 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 P(n) that depends on a natural number parameter. If one takes P(n) as a hypothesis and then deduces P(n) as a conclusion, nothing useful can be drawn from this; but if instead one takes P(n) as a hypothesis and somehow manages to deduce P(n+1) as a conclusion, then (providing one can also verify a base case such as P(0) or P(1)), one can now use mathematical induction to rigorously and unconditionally conclude P(n) for all n.

  • A well-known variant is the principle of strong induction: if, for each n, one can deduce P(n) assuming that P(m) is true for all m < n, then this is not a circular deduction, but is in fact strong enough to establish P(n) for all n (provided that n ranges in a well-ordered set, such as the natural numbers).

  • Suppose one has a continuous function  [0,1] \to \R, and one wishes to establish the bound f(t) \leq M for all 0 \leq t \leq 1 and some given M > 0. If one was only able to establish the bound f(t) \leq M at each t assuming the bound f(t) \leq M, then no conclusion can be drawn. If however, one was able to establish the bound f(t) \leq M assuming the bound f(t) \leq 2M at that value of t, then (assuming one can also verify f(t_0) \leq M for at least one "base" value of t_0) one can show that f(t) \leq M for all t unconditionally, since if f(t) exceeded M anywhere then by the intermediate value theorem we would have M < f(t) \leq 2M for at least one value of t, a contradiction. (Alternatively, one can argue that the set  f(t) \leq M \} is open, closed, and non-empty, and thus must equal all of the connected interval [0,1]). Clearly one can replace [0,1] by any other connected set here.

  • There is also a "strong induction" version of the previous trick: if, for each t \in [0,1] one can prove f(t) \leq M assuming that f(s) \leq 2M for all s < t, then f(t) \leq M in fact holds for all t \in [0,1]. Again, one can replace [0,1] by other connected intervals (though for intervals containing -\infty, one needs a base case to get started).

  • There is nothing special about the factor of 2 here. Even an epsilon gain over the trivial implication f(t) \leq M \implies f(t) \leq M, say to f(t) \leq M \implies f(t) \leq M-\varepsilon, makes all the difference between a useless implication and a highly useful one.

  • If one wants to show some sort of "exact" statement P_0, and one has discovered some sort of "non-trivial" implication of the form P_0 \implies P_0, then no conclusion can initially be drawn; but if however this non-trivial implication can be perturbed to something like P_\varepsilon \implies P_{\varepsilon/2} for all \varepsilon > 0, where P_\varepsilon is some "approximate" version of P_0, and one can already show that P_1 (say) is true, then this implies that P_\varepsilon is true for arbitrarily small \varepsilon, which can sometimes be used to recover the original statement P_0 (cf. "create an epsilon of room").

  • Again, there is nothing special about \varepsilon/2 in the previous scheme: any implication of the form P_{\varepsilon} \implies P_{\varepsilon - c(\varepsilon)} would work, so long as c(\varepsilon) is bounded away from zero whenever \varepsilon 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

Comments

Post new comment

(Note: commenting is not possible on this snapshot.)

Before posting from this form, please consider whether it would be more appropriate to make an inline comment using the Turn commenting on link near the bottom of the window. (Simply click the link, move the cursor over the article, and click on the piece of text on which you want to comment.)

snapshot
Notifications