Start a new discussion

Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

Site Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

• CommentRowNumber1.
• CommentAuthorMike Shulman
• CommentTimeDec 30th 2017

Created weak excluded middle, which is equivalent to the one of de Morgan’s laws that is not intuitionistically valid.

1. Previous proof of the fourth case was wrong because it used the classical logic to convert $\neg \neg P$ into $P$.

Best regards. Maks Romih.

maksr

• CommentRowNumber3.
• CommentAuthorTodd_Trimble
• CommentTimeMay 30th 2019

No, the previous proof did not do that. I think you misunderstood the argument. I’ll spell out in more detail what the previous argument was:

We are trying to show that $\neg P \vee \neg Q$ follows from the assumption $\neg (P \wedge Q)$. From the hypothesis of weak excluded middle, we have $(\neg P \vee \neg \neg P) \wedge (\neg Q \vee \neg \neg Q)$, and then distributivity of $wedge$ over $\vee$ (which holds in a Heyting algebra) yields

$(\neg P \wedge \neg Q) \vee (\neg P \wedge \neg \neg Q) \vee (\neg \neg P \wedge \neg Q) \vee (\neg \neg P \wedge \neg \neg Q)$

where we have $\neg P \wedge \neg Q \vdash \neg P \vdash \neg P \vee \neg Q$ and $\neg P \wedge \neg \neg Q \vdash \neg P \vdash \neg P \vee \neg Q$ and $\neg \neg P \wedge \neg Q \vdash \neg Q \vdash \neg P \vee \neg Q$. So in each of these three cases, we can infer $\neg P \vee \neg Q$. In the fourth case where the assumption is $\neg \neg P \wedge \neg \neg Q$, it is a known result from Heyting algebras that this is equivalent to $\neg \neg (P \wedge Q)$ (see the first lemma and its proof in this section of the Heyting algebra article). This $\neg \neg (P \wedge Q)$ together with the assumption $\neg (P \wedge Q)$ entails falsity which also entails $\neg P \vee \neg Q$.

If need be, this greater level of detail can be added, but under the general informal nLab rule that edits which erase the useful work of others should be undone, I would be inclined to roll back to the previous version.

• CommentRowNumber4.
• CommentAuthorMike Shulman
• CommentTimeMay 30th 2019

Rolled back. (Apparently rollbacks aren’t automatically announced on Forum threads?) I’d be happy for more detail to be added however.

• CommentRowNumber5.
• CommentAuthorTodd_Trimble
• CommentTimeMay 30th 2019

• CommentRowNumber6.
• CommentAuthormaksr
• CommentTimeMay 31st 2019
• (edited May 31st 2019)

Thank you both, you are right. Yes I didn’t know $\neg \neg P \wedge \neg \neg Q \to \neg \neg (P \wedge Q)$. When I tried to prove it in Coq, it seemed that the fourth case is not a contradiction, because I could produce $\neg P$ from it, but of course, when there is a contradiction you can prove anything.

Just in case, here is my Coq proof of $\neg \neg P \to \neg \neg Q \to \neg \neg (P \wedge Q)$:

Check (fun (P Q:Prop)(nnp:~~P)(nnq:~~Q)
=> fun npq
=> nnp (fun p
=> nnq ((fun p q
=> npq (conj p q)) p))).