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.2 required=5.0 tests=DKIM_SIGNED,DKIM_VALID, DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FORGED_FROMDOMAIN,FREEMAIL_FROM, HEADER_FROM_DIFFERENT_DOMAINS,MAILING_LIST_MULTI,RCVD_IN_DNSWL_NONE autolearn=ham autolearn_force=no version=3.4.2 Received: from mail-pf1-x437.google.com (mail-pf1-x437.google.com [IPv6:2607:f8b0:4864:20::437]) by inbox.vuxu.org (OpenSMTPD) with ESMTP id a81680e2 for ; Wed, 18 Sep 2019 12:16:30 +0000 (UTC) Received: by mail-pf1-x437.google.com with SMTP id v3sf4732096pff.4 for ; Wed, 18 Sep 2019 05:16:30 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1568808989; cv=pass; d=google.com; s=arc-20160816; b=wwl2dGhM3fksVZp4iq3AFnODH032lxoHJbIXKveXjvF7V5lbTYAd/6lEDgNx1KxOwB 9krqo81vxfuBn/0OdjaBOp6sZLQT7YToNSpv5C2tuNf92XdkctQ1bPMBHpa04HsP2gy1 v1xHZcds7+xo9A565hCOg2kp6yeSk6+VZ/JU8n4VbmglYIf4OTiaPBdSVxSK4WVoOLP9 6VhEuOZwcbY/sZTIHBhIdJvHwJhIYaH/UjMWi4ZM99ahml/OwxgwOa1ZEqUnW0x1+pQg 9fHlS52ei7wAe+SAZHW8qg6NoDZ4NVFFqkML+GeF/xJCG8fhviWtuBnJYku3uj6oPrdV Baew== 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:content-transfer-encoding:cc:to:subject :message-id:date:from:in-reply-to:references:mime-version:sender :dkim-signature:dkim-signature; bh=NZUIjpyTM66pm5jqg1lctM1JbgPZl5zNP0rfDq05CiA=; b=kZuJKRFadMhpoufZHslFjKsH98Pm1ti0bswrfIigSjIU/ZE8GQP8SeXyJxHkuPV4lb 3Aw8l/A7rR2WILhOtK8VC5+fQY1VN1W2fZn6vUb9lc3cJV1AXDqZ+7iO+DsNaCt4XaAW yZUY/BVB0fpSkK5gNGCVvFQKIAE8xG1kvUO0+oqM/JGk1xoO5KCvw9rQrmta4GHx2V+c 59rg4njtl6gD2V7vkZMQNu7mu+oxp2AhHDHgQru2D2eZJhjWJy/Ek6G115kC+GGT7SQe GqYn9VpDZiukYyXSBPTqQpp6rwsAlCDHqm2rVamjJYHD6yRBxEq1LLoYeM/F7Q6DpiQL Ccyg== ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=P+poJGVA; spf=pass (google.com: domain of andersmortberg@gmail.com designates 2607:f8b0:4864:20::331 as permitted sender) smtp.mailfrom=andersmortberg@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com 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:cc:content-transfer-encoding:x-original-sender :x-original-authentication-results:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-unsubscribe; bh=NZUIjpyTM66pm5jqg1lctM1JbgPZl5zNP0rfDq05CiA=; b=NYuVkagM+5cTVg81/IQALi1XiecvoPsGwYDylWKacTplno9ih3GxqeJMdOcltmryf8 4axwgkQdLLyWdkO1E+K49DbQw3CPOC5tyAY3ApFIqEKc7VgPI8hwEPHRz/bK5X8760i2 W11HK6XwPh0QschjEPakuO/TH78BrWeSS09UDE/j041pfq7aKD7mh++JA1TmLp9+VeVR tMWJuQRuu16pEuxIstMmFzVR75Vig+eOQyk3X88k0bRW320zg2rH5/2x2rc/pRWDCXMB otaQFbDh9XkOa1O9FQXbNkOuXTjk7cE3ri/LYXn5y4wjxjLqMMHkklVD83vkiSXAzcot HLog== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding:x-original-sender :x-original-authentication-results:precedence:mailing-list:list-id :list-post:list-help:list-archive:list-unsubscribe; bh=NZUIjpyTM66pm5jqg1lctM1JbgPZl5zNP0rfDq05CiA=; b=JGLF/xMc4H6L69Q0KuvqXB9l7+c2HsYTgEr6WzS987uG61+Pn1D9rkGoVKNYuNbHlj 2Ox60X7OrpFMj9gW4tvRDvUB+sUh/CeAfepU/EPzv6rWosxyvz9guYfa9NHzV1mCMayk BNX6vjf4WSed9Q9419JmubC3V2+6j9Kzywxm2gQE+vEQDmKhZOYVy+ulW/h1BBb70/pE inhaV4eTmD6BnC6k7M8qagu9vKM598YjvgaS4BIn1YD+TJ846/ETCaOuKKScdfEVvXGr jXLexFgrZrf8TlC12XiuuGB4YNQIsajRWGFzFYoAGp6ns+HiTn9ANXySZQGsBdpym2mQ qZPQ== 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:cc:content-transfer-encoding :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=NZUIjpyTM66pm5jqg1lctM1JbgPZl5zNP0rfDq05CiA=; b=hNj+55/oRlZA7U79Obf9J0sFmd8qOasFj5fF/7X7Y1+Qcdcr5Ri3goz6GK8QZreXm6 Yhc29hd3eaWiL7AJz+/EZw+COy0nRZ4eJ4BTd9hyv8FYp6EaUzlHa33icFc03H/vhlWi wMZ2hHr/yGKXpVffKuD79ZmYXu0KDlhoNSk5Mq6V6d2ZMT1isltDNw/WyIz8L8CbSCCB 5VslRXiHQ4QNTna+njJkTOLasKk0FxF5ZxhCxlSomyGtetkrvMgrv750XYl3gOwH0Wx4 DHZ0zSdwuMO8aG/EU+u4eKNDr4PbLFCxzMQI1OIye0KUdmVuqwWY/iobFqWzik7Xd+oq 1vig== Sender: homotopytypetheory@googlegroups.com X-Gm-Message-State: APjAAAVJNZH4e4vJJcjIaCoGhV0kM0Ujymxg+sVAAD2Pm65SCG5kgE0R P/pJt6mvJ4QCP/LLVPWxGwk= X-Google-Smtp-Source: APXvYqyP/hhUKeaCZGi1tTzayi/wh2maFA8X7ZwE7YbBnSdklNzb//qfpIGyj8cTR+sgbKuAOb1PPQ== X-Received: by 2002:a17:902:326:: with SMTP id 35mr3984418pld.128.1568808989124; Wed, 18 Sep 2019 05:16:29 -0700 (PDT) X-BeenThere: homotopytypetheory@googlegroups.com Received: by 2002:a17:90a:8a8c:: with SMTP id x12ls668026pjn.5.gmail; Wed, 18 Sep 2019 05:16:28 -0700 (PDT) X-Received: by 2002:a17:90a:8d13:: with SMTP id c19mr3566632pjo.142.1568808988686; Wed, 18 Sep 2019 05:16:28 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1568808988; cv=none; d=google.com; s=arc-20160816; b=ZZ4DD+5xEayovjFDM8ADKxzilVKo9SIrFELiMjmh2fN0jEZhA5ZwxOfxhRl6vwzqKy 2rjdO+lMDLLM+5QG4FE87yeNdlfXuaRiSPG3nFZzj8N50Z8w+XIFDlYC6Km2ugdcAqgw X+2kSJ64OItRoLeechDw1Mn7dAw0J66KFAuM2s+wjes2FtTU5pw+5qN+Z+4uBNgw5Gb7 z44TXyfhz1rpl5N2JLk8ZxPeX9hRWBvBwV4gW1ensKViwEVGhKKs0mGILgOTIP/GKohM j400ECSNvi74HyQCgCbRa5548iWetWrQZvmyl4kXXPeatffGmJuJYe68OZfrd0R/NZHw XJhw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:dkim-signature; bh=hY+U33Muk1guoZzW4T8WPeDhBTiML0H/o4bhcyiJKdk=; b=beyPD+IbaXGxtyhoCLLCA0nKskQ/sMDrn6piJ/bpugfklWQxUMQ59i4aiXH0APFPlp fl+NH0HcY7UUZ5axcTtPgiHah2EJdPjeN0opkrG5G8i/SCcbZjxMnbIS6oAczLlkyJzU wWzXXn/deopduReqn1U0dxFUZ7eurDWGx5aPJEMuHS6uF/m/W1VnUXiploIKi+KLVUOH GJhTGMPY2Zqcy7gatbpuGmRhMlgNEAU8NPSNggfWBtVxdn1UykoXGk8WqEvmviW+Sm0D sbLV0CgYVcfQd/AaFN0N2CglATIbghZ9CwUsxoGxN+dftkgtPSmkOVPYExeE1/NJktH1 lfYQ== ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=P+poJGVA; spf=pass (google.com: domain of andersmortberg@gmail.com designates 2607:f8b0:4864:20::331 as permitted sender) smtp.mailfrom=andersmortberg@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: from mail-ot1-x331.google.com (mail-ot1-x331.google.com. [2607:f8b0:4864:20::331]) by gmr-mx.google.com with ESMTPS id p9si91358pjo.0.2019.09.18.05.16.28 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Wed, 18 Sep 2019 05:16:28 -0700 (PDT) Received-SPF: pass (google.com: domain of andersmortberg@gmail.com designates 2607:f8b0:4864:20::331 as permitted sender) client-ip=2607:f8b0:4864:20::331; Received: by mail-ot1-x331.google.com with SMTP id 21so6070193otj.11 for ; Wed, 18 Sep 2019 05:16:28 -0700 (PDT) X-Received: by 2002:a9d:6a8a:: with SMTP id l10mr2404903otq.97.1568808988159; Wed, 18 Sep 2019 05:16:28 -0700 (PDT) MIME-Version: 1.0 References: <10B7D7E9-3155-4FA0-90E0-BB6BE2C37B1B@wesleyan.edu> In-Reply-To: From: Anders Mortberg Date: Wed, 18 Sep 2019 14:16:16 +0200 Message-ID: Subject: Re: [HoTT] A question about the problem with regularity in CCHM cubical type theory To: Jasper Hugunin Cc: "Licata, Dan" , "HomotopyTypeTheory@googlegroups.com" Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Original-Sender: andersmortberg@gmail.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=P+poJGVA; spf=pass (google.com: domain of andersmortberg@gmail.com designates 2607:f8b0:4864:20::331 as permitted sender) smtp.mailfrom=andersmortberg@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com 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: , 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 operatio= n 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= this thread. > (You then need comp Glue to respect this equation, which appears impossib= le.) > > The way to get around it is, in my opinion, to add a separate type former= Box^i [ phi |-> T ] A for phi |- A =3D T(i1), satisfying the laws phi |- B= ox^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 i= s also apparently not possible in CCHM, but you now have the extra informat= ion that A is a line of types. (Using Box to turn an equivalence into a lin= e of types in the definition of comp Box is circular.) > > I've developed a notion of (regular) n-dimensional composition, which I t= hink might suffice to complete the argument. > If you call a notion of Box that satisfies Box^i [ phi |-> A ] A =3D A "r= egular Box's", then the problem can be reduced to saying that to give regul= ar 1-dimensional composition of regular 1-dimensional boxes, you need some = sort of "(doubly) regular 2-dimensional composition" for A, and in CCHM suc= h 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 suffic= e 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 composi= tion (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 f= or 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. > > =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,= then comp^i A [ phi |-> a ] a0 =3D a0. > We have regular composition for Glue types, but we don't have comp^i (Glu= e [ 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 reg= ular 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) f= or 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 o= ver two dimensions simultaneously. Write (i ?'[a] j) for this, where a give= s the location in the path. > However, my intuition tells me that while this two-dimensional regular co= mposition may be preserved by all the usual type formers, optimistically in= cluding Glue and Box, because the two-dimensional composition for Box will = have 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? The= re are six ways to compose along the edges of a cube, forming a hexagon tha= t 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:=3Dk) [ phi |-> t(i,j:=3Dk) ] t0), which a= grees with composing either right then up or up then right when T is degene= rate 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 straightforw= ardly. > > For each n-cube i_1, ..., i_n |- A, we have an n-dimensional regular comp= osition 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 composit= ion 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, w= hich 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 = the four corners given by coercing over i then j then k, coercing over i th= en j and k simultaneously, coercing over i and j simultaneously then coerci= ng 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 a= re 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), trea= ting j_0 =3D j_n =3D 1. > Extending this to =3D and o, if A, a are degenerate in i, then (i =3D 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 ex= plain 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 a= 0 : 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 th= e face maps j_k =3D 0 and j_k =3D 1 in the output, and one for when A, a ar= e 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 =3D j_n =3D 1, we get a = "zero-dimensional" composition operation, which should be taken to be the i= dentity. (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-dimen= sional 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 =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 |- B= ox^i1...^im _{j_1}..._{j_n-1} [ phi |-> T ] A for phi, i1, ..., im |- T, wi= th phi |- A =3D T(i_k :=3D 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 fo= r 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 uni= verse, 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)-dimension= al regular composition for pres will make this work. > > I have sketched on paper that composition for Glue and Box are regular, b= ut that is already pushing the limits of my confidence in paper calculation= s. > 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 wrote: >> >> Wow! I read that pretty closely and couldn=E2=80=99t find a problem. Tha= t is 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 d= egenerate, 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=E2=80=99s still a problem with using those glue ty= pes 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=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. 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 C= CHM paper you linked, reproduced below. >> As you know, the single potential issue is that we need pres of a degene= rate filling problem and function to be reflexivity. I claim that this hold= s by regularity of composition in T and A, partly as a consequence of the f= act 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 =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 t= hat 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 = (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 comp^i A [ psi |-> f b, j =3D 1 |-> f (fill^i T [ psi |-> t = ] t0) ] (f t0) =3D comp^i A [ psi |-> f b, j =3D 1 |-> f t0 ] (f t0) = =3D 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 i= n the delta face of equiv) >> a1 =3D a1' (the only dependence on j is via (alpha j), but alpha =3D ome= ga =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 = Orton-Pitts and Cartesian cubes. >> >> Best regards, >> - Jasper Hugunin >> >> On Mon, Sep 16, 2019 at 12:18 PM Licata, Dan wrot= e: >>> >>> Hi Jasper, >>> >>> It would help me follow the discussion if you could say a little more a= bout (a) which version of composition for Glue exactly you mean (because th= ere 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 reasoning for why you th= ink 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 is= sue is with the =E2=80=98pres=E2=80=99 path omega, which via the equiv oper= ation ends up in alpha, so the system in a1 may not be degenerate even if t= he 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 with the adjust_com operation on page 20,= which is later used for aligning (in that case beta is (forall i phi)). T= he potential issue is that adjust_com uses a *filler*, not just a compositi= on from 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= connections, so it=E2=80=99s a little different, but I think there still h= as to be a dependence on z for it to even type check =E2=80=94 it should co= me up because of the connection term that is substituted into the type of t= he composition problem. So I=E2=80=99d guess there is still a problem in t= he 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 wrote: >>> > >>> > This doesn't seem right; as far as I can tell, composition for Glue t= ypes 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 b= y >>> > Sattler and Orton around 2016 that one can factor out this step in ou= r >>> > 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 considerabl= e >>> > 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 Andre= w >>> > Swan is starting as a postdoc over in Baker Hall in October, so he ca= n >>> > 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, 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 alre= ady explained 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 univ= erse 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 reg= ularity 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 arg= ument. >>> > >> >>> > >> Context: >>> > >> I've been studying and using CCHM cubical type theory recently, an= d 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 m= ailing list, the definition of composition for the universe was found to no= t 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 a= lso degenerate in that direction, reduces to just the bottom of the box. Th= is 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 |-> eq= uiv^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, s= end an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. >>> > > To view this discussion on the web visit https://groups.google.com/= d/msgid/HomotopyTypeTheory/CAGTS-a9oS0CQDGKgj7ghCh8%2BZwAcAefiTg4JJVHemV3HU= PcPEg%40mail.gmail.com. >>> > >>> > -- >>> > You received this message because you are subscribed to the Google Gr= oups "Homotopy Type Theory" group. >>> > To unsubscribe from this group and stop receiving emails from it, sen= d 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%3Df= vOQ%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/msgi= d/HomotopyTypeTheory/CAGTS-a8E03C3BMEwi-T4qjet4EbCgnePhR3Ffa1MepxNmtZoUA%40= mail.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/CAMWCpp%3DEMvH%2BXtRn7AfyjRDjmiwxfML2JQqKyPjXAhM%2BM2vcj= w%40mail.gmail.com.