Nontrivial circular arguments?

2011-01-27T14:48:30Z

There is a famous circular argument for the Prime Number Theorem (PNT). It turns out that there exists an infinite sequence of elementary-to-prove Chebyshev-type estimates that taken together imply PNT. Unfortunately, the collective existence of all these proofs seems to require the PNT, so one must work hard a la Selberg and Erdos for an elementary proof. See Harold Diamond, Elementary methods in the study of the distribution of prime numbers, Bull. Amer. Math. Soc. N. S. 7 (1982), 553-589.

Now on the traditional view, circular proofs simply have no value at all. Yet one feels perhaps that the example in the previous paragraph has something to say. Just an illusion? Or does there exist a foundational framework where circular proofs of this special sort enjoy bona fide status?

Just to riff a little more, imagine that the Goldbach conjecture turns out independent of PA (or some other, perhaps weaker, axiom system for arithmetic). The truth of the Goldbach conjecture (required for independence!) would then imply the existence of a proof (trivial!) for any given even number that that one even number equals the sum of two primes. Now that obviously isn't very interesting compared to the example in the first paragraph, and perhaps the difference has something to do with the greater quantifier complexity of PNT?

As a side question, are there any similar stories in the lore of the Riemann Hypothesis? For example, does RH imply the existence of an infinite sequence of zero-free region proofs of a known form that collectively amount to RH?

EDIT: Lest this come up repeatedly, let me expand upon a remark I made in a comment below:

I would be interested to know if RH implies the existence of proofs of a known form in a known system within which one does not assume RH, such that the conclusions of all these proofs conjunctively yield RH.

Actually the answer to my question is "yes" though I find my own example unsatisfying (rather like the Goldbach example):

We can check zeros up to a given magnitude rigorously by known (non-trivial) numerical techniques. RH predicts these tests will come out positive, but of course the tests don't rely on RH. If we know they all come out positive, that's RH. I find this unsatisfying because the little proofs approximate the whole of RH so badly (compared to how the Chebyshev estimates really do make one feel one has PNT for all practical purposes). Now a family of zero-free regions that union up to $\sigma >1/2$ where each new zero-free region had strong arithmetic consequences, that would seem interesting.

Answer by Joel David Hamkins for Nontrivial circular arguments?

2011-01-27T19:04:04Z

Perhaps an example of the kind of circularity you mention arises with the self-reference phenomenon that arises in connection with the incompleteness theorems and related applications. Specifically, Gödel proved the fixed-point lemma that for any assertion $\varphi(x)$ in arithmetic, there is a sentence $\psi$ such that PA, or any sufficiently powerful and expressible theory, proves that $\psi$ is equivalent to $\varphi(\ulcorner\psi\urcorner)$. In other words, $\psi$ is equivalent to the statement "$\psi$ has property $\varphi$." Thus, statements in the language of arithmetic can refer to themselves, and so self-reference, the stuff of paradox and nonsense, enters our beautiful number theory.

One famous example, used by Gödel to prove the first incompleteness theorem, occurs when $\varphi(x)$ asserts, "$x$ is the code of a statement having no proof in PA", for then the resulting fixed point $\psi$ effectively asserts "this statement is not provable". It follows now that it cannot be provable, for then it would be a false provable statement, and so it is true. Thus, it is a true unprovable statement, establishing the first incompleteness theorem.

A dual version of this, however, exhibits your circularity property in a stronger way. Namely, let us apply the fixed point lemma to the formula $p(x)$ asserting "$x$ is the code of a statement provable in PA." In this case, the resulting fixed point $\psi$ asserts "this statement IS provable." Consider now the following theorem of Löb:

Theorem.(Löb) If the Peano Axioms (PA) prove the implication (PA proves $\varphi$)$\to\varphi$, then PA proves $\varphi$ directly.

(And the converse is immediate, so PA proves that (PA proves $\varphi$)$\to \varphi$ if and only if PA proves $\varphi$.)

In the case of $\psi$ asserting "$\psi$ is provable," we have that the hypothesis of Löb's theorem holds, and so we may make the conclusion that yes, indeed, $\psi$ really is provable! In other words, the statement "this statement is provable" really is provable, although no naive argument will establish this.

The proof of Löb's theorem is itself a surprising exercise in circularity, something like the following:

Theorem. Santa exists.

Proof. Let $S$ be the statement, "If S holds, then Santa exists." Now, we claim that $S$ is true. Since it is an implication, we assume the hypothesis, and argue for the conclusion. So assume that the hypothesis of S is true; that is, assume $S$ holds. But then the implication expressed by $S$ is true. So the conclusion that Santa exists is also true. So we have shown under the assumption of the hypothesis of $S$ that the conclusion is true. So we have established that $S$ holds. Now, by $S$, it follows that Santa exists. QED

(Those who know the proof of Löb's theorem will agree that the proof is fundamentally the same as the above, except that it is fully rigorous nonsense instead of silly nonsense!)

Nontrivial circular arguments? - MathOverflow

Nontrivial circular arguments?

Answer by Joel David Hamkins for Nontrivial circular arguments?