2

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?

martian03
  • 75
  • 2
    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. – Robert Israel Mar 22 '13 at 20:11

1 Answers1

5

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.

Community
  • 1
Peter Smith
  • 54,743
  • Let P : "If Q is provably equivalent with P, then Q is provable." . // . Now, is P provable? – martian03 Mar 23 '13 at 00:54
  • @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). – hmakholm left over Monica Mar 23 '13 at 12:56
  • @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? – martian03 Mar 23 '13 at 15:21
  • @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. – hmakholm left over Monica Mar 23 '13 at 15:46
  • @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. – martian03 Mar 23 '13 at 16:00