[Iris-Club] Excluded middle leads to inconsistency

Joseph Tassarotti jtassaro at andrew.cmu.edu
Wed May 3 11:49:38 CEST 2017


Hi all,

Thanks for the many responses. Let me just say why I found this 
surprising (setting aside the point about affine/linear BI and excluded 
middle). There is a well-known *classical* modal logic GL (for 
"Godel-Lob") that has been studied for a long time, which has a Lob 
rule. So, I didn't see any reason why the Lob rule should be 
incompatible with excluded middle!

It's true that in GL the Lob rule is instead  ▷(▷P -> P) -> ▷P, but 
Nakano showed that the stronger version we use is derivable from this 
weaker version. Therefore I assumed that the stronger rule we use should 
also be compatible with excluded middle. But apparently it isn't.

I think what's going on is that in GL one does not have P -> ▷P. And 
Nakano's proof of the equivalence of the two Lob rules relies on 
precisely this fact. So, what you can't have is weak lob + this axiom + 
excluded middle. Of course, P |- ▷P is absolutely crucial in Iris and 
the other uses of the later modality in the PL community.

-Joe

On 05/03/2017 03:07 AM, Aleš Bizjak wrote:
> Hi Joe.
>
> On 02 May 2017, at 19:53:29, Joseph Tassarotti wrote:
>
>> At ETAPS last week there was a lot of discussion about linear vs. affine
>> separation logic and classical vs. intuitionistic logic.
>>
>> I began to wonder whether we can consistently add the axiom (P \/ P ->
>> False) to the Iris base logic. I was surprised to learn that the answer is no,
>> as one is then able to derive (later False). I include a proof below. This does
>> not use any of the multiplicative connectives at all, so it's actually probably
>> the case for many guarded type theories as well. Is this mentioned anywhere? I
>> did a bit of searching, and it appears that in the modal/provability logic
>> community, it is known that P \/ ~P is inconsistent in some even weaker
>> provability logics than the base logic of Iris, but I haven't seen this pointed
>> out in the PL community.
> I don't recall any specific place where this is mentioned, but it is a
> "well-known" fact that excluded middle (in general) makes ▷ trivial.
>
> An even easier way to see this is to assume double negation elimination instead.
> Then the Löb axiom states ¬¬▷⊥, and so ▷⊥, from which ▷P for any P.
>
> This uses just the Löb rule and monotonicity of ▷.
>
> -- Aleš
>




More information about the Iris-Club mailing list