From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on inbox.vuxu.org X-Spam-Level: X-Spam-Status: No, score=-1.1 required=5.0 tests=DKIMWL_WL_MED,DKIM_SIGNED, DKIM_VALID,DKIM_VALID_EF,HEADER_FROM_DIFFERENT_DOMAINS,HTML_MESSAGE, MAILING_LIST_MULTI,RCVD_IN_DNSWL_NONE autolearn=ham autolearn_force=no version=3.4.2 Received: from mail-pf1-x439.google.com (mail-pf1-x439.google.com [IPv6:2607:f8b0:4864:20::439]) by inbox.vuxu.org (OpenSMTPD) with ESMTP id 727304bc for ; Mon, 16 Sep 2019 02:18:26 +0000 (UTC) Received: by mail-pf1-x439.google.com with SMTP id w126sf24963224pfd.22 for ; Sun, 15 Sep 2019 19:18:26 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1568600305; cv=pass; d=google.com; s=arc-20160816; b=KFK1U4mFJvA6UdgUKBUOOJYpYGBum+umeY/xmPYSPUjJ4BNPAv89sxkB700itqiMqR Mef0WDl50GFM30zGKTCh0pbqH4Wjh+uRA4WN1/HdCW3BFiz5zP1WiE4jk4VF4vUnfvL8 O+bLwdKekfBGsblHpOf+kNU2JxuXRGBtykn9DvdoYupKrlx0pTKSq/KSjouac1GU1I5Q S5XNHja9n0r7xuvw8jZUuE0dNeFE0DTcD86msuqwymnyKyVNeepMQ3K8ut2Ftkpbo7q5 2fuNFusYLQ2wYg3PMjHEXIJ/7voIPKcfmk2OZTw0bsuRN4BLbyC4OHWVlecKOlvYIP8h Q1vw== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-unsubscribe:list-archive:list-help:list-post:list-id :mailing-list:precedence:to:subject:message-id:date:from:in-reply-to :references:mime-version:sender:dkim-signature; bh=Fy37ozWduI5jzTiTOmrbvQckapHIS7lmtL217k+6ew4=; b=fI5MhULXt6hLFLDeROmicOEnym9gYHu0QCsHVQP2yCjyjxttqgh1q2kjYMpbCa4klh IxsF9y2HpexU2pVcrrV27Uoz+fk9+eFL43u4kmXfslvtl082A2I0a5nQH4tOlhFaDUdI Q5GAySWJz6TfPbYdI7tC2wwsKbYh9kjMxhMsotGdlPKh5cUY40zmsUe86HmeZnKjOdkv uIfD0ReZZsQg+kR6NAQjwXk4VD/rxt+VK7Qv/oBaORqbKTSLgTu+PtBUWmxVy6OxT+St +oOtgvmNHXDOHW2YMoeGBNVrp0LMSuFyaT7EabXhOrC78E7mTUKNLJAXtfsE99g6+cHz S4/g== ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@cs.washington.edu header.s=goo201206 header.b=a0Pundhx; spf=neutral (google.com: 2607:f8b0:4864:20::336 is neither permitted nor denied by best guess record for domain of jasperh@cs.washington.edu) smtp.mailfrom=jasperh@cs.washington.edu; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=cs.washington.edu DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20161025; h=sender:mime-version:references:in-reply-to:from:date:message-id :subject:to:x-original-sender:x-original-authentication-results :precedence:mailing-list:list-id:list-post:list-help:list-archive :list-unsubscribe; bh=Fy37ozWduI5jzTiTOmrbvQckapHIS7lmtL217k+6ew4=; b=dLHBgQ6t0oqe3JBjf3ybD5SsWyRg7WOtroxAVOjuJFV7B4aQW+jmW8hAQci89yDeL6 XlZQUEI/GKL7x1jLMOpFf4jA0p4ZeyHJ/y8UCHCoJCkuyh/0G47YqOagk2cbuOAlpsD9 PofiD4qdtg2fYLyxV8JQu7jImx3lsLmotY8vrTCex9cG/C0hfYMZuufSklF6ylx1Ixo2 AQz/hgtc89aKMwIRMIZE4LuAi/bIVVEoeczDuewVd9YgenHnBlbbi5iNO4tSrAiG03K+ TXlfIzIYp7CaMMlRd7sB4wDS9cZjxjNFi3Qsj9mhCWOLCRot0w9Yf6tP4f2GGpsvb//x 3mOA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=sender:x-gm-message-state:mime-version:references:in-reply-to:from :date:message-id:subject:to:x-original-sender :x-original-authentication-results:precedence:mailing-list:list-id :x-spam-checked-in-group:list-post:list-help:list-archive :list-unsubscribe; bh=Fy37ozWduI5jzTiTOmrbvQckapHIS7lmtL217k+6ew4=; b=RHVU5GgzoqGZD7efmMmhyp1vGfhIX5g9Spx90h3rmPcS1Sl/sdOGDMGTmLxVGKszDI i+lIOuf2MX+EWqfZct9AL05Wow5BolRVxMfueMkomyJGJZL3d7IFK3PbtJDHX/AT6mU7 DfDPDozKTTe+VrUoeYX6+lETRUtOI5QfcgSHX5kzw3XLfw/8KuZAmZnASC2qZg+ynEoT i2YVtjdpuRC62Fc/jEEUpEMRvTqyypDLQl2nvo1rroxnwmWNU9qyD2bE05B0HAWDNhbl uaxc9lxHWZBbgm5tVdMEeFC5joTAnWxFBBH1B51bwHyayPREK88vQW6Zh92fvTsCUJpw 40Zg== Sender: homotopytypetheory@googlegroups.com X-Gm-Message-State: APjAAAVLPTMNQ6WP2SGA6WOrGV9E+RazDumN1K0r/cSrCB+G4Srp+ROU y0pMndVywHxTuK/EoH4irDQ= X-Google-Smtp-Source: APXvYqzPNNQ4uCuVfDw4RijqywRJ479o7nfzV2K4vzCVwlHUTqZ4O3K/vxfH3thCfPSRFOVmVUcVOA== X-Received: by 2002:a17:902:9a0a:: with SMTP id v10mr42347974plp.186.1568600304577; Sun, 15 Sep 2019 19:18:24 -0700 (PDT) X-BeenThere: homotopytypetheory@googlegroups.com Received: by 2002:aa7:9343:: with SMTP id 3ls736860pfn.15.gmail; Sun, 15 Sep 2019 19:18:24 -0700 (PDT) X-Received: by 2002:a63:e90c:: with SMTP id i12mr7417247pgh.40.1568600304093; Sun, 15 Sep 2019 19:18:24 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1568600304; cv=none; d=google.com; s=arc-20160816; b=u916gR0lgVXXR3R34rYIQmBb7wyHgp/qxGY5Pa1BNWdTg304s24jYVVP+Nvpb7aqif b0y+DFITsoAGQS9vCqLLPjDOITbj2j25DkB/C+Y7uQ8EEopuKlENcGSRHJOop9l4cJ2j 5W9K4q4UvU/hp0TH3W6dNRZH1a73k6owvPWPHSdjh/y4R25eQ+iJoZy3rSFWF49aFY6c s0Utx/HKsKh168Q14dF3OA+3l92GCpudszV12VDV/UB8OG768NZSAy+lqoG9ubGro6b8 VJ12Ixtg+0BIJybyWXen0KP0D1DlSusZZHGZt/u6Qt7fF+vQHBs6WpHF/j0M8v+0drn1 5z4Q== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :dkim-signature; bh=uZ54007hjDDoILMRRNiT81NeL0X7aImyY+jTYpsJAJo=; b=GenifcKBjhOUWVPasKv8HcsgJyTDaW0usEJjgns82Ztq8YcX9J9RHj2egDqv06CQbD OfjoPLMYe9l4Ek4aHWznyHTbzkBgywz+u7jWfLYUyeUX6Qr5trsWCa9HQx47QJHeynhd ZBDxHkSBaxSg+55kdcc6tzu81SldLf6VURKpvyweWk/Y3LoobyU4M7qJ1TTKcL476WjN MuOyAJNmvt7YucP46YTzL9zlU/lrMRjerDyMnN4Ep70YOWHqcm8yOTSk5vMHSTWASqxR Foc0IO69KUeOdGCRcur8lK2YvAoNX7BSZDIVy4is69bRb6o2c0osihhWO/dlR4FvyxUd Aqfg== ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@cs.washington.edu header.s=goo201206 header.b=a0Pundhx; spf=neutral (google.com: 2607:f8b0:4864:20::336 is neither permitted nor denied by best guess record for domain of jasperh@cs.washington.edu) smtp.mailfrom=jasperh@cs.washington.edu; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=cs.washington.edu Received: from mail-ot1-x336.google.com (mail-ot1-x336.google.com. [2607:f8b0:4864:20::336]) by gmr-mx.google.com with ESMTPS id br8si317835pjb.3.2019.09.15.19.18.24 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Sun, 15 Sep 2019 19:18:24 -0700 (PDT) Received-SPF: neutral (google.com: 2607:f8b0:4864:20::336 is neither permitted nor denied by best guess record for domain of jasperh@cs.washington.edu) client-ip=2607:f8b0:4864:20::336; Received: by mail-ot1-x336.google.com with SMTP id g13so4309623otp.8 for ; Sun, 15 Sep 2019 19:18:24 -0700 (PDT) X-Received: by 2002:a9d:7842:: with SMTP id c2mr7865026otm.171.1568600303470; Sun, 15 Sep 2019 19:18:23 -0700 (PDT) MIME-Version: 1.0 References: In-Reply-To: From: Jasper Hugunin Date: Sun, 15 Sep 2019 22:18:37 -0400 Message-ID: Subject: Fwd: [HoTT] Re: A question about the problem with regularity in CCHM cubical type theory To: HomotopyTypeTheory@googlegroups.com Content-Type: multipart/alternative; boundary="000000000000e222870592a23756" X-Original-Sender: jasperh@cs.washington.edu X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@cs.washington.edu header.s=goo201206 header.b=a0Pundhx; spf=neutral (google.com: 2607:f8b0:4864:20::336 is neither permitted nor denied by best guess record for domain of jasperh@cs.washington.edu) smtp.mailfrom=jasperh@cs.washington.edu; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=cs.washington.edu Precedence: list Mailing-list: list HomotopyTypeTheory@googlegroups.com; contact HomotopyTypeTheory+owners@googlegroups.com List-ID: X-Google-Group-Id: 1041266174716 List-Post: , List-Help: , List-Archive: , --000000000000e222870592a23756 Content-Type: text/plain; charset="UTF-8" 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 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 > 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. --000000000000e222870592a23756 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
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>
- Jasper Hugunin

On Sun, Sep 15, 2019 at 3:28 AM An= ders 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". Thi= s 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 t= his 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, be= cause of a subtlety I had been forgetting.
>
> Since types are *Kan* cubical sets, we need that the Kan operations ag= ree as well as the sets.
> So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, c= ompGlue) =3D (A, compA), and getting that the Kan operations to agree was/i= s 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&g= t; 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:<= br> >> 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 s= trict 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 f= ound to not satisfy regularity.
>> I don't remember seeing the regularity condition defined anywh= ere, but my understanding is that it requires that composition in a degener= ate line of types, with the system of constraints giving the sides of the b= ox 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 rea= sons 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 Gro= ups "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%2BZ= wAcAefiTg4JJVHemV3HUPcPEg%40mail.gmail.com.

--
You received this message because you are subscribed to the Google Groups &= quot;Homotopy Type Theory" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to = HomotopyTypeTheory+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://g= roups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8= myrXD1g5P3DCjSO%3DfvOQ%40mail.gmail.com.
--000000000000e222870592a23756--