Want to take part in these discussions? Sign in if you have an account, or apply for one below
Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.
Created weak excluded middle, which is equivalent to the one of de Morgan’s laws that is not intuitionistically valid.
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.
Rolled back. (Apparently rollbacks aren’t automatically announced on Forum threads?) I’d be happy for more detail to be added however.
Added a detail.
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))).
1 to 6 of 6