Not signed in

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

• Username
• Password
• Remember me

• Sign in using OpenID
• Remember me

• Forgot your password?
• Apply for membership

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology definitions deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nforum nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

1. • CommentRowNumber1.
   • CommentAuthorMike Shulman
   • CommentTimeDec 30th 2017
   • PermaLink
   Author: Mike Shulman
   Format: MarkdownItexCreated [[weak excluded middle]], which is equivalent to the one of [[de Morgan's laws]] that is not intuitionistically valid.

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

2. • CommentRowNumber2.
   • CommentAuthornLab edit announcer
   • CommentTimeMay 30th 2019
   • PermaLink
   Author: nLab edit announcer
   Format: MarkdownItexPrevious 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 <a href="https://ncatlab.org/nlab/revision/diff/weak+excluded+middle/2">diff</a>, <a href="https://ncatlab.org/nlab/revision/weak+excluded+middle/2">v2</a>, <a href="https://ncatlab.org/nlab/show/weak+excluded+middle">current</a>

   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

   diff, v2, current

3. • CommentRowNumber3.
   • CommentAuthorTodd_Trimble
   • CommentTimeMay 30th 2019
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexNo, 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](https://ncatlab.org/nlab/show/Heyting+algebra#ToBooleanAlgebras) 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.

   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.

4. • CommentRowNumber4.
   • CommentAuthorMike Shulman
   • CommentTimeMay 30th 2019
   • PermaLink
   Author: Mike Shulman
   Format: MarkdownItexRolled back. (Apparently rollbacks aren't automatically announced on Forum threads?) I'd be happy for more detail to be added however.

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

5. • CommentRowNumber5.
   • CommentAuthorTodd_Trimble
   • CommentTimeMay 30th 2019
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexAdded a detail.

   Added a detail.

6. • CommentRowNumber6.
   • CommentAuthormaksr
   • CommentTimeMay 31st 2019
   • (edited May 31st 2019)
   • PermaLink
   Author: maksr
   Format: MarkdownItexThank 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))).

   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))).
   

7. • CommentRowNumber7.
   • CommentAuthornLab edit announcer
   • CommentTimeNov 16th 2022
   • PermaLink
   Author: nLab edit announcer
   Format: MarkdownItexadded links to [[De Morgan's law]], [[De Morgan Heyting algebra]], and [[De Morgan Heyting category]] Anonymous <a href="https://ncatlab.org/nlab/revision/diff/weak+excluded+middle/5">diff</a>, <a href="https://ncatlab.org/nlab/revision/weak+excluded+middle/5">v5</a>, <a href="https://ncatlab.org/nlab/show/weak+excluded+middle">current</a>

   added links to De Morgan’s law, De Morgan Heyting algebra, and De Morgan Heyting category

   Anonymous

   diff, v5, current