MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

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(\lucorner\psi\rucorner)$. \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!) 1 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(\lucorner\psi\rucorner)$. 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