Not signed in (Sign In)

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

  • Sign in using OpenID

Site Tag Cloud

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics 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 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 kan lie-theory limit 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 newpage nlab nonassociative noncommutative noncommutative-geometry number-theory object 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 string string-theory subobject superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory type type-theory universal variational-calculus

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

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • 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 ¬¬P\neg \neg P into PP.

    Best regards. Maks Romih.


    diff, v2, current

    • 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 ¬P¬Q\neg P \vee \neg Q follows from the assumption ¬(PQ)\neg (P \wedge Q). From the hypothesis of weak excluded middle, we have (¬P¬¬P)(¬Q¬¬Q)(\neg P \vee \neg \neg P) \wedge (\neg Q \vee \neg \neg Q), and then distributivity of wedgewedge over \vee (which holds in a Heyting algebra) yields

    (¬P¬Q)(¬P¬¬Q)(¬¬P¬Q)(¬¬P¬¬Q)(\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 ¬P¬Q¬P¬P¬Q\neg P \wedge \neg Q \vdash \neg P \vdash \neg P \vee \neg Q and ¬P¬¬Q¬P¬P¬Q\neg P \wedge \neg \neg Q \vdash \neg P \vdash \neg P \vee \neg Q and ¬¬P¬Q¬Q¬P¬Q\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 ¬P¬Q\neg P \vee \neg Q. In the fourth case where the assumption is ¬¬P¬¬Q\neg \neg P \wedge \neg \neg Q, it is a known result from Heyting algebras that this is equivalent to ¬¬(PQ)\neg \neg (P \wedge Q) (see the first lemma and its proof in this section of the Heyting algebra article). This ¬¬(PQ)\neg \neg (P \wedge Q) together with the assumption ¬(PQ)\neg (P \wedge Q) entails falsity which also entails ¬P¬Q\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

    Added a detail.

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

    Thank you both, you are right. Yes I didn’t know ¬¬P¬¬Q¬¬(PQ)\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 ¬P\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 ¬¬P¬¬Q¬¬(PQ)\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))).
Add your comments
  • Please log in or leave your comment as a "guest post". If commenting as a "guest", please include your name in the message as a courtesy. Note: only certain categories allow guest posts.
  • To produce a hyperlink to an nLab entry, simply put double square brackets around its name, e.g. [[category]]. To use (La)TeX mathematics in your post, make sure Markdown+Itex is selected below and put your mathematics between dollar signs as usual. Only a subset of the usual TeX math commands are accepted: see here for a list.

  • (Help)