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-wr1-x437.google.com (mail-wr1-x437.google.com [IPv6:2a00:1450:4864:20::437]) by inbox.vuxu.org (OpenSMTPD) with ESMTP id 230c262d for ; Wed, 18 Sep 2019 12:52:04 +0000 (UTC) Received: by mail-wr1-x437.google.com with SMTP id w10sf2320649wrl.5 for ; Wed, 18 Sep 2019 05:52:04 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1568811123; cv=pass; d=google.com; s=arc-20160816; b=BLFFpzIOYHYHkOJzdTp49mHAvobhnzL669D6PPSsoAJdLKseiB8JEC4gzNJywNamEH YRopyX7BBePfn23KqUrbYI3xVmEgNJn7iY7b1UeLQYIH7zZQlh7wXdy/XVWQlcPq1eoD dSLDoJBOBJBKC85WGRNamq8N9rpKYZ3ygRxmCcpkeFEn/jFEushykT+Bo7IXPv+mLZwT JBJFAjyNHeUteyzf5JB6BPDBsZfVBWO0FVP//A1Z5URw8wQ0oR6nZJn29/mEfrG5MmD6 isQjKTrisIXSfpUPcsCm88XmS58fP+wr0P8k/AfAKXhqZY84/trqxMnmQ801HNSZhWhk 7Dew== 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:mime-version:content-language :accept-language:in-reply-to:references:message-id:date:thread-index :thread-topic:subject:cc:to:from:sender:dkim-signature; bh=GhMY91juMNLm9VatlGnUK1obWYzttRIfpvt1w0nsz8E=; b=jqQ8RoUbE+0ZrjYQwSqUp8qkP4nsBc9VEmzu7vZwmCOMUfj4agTmUaukECJx1sBGIp J1ojCBOFbFr8gX1CYseXiA9cVm6J9S/Lk4UB5/ONJAm4HRtGTxwbaF/tnNMiyhsYKDxe dcJHwElHnTmu0XrzPHpuiuTxNxni6c/b2/qY53YsXnPe0OSpZVQqE4mFXHH/+53MLZox yFmGTYeUdVwxSJPXNz3sOhNgCV+TC4ld5iuknwuHohCTdsIbfzY1275NCwZ4t2a5kSIN zjK9v0jIQ0pv9JbdUp1GQBoAQF0rKX1sZozui2gEc+QZpPeLwwY026xV0LcWyDKaldzy baCw== ARC-Authentication-Results: i=2; gmr-mx.google.com; spf=pass (google.com: domain of thierry.coquand@cse.gu.se designates 129.16.226.138 as permitted sender) smtp.mailfrom=Thierry.Coquand@cse.gu.se DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20161025; h=sender:from:to:cc:subject:thread-topic:thread-index:date:message-id :references:in-reply-to:accept-language:content-language :mime-version:x-original-sender:x-original-authentication-results :precedence:mailing-list:list-id:list-post:list-help:list-archive :list-unsubscribe; bh=GhMY91juMNLm9VatlGnUK1obWYzttRIfpvt1w0nsz8E=; b=FxfK0c+VREbdhnhDry84RnqEMIIdcMXXvUCiIKE2UCCafIN7nExfwMaNSIA6kbNu09 m5DqGQJuvnpaT5e6SWT43tzYHJLgxzLWUlu2omKsmY5H9CU1ojm9vXVLr9Dhr5ag6mXp lBok+o35Fx9EcR7Iao84Jsjwa1muz178u1TTygg97JuTqKoP2lpKKZ50I98hrHgi3b59 lHEJ8FJfklNIoVgGz79FwU+sO5OrpTYhf51ffq2mqsgPqmHSxonMn5PjFUn2f4QdT4cJ u0SQx/7zhwFsoyDNMz/LWoC+evoeONfYH8NJ2ROc9PKfx0HoSbGOkjFjvSMGOo5TlDkS vEUw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=sender:x-gm-message-state:from:to:cc:subject:thread-topic :thread-index:date:message-id:references:in-reply-to:accept-language :content-language:mime-version: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=GhMY91juMNLm9VatlGnUK1obWYzttRIfpvt1w0nsz8E=; b=j33mfA5DKQfq2rAu1ykI0bO4PCZrRHq3xN9v+zvewzkcvGf8PwYK7F+N6eRu8/BA95 Y9Q6EQ4ElBc8pPgb2XQggxPXZnKVnjWYm4nvDVv52mFfCXhc5TO2Rihe3JI65fIXw9nE KwD3/RYNNv6PFzGoE3Y34jJum42ngviHgJ5j5lLvn9dWk3frYD5Y+jx4QkASKFexRq3/ xUlAlOtHxPF34he6Gx/SlLTpKmMhXLUyVVFZEIOE+ryVGkG0l39tsw8ebsHLRB7CcZdZ L7e22d7oQcgRcXeJBLQZEhrOlcocE5pggaDwUXZStoBBF/s6z37KFysQAd+Oubk9R4ex k1rQ== Sender: homotopytypetheory@googlegroups.com X-Gm-Message-State: APjAAAXJQm23+f6tLaH4URH4z4ek5oHWnahhFvMqFZ0+O5etDnqYYwFY QvHIQKQO4ASKdY/IiG8V668= X-Google-Smtp-Source: APXvYqwtINSUPek9Ncsxo+BBc3pSaqUpad+D29UjS12Rqklz/5W6DICx5dzfZ48wktYe2Lrr97EyMA== X-Received: by 2002:adf:f4cd:: with SMTP id h13mr3218507wrp.42.1568811123608; Wed, 18 Sep 2019 05:52:03 -0700 (PDT) X-BeenThere: homotopytypetheory@googlegroups.com Received: by 2002:a1c:99d7:: with SMTP id b206ls915979wme.2.canary-gmail; Wed, 18 Sep 2019 05:52:03 -0700 (PDT) X-Received: by 2002:a1c:29c4:: with SMTP id p187mr3014560wmp.28.1568811122964; Wed, 18 Sep 2019 05:52:02 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1568811122; cv=none; d=google.com; s=arc-20160816; b=zYqNt+ESme3I8ee/JyBqtsuUja/pGJ8ROBITmNx/aiKnutdF7QQB6tZVhO8uognR7Q bLiioz1Wj8NshZn+qtl2X6pLcpXbvD++9Ijx+fTg3W/CRaaNnUfiUw+md6WZaOVN/lJG LzOm4rwe6P4H8LkEv8qr1tHbZ4z1zM0AUax9UfCj3RHFoLmoII3vBF/MQrPEGtRc7tfC iF5ySN73nrXuSr7vI+Xg9mN3lBXj/L6XNpcLyekaqOVrnZx6MpSu80Rk+bp3Uh+VJJ8L K8kh9AWep6hHw8i6za7dmhwSZJg4Nsxcz0mvPNp4iCdAmFITSCCtgNacMXBrNVF6Lzwa 379g== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=mime-version:content-language:accept-language:in-reply-to :references:message-id:date:thread-index:thread-topic:subject:cc:to :from; bh=2Ulb4LXR1aKRYVr4zGgKaC8gPJcuUh0ZjTKTWIrngHI=; b=EIg5wI4Bsb5LLYt+pBWVMKvx/dPdTRgEYlnDm0r4MT1bHxDe4ABvxAIUpXb6bRP/to bCHopyZplOGSEDQ2pn8s8iDtbJhVFaCpsHcECgEdCkoUp1vHMELLaHXVIs6Rz41MRe2p 34i8TlsS9/CbScB7MFz++SQCwYSk986zAjMAW7zfzR932BeEjUqWzHmoZOqvqVxsEMZF zzv4/2S9DpdhtEhOAp1vkzZcNdrlixJq7bIGrQR7B1pH7SINEfleOJmTybcS08L3ERrp 6AVg1law7yHXPWFs6E770z34ksvPXfkA/+pIqANLVOgJQpuahklJTN4P+wpiigIYVR+m jYUQ== ARC-Authentication-Results: i=1; gmr-mx.google.com; spf=pass (google.com: domain of thierry.coquand@cse.gu.se designates 129.16.226.138 as permitted sender) smtp.mailfrom=Thierry.Coquand@cse.gu.se Received: from arryn.ita.chalmers.se (arryn.ita.chalmers.se. [129.16.226.138]) by gmr-mx.google.com with ESMTPS id 5si462960wmf.1.2019.09.18.05.52.02 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Wed, 18 Sep 2019 05:52:02 -0700 (PDT) Received-SPF: pass (google.com: domain of thierry.coquand@cse.gu.se designates 129.16.226.138 as permitted sender) client-ip=129.16.226.138; Received: from tyrell.ita.chalmers.se (129.16.226.132) by arryn.ita.chalmers.se (129.16.226.138) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384_P256) id 15.1.1713.5; Wed, 18 Sep 2019 14:52:02 +0200 Received: from tyrell.ita.chalmers.se ([129.16.226.132]) by tyrell.ita.chalmers.se ([129.16.226.132]) with mapi id 15.01.1713.004; Wed, 18 Sep 2019 14:52:02 +0200 From: Thierry Coquand To: Anders Mortberg CC: Jasper Hugunin , "Licata, Dan" , "HomotopyTypeTheory@googlegroups.com" Subject: Re: [HoTT] A question about the problem with regularity in CCHM cubical type theory Thread-Topic: [HoTT] A question about the problem with regularity in CCHM cubical type theory Thread-Index: AQHVbKphMn4/7k6XB0KZFmPOhV7EdqcuaCUAgAAfQQCAABVJgIACnjIAgAAJ/YA= Date: Wed, 18 Sep 2019 12:52:02 +0000 Message-ID: References: <10B7D7E9-3155-4FA0-90E0-BB6BE2C37B1B@wesleyan.edu> In-Reply-To: Accept-Language: en-US, sv-SE Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [129.16.10.245] Content-Type: multipart/alternative; boundary="_000_C1FA3BE5646947F79049914A6AFC68BAchalmersse_" MIME-Version: 1.0 X-Original-Sender: thierry.coquand@cse.gu.se X-Original-Authentication-Results: gmr-mx.google.com; spf=pass (google.com: domain of thierry.coquand@cse.gu.se designates 129.16.226.138 as permitted sender) smtp.mailfrom=Thierry.Coquand@cse.gu.se 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: , --_000_C1FA3BE5646947F79049914A6AFC68BAchalmersse_ Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Indeed, one can find traces of this in the note http://www.cse.chalmers.se/~coquand/compv1.pdf Thierry PS: The =E2=80=9Cglueing=E2=80=9D operation was then introduced only as a c= omputational way to transform an equivalence to a path and one needed another composition for the universe t= o get regularity. One insight was the reduction of =E2=80=9Cfilling=E2=80=9D to =E2=80=9Ccomposition=E2=80=9D but= this was using regularity. As explained in the thread, there was a bug with composition in the univer= se, 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 =E2=80=9Cglueing=E2=80=9D w= as already enough to get univalence. This was explained later by understanding that this =E2=80=9Cglueing=E2=80= =9D operation actually expresses the =E2=80=9Cequivalence extension property=E2=80=9D (used in the= simplicial set model for proving univalence). This was helped by the introduction of the notion = of =E2=80=9Cpartial elements=E2=80=9D which also simplified the presentation and made proof checking much easier.= We could recover a model but without Path =3D Id. It was really surprising, at least for me, that on= e could still define Id from Path (using Andrew Swan=E2=80=99s method). On 18 Sep 2019, at 14:16, Anders Mortberg > 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 =3D 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 =3D 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 =3D 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 =3D B0 2. if i # A then comp^j (hcomp^i_U [phi -> A] A0) [psi -> B] B0 =3D 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 =3D 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 =3D Id. -- Anders On Mon, Sep 16, 2019 at 10:17 PM Jasper Hugunin > 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 = =3D A, but this is somehow unnatural. However, it is what I was postulating in step 1 of the initial message of t= his 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 B= ox^i [ phi |-> T ] A for phi |- A =3D T(i1), satisfying the laws phi |- Box= ^i [ phi |-> T ] A =3D T(i0) and regularity: Box^i [ phi |-> A ] A =3D A. You then need comp Box to respect Box^i [ phi |-> A ] A =3D A, and this is = also apparently not possible in CCHM, but you now have the extra informatio= n 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 thi= nk might suffice to complete the argument. If you call a notion of Box that satisfies Box^i [ phi |-> A ] A =3D A "reg= ular 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 so= rt 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 di= rection or the other. Of course (I haven't actually checked, but my intuition says that), once yo= u have 2-dimensional composition you will need n-dimensional composition, a= nd 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 compositi= on (returning an (n-1)-dimensional cube), since it feels unfair to say "I k= now 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 c= orresponding to faces in the result. =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D In CCHM, the basic Kan operation is (comp^i A [ phi |-> a ] a0 : A(i1) [ ph= i |-> a(i1) ]) for i |- A with phi, i |- a : A and a0 : A(i0) [ phi |-> a(i= 0) ]. Regularity for this operation means that if A and a are independent of i, t= hen comp^i A [ phi |-> a ] a0 =3D a0. We have regular composition for Glue types, but we don't have comp^i (Glue = [ phi |-> (A, equivRefl) ] A) =3D comp^i A. Simplifying things a little, we can take hcom^i U [ phi |-> T ] A =3D Box^i= [ phi |-> T(i :=3D ~ i) ] A to be a new type former, and give that a regul= ar composition operation. Here the thing blocking us from getting comp^i (Box^j [ phi |-> A ] A) =3D = 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) [ ph= i |-> 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 =3D j) for= composition over the diagonal (i =3D 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 ove= r 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 comp= osition may be preserved by all the usual type formers, optimistically incl= uding Glue and Box, because the two-dimensional composition for Box will ha= ve to satisfy an additional law comp2^i^j (Box [ phi |-> A ] A) =3D 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: al= ong the diagonal (comp^k T(i,j:=3Dk) [ phi |-> t(i,j:=3Dk) ] t0), which agr= ees with composing either right then up or up then right when T is degenera= te 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 th= en 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 straightforwar= dly. For each n-cube i_1, ..., i_n |- A, we have an n-dimensional regular compos= ition 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 compositio= n 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, whi= ch we describe by saying that ?[0] reduces to =3D and ?[1] reduces to o. Thus for 2-dimensional A, we have a line (i =3D j) --- (i ?[a] j) --- (i o = j), and for three dimensional A, we have a square with four faces (i =3D j = ?[a_2] k), (i o j ?[a_2] k), (i ?[a1] j =3D k) (i ?[a1] j o k), relating th= e 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), treati= ng j_0 =3D j_n =3D 1. Extending this to =3D and o, if A, a are degenerate in i, then (i =3D j) an= d (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 expl= ain it well) This all gives a notion of n-dimensional regular composition, which takes a= n n-cube type A and partial term phi, i1, ..., in |- a and a base point a0 = : A(i_k :=3D 0)[ phi |-> a(i_k :=3D 0) ] and returns an (n-1)-cube in A(i_k= :=3D 1) [ phi |-> everywhere a(i_k :=3D 1) ]. There are three classes of equations that this has to satisfy, two for the = face maps j_k =3D 0 and j_k =3D 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 u= sual regular comp. Considering j_k to be formally extended with j_0 =3D j_n =3D 1, we get a "z= ero-dimensional" composition operation, which should be taken to be the ide= ntity. (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 fo= rmers (Pi, Sg, Path, ...) by essentially the same argument as for 1-dimensi= onal comp. I think I have worked out how to give a regular n-dimensional composition o= peration for Glue, by essentially the same argument as in CCHM, but with ad= ditional faces for j_k =3D 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 =3D T(i_k :=3D 1). I think I have worked out how to give a regular n-dimensional composition o= peration 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)-d= imensional regular composition. To use Box as the regular n-dimensional composition operation for the unive= rse, we need that (Box, comp Box) respects the equations for when j_k =3D 0= , j_k =3D 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 l= ayer 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 > wrote: Wow! I read that pretty closely and couldn=E2=80=99t find a problem. That i= s surprising to me. Will look more later. What I was saying about fill for the aligning algorithm is also wrong =E2= =80=94 I wasn=E2=80=99t thinking that the type of the filling was also dege= nerate, 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 un= der glue types, there=E2=80=99s still a problem with using those glue types= to show that that universe is itself regularly fibrant, I think? If you de= fine comp U [phi -> i.T] B to be Glue [phi -> T(1),...] B then no matter ho= w nice the equivalence is (eg the identity) when i doesn=E2=80=99t occur in= T, the type will not equal B =E2=80=94 that would be an extra equation abo= ut the Glue type constructor itself. Does that seem right? -Dan On Sep 16, 2019, at 1:09 PM, Jasper Hugunin > 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 degenerat= e filling problem and function to be reflexivity. I claim that this holds b= y 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 co= nnections (and I believe also holds for fill as defined in ABCFHL). (a) Given i |- B =3D Glue [ phi |-> (T, f) ] A, with psi, i |- b : B and b0 : B= (i0)[ psi |-> b(i0) ], we want to compute b1 =3D comp^i B [ psi |-> b ] b0 = : B(i1)[ psi |-> b(i1) ]. We set a :=3D unglue b and a0 :=3D unglue b0. Set delta :=3D forall i. phi. Then we take: a1' :=3D comp^i A [ psi |-> a ] a0 delta |- t1' :=3D comp^i T [ psi |-> b ] b0 delta |- omega :=3D pres^i f [ psi |-> b ] b0 phi(i1) |- (t, alpha) :=3D equiv f(i1) [ delta |-> (t1', omega), psi |-> (b= (i1), refl a1') ] a1' a1 :=3D hcomp^j A(i1) [ phi(i1) |-> alpha j, psi |-> a(i1) ] a1' (note that= in the regular setting the psi face is redundant) b1 :=3D 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 =3D comp^i A [ psi |-> f b, j =3D 1 |-> f (fi= ll^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 =3D b0. We have that a is independent of i, and delta =3D phi. First consider delta (=3D phi) |- pres^i f [ psi |-> b ] b0. (This is the e= xplanation of your first dash) Note that if comp^i A is regular, then fill^i A [ psi |-> b ] b0 =3D b This is comp^i A [ psi |-> f b, j =3D 1 |-> f (fill^i T [ psi |-> t ] t= 0) ] (f t0) =3D comp^i A [ psi |-> f b, j =3D 1 |-> f t0 ] (f t0) =3D <= j> f t0. Thus pres of a degenerate filling problem and function is reflexivity. Going back to composition of Glue, a1' =3D a0 phi |- t1' =3D b0 phi |- omega =3D refl (f b0) phi |- (t1, alpha) =3D (t1', omega) (since delta =3D phi, so we end up in t= he delta face of equiv) a1 =3D a1' (the only dependence on j is via (alpha j), but alpha =3D omega = =3D refl, so this filling problem is degenerate) b1 =3D glue [ phi |-> t1 ] a1 =3D glue [ phi |-> b0 ] a0 =3D glue [ phi |->= b0 ] (unglue b0) =3D 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 Ort= on-Pitts and Cartesian cubes. Best regards, - Jasper Hugunin On Mon, Sep 16, 2019 at 12:18 PM Licata, Dan > 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 =E2=80=9Caligned=E2=80=9D one= from Orton-Pitts, which are intensionally different, as well as other poss= ible 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 =E2=80=98pres=E2=80=99 path omega, which via the equiv operatio= n ends up in alpha, so the system in a1 may not be degenerate even if the i= nput 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 =E2=80=9Call the way at the = outside=E2=80=9D, an issue is with the adjust_com operation on page 20, whi= ch is later used for aligning (in that case beta is (forall i phi)). The p= otential issue is that adjust_com uses a *filler*, not just a composition f= rom 0 to 1, so even if t doesn=E2=80=99t depend on z, the filling does, and= the outer com won=E2=80=99t cancel. In CCHM, filling is defined using con= nections, so it=E2=80=99s a little different, but I think there still has t= o be a dependence on z for it to even type check =E2=80=94 it should come u= p because of the connection term that is substituted into the type of the c= omposition problem. So I=E2=80=99d guess there is still a problem in the a= ligned 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 > wrote: This doesn't seem right; as far as I can tell, composition for Glue types i= n 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 a= s well as the sets. So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, compGlue)= =3D (A, compA), and getting that the Kan operations to agree was/is diffic= ult. (Now that I know what the answer is, it is clear that this was already expl= ained in the initial discussion.) Humbly, - Jasper Hugunin On Fri, Sep 13, 2019 at 2:10 AM 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 c= ondition 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 regul= arity 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 f= inding myself wishing that J computed strictly. If I understand correctly, early implementations of ctt did have strict J f= or Path types, and this was justified by a "regularity" condition on the co= mposition operation, but as discussed in this thread on the HoTT mailing li= st, 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 u= nderstanding is that it requires that composition in a degenerate line of t= ypes, with the system of constraints giving the sides of the box also degen= erate 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 ref= l ] 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 e= mail to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/= HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HUPcPEg%40= mail.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 e= mail to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/= HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5QWffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%40= mail.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 e= mail to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/= HomotopyTypeTheory/CAGTS-a8E03C3BMEwi-T4qjet4EbCgnePhR3Ffa1MepxNmtZoUA%40ma= il.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 e= mail to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/= HomotopyTypeTheory/CAMWCpp%3DEMvH%2BXtRn7AfyjRDjmiwxfML2JQqKyPjXAhM%2BM2vcj= w%40mail.gmail.com. --=20 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 e= mail 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. --_000_C1FA3BE5646947F79049914A6AFC68BAchalmersse_ Content-Type: text/html; charset="UTF-8" Content-ID: <48DB885FF004184888F5C53658FFE9A2@chalmers.se> Content-Transfer-Encoding: quoted-printable  Indeed, one can find traces of this in the note 

http://www.cse.chalmers.se/~coquand/compv1.pdf

 Thierry



PS: The =E2=80=9Cglueing=E2=80=9D operation was then introd= uced only as a computational way to transform an 
equivalence to a path and one needed another composition fo= r the universe to get regularity. One insight was the
reduction of =E2=80=9Cfilling=E2=80=9D to =E2=80=9Ccomposit= ion=E2=80=9D but this was using regularity.
As explained in the thread, there was  a bug with comp= osition in the universe, found by Carlo, Dan
and Bob. After this problem was made explicit, one could fi= nd another way (a little more
complex) to reduce filling to composition which does not us= e regularity.
It was then realised (by Anders and Simon) that =E2=80=9Cgl= ueing=E2=80=9D was already enough to get univalence.
This was explained later by understanding that this =E2=80= =9Cglueing=E2=80=9D operation actually
expresses the =E2=80=9Cequivalence extension property=E2=80= =9D (used in the simplicial set model
for proving univalence). This was helped by the introductio= n of the notion of =E2=80=9Cpartial elements=E2=80=9D 
which also simplified the presentation and made proof check= ing much easier. We could recover a model
but without Path =3D Id. It was really surprising, at least= for me, that one could still define Id
from Path (using Andrew Swan=E2=80=99s method).





On 18 Sep 2019, at 14:16, Anders Mortberg <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,<= br class=3D""> reflEquiv) ] A =3D A" to get a regular version of the reduction of com= p
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 =3D hcomp^i_U [phi -> A] A0

For regularity we need the following condition on hcomp_U (where "i #<= br class=3D""> 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 =3D 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 =3D B0

2. if i # A then

comp^j (hcomp^i_U [phi -> A] A0) [psi -> B] B0 =3D comp^j A0 [psi -&g= t; 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 =3D 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 =3D Id.

--
Anders






On Mon, Sep 16, 2019 at 10:17 PM Jasper Hugunin
<jasperh@cs.wash= ington.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 =3D A, but this is somehow unnatural.
However, it is what I was postulating in step 1 of the initial message of t= his 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 B= ox^i [ phi |-> T ] A for phi |- A =3D T(i1), satisfying the laws phi |- = Box^i [ phi |-> T ] A =3D T(i0) and regularity: Box^i [ phi |-> A ] A= =3D A.
You then need comp Box to respect Box^i [ phi |-> A ] A =3D A, and this = is also apparently not possible in CCHM, but you now have the extra informa= tion that A is a line of types. (Using Box to turn an equivalence into a li= ne of types in the definition of comp Box is circular.)

I've developed a notion of (regular) n-dimensional composition, which I thi= nk might suffice to complete the argument.
If you call a notion of Box that satisfies Box^i [ phi |-> A ] A =3D A &= quot;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-dim= ensional composition" which is regular in one direction or the other.<= br class=3D""> Of course (I haven't actually checked, but my intuition says that), once yo= u have 2-dimensional composition you will need n-dimensional composition, a= nd then hopefully regular (n+m)-dimensional composition for A will suff= ice 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 compositi= on (returning an (n-1)-dimensional cube), since it feels unfair to say &quo= t;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 c= orresponding to faces in the result.

=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D

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, t= hen comp^i A [ phi |-> a ] a0 =3D a0.
We have regular composition for Glue types, but we don't have comp^i (Glue = [ phi |-> (A, equivRefl) ] A) =3D comp^i A.
Simplifying things a little, we can take hcom^i U [ phi |-> T ] A =3D Bo= x^i [ phi |-> T(i :=3D ~ 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) = =3D 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 =3D j) for= composition over the diagonal (i =3D 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 ove= r 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 comp= osition may be preserved by all the usual type formers, optimistically incl= uding Glue and Box, because the two-dimensional composition for Box will ha= ve to satisfy an additional law comp2^i^j (Box [ phi |-> A ] A) =3D 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: al= ong the diagonal (comp^k T(i,j:=3Dk) [ phi |-> t(i,j:=3Dk) ] t0), which = agrees with composing either right then up or up then right when T is degen= erate 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 th= en 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 ex= tended to higher dimensions straightforwardly.

For each n-cube i_1, ..., i_n |- A, we have an n-dimensional regular compos= ition 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 compositio= n 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 hav= e to describe the faces of this cube, which we describe by saying that ?[0]= reduces to =3D and ?[1] reduces to o.
Thus for 2-dimensional A, we have a line (i =3D j) --- (i ?[a] j) --- (i o = j), and for three dimensional A, we have a square with four faces (i =3D j = ?[a_2] k), (i o j ?[a_2] k), (i ?[a1] j =3D k) (i ?[a1] j o k), relating th= e four corners given by coercing over i then j then k, coercing over i then j and k simultaneously, coercing ove= r 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&= #43;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 =3D j_n =3D 1.
Extending this to =3D and o, if A, a are degenerate in i, then (i =3D j) an= d (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 expl= ain it well)

This all gives a notion of n-dimensional regular composition, which takes a= n n-cube type A and partial term phi, i1, ..., in |- a and a base point a0 = : A(i_k :=3D 0)[ phi |-> a(i_k :=3D 0) ] and returns an (n-1)-cube in A(= i_k :=3D 1) [ phi |-> everywhere a(i_k :=3D 1) ].
There are three classes of equations that this has to satisfy, two for the = face maps j_k =3D 0 and j_k =3D 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 u= sual regular comp.
Considering j_k to be formally extended with j_0 =3D j_n =3D 1, we get a &q= uot;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 fo= rmers (Pi, Sg, Path, ...) by essentially the same argument as for 1-dimensi= onal comp.
I think I have worked out how to give a regular n-dimensional composition o= peration for Glue, by essentially the same argument as in CCHM, but with ad= ditional faces for j_k =3D 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, w= ith phi |- A =3D T(i_k :=3D 1).
I think I have worked out how to give a regular n-dimensional composition o= peration 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 unive= rse, we need that (Box, comp Box) respects the equations for when j_k =3D 0= , j_k =3D 1, or T is independent of j.
My hope is that, as in the (1, 1) dimensional case, using (m+n)-dimensi= onal 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 l= ayer 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=E2=80=99t find a problem. That i= s surprising to me. Will look more later.

What I was saying about fill for the aligning algorithm is also wrong =E2= =80=94 I wasn=E2=80=99t thinking that the type of the filling was also dege= nerate, 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 un= der glue types, there=E2=80=99s still a problem with using those glue types= to show that that universe is itself regularly fibrant, I think? If you de= fine comp U [phi -> i.T] B to be Glue [phi -> T(1),...] B then no matter how nice the equivalence is (eg the ident= ity) when i doesn=E2=80=99t occur in T, the type will not equal B =E2=80=94= that would be an extra equation about the Glue type constructor itself. Do= es 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 degenerat= e filling problem and function to be reflexivity. I claim that this holds b= y 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 h= olds for fill as defined in ABCFHL).

(a)
Given i |- B =3D Glue [ phi |-> (T, f) ] A, with psi, i |- b : B and b0 = : B(i0)[ psi |-> b(i0) ], we want to compute b1 =3D comp^i B [ psi |->= ; b ] b0 : B(i1)[ psi |-> b(i1) ].
We set a :=3D unglue b and a0 :=3D unglue b0.
Set delta :=3D forall i. phi.
Then we take:
a1' :=3D comp^i A [ psi |-> a ] a0
delta |- t1' :=3D comp^i T [ psi |-> b ] b0
delta |- omega :=3D pres^i f [ psi |-> b ] b0
phi(i1) |- (t, alpha) :=3D equiv f(i1) [ delta |-> (t1', omega), psi |-&= gt; (b(i1), refl a1') ] a1'
a1 :=3D hcomp^j A(i1) [ phi(i1) |-> alpha j, psi |-> a(i1) ] a1' (not= e that in the regular setting the psi face is redundant)
b1 :=3D glue [ phi(i1) |-> t1 ] a1

With given i |- f : T -> A, with psi, i |- b : T and b0 : T(i0)[ psi |-&= gt; b(i0) ], we define
pres^i f [ psi |-> b ] b0 =3D <j> comp^i A [ psi |-> f b, j =3D= 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 =3D b0.
We have that a is independent of i, and delta =3D phi.

First consider delta (=3D phi) |- pres^i f [ psi |-> b ] b0. (This is th= e explanation of your first dash)
Note that if comp^i A is regular, then fill^i A [ psi |-> b ] b0 =3D b This is <j> comp^i A [ psi |-> f b, j =3D 1 |-> f (fill^i T [ p= si |-> t ] t0) ] (f t0) =3D <j> comp^i A [ psi |-> f b, j =3D 1= |-> f t0 ] (f t0) =3D <j> f t0.
Thus pres of a degenerate filling problem and function is reflexivity.

Going back to composition of Glue,
a1' =3D a0
phi |- t1' =3D b0
phi |- omega =3D refl (f b0)
phi |- (t1, alpha) =3D (t1', omega) (since delta =3D phi, so we end up in t= he delta face of equiv)
a1 =3D a1' (the only dependence on j is via (alpha j), but alpha =3D omega = =3D refl, so this filling problem is degenerate)
b1 =3D glue [ phi |-> t1 ] a1 =3D glue [ phi |-> b0 ] a0 =3D glue [ p= hi |-> b0 ] (unglue b0) =3D 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 Ort= on-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 =E2=80=9Caligned=E2=80=9D one= from Orton-Pitts, which are intensionally different, as well as other possible variations), and (b) include some of your reason= ing for why you think things are regular, to make it easier for me and othe= rs to reconstruct.

My current understanding is that

- For CCHM proper https://arxiv.org/pdf/1611.02108.pdf the potential issue is with the= =E2=80=98pres=E2=80=99 path omega, which via the equiv operation ends up i= n 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 =E2=80=9Call the way at the outside=E2=80=9D, an issue is wi= th the adjust_com operation on page 20, which is later used for aligning (i= n 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=E2=80=99t depend on z, the filling does, and the out= er com won=E2=80=99t cancel.  In CCHM, filling is defined using connec= tions, so it=E2=80=99s a little different, but I think there still has to be a dependence on z for it to even type check =E2=80=94 it s= hould come up because of the connection term that is substituted into the t= ype of the composition problem.  So I=E2=80=99d 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 H= ugunin <jasperh@= cs.washington.edu> wrote:

This doesn't seem right; as far as I can tell, composition for Glue types i= n 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". 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 (htt= ps://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.wash= ington.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 a= s well as the sets.
So part 1 could be thought of as (Glue [ phi |-> equivRefl A ] A, compGl= ue) =3D (A, compA), and getting that the Kan operations to agree was/is dif= ficult.
(Now that I know what the answer is, it is clear that this was already expl= ained 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 |-> e= quiv^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 regularit= y 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 regul= arity 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 f= inding myself wishing that J computed strictly.
If I understand correctly, early implementations of ctt did have strict J f= or 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 u= nderstanding is that it requires that composition in a degenerate line of t= ypes, with the system of constraints giving the sides of the box also degen= erate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual typ= e formers, plus Glue, but not the universe with computation defined as in t= he CCHM paper (for trivial reasons and non-trivial reasons; it gets stuck a= t 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 &= 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://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghC= h8%2BZwAcAefiTg4JJVHemV3HUPcPEg%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://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8SZx8PiaD-9rq5Q= WffU75Wz8myrXD1g5P3DCjSO%3DfvOQ%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://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a8E03C3BMEwi-T4q= jet4EbCgnePhR3Ffa1MepxNmtZoUA%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://groups.google.com/d/msgid/HomotopyTypeTheory/CAMWCpp%3DEMvH%2BXtRn7= AfyjRDjmiwxfML2JQqKyPjXAhM%2BM2vcjw%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://groups.google.com/d/m= sgid/HomotopyTypeTheory/C1FA3BE5-6469-47F7-9049-914A6AFC68BA%40chalmers.se<= /a>.
--_000_C1FA3BE5646947F79049914A6AFC68BAchalmersse_--