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-x438.google.com (mail-pf1-x438.google.com [IPv6:2607:f8b0:4864:20::438]) by inbox.vuxu.org (OpenSMTPD) with ESMTP id 64b9681e for ; Thu, 19 Sep 2019 08:21:11 +0000 (UTC) Received: by mail-pf1-x438.google.com with SMTP id v3sf1759435pff.4 for ; Thu, 19 Sep 2019 01:21:10 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1568881270; cv=pass; d=google.com; s=arc-20160816; b=Nju2mvNnC5AdvMsNqjlKnwnqtWmKh1l2+BZouXU13APWtOK9tzcaLl/bV5BsXdLWnI an516VzSWfkRn/sSoDR7EIHBB3pGiYAN684Wpc6nj0ZgJsb5CEXFuMQvLgrBLgCr+/sA mDQ3ZplbY1eEBOkmi7EQRVNg3ljATaUQznLpDvuWe7rSnAEGFWOFkhjiZZl5gAMvKFMc +ht8q/phwgp99R16uQARVnVbgp+mF0uX9Efq7HzgjntpOH+c86HObL24jlFxzbx9+IW1 Gkwq9rOJjr9KU8qGKvmWmOR8uY4uTK9xURV7yrClu1Oo3gikyVphn8z67JhfOPQRykU+ Hf7g== 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=Zgm1jmVZ1nzp073zFudgy89gWeLSC74c72OimyD0nNQ=; b=I3P0508usv0l8Mew5AQFoiU997NHftZSZYqFjvuuZY6ykVEkbXcTjtRV4osI/mdD7O RCz8V/QRBpuxqhbScM/OgaKHIS9zJW5eu8uoJCExqoeKErWjm4KdM5OoVKNkd0tunnb/ lSRujkNYejuu5ENiwWwIJkDMv5qgw2h/YbVf+M6gcWUV8iD///ZRiTB0CHUAxGoqreyN ummUEcf26qImqZXHxGx2DtDH4/SNmoVY5gy7NgRKEcGv01pFY1MpFkvpNopKEYPBLTeL KXjryx3F1eUlL2wiHijTphTvMMjzvcHc8BM88eetIXui/vdRAYssJbk0q6jaMS3oFG/V 7gxw== ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=WhphThyl; spf=pass (google.com: domain of andersmortberg@gmail.com designates 2607:f8b0:4864:20::32d 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=Zgm1jmVZ1nzp073zFudgy89gWeLSC74c72OimyD0nNQ=; b=SgEiJ7DKKLQrhi555h5MGN4Okw6TgefU2c4/EltQYJMrL/hMJj4doNf9gljrMh+ahQ RoI1B/JS+9zh1AaVz5DH7gU8QH8pwsmU5hPxk8WG9qcUFQvc0/x27+fVwu3Rmvk6ewBu +nJ6OfuheaI3xCF12ADaDLW7pE/shX5mfBUIg1U2QfMfpzZcQcNU6RVTN3058wWdATks wzpgpZUv5FR7YZPsPV4v78uNq8izVsapLj/W1IYvbnk8cYa15oHfDGOXN/PYvCyyblhX XehRznMrbBJgRHvsw0Rl3QYEYGnhTF1xEtYzSFSAFsP0SokfhmVd2NwaFQbPwc0+qXyc SoTA== 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=Zgm1jmVZ1nzp073zFudgy89gWeLSC74c72OimyD0nNQ=; b=GtE2ct+Dtke9j1Q1mAWCvZSwaS/ZwEqymcqLeey+jA+sJs5tgm5zRHGkyoJ8JDryH1 5AWhz7kaQRa9Wyw1VfTRPQuMWAbl5iBEX2x5TV0XElbLNXHnYOMn0TD+t8oBA+Ppz7Me 0an6bLs5jMtRYZsc6Zvr7IBXtN+rQrzVnGozaVvGfW2tlFGt3mLWYNvsE1XLBrAl+TY6 mCj1MjSfVfT9drjPtfG3JJ14FML8W7aWei/6/asusR1zUGF9m1uDy9SBqlB8omvRR4/U AdSgMhVttDywhWQSjzVGUV12U9RomQ55bm8MYg+4mPmwJzOfNVkdyvuNvoK/wxNikxdF QCIA== 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=Zgm1jmVZ1nzp073zFudgy89gWeLSC74c72OimyD0nNQ=; b=VdOcKMZ++VRZb6Ms1v/bX9s7aOSyhZCpPdE6bKzw7znQ+fK8Z92GqN3CK5RYmThshr ButqKZjmrthMp5cLe6TNEoUdw+FLTplUJ3kJzsjR6WmC6ZtQhdHpeD7c9dROTWPOKdH7 ksQK006OK7deRSPcZfGbe9VmhUwj1i3ovv8vkMQlGD7YKNIsm1xG4CR+CQP+XIFpzSvj brNhtfNs9j0n0FQFTUdcy95B+u6Ou43PhWQ7BzJEgExSkSCymIqtxavKcCIUYFMdiz4z vGaGqYc4dwggFG37yZPzL5v3Pdloj/OaLwz8YdpVtjPAaMa/TR8lcpLVT5hu3aPxqOB0 TWSw== Sender: homotopytypetheory@googlegroups.com X-Gm-Message-State: APjAAAWYkcUoxj2MeXaSaD0btC1JJux/OxvzvPTedWRB1ghdMXfDYsvA 5h51Um5jPwp02sPXkJruWSs= X-Google-Smtp-Source: APXvYqwD03E/u6YfIpwosq1r4rNfRPA/YnejouxP5FB7ciFXkFSexusp3zFSq2coQaV1l5tpn8MTag== X-Received: by 2002:a65:4549:: with SMTP id x9mr1195763pgr.170.1568881269720; Thu, 19 Sep 2019 01:21:09 -0700 (PDT) X-BeenThere: homotopytypetheory@googlegroups.com Received: by 2002:a17:902:b402:: with SMTP id x2ls827191plr.10.gmail; Thu, 19 Sep 2019 01:21:09 -0700 (PDT) X-Received: by 2002:a17:90a:26e3:: with SMTP id m90mr2348141pje.57.1568881269327; Thu, 19 Sep 2019 01:21:09 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1568881269; cv=none; d=google.com; s=arc-20160816; b=yL9Nmph0a/IAr+e5tOlujOT7F3t7WO7SN5josoIpR4OEuto4Rvbw83uXdBKL1VzLTf jUyJKs9kjv2XOsowjOge39dooxU7PYEaEXuvYKgrgFai485utKbPUA9J3qM5BttQcWWr JKmXZFaFXZUwHg6fa4/zagDcU8IyjN8V7JU8U0cfM8wBtQanB2dA/doh7iiutYrdrnOD Zk9YglO5a1pOdjbBVaqL8+6AcRmr+8z9OGbTBBpBkZjpyJuau8X8uL6Uwg1IVw4b9MMv N6fTI/xSPC7pR4psgjNCZgDpSrkB7As/JBHSWPK2NY9jPRZIA/6NSv2ikjqlU4qIBFhM iG1Q== 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=+jlcUazLd1hI2JLQ+OsLJEST2aPKwsDEPlmF0fCygyI=; b=MzK62ke6JhNQYVTRPf5hLp/9iBB//1XibxnMzdJHxURi+4t8PbHNmPUijNookK2zEM ADsA28Q3DfT4Uqt9T5k3jmTvEEH2gbpfeY7Ptx9kLEsu0/ktnTkXUo7cszr8DysqG5Hd lMqfnEQjHx2v3QbF3U0zwZbBAIB8w1M6RwJTdedcnGoI/ONXO3AbUNgBCO04wdItMP/K gfOrwimeL/KkDWWG6Y+h5rxiPWZQB0WCL2Xe+gd3aTZ6781NgbShJFXYY6NieNO1K5d1 MnQn2SmNgfChf+RXKfMoBar1xlU1e7zv0UFenCQX3UiMOER6rMtcf0YXugx6KU/4RyNA PWRA== ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20161025 header.b=WhphThyl; spf=pass (google.com: domain of andersmortberg@gmail.com designates 2607:f8b0:4864:20::32d as permitted sender) smtp.mailfrom=andersmortberg@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com Received: from mail-ot1-x32d.google.com (mail-ot1-x32d.google.com. [2607:f8b0:4864:20::32d]) by gmr-mx.google.com with ESMTPS id br8si800154pjb.3.2019.09.19.01.21.09 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 19 Sep 2019 01:21:09 -0700 (PDT) Received-SPF: pass (google.com: domain of andersmortberg@gmail.com designates 2607:f8b0:4864:20::32d as permitted sender) client-ip=2607:f8b0:4864:20::32d; Received: by mail-ot1-x32d.google.com with SMTP id k32so2334873otc.4 for ; Thu, 19 Sep 2019 01:21:09 -0700 (PDT) X-Received: by 2002:a05:6830:11c9:: with SMTP id v9mr5763237otq.125.1568881268879; Thu, 19 Sep 2019 01:21:08 -0700 (PDT) MIME-Version: 1.0 References: <1DF8E802-2959-4BEF-A85A-3C6E5E7B9595@wesleyan.edu> In-Reply-To: From: Anders Mortberg Date: Thu, 19 Sep 2019 10:20:56 +0200 Message-ID: Subject: Re: [HoTT] Recovering an equivalence from univalence in cubical type theory To: Evan Cavallo Cc: Michael Shulman , "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=WhphThyl; spf=pass (google.com: domain of andersmortberg@gmail.com designates 2607:f8b0:4864:20::32d 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: , All variations of CCHM that I know suffer from the same issue as ABCFHL for the reasons explained by Dan and Evan. Just as in the cartesian setting fst(coe(ua(e))) reduces to fst(e) composed with some "morally-the-identity-compositions" that don't disappear automatically. For example, in Cubical Agda fst(coe(ua(e))) reduces to fst(e) composed with a coe in a constant family that we have to take care of manually (we write transport for coe): https://github.com/agda/cubical/blob/master/Cubical/Foundations/Univalence.= agda#L149 In my experience this is rarely a problem in practice though. It's a bit annoying to insert these corrections manually in proofs, but it happens quite rarely and when doing concrete computations with closed types they disappear automatically. One difference I've noticed when doing synthetic homotopy theory in cubical type theory compared to HoTT is that we use equalities and univalence a lot more. The fact that we sometimes need to insert these correction terms is largely compensated by all of the useful primitives of cubical type theory that we have for working with equalities that are not available for equivalences (path abstraction/application, composition...). -- Anders On Wed, Sep 18, 2019 at 10:36 PM Evan Cavallo wrote= : > > The definition of univalence for BCH cubical sets in https://arxiv.org/ab= s/1710.10941 does satisfy the property that fst(coe(ua(e))) =3D fst(e) : A = -> B exactly. They note (Remark 7) that the definition can also be adjusted= so that transporting backwards along the equivalence gives the inverse fun= ction one can extract from e. > > Roughly, the problem Dan describes in ABCFHL---that the B in Glue [alpha = -> T] B can also depend on the direction of coercion x---can be avoided in = the BCH analogue of Glue by simply demanding that B is degenerate in x. The= restricted operation is still sufficient to prove univalence. We can't mak= e sense of this in a structural cubical set model because the property of b= eing degenerate in a given variable isn't stable under diagonal substitutio= n. > > Evan > > 2019=E5=B9=B49=E6=9C=8818=E6=97=A5(=E6=B0=B4) 15:23 Michael Shulman : >> >> Thanks, that's very interesting! >> >> The reason I ask is that I was wondering to what extent the type "A=3DB" >> can be regarded as "a coherent definition of equivalence" alongside >> half-adjoint equivalences, maps with contractible fibers, etc. Of >> course in some sense it is (even in Book HoTT), since it's equivalent >> to Equiv(A,B); but the question is how practical it is -- for >> instance, is it reasonable when doing synthetic homotopy theory to >> state all equivalences as equalities? >> >> In practice, the way we often construct equivalences is to make them >> out of a quasi-inverse pair, and all the standard definitions of >> equivalence have the nice property that they remember the two >> functions in the quasi-inverse pair judgmentally. My experience with >> the HoTT/Coq library is that this property is very useful, which is >> one reason we state equivalences as equivalences rather than making >> use of univalence to state them as equalities (another reason is that >> it avoids "univalence-redexes" all over the theory). Half-adjoint >> equivalences have the additional nice property that they remember one >> of the homotopies judgmentally, and if you're willing to prove the >> coherence 2-path by hand then they can be made to remember both of the >> homotopies; this seems to be much less useful than I thought it would >> be when we made the choice to use half-adjoint equivalences in the >> HoTT/Coq library, but it has proven useful at least once. >> >> So I was wondering to what extent equality of types in cubical type >> theory has properties like this. It sounds from what you say like the >> answer is "not much". This makes the lack of regularity seem like a >> rather more serious problem than I had previously thought. >> >> On Wed, Sep 18, 2019 at 9:15 AM Licata, Dan wrote= : >> > >> > In ABCFHL, even the function fst(coe(ua(e))) : A -> B is only path-equ= al to fst(e) : A -> B. If I recall correctly, the issue is that compositio= n in the Glue type that you use to implement ua doesn=E2=80=99t judgemental= ly give you f; instead there is some morally-the-identity-composition (tha= t would cancel with regularity) that gets stuck in. This is because the ge= neral algorithm for composition in the glue type has to coerce in the =E2= =80=9Cbase=E2=80=9D of the glue type (B in Glue [alpha -> T] B), which in t= he case of ua(e) =3D Glue [x =3D 0 -> (A,e), x=3D1 -> (B,id)] B is degenera= te in x, but in general might not be. >> > >> > I don=E2=80=99t recall any cubical type theories solving this, but I d= on=E2=80=99t remember the details of all of the other variations that have = been explored well enough to say for sure. >> > >> > > On Sep 18, 2019, at 11:42 AM, Michael Shulman = wrote: >> > > >> > > Let Equiv(A,B) denote the type of half-adjoint equivalences, so that >> > > an e:Equiv(A,B) consists of five data: a function A -> B, a function= B >> > > -> A, two homotopies, and a coherence 2-path. Using univalence, we >> > > can make e into an identification ua(e) : A=3DB, and then back into = an >> > > equivalence coe(ua(e)) : Equiv(A,B), which is typally equal to e. >> > > >> > > Now we might wonder whether coe(ua(e)) might be in fact *judgmentall= y* >> > > equal to e; or at least whether this might be true of some, if not >> > > all, of its five components. In Book HoTT this is clearly not the >> > > case, since univalence is posited as an axiom about which we know >> > > nothing else. But what about cubical type theories? Can any of the >> > > components of an equivalence e be recovered, up to judgmental >> > > equality, from coe(ua(e))? (My guess would be that at least the >> > > function A -> B, and probably also the function B -> A, can be >> > > recovered, but perhaps not more.) >> > > >> > > -- >> > > You received this message because you are subscribed to the Google G= roups "Homotopy Type Theory" group. >> > > To unsubscribe from this group and stop receiving emails from it, se= nd an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. >> > > To view this discussion on the web visit https://groups.google.com/d= /msgid/HomotopyTypeTheory/CAOvivQzzSXNHs%2BzbPQTyHEuU53aHXJ0sPe4pr%2Byf0ahL= GvUpVA%40mail.gmail.com. >> > >> > -- >> > 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/m= sgid/HomotopyTypeTheory/1DF8E802-2959-4BEF-A85A-3C6E5E7B9595%40wesleyan.edu= . >> >> -- >> You received this message because you are subscribed to the Google Group= s "Homotopy Type Theory" group. >> To unsubscribe from this group and stop receiving emails from it, send a= n email to HomotopyTypeTheory+unsubscribe@googlegroups.com. >> To view this discussion on the web visit https://groups.google.com/d/msg= id/HomotopyTypeTheory/CAOvivQz_wY2CVp9Y5caEehVotR7w7D%3DoP6jpoUxm463pNdNHuA= %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/CAFcn59ZLBcQMwJUMnnDKq3ewf582x4z4aqce4xR16xzcQeRxgA%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/CAMWCppk7Dz6EEsf0R7pQhS9z2Y11jTMAhxo674G4%2BqEUqssM9A%40= mail.gmail.com.