Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
3  
Perhaps psychologically we feel that the infinite sequence of Chebyshev-type estimates could, in principle, be attacked by other methods. I don't think anyone has ruled out this possibility, in any case. –  Qiaochu Yuan Jan 27 '11 at 15:53
2  
Every circular proof is also a proof of equivalence. That is, the unsatisfying circular proof, using an assumption that ends up depending on the thing to be proved, is also a proof the assumption is equivalent to the conclusion (they both imply each other). The hard part is to extract from the disappointment the bidirection or circle of implication. –  Mitch Harris Jan 27 '11 at 18:13
2  
The estimate $\psi(x)=x+O_{\varepsilon}(x^{1/2+\varepsilon})$ implies RH, which implies $\psi(x)=x+O(x^{1/2}\log^2{x})$. I've always found this rather amusing. –  David Hansen Jan 28 '11 at 1:33
1  
Given that $\sqrt{2}$ is irrational we get that for every rational with $\frac{p}{q} \le \sqrt{2}$ we have $\frac{p}{q} <\frac{p}{q}+\frac{1}{3q^2} <\sqrt{2}$ with something similar from above. –  Aaron Meyerowitz Jan 28 '11 at 6:12
4  
tricki.org/article/… –  Terry Tao Jan 28 '11 at 11:03
show 1 more comment

1 Answer 1

up vote 27 down vote accepted

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!)

share|improve this answer
    
Thanks! Löb's theorem is new to me. Did you you mean to vary the typeface of "S" that once? –  David Feldman Jan 27 '11 at 19:33
2  
This is a really nice answer Joel. –  Adam Hughes Jan 27 '11 at 19:33
    
David, that different-font S was a typo. Here is a link to Loeb's theorem on Wikipedia: en.wikipedia.org/wiki/L%C3%B6b's_theorem (watch out for the apostraphe, which somehow causes a problem). And thank you, Adam, I'm glad you like it! –  Joel David Hamkins Jan 27 '11 at 19:43
    
yudkowsky.net/rational/lobs-theorem –  Andres Caicedo Jan 27 '11 at 21:16
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.