Consider the formal system $GLS$, whose axioms are the theorems of $GL$ plus all sentences of the form $\square A\rightarrow A$.

A translation maps a sentence of modal logic to a sentence in the language of Peano Arithmetic where $\square$ is interpreted a a provability predicate.

It is well-known result that the translations of the theorems of $GLS$ are true, in the sense that they are true in the standard model of arithmetic.

However, the proof is laid on the grounds that $Bew(\ulcorner A\urcorner)\rightarrow A$ is always true for every closed sentence $A$.

But if that was the case, then I could add all such sentences as axioms to $PA$ and end up with a consistent system, since at least the standard model satisfies it.

But Löb's theorem tells us that such a system cannot possibly be consistent, suggesting that then the theorems of $GLS$ are not always true. I particular, it seems that $Bew(\ulcorner A\urcorner)\rightarrow A$ is true iff $A$ is true.

Where is the flaw in my reasoning? Am I misunderstanding something?

A formalization of how my argument goes.

Let $PA'$ stand for $PA$ plus all axioms of the form $Bew_{PA}(A)\rightarrow A$.

Let $A$ be any sentence. Then as $PA$ extends minimal arithmetic, the diagonal lemma applies, so for every formula with one free variable $\psi(x)$ we can find a sentence $B$ such that $PA\vdash B\iff \psi(\ulcorner A\urcorner)$.

Consider $\psi(x) = Bew_{PA}(x)\rightarrow A$. Then there exists $S$ such that:

$$ PA\vdash S\iff Bew_{PA}(S)\rightarrow A $$

Then by normality we have that: $$ PA\vdash Bew_{PA}(S)\rightarrow( Bew_{PA}(Bew_{PA}(S))\rightarrow Bew_{PA}(A)) $$ As we have also that: $$ PA\vdash Bew_{PA}(S)\rightarrow Bew_{PA}(Bew_{PA}(S)) $$ Then: $$ PA\vdash Bew_{PA}(S)\rightarrow Bew_{PA}(A) $$

Now, as $PA'$ extends $PA$, then we also have that: $$ PA'\vdash Bew_{PA}(S)\rightarrow Bew_{PA}(A) $$

The new axioms we have added state that: $$ PA'\vdash Bew_{PA}(A)\rightarrow A $$ Therefore: $$ PA'\vdash Bew_{PA}(S)\rightarrow A $$ But then by the very definition of $S$ we have that: $$ PA'\vdash S $$ By necessitation: $$ PA'\vdash Bew_{PA}(S) $$ And thus by modus ponens we conclude finally that: $$ PA'\vdash A $$ Since $A$ was arbitrary, it could have been $0\ne 1$. So $PA'$ is inconsistent, even though the axioms we added are true. What is going on?


1 Answer 1


Your mistake is that you mixed up the different provability operators. See the further remarks in this post. Specifically, let $\def\prov{\square}$$PA' = PA + Con(PA) = PA + \neg \prov_{PA} \bot$. Then $PA'$ is consistent and $PA' \vdash Con(PA)$ but $PA' \nvdash Con(PA') = \neg \prov_{PA'} \bot$. Lob's theorem indeed still holds for $PA'$ as expected, which involves $\prov_{PA'}$, not $\prov_{PA}$. Always remember that the modal sentences have different translations when you change the theory. $\def\imp{\rightarrow}$ $\def\eq{\leftrightarrow}$

In your edited question, your "normality" step is wrong. As I said in my linked post, it's far better to use provability logic with explicit tag on each "$\prov$" when you're playing with different theories. Look carefully at (D1). If you have $PA' \vdash φ$ you get $PA' \vdash \prov_{PA'} φ$, but you claimed in your normality step $PA' \vdash \prov_{PA} φ$, which is obviously invalid. Also, I don't know whether it is by chance that your other steps are valid, since in fact in your "normality" step you are actually attempting to use both (D1) and (D2) in one go. The use of the fixed-point lemma earlier, the (D2) part there, and the (D3) used later, turns out to be okay simply because $PA'$ extends $PA$.

In your final edited question, you're right that you can do everything in $PA$ until the "necessitation" step. But that's just (D1), which is also used in your "normality" step, so you should still have mentioned that.

  • $\begingroup$ But since $PA'$ is strictly stronger than $PA$, I should still be able to do the usual 'Santa Claus sentence' proof to conclude that since $PA'\vdash \square_{PA} \bot \rightarrow \bot$ then $PA'\vdash \bot$, amirite? $\endgroup$ Commented Jul 3, 2016 at 18:43
  • $\begingroup$ @Jsevillamol: No, for precisely the reason I state in my answer; you didn't correctly translate the modal sentence, and Lob's theorem for PA' says something using $\prov_{PA'}$, NOT $\prov_{PA}$! $\endgroup$
    – user21820
    Commented Jul 3, 2016 at 23:34
  • $\begingroup$ Forgive my stuborness, but I still do not get it. Could you please revise the edit that I just made to the question and point out my mistake? $\endgroup$ Commented Jul 4, 2016 at 1:39
  • $\begingroup$ @Jsevillamol: I've edited my answer to address your edit. Clear now? $\endgroup$
    – user21820
    Commented Jul 4, 2016 at 13:32
  • 1
    $\begingroup$ @Jsevillamol: You're welcome. I've edited my answer to make it correspond to your new question. Normally on Math SE one shouldn't edit a question to invalidate an existing answer unless the question was clearly incorrect. But here it's indeed a good observation that the problem can be delayed until nearly the end. And yes I was a bit blur concerning the fixed-point lemma, since you're right that it applies to $PA$ and $PA'$ proves the same sentence that it gives, exactly the same reason as I gave for the others... $\endgroup$
    – user21820
    Commented Jul 4, 2016 at 23:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .