I learned Löb's theorem. As I understanding, if a statement is formed like "I am provable", the statement should be provable.

I want to ask further about Löb's theorem.

There is two sentences, P and Q.

P: P and Q is provable both.

Q: P and Q is provable both.


Now, can we prove that P and Q is provable both? Is this relevant to Löb's theorem?

  • 2
    $\begingroup$ Assuming your "probable" should be "provable", statements $P$ and $Q$ are the same (or at least provably equivalent), so we are exactly in the situation of Löb's theorem. $\endgroup$ – Robert Israel Mar 22 '13 at 20:11

Löb's Theorem says that,

If certain conditions hold for the theory $T$, then if $T \vdash Prov(\overline{\ulcorner\varphi\urcorner}) \to \varphi$, then $T \vdash \varphi$.

(Here $\overline{\ulcorner\varphi\urcorner}$ is $T$'s formal numeral for $\varphi$'s Gödel number under some given coding scheme: and $Prov$ is a 'provability predicate' suitably expressing the property of numbering a $T$-theorem in that scheme. Details in any textbook!)

Apply this to a Henkin sentence $H$ which is a fixed point for the provability predicate, i.e.

$T \vdash H \equiv Prov(\overline{\ulcorner H\urcorner})$

(so $H$ sort-of-says "I am provable"), and it is immediate that

$T \vdash H$.

Now: suppose (just suppose!) we have a pair of sentences $P, Q$ such that

$T \vdash P \equiv Prov(\overline{\ulcorner (P \land Q) \urcorner})$

$T \vdash Q \equiv Prov(\overline{\ulcorner (P \land Q) \urcorner})$.

So $P$ sort-of-says "$P \land Q$ is provable" and likewise for $Q$. Then trivially, we'd also have

$T \vdash (P \land Q) \equiv Prov(\overline{\ulcorner (P \land Q) \urcorner})$.

Then, by Löb's Theorem again, we'd have

$T \vdash (P \land Q)$, and hence $ T \vdash P$ and $T \vdash Q$.

But there is no novel interest in this as far as I can see.

  • $\begingroup$ Let P : "If Q is provably equivalent with P, then Q is provable." . // . Now, is P provable? $\endgroup$ – HoCheol SHIN Mar 23 '13 at 0:54
  • $\begingroup$ @HoCheolSHIN: Not necessarily. In particular if $\vdash\neg Q$, then $P$ effectively says "I am not provably equivalent to false", that is "I am not disprovable". And so $\neg P$ is provable, by Löb's theorem. (On the other hand, if $\vdash Q$ then $P$ is trivially true). $\endgroup$ – Henning Makholm Mar 23 '13 at 12:56
  • $\begingroup$ @HenningMakholm, you mean "if ⊢¬Q, then ¬P is provable. if ⊢Q, then P is provable." Hence, P effectively says "if Q is provably equivalent with P, Q is provably equivalent with P." Can we prove this P is not provable? $\endgroup$ – HoCheol SHIN Mar 23 '13 at 15:21
  • $\begingroup$ @HoCheolSHIN: No, that's not what it effectively says, since my analysis doesn't cover the possibility that neither $Q$ nor $\neg Q$ is provable. I don't have a good idea of what happens to $P$ then. $\endgroup$ – Henning Makholm Mar 23 '13 at 15:46
  • $\begingroup$ @HenningMakholm Thank you for your quick answer. // I just want to expand my original question. My original question was about two sentences P and Q. If I expand it three sentences P,Q,R, the conclusion is same. All P,Q,R is provable. // So this logic will be enlarged to infinite. // Let P: "All sentences which are equivalent with P, are provable" // by same logic, all of them look provable. $\endgroup$ – HoCheol SHIN Mar 23 '13 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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