*[HoTT] Recovering an equivalence from univalence in cubical type theory@ 2019-09-18 15:42 Michael Shulman2019-09-18 16:15 ` Licata, Dan 0 siblings, 1 reply; 5+ messages in thread From: Michael Shulman @ 2019-09-18 15:42 UTC (permalink / raw) To: HomotopyTypeTheory 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=B, 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 *judgmentally* 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 Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQzzSXNHs%2BzbPQTyHEuU53aHXJ0sPe4pr%2Byf0ahLGvUpVA%40mail.gmail.com. ^ permalink raw reply [flat|nested] 5+ messages in thread

*Re: [HoTT] Recovering an equivalence from univalence in cubical type theory2019-09-18 15:42 [HoTT] Recovering an equivalence from univalence in cubical type theory Michael Shulman@ 2019-09-18 16:15 ` Licata, Dan2019-09-18 19:23 ` Michael Shulman 0 siblings, 1 reply; 5+ messages in thread From: Licata, Dan @ 2019-09-18 16:15 UTC (permalink / raw) To: Michael Shulman;+Cc:HomotopyTypeTheory In ABCFHL, even the function fst(coe(ua(e))) : A -> B is only path-equal to fst(e) : A -> B. If I recall correctly, the issue is that composition in the Glue type that you use to implement ua doesn’t judgementally give you f; instead there is some morally-the-identity-composition (that would cancel with regularity) that gets stuck in. This is because the general algorithm for composition in the glue type has to coerce in the “base” of the glue type (B in Glue [alpha -> T] B), which in the case of ua(e) = Glue [x = 0 -> (A,e), x=1 -> (B,id)] B is degenerate in x, but in general might not be. I don’t recall any cubical type theories solving this, but I don’t 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 <shulman@sandiego.edu> 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=B, 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 *judgmentally* > 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 Groups "Homotopy Type Theory" group. > To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQzzSXNHs%2BzbPQTyHEuU53aHXJ0sPe4pr%2Byf0ahLGvUpVA%40mail.gmail.com. -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/1DF8E802-2959-4BEF-A85A-3C6E5E7B9595%40wesleyan.edu. ^ permalink raw reply [flat|nested] 5+ messages in thread

*Re: [HoTT] Recovering an equivalence from univalence in cubical type theory2019-09-18 16:15 ` Licata, Dan@ 2019-09-18 19:23 ` Michael Shulman2019-09-18 20:35 ` Evan Cavallo 0 siblings, 1 reply; 5+ messages in thread From: Michael Shulman @ 2019-09-18 19:23 UTC (permalink / raw) To: Licata, Dan;+Cc:HomotopyTypeTheory Thanks, that's very interesting! The reason I ask is that I was wondering to what extent the type "A=B" 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 <dlicata@wesleyan.edu> wrote: > > In ABCFHL, even the function fst(coe(ua(e))) : A -> B is only path-equal to fst(e) : A -> B. If I recall correctly, the issue is that composition in the Glue type that you use to implement ua doesn’t judgementally give you f; instead there is some morally-the-identity-composition (that would cancel with regularity) that gets stuck in. This is because the general algorithm for composition in the glue type has to coerce in the “base” of the glue type (B in Glue [alpha -> T] B), which in the case of ua(e) = Glue [x = 0 -> (A,e), x=1 -> (B,id)] B is degenerate in x, but in general might not be. > > I don’t recall any cubical type theories solving this, but I don’t 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 <shulman@sandiego.edu> 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=B, 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 *judgmentally* > > 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 Groups "Homotopy Type Theory" group. > > To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQzzSXNHs%2BzbPQTyHEuU53aHXJ0sPe4pr%2Byf0ahLGvUpVA%40mail.gmail.com. > > -- > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. > To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/1DF8E802-2959-4BEF-A85A-3C6E5E7B9595%40wesleyan.edu. -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQz_wY2CVp9Y5caEehVotR7w7D%3DoP6jpoUxm463pNdNHuA%40mail.gmail.com. ^ permalink raw reply [flat|nested] 5+ messages in thread

*Re: [HoTT] Recovering an equivalence from univalence in cubical type theory2019-09-18 19:23 ` Michael Shulman@ 2019-09-18 20:35 ` Evan Cavallo2019-09-19 8:20 ` Anders Mortberg 0 siblings, 1 reply; 5+ messages in thread From: Evan Cavallo @ 2019-09-18 20:35 UTC (permalink / raw) To: Michael Shulman;+Cc:Licata, Dan, HomotopyTypeTheory [-- Attachment #1: Type: text/plain, Size: 6392 bytes --] The definition of univalence for BCH cubical sets in https://arxiv.org/abs/1710.10941 does satisfy the property that fst(coe(ua(e))) = 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 function 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 make sense of this in a structural cubical set model because the property of being degenerate in a given variable isn't stable under diagonal substitution. Evan 2019年9月18日(水) 15:23 Michael Shulman <shulman@sandiego.edu>: > Thanks, that's very interesting! > > The reason I ask is that I was wondering to what extent the type "A=B" > 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 <dlicata@wesleyan.edu> wrote: > > > > In ABCFHL, even the function fst(coe(ua(e))) : A -> B is only path-equal > to fst(e) : A -> B. If I recall correctly, the issue is that composition > in the Glue type that you use to implement ua doesn’t judgementally give > you f; instead there is some morally-the-identity-composition (that would > cancel with regularity) that gets stuck in. This is because the general > algorithm for composition in the glue type has to coerce in the “base” of > the glue type (B in Glue [alpha -> T] B), which in the case of ua(e) = Glue > [x = 0 -> (A,e), x=1 -> (B,id)] B is degenerate in x, but in general might > not be. > > > > I don’t recall any cubical type theories solving this, but I don’t > 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 <shulman@sandiego.edu> > 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=B, 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 *judgmentally* > > > 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 > Groups "Homotopy Type Theory" group. > > > To unsubscribe from this group and stop receiving emails from it, send > an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > > > To view this discussion on the web visit > https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQzzSXNHs%2BzbPQTyHEuU53aHXJ0sPe4pr%2Byf0ahLGvUpVA%40mail.gmail.com > . > > > > -- > > You received this message because you are subscribed to the Google > Groups "Homotopy Type Theory" group. > > To unsubscribe from this group and stop receiving emails from it, send > an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/HomotopyTypeTheory/1DF8E802-2959-4BEF-A85A-3C6E5E7B9595%40wesleyan.edu > . > > -- > You received this message because you are subscribed to the Google Groups > "Homotopy Type Theory" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to HomotopyTypeTheory+unsubscribe@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/HomotopyTypeTheory/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/msgid/HomotopyTypeTheory/CAFcn59ZLBcQMwJUMnnDKq3ewf582x4z4aqce4xR16xzcQeRxgA%40mail.gmail.com. [-- Attachment #2: Type: text/html, Size: 8303 bytes --] ^ permalink raw reply [flat|nested] 5+ messages in thread

*2019-09-18 20:35 ` Evan CavalloRe: [HoTT] Recovering an equivalence from univalence in cubical type theory@ 2019-09-19 8:20 ` Anders Mortberg0 siblings, 0 replies; 5+ messages in thread From: Anders Mortberg @ 2019-09-19 8:20 UTC (permalink / raw) To: Evan Cavallo;+Cc:Michael Shulman, Licata, Dan, HomotopyTypeTheory 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 <evancavallo@gmail.com> wrote: > > The definition of univalence for BCH cubical sets in https://arxiv.org/abs/1710.10941 does satisfy the property that fst(coe(ua(e))) = 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 function 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 make sense of this in a structural cubical set model because the property of being degenerate in a given variable isn't stable under diagonal substitution. > > Evan > > 2019年9月18日(水) 15:23 Michael Shulman <shulman@sandiego.edu>: >> >> Thanks, that's very interesting! >> >> The reason I ask is that I was wondering to what extent the type "A=B" >> 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 <dlicata@wesleyan.edu> wrote: >> > >> > In ABCFHL, even the function fst(coe(ua(e))) : A -> B is only path-equal to fst(e) : A -> B. If I recall correctly, the issue is that composition in the Glue type that you use to implement ua doesn’t judgementally give you f; instead there is some morally-the-identity-composition (that would cancel with regularity) that gets stuck in. This is because the general algorithm for composition in the glue type has to coerce in the “base” of the glue type (B in Glue [alpha -> T] B), which in the case of ua(e) = Glue [x = 0 -> (A,e), x=1 -> (B,id)] B is degenerate in x, but in general might not be. >> > >> > I don’t recall any cubical type theories solving this, but I don’t 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 <shulman@sandiego.edu> 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=B, 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 *judgmentally* >> > > 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 Groups "Homotopy Type Theory" group. >> > > To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. >> > > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQzzSXNHs%2BzbPQTyHEuU53aHXJ0sPe4pr%2Byf0ahLGvUpVA%40mail.gmail.com. >> > >> > -- >> > You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. >> > To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. >> > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/1DF8E802-2959-4BEF-A85A-3C6E5E7B9595%40wesleyan.edu. >> >> -- >> You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. >> To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. >> To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/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/msgid/HomotopyTypeTheory/CAFcn59ZLBcQMwJUMnnDKq3ewf582x4z4aqce4xR16xzcQeRxgA%40mail.gmail.com. -- You received this message because you are subscribed to the Google Groups "Homotopy Type Theory" group. To unsubscribe from this group and stop receiving emails from it, send an email to HomotopyTypeTheory+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAMWCppk7Dz6EEsf0R7pQhS9z2Y11jTMAhxo674G4%2BqEUqssM9A%40mail.gmail.com. ^ permalink raw reply [flat|nested] 5+ messages in thread

end of thread, back to indexThread overview:5+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-09-18 15:42 [HoTT] Recovering an equivalence from univalence in cubical type theory Michael Shulman 2019-09-18 16:15 ` Licata, Dan 2019-09-18 19:23 ` Michael Shulman 2019-09-18 20:35 ` Evan Cavallo 2019-09-19 8:20 ` Anders Mortberg

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