*[HoTT] A question about the problem with regularity in CCHM cubical type theory@ 2019-09-13 6:10 Jasper Hugunin2019-09-15 5:57 ` [HoTT] " Jasper Hugunin 2019-09-15 11:55 ` [HoTT] " Andrew Swan 0 siblings, 2 replies; 13+ messages in thread From: Jasper Hugunin @ 2019-09-13 6:10 UTC (permalink / raw) To: HomotopyTypeTheory [-- Attachment #1: Type: text/plain, Size: 2138 bytes --] Hello all, I've been trying to understand better why composition for the universe does not satisfy regularity. Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts: 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself) 2. That equiv^i (refl A) reduces to equivRefl A I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument. Context: I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly. If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in this thread on the HoTT mailing list <https://groups.google.com/d/msg/homotopytypetheory/oXQe5u_Mmtk/3HEDk5g5uq4J>, the definition of composition for the universe was found to not satisfy regularity. I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in the CCHM paper <http://www.cse.chalmers.se/~coquand/cubicaltt.pdf> (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything). Best regards, - Jasper Hugunin -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8fo4FKCLiCVCYm6AGeVc%3DqB8QNUZ3Weho6kLT8NXtc-Q%40mail.gmail.com. [-- Attachment #2: Type: text/html, Size: 2723 bytes --] <div dir="ltr">Hello all,<div><br></div><div><div>I've been trying to understand better why composition for the universe does not satisfy regularity.</div><div>Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts:</div><div>1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself)</div><div>2. That equiv^i (refl A) reduces to equivRefl A</div><div>I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument.</div><div><br></div><div>Context:</div><div><div>I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly.</div><div>If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in <a href="https://groups.google.com/d/msg/homotopytypetheory/oXQe5u_Mmtk/3HEDk5g5uq4J" target="_blank">this thread on the HoTT mailing list</a>, the definition of composition for the universe was found to not satisfy regularity.</div><div>I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in <a href="http://www.cse.chalmers.se/~coquand/cubicaltt.pdf" target="_blank">the CCHM paper</a> (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything).</div><div><br></div></div></div><div>Best regards,</div><div>- Jasper Hugunin</div></div> <p></p> -- <br /> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br /> To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br /> To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8fo4FKCLiCVCYm6AGeVc%3DqB8QNUZ3Weho6kLT8NXtc-Q%40mail.gmail.com?utm_medium=email&utm_source=footer">https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8fo4FKCLiCVCYm6AGeVc%3DqB8QNUZ3Weho6kLT8NXtc-Q%40mail.gmail.com</a>.<br /> ^ permalink raw reply [flat|nested] 13+ messages in thread

*[HoTT] Re: A question about the problem with regularity in CCHM cubical type theory2019-09-13 6:10 [HoTT] A question about the problem with regularity in CCHM cubical type theory Jasper Hugunin@ 2019-09-15 5:57 ` " Jasper Hugunin[not found] ` <CAMWCppk4PWzfZ1HKNLMdAZ=RBC-ARxtJXR8okvwO3raea5gC8Q@mail.gmail.com> 2019-09-15 11:55 ` [HoTT] " Andrew Swan 1 sibling, 1 reply; 13+ messages in thread From: Jasper Hugunin @ 2019-09-15 5:57 UTC (permalink / raw) To: HomotopyTypeTheory [-- Attachment #1: Type: text/plain, Size: 2788 bytes --] Offline, Carlo Angiuli showed me that the difficulty was in part 1, because of a subtlety I had been forgetting. Since types are *Kan* cubical sets, we need that the Kan operations agree as well as the sets. So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, compGlue) = (A, compA), and getting that the Kan operations to agree was/is difficult. (Now that I know what the answer is, it is clear that this was already explained in the initial discussion.) Humbly, - Jasper Hugunin On Fri, Sep 13, 2019 at 2:10 AM Jasper Hugunin <jasperh@cs.washington.edu> wrote: > Hello all, > > I've been trying to understand better why composition for the universe > does not satisfy regularity. > Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> > equiv^i E ] A, I would expect regularity to follow from two parts: > 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity > condition for the Glue type constructor itself) > 2. That equiv^i (refl A) reduces to equivRefl A > I'm curious as to which (or both) of these parts was the issue, or if > regularity for the universe was supposed to follow from a different > argument. > > Context: > I've been studying and using CCHM cubical type theory recently, and often > finding myself wishing that J computed strictly. > If I understand correctly, early implementations of ctt did have strict J > for Path types, and this was justified by a "regularity" condition on the > composition operation, but as discussed in this thread on the HoTT > mailing list > <https://groups.google.com/d/msg/homotopytypetheory/oXQe5u_Mmtk/3HEDk5g5uq4J>, > the definition of composition for the universe was found to not satisfy > regularity. > I don't remember seeing the regularity condition defined anywhere, but my > understanding is that it requires that composition in a degenerate line of > types, with the system of constraints giving the sides of the box also > degenerate in that direction, reduces to just the bottom of the box. This > seems to be closed under the usual type formers, plus Glue, but not the > universe with computation defined as in the CCHM paper > <http://www.cse.chalmers.se/~coquand/cubicaltt.pdf> (for trivial reasons > and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> > equiv^i refl ] A not reducing to anything). > > Best regards, > - Jasper Hugunin > -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com. [-- Attachment #2: Type: text/html, Size: 3671 bytes --] <div dir="ltr">Offline, Carlo Angiuli showed me that the difficulty was in part 1, because of a subtlety I had been forgetting.<div><br></div><div>Since types are *Kan* cubical sets, we need that the Kan operations agree as well as the sets.</div><div>So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, compGlue) = (A, compA), and getting that the Kan operations to agree was/is difficult.</div><div>(Now that I know what the answer is, it is clear that this was already explained in the initial discussion.)</div><div><br></div><div>Humbly,</div><div>- Jasper Hugunin</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Sep 13, 2019 at 2:10 AM Jasper Hugunin <<a href="mailto:jasperh@cs.washington.edu">jasperh@cs.washington.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hello all,<div><br></div><div><div>I've been trying to understand better why composition for the universe does not satisfy regularity.</div><div>Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts:</div><div>1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself)</div><div>2. That equiv^i (refl A) reduces to equivRefl A</div><div>I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument.</div><div><br></div><div>Context:</div><div><div>I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly.</div><div>If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in <a href="https://groups.google.com/d/msg/homotopytypetheory/oXQe5u_Mmtk/3HEDk5g5uq4J" target="_blank">this thread on the HoTT mailing list</a>, the definition of composition for the universe was found to not satisfy regularity.</div><div>I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in <a href="http://www.cse.chalmers.se/~coquand/cubicaltt.pdf" target="_blank">the CCHM paper</a> (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything).</div><div><br></div></div></div><div>Best regards,</div><div>- Jasper Hugunin</div></div> </blockquote></div> <p></p> -- <br /> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br /> To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br /> To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com?utm_medium=email&utm_source=footer">https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com</a>.<br /> ^ permalink raw reply [flat|nested] 13+ messages in thread

*[HoTT] Re: A question about the problem with regularity in CCHM cubical type theory2019-09-13 6:10 [HoTT] A question about the problem with regularity in CCHM cubical type theory Jasper Hugunin 2019-09-15 5:57 ` [HoTT] " Jasper Hugunin@ 2019-09-15 11:55 ` " Andrew Swan2019-09-15 22:38 ` Jasper Hugunin 2019-09-16 1:04 ` Jon Sterling 1 sibling, 2 replies; 13+ messages in thread From: Andrew Swan @ 2019-09-15 11:55 UTC (permalink / raw) To: Homotopy Type Theory [-- Attachment #1.1: Type: text/plain, Size: 2683 bytes --] You might have already seen this, but I have a paper on some related issues at https://arxiv.org/abs/1808.00920 . In that paper I didn't look at the original version of regularity, but a more recent version ("all monomorphisms are cofibrations") that fits better with the general framework of Orton and Pitts. In that case it is definitely equality of objects that causes problems. Best, Andrew On Friday, 13 September 2019 08:10:42 UTC+2, Jasper Hugunin wrote: > > Hello all, > > I've been trying to understand better why composition for the universe > does not satisfy regularity. > Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> > equiv^i E ] A, I would expect regularity to follow from two parts: > 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity > condition for the Glue type constructor itself) > 2. That equiv^i (refl A) reduces to equivRefl A > I'm curious as to which (or both) of these parts was the issue, or if > regularity for the universe was supposed to follow from a different > argument. > > Context: > I've been studying and using CCHM cubical type theory recently, and often > finding myself wishing that J computed strictly. > If I understand correctly, early implementations of ctt did have strict J > for Path types, and this was justified by a "regularity" condition on the > composition operation, but as discussed in this thread on the HoTT > mailing list > <https://groups.google.com/d/msg/homotopytypetheory/oXQe5u_Mmtk/3HEDk5g5uq4J>, > the definition of composition for the universe was found to not satisfy > regularity. > I don't remember seeing the regularity condition defined anywhere, but my > understanding is that it requires that composition in a degenerate line of > types, with the system of constraints giving the sides of the box also > degenerate in that direction, reduces to just the bottom of the box. This > seems to be closed under the usual type formers, plus Glue, but not the > universe with computation defined as in the CCHM paper > <http://www.cse.chalmers.se/~coquand/cubicaltt.pdf> (for trivial reasons > and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> > equiv^i refl ] A not reducing to anything). > > Best regards, > - Jasper Hugunin > -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com. [-- Attachment #1.2: Type: text/html, Size: 4094 bytes --] <div dir="ltr">You might have already seen this, but I have a paper on some related issues at <a href="https://arxiv.org/abs/1808.00920">https://arxiv.org/abs/1808.00920</a> . In that paper I didn't look at the original version of regularity, but a more recent version ("all monomorphisms are cofibrations") that fits better with the general framework of Orton and Pitts. In that case it is definitely equality of objects that causes problems.<div><br></div><div>Best,</div><div>Andrew<br><br>On Friday, 13 September 2019 08:10:42 UTC+2, Jasper Hugunin wrote:<blockquote class="gmail_quote" style="margin: 0;margin-left: 0.8ex;border-left: 1px #ccc solid;padding-left: 1ex;"><div dir="ltr">Hello all,<div><br></div><div><div>I've been trying to understand better why composition for the universe does not satisfy regularity.</div><div>Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts:</div><div>1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself)</div><div>2. That equiv^i (refl A) reduces to equivRefl A</div><div>I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument.</div><div><br></div><div>Context:</div><div><div>I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly.</div><div>If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in <a href="https://groups.google.com/d/msg/homotopytypetheory/oXQe5u_Mmtk/3HEDk5g5uq4J" target="_blank" rel="nofollow" onmousedown="this.href='https://groups.google.com/d/msg/homotopytypetheory/oXQe5u_Mmtk/3HEDk5g5uq4J';return true;" onclick="this.href='https://groups.google.com/d/msg/homotopytypetheory/oXQe5u_Mmtk/3HEDk5g5uq4J';return true;">this thread on the HoTT mailing list</a>, the definition of composition for the universe was found to not satisfy regularity.</div><div>I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in <a href="http://www.cse.chalmers.se/~coquand/cubicaltt.pdf" target="_blank" rel="nofollow" onmousedown="this.href='http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.cse.chalmers.se%2F~coquand%2Fcubicaltt.pdf\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNEwGF-VNBcwNjl2ZnvRdrx2CgOJPQ';return true;" onclick="this.href='http://www.google.com/url?q\x3dhttp%3A%2F%2Fwww.cse.chalmers.se%2F~coquand%2Fcubicaltt.pdf\x26sa\x3dD\x26sntz\x3d1\x26usg\x3dAFQjCNEwGF-VNBcwNjl2ZnvRdrx2CgOJPQ';return true;">the CCHM paper</a> (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything).</div><div><br></div></div></div><div>Best regards,</div><div>- Jasper Hugunin</div></div> </blockquote></div></div> <p></p> -- <br /> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br /> To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br /> To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com?utm_medium=email&utm_source=footer">https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com</a>.<br /> ^ permalink raw reply [flat|nested] 13+ messages in thread

*Re: [HoTT] Re: A question about the problem with regularity in CCHM cubical type theory2019-09-15 11:55 ` [HoTT] " Andrew Swan@ 2019-09-15 22:38 ` Jasper Hugunin2019-09-16 1:04 ` Jon Sterling 1 sibling, 0 replies; 13+ messages in thread From: Jasper Hugunin @ 2019-09-15 22:38 UTC (permalink / raw) To: HomotopyTypeTheory [-- Attachment #1: Type: text/plain, Size: 5326 bytes --] In CCHM, my understanding is that composition for Glue [ phi |-> (T, f) ] A is actually regular, and reduces to composition in T on (forall i. phi), assuming composition is regular for A and T. The regularity does seem to fail in ABCFHL, as you pointed out Anders, but is perhaps repairable. What Carlo told me was that the problem is getting composition for Glue [ phi |-> (T, f) ] A which is regular, reduces to composition in T on (forall i. phi), *and* reduces to composition in A when (T, f) = (A, equivRefl). We get the first two but not the third in CCHM. The problem as Carlo explained it was that given a square of types i, j |- A and a point a : A (i0) (j0), we can prove Path (coe^i A o coe^j A) (coe^j A o coe^i A) (coercing around the square in right then up vs up then right), and (assuming regularity for A), we can take this to be degenerate when A is degenerate in i, or give a different path which is degenerate when A is degenerate in j, but constructing a path which is degenerate when A is degenerate in i or j is elusive. I have an idea for how to add new terms/operations (a sort of generalization of comp) such that such a path is constructible, but I haven't yet checked that there is a univalent universe with these more general operations. I also don't understand the negative results from Andrew well enough to tell if they rule out such an approach. The idea is to add terms witnessing that for every square x, y |- A x y we have Path (coe^i (A i i)) ((coe^i (A i 0)) o (coe^i (A 1 i))) which is degenerate when A is degenerate in x OR y, plus similar terms for higher cubes, since once you need dimensions one and two you probably need dimension n, and a similar thing for hcomp, or you can do coe and hcomp together in just comp. Composing two of these paths then gives the needed proof that coercing around the square either way is equal, in a degenerate fashion if A is degenerate in x or y. Best regards, - Jasper Hugunin On Sun, Sep 15, 2019 at 7:55 AM Andrew Swan <wakelin.swan@gmail.com> wrote: > You might have already seen this, but I have a paper on some related > issues at https://arxiv.org/abs/1808.00920 . In that paper I didn't look > at the original version of regularity, but a more recent version ("all > monomorphisms are cofibrations") that fits better with the general > framework of Orton and Pitts. In that case it is definitely equality of > objects that causes problems. > > Best, > Andrew > > On Friday, 13 September 2019 08:10:42 UTC+2, Jasper Hugunin wrote: >> >> Hello all, >> >> I've been trying to understand better why composition for the universe >> does not satisfy regularity. >> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> >> equiv^i E ] A, I would expect regularity to follow from two parts: >> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity >> condition for the Glue type constructor itself) >> 2. That equiv^i (refl A) reduces to equivRefl A >> I'm curious as to which (or both) of these parts was the issue, or if >> regularity for the universe was supposed to follow from a different >> argument. >> >> Context: >> I've been studying and using CCHM cubical type theory recently, and often >> finding myself wishing that J computed strictly. >> If I understand correctly, early implementations of ctt did have strict J >> for Path types, and this was justified by a "regularity" condition on the >> composition operation, but as discussed in this thread on the HoTT >> mailing list >> <https://groups.google.com/d/msg/homotopytypetheory/oXQe5u_Mmtk/3HEDk5g5uq4J>, >> the definition of composition for the universe was found to not satisfy >> regularity. >> I don't remember seeing the regularity condition defined anywhere, but my >> understanding is that it requires that composition in a degenerate line of >> types, with the system of constraints giving the sides of the box also >> degenerate in that direction, reduces to just the bottom of the box. This >> seems to be closed under the usual type formers, plus Glue, but not the >> universe with computation defined as in the CCHM paper >> <http://www.cse.chalmers.se/~coquand/cubicaltt.pdf> (for trivial reasons >> and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> >> equiv^i refl ] A not reducing to anything). >> >> Best regards, >> - Jasper Hugunin >> > -- > You received this message because you are subscribed to the Google Groups > "Homotopy Type Theory" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com > <https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9XATMbfyyp00M8kqiEoFyj7XsxahMa3AdzXth_%3DLbTiA%40mail.gmail.com. [-- Attachment #2: Type: text/html, Size: 6717 bytes --] <div dir="ltr"><div>In CCHM, my understanding is that composition for Glue [ phi |-> (T, f) ] A is actually regular, and reduces to composition in T on (forall i. phi), assuming composition is regular for A and T.<br></div><div>The regularity does seem to fail in ABCFHL, as you pointed out Anders, but is perhaps repairable.</div><div><br></div><div>What Carlo told me was that the problem is getting composition for Glue [ phi |-> (T, f) ] A which is regular, reduces to composition in T on (forall i. phi), *and* reduces to composition in A when (T, f) = (A, equivRefl).</div><div>We get the first two but not the third in CCHM.</div><div><br></div><div>The problem as Carlo explained it was that given a square of types i, j |- A and a point a : A (i0) (j0), we can prove Path (coe^i A o coe^j A) (coe^j A o coe^i A) (coercing around the square in right then up vs up then right), and (assuming regularity for A), we can take this to be degenerate when A is degenerate in i, or give a different path which is degenerate when A is degenerate in j, but constructing a path which is degenerate when A is degenerate in i or j is elusive.</div><div><br></div><div>I have an idea for how to add new terms/operations (a sort of generalization of comp) such that such a path is constructible, but I haven't yet checked that there is a univalent universe with these more general operations.</div><div>I also don't understand the negative results from Andrew well enough to tell if they rule out such an approach.</div><div><br></div><div>The idea is to add terms witnessing that for every square x, y |- A x y we have Path (coe^i (A i i)) ((coe^i (A i 0)) o (coe^i (A 1 i))) which is degenerate when A is degenerate in x OR y, plus similar terms for higher cubes, since once you need dimensions one and two you probably need dimension n, and a similar thing for hcomp, or you can do coe and hcomp together in just comp.</div><div>Composing two of these paths then gives the needed proof that coercing around the square either way is equal, in a degenerate fashion if A is degenerate in x or y.<br></div><div> </div><div>Best regards,</div><div>- Jasper Hugunin</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Sep 15, 2019 at 7:55 AM Andrew Swan <<a href="mailto:wakelin.swan@gmail.com">wakelin.swan@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">You might have already seen this, but I have a paper on some related issues at <a href="https://arxiv.org/abs/1808.00920" target="_blank">https://arxiv.org/abs/1808.00920</a> . In that paper I didn't look at the original version of regularity, but a more recent version ("all monomorphisms are cofibrations") that fits better with the general framework of Orton and Pitts. In that case it is definitely equality of objects that causes problems.<div><br></div><div>Best,</div><div>Andrew<br><br>On Friday, 13 September 2019 08:10:42 UTC+2, Jasper Hugunin wrote:<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hello all,<div><br></div><div><div>I've been trying to understand better why composition for the universe does not satisfy regularity.</div><div>Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts:</div><div>1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself)</div><div>2. That equiv^i (refl A) reduces to equivRefl A</div><div>I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument.</div><div><br></div><div>Context:</div><div><div>I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly.</div><div>If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in <a href="https://groups.google.com/d/msg/homotopytypetheory/oXQe5u_Mmtk/3HEDk5g5uq4J" rel="nofollow" target="_blank">this thread on the HoTT mailing list</a>, the definition of composition for the universe was found to not satisfy regularity.</div><div>I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in <a href="http://www.cse.chalmers.se/~coquand/cubicaltt.pdf" rel="nofollow" target="_blank">the CCHM paper</a> (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything).</div><div><br></div></div></div><div>Best regards,</div><div>- Jasper Hugunin</div></div> </blockquote></div></div> <p></p> -- <br> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br> To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com" target="_blank">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br> To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com?utm_medium=email&utm_source=footer" target="_blank">https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com</a>.<br> </blockquote></div> <p></p> -- <br /> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br /> To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br /> To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9XATMbfyyp00M8kqiEoFyj7XsxahMa3AdzXth_%3DLbTiA%40mail.gmail.com?utm_medium=email&utm_source=footer">https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9XATMbfyyp00M8kqiEoFyj7XsxahMa3AdzXth_%3DLbTiA%40mail.gmail.com</a>.<br /> ^ permalink raw reply [flat|nested] 13+ messages in thread

*Re: [HoTT] Re: A question about the problem with regularity in CCHM cubical type theory2019-09-15 11:55 ` [HoTT] " Andrew Swan 2019-09-15 22:38 ` Jasper Hugunin@ 2019-09-16 1:04 ` Jon Sterling[not found] ` <A605E6EE-0101-4390-B50D-A6AEB36FDCC2@icloud.com> 1 sibling, 1 reply; 13+ messages in thread From: Jon Sterling @ 2019-09-16 1:04 UTC (permalink / raw) To: Martin Escardo' via Homotopy Type Theory Hi Andrew, Does "all monomorphisms are cofibrations" imply that identity and path types coincide? or only the other way around? Thanks, Jon On Sun, Sep 15, 2019, at 7:55 AM, Andrew Swan wrote: > You might have already seen this, but I have a paper on some related > issues at https://arxiv.org/abs/1808.00920 . In that paper I didn't > look at the original version of regularity, but a more recent version > ("all monomorphisms are cofibrations") that fits better with the > general framework of Orton and Pitts. In that case it is definitely > equality of objects that causes problems. > > Best, > Andrew > > On Friday, 13 September 2019 08:10:42 UTC+2, Jasper Hugunin wrote: > > Hello all, > > > > I've been trying to understand better why composition for the universe does not satisfy regularity. > > Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts: > > 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself) > > 2. That equiv^i (refl A) reduces to equivRefl A > > I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument. > > > > Context: > > I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly. > > If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in this thread on the HoTT mailing list <https://groups.google.com/d/msg/homotopytypetheory/oXQe5u_Mmtk/3HEDk5g5uq4J>, the definition of composition for the universe was found to not satisfy regularity. > > I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in the CCHM paper <http://www.cse.chalmers.se/~coquand/cubicaltt.pdf> (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything). > > > > Best regards, > > - Jasper Hugunin > > -- > You received this message because you are subscribed to the Google > Groups "Homotopy Type Theory" group. > To unsubscribe from this group and stop receiving emails from it, send > an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com <https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com?utm_medium=email&utm_source=footer>. -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/80a2be3b-afaa-4106-9c69-0df6567ec709%40www.fastmail.com. ^ permalink raw reply [flat|nested] 13+ messages in thread

*Re: [HoTT] Re: A question about the problem with regularity in CCHM cubical type theory[not found] ` <A605E6EE-0101-4390-B50D-A6AEB36FDCC2@icloud.com>@ 2019-09-16 1:44 ` Jon Sterling0 siblings, 0 replies; 13+ messages in thread From: Jon Sterling @ 2019-09-16 1:44 UTC (permalink / raw) To: steve awodey;+Cc:Martin Escardo' via Homotopy Type Theory [-- Attachment #1: Type: text/plain, Size: 4321 bytes --] Thanks Steve! On Sun, Sep 15, 2019, at 9:38 PM, steve awodey wrote: > It does: the relf term is always a weak equivalence by 3 for 2, and it’s monic because it’s a section. > > Sent from my iPhone > > > On Sep 15, 2019, at 21:04, Jon Sterling <jon@jonmsterling.com> wrote: > > > > Hi Andrew, > > > > Does "all monomorphisms are cofibrations" imply that identity and path types coincide? or only the other way around? > > > > Thanks, > > Jon > > > > > >> On Sun, Sep 15, 2019, at 7:55 AM, Andrew Swan wrote: > >> You might have already seen this, but I have a paper on some related > >> issues at https://arxiv.org/abs/1808.00920 . In that paper I didn't > >> look at the original version of regularity, but a more recent version > >> ("all monomorphisms are cofibrations") that fits better with the > >> general framework of Orton and Pitts. In that case it is definitely > >> equality of objects that causes problems. > >> > >> Best, > >> Andrew > >> > >>> On Friday, 13 September 2019 08:10:42 UTC+2, Jasper Hugunin wrote: > >>> Hello all, > >>> > >>> I've been trying to understand better why composition for the universe does not satisfy regularity. > >>> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts: > >>> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself) > >>> 2. That equiv^i (refl A) reduces to equivRefl A > >>> I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument. > >>> > >>> Context: > >>> I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly. > >>> If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in this thread on the HoTT mailing list <https://groups.google.com/d/msg/homotopytypetheory/oXQe5u_Mmtk/3HEDk5g5uq4J>, the definition of composition for the universe was found to not satisfy regularity. > >>> I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in the CCHM paper <http://www.cse.chalmers.se/~coquand/cubicaltt.pdf> (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything). > >>> > >>> Best regards, > >>> - Jasper Hugunin > >> > >> -- > >> You received this message because you are subscribed to the Google > >> Groups "Homotopy Type Theory" group. > >> To unsubscribe from this group and stop receiving emails from it, send > >> an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > >> To view this discussion on the web visit > >> https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com <https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com?utm_medium=email&utm_source=footer>. > > > > -- > > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. > > To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/80a2be3b-afaa-4106-9c69-0df6567ec709%40www.fastmail.com. > > -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/afe67df2-7f4a-4e51-abc9-3f8e3a985623%40www.fastmail.com. [-- Attachment #2: Type: text/html, Size: 7451 bytes --] <!DOCTYPE html><html><head><title></title><style type="text/css">p.MsoNormal,p.MsoNoSpacing{margin:0}</style></head><body><div style="font-family:Arial;">Thanks Steve!</div><div style="font-family:Arial;"><br></div><div>On Sun, Sep 15, 2019, at 9:38 PM, steve awodey wrote:<br></div><blockquote type="cite" id="qt"><div style="font-family:Arial;">It does: the relf term is always a weak equivalence by 3 for 2, and it’s monic because it’s a section. <br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">Sent from my iPhone<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;">> On Sep 15, 2019, at 21:04, Jon Sterling <jon@jonmsterling.com> wrote:<br></div><div style="font-family:Arial;">> <br></div><div style="font-family:Arial;">> Hi Andrew,<br></div><div style="font-family:Arial;">> <br></div><div style="font-family:Arial;">> Does "all monomorphisms are cofibrations" imply that identity and path types coincide? or only the other way around?<br></div><div style="font-family:Arial;">> <br></div><div style="font-family:Arial;">> Thanks,<br></div><div style="font-family:Arial;">> Jon<br></div><div style="font-family:Arial;">> <br></div><div style="font-family:Arial;">> <br></div><div style="font-family:Arial;">>> On Sun, Sep 15, 2019, at 7:55 AM, Andrew Swan wrote:<br></div><div style="font-family:Arial;">>> You might have already seen this, but I have a paper on some related <br></div><div style="font-family:Arial;">>> issues at https://arxiv.org/abs/1808.00920 . In that paper I didn't <br></div><div style="font-family:Arial;">>> look at the original version of regularity, but a more recent version <br></div><div style="font-family:Arial;">>> ("all monomorphisms are cofibrations") that fits better with the <br></div><div style="font-family:Arial;">>> general framework of Orton and Pitts. In that case it is definitely <br></div><div style="font-family:Arial;">>> equality of objects that causes problems.<br></div><div style="font-family:Arial;">>> <br></div><div style="font-family:Arial;">>> Best,<br></div><div style="font-family:Arial;">>> Andrew<br></div><div style="font-family:Arial;">>> <br></div><div style="font-family:Arial;">>>> On Friday, 13 September 2019 08:10:42 UTC+2, Jasper Hugunin wrote:<br></div><div style="font-family:Arial;">>>> Hello all,<br></div><div style="font-family:Arial;">>>> <br></div><div style="font-family:Arial;">>>> I've been trying to understand better why composition for the universe does not satisfy regularity.<br></div><div style="font-family:Arial;">>>> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts:<br></div><div style="font-family:Arial;">>>> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself)<br></div><div style="font-family:Arial;">>>> 2. That equiv^i (refl A) reduces to equivRefl A<br></div><div style="font-family:Arial;">>>> I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument.<br></div><div style="font-family:Arial;">>>> <br></div><div style="font-family:Arial;">>>> Context:<br></div><div style="font-family:Arial;">>>> I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly.<br></div><div style="font-family:Arial;">>>> If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in this thread on the HoTT mailing list <https://groups.google.com/d/msg/homotopytypetheory/oXQe5u_Mmtk/3HEDk5g5uq4J>, the definition of composition for the universe was found to not satisfy regularity.<br></div><div style="font-family:Arial;">>>> I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in the CCHM paper <http://www.cse.chalmers.se/~coquand/cubicaltt.pdf> (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything).<br></div><div style="font-family:Arial;">>>> <br></div><div style="font-family:Arial;">>>> Best regards,<br></div><div style="font-family:Arial;">>>> - Jasper Hugunin<br></div><div style="font-family:Arial;">>> <br></div><div style="font-family:Arial;">>> -- <br></div><div style="font-family:Arial;">>> You received this message because you are subscribed to the Google <br></div><div style="font-family:Arial;">>> Groups "Homotopy Type Theory" group.<br></div><div style="font-family:Arial;">>> To unsubscribe from this group and stop receiving emails from it, send <br></div><div style="font-family:Arial;">>> an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.<br></div><div style="font-family:Arial;">>> To view this discussion on the web visit <br></div><div style="font-family:Arial;">>> https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com <https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com?utm_medium=email&utm_source=footer>.<br></div><div style="font-family:Arial;">> <br></div><div style="font-family:Arial;">> -- <br></div><div style="font-family:Arial;">> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br></div><div style="font-family:Arial;">> To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com.<br></div><div style="font-family:Arial;">> To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/80a2be3b-afaa-4106-9c69-0df6567ec709%40www.fastmail.com.<br></div><div style="font-family:Arial;"><br></div><div style="font-family:Arial;"><br></div></blockquote></body></html> <p></p> -- <br /> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br /> To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br /> To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/afe67df2-7f4a-4e51-abc9-3f8e3a985623%40www.fastmail.com?utm_medium=email&utm_source=footer">https://groups.google.com/d/msgid/HomotopyTypeTheory/afe67df2-7f4a-4e51-abc9-3f8e3a985623%40www.fastmail.com</a>.<br /> ^ permalink raw reply [flat|nested] 13+ messages in thread

*Fwd: [HoTT] Re: A question about the problem with regularity in CCHM cubical type theory[not found] ` <CAGTS-a-SvWWF+br6sKxGj6ufVY=4m830FH9BDg06QJR1vbNFsw@mail.gmail.com>@ 2019-09-16 2:18 ` " Jasper Hugunin2019-09-16 16:18 ` [HoTT] " Licata, Dan 0 siblings, 1 reply; 13+ messages in thread From: Jasper Hugunin @ 2019-09-16 2:18 UTC (permalink / raw) To: HomotopyTypeTheory [-- Attachment #1: Type: text/plain, Size: 5022 bytes --] This doesn't seem right; as far as I can tell, composition for Glue types in CCHM preserves regularity and reduces to composition in A on phi. - Jasper Hugunin On Sun, Sep 15, 2019 at 3:28 AM Anders Mortberg <anders.mortberg@math.su.se> wrote: > Hi Jasper, > > Indeed, the problem is to construct an algorithm for comp (or even > coe/transp) for Glue that reduces to the one of A when phi is true > while still preserving regularity. It was pointed out independently by > Sattler and Orton around 2016 that one can factor out this step in our > algorithm in a separate lemma that is now called "alignment". This is > Thm 6.13 in Orton-Pitts and discussed in a paragraph in the end of > section 2.11 of ABCFHL. Unless I'm misremembering this is exactly > where regularity for comp for Glue types break down. In this step we > do an additional comp/hcomp that inserts an additional forall i. phi > face making the comp/coe irregular. > > One could imagine there being a way to modify the algorithm to avoid > this, maybe by inlining the alignment step... But despite considerable > efforts no one has been able to figure this out and I think Swan's > recent paper (https://arxiv.org/abs/1808.00920v3) shows that this is > not even possible! > > Another approach would be to have weak Glue types that don't strictly > reduce to A when phi is true, but this causes problems for the > composition in the universe and would be weird for cubical type > theory... > > In light of Swan's negative results I think we need a completely new > approach if we ever hope to solve this problem. Luckily for you Andrew > Swan is starting as a postdoc over in Baker Hall in October, so he can > explain his counterexamples to you in person. > > Best, > Anders > > On Sun, Sep 15, 2019 at 7:57 AM Jasper Hugunin > <jasperh@cs.washington.edu> wrote: > > > > Offline, Carlo Angiuli showed me that the difficulty was in part 1, > because of a subtlety I had been forgetting. > > > > Since types are *Kan* cubical sets, we need that the Kan operations > agree as well as the sets. > > So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, > compGlue) = (A, compA), and getting that the Kan operations to agree was/is > difficult. > > (Now that I know what the answer is, it is clear that this was already > explained in the initial discussion.) > > > > Humbly, > > - Jasper Hugunin > > > > On Fri, Sep 13, 2019 at 2:10 AM Jasper Hugunin < > jasperh@cs.washington.edu> wrote: > >> > >> Hello all, > >> > >> I've been trying to understand better why composition for the universe > does not satisfy regularity. > >> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> > equiv^i E ] A, I would expect regularity to follow from two parts: > >> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of > regularity condition for the Glue type constructor itself) > >> 2. That equiv^i (refl A) reduces to equivRefl A > >> I'm curious as to which (or both) of these parts was the issue, or if > regularity for the universe was supposed to follow from a different > argument. > >> > >> Context: > >> I've been studying and using CCHM cubical type theory recently, and > often finding myself wishing that J computed strictly. > >> If I understand correctly, early implementations of ctt did have strict > J for Path types, and this was justified by a "regularity" condition on the > composition operation, but as discussed in this thread on the HoTT mailing > list, the definition of composition for the universe was found to not > satisfy regularity. > >> I don't remember seeing the regularity condition defined anywhere, but > my understanding is that it requires that composition in a degenerate line > of types, with the system of constraints giving the sides of the box also > degenerate in that direction, reduces to just the bottom of the box. This > seems to be closed under the usual type formers, plus Glue, but not the > universe with computation defined as in the CCHM paper (for trivial reasons > and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> > equiv^i refl ] A not reducing to anything). > >> > >> Best regards, > >> - Jasper Hugunin > > > > -- > > You received this message because you are subscribed to the Google > Groups "Homotopy Type Theory" group. > > To unsubscribe from this group and stop receiving emails from it, send > an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com > . > -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com. [-- Attachment #2: Type: text/html, Size: 6564 bytes --] <div dir="ltr"><div class="gmail_quote"><div dir="ltr"><div dir="ltr">This doesn't seem right; as far as I can tell, composition for Glue types in CCHM preserves regularity and reduces to composition in A on phi.<div><br></div><div>- Jasper Hugunin</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Sep 15, 2019 at 3:28 AM Anders Mortberg <<a href="mailto:anders.mortberg@math.su.se" target="_blank">anders.mortberg@math.su.se</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi Jasper,<br> <br> Indeed, the problem is to construct an algorithm for comp (or even<br> coe/transp) for Glue that reduces to the one of A when phi is true<br> while still preserving regularity. It was pointed out independently by<br> Sattler and Orton around 2016 that one can factor out this step in our<br> algorithm in a separate lemma that is now called "alignment". This is<br> Thm 6.13 in Orton-Pitts and discussed in a paragraph in the end of<br> section 2.11 of ABCFHL. Unless I'm misremembering this is exactly<br> where regularity for comp for Glue types break down. In this step we<br> do an additional comp/hcomp that inserts an additional forall i. phi<br> face making the comp/coe irregular.<br> <br> One could imagine there being a way to modify the algorithm to avoid<br> this, maybe by inlining the alignment step... But despite considerable<br> efforts no one has been able to figure this out and I think Swan's<br> recent paper (<a href="https://arxiv.org/abs/1808.00920v3" rel="noreferrer" target="_blank">https://arxiv.org/abs/1808.00920v3</a>) shows that this is<br> not even possible!<br> <br> Another approach would be to have weak Glue types that don't strictly<br> reduce to A when phi is true, but this causes problems for the<br> composition in the universe and would be weird for cubical type<br> theory...<br> <br> In light of Swan's negative results I think we need a completely new<br> approach if we ever hope to solve this problem. Luckily for you Andrew<br> Swan is starting as a postdoc over in Baker Hall in October, so he can<br> explain his counterexamples to you in person.<br> <br> Best,<br> Anders<br> <br> On Sun, Sep 15, 2019 at 7:57 AM Jasper Hugunin<br> <<a href="mailto:jasperh@cs.washington.edu" target="_blank">jasperh@cs.washington.edu</a>> wrote:<br> ><br> > Offline, Carlo Angiuli showed me that the difficulty was in part 1, because of a subtlety I had been forgetting.<br> ><br> > Since types are *Kan* cubical sets, we need that the Kan operations agree as well as the sets.<br> > So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, compGlue) = (A, compA), and getting that the Kan operations to agree was/is difficult.<br> > (Now that I know what the answer is, it is clear that this was already explained in the initial discussion.)<br> ><br> > Humbly,<br> > - Jasper Hugunin<br> ><br> > On Fri, Sep 13, 2019 at 2:10 AM Jasper Hugunin <<a href="mailto:jasperh@cs.washington.edu" target="_blank">jasperh@cs.washington.edu</a>> wrote:<br> >><br> >> Hello all,<br> >><br> >> I've been trying to understand better why composition for the universe does not satisfy regularity.<br> >> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts:<br> >> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself)<br> >> 2. That equiv^i (refl A) reduces to equivRefl A<br> >> I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument.<br> >><br> >> Context:<br> >> I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly.<br> >> If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in this thread on the HoTT mailing list, the definition of composition for the universe was found to not satisfy regularity.<br> >> I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in the CCHM paper (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything).<br> >><br> >> Best regards,<br> >> - Jasper Hugunin<br> ><br> > --<br> > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br> > To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory%2Bunsubscribe@googlegroups.com" target="_blank">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br> > To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com" rel="noreferrer" target="_blank">https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com</a>.<br> </blockquote></div></div> </div></div> <p></p> -- <br /> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br /> To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br /> To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com?utm_medium=email&utm_source=footer">https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com</a>.<br /> ^ permalink raw reply [flat|nested] 13+ messages in thread

*Re: [HoTT] A question about the problem with regularity in CCHM cubical type theory2019-09-16 2:18 ` Fwd: " Jasper Hugunin@ 2019-09-16 16:18 ` " Licata, Dan2019-09-16 17:09 ` Jasper Hugunin 0 siblings, 1 reply; 13+ messages in thread From: Licata, Dan @ 2019-09-16 16:18 UTC (permalink / raw) To: Jasper Hugunin;+Cc:HomotopyTypeTheory Hi Jasper, It would help me follow the discussion if you could say a little more about (a) which version of composition for Glue exactly you mean (because there is at least the one in the CCHM paper and the “aligned” one from Orton-Pitts, which are intensionally different, as well as other possible variations), and (b) include some of your reasoning for why you think things are regular, to make it easier for me and others to reconstruct. My current understanding is that - For CCHM proper https://arxiv.org/pdf/1611.02108.pdf the potential issue is with the ‘pres’ path omega, which via the equiv operation ends up in alpha, so the system in a1 may not be degenerate even if the input is. Do you think this does work out to be degenerate? - For the current version of ABCFHL https://github.com/dlicata335/cart-cube/blob/master/cart-cube.pdf which uses aligning “all the way at the outside”, an issue is with the adjust_com operation on page 20, which is later used for aligning (in that case beta is (forall i phi)). The potential issue is that adjust_com uses a *filler*, not just a composition from 0 to 1, so even if t doesn’t depend on z, the filling does, and the outer com won’t cancel. In CCHM, filling is defined using connections, so it’s a little different, but I think there still has to be a dependence on z for it to even type check — it should come up because of the connection term that is substituted into the type of the composition problem. So I’d guess there is still a problem in the aligned algorithm for CCHM. However, it would be great if this is wrong and something does work! -Dan > On Sep 15, 2019, at 10:18 PM, Jasper Hugunin <jasperh@cs.washington.edu> wrote: > > This doesn't seem right; as far as I can tell, composition for Glue types in CCHM preserves regularity and reduces to composition in A on phi. > > - Jasper Hugunin > > On Sun, Sep 15, 2019 at 3:28 AM Anders Mortberg <anders.mortberg@math.su.se> wrote: > Hi Jasper, > > Indeed, the problem is to construct an algorithm for comp (or even > coe/transp) for Glue that reduces to the one of A when phi is true > while still preserving regularity. It was pointed out independently by > Sattler and Orton around 2016 that one can factor out this step in our > algorithm in a separate lemma that is now called "alignment". This is > Thm 6.13 in Orton-Pitts and discussed in a paragraph in the end of > section 2.11 of ABCFHL. Unless I'm misremembering this is exactly > where regularity for comp for Glue types break down. In this step we > do an additional comp/hcomp that inserts an additional forall i. phi > face making the comp/coe irregular. > > One could imagine there being a way to modify the algorithm to avoid > this, maybe by inlining the alignment step... But despite considerable > efforts no one has been able to figure this out and I think Swan's > recent paper (https://arxiv.org/abs/1808.00920v3) shows that this is > not even possible! > > Another approach would be to have weak Glue types that don't strictly > reduce to A when phi is true, but this causes problems for the > composition in the universe and would be weird for cubical type > theory... > > In light of Swan's negative results I think we need a completely new > approach if we ever hope to solve this problem. Luckily for you Andrew > Swan is starting as a postdoc over in Baker Hall in October, so he can > explain his counterexamples to you in person. > > Best, > Anders > > On Sun, Sep 15, 2019 at 7:57 AM Jasper Hugunin > <jasperh@cs.washington.edu> wrote: > > > > Offline, Carlo Angiuli showed me that the difficulty was in part 1, because of a subtlety I had been forgetting. > > > > Since types are *Kan* cubical sets, we need that the Kan operations agree as well as the sets. > > So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, compGlue) = (A, compA), and getting that the Kan operations to agree was/is difficult. > > (Now that I know what the answer is, it is clear that this was already explained in the initial discussion.) > > > > Humbly, > > - Jasper Hugunin > > > > On Fri, Sep 13, 2019 at 2:10 AM Jasper Hugunin <jasperh@cs.washington.edu> wrote: > >> > >> Hello all, > >> > >> I've been trying to understand better why composition for the universe does not satisfy regularity. > >> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts: > >> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself) > >> 2. That equiv^i (refl A) reduces to equivRefl A > >> I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument. > >> > >> Context: > >> I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly. > >> If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in this thread on the HoTT mailing list, the definition of composition for the universe was found to not satisfy regularity. > >> I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in the CCHM paper (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything). > >> > >> Best regards, > >> - Jasper Hugunin > > > > -- > > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. > > To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com. > > -- > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. > To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com. -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/10B7D7E9-3155-4FA0-90E0-BB6BE2C37B1B%40wesleyan.edu. ^ permalink raw reply [flat|nested] 13+ messages in thread

*Re: [HoTT] A question about the problem with regularity in CCHM cubical type theory2019-09-16 16:18 ` [HoTT] " Licata, Dan@ 2019-09-16 17:09 ` Jasper Hugunin2019-09-16 19:01 ` Licata, Dan 0 siblings, 1 reply; 13+ messages in thread From: Jasper Hugunin @ 2019-09-16 17:09 UTC (permalink / raw) To: Licata, Dan;+Cc:HomotopyTypeTheory [-- Attachment #1: Type: text/plain, Size: 10342 bytes --] Hi Dan, Of course. I'm thinking primarily of composition for Glue given in the CCHM paper you linked, reproduced below. As you know, the single potential issue is that we need pres of a degenerate filling problem and function to be reflexivity. I claim that this holds by regularity of composition in T and A, partly as a consequence of the fact that regularity of composition implies regularity of filling (that fill of a degenerate system is refl), which certainly holds for fill defined by connections (and I believe also holds for fill as defined in ABCFHL). (a) Given i |- B = Glue [ phi |-> (T, f) ] A, with psi, i |- b : B and b0 : B(i0)[ psi |-> b(i0) ], we want to compute b1 = comp^i B [ psi |-> b ] b0 : B(i1)[ psi |-> b(i1) ]. We set a := unglue b and a0 := unglue b0. Set delta := forall i. phi. Then we take: a1' := comp^i A [ psi |-> a ] a0 delta |- t1' := comp^i T [ psi |-> b ] b0 delta |- omega := pres^i f [ psi |-> b ] b0 phi(i1) |- (t, alpha) := equiv f(i1) [ delta |-> (t1', omega), psi |-> (b(i1), refl a1') ] a1' a1 := hcomp^j A(i1) [ phi(i1) |-> alpha j, psi |-> a(i1) ] a1' (note that in the regular setting the psi face is redundant) b1 := glue [ phi(i1) |-> t1 ] a1 With given i |- f : T -> A, with psi, i |- b : T and b0 : T(i0)[ psi |-> b(i0) ], we define pres^i f [ psi |-> b ] b0 = <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> b ] b0) ] (f(i0) b0). (b) Now consider the regular case, where phi, T, f, and A are independent of i. We want that b1 = b0. We have that a is independent of i, and delta = phi. First consider delta (= phi) |- pres^i f [ psi |-> b ] b0. (This is the explanation of your first dash) Note that if comp^i A is regular, then fill^i A [ psi |-> b ] b0 = b This is <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> t ] t0) ] (f t0) = <j> comp^i A [ psi |-> f b, j = 1 |-> f t0 ] (f t0) = <j> f t0. Thus pres of a degenerate filling problem and function is reflexivity. Going back to composition of Glue, a1' = a0 phi |- t1' = b0 phi |- omega = refl (f b0) phi |- (t1, alpha) = (t1', omega) (since delta = phi, so we end up in the delta face of equiv) a1 = a1' (the only dependence on j is via (alpha j), but alpha = omega = refl, so this filling problem is degenerate) b1 = glue [ phi |-> t1 ] a1 = glue [ phi |-> b0 ] a0 = glue [ phi |-> b0 ] (unglue b0) = b0 (by eta, see Figure 4 in CCHM) Thus this algorithm for composition of Glue is regular. Other algorithms, such as the one in ABCFHL, may not be, but I am prone to believe that there exist regular algorithms in other settings including Orton-Pitts and Cartesian cubes. Best regards, - Jasper Hugunin On Mon, Sep 16, 2019 at 12:18 PM Licata, Dan <dlicata@wesleyan.edu> wrote: > Hi Jasper, > > It would help me follow the discussion if you could say a little more > about (a) which version of composition for Glue exactly you mean (because > there is at least the one in the CCHM paper and the “aligned” one from > Orton-Pitts, which are intensionally different, as well as other possible > variations), and (b) include some of your reasoning for why you think > things are regular, to make it easier for me and others to reconstruct. > > My current understanding is that > > - For CCHM proper https://arxiv.org/pdf/1611.02108.pdf the potential > issue is with the ‘pres’ path omega, which via the equiv operation ends up > in alpha, so the system in a1 may not be degenerate even if the input is. > Do you think this does work out to be degenerate? > > - For the current version of ABCFHL > https://github.com/dlicata335/cart-cube/blob/master/cart-cube.pdf which > uses aligning “all the way at the outside”, an issue is with the adjust_com > operation on page 20, which is later used for aligning (in that case beta > is (forall i phi)). The potential issue is that adjust_com uses a > *filler*, not just a composition from 0 to 1, so even if t doesn’t depend > on z, the filling does, and the outer com won’t cancel. In CCHM, filling > is defined using connections, so it’s a little different, but I think there > still has to be a dependence on z for it to even type check — it should > come up because of the connection term that is substituted into the type of > the composition problem. So I’d guess there is still a problem in the > aligned algorithm for CCHM. > > However, it would be great if this is wrong and something does work! > > -Dan > > > On Sep 15, 2019, at 10:18 PM, Jasper Hugunin <jasperh@cs.washington.edu> > wrote: > > > > This doesn't seem right; as far as I can tell, composition for Glue > types in CCHM preserves regularity and reduces to composition in A on phi. > > > > - Jasper Hugunin > > > > On Sun, Sep 15, 2019 at 3:28 AM Anders Mortberg < > anders.mortberg@math.su.se> wrote: > > Hi Jasper, > > > > Indeed, the problem is to construct an algorithm for comp (or even > > coe/transp) for Glue that reduces to the one of A when phi is true > > while still preserving regularity. It was pointed out independently by > > Sattler and Orton around 2016 that one can factor out this step in our > > algorithm in a separate lemma that is now called "alignment". This is > > Thm 6.13 in Orton-Pitts and discussed in a paragraph in the end of > > section 2.11 of ABCFHL. Unless I'm misremembering this is exactly > > where regularity for comp for Glue types break down. In this step we > > do an additional comp/hcomp that inserts an additional forall i. phi > > face making the comp/coe irregular. > > > > One could imagine there being a way to modify the algorithm to avoid > > this, maybe by inlining the alignment step... But despite considerable > > efforts no one has been able to figure this out and I think Swan's > > recent paper (https://arxiv.org/abs/1808.00920v3) shows that this is > > not even possible! > > > > Another approach would be to have weak Glue types that don't strictly > > reduce to A when phi is true, but this causes problems for the > > composition in the universe and would be weird for cubical type > > theory... > > > > In light of Swan's negative results I think we need a completely new > > approach if we ever hope to solve this problem. Luckily for you Andrew > > Swan is starting as a postdoc over in Baker Hall in October, so he can > > explain his counterexamples to you in person. > > > > Best, > > Anders > > > > On Sun, Sep 15, 2019 at 7:57 AM Jasper Hugunin > > <jasperh@cs.washington.edu> wrote: > > > > > > Offline, Carlo Angiuli showed me that the difficulty was in part 1, > because of a subtlety I had been forgetting. > > > > > > Since types are *Kan* cubical sets, we need that the Kan operations > agree as well as the sets. > > > So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, > compGlue) = (A, compA), and getting that the Kan operations to agree was/is > difficult. > > > (Now that I know what the answer is, it is clear that this was already > explained in the initial discussion.) > > > > > > Humbly, > > > - Jasper Hugunin > > > > > > On Fri, Sep 13, 2019 at 2:10 AM Jasper Hugunin < > jasperh@cs.washington.edu> wrote: > > >> > > >> Hello all, > > >> > > >> I've been trying to understand better why composition for the > universe does not satisfy regularity. > > >> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> > equiv^i E ] A, I would expect regularity to follow from two parts: > > >> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of > regularity condition for the Glue type constructor itself) > > >> 2. That equiv^i (refl A) reduces to equivRefl A > > >> I'm curious as to which (or both) of these parts was the issue, or if > regularity for the universe was supposed to follow from a different > argument. > > >> > > >> Context: > > >> I've been studying and using CCHM cubical type theory recently, and > often finding myself wishing that J computed strictly. > > >> If I understand correctly, early implementations of ctt did have > strict J for Path types, and this was justified by a "regularity" condition > on the composition operation, but as discussed in this thread on the HoTT > mailing list, the definition of composition for the universe was found to > not satisfy regularity. > > >> I don't remember seeing the regularity condition defined anywhere, > but my understanding is that it requires that composition in a degenerate > line of types, with the system of constraints giving the sides of the box > also degenerate in that direction, reduces to just the bottom of the box. > This seems to be closed under the usual type formers, plus Glue, but not > the universe with computation defined as in the CCHM paper (for trivial > reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi > |-> equiv^i refl ] A not reducing to anything). > > >> > > >> Best regards, > > >> - Jasper Hugunin > > > > > > -- > > > You received this message because you are subscribed to the Google > Groups "Homotopy Type Theory" group. > > > To unsubscribe from this group and stop receiving emails from it, send > an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > > > To view this discussion on the web visit > https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com > . > > > > -- > > You received this message because you are subscribed to the Google > Groups "Homotopy Type Theory" group. > > To unsubscribe from this group and stop receiving emails from it, send > an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com > . > > -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a_qUJdhOcQUznrY3JetHjQpCasCYHb1PR2hBPL0%2BMj1xg%40mail.gmail.com. [-- Attachment #2: Type: text/html, Size: 13041 bytes --] <div dir="ltr">Hi Dan,<div><br></div><div>Of course. I'm thinking primarily of composition for Glue given in the CCHM paper you linked, reproduced below.</div><div>As you know, the single potential issue is that we need pres of a degenerate filling problem and function to be reflexivity. I claim that this holds by regularity of composition in T and A, partly as a consequence of the fact that regularity of composition implies regularity of filling (that fill of a degenerate system is refl), which certainly holds for fill defined by connections (and I believe also holds for fill as defined in ABCFHL).</div><div><br></div><div>(a)</div><div>Given i |- B = Glue [ phi |-> (T, f) ] A, with psi, i |- b : B and b0 : B(i0)[ psi |-> b(i0) ], we want to compute b1 = comp^i B [ psi |-> b ] b0 : B(i1)[ psi |-> b(i1) ].</div><div>We set a := unglue b and a0 := unglue b0.</div><div>Set delta := forall i. phi.</div><div>Then we take:</div><div>a1' := comp^i A [ psi |-> a ] a0</div><div>delta |- t1' := comp^i T [ psi |-> b ] b0</div><div>delta |- omega := pres^i f [ psi |-> b ] b0</div><div>phi(i1) |- (t, alpha) := equiv f(i1) [ delta |-> (t1', omega), psi |-> (b(i1), refl a1') ] a1'</div><div>a1 := hcomp^j A(i1) [ phi(i1) |-> alpha j, psi |-> a(i1) ] a1' (note that in the regular setting the psi face is redundant)</div><div>b1 := glue [ phi(i1) |-> t1 ] a1</div><div><br></div><div>With given i |- f : T -> A, with psi, i |- b : T and b0 : T(i0)[ psi |-> b(i0) ], we define</div><div>pres^i f [ psi |-> b ] b0 = <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> b ] b0) ] (f(i0) b0).</div><div><br></div><div>(b)</div><div>Now consider the regular case, where phi, T, f, and A are independent of i. We want that b1 = b0.</div><div>We have that a is independent of i, and delta = phi.</div><div><br></div><div>First consider delta (= phi) |- pres^i f [ psi |-> b ] b0. (This is the explanation of your first dash)</div><div>Note that if comp^i A is regular, then fill^i A [ psi |-> b ] b0 = b</div><div>This is <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> t ] t0) ] (f t0) = <j> comp^i A [ psi |-> f b, j = 1 |-> f t0 ] (f t0) = <j> f t0.</div><div>Thus pres of a degenerate filling problem and function is reflexivity.</div><div><br></div><div>Going back to composition of Glue,</div><div>a1' = a0<br></div><div>phi |- t1' = b0</div><div>phi |- omega = refl (f b0)</div><div>phi |- (t1, alpha) = (t1', omega) (since delta = phi, so we end up in the delta face of equiv)</div><div>a1 = a1' (the only dependence on j is via (alpha j), but alpha = omega = refl, so this filling problem is degenerate)</div><div>b1 = glue [ phi |-> t1 ] a1 = glue [ phi |-> b0 ] a0 = glue [ phi |-> b0 ] (unglue b0) = b0 (by eta, see Figure 4 in CCHM)</div><div><br></div><div>Thus this algorithm for composition of Glue is regular.</div><div>Other algorithms, such as the one in ABCFHL, may not be, but I am prone to believe that there exist regular algorithms in other settings including Orton-Pitts and Cartesian cubes.</div><div><br></div><div>Best regards,</div><div>- Jasper Hugunin</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Sep 16, 2019 at 12:18 PM Licata, Dan <<a href="mailto:dlicata@wesleyan.edu">dlicata@wesleyan.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi Jasper,<br> <br> It would help me follow the discussion if you could say a little more about (a) which version of composition for Glue exactly you mean (because there is at least the one in the CCHM paper and the “aligned” one from Orton-Pitts, which are intensionally different, as well as other possible variations), and (b) include some of your reasoning for why you think things are regular, to make it easier for me and others to reconstruct. <br> <br> My current understanding is that<br> <br> - For CCHM proper <a href="https://arxiv.org/pdf/1611.02108.pdf" rel="noreferrer" target="_blank">https://arxiv.org/pdf/1611.02108.pdf</a> the potential issue is with the ‘pres’ path omega, which via the equiv operation ends up in alpha, so the system in a1 may not be degenerate even if the input is. Do you think this does work out to be degenerate? <br> <br> - For the current version of ABCFHL <a href="https://github.com/dlicata335/cart-cube/blob/master/cart-cube.pdf" rel="noreferrer" target="_blank">https://github.com/dlicata335/cart-cube/blob/master/cart-cube.pdf</a> which uses aligning “all the way at the outside”, an issue is with the adjust_com operation on page 20, which is later used for aligning (in that case beta is (forall i phi)). The potential issue is that adjust_com uses a *filler*, not just a composition from 0 to 1, so even if t doesn’t depend on z, the filling does, and the outer com won’t cancel. In CCHM, filling is defined using connections, so it’s a little different, but I think there still has to be a dependence on z for it to even type check — it should come up because of the connection term that is substituted into the type of the composition problem. So I’d guess there is still a problem in the aligned algorithm for CCHM. <br> <br> However, it would be great if this is wrong and something does work! <br> <br> -Dan<br> <br> > On Sep 15, 2019, at 10:18 PM, Jasper Hugunin <<a href="mailto:jasperh@cs.washington.edu" target="_blank">jasperh@cs.washington.edu</a>> wrote:<br> > <br> > This doesn't seem right; as far as I can tell, composition for Glue types in CCHM preserves regularity and reduces to composition in A on phi.<br> > <br> > - Jasper Hugunin<br> > <br> > On Sun, Sep 15, 2019 at 3:28 AM Anders Mortberg <<a href="mailto:anders.mortberg@math.su.se" target="_blank">anders.mortberg@math.su.se</a>> wrote:<br> > Hi Jasper,<br> > <br> > Indeed, the problem is to construct an algorithm for comp (or even<br> > coe/transp) for Glue that reduces to the one of A when phi is true<br> > while still preserving regularity. It was pointed out independently by<br> > Sattler and Orton around 2016 that one can factor out this step in our<br> > algorithm in a separate lemma that is now called "alignment". This is<br> > Thm 6.13 in Orton-Pitts and discussed in a paragraph in the end of<br> > section 2.11 of ABCFHL. Unless I'm misremembering this is exactly<br> > where regularity for comp for Glue types break down. In this step we<br> > do an additional comp/hcomp that inserts an additional forall i. phi<br> > face making the comp/coe irregular.<br> > <br> > One could imagine there being a way to modify the algorithm to avoid<br> > this, maybe by inlining the alignment step... But despite considerable<br> > efforts no one has been able to figure this out and I think Swan's<br> > recent paper (<a href="https://arxiv.org/abs/1808.00920v3" rel="noreferrer" target="_blank">https://arxiv.org/abs/1808.00920v3</a>) shows that this is<br> > not even possible!<br> > <br> > Another approach would be to have weak Glue types that don't strictly<br> > reduce to A when phi is true, but this causes problems for the<br> > composition in the universe and would be weird for cubical type<br> > theory...<br> > <br> > In light of Swan's negative results I think we need a completely new<br> > approach if we ever hope to solve this problem. Luckily for you Andrew<br> > Swan is starting as a postdoc over in Baker Hall in October, so he can<br> > explain his counterexamples to you in person.<br> > <br> > Best,<br> > Anders<br> > <br> > On Sun, Sep 15, 2019 at 7:57 AM Jasper Hugunin<br> > <<a href="mailto:jasperh@cs.washington.edu" target="_blank">jasperh@cs.washington.edu</a>> wrote:<br> > ><br> > > Offline, Carlo Angiuli showed me that the difficulty was in part 1, because of a subtlety I had been forgetting.<br> > ><br> > > Since types are *Kan* cubical sets, we need that the Kan operations agree as well as the sets.<br> > > So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, compGlue) = (A, compA), and getting that the Kan operations to agree was/is difficult.<br> > > (Now that I know what the answer is, it is clear that this was already explained in the initial discussion.)<br> > ><br> > > Humbly,<br> > > - Jasper Hugunin<br> > ><br> > > On Fri, Sep 13, 2019 at 2:10 AM Jasper Hugunin <<a href="mailto:jasperh@cs.washington.edu" target="_blank">jasperh@cs.washington.edu</a>> wrote:<br> > >><br> > >> Hello all,<br> > >><br> > >> I've been trying to understand better why composition for the universe does not satisfy regularity.<br> > >> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts:<br> > >> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself)<br> > >> 2. That equiv^i (refl A) reduces to equivRefl A<br> > >> I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument.<br> > >><br> > >> Context:<br> > >> I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly.<br> > >> If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in this thread on the HoTT mailing list, the definition of composition for the universe was found to not satisfy regularity.<br> > >> I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in the CCHM paper (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything).<br> > >><br> > >> Best regards,<br> > >> - Jasper Hugunin<br> > ><br> > > --<br> > > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br> > > To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory%2Bunsubscribe@googlegroups.com" target="_blank">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br> > > To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com" rel="noreferrer" target="_blank">https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com</a>.<br> > <br> > -- <br> > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br> > To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory%2Bunsubscribe@googlegroups.com" target="_blank">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br> > To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com" rel="noreferrer" target="_blank">https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com</a>.<br> <br> </blockquote></div> <p></p> -- <br /> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br /> To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br /> To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a_qUJdhOcQUznrY3JetHjQpCasCYHb1PR2hBPL0%2BMj1xg%40mail.gmail.com?utm_medium=email&utm_source=footer">https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a_qUJdhOcQUznrY3JetHjQpCasCYHb1PR2hBPL0%2BMj1xg%40mail.gmail.com</a>.<br /> ^ permalink raw reply [flat|nested] 13+ messages in thread

*Re: [HoTT] A question about the problem with regularity in CCHM cubical type theory2019-09-16 17:09 ` Jasper Hugunin@ 2019-09-16 19:01 ` Licata, Dan2019-09-16 20:17 ` Jasper Hugunin 0 siblings, 1 reply; 13+ messages in thread From: Licata, Dan @ 2019-09-16 19:01 UTC (permalink / raw) To: Jasper Hugunin;+Cc:HomotopyTypeTheory [-- Attachment #1: Type: text/plain, Size: 11166 bytes --] Wow! I read that pretty closely and couldn’t find a problem. That is surprising to me. Will look more later. What I was saying about fill for the aligning algorithm is also wrong — I wasn’t thinking that the type of the filling was also degenerate, but of course it is here. So that might work too. However, even if there can be a universe of regular types that is closed under glue types, there’s still a problem with using those glue types to show that that universe is itself regularly fibrant, I think? If you define comp U [phi -> i.T] B to be Glue [phi -> T(1),...] B then no matter how nice the equivalence is (eg the identity) when i doesn’t occur in T, the type will not equal B — that would be an extra equation about the Glue type constructor itself. Does that seem right? -Dan On Sep 16, 2019, at 1:09 PM, Jasper Hugunin <jasperh@cs.washington.edu<mailto:jasperh@cs.washington.edu>> wrote: Hi Dan, Of course. I'm thinking primarily of composition for Glue given in the CCHM paper you linked, reproduced below. As you know, the single potential issue is that we need pres of a degenerate filling problem and function to be reflexivity. I claim that this holds by regularity of composition in T and A, partly as a consequence of the fact that regularity of composition implies regularity of filling (that fill of a degenerate system is refl), which certainly holds for fill defined by connections (and I believe also holds for fill as defined in ABCFHL). (a) Given i |- B = Glue [ phi |-> (T, f) ] A, with psi, i |- b : B and b0 : B(i0)[ psi |-> b(i0) ], we want to compute b1 = comp^i B [ psi |-> b ] b0 : B(i1)[ psi |-> b(i1) ]. We set a := unglue b and a0 := unglue b0. Set delta := forall i. phi. Then we take: a1' := comp^i A [ psi |-> a ] a0 delta |- t1' := comp^i T [ psi |-> b ] b0 delta |- omega := pres^i f [ psi |-> b ] b0 phi(i1) |- (t, alpha) := equiv f(i1) [ delta |-> (t1', omega), psi |-> (b(i1), refl a1') ] a1' a1 := hcomp^j A(i1) [ phi(i1) |-> alpha j, psi |-> a(i1) ] a1' (note that in the regular setting the psi face is redundant) b1 := glue [ phi(i1) |-> t1 ] a1 With given i |- f : T -> A, with psi, i |- b : T and b0 : T(i0)[ psi |-> b(i0) ], we define pres^i f [ psi |-> b ] b0 = <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> b ] b0) ] (f(i0) b0). (b) Now consider the regular case, where phi, T, f, and A are independent of i. We want that b1 = b0. We have that a is independent of i, and delta = phi. First consider delta (= phi) |- pres^i f [ psi |-> b ] b0. (This is the explanation of your first dash) Note that if comp^i A is regular, then fill^i A [ psi |-> b ] b0 = b This is <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> t ] t0) ] (f t0) = <j> comp^i A [ psi |-> f b, j = 1 |-> f t0 ] (f t0) = <j> f t0. Thus pres of a degenerate filling problem and function is reflexivity. Going back to composition of Glue, a1' = a0 phi |- t1' = b0 phi |- omega = refl (f b0) phi |- (t1, alpha) = (t1', omega) (since delta = phi, so we end up in the delta face of equiv) a1 = a1' (the only dependence on j is via (alpha j), but alpha = omega = refl, so this filling problem is degenerate) b1 = glue [ phi |-> t1 ] a1 = glue [ phi |-> b0 ] a0 = glue [ phi |-> b0 ] (unglue b0) = b0 (by eta, see Figure 4 in CCHM) Thus this algorithm for composition of Glue is regular. Other algorithms, such as the one in ABCFHL, may not be, but I am prone to believe that there exist regular algorithms in other settings including Orton-Pitts and Cartesian cubes. Best regards, - Jasper Hugunin On Mon, Sep 16, 2019 at 12:18 PM Licata, Dan <dlicata@wesleyan.edu<mailto:dlicata@wesleyan.edu>> wrote: Hi Jasper, It would help me follow the discussion if you could say a little more about (a) which version of composition for Glue exactly you mean (because there is at least the one in the CCHM paper and the “aligned” one from Orton-Pitts, which are intensionally different, as well as other possible variations), and (b) include some of your reasoning for why you think things are regular, to make it easier for me and others to reconstruct. My current understanding is that - For CCHM proper https://arxiv.org/pdf/1611.02108.pdf the potential issue is with the ‘pres’ path omega, which via the equiv operation ends up in alpha, so the system in a1 may not be degenerate even if the input is. Do you think this does work out to be degenerate? - For the current version of ABCFHL https://github.com/dlicata335/cart-cube/blob/master/cart-cube.pdf which uses aligning “all the way at the outside”, an issue is with the adjust_com operation on page 20, which is later used for aligning (in that case beta is (forall i phi)). The potential issue is that adjust_com uses a *filler*, not just a composition from 0 to 1, so even if t doesn’t depend on z, the filling does, and the outer com won’t cancel. In CCHM, filling is defined using connections, so it’s a little different, but I think there still has to be a dependence on z for it to even type check — it should come up because of the connection term that is substituted into the type of the composition problem. So I’d guess there is still a problem in the aligned algorithm for CCHM. However, it would be great if this is wrong and something does work! -Dan > On Sep 15, 2019, at 10:18 PM, Jasper Hugunin <jasperh@cs.washington.edu<mailto:jasperh@cs.washington.edu>> wrote: > > This doesn't seem right; as far as I can tell, composition for Glue types in CCHM preserves regularity and reduces to composition in A on phi. > > - Jasper Hugunin > > On Sun, Sep 15, 2019 at 3:28 AM Anders Mortberg <anders.mortberg@math.su.se<mailto:anders.mortberg@math.su.se>> wrote: > Hi Jasper, > > Indeed, the problem is to construct an algorithm for comp (or even > coe/transp) for Glue that reduces to the one of A when phi is true > while still preserving regularity. It was pointed out independently by > Sattler and Orton around 2016 that one can factor out this step in our > algorithm in a separate lemma that is now called "alignment". This is > Thm 6.13 in Orton-Pitts and discussed in a paragraph in the end of > section 2.11 of ABCFHL. Unless I'm misremembering this is exactly > where regularity for comp for Glue types break down. In this step we > do an additional comp/hcomp that inserts an additional forall i. phi > face making the comp/coe irregular. > > One could imagine there being a way to modify the algorithm to avoid > this, maybe by inlining the alignment step... But despite considerable > efforts no one has been able to figure this out and I think Swan's > recent paper (https://arxiv.org/abs/1808.00920v3) shows that this is > not even possible! > > Another approach would be to have weak Glue types that don't strictly > reduce to A when phi is true, but this causes problems for the > composition in the universe and would be weird for cubical type > theory... > > In light of Swan's negative results I think we need a completely new > approach if we ever hope to solve this problem. Luckily for you Andrew > Swan is starting as a postdoc over in Baker Hall in October, so he can > explain his counterexamples to you in person. > > Best, > Anders > > On Sun, Sep 15, 2019 at 7:57 AM Jasper Hugunin > <jasperh@cs.washington.edu<mailto:jasperh@cs.washington.edu>> wrote: > > > > Offline, Carlo Angiuli showed me that the difficulty was in part 1, because of a subtlety I had been forgetting. > > > > Since types are *Kan* cubical sets, we need that the Kan operations agree as well as the sets. > > So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, compGlue) = (A, compA), and getting that the Kan operations to agree was/is difficult. > > (Now that I know what the answer is, it is clear that this was already explained in the initial discussion.) > > > > Humbly, > > - Jasper Hugunin > > > > On Fri, Sep 13, 2019 at 2:10 AM Jasper Hugunin <jasperh@cs.washington.edu<mailto:jasperh@cs.washington.edu>> wrote: > >> > >> Hello all, > >> > >> I've been trying to understand better why composition for the universe does not satisfy regularity. > >> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts: > >> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself) > >> 2. That equiv^i (refl A) reduces to equivRefl A > >> I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument. > >> > >> Context: > >> I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly. > >> If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in this thread on the HoTT mailing list, the definition of composition for the universe was found to not satisfy regularity. > >> I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in the CCHM paper (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything). > >> > >> Best regards, > >> - Jasper Hugunin > > > > -- > > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. > > To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com<mailto:HomotopyTypeTheory%2Bunsubscribe@googlegroups.com>. > > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com. > > -- > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. > To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com<mailto:HomotopyTypeTheory%2Bunsubscribe@googlegroups.com>. > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com. -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CB28E4E1-73EC-4405-A268-350D028A0C93%40wesleyan.edu. [-- Attachment #2: Type: text/html, Size: 14574 bytes --] <html> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> </head> <body dir="auto"> Wow! I read that pretty closely and couldn’t find a problem. That is surprising to me. Will look more later. <div><br> </div> <div>What I was saying about fill for the aligning algorithm is also wrong — I wasn’t thinking that the type of the filling was also degenerate, but of course it is here. So that might work too. </div> <div><br> </div> <div>However, even if there can be a universe of regular types that is closed under glue types, there’s still a problem with using those glue types to show that that universe is itself regularly fibrant, I think? If you define comp U [phi -> i.T] B to be Glue [phi -> T(1),...] B then no matter how nice the equivalence is (eg the identity) when i doesn’t occur in T, the type will not equal B — that would be an extra equation about the Glue type constructor itself. Does that seem right?</div> <div><br> </div> <div> <div id="AppleMailSignature" dir="ltr"> <div><span class="Apple-style-span" style="-webkit-tap-highlight-color: rgba(26, 26, 26, 0.294118);">-Dan</span></div> </div> <div dir="ltr"><br> On Sep 16, 2019, at 1:09 PM, Jasper Hugunin <<a href="mailto:jasperh@cs.washington.edu">jasperh@cs.washington.edu</a>> wrote:<br> <br> </div> <blockquote type="cite"> <div dir="ltr"> <div dir="ltr">Hi Dan, <div><br> </div> <div>Of course. I'm thinking primarily of composition for Glue given in the CCHM paper you linked, reproduced below.</div> <div>As you know, the single potential issue is that we need pres of a degenerate filling problem and function to be reflexivity. I claim that this holds by regularity of composition in T and A, partly as a consequence of the fact that regularity of composition implies regularity of filling (that fill of a degenerate system is refl), which certainly holds for fill defined by connections (and I believe also holds for fill as defined in ABCFHL).</div> <div><br> </div> <div>(a)</div> <div>Given i |- B = Glue [ phi |-> (T, f) ] A, with psi, i |- b : B and b0 : B(i0)[ psi |-> b(i0) ], we want to compute b1 = comp^i B [ psi |-> b ] b0 : B(i1)[ psi |-> b(i1) ].</div> <div>We set a := unglue b and a0 := unglue b0.</div> <div>Set delta := forall i. phi.</div> <div>Then we take:</div> <div>a1' := comp^i A [ psi |-> a ] a0</div> <div>delta |- t1' := comp^i T [ psi |-> b ] b0</div> <div>delta |- omega := pres^i f [ psi |-> b ] b0</div> <div>phi(i1) |- (t, alpha) := equiv f(i1) [ delta |-> (t1', omega), psi |-> (b(i1), refl a1') ] a1'</div> <div>a1 := hcomp^j A(i1) [ phi(i1) |-> alpha j, psi |-> a(i1) ] a1' (note that in the regular setting the psi face is redundant)</div> <div>b1 := glue [ phi(i1) |-> t1 ] a1</div> <div><br> </div> <div>With given i |- f : T -> A, with psi, i |- b : T and b0 : T(i0)[ psi |-> b(i0) ], we define</div> <div>pres^i f [ psi |-> b ] b0 = <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> b ] b0) ] (f(i0) b0).</div> <div><br> </div> <div>(b)</div> <div>Now consider the regular case, where phi, T, f, and A are independent of i. We want that b1 = b0.</div> <div>We have that a is independent of i, and delta = phi.</div> <div><br> </div> <div>First consider delta (= phi) |- pres^i f [ psi |-> b ] b0. (This is the explanation of your first dash)</div> <div>Note that if comp^i A is regular, then fill^i A [ psi |-> b ] b0 = b</div> <div>This is <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> t ] t0) ] (f t0) = <j> comp^i A [ psi |-> f b, j = 1 |-> f t0 ] (f t0) = <j> f t0.</div> <div>Thus pres of a degenerate filling problem and function is reflexivity.</div> <div><br> </div> <div>Going back to composition of Glue,</div> <div>a1' = a0<br> </div> <div>phi |- t1' = b0</div> <div>phi |- omega = refl (f b0)</div> <div>phi |- (t1, alpha) = (t1', omega) (since delta = phi, so we end up in the delta face of equiv)</div> <div>a1 = a1' (the only dependence on j is via (alpha j), but alpha = omega = refl, so this filling problem is degenerate)</div> <div>b1 = glue [ phi |-> t1 ] a1 = glue [ phi |-> b0 ] a0 = glue [ phi |-> b0 ] (unglue b0) = b0 (by eta, see Figure 4 in CCHM)</div> <div><br> </div> <div>Thus this algorithm for composition of Glue is regular.</div> <div>Other algorithms, such as the one in ABCFHL, may not be, but I am prone to believe that there exist regular algorithms in other settings including Orton-Pitts and Cartesian cubes.</div> <div><br> </div> <div>Best regards,</div> <div>- Jasper Hugunin</div> </div> <br> <div class="gmail_quote"> <div dir="ltr" class="gmail_attr">On Mon, Sep 16, 2019 at 12:18 PM Licata, Dan <<a href="mailto:dlicata@wesleyan.edu">dlicata@wesleyan.edu</a>> wrote:<br> </div> <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> Hi Jasper,<br> <br> It would help me follow the discussion if you could say a little more about (a) which version of composition for Glue exactly you mean (because there is at least the one in the CCHM paper and the “aligned” one from Orton-Pitts, which are intensionally different, as well as other possible variations), and (b) include some of your reasoning for why you think things are regular, to make it easier for me and others to reconstruct. <br> <br> My current understanding is that<br> <br> - For CCHM proper <a href="https://arxiv.org/pdf/1611.02108.pdf" rel="noreferrer" target="_blank"> https://arxiv.org/pdf/1611.02108.pdf</a> the potential issue is with the ‘pres’ path omega, which via the equiv operation ends up in alpha, so the system in a1 may not be degenerate even if the input is. Do you think this does work out to be degenerate? <br> <br> - For the current version of ABCFHL <a href="https://github.com/dlicata335/cart-cube/blob/master/cart-cube.pdf" rel="noreferrer" target="_blank"> https://github.com/dlicata335/cart-cube/blob/master/cart-cube.pdf</a> which uses aligning “all the way at the outside”, an issue is with the adjust_com operation on page 20, which is later used for aligning (in that case beta is (forall i phi)). The potential issue is that adjust_com uses a *filler*, not just a composition from 0 to 1, so even if t doesn’t depend on z, the filling does, and the outer com won’t cancel. In CCHM, filling is defined using connections, so it’s a little different, but I think there still has to be a dependence on z for it to even type check — it should come up because of the connection term that is substituted into the type of the composition problem. So I’d guess there is still a problem in the aligned algorithm for CCHM. <br> <br> However, it would be great if this is wrong and something does work! <br> <br> -Dan<br> <br> > On Sep 15, 2019, at 10:18 PM, Jasper Hugunin <<a href="mailto:jasperh@cs.washington.edu" target="_blank">jasperh@cs.washington.edu</a>> wrote:<br> > <br> > This doesn't seem right; as far as I can tell, composition for Glue types in CCHM preserves regularity and reduces to composition in A on phi.<br> > <br> > - Jasper Hugunin<br> > <br> > On Sun, Sep 15, 2019 at 3:28 AM Anders Mortberg <<a href="mailto:anders.mortberg@math.su.se" target="_blank">anders.mortberg@math.su.se</a>> wrote:<br> > Hi Jasper,<br> > <br> > Indeed, the problem is to construct an algorithm for comp (or even<br> > coe/transp) for Glue that reduces to the one of A when phi is true<br> > while still preserving regularity. It was pointed out independently by<br> > Sattler and Orton around 2016 that one can factor out this step in our<br> > algorithm in a separate lemma that is now called "alignment". This is<br> > Thm 6.13 in Orton-Pitts and discussed in a paragraph in the end of<br> > section 2.11 of ABCFHL. Unless I'm misremembering this is exactly<br> > where regularity for comp for Glue types break down. In this step we<br> > do an additional comp/hcomp that inserts an additional forall i. phi<br> > face making the comp/coe irregular.<br> > <br> > One could imagine there being a way to modify the algorithm to avoid<br> > this, maybe by inlining the alignment step... But despite considerable<br> > efforts no one has been able to figure this out and I think Swan's<br> > recent paper (<a href="https://arxiv.org/abs/1808.00920v3" rel="noreferrer" target="_blank">https://arxiv.org/abs/1808.00920v3</a>) shows that this is<br> > not even possible!<br> > <br> > Another approach would be to have weak Glue types that don't strictly<br> > reduce to A when phi is true, but this causes problems for the<br> > composition in the universe and would be weird for cubical type<br> > theory...<br> > <br> > In light of Swan's negative results I think we need a completely new<br> > approach if we ever hope to solve this problem. Luckily for you Andrew<br> > Swan is starting as a postdoc over in Baker Hall in October, so he can<br> > explain his counterexamples to you in person.<br> > <br> > Best,<br> > Anders<br> > <br> > On Sun, Sep 15, 2019 at 7:57 AM Jasper Hugunin<br> > <<a href="mailto:jasperh@cs.washington.edu" target="_blank">jasperh@cs.washington.edu</a>> wrote:<br> > ><br> > > Offline, Carlo Angiuli showed me that the difficulty was in part 1, because of a subtlety I had been forgetting.<br> > ><br> > > Since types are *Kan* cubical sets, we need that the Kan operations agree as well as the sets.<br> > > So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, compGlue) = (A, compA), and getting that the Kan operations to agree was/is difficult.<br> > > (Now that I know what the answer is, it is clear that this was already explained in the initial discussion.)<br> > ><br> > > Humbly,<br> > > - Jasper Hugunin<br> > ><br> > > On Fri, Sep 13, 2019 at 2:10 AM Jasper Hugunin <<a href="mailto:jasperh@cs.washington.edu" target="_blank">jasperh@cs.washington.edu</a>> wrote:<br> > >><br> > >> Hello all,<br> > >><br> > >> I've been trying to understand better why composition for the universe does not satisfy regularity.<br> > >> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts:<br> > >> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself)<br> > >> 2. That equiv^i (refl A) reduces to equivRefl A<br> > >> I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument.<br> > >><br> > >> Context:<br> > >> I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly.<br> > >> If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in this thread on the HoTT mailing list, the definition of composition for the universe was found to not satisfy regularity.<br> > >> I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in the CCHM paper (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything).<br> > >><br> > >> Best regards,<br> > >> - Jasper Hugunin<br> > ><br> > > --<br> > > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br> > > To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory%2Bunsubscribe@googlegroups.com" target="_blank"> HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br> > > To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com" rel="noreferrer" target="_blank"> https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com</a>.<br> > <br> > -- <br> > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br> > To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory%2Bunsubscribe@googlegroups.com" target="_blank"> HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br> > To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com" rel="noreferrer" target="_blank"> https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com</a>.<br> <br> </blockquote> </div> </div> </blockquote> </div> </body> </html> <p></p> -- <br /> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br /> To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br /> To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CB28E4E1-73EC-4405-A268-350D028A0C93%40wesleyan.edu?utm_medium=email&utm_source=footer">https://groups.google.com/d/msgid/HomotopyTypeTheory/CB28E4E1-73EC-4405-A268-350D028A0C93%40wesleyan.edu</a>.<br /> ^ permalink raw reply [flat|nested] 13+ messages in thread

*Re: [HoTT] A question about the problem with regularity in CCHM cubical type theory2019-09-16 19:01 ` Licata, Dan@ 2019-09-16 20:17 ` Jasper Hugunin2019-09-18 12:16 ` Anders Mortberg 0 siblings, 1 reply; 13+ messages in thread From: Jasper Hugunin @ 2019-09-16 20:17 UTC (permalink / raw) To: Licata, Dan;+Cc:HomotopyTypeTheory [-- Attachment #1: Type: text/plain, Size: 20484 bytes --] I agree with the problem of using Glue types for the composition operation in the universe. You could imagine an extra equation that Glue [ phi |-> (A, reflEquiv) ] A = A, but this is somehow unnatural. However, it is what I was postulating in step 1 of the initial message of this thread. (You then need comp Glue to respect this equation, which appears impossible.) The way to get around it is, in my opinion, to add a separate type former Box^i [ phi |-> T ] A for phi |- A = T(i1), satisfying the laws phi |- Box^i [ phi |-> T ] A = T(i0) and regularity: Box^i [ phi |-> A ] A = A. You then need comp Box to respect Box^i [ phi |-> A ] A = A, and this is also apparently not possible in CCHM, but you now have the extra information that A is a line of types. (Using Box to turn an equivalence into a line of types in the definition of comp Box is circular.) I've developed a notion of (regular) n-dimensional composition, which I think might suffice to complete the argument. If you call a notion of Box that satisfies Box^i [ phi |-> A ] A = A "regular Box's", then the problem can be reduced to saying that to give regular 1-dimensional composition of regular 1-dimensional boxes, you need some sort of "(doubly) regular 2-dimensional composition" for A, and in CCHM such we can only get this "2-dimensional composition" which is regular in one direction or the other. Of course (I haven't actually checked, but my intuition says that), once you have 2-dimensional composition you will need n-dimensional composition, and then hopefully regular (n+m)-dimensional composition for A will suffice to define regular n-dimensional composition of regular n-dimensional Box's. Below I'll put an explanation of my idea of regular n-dimensional composition (returning an (n-1)-dimensional cube), since it feels unfair to say "I know how to do this" and hide "how to do this". Unfortunately, it is quite complex; read at your own peril. I don't yet know how to intelligibly describe n-dimensional composition for Glue and Box. For now I'll just say that they should be essentially the same as in the 1-dimensional case, but with extra faces in the equiv and final hcomp steps corresponding to faces in the result. =============== In CCHM, the basic Kan operation is (comp^i A [ phi |-> a ] a0 : A(i1) [ phi |-> a(i1) ]) for i |- A with phi, i |- a : A and a0 : A(i0) [ phi |-> a(i0) ]. Regularity for this operation means that if A and a are independent of i, then comp^i A [ phi |-> a ] a0 = a0. We have regular composition for Glue types, but we don't have comp^i (Glue [ phi |-> (A, equivRefl) ] A) = comp^i A. Simplifying things a little, we can take hcom^i U [ phi |-> T ] A = Box^i [ phi |-> T(i := ~ i) ] A to be a new type former, and give that a regular composition operation. Here the thing blocking us from getting comp^i (Box^j [ phi |-> A ] A) = comp^i A is that, given i, j |- T with phi, i, j |- t : T and t0 : T(i0)(j0)[ phi |-> t(i0)(j0) ], we need a Path T(i1)(j1) (comp^i T(j1) [ phi |-> t(j1) ] (comp^j T(i0) [ phi |-> t(i0) ] t0)) (comp^j T(i1) [ phi |-> t(i1) ] (comp^i T(j0) [ phi |-> t(j0) ] t0)) which is refl if T is degenerate in i OR j. This path plays the role that pres does in composition for Glue. (I will write (i o j) for composition over j then over i, and (i = j) for composition over the diagonal (i = j). Then we want a path from (i o j) to (j o i) which is degenerate if T is degenerate in i OR j. We can't construct such a doubly regular path, but we can postulate it as a new operation our types have to have, as a sort of regular composition over two dimensions simultaneously. Write (i ?'[a] j) for this, where a gives the location in the path. However, my intuition tells me that while this two-dimensional regular composition may be preserved by all the usual type formers, optimistically including Glue and Box, because the two-dimensional composition for Box will have to satisfy an additional law comp2^i^j (Box [ phi |-> A ] A) = comp2^i^j A, we will end up needing some sort of three-dimensional analogue. Once we need dimensions 1 and 2, we will almost certainly need dimension n. But what should the type of three dimensional regular composition be? There are six ways to compose along the edges of a cube, forming a hexagon that we wan't to fill, but hexagons don't fit nicely into cubical type theory. Here, we remember that there is one more way to compose across a square: along the diagonal (comp^k T(i,j:=k) [ phi |-> t(i,j:=k) ] t0), which agrees with composing either right then up or up then right when T is degenerate in i or j (with regularity). Allowing diagonals, for each square we can give a path from the diagonal to going up then right, with swapping i and j giving a path to going right then up. Then if both of these are degenerate when T is degenerate in i or j, their composition is also, so we recover a path between (i o j) and (j o i). And this formulation can be extended to higher dimensions straightforwardly. For each n-cube i_1, ..., i_n |- A, we have an n-dimensional regular composition operation which is a (n-1)-dimensional cube. Consider notation (i_1 ?[j_1] i_2 ?[j_2] ... ?[j_n-1] i_n) This is supposed to represent composition in an n-cube indexed by the i's, where our position in the resulting (n-1)-cube is given by the j's. We have to describe the faces of this cube, which we describe by saying that ?[0] reduces to = and ?[1] reduces to o. Thus for 2-dimensional A, we have a line (i = j) --- (i ?[a] j) --- (i o j), and for three dimensional A, we have a square with four faces (i = j ?[a_2] k), (i o j ?[a_2] k), (i ?[a1] j = k) (i ?[a1] j o k), relating the four corners given by coercing over i then j then k, coercing over i then j and k simultaneously, coercing over i and j simultaneously then coercing over k, and coercing over i, j, and k simultaneously. The point is that this gives a well-defined notion of cube. We also have to define the regularity condition: what happens when A, a are degenerate in i_k? We require that (i_1 ... i_k-1 ?[j_k-1] i_k ?[j_k] i_k+1 ... i_n) is equal to (i_1 ... i_k-1 ?[j_k-1 v j_k] i_k+1 ... i_n), treating j_0 = j_n = 1. Extending this to = and o, if A, a are degenerate in i, then (i = j) and (i o j) reduce to (j). On a two-dimensional cube, this says that (i ?[a] j) reduces to (j) when A, a are degenerate in i, and to (i) when A, a are degenerate in j. (That this is all coherent is obvious to me, but I have no idea how to explain it well) This all gives a notion of n-dimensional regular composition, which takes an n-cube type A and partial term phi, i1, ..., in |- a and a base point a0 : A(i_k := 0)[ phi |-> a(i_k := 0) ] and returns an (n-1)-cube in A(i_k := 1) [ phi |-> everywhere a(i_k := 1) ]. There are three classes of equations that this has to satisfy, two for the face maps j_k = 0 and j_k = 1 in the output, and one for when A, a are degenerate in i_k. In the one-dimensional case, this is the same as the specification of the usual regular comp. Considering j_k to be formally extended with j_0 = j_n = 1, we get a "zero-dimensional" composition operation, which should be taken to be the identity. (I have no idea what it would mean to let j_0 and j_n vary) I am reasonably confident that this operation is closed under usual type formers (Pi, Sg, Path, ...) by essentially the same argument as for 1-dimensional comp. I think I have worked out how to give a regular n-dimensional composition operation for Glue, by essentially the same argument as in CCHM, but with additional faces for j_k = 1 in the equiv and final hcomp steps. In this setting, we want Box to also be m-dimensional: j_1 ... j_n-1 |- Box^i1...^im _{j_1}..._{j_n-1} [ phi |-> T ] A for phi, i1, ..., im |- T, with phi |- A = T(i_k := 1). I think I have worked out how to give a regular n-dimensional composition operation for m-dimensional Box, using essentially the same argument as for Glue, but replacing pres with the composition of two paths given by (m+n)-dimensional regular composition. To use Box as the regular n-dimensional composition operation for the universe, we need that (Box, comp Box) respects the equations for when j_k = 0, j_k = 1, or T is independent of j. My hope is that, as in the (1, 1) dimensional case, using (m+n)-dimensional regular composition for pres will make this work. I have sketched on paper that composition for Glue and Box are regular, but that is already pushing the limits of my confidence in paper calculations. Checking that comp Box respects the equations that it needs to is another layer more complex, and I haven't managed to do so on paper. However, by analogy with the (1, 1) dimensional case, I am hopeful. On Mon, Sep 16, 2019 at 3:01 PM Licata, Dan <dlicata@wesleyan.edu> wrote: > Wow! I read that pretty closely and couldn’t find a problem. That is > surprising to me. Will look more later. > > What I was saying about fill for the aligning algorithm is also wrong — I > wasn’t thinking that the type of the filling was also degenerate, but of > course it is here. So that might work too. > > However, even if there can be a universe of regular types that is closed > under glue types, there’s still a problem with using those glue types to > show that that universe is itself regularly fibrant, I think? If you define > comp U [phi -> i.T] B to be Glue [phi -> T(1),...] B then no matter how > nice the equivalence is (eg the identity) when i doesn’t occur in T, the > type will not equal B — that would be an extra equation about the Glue type > constructor itself. Does that seem right? > > -Dan > > On Sep 16, 2019, at 1:09 PM, Jasper Hugunin <jasperh@cs.washington.edu> > wrote: > > Hi Dan, > > Of course. I'm thinking primarily of composition for Glue given in the > CCHM paper you linked, reproduced below. > As you know, the single potential issue is that we need pres of a > degenerate filling problem and function to be reflexivity. I claim that > this holds by regularity of composition in T and A, partly as a consequence > of the fact that regularity of composition implies regularity of filling > (that fill of a degenerate system is refl), which certainly holds for fill > defined by connections (and I believe also holds for fill as defined in > ABCFHL). > > (a) > Given i |- B = Glue [ phi |-> (T, f) ] A, with psi, i |- b : B and b0 : > B(i0)[ psi |-> b(i0) ], we want to compute b1 = comp^i B [ psi |-> b ] b0 : > B(i1)[ psi |-> b(i1) ]. > We set a := unglue b and a0 := unglue b0. > Set delta := forall i. phi. > Then we take: > a1' := comp^i A [ psi |-> a ] a0 > delta |- t1' := comp^i T [ psi |-> b ] b0 > delta |- omega := pres^i f [ psi |-> b ] b0 > phi(i1) |- (t, alpha) := equiv f(i1) [ delta |-> (t1', omega), psi |-> > (b(i1), refl a1') ] a1' > a1 := hcomp^j A(i1) [ phi(i1) |-> alpha j, psi |-> a(i1) ] a1' (note that > in the regular setting the psi face is redundant) > b1 := glue [ phi(i1) |-> t1 ] a1 > > With given i |- f : T -> A, with psi, i |- b : T and b0 : T(i0)[ psi |-> > b(i0) ], we define > pres^i f [ psi |-> b ] b0 = <j> comp^i A [ psi |-> f b, j = 1 |-> f > (fill^i T [ psi |-> b ] b0) ] (f(i0) b0). > > (b) > Now consider the regular case, where phi, T, f, and A are independent of > i. We want that b1 = b0. > We have that a is independent of i, and delta = phi. > > First consider delta (= phi) |- pres^i f [ psi |-> b ] b0. (This is the > explanation of your first dash) > Note that if comp^i A is regular, then fill^i A [ psi |-> b ] b0 = b > This is <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> t ] > t0) ] (f t0) = <j> comp^i A [ psi |-> f b, j = 1 |-> f t0 ] (f t0) = <j> f > t0. > Thus pres of a degenerate filling problem and function is reflexivity. > > Going back to composition of Glue, > a1' = a0 > phi |- t1' = b0 > phi |- omega = refl (f b0) > phi |- (t1, alpha) = (t1', omega) (since delta = phi, so we end up in the > delta face of equiv) > a1 = a1' (the only dependence on j is via (alpha j), but alpha = omega = > refl, so this filling problem is degenerate) > b1 = glue [ phi |-> t1 ] a1 = glue [ phi |-> b0 ] a0 = glue [ phi |-> b0 ] > (unglue b0) = b0 (by eta, see Figure 4 in CCHM) > > Thus this algorithm for composition of Glue is regular. > Other algorithms, such as the one in ABCFHL, may not be, but I am prone to > believe that there exist regular algorithms in other settings including > Orton-Pitts and Cartesian cubes. > > Best regards, > - Jasper Hugunin > > On Mon, Sep 16, 2019 at 12:18 PM Licata, Dan <dlicata@wesleyan.edu> wrote: > >> Hi Jasper, >> >> It would help me follow the discussion if you could say a little more >> about (a) which version of composition for Glue exactly you mean (because >> there is at least the one in the CCHM paper and the “aligned” one from >> Orton-Pitts, which are intensionally different, as well as other possible >> variations), and (b) include some of your reasoning for why you think >> things are regular, to make it easier for me and others to reconstruct. >> >> My current understanding is that >> >> - For CCHM proper https://arxiv.org/pdf/1611.02108.pdf the potential >> issue is with the ‘pres’ path omega, which via the equiv operation ends up >> in alpha, so the system in a1 may not be degenerate even if the input is. >> Do you think this does work out to be degenerate? >> >> - For the current version of ABCFHL >> https://github.com/dlicata335/cart-cube/blob/master/cart-cube.pdf which >> uses aligning “all the way at the outside”, an issue is with the adjust_com >> operation on page 20, which is later used for aligning (in that case beta >> is (forall i phi)). The potential issue is that adjust_com uses a >> *filler*, not just a composition from 0 to 1, so even if t doesn’t depend >> on z, the filling does, and the outer com won’t cancel. In CCHM, filling >> is defined using connections, so it’s a little different, but I think there >> still has to be a dependence on z for it to even type check — it should >> come up because of the connection term that is substituted into the type of >> the composition problem. So I’d guess there is still a problem in the >> aligned algorithm for CCHM. >> >> However, it would be great if this is wrong and something does work! >> >> -Dan >> >> > On Sep 15, 2019, at 10:18 PM, Jasper Hugunin <jasperh@cs.washington.edu> >> wrote: >> > >> > This doesn't seem right; as far as I can tell, composition for Glue >> types in CCHM preserves regularity and reduces to composition in A on phi. >> > >> > - Jasper Hugunin >> > >> > On Sun, Sep 15, 2019 at 3:28 AM Anders Mortberg < >> anders.mortberg@math.su.se> wrote: >> > Hi Jasper, >> > >> > Indeed, the problem is to construct an algorithm for comp (or even >> > coe/transp) for Glue that reduces to the one of A when phi is true >> > while still preserving regularity. It was pointed out independently by >> > Sattler and Orton around 2016 that one can factor out this step in our >> > algorithm in a separate lemma that is now called "alignment". This is >> > Thm 6.13 in Orton-Pitts and discussed in a paragraph in the end of >> > section 2.11 of ABCFHL. Unless I'm misremembering this is exactly >> > where regularity for comp for Glue types break down. In this step we >> > do an additional comp/hcomp that inserts an additional forall i. phi >> > face making the comp/coe irregular. >> > >> > One could imagine there being a way to modify the algorithm to avoid >> > this, maybe by inlining the alignment step... But despite considerable >> > efforts no one has been able to figure this out and I think Swan's >> > recent paper (https://arxiv.org/abs/1808.00920v3) shows that this is >> > not even possible! >> > >> > Another approach would be to have weak Glue types that don't strictly >> > reduce to A when phi is true, but this causes problems for the >> > composition in the universe and would be weird for cubical type >> > theory... >> > >> > In light of Swan's negative results I think we need a completely new >> > approach if we ever hope to solve this problem. Luckily for you Andrew >> > Swan is starting as a postdoc over in Baker Hall in October, so he can >> > explain his counterexamples to you in person. >> > >> > Best, >> > Anders >> > >> > On Sun, Sep 15, 2019 at 7:57 AM Jasper Hugunin >> > <jasperh@cs.washington.edu> wrote: >> > > >> > > Offline, Carlo Angiuli showed me that the difficulty was in part 1, >> because of a subtlety I had been forgetting. >> > > >> > > Since types are *Kan* cubical sets, we need that the Kan operations >> agree as well as the sets. >> > > So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, >> compGlue) = (A, compA), and getting that the Kan operations to agree was/is >> difficult. >> > > (Now that I know what the answer is, it is clear that this was >> already explained in the initial discussion.) >> > > >> > > Humbly, >> > > - Jasper Hugunin >> > > >> > > On Fri, Sep 13, 2019 at 2:10 AM Jasper Hugunin < >> jasperh@cs.washington.edu> wrote: >> > >> >> > >> Hello all, >> > >> >> > >> I've been trying to understand better why composition for the >> universe does not satisfy regularity. >> > >> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> >> equiv^i E ] A, I would expect regularity to follow from two parts: >> > >> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of >> regularity condition for the Glue type constructor itself) >> > >> 2. That equiv^i (refl A) reduces to equivRefl A >> > >> I'm curious as to which (or both) of these parts was the issue, or >> if regularity for the universe was supposed to follow from a different >> argument. >> > >> >> > >> Context: >> > >> I've been studying and using CCHM cubical type theory recently, and >> often finding myself wishing that J computed strictly. >> > >> If I understand correctly, early implementations of ctt did have >> strict J for Path types, and this was justified by a "regularity" condition >> on the composition operation, but as discussed in this thread on the HoTT >> mailing list, the definition of composition for the universe was found to >> not satisfy regularity. >> > >> I don't remember seeing the regularity condition defined anywhere, >> but my understanding is that it requires that composition in a degenerate >> line of types, with the system of constraints giving the sides of the box >> also degenerate in that direction, reduces to just the bottom of the box. >> This seems to be closed under the usual type formers, plus Glue, but not >> the universe with computation defined as in the CCHM paper (for trivial >> reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi >> |-> equiv^i refl ] A not reducing to anything). >> > >> >> > >> Best regards, >> > >> - Jasper Hugunin >> > > >> > > -- >> > > You received this message because you are subscribed to the Google >> Groups "Homotopy Type Theory" group. >> > > To unsubscribe from this group and stop receiving emails from it, >> send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. >> > > To view this discussion on the web visit >> https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com >> . >> > >> > -- >> > You received this message because you are subscribed to the Google >> Groups "Homotopy Type Theory" group. >> > To unsubscribe from this group and stop receiving emails from it, send >> an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. >> > To view this discussion on the web visit >> https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com >> . >> >> -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8E03C3BMEwi-T4qjet4EbCgnePhR3Ffa1MepxNmtZoUA%40mail.gmail.com. [-- Attachment #2: Type: text/html, Size: 24466 bytes --] <div dir="ltr">I agree with the problem of using Glue types for the composition operation in the universe.<div>You could imagine an extra equation that Glue [ phi |-> (A, reflEquiv) ] A = A, but this is somehow unnatural.</div><div>However, it is what I was postulating in step 1 of the initial message of this thread.</div><div>(You then need comp Glue to respect this equation, which appears impossible.)</div><div><br><div>The way to get around it is, in my opinion, to add a separate type former Box^i [ phi |-> T ] A for phi |- A = T(i1), satisfying the laws phi |- Box^i [ phi |-> T ] A = T(i0) and regularity: Box^i [ phi |-> A ] A = A.</div></div><div>You then need comp Box to respect Box^i [ phi |-> A ] A = A, and this is also apparently not possible in CCHM, but you now have the extra information that A is a line of types. (Using Box to turn an equivalence into a line of types in the definition of comp Box is circular.)</div><div><br></div><div>I've developed a notion of (regular) n-dimensional composition, which I think might suffice to complete the argument.</div><div>If you call a notion of Box that satisfies Box^i [ phi |-> A ] A = A "regular Box's", then the problem can be reduced to saying that to give regular 1-dimensional composition of regular 1-dimensional boxes, you need some sort of "(doubly) regular 2-dimensional composition" for A, and in CCHM such we can only get this "2-dimensional composition" which is regular in one direction or the other.</div><div>Of course (I haven't actually checked, but my intuition says that), once you have 2-dimensional composition you will need n-dimensional composition, and then hopefully regular (n+m)-dimensional composition for A will suffice to define regular n-dimensional composition of regular n-dimensional Box's.</div><div><br></div><div>Below I'll put an explanation of my idea of regular n-dimensional composition (returning an (n-1)-dimensional cube), since it feels unfair to say "I know how to do this" and hide "how to do this".</div><div>Unfortunately, it is quite complex; read at your own peril.</div><div><br></div><div>I don't yet know how to intelligibly describe n-dimensional composition for Glue and Box.</div><div>For now I'll just say that they should be essentially the same as in the 1-dimensional case, but with extra faces in the equiv and final hcomp steps corresponding to faces in the result.</div><div><br></div><div>===============</div><div><br></div><div><div>In CCHM, the basic Kan operation is (comp^i A [ phi |-> a ] a0 : A(i1) [ phi |-> a(i1) ]) for i |- A with phi, i |- a : A and a0 : A(i0) [ phi |-> a(i0) ].<br></div><div>Regularity for this operation means that if A and a are independent of i, then comp^i A [ phi |-> a ] a0 = a0.</div><div>We have regular composition for Glue types, but we don't have comp^i (Glue [ phi |-> (A, equivRefl) ] A) = comp^i A.</div><div>Simplifying things a little, we can take hcom^i U [ phi |-> T ] A = Box^i [ phi |-> T(i := ~ i) ] A to be a new type former, and give that a regular composition operation.</div><div>Here the thing blocking us from getting comp^i (Box^j [ phi |-> A ] A) = comp^i A is that, given i, j |- T with phi, i, j |- t : T and t0 : T(i0)(j0)[ phi |-> t(i0)(j0) ],</div><div>we need a Path T(i1)(j1) (comp^i T(j1) [ phi |-> t(j1) ] (comp^j T(i0) [ phi |-> t(i0) ] t0)) (comp^j T(i1) [ phi |-> t(i1) ] (comp^i T(j0) [ phi |-> t(j0) ] t0)) which is refl if T is degenerate in i OR j.</div><div>This path plays the role that pres does in composition for Glue.</div><div>(I will write (i o j) for composition over j then over i, and (i = j) for composition over the diagonal (i = j). Then we want a path from (i o j) to (j o i) which is degenerate if T is degenerate in i OR j.</div><div><br></div><div>We can't construct such a doubly regular path, but we can postulate it as a new operation our types have to have, as a sort of regular composition over two dimensions simultaneously. Write (i ?'[a] j) for this, where a gives the location in the path.</div><div>However, my intuition tells me that while this two-dimensional regular composition may be preserved by all the usual type formers, optimistically including Glue and Box, because the two-dimensional composition for Box will have to satisfy an additional law comp2^i^j (Box [ phi |-> A ] A) = comp2^i^j A, we will end up needing some sort of three-dimensional analogue.</div><div>Once we need dimensions 1 and 2, we will almost certainly need dimension n.</div><div><br></div><div>But what should the type of three dimensional regular composition be? There are six ways to compose along the edges of a cube, forming a hexagon that we wan't to fill, but hexagons don't fit nicely into cubical type theory.</div><div>Here, we remember that there is one more way to compose across a square: along the diagonal (comp^k T(i,j:=k) [ phi |-> t(i,j:=k) ] t0), which agrees with composing either right then up or up then right when T is degenerate in i or j (with regularity).</div><div>Allowing diagonals, for each square we can give a path from the diagonal to going up then right, with swapping i and j giving a path to going right then up. Then if both of these are degenerate when T is degenerate in i or j, their composition is also, so we recover a path between (i o j) and (j o i). And this formulation can be extended to higher dimensions straightforwardly.</div><div><br></div><div>For each n-cube i_1, ..., i_n |- A, we have an n-dimensional regular composition operation which is a (n-1)-dimensional cube. Consider notation (i_1 ?[j_1] i_2 ?[j_2] ... ?[j_n-1] i_n) This is supposed to represent composition in an n-cube indexed by the i's, where our position in the resulting (n-1)-cube is given by the j's. We have to describe the faces of this cube, which we describe by saying that ?[0] reduces to = and ?[1] reduces to o.</div><div>Thus for 2-dimensional A, we have a line (i = j) --- (i ?[a] j) --- (i o j), and for three dimensional A, we have a square with four faces (i = j ?[a_2] k), (i o j ?[a_2] k), (i ?[a1] j = k) (i ?[a1] j o k), relating the four corners given by coercing over i then j then k, coercing over i then j and k simultaneously, coercing over i and j simultaneously then coercing over k, and coercing over i, j, and k simultaneously.</div><div>The point is that this gives a well-defined notion of cube.</div><div>We also have to define the regularity condition: what happens when A, a are degenerate in i_k? We require that (i_1 ... i_k-1 ?[j_k-1] i_k ?[j_k] i_k+1 ... i_n) is equal to (i_1 ... i_k-1 ?[j_k-1 v j_k] i_k+1 ... i_n), treating j_0 = j_n = 1.</div><div>Extending this to = and o, if A, a are degenerate in i, then (i = j) and (i o j) reduce to (j).</div><div>On a two-dimensional cube, this says that (i ?[a] j) reduces to (j) when A, a are degenerate in i, and to (i) when A, a are degenerate in j.</div><div>(That this is all coherent is obvious to me, but I have no idea how to explain it well)</div><div><br></div><div>This all gives a notion of n-dimensional regular composition, which takes an n-cube type A and partial term phi, i1, ..., in |- a and a base point a0 : A(i_k := 0)[ phi |-> a(i_k := 0) ] and returns an (n-1)-cube in A(i_k := 1) [ phi |-> everywhere a(i_k := 1) ].</div><div>There are three classes of equations that this has to satisfy, two for the face maps j_k = 0 and j_k = 1 in the output, and one for when A, a are degenerate in i_k.</div><div>In the one-dimensional case, this is the same as the specification of the usual regular comp.</div><div>Considering j_k to be formally extended with j_0 = j_n = 1, we get a "zero-dimensional" composition operation, which should be taken to be the identity. (I have no idea what it would mean to let j_0 and j_n vary)</div><div>I am reasonably confident that this operation is closed under usual type formers (Pi, Sg, Path, ...) by essentially the same argument as for 1-dimensional comp.</div><div>I think I have worked out how to give a regular n-dimensional composition operation for Glue, by essentially the same argument as in CCHM, but with additional faces for j_k = 1 in the equiv and final hcomp steps.</div><div><br></div><div>In this setting, we want Box to also be m-dimensional: j_1 ... j_n-1 |- Box^i1...^im _{j_1}..._{j_n-1} [ phi |-> T ] A for phi, i1, ..., im |- T, with phi |- A = T(i_k := 1).</div><div>I think I have worked out how to give a regular n-dimensional composition operation for m-dimensional Box, using essentially the same argument as for Glue, but replacing pres with the composition of two paths given by (m+n)-dimensional regular composition.</div><div>To use Box as the regular n-dimensional composition operation for the universe, we need that (Box, comp Box) respects the equations for when j_k = 0, j_k = 1, or T is independent of j.</div><div>My hope is that, as in the (1, 1) dimensional case, using (m+n)-dimensional regular composition for pres will make this work.</div><div><br></div><div>I have sketched on paper that composition for Glue and Box are regular, but that is already pushing the limits of my confidence in paper calculations.</div><div>Checking that comp Box respects the equations that it needs to is another layer more complex, and I haven't managed to do so on paper.</div><div>However, by analogy with the (1, 1) dimensional case, I am hopeful.</div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Mon, Sep 16, 2019 at 3:01 PM Licata, Dan <<a href="mailto:dlicata@wesleyan.edu">dlicata@wesleyan.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> <div dir="auto"> Wow! I read that pretty closely and couldn’t find a problem. That is surprising to me. Will look more later. <div><br> </div> <div>What I was saying about fill for the aligning algorithm is also wrong — I wasn’t thinking that the type of the filling was also degenerate, but of course it is here. So that might work too. </div> <div><br> </div> <div>However, even if there can be a universe of regular types that is closed under glue types, there’s still a problem with using those glue types to show that that universe is itself regularly fibrant, I think? If you define comp U [phi -> i.T] B to be Glue [phi -> T(1),...] B then no matter how nice the equivalence is (eg the identity) when i doesn’t occur in T, the type will not equal B — that would be an extra equation about the Glue type constructor itself. Does that seem right?</div> <div><br> </div> <div> <div id="gmail-m_-8115217170406216258AppleMailSignature" dir="ltr"> <div><span class="gmail-m_-8115217170406216258Apple-style-span">-Dan</span></div> </div> <div dir="ltr"><br> On Sep 16, 2019, at 1:09 PM, Jasper Hugunin <<a href="mailto:jasperh@cs.washington.edu" target="_blank">jasperh@cs.washington.edu</a>> wrote:<br> <br> </div> <blockquote type="cite"> <div dir="ltr"> <div dir="ltr">Hi Dan, <div><br> </div> <div>Of course. I'm thinking primarily of composition for Glue given in the CCHM paper you linked, reproduced below.</div> <div>As you know, the single potential issue is that we need pres of a degenerate filling problem and function to be reflexivity. I claim that this holds by regularity of composition in T and A, partly as a consequence of the fact that regularity of composition implies regularity of filling (that fill of a degenerate system is refl), which certainly holds for fill defined by connections (and I believe also holds for fill as defined in ABCFHL).</div> <div><br> </div> <div>(a)</div> <div>Given i |- B = Glue [ phi |-> (T, f) ] A, with psi, i |- b : B and b0 : B(i0)[ psi |-> b(i0) ], we want to compute b1 = comp^i B [ psi |-> b ] b0 : B(i1)[ psi |-> b(i1) ].</div> <div>We set a := unglue b and a0 := unglue b0.</div> <div>Set delta := forall i. phi.</div> <div>Then we take:</div> <div>a1' := comp^i A [ psi |-> a ] a0</div> <div>delta |- t1' := comp^i T [ psi |-> b ] b0</div> <div>delta |- omega := pres^i f [ psi |-> b ] b0</div> <div>phi(i1) |- (t, alpha) := equiv f(i1) [ delta |-> (t1', omega), psi |-> (b(i1), refl a1') ] a1'</div> <div>a1 := hcomp^j A(i1) [ phi(i1) |-> alpha j, psi |-> a(i1) ] a1' (note that in the regular setting the psi face is redundant)</div> <div>b1 := glue [ phi(i1) |-> t1 ] a1</div> <div><br> </div> <div>With given i |- f : T -> A, with psi, i |- b : T and b0 : T(i0)[ psi |-> b(i0) ], we define</div> <div>pres^i f [ psi |-> b ] b0 = <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> b ] b0) ] (f(i0) b0).</div> <div><br> </div> <div>(b)</div> <div>Now consider the regular case, where phi, T, f, and A are independent of i. We want that b1 = b0.</div> <div>We have that a is independent of i, and delta = phi.</div> <div><br> </div> <div>First consider delta (= phi) |- pres^i f [ psi |-> b ] b0. (This is the explanation of your first dash)</div> <div>Note that if comp^i A is regular, then fill^i A [ psi |-> b ] b0 = b</div> <div>This is <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> t ] t0) ] (f t0) = <j> comp^i A [ psi |-> f b, j = 1 |-> f t0 ] (f t0) = <j> f t0.</div> <div>Thus pres of a degenerate filling problem and function is reflexivity.</div> <div><br> </div> <div>Going back to composition of Glue,</div> <div>a1' = a0<br> </div> <div>phi |- t1' = b0</div> <div>phi |- omega = refl (f b0)</div> <div>phi |- (t1, alpha) = (t1', omega) (since delta = phi, so we end up in the delta face of equiv)</div> <div>a1 = a1' (the only dependence on j is via (alpha j), but alpha = omega = refl, so this filling problem is degenerate)</div> <div>b1 = glue [ phi |-> t1 ] a1 = glue [ phi |-> b0 ] a0 = glue [ phi |-> b0 ] (unglue b0) = b0 (by eta, see Figure 4 in CCHM)</div> <div><br> </div> <div>Thus this algorithm for composition of Glue is regular.</div> <div>Other algorithms, such as the one in ABCFHL, may not be, but I am prone to believe that there exist regular algorithms in other settings including Orton-Pitts and Cartesian cubes.</div> <div><br> </div> <div>Best regards,</div> <div>- Jasper Hugunin</div> </div> <br> <div class="gmail_quote"> <div dir="ltr" class="gmail_attr">On Mon, Sep 16, 2019 at 12:18 PM Licata, Dan <<a href="mailto:dlicata@wesleyan.edu" target="_blank">dlicata@wesleyan.edu</a>> wrote:<br> </div> <blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> Hi Jasper,<br> <br> It would help me follow the discussion if you could say a little more about (a) which version of composition for Glue exactly you mean (because there is at least the one in the CCHM paper and the “aligned” one from Orton-Pitts, which are intensionally different, as well as other possible variations), and (b) include some of your reasoning for why you think things are regular, to make it easier for me and others to reconstruct. <br> <br> My current understanding is that<br> <br> - For CCHM proper <a href="https://arxiv.org/pdf/1611.02108.pdf" rel="noreferrer" target="_blank"> https://arxiv.org/pdf/1611.02108.pdf</a> the potential issue is with the ‘pres’ path omega, which via the equiv operation ends up in alpha, so the system in a1 may not be degenerate even if the input is. Do you think this does work out to be degenerate? <br> <br> - For the current version of ABCFHL <a href="https://github.com/dlicata335/cart-cube/blob/master/cart-cube.pdf" rel="noreferrer" target="_blank"> https://github.com/dlicata335/cart-cube/blob/master/cart-cube.pdf</a> which uses aligning “all the way at the outside”, an issue is with the adjust_com operation on page 20, which is later used for aligning (in that case beta is (forall i phi)). The potential issue is that adjust_com uses a *filler*, not just a composition from 0 to 1, so even if t doesn’t depend on z, the filling does, and the outer com won’t cancel. In CCHM, filling is defined using connections, so it’s a little different, but I think there still has to be a dependence on z for it to even type check — it should come up because of the connection term that is substituted into the type of the composition problem. So I’d guess there is still a problem in the aligned algorithm for CCHM. <br> <br> However, it would be great if this is wrong and something does work! <br> <br> -Dan<br> <br> > On Sep 15, 2019, at 10:18 PM, Jasper Hugunin <<a href="mailto:jasperh@cs.washington.edu" target="_blank">jasperh@cs.washington.edu</a>> wrote:<br> > <br> > This doesn't seem right; as far as I can tell, composition for Glue types in CCHM preserves regularity and reduces to composition in A on phi.<br> > <br> > - Jasper Hugunin<br> > <br> > On Sun, Sep 15, 2019 at 3:28 AM Anders Mortberg <<a href="mailto:anders.mortberg@math.su.se" target="_blank">anders.mortberg@math.su.se</a>> wrote:<br> > Hi Jasper,<br> > <br> > Indeed, the problem is to construct an algorithm for comp (or even<br> > coe/transp) for Glue that reduces to the one of A when phi is true<br> > while still preserving regularity. It was pointed out independently by<br> > Sattler and Orton around 2016 that one can factor out this step in our<br> > algorithm in a separate lemma that is now called "alignment". This is<br> > Thm 6.13 in Orton-Pitts and discussed in a paragraph in the end of<br> > section 2.11 of ABCFHL. Unless I'm misremembering this is exactly<br> > where regularity for comp for Glue types break down. In this step we<br> > do an additional comp/hcomp that inserts an additional forall i. phi<br> > face making the comp/coe irregular.<br> > <br> > One could imagine there being a way to modify the algorithm to avoid<br> > this, maybe by inlining the alignment step... But despite considerable<br> > efforts no one has been able to figure this out and I think Swan's<br> > recent paper (<a href="https://arxiv.org/abs/1808.00920v3" rel="noreferrer" target="_blank">https://arxiv.org/abs/1808.00920v3</a>) shows that this is<br> > not even possible!<br> > <br> > Another approach would be to have weak Glue types that don't strictly<br> > reduce to A when phi is true, but this causes problems for the<br> > composition in the universe and would be weird for cubical type<br> > theory...<br> > <br> > In light of Swan's negative results I think we need a completely new<br> > approach if we ever hope to solve this problem. Luckily for you Andrew<br> > Swan is starting as a postdoc over in Baker Hall in October, so he can<br> > explain his counterexamples to you in person.<br> > <br> > Best,<br> > Anders<br> > <br> > On Sun, Sep 15, 2019 at 7:57 AM Jasper Hugunin<br> > <<a href="mailto:jasperh@cs.washington.edu" target="_blank">jasperh@cs.washington.edu</a>> wrote:<br> > ><br> > > Offline, Carlo Angiuli showed me that the difficulty was in part 1, because of a subtlety I had been forgetting.<br> > ><br> > > Since types are *Kan* cubical sets, we need that the Kan operations agree as well as the sets.<br> > > So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, compGlue) = (A, compA), and getting that the Kan operations to agree was/is difficult.<br> > > (Now that I know what the answer is, it is clear that this was already explained in the initial discussion.)<br> > ><br> > > Humbly,<br> > > - Jasper Hugunin<br> > ><br> > > On Fri, Sep 13, 2019 at 2:10 AM Jasper Hugunin <<a href="mailto:jasperh@cs.washington.edu" target="_blank">jasperh@cs.washington.edu</a>> wrote:<br> > >><br> > >> Hello all,<br> > >><br> > >> I've been trying to understand better why composition for the universe does not satisfy regularity.<br> > >> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts:<br> > >> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself)<br> > >> 2. That equiv^i (refl A) reduces to equivRefl A<br> > >> I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument.<br> > >><br> > >> Context:<br> > >> I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly.<br> > >> If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in this thread on the HoTT mailing list, the definition of composition for the universe was found to not satisfy regularity.<br> > >> I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in the CCHM paper (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything).<br> > >><br> > >> Best regards,<br> > >> - Jasper Hugunin<br> > ><br> > > --<br> > > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br> > > To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory%2Bunsubscribe@googlegroups.com" target="_blank"> HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br> > > To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com" rel="noreferrer" target="_blank"> https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com</a>.<br> > <br> > -- <br> > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br> > To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory%2Bunsubscribe@googlegroups.com" target="_blank"> HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br> > To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com" rel="noreferrer" target="_blank"> https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com</a>.<br> <br> </blockquote> </div> </div> </blockquote> </div> </div> </blockquote></div> <p></p> -- <br /> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br /> To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br /> To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8E03C3BMEwi-T4qjet4EbCgnePhR3Ffa1MepxNmtZoUA%40mail.gmail.com?utm_medium=email&utm_source=footer">https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8E03C3BMEwi-T4qjet4EbCgnePhR3Ffa1MepxNmtZoUA%40mail.gmail.com</a>.<br /> ^ permalink raw reply [flat|nested] 13+ messages in thread

*Re: [HoTT] A question about the problem with regularity in CCHM cubical type theory2019-09-16 20:17 ` Jasper Hugunin@ 2019-09-18 12:16 ` Anders Mortberg2019-09-18 12:52 ` Thierry Coquand 0 siblings, 1 reply; 13+ messages in thread From: Anders Mortberg @ 2019-09-18 12:16 UTC (permalink / raw) To: Jasper Hugunin;+Cc:Licata, Dan, HomotopyTypeTheory I tried to recall what the problem with regularity for comp for universes was in CCHM and here's what I've come up with. As pointed out by Dan and Jasper we need an equation like "Glue [ phi |-> (A, reflEquiv) ] A = A" to get a regular version of the reduction of comp for U to comp for Glue. This indeed seems very unnatural and it is not what we tried. What we instead did in the old buggy version of cubicaltt was to add new hcomp_U values to CCHM for compositions of types and reduce comp in U to one of these: comp^i U [phi -> A] A0 = hcomp^i_U [phi -> A] A0 For regularity we need the following condition on hcomp_U (where "i # A" means that i does not occur in A, i.e. if we're only attaching degenerate sides to A0): if i # A then hcomp^i_U [phi -> A] A0 = A0 The problem is then to define comp^j (hcomp^i_U [phi -> A] A0) [psi -> B] B0 such that it satisfies the standard equations for comp/hcomp_U and regularity. There are in particular two regularity conditions that we need to take into account: 1. if j # (hcomp^i_U [phi -> A] A0) and j # B then comp^j (hcomp^i_U [phi -> A] A0) [psi -> B] B0 = B0 2. if i # A then comp^j (hcomp^i_U [phi -> A] A0) [psi -> B] B0 = comp^j A0 [psi -> B] B0 We achieved 1 by essentially doing the same algorithm as for comp Glue (which Jasper pointed out is indeed regular), but this only satisfied the equation comp^j (hcomp^i_U [] A0) [psi -> B] B0 = comp^j A0 [psi -> B] B0 and not the full version of 2. I think this is what Dan and the others found and reported to us, at least that's how I read the old thread. It might be possible to get 2 and not 1, but I would be very surprised if we can get both 1 and 2 by just adapting the algorithms. Indeed, in light of Andrew's negative results I would expect substantial changes and some new ideas to be necessary in order to give a constructive model of univalent type theory where Path = Id. -- Anders On Mon, Sep 16, 2019 at 10:17 PM Jasper Hugunin <jasperh@cs.washington.edu> wrote: > > I agree with the problem of using Glue types for the composition operation in the universe. > You could imagine an extra equation that Glue [ phi |-> (A, reflEquiv) ] A = A, but this is somehow unnatural. > However, it is what I was postulating in step 1 of the initial message of this thread. > (You then need comp Glue to respect this equation, which appears impossible.) > > The way to get around it is, in my opinion, to add a separate type former Box^i [ phi |-> T ] A for phi |- A = T(i1), satisfying the laws phi |- Box^i [ phi |-> T ] A = T(i0) and regularity: Box^i [ phi |-> A ] A = A. > You then need comp Box to respect Box^i [ phi |-> A ] A = A, and this is also apparently not possible in CCHM, but you now have the extra information that A is a line of types. (Using Box to turn an equivalence into a line of types in the definition of comp Box is circular.) > > I've developed a notion of (regular) n-dimensional composition, which I think might suffice to complete the argument. > If you call a notion of Box that satisfies Box^i [ phi |-> A ] A = A "regular Box's", then the problem can be reduced to saying that to give regular 1-dimensional composition of regular 1-dimensional boxes, you need some sort of "(doubly) regular 2-dimensional composition" for A, and in CCHM such we can only get this "2-dimensional composition" which is regular in one direction or the other. > Of course (I haven't actually checked, but my intuition says that), once you have 2-dimensional composition you will need n-dimensional composition, and then hopefully regular (n+m)-dimensional composition for A will suffice to define regular n-dimensional composition of regular n-dimensional Box's. > > Below I'll put an explanation of my idea of regular n-dimensional composition (returning an (n-1)-dimensional cube), since it feels unfair to say "I know how to do this" and hide "how to do this". > Unfortunately, it is quite complex; read at your own peril. > > I don't yet know how to intelligibly describe n-dimensional composition for Glue and Box. > For now I'll just say that they should be essentially the same as in the 1-dimensional case, but with extra faces in the equiv and final hcomp steps corresponding to faces in the result. > > =============== > > In CCHM, the basic Kan operation is (comp^i A [ phi |-> a ] a0 : A(i1) [ phi |-> a(i1) ]) for i |- A with phi, i |- a : A and a0 : A(i0) [ phi |-> a(i0) ]. > Regularity for this operation means that if A and a are independent of i, then comp^i A [ phi |-> a ] a0 = a0. > We have regular composition for Glue types, but we don't have comp^i (Glue [ phi |-> (A, equivRefl) ] A) = comp^i A. > Simplifying things a little, we can take hcom^i U [ phi |-> T ] A = Box^i [ phi |-> T(i := ~ i) ] A to be a new type former, and give that a regular composition operation. > Here the thing blocking us from getting comp^i (Box^j [ phi |-> A ] A) = comp^i A is that, given i, j |- T with phi, i, j |- t : T and t0 : T(i0)(j0)[ phi |-> t(i0)(j0) ], > we need a Path T(i1)(j1) (comp^i T(j1) [ phi |-> t(j1) ] (comp^j T(i0) [ phi |-> t(i0) ] t0)) (comp^j T(i1) [ phi |-> t(i1) ] (comp^i T(j0) [ phi |-> t(j0) ] t0)) which is refl if T is degenerate in i OR j. > This path plays the role that pres does in composition for Glue. > (I will write (i o j) for composition over j then over i, and (i = j) for composition over the diagonal (i = j). Then we want a path from (i o j) to (j o i) which is degenerate if T is degenerate in i OR j. > > We can't construct such a doubly regular path, but we can postulate it as a new operation our types have to have, as a sort of regular composition over two dimensions simultaneously. Write (i ?'[a] j) for this, where a gives the location in the path. > However, my intuition tells me that while this two-dimensional regular composition may be preserved by all the usual type formers, optimistically including Glue and Box, because the two-dimensional composition for Box will have to satisfy an additional law comp2^i^j (Box [ phi |-> A ] A) = comp2^i^j A, we will end up needing some sort of three-dimensional analogue. > Once we need dimensions 1 and 2, we will almost certainly need dimension n. > > But what should the type of three dimensional regular composition be? There are six ways to compose along the edges of a cube, forming a hexagon that we wan't to fill, but hexagons don't fit nicely into cubical type theory. > Here, we remember that there is one more way to compose across a square: along the diagonal (comp^k T(i,j:=k) [ phi |-> t(i,j:=k) ] t0), which agrees with composing either right then up or up then right when T is degenerate in i or j (with regularity). > Allowing diagonals, for each square we can give a path from the diagonal to going up then right, with swapping i and j giving a path to going right then up. Then if both of these are degenerate when T is degenerate in i or j, their composition is also, so we recover a path between (i o j) and (j o i). And this formulation can be extended to higher dimensions straightforwardly. > > For each n-cube i_1, ..., i_n |- A, we have an n-dimensional regular composition operation which is a (n-1)-dimensional cube. Consider notation (i_1 ?[j_1] i_2 ?[j_2] ... ?[j_n-1] i_n) This is supposed to represent composition in an n-cube indexed by the i's, where our position in the resulting (n-1)-cube is given by the j's. We have to describe the faces of this cube, which we describe by saying that ?[0] reduces to = and ?[1] reduces to o. > Thus for 2-dimensional A, we have a line (i = j) --- (i ?[a] j) --- (i o j), and for three dimensional A, we have a square with four faces (i = j ?[a_2] k), (i o j ?[a_2] k), (i ?[a1] j = k) (i ?[a1] j o k), relating the four corners given by coercing over i then j then k, coercing over i then j and k simultaneously, coercing over i and j simultaneously then coercing over k, and coercing over i, j, and k simultaneously. > The point is that this gives a well-defined notion of cube. > We also have to define the regularity condition: what happens when A, a are degenerate in i_k? We require that (i_1 ... i_k-1 ?[j_k-1] i_k ?[j_k] i_k+1 ... i_n) is equal to (i_1 ... i_k-1 ?[j_k-1 v j_k] i_k+1 ... i_n), treating j_0 = j_n = 1. > Extending this to = and o, if A, a are degenerate in i, then (i = j) and (i o j) reduce to (j). > On a two-dimensional cube, this says that (i ?[a] j) reduces to (j) when A, a are degenerate in i, and to (i) when A, a are degenerate in j. > (That this is all coherent is obvious to me, but I have no idea how to explain it well) > > This all gives a notion of n-dimensional regular composition, which takes an n-cube type A and partial term phi, i1, ..., in |- a and a base point a0 : A(i_k := 0)[ phi |-> a(i_k := 0) ] and returns an (n-1)-cube in A(i_k := 1) [ phi |-> everywhere a(i_k := 1) ]. > There are three classes of equations that this has to satisfy, two for the face maps j_k = 0 and j_k = 1 in the output, and one for when A, a are degenerate in i_k. > In the one-dimensional case, this is the same as the specification of the usual regular comp. > Considering j_k to be formally extended with j_0 = j_n = 1, we get a "zero-dimensional" composition operation, which should be taken to be the identity. (I have no idea what it would mean to let j_0 and j_n vary) > I am reasonably confident that this operation is closed under usual type formers (Pi, Sg, Path, ...) by essentially the same argument as for 1-dimensional comp. > I think I have worked out how to give a regular n-dimensional composition operation for Glue, by essentially the same argument as in CCHM, but with additional faces for j_k = 1 in the equiv and final hcomp steps. > > In this setting, we want Box to also be m-dimensional: j_1 ... j_n-1 |- Box^i1...^im _{j_1}..._{j_n-1} [ phi |-> T ] A for phi, i1, ..., im |- T, with phi |- A = T(i_k := 1). > I think I have worked out how to give a regular n-dimensional composition operation for m-dimensional Box, using essentially the same argument as for Glue, but replacing pres with the composition of two paths given by (m+n)-dimensional regular composition. > To use Box as the regular n-dimensional composition operation for the universe, we need that (Box, comp Box) respects the equations for when j_k = 0, j_k = 1, or T is independent of j. > My hope is that, as in the (1, 1) dimensional case, using (m+n)-dimensional regular composition for pres will make this work. > > I have sketched on paper that composition for Glue and Box are regular, but that is already pushing the limits of my confidence in paper calculations. > Checking that comp Box respects the equations that it needs to is another layer more complex, and I haven't managed to do so on paper. > However, by analogy with the (1, 1) dimensional case, I am hopeful. > > On Mon, Sep 16, 2019 at 3:01 PM Licata, Dan <dlicata@wesleyan.edu> wrote: >> >> Wow! I read that pretty closely and couldn’t find a problem. That is surprising to me. Will look more later. >> >> What I was saying about fill for the aligning algorithm is also wrong — I wasn’t thinking that the type of the filling was also degenerate, but of course it is here. So that might work too. >> >> However, even if there can be a universe of regular types that is closed under glue types, there’s still a problem with using those glue types to show that that universe is itself regularly fibrant, I think? If you define comp U [phi -> i.T] B to be Glue [phi -> T(1),...] B then no matter how nice the equivalence is (eg the identity) when i doesn’t occur in T, the type will not equal B — that would be an extra equation about the Glue type constructor itself. Does that seem right? >> >> -Dan >> >> On Sep 16, 2019, at 1:09 PM, Jasper Hugunin <jasperh@cs.washington.edu> wrote: >> >> Hi Dan, >> >> Of course. I'm thinking primarily of composition for Glue given in the CCHM paper you linked, reproduced below. >> As you know, the single potential issue is that we need pres of a degenerate filling problem and function to be reflexivity. I claim that this holds by regularity of composition in T and A, partly as a consequence of the fact that regularity of composition implies regularity of filling (that fill of a degenerate system is refl), which certainly holds for fill defined by connections (and I believe also holds for fill as defined in ABCFHL). >> >> (a) >> Given i |- B = Glue [ phi |-> (T, f) ] A, with psi, i |- b : B and b0 : B(i0)[ psi |-> b(i0) ], we want to compute b1 = comp^i B [ psi |-> b ] b0 : B(i1)[ psi |-> b(i1) ]. >> We set a := unglue b and a0 := unglue b0. >> Set delta := forall i. phi. >> Then we take: >> a1' := comp^i A [ psi |-> a ] a0 >> delta |- t1' := comp^i T [ psi |-> b ] b0 >> delta |- omega := pres^i f [ psi |-> b ] b0 >> phi(i1) |- (t, alpha) := equiv f(i1) [ delta |-> (t1', omega), psi |-> (b(i1), refl a1') ] a1' >> a1 := hcomp^j A(i1) [ phi(i1) |-> alpha j, psi |-> a(i1) ] a1' (note that in the regular setting the psi face is redundant) >> b1 := glue [ phi(i1) |-> t1 ] a1 >> >> With given i |- f : T -> A, with psi, i |- b : T and b0 : T(i0)[ psi |-> b(i0) ], we define >> pres^i f [ psi |-> b ] b0 = <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> b ] b0) ] (f(i0) b0). >> >> (b) >> Now consider the regular case, where phi, T, f, and A are independent of i. We want that b1 = b0. >> We have that a is independent of i, and delta = phi. >> >> First consider delta (= phi) |- pres^i f [ psi |-> b ] b0. (This is the explanation of your first dash) >> Note that if comp^i A is regular, then fill^i A [ psi |-> b ] b0 = b >> This is <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> t ] t0) ] (f t0) = <j> comp^i A [ psi |-> f b, j = 1 |-> f t0 ] (f t0) = <j> f t0. >> Thus pres of a degenerate filling problem and function is reflexivity. >> >> Going back to composition of Glue, >> a1' = a0 >> phi |- t1' = b0 >> phi |- omega = refl (f b0) >> phi |- (t1, alpha) = (t1', omega) (since delta = phi, so we end up in the delta face of equiv) >> a1 = a1' (the only dependence on j is via (alpha j), but alpha = omega = refl, so this filling problem is degenerate) >> b1 = glue [ phi |-> t1 ] a1 = glue [ phi |-> b0 ] a0 = glue [ phi |-> b0 ] (unglue b0) = b0 (by eta, see Figure 4 in CCHM) >> >> Thus this algorithm for composition of Glue is regular. >> Other algorithms, such as the one in ABCFHL, may not be, but I am prone to believe that there exist regular algorithms in other settings including Orton-Pitts and Cartesian cubes. >> >> Best regards, >> - Jasper Hugunin >> >> On Mon, Sep 16, 2019 at 12:18 PM Licata, Dan <dlicata@wesleyan.edu> wrote: >>> >>> Hi Jasper, >>> >>> It would help me follow the discussion if you could say a little more about (a) which version of composition for Glue exactly you mean (because there is at least the one in the CCHM paper and the “aligned” one from Orton-Pitts, which are intensionally different, as well as other possible variations), and (b) include some of your reasoning for why you think things are regular, to make it easier for me and others to reconstruct. >>> >>> My current understanding is that >>> >>> - For CCHM proper https://arxiv.org/pdf/1611.02108.pdf the potential issue is with the ‘pres’ path omega, which via the equiv operation ends up in alpha, so the system in a1 may not be degenerate even if the input is. Do you think this does work out to be degenerate? >>> >>> - For the current version of ABCFHL https://github.com/dlicata335/cart-cube/blob/master/cart-cube.pdf which uses aligning “all the way at the outside”, an issue is with the adjust_com operation on page 20, which is later used for aligning (in that case beta is (forall i phi)). The potential issue is that adjust_com uses a *filler*, not just a composition from 0 to 1, so even if t doesn’t depend on z, the filling does, and the outer com won’t cancel. In CCHM, filling is defined using connections, so it’s a little different, but I think there still has to be a dependence on z for it to even type check — it should come up because of the connection term that is substituted into the type of the composition problem. So I’d guess there is still a problem in the aligned algorithm for CCHM. >>> >>> However, it would be great if this is wrong and something does work! >>> >>> -Dan >>> >>> > On Sep 15, 2019, at 10:18 PM, Jasper Hugunin <jasperh@cs.washington.edu> wrote: >>> > >>> > This doesn't seem right; as far as I can tell, composition for Glue types in CCHM preserves regularity and reduces to composition in A on phi. >>> > >>> > - Jasper Hugunin >>> > >>> > On Sun, Sep 15, 2019 at 3:28 AM Anders Mortberg <anders.mortberg@math.su.se> wrote: >>> > Hi Jasper, >>> > >>> > Indeed, the problem is to construct an algorithm for comp (or even >>> > coe/transp) for Glue that reduces to the one of A when phi is true >>> > while still preserving regularity. It was pointed out independently by >>> > Sattler and Orton around 2016 that one can factor out this step in our >>> > algorithm in a separate lemma that is now called "alignment". This is >>> > Thm 6.13 in Orton-Pitts and discussed in a paragraph in the end of >>> > section 2.11 of ABCFHL. Unless I'm misremembering this is exactly >>> > where regularity for comp for Glue types break down. In this step we >>> > do an additional comp/hcomp that inserts an additional forall i. phi >>> > face making the comp/coe irregular. >>> > >>> > One could imagine there being a way to modify the algorithm to avoid >>> > this, maybe by inlining the alignment step... But despite considerable >>> > efforts no one has been able to figure this out and I think Swan's >>> > recent paper (https://arxiv.org/abs/1808.00920v3) shows that this is >>> > not even possible! >>> > >>> > Another approach would be to have weak Glue types that don't strictly >>> > reduce to A when phi is true, but this causes problems for the >>> > composition in the universe and would be weird for cubical type >>> > theory... >>> > >>> > In light of Swan's negative results I think we need a completely new >>> > approach if we ever hope to solve this problem. Luckily for you Andrew >>> > Swan is starting as a postdoc over in Baker Hall in October, so he can >>> > explain his counterexamples to you in person. >>> > >>> > Best, >>> > Anders >>> > >>> > On Sun, Sep 15, 2019 at 7:57 AM Jasper Hugunin >>> > <jasperh@cs.washington.edu> wrote: >>> > > >>> > > Offline, Carlo Angiuli showed me that the difficulty was in part 1, because of a subtlety I had been forgetting. >>> > > >>> > > Since types are *Kan* cubical sets, we need that the Kan operations agree as well as the sets. >>> > > So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, compGlue) = (A, compA), and getting that the Kan operations to agree was/is difficult. >>> > > (Now that I know what the answer is, it is clear that this was already explained in the initial discussion.) >>> > > >>> > > Humbly, >>> > > - Jasper Hugunin >>> > > >>> > > On Fri, Sep 13, 2019 at 2:10 AM Jasper Hugunin <jasperh@cs.washington.edu> wrote: >>> > >> >>> > >> Hello all, >>> > >> >>> > >> I've been trying to understand better why composition for the universe does not satisfy regularity. >>> > >> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts: >>> > >> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself) >>> > >> 2. That equiv^i (refl A) reduces to equivRefl A >>> > >> I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument. >>> > >> >>> > >> Context: >>> > >> I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly. >>> > >> If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in this thread on the HoTT mailing list, the definition of composition for the universe was found to not satisfy regularity. >>> > >> I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in the CCHM paper (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything). >>> > >> >>> > >> Best regards, >>> > >> - Jasper Hugunin >>> > > >>> > > -- >>> > > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. >>> > > To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. >>> > > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com. >>> > >>> > -- >>> > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. >>> > To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. >>> > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com. >>> > -- > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. > To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8E03C3BMEwi-T4qjet4EbCgnePhR3Ffa1MepxNmtZoUA%40mail.gmail.com. -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAMWCpp%3DEMvH%2BXtRn7AfyjRDjmiwxfML2JQqKyPjXAhM%2BM2vcjw%40mail.gmail.com. ^ permalink raw reply [flat|nested] 13+ messages in thread

*2019-09-18 12:16 ` Anders MortbergRe: [HoTT] A question about the problem with regularity in CCHM cubical type theory@ 2019-09-18 12:52 ` Thierry Coquand0 siblings, 0 replies; 13+ messages in thread From: Thierry Coquand @ 2019-09-18 12:52 UTC (permalink / raw) To: Anders Mortberg;+Cc:Jasper Hugunin, Licata, Dan, HomotopyTypeTheory [-- Attachment #1: Type: text/plain, Size: 24266 bytes --] Indeed, one can find traces of this in the note http://www.cse.chalmers.se/~coquand/compv1.pdf Thierry PS: The “glueing” operation was then introduced only as a computational way to transform an equivalence to a path and one needed another composition for the universe to get regularity. One insight was the reduction of “filling” to “composition” but this was using regularity. As explained in the thread, there was a bug with composition in the universe, found by Carlo, Dan and Bob. After this problem was made explicit, one could find another way (a little more complex) to reduce filling to composition which does not use regularity. It was then realised (by Anders and Simon) that “glueing” was already enough to get univalence. This was explained later by understanding that this “glueing” operation actually expresses the “equivalence extension property” (used in the simplicial set model for proving univalence). This was helped by the introduction of the notion of “partial elements” which also simplified the presentation and made proof checking much easier. We could recover a model but without Path = Id. It was really surprising, at least for me, that one could still define Id from Path (using Andrew Swan’s method). On 18 Sep 2019, at 14:16, Anders Mortberg <andersmortberg@gmail.com<mailto:andersmortberg@gmail.com>> wrote: I tried to recall what the problem with regularity for comp for universes was in CCHM and here's what I've come up with. As pointed out by Dan and Jasper we need an equation like "Glue [ phi |-> (A, reflEquiv) ] A = A" to get a regular version of the reduction of comp for U to comp for Glue. This indeed seems very unnatural and it is not what we tried. What we instead did in the old buggy version of cubicaltt was to add new hcomp_U values to CCHM for compositions of types and reduce comp in U to one of these: comp^i U [phi -> A] A0 = hcomp^i_U [phi -> A] A0 For regularity we need the following condition on hcomp_U (where "i # A" means that i does not occur in A, i.e. if we're only attaching degenerate sides to A0): if i # A then hcomp^i_U [phi -> A] A0 = A0 The problem is then to define comp^j (hcomp^i_U [phi -> A] A0) [psi -> B] B0 such that it satisfies the standard equations for comp/hcomp_U and regularity. There are in particular two regularity conditions that we need to take into account: 1. if j # (hcomp^i_U [phi -> A] A0) and j # B then comp^j (hcomp^i_U [phi -> A] A0) [psi -> B] B0 = B0 2. if i # A then comp^j (hcomp^i_U [phi -> A] A0) [psi -> B] B0 = comp^j A0 [psi -> B] B0 We achieved 1 by essentially doing the same algorithm as for comp Glue (which Jasper pointed out is indeed regular), but this only satisfied the equation comp^j (hcomp^i_U [] A0) [psi -> B] B0 = comp^j A0 [psi -> B] B0 and not the full version of 2. I think this is what Dan and the others found and reported to us, at least that's how I read the old thread. It might be possible to get 2 and not 1, but I would be very surprised if we can get both 1 and 2 by just adapting the algorithms. Indeed, in light of Andrew's negative results I would expect substantial changes and some new ideas to be necessary in order to give a constructive model of univalent type theory where Path = Id. -- Anders On Mon, Sep 16, 2019 at 10:17 PM Jasper Hugunin <jasperh@cs.washington.edu<mailto:jasperh@cs.washington.edu>> wrote: I agree with the problem of using Glue types for the composition operation in the universe. You could imagine an extra equation that Glue [ phi |-> (A, reflEquiv) ] A = A, but this is somehow unnatural. However, it is what I was postulating in step 1 of the initial message of this thread. (You then need comp Glue to respect this equation, which appears impossible.) The way to get around it is, in my opinion, to add a separate type former Box^i [ phi |-> T ] A for phi |- A = T(i1), satisfying the laws phi |- Box^i [ phi |-> T ] A = T(i0) and regularity: Box^i [ phi |-> A ] A = A. You then need comp Box to respect Box^i [ phi |-> A ] A = A, and this is also apparently not possible in CCHM, but you now have the extra information that A is a line of types. (Using Box to turn an equivalence into a line of types in the definition of comp Box is circular.) I've developed a notion of (regular) n-dimensional composition, which I think might suffice to complete the argument. If you call a notion of Box that satisfies Box^i [ phi |-> A ] A = A "regular Box's", then the problem can be reduced to saying that to give regular 1-dimensional composition of regular 1-dimensional boxes, you need some sort of "(doubly) regular 2-dimensional composition" for A, and in CCHM such we can only get this "2-dimensional composition" which is regular in one direction or the other. Of course (I haven't actually checked, but my intuition says that), once you have 2-dimensional composition you will need n-dimensional composition, and then hopefully regular (n+m)-dimensional composition for A will suffice to define regular n-dimensional composition of regular n-dimensional Box's. Below I'll put an explanation of my idea of regular n-dimensional composition (returning an (n-1)-dimensional cube), since it feels unfair to say "I know how to do this" and hide "how to do this". Unfortunately, it is quite complex; read at your own peril. I don't yet know how to intelligibly describe n-dimensional composition for Glue and Box. For now I'll just say that they should be essentially the same as in the 1-dimensional case, but with extra faces in the equiv and final hcomp steps corresponding to faces in the result. =============== In CCHM, the basic Kan operation is (comp^i A [ phi |-> a ] a0 : A(i1) [ phi |-> a(i1) ]) for i |- A with phi, i |- a : A and a0 : A(i0) [ phi |-> a(i0) ]. Regularity for this operation means that if A and a are independent of i, then comp^i A [ phi |-> a ] a0 = a0. We have regular composition for Glue types, but we don't have comp^i (Glue [ phi |-> (A, equivRefl) ] A) = comp^i A. Simplifying things a little, we can take hcom^i U [ phi |-> T ] A = Box^i [ phi |-> T(i := ~ i) ] A to be a new type former, and give that a regular composition operation. Here the thing blocking us from getting comp^i (Box^j [ phi |-> A ] A) = comp^i A is that, given i, j |- T with phi, i, j |- t : T and t0 : T(i0)(j0)[ phi |-> t(i0)(j0) ], we need a Path T(i1)(j1) (comp^i T(j1) [ phi |-> t(j1) ] (comp^j T(i0) [ phi |-> t(i0) ] t0)) (comp^j T(i1) [ phi |-> t(i1) ] (comp^i T(j0) [ phi |-> t(j0) ] t0)) which is refl if T is degenerate in i OR j. This path plays the role that pres does in composition for Glue. (I will write (i o j) for composition over j then over i, and (i = j) for composition over the diagonal (i = j). Then we want a path from (i o j) to (j o i) which is degenerate if T is degenerate in i OR j. We can't construct such a doubly regular path, but we can postulate it as a new operation our types have to have, as a sort of regular composition over two dimensions simultaneously. Write (i ?'[a] j) for this, where a gives the location in the path. However, my intuition tells me that while this two-dimensional regular composition may be preserved by all the usual type formers, optimistically including Glue and Box, because the two-dimensional composition for Box will have to satisfy an additional law comp2^i^j (Box [ phi |-> A ] A) = comp2^i^j A, we will end up needing some sort of three-dimensional analogue. Once we need dimensions 1 and 2, we will almost certainly need dimension n. But what should the type of three dimensional regular composition be? There are six ways to compose along the edges of a cube, forming a hexagon that we wan't to fill, but hexagons don't fit nicely into cubical type theory. Here, we remember that there is one more way to compose across a square: along the diagonal (comp^k T(i,j:=k) [ phi |-> t(i,j:=k) ] t0), which agrees with composing either right then up or up then right when T is degenerate in i or j (with regularity). Allowing diagonals, for each square we can give a path from the diagonal to going up then right, with swapping i and j giving a path to going right then up. Then if both of these are degenerate when T is degenerate in i or j, their composition is also, so we recover a path between (i o j) and (j o i). And this formulation can be extended to higher dimensions straightforwardly. For each n-cube i_1, ..., i_n |- A, we have an n-dimensional regular composition operation which is a (n-1)-dimensional cube. Consider notation (i_1 ?[j_1] i_2 ?[j_2] ... ?[j_n-1] i_n) This is supposed to represent composition in an n-cube indexed by the i's, where our position in the resulting (n-1)-cube is given by the j's. We have to describe the faces of this cube, which we describe by saying that ?[0] reduces to = and ?[1] reduces to o. Thus for 2-dimensional A, we have a line (i = j) --- (i ?[a] j) --- (i o j), and for three dimensional A, we have a square with four faces (i = j ?[a_2] k), (i o j ?[a_2] k), (i ?[a1] j = k) (i ?[a1] j o k), relating the four corners given by coercing over i then j then k, coercing over i then j and k simultaneously, coercing over i and j simultaneously then coercing over k, and coercing over i, j, and k simultaneously. The point is that this gives a well-defined notion of cube. We also have to define the regularity condition: what happens when A, a are degenerate in i_k? We require that (i_1 ... i_k-1 ?[j_k-1] i_k ?[j_k] i_k+1 ... i_n) is equal to (i_1 ... i_k-1 ?[j_k-1 v j_k] i_k+1 ... i_n), treating j_0 = j_n = 1. Extending this to = and o, if A, a are degenerate in i, then (i = j) and (i o j) reduce to (j). On a two-dimensional cube, this says that (i ?[a] j) reduces to (j) when A, a are degenerate in i, and to (i) when A, a are degenerate in j. (That this is all coherent is obvious to me, but I have no idea how to explain it well) This all gives a notion of n-dimensional regular composition, which takes an n-cube type A and partial term phi, i1, ..., in |- a and a base point a0 : A(i_k := 0)[ phi |-> a(i_k := 0) ] and returns an (n-1)-cube in A(i_k := 1) [ phi |-> everywhere a(i_k := 1) ]. There are three classes of equations that this has to satisfy, two for the face maps j_k = 0 and j_k = 1 in the output, and one for when A, a are degenerate in i_k. In the one-dimensional case, this is the same as the specification of the usual regular comp. Considering j_k to be formally extended with j_0 = j_n = 1, we get a "zero-dimensional" composition operation, which should be taken to be the identity. (I have no idea what it would mean to let j_0 and j_n vary) I am reasonably confident that this operation is closed under usual type formers (Pi, Sg, Path, ...) by essentially the same argument as for 1-dimensional comp. I think I have worked out how to give a regular n-dimensional composition operation for Glue, by essentially the same argument as in CCHM, but with additional faces for j_k = 1 in the equiv and final hcomp steps. In this setting, we want Box to also be m-dimensional: j_1 ... j_n-1 |- Box^i1...^im _{j_1}..._{j_n-1} [ phi |-> T ] A for phi, i1, ..., im |- T, with phi |- A = T(i_k := 1). I think I have worked out how to give a regular n-dimensional composition operation for m-dimensional Box, using essentially the same argument as for Glue, but replacing pres with the composition of two paths given by (m+n)-dimensional regular composition. To use Box as the regular n-dimensional composition operation for the universe, we need that (Box, comp Box) respects the equations for when j_k = 0, j_k = 1, or T is independent of j. My hope is that, as in the (1, 1) dimensional case, using (m+n)-dimensional regular composition for pres will make this work. I have sketched on paper that composition for Glue and Box are regular, but that is already pushing the limits of my confidence in paper calculations. Checking that comp Box respects the equations that it needs to is another layer more complex, and I haven't managed to do so on paper. However, by analogy with the (1, 1) dimensional case, I am hopeful. On Mon, Sep 16, 2019 at 3:01 PM Licata, Dan <dlicata@wesleyan.edu<mailto:dlicata@wesleyan.edu>> wrote: Wow! I read that pretty closely and couldn’t find a problem. That is surprising to me. Will look more later. What I was saying about fill for the aligning algorithm is also wrong — I wasn’t thinking that the type of the filling was also degenerate, but of course it is here. So that might work too. However, even if there can be a universe of regular types that is closed under glue types, there’s still a problem with using those glue types to show that that universe is itself regularly fibrant, I think? If you define comp U [phi -> i.T] B to be Glue [phi -> T(1),...] B then no matter how nice the equivalence is (eg the identity) when i doesn’t occur in T, the type will not equal B — that would be an extra equation about the Glue type constructor itself. Does that seem right? -Dan On Sep 16, 2019, at 1:09 PM, Jasper Hugunin <jasperh@cs.washington.edu<mailto:jasperh@cs.washington.edu>> wrote: Hi Dan, Of course. I'm thinking primarily of composition for Glue given in the CCHM paper you linked, reproduced below. As you know, the single potential issue is that we need pres of a degenerate filling problem and function to be reflexivity. I claim that this holds by regularity of composition in T and A, partly as a consequence of the fact that regularity of composition implies regularity of filling (that fill of a degenerate system is refl), which certainly holds for fill defined by connections (and I believe also holds for fill as defined in ABCFHL). (a) Given i |- B = Glue [ phi |-> (T, f) ] A, with psi, i |- b : B and b0 : B(i0)[ psi |-> b(i0) ], we want to compute b1 = comp^i B [ psi |-> b ] b0 : B(i1)[ psi |-> b(i1) ]. We set a := unglue b and a0 := unglue b0. Set delta := forall i. phi. Then we take: a1' := comp^i A [ psi |-> a ] a0 delta |- t1' := comp^i T [ psi |-> b ] b0 delta |- omega := pres^i f [ psi |-> b ] b0 phi(i1) |- (t, alpha) := equiv f(i1) [ delta |-> (t1', omega), psi |-> (b(i1), refl a1') ] a1' a1 := hcomp^j A(i1) [ phi(i1) |-> alpha j, psi |-> a(i1) ] a1' (note that in the regular setting the psi face is redundant) b1 := glue [ phi(i1) |-> t1 ] a1 With given i |- f : T -> A, with psi, i |- b : T and b0 : T(i0)[ psi |-> b(i0) ], we define pres^i f [ psi |-> b ] b0 = <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> b ] b0) ] (f(i0) b0). (b) Now consider the regular case, where phi, T, f, and A are independent of i. We want that b1 = b0. We have that a is independent of i, and delta = phi. First consider delta (= phi) |- pres^i f [ psi |-> b ] b0. (This is the explanation of your first dash) Note that if comp^i A is regular, then fill^i A [ psi |-> b ] b0 = b This is <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> t ] t0) ] (f t0) = <j> comp^i A [ psi |-> f b, j = 1 |-> f t0 ] (f t0) = <j> f t0. Thus pres of a degenerate filling problem and function is reflexivity. Going back to composition of Glue, a1' = a0 phi |- t1' = b0 phi |- omega = refl (f b0) phi |- (t1, alpha) = (t1', omega) (since delta = phi, so we end up in the delta face of equiv) a1 = a1' (the only dependence on j is via (alpha j), but alpha = omega = refl, so this filling problem is degenerate) b1 = glue [ phi |-> t1 ] a1 = glue [ phi |-> b0 ] a0 = glue [ phi |-> b0 ] (unglue b0) = b0 (by eta, see Figure 4 in CCHM) Thus this algorithm for composition of Glue is regular. Other algorithms, such as the one in ABCFHL, may not be, but I am prone to believe that there exist regular algorithms in other settings including Orton-Pitts and Cartesian cubes. Best regards, - Jasper Hugunin On Mon, Sep 16, 2019 at 12:18 PM Licata, Dan <dlicata@wesleyan.edu<mailto:dlicata@wesleyan.edu>> wrote: Hi Jasper, It would help me follow the discussion if you could say a little more about (a) which version of composition for Glue exactly you mean (because there is at least the one in the CCHM paper and the “aligned” one from Orton-Pitts, which are intensionally different, as well as other possible variations), and (b) include some of your reasoning for why you think things are regular, to make it easier for me and others to reconstruct. My current understanding is that - For CCHM proper https://arxiv.org/pdf/1611.02108.pdf the potential issue is with the ‘pres’ path omega, which via the equiv operation ends up in alpha, so the system in a1 may not be degenerate even if the input is. Do you think this does work out to be degenerate? - For the current version of ABCFHL https://github.com/dlicata335/cart-cube/blob/master/cart-cube.pdf which uses aligning “all the way at the outside”, an issue is with the adjust_com operation on page 20, which is later used for aligning (in that case beta is (forall i phi)). The potential issue is that adjust_com uses a *filler*, not just a composition from 0 to 1, so even if t doesn’t depend on z, the filling does, and the outer com won’t cancel. In CCHM, filling is defined using connections, so it’s a little different, but I think there still has to be a dependence on z for it to even type check — it should come up because of the connection term that is substituted into the type of the composition problem. So I’d guess there is still a problem in the aligned algorithm for CCHM. However, it would be great if this is wrong and something does work! -Dan On Sep 15, 2019, at 10:18 PM, Jasper Hugunin <jasperh@cs.washington.edu<mailto:jasperh@cs.washington.edu>> wrote: This doesn't seem right; as far as I can tell, composition for Glue types in CCHM preserves regularity and reduces to composition in A on phi. - Jasper Hugunin On Sun, Sep 15, 2019 at 3:28 AM Anders Mortberg <anders.mortberg@math.su.se<mailto:anders.mortberg@math.su.se>> wrote: Hi Jasper, Indeed, the problem is to construct an algorithm for comp (or even coe/transp) for Glue that reduces to the one of A when phi is true while still preserving regularity. It was pointed out independently by Sattler and Orton around 2016 that one can factor out this step in our algorithm in a separate lemma that is now called "alignment". This is Thm 6.13 in Orton-Pitts and discussed in a paragraph in the end of section 2.11 of ABCFHL. Unless I'm misremembering this is exactly where regularity for comp for Glue types break down. In this step we do an additional comp/hcomp that inserts an additional forall i. phi face making the comp/coe irregular. One could imagine there being a way to modify the algorithm to avoid this, maybe by inlining the alignment step... But despite considerable efforts no one has been able to figure this out and I think Swan's recent paper (https://arxiv.org/abs/1808.00920v3) shows that this is not even possible! Another approach would be to have weak Glue types that don't strictly reduce to A when phi is true, but this causes problems for the composition in the universe and would be weird for cubical type theory... In light of Swan's negative results I think we need a completely new approach if we ever hope to solve this problem. Luckily for you Andrew Swan is starting as a postdoc over in Baker Hall in October, so he can explain his counterexamples to you in person. Best, Anders On Sun, Sep 15, 2019 at 7:57 AM Jasper Hugunin <jasperh@cs.washington.edu<mailto:jasperh@cs.washington.edu>> wrote: Offline, Carlo Angiuli showed me that the difficulty was in part 1, because of a subtlety I had been forgetting. Since types are *Kan* cubical sets, we need that the Kan operations agree as well as the sets. So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, compGlue) = (A, compA), and getting that the Kan operations to agree was/is difficult. (Now that I know what the answer is, it is clear that this was already explained in the initial discussion.) Humbly, - Jasper Hugunin On Fri, Sep 13, 2019 at 2:10 AM Jasper Hugunin <jasperh@cs.washington.edu<mailto:jasperh@cs.washington.edu>> wrote: Hello all, I've been trying to understand better why composition for the universe does not satisfy regularity. Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts: 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself) 2. That equiv^i (refl A) reduces to equivRefl A I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument. Context: I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly. If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in this thread on the HoTT mailing list, the definition of composition for the universe was found to not satisfy regularity. I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in the CCHM paper (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything). Best regards, - Jasper Hugunin -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com<mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com>. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com. -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com<mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com>. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com. -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com<mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com>. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8E03C3BMEwi-T4qjet4EbCgnePhR3Ffa1MepxNmtZoUA%40mail.gmail.com. -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com<mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com>. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAMWCpp%3DEMvH%2BXtRn7AfyjRDjmiwxfML2JQqKyPjXAhM%2BM2vcjw%40mail.gmail.com. -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/C1FA3BE5-6469-47F7-9049-914A6AFC68BA%40chalmers.se. [-- Attachment #2: Type: text/html, Size: 31258 bytes --] <html> <head> <meta http-equiv="Content-Type" content="text/html; charset=utf-8"> </head> <body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""> Indeed, one can find traces of this in the note <div class=""><br class=""> </div> <div class=""><a href="http://www.cse.chalmers.se/~coquand/compv1.pdf" class="">http://www.cse.chalmers.se/~coquand/compv1.pdf</a></div> <div class=""><br class=""> </div> <div class=""> Thierry</div> <div class=""><br class=""> </div> <div class=""><br class=""> </div> <div class=""><br class=""> </div> <div class="">PS: The “glueing” operation was then introduced only as a computational way to transform an </div> <div class="">equivalence to a path and one needed another composition for the universe to get regularity. One insight was the</div> <div class="">reduction of “filling” to “composition” but this was using regularity.</div> <div class="">As explained in the thread, there was a bug with composition in the universe, found by Carlo, Dan</div> <div class="">and Bob. After this problem was made explicit, one could find another way (a little more</div> <div class="">complex) to reduce filling to composition which does not use regularity.</div> <div class="">It was then realised (by Anders and Simon) that “glueing” was already enough to get univalence.</div> <div class="">This was explained later by understanding that this “glueing” operation actually</div> <div class="">expresses the “equivalence extension property” (used in the simplicial set model</div> <div class="">for proving univalence). This was helped by the introduction of the notion of “partial elements” </div> <div class="">which also simplified the presentation and made proof checking much easier. We could recover a model</div> <div class="">but without Path = Id. It was really surprising, at least for me, that one could still define Id</div> <div class="">from Path (using Andrew Swan’s method).</div> <div class=""><br class=""> </div> <div class=""><br class=""> </div> <div class=""><br class=""> </div> <div class=""><br class=""> <div><br class=""> <blockquote type="cite" class=""> <div class="">On 18 Sep 2019, at 14:16, Anders Mortberg <<a href="mailto:andersmortberg@gmail.com" class="">andersmortberg@gmail.com</a>> wrote:</div> <br class="Apple-interchange-newline"> <div class=""> <div class="">I tried to recall what the problem with regularity for comp for<br class=""> universes was in CCHM and here's what I've come up with. As pointed<br class=""> out by Dan and Jasper we need an equation like "Glue [ phi |-> (A,<br class=""> reflEquiv) ] A = A" to get a regular version of the reduction of comp<br class=""> for U to comp for Glue. This indeed seems very unnatural and it is not<br class=""> what we tried.<br class=""> <br class=""> What we instead did in the old buggy version of cubicaltt was to add<br class=""> new hcomp_U values to CCHM for compositions of types and reduce comp<br class=""> in U to one of these:<br class=""> <br class=""> comp^i U [phi -> A] A0 = hcomp^i_U [phi -> A] A0<br class=""> <br class=""> For regularity we need the following condition on hcomp_U (where "i #<br class=""> A" means that i does not occur in A, i.e. if we're only attaching<br class=""> degenerate sides to A0):<br class=""> <br class=""> if i # A then hcomp^i_U [phi -> A] A0 = A0<br class=""> <br class=""> <br class=""> The problem is then to define<br class=""> <br class=""> comp^j (hcomp^i_U [phi -> A] A0) [psi -> B] B0<br class=""> <br class=""> such that it satisfies the standard equations for comp/hcomp_U and<br class=""> regularity. There are in particular two regularity conditions that we<br class=""> need to take into account:<br class=""> <br class=""> 1. if j # (hcomp^i_U [phi -> A] A0) and j # B then<br class=""> <br class=""> comp^j (hcomp^i_U [phi -> A] A0) [psi -> B] B0 = B0<br class=""> <br class=""> 2. if i # A then<br class=""> <br class=""> comp^j (hcomp^i_U [phi -> A] A0) [psi -> B] B0 = comp^j A0 [psi -> B] B0<br class=""> <br class=""> <br class=""> We achieved 1 by essentially doing the same algorithm as for comp Glue<br class=""> (which Jasper pointed out is indeed regular), but this only satisfied<br class=""> the equation<br class=""> <br class=""> comp^j (hcomp^i_U [] A0) [psi -> B] B0 = comp^j A0 [psi -> B] B0<br class=""> <br class=""> and not the full version of 2. I think this is what Dan and the others<br class=""> found and reported to us, at least that's how I read the old thread.<br class=""> It might be possible to get 2 and not 1, but I would be very surprised<br class=""> if we can get both 1 and 2 by just adapting the algorithms. Indeed, in<br class=""> light of Andrew's negative results I would expect substantial changes<br class=""> and some new ideas to be necessary in order to give a constructive<br class=""> model of univalent type theory where Path = Id.<br class=""> <br class=""> --<br class=""> Anders<br class=""> <br class=""> <br class=""> <br class=""> <br class=""> <br class=""> <br class=""> On Mon, Sep 16, 2019 at 10:17 PM Jasper Hugunin<br class=""> <<a href="mailto:jasperh@cs.washington.edu" class="">jasperh@cs.washington.edu</a>> wrote:<br class=""> <blockquote type="cite" class=""><br class=""> I agree with the problem of using Glue types for the composition operation in the universe.<br class=""> You could imagine an extra equation that Glue [ phi |-> (A, reflEquiv) ] A = A, but this is somehow unnatural.<br class=""> However, it is what I was postulating in step 1 of the initial message of this thread.<br class=""> (You then need comp Glue to respect this equation, which appears impossible.)<br class=""> <br class=""> The way to get around it is, in my opinion, to add a separate type former Box^i [ phi |-> T ] A for phi |- A = T(i1), satisfying the laws phi |- Box^i [ phi |-> T ] A = T(i0) and regularity: Box^i [ phi |-> A ] A = A.<br class=""> You then need comp Box to respect Box^i [ phi |-> A ] A = A, and this is also apparently not possible in CCHM, but you now have the extra information that A is a line of types. (Using Box to turn an equivalence into a line of types in the definition of comp Box is circular.)<br class=""> <br class=""> I've developed a notion of (regular) n-dimensional composition, which I think might suffice to complete the argument.<br class=""> If you call a notion of Box that satisfies Box^i [ phi |-> A ] A = A "regular Box's", then the problem can be reduced to saying that to give regular 1-dimensional composition of regular 1-dimensional boxes, you need some sort of "(doubly) regular 2-dimensional composition" for A, and in CCHM such we can only get this "2-dimensional composition" which is regular in one direction or the other.<br class=""> Of course (I haven't actually checked, but my intuition says that), once you have 2-dimensional composition you will need n-dimensional composition, and then hopefully regular (n+m)-dimensional composition for A will suffice to define regular n-dimensional composition of regular n-dimensional Box's.<br class=""> <br class=""> Below I'll put an explanation of my idea of regular n-dimensional composition (returning an (n-1)-dimensional cube), since it feels unfair to say "I know how to do this" and hide "how to do this".<br class=""> Unfortunately, it is quite complex; read at your own peril.<br class=""> <br class=""> I don't yet know how to intelligibly describe n-dimensional composition for Glue and Box.<br class=""> For now I'll just say that they should be essentially the same as in the 1-dimensional case, but with extra faces in the equiv and final hcomp steps corresponding to faces in the result.<br class=""> <br class=""> ===============<br class=""> <br class=""> In CCHM, the basic Kan operation is (comp^i A [ phi |-> a ] a0 : A(i1) [ phi |-> a(i1) ]) for i |- A with phi, i |- a : A and a0 : A(i0) [ phi |-> a(i0) ].<br class=""> Regularity for this operation means that if A and a are independent of i, then comp^i A [ phi |-> a ] a0 = a0.<br class=""> We have regular composition for Glue types, but we don't have comp^i (Glue [ phi |-> (A, equivRefl) ] A) = comp^i A.<br class=""> Simplifying things a little, we can take hcom^i U [ phi |-> T ] A = Box^i [ phi |-> T(i := ~ i) ] A to be a new type former, and give that a regular composition operation.<br class=""> Here the thing blocking us from getting comp^i (Box^j [ phi |-> A ] A) = comp^i A is that, given i, j |- T with phi, i, j |- t : T and t0 : T(i0)(j0)[ phi |-> t(i0)(j0) ],<br class=""> we need a Path T(i1)(j1) (comp^i T(j1) [ phi |-> t(j1) ] (comp^j T(i0) [ phi |-> t(i0) ] t0)) (comp^j T(i1) [ phi |-> t(i1) ] (comp^i T(j0) [ phi |-> t(j0) ] t0)) which is refl if T is degenerate in i OR j.<br class=""> This path plays the role that pres does in composition for Glue.<br class=""> (I will write (i o j) for composition over j then over i, and (i = j) for composition over the diagonal (i = j). Then we want a path from (i o j) to (j o i) which is degenerate if T is degenerate in i OR j.<br class=""> <br class=""> We can't construct such a doubly regular path, but we can postulate it as a new operation our types have to have, as a sort of regular composition over two dimensions simultaneously. Write (i ?'[a] j) for this, where a gives the location in the path.<br class=""> However, my intuition tells me that while this two-dimensional regular composition may be preserved by all the usual type formers, optimistically including Glue and Box, because the two-dimensional composition for Box will have to satisfy an additional law comp2^i^j (Box [ phi |-> A ] A) = comp2^i^j A, we will end up needing some sort of three-dimensional analogue.<br class=""> Once we need dimensions 1 and 2, we will almost certainly need dimension n.<br class=""> <br class=""> But what should the type of three dimensional regular composition be? There are six ways to compose along the edges of a cube, forming a hexagon that we wan't to fill, but hexagons don't fit nicely into cubical type theory.<br class=""> Here, we remember that there is one more way to compose across a square: along the diagonal (comp^k T(i,j:=k) [ phi |-> t(i,j:=k) ] t0), which agrees with composing either right then up or up then right when T is degenerate in i or j (with regularity).<br class=""> Allowing diagonals, for each square we can give a path from the diagonal to going up then right, with swapping i and j giving a path to going right then up. Then if both of these are degenerate when T is degenerate in i or j, their composition is also, so we recover a path between (i o j) and (j o i). And this formulation can be extended to higher dimensions straightforwardly.<br class=""> <br class=""> For each n-cube i_1, ..., i_n |- A, we have an n-dimensional regular composition operation which is a (n-1)-dimensional cube. Consider notation (i_1 ?[j_1] i_2 ?[j_2] ... ?[j_n-1] i_n) This is supposed to represent composition in an n-cube indexed by the i's, where our position in the resulting (n-1)-cube is given by the j's. We have to describe the faces of this cube, which we describe by saying that ?[0] reduces to = and ?[1] reduces to o.<br class=""> Thus for 2-dimensional A, we have a line (i = j) --- (i ?[a] j) --- (i o j), and for three dimensional A, we have a square with four faces (i = j ?[a_2] k), (i o j ?[a_2] k), (i ?[a1] j = k) (i ?[a1] j o k), relating the four corners given by coercing over i then j then k, coercing over i then j and k simultaneously, coercing over i and j simultaneously then coercing over k, and coercing over i, j, and k simultaneously.<br class=""> The point is that this gives a well-defined notion of cube.<br class=""> We also have to define the regularity condition: what happens when A, a are degenerate in i_k? We require that (i_1 ... i_k-1 ?[j_k-1] i_k ?[j_k] i_k+1 ... i_n) is equal to (i_1 ... i_k-1 ?[j_k-1 v j_k] i_k+1 ... i_n), treating j_0 = j_n = 1.<br class=""> Extending this to = and o, if A, a are degenerate in i, then (i = j) and (i o j) reduce to (j).<br class=""> On a two-dimensional cube, this says that (i ?[a] j) reduces to (j) when A, a are degenerate in i, and to (i) when A, a are degenerate in j.<br class=""> (That this is all coherent is obvious to me, but I have no idea how to explain it well)<br class=""> <br class=""> This all gives a notion of n-dimensional regular composition, which takes an n-cube type A and partial term phi, i1, ..., in |- a and a base point a0 : A(i_k := 0)[ phi |-> a(i_k := 0) ] and returns an (n-1)-cube in A(i_k := 1) [ phi |-> everywhere a(i_k := 1) ].<br class=""> There are three classes of equations that this has to satisfy, two for the face maps j_k = 0 and j_k = 1 in the output, and one for when A, a are degenerate in i_k.<br class=""> In the one-dimensional case, this is the same as the specification of the usual regular comp.<br class=""> Considering j_k to be formally extended with j_0 = j_n = 1, we get a "zero-dimensional" composition operation, which should be taken to be the identity. (I have no idea what it would mean to let j_0 and j_n vary)<br class=""> I am reasonably confident that this operation is closed under usual type formers (Pi, Sg, Path, ...) by essentially the same argument as for 1-dimensional comp.<br class=""> I think I have worked out how to give a regular n-dimensional composition operation for Glue, by essentially the same argument as in CCHM, but with additional faces for j_k = 1 in the equiv and final hcomp steps.<br class=""> <br class=""> In this setting, we want Box to also be m-dimensional: j_1 ... j_n-1 |- Box^i1...^im _{j_1}..._{j_n-1} [ phi |-> T ] A for phi, i1, ..., im |- T, with phi |- A = T(i_k := 1).<br class=""> I think I have worked out how to give a regular n-dimensional composition operation for m-dimensional Box, using essentially the same argument as for Glue, but replacing pres with the composition of two paths given by (m+n)-dimensional regular composition.<br class=""> To use Box as the regular n-dimensional composition operation for the universe, we need that (Box, comp Box) respects the equations for when j_k = 0, j_k = 1, or T is independent of j.<br class=""> My hope is that, as in the (1, 1) dimensional case, using (m+n)-dimensional regular composition for pres will make this work.<br class=""> <br class=""> I have sketched on paper that composition for Glue and Box are regular, but that is already pushing the limits of my confidence in paper calculations.<br class=""> Checking that comp Box respects the equations that it needs to is another layer more complex, and I haven't managed to do so on paper.<br class=""> However, by analogy with the (1, 1) dimensional case, I am hopeful.<br class=""> <br class=""> On Mon, Sep 16, 2019 at 3:01 PM Licata, Dan <<a href="mailto:dlicata@wesleyan.edu" class="">dlicata@wesleyan.edu</a>> wrote:<br class=""> <blockquote type="cite" class=""><br class=""> Wow! I read that pretty closely and couldn’t find a problem. That is surprising to me. Will look more later.<br class=""> <br class=""> What I was saying about fill for the aligning algorithm is also wrong — I wasn’t thinking that the type of the filling was also degenerate, but of course it is here. So that might work too.<br class=""> <br class=""> However, even if there can be a universe of regular types that is closed under glue types, there’s still a problem with using those glue types to show that that universe is itself regularly fibrant, I think? If you define comp U [phi -> i.T] B to be Glue [phi -> T(1),...] B then no matter how nice the equivalence is (eg the identity) when i doesn’t occur in T, the type will not equal B — that would be an extra equation about the Glue type constructor itself. Does that seem right?<br class=""> <br class=""> -Dan<br class=""> <br class=""> On Sep 16, 2019, at 1:09 PM, Jasper Hugunin <<a href="mailto:jasperh@cs.washington.edu" class="">jasperh@cs.washington.edu</a>> wrote:<br class=""> <br class=""> Hi Dan,<br class=""> <br class=""> Of course. I'm thinking primarily of composition for Glue given in the CCHM paper you linked, reproduced below.<br class=""> As you know, the single potential issue is that we need pres of a degenerate filling problem and function to be reflexivity. I claim that this holds by regularity of composition in T and A, partly as a consequence of the fact that regularity of composition implies regularity of filling (that fill of a degenerate system is refl), which certainly holds for fill defined by connections (and I believe also holds for fill as defined in ABCFHL).<br class=""> <br class=""> (a)<br class=""> Given i |- B = Glue [ phi |-> (T, f) ] A, with psi, i |- b : B and b0 : B(i0)[ psi |-> b(i0) ], we want to compute b1 = comp^i B [ psi |-> b ] b0 : B(i1)[ psi |-> b(i1) ].<br class=""> We set a := unglue b and a0 := unglue b0.<br class=""> Set delta := forall i. phi.<br class=""> Then we take:<br class=""> a1' := comp^i A [ psi |-> a ] a0<br class=""> delta |- t1' := comp^i T [ psi |-> b ] b0<br class=""> delta |- omega := pres^i f [ psi |-> b ] b0<br class=""> phi(i1) |- (t, alpha) := equiv f(i1) [ delta |-> (t1', omega), psi |-> (b(i1), refl a1') ] a1'<br class=""> a1 := hcomp^j A(i1) [ phi(i1) |-> alpha j, psi |-> a(i1) ] a1' (note that in the regular setting the psi face is redundant)<br class=""> b1 := glue [ phi(i1) |-> t1 ] a1<br class=""> <br class=""> With given i |- f : T -> A, with psi, i |- b : T and b0 : T(i0)[ psi |-> b(i0) ], we define<br class=""> pres^i f [ psi |-> b ] b0 = <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> b ] b0) ] (f(i0) b0).<br class=""> <br class=""> (b)<br class=""> Now consider the regular case, where phi, T, f, and A are independent of i. We want that b1 = b0.<br class=""> We have that a is independent of i, and delta = phi.<br class=""> <br class=""> First consider delta (= phi) |- pres^i f [ psi |-> b ] b0. (This is the explanation of your first dash)<br class=""> Note that if comp^i A is regular, then fill^i A [ psi |-> b ] b0 = b<br class=""> This is <j> comp^i A [ psi |-> f b, j = 1 |-> f (fill^i T [ psi |-> t ] t0) ] (f t0) = <j> comp^i A [ psi |-> f b, j = 1 |-> f t0 ] (f t0) = <j> f t0.<br class=""> Thus pres of a degenerate filling problem and function is reflexivity.<br class=""> <br class=""> Going back to composition of Glue,<br class=""> a1' = a0<br class=""> phi |- t1' = b0<br class=""> phi |- omega = refl (f b0)<br class=""> phi |- (t1, alpha) = (t1', omega) (since delta = phi, so we end up in the delta face of equiv)<br class=""> a1 = a1' (the only dependence on j is via (alpha j), but alpha = omega = refl, so this filling problem is degenerate)<br class=""> b1 = glue [ phi |-> t1 ] a1 = glue [ phi |-> b0 ] a0 = glue [ phi |-> b0 ] (unglue b0) = b0 (by eta, see Figure 4 in CCHM)<br class=""> <br class=""> Thus this algorithm for composition of Glue is regular.<br class=""> Other algorithms, such as the one in ABCFHL, may not be, but I am prone to believe that there exist regular algorithms in other settings including Orton-Pitts and Cartesian cubes.<br class=""> <br class=""> Best regards,<br class=""> - Jasper Hugunin<br class=""> <br class=""> On Mon, Sep 16, 2019 at 12:18 PM Licata, Dan <<a href="mailto:dlicata@wesleyan.edu" class="">dlicata@wesleyan.edu</a>> wrote:<br class=""> <blockquote type="cite" class=""><br class=""> Hi Jasper,<br class=""> <br class=""> It would help me follow the discussion if you could say a little more about (a) which version of composition for Glue exactly you mean (because there is at least the one in the CCHM paper and the “aligned” one from Orton-Pitts, which are intensionally different, as well as other possible variations), and (b) include some of your reasoning for why you think things are regular, to make it easier for me and others to reconstruct.<br class=""> <br class=""> My current understanding is that<br class=""> <br class=""> - For CCHM proper <a href="https://arxiv.org/pdf/1611.02108.pdf" class="">https://arxiv.org/pdf/1611.02108.pdf</a> the potential issue is with the ‘pres’ path omega, which via the equiv operation ends up in alpha, so the system in a1 may not be degenerate even if the input is. Do you think this does work out to be degenerate?<br class=""> <br class=""> - For the current version of ABCFHL <a href="https://github.com/dlicata335/cart-cube/blob/master/cart-cube.pdf" class=""> https://github.com/dlicata335/cart-cube/blob/master/cart-cube.pdf</a> which uses aligning “all the way at the outside”, an issue is with the adjust_com operation on page 20, which is later used for aligning (in that case beta is (forall i phi)). The potential issue is that adjust_com uses a *filler*, not just a composition from 0 to 1, so even if t doesn’t depend on z, the filling does, and the outer com won’t cancel. In CCHM, filling is defined using connections, so it’s a little different, but I think there still has to be a dependence on z for it to even type check — it should come up because of the connection term that is substituted into the type of the composition problem. So I’d guess there is still a problem in the aligned algorithm for CCHM.<br class=""> <br class=""> However, it would be great if this is wrong and something does work!<br class=""> <br class=""> -Dan<br class=""> <br class=""> <blockquote type="cite" class="">On Sep 15, 2019, at 10:18 PM, Jasper Hugunin <<a href="mailto:jasperh@cs.washington.edu" class="">jasperh@cs.washington.edu</a>> wrote:<br class=""> <br class=""> This doesn't seem right; as far as I can tell, composition for Glue types in CCHM preserves regularity and reduces to composition in A on phi.<br class=""> <br class=""> - Jasper Hugunin<br class=""> <br class=""> On Sun, Sep 15, 2019 at 3:28 AM Anders Mortberg <<a href="mailto:anders.mortberg@math.su.se" class="">anders.mortberg@math.su.se</a>> wrote:<br class=""> Hi Jasper,<br class=""> <br class=""> Indeed, the problem is to construct an algorithm for comp (or even<br class=""> coe/transp) for Glue that reduces to the one of A when phi is true<br class=""> while still preserving regularity. It was pointed out independently by<br class=""> Sattler and Orton around 2016 that one can factor out this step in our<br class=""> algorithm in a separate lemma that is now called "alignment". This is<br class=""> Thm 6.13 in Orton-Pitts and discussed in a paragraph in the end of<br class=""> section 2.11 of ABCFHL. Unless I'm misremembering this is exactly<br class=""> where regularity for comp for Glue types break down. In this step we<br class=""> do an additional comp/hcomp that inserts an additional forall i. phi<br class=""> face making the comp/coe irregular.<br class=""> <br class=""> One could imagine there being a way to modify the algorithm to avoid<br class=""> this, maybe by inlining the alignment step... But despite considerable<br class=""> efforts no one has been able to figure this out and I think Swan's<br class=""> recent paper (<a href="https://arxiv.org/abs/1808.00920v3" class="">https://arxiv.org/abs/1808.00920v3</a>) shows that this is<br class=""> not even possible!<br class=""> <br class=""> Another approach would be to have weak Glue types that don't strictly<br class=""> reduce to A when phi is true, but this causes problems for the<br class=""> composition in the universe and would be weird for cubical type<br class=""> theory...<br class=""> <br class=""> In light of Swan's negative results I think we need a completely new<br class=""> approach if we ever hope to solve this problem. Luckily for you Andrew<br class=""> Swan is starting as a postdoc over in Baker Hall in October, so he can<br class=""> explain his counterexamples to you in person.<br class=""> <br class=""> Best,<br class=""> Anders<br class=""> <br class=""> On Sun, Sep 15, 2019 at 7:57 AM Jasper Hugunin<br class=""> <<a href="mailto:jasperh@cs.washington.edu" class="">jasperh@cs.washington.edu</a>> wrote:<br class=""> <blockquote type="cite" class=""><br class=""> Offline, Carlo Angiuli showed me that the difficulty was in part 1, because of a subtlety I had been forgetting.<br class=""> <br class=""> Since types are *Kan* cubical sets, we need that the Kan operations agree as well as the sets.<br class=""> So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, compGlue) = (A, compA), and getting that the Kan operations to agree was/is difficult.<br class=""> (Now that I know what the answer is, it is clear that this was already explained in the initial discussion.)<br class=""> <br class=""> Humbly,<br class=""> - Jasper Hugunin<br class=""> <br class=""> On Fri, Sep 13, 2019 at 2:10 AM Jasper Hugunin <<a href="mailto:jasperh@cs.washington.edu" class="">jasperh@cs.washington.edu</a>> wrote:<br class=""> <blockquote type="cite" class=""><br class=""> Hello all,<br class=""> <br class=""> I've been trying to understand better why composition for the universe does not satisfy regularity.<br class=""> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |-> equiv^i E ] A, I would expect regularity to follow from two parts:<br class=""> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself)<br class=""> 2. That equiv^i (refl A) reduces to equivRefl A<br class=""> I'm curious as to which (or both) of these parts was the issue, or if regularity for the universe was supposed to follow from a different argument.<br class=""> <br class=""> Context:<br class=""> I've been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly.<br class=""> If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a "regularity" condition on the composition operation, but as discussed in this thread on the HoTT mailing list, the definition of composition for the universe was found to not satisfy regularity.<br class=""> I don't remember seeing the regularity condition defined anywhere, but my understanding is that it requires that composition in a degenerate line of types, with the system of constraints giving the sides of the box also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in the CCHM paper (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-> equiv^i refl ] A not reducing to anything).<br class=""> <br class=""> Best regards,<br class=""> - Jasper Hugunin<br class=""> </blockquote> <br class=""> --<br class=""> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br class=""> To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com" class="">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br class=""> To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com" class=""> https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com</a>.<br class=""> </blockquote> <br class=""> --<br class=""> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br class=""> To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com" class="">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br class=""> To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com" class=""> https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com</a>.<br class=""> </blockquote> <br class=""> </blockquote> </blockquote> --<br class=""> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br class=""> To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com" class="">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br class=""> To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8E03C3BMEwi-T4qjet4EbCgnePhR3Ffa1MepxNmtZoUA%40mail.gmail.com" class=""> https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8E03C3BMEwi-T4qjet4EbCgnePhR3Ffa1MepxNmtZoUA%40mail.gmail.com</a>.<br class=""> </blockquote> <br class=""> -- <br class=""> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br class=""> To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com" class="">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br class=""> To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAMWCpp%3DEMvH%2BXtRn7AfyjRDjmiwxfML2JQqKyPjXAhM%2BM2vcjw%40mail.gmail.com" class=""> https://groups.google.com/d/msgid/HomotopyTypeTheory/CAMWCpp%3DEMvH%2BXtRn7AfyjRDjmiwxfML2JQqKyPjXAhM%2BM2vcjw%40mail.gmail.com</a>.<br class=""> </div> </div> </blockquote> </div> <br class=""> </div> </body> </html> <p></p> -- <br /> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group.<br /> To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br /> To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/C1FA3BE5-6469-47F7-9049-914A6AFC68BA%40chalmers.se?utm_medium=email&utm_source=footer">https://groups.google.com/d/msgid/HomotopyTypeTheory/C1FA3BE5-6469-47F7-9049-914A6AFC68BA%40chalmers.se</a>.<br /> ^ permalink raw reply [flat|nested] 13+ messages in thread

end of thread, back to indexThread overview:13+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-09-13 6:10 [HoTT] A question about the problem with regularity in CCHM cubical type theory Jasper Hugunin 2019-09-15 5:57 ` [HoTT] " Jasper Hugunin [not found] ` <CAMWCppk4PWzfZ1HKNLMdAZ=RBC-ARxtJXR8okvwO3raea5gC8Q@mail.gmail.com> [not found] ` <CAGTS-a-SvWWF+br6sKxGj6ufVY=4m830FH9BDg06QJR1vbNFsw@mail.gmail.com> 2019-09-16 2:18 ` Fwd: " Jasper Hugunin 2019-09-16 16:18 ` [HoTT] " Licata, Dan 2019-09-16 17:09 ` Jasper Hugunin 2019-09-16 19:01 ` Licata, Dan 2019-09-16 20:17 ` Jasper Hugunin 2019-09-18 12:16 ` Anders Mortberg 2019-09-18 12:52 ` Thierry Coquand 2019-09-15 11:55 ` [HoTT] " Andrew Swan 2019-09-15 22:38 ` Jasper Hugunin 2019-09-16 1:04 ` Jon Sterling [not found] ` <A605E6EE-0101-4390-B50D-A6AEB36FDCC2@icloud.com> 2019-09-16 1:44 ` Jon Sterling

Discussion of Homotopy Type Theory and Univalent Foundations Archives are clonable: git clone --mirror http://inbox.vuxu.org/hott Example config snippet for mirrors Newsgroup available over NNTP: nntp://inbox.vuxu.org/vuxu.archive.hott AGPL code for this site: git clone https://public-inbox.org/public-inbox.git