* [HoTT] (Beginner's question) Uses of HITs beyond homotopy theory @ 2019-08-08 18:32 Timothy Carstens 2019-08-08 18:52 ` [HoTT] " Niels van der Weide 2019-08-08 20:18 ` [HoTT] " Steve Awodey 0 siblings, 2 replies; 6+ messages in thread From: Timothy Carstens @ 2019-08-08 18:32 UTC (permalink / raw) To: Homotopy Type Theory [-- Attachment #1: Type: text/plain, Size: 1127 bytes --] Sorry for the broad & naive question. I'm a geometer by training but have been working in compsci for most of my career (with lots of time spent in Coq verifying programs). I've got a naive question that I hope isn't too inappropriate for this list: can anyone suggest some papers that show applications of HITs? I'm embarrassed to admit it, but I don't know any applications outside of synthetic homotopy theory and higher categories. Perhaps categorical semantics? But even still I'm not personally aware of any applied results from that domain (contrast with operational semantics; but I am extremely ignorant, so please correct me!) All my best and apologies in advance if this is off-topic for this list, -t -- 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/CAJGt_zG%2B04Rfbs_py%3DPYkubbwzeYb0TRhhfek-RT663uVUo%3D-A%40mail.gmail.com. [-- Attachment #2: Type: text/html, Size: 1589 bytes --] ^ permalink raw reply [flat|nested] 6+ messages in thread
* [HoTT] Re: (Beginner's question) Uses of HITs beyond homotopy theory 2019-08-08 18:32 [HoTT] (Beginner's question) Uses of HITs beyond homotopy theory Timothy Carstens @ 2019-08-08 18:52 ` Niels van der Weide 2019-08-08 20:18 ` [HoTT] " Steve Awodey 1 sibling, 0 replies; 6+ messages in thread From: Niels van der Weide @ 2019-08-08 18:52 UTC (permalink / raw) To: Homotopy Type Theory [-- Attachment #1.1: Type: text/plain, Size: 1803 bytes --] Some established applications of HITs outside of synthetic homotopy theory: - Partiality monad, see "Partiality Revisited" by Altenkirch, Danielsson, and Kraus - Type Theory in Type Theory, see 'Type Theory in Type Theory with Quotient Inductive Inductive Types' and 'Normalization by evaluation for dependent types' by Altenkirch and Kaposi - Free algebraic structures, see HoTT book 6.11 and the paper "Finite Sets in Homotopy Type Theory" by Frumin, Geuvers, Gondelman, Van der Weide - Patch theory, see 'Homotopical Patch Theory' by Angiuli, Morehouse, Licata, and Harper On Thursday, August 8, 2019 at 8:33:06 PM UTC+2, Timothy Carstens wrote: > > Sorry for the broad & naive question. I'm a geometer by training but have > been working in compsci for most of my career (with lots of time spent in > Coq verifying programs). > > I've got a naive question that I hope isn't too inappropriate for this > list: can anyone suggest some papers that show applications of HITs? I'm > embarrassed to admit it, but I don't know any applications outside of > synthetic homotopy theory and higher categories. > > Perhaps categorical semantics? But even still I'm not personally aware of > any applied results from that domain (contrast with operational semantics; > but I am extremely ignorant, so please correct me!) > > All my best and apologies in advance if this is off-topic for this list, > -t > > -- 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/bc0fb45d-fe21-4380-bfcb-70cc58fbeef2%40googlegroups.com. [-- Attachment #1.2: Type: text/html, Size: 2446 bytes --] ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [HoTT] (Beginner's question) Uses of HITs beyond homotopy theory 2019-08-08 18:32 [HoTT] (Beginner's question) Uses of HITs beyond homotopy theory Timothy Carstens 2019-08-08 18:52 ` [HoTT] " Niels van der Weide @ 2019-08-08 20:18 ` Steve Awodey 2019-08-08 21:49 ` Michael Shulman 1 sibling, 1 reply; 6+ messages in thread From: Steve Awodey @ 2019-08-08 20:18 UTC (permalink / raw) To: Timothy Carstens; +Cc: Homotopy Type Theory [-- Attachment #1: Type: text/plain, Size: 1924 bytes --] quotients by equivalence relations. see HoTT Book 6.10 > On Aug 8, 2019, at 2:32 PM, Timothy Carstens <intoverflow@gmail.com> wrote: > > Sorry for the broad & naive question. I'm a geometer by training but have been working in compsci for most of my career (with lots of time spent in Coq verifying programs). > > I've got a naive question that I hope isn't too inappropriate for this list: can anyone suggest some papers that show applications of HITs? I'm embarrassed to admit it, but I don't know any applications outside of synthetic homotopy theory and higher categories. > > Perhaps categorical semantics? But even still I'm not personally aware of any applied results from that domain (contrast with operational semantics; but I am extremely ignorant, so please correct me!) > > All my best and apologies in advance if this is off-topic for this list, > -t > > > -- > 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 <mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com>. > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAJGt_zG%2B04Rfbs_py%3DPYkubbwzeYb0TRhhfek-RT663uVUo%3D-A%40mail.gmail.com <https://groups.google.com/d/msgid/HomotopyTypeTheory/CAJGt_zG%2B04Rfbs_py%3DPYkubbwzeYb0TRhhfek-RT663uVUo%3D-A%40mail.gmail.com?utm_medium=email&utm_source=footer>. -- 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/728FA1EA-014C-4242-8B34-33A17D7B9208%40gmail.com. [-- Attachment #2: Type: text/html, Size: 3038 bytes --] ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [HoTT] (Beginner's question) Uses of HITs beyond homotopy theory 2019-08-08 20:18 ` [HoTT] " Steve Awodey @ 2019-08-08 21:49 ` Michael Shulman 2019-08-08 22:09 ` Timothy Carstens 0 siblings, 1 reply; 6+ messages in thread From: Michael Shulman @ 2019-08-08 21:49 UTC (permalink / raw) To: Timothy Carstens; +Cc: Homotopy Type Theory More generally, all colimits other than coproducts are HITs (of the "non-recursive" variety). This includes both homotopy colimits and ordinary colimits of sets (obtained by 0-truncating homotopy colimits). Having colimits of sets is fairly essential for nearly all ordinary set-based mathematics, even for people who don't care about homotopy theory or higher category theory in the slightest. There aren't really papers specifically about this, because it's so vast, and because there's not much to say other than the observation that colimits exist, since at that point you can just appeal to the long-known fact that once the category of sets satisfies certain basic properties (Lawvere's "Elementary Theory of the Category of Sets") it suffices as a basis on which to develop a large amount of mathematics. The verification of these axioms in HoTT with HITs can be found in section 10.1 of the HoTT Book. (Before HITs, people formalizing set-based mathematics in type theory used "setoids" to mimic quotients and other colimits.) Beyond this, in set-based mathematics HITs are used to construct free algebraic structures, as Niels said. Some free algebraic structures (free monoids, free groups, free rings, etc.) can be constructed based only on the axioms of ETCS, but for fancier (and in particular, infinitary) algebraic structures one needs more. In fact there are algebraic theories for which free algebraic structures cannot be constructed in ZF (at least, under a large cardinal assumption): the idea is to use a theory to encode the existence of large regular cardinals, which cannot be constructed in ZF (see Blass's paper "Words, free algebras, and coequalizers"). But HITs suffice to construct even free infinitary algebras of this sort; see e.g. section 9 of my paper with Peter Lumsdaine, "Semantics of higher inductive types". Thus, HITs can be useful for doing (universal) algebra constructively, where here "constructively" can even mean "with classical logic but without the axiom of choice". On Thu, Aug 8, 2019 at 1:18 PM Steve Awodey <steveawodey@gmail.com> wrote: > > quotients by equivalence relations. > see HoTT Book 6.10 > > On Aug 8, 2019, at 2:32 PM, Timothy Carstens <intoverflow@gmail.com> wrote: > > Sorry for the broad & naive question. I'm a geometer by training but have been working in compsci for most of my career (with lots of time spent in Coq verifying programs). > > I've got a naive question that I hope isn't too inappropriate for this list: can anyone suggest some papers that show applications of HITs? I'm embarrassed to admit it, but I don't know any applications outside of synthetic homotopy theory and higher categories. > > Perhaps categorical semantics? But even still I'm not personally aware of any applied results from that domain (contrast with operational semantics; but I am extremely ignorant, so please correct me!) > > All my best and apologies in advance if this is off-topic for this list, > -t > > > -- > 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/CAJGt_zG%2B04Rfbs_py%3DPYkubbwzeYb0TRhhfek-RT663uVUo%3D-A%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/728FA1EA-014C-4242-8B34-33A17D7B9208%40gmail.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/CAOvivQyYyPzpT0Y04vi27gdg6Un147RkJ4tyPcCRC_Tsed5PMA%40mail.gmail.com. ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [HoTT] (Beginner's question) Uses of HITs beyond homotopy theory 2019-08-08 21:49 ` Michael Shulman @ 2019-08-08 22:09 ` Timothy Carstens 2019-08-09 10:36 ` Thorsten Altenkirch 0 siblings, 1 reply; 6+ messages in thread From: Timothy Carstens @ 2019-08-08 22:09 UTC (permalink / raw) Cc: Homotopy Type Theory [-- Attachment #1: Type: text/plain, Size: 4999 bytes --] Thank you for the excellent replies! It looks like I was struggling with a lack of imagination while the answer was staring me right in the face. On Thu, Aug 8, 2019 at 2:49 PM Michael Shulman <shulman@sandiego.edu> wrote: > More generally, all colimits other than coproducts are HITs (of the > "non-recursive" variety). This includes both homotopy colimits and > ordinary colimits of sets (obtained by 0-truncating homotopy > colimits). Having colimits of sets is fairly essential for nearly all > ordinary set-based mathematics, even for people who don't care about > homotopy theory or higher category theory in the slightest. There > aren't really papers specifically about this, because it's so vast, > and because there's not much to say other than the observation that > colimits exist, since at that point you can just appeal to the > long-known fact that once the category of sets satisfies certain basic > properties (Lawvere's "Elementary Theory of the Category of Sets") it > suffices as a basis on which to develop a large amount of mathematics. > The verification of these axioms in HoTT with HITs can be found in > section 10.1 of the HoTT Book. (Before HITs, people formalizing > set-based mathematics in type theory used "setoids" to mimic quotients > and other colimits.) > > Beyond this, in set-based mathematics HITs are used to construct free > algebraic structures, as Niels said. Some free algebraic structures > (free monoids, free groups, free rings, etc.) can be constructed based > only on the axioms of ETCS, but for fancier (and in particular, > infinitary) algebraic structures one needs more. In fact there are > algebraic theories for which free algebraic structures cannot be > constructed in ZF (at least, under a large cardinal assumption): the > idea is to use a theory to encode the existence of large regular > cardinals, which cannot be constructed in ZF (see Blass's paper > "Words, free algebras, and coequalizers"). But HITs suffice to > construct even free infinitary algebras of this sort; see e.g. section > 9 of my paper with Peter Lumsdaine, "Semantics of higher inductive > types". Thus, HITs can be useful for doing (universal) algebra > constructively, where here "constructively" can even mean "with > classical logic but without the axiom of choice". > > On Thu, Aug 8, 2019 at 1:18 PM Steve Awodey <steveawodey@gmail.com> wrote: > > > > quotients by equivalence relations. > > see HoTT Book 6.10 > > > > On Aug 8, 2019, at 2:32 PM, Timothy Carstens <intoverflow@gmail.com> > wrote: > > > > Sorry for the broad & naive question. I'm a geometer by training but > have been working in compsci for most of my career (with lots of time spent > in Coq verifying programs). > > > > I've got a naive question that I hope isn't too inappropriate for this > list: can anyone suggest some papers that show applications of HITs? I'm > embarrassed to admit it, but I don't know any applications outside of > synthetic homotopy theory and higher categories. > > > > Perhaps categorical semantics? But even still I'm not personally aware > of any applied results from that domain (contrast with operational > semantics; but I am extremely ignorant, so please correct me!) > > > > All my best and apologies in advance if this is off-topic for this list, > > -t > > > > > > -- > > 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/CAJGt_zG%2B04Rfbs_py%3DPYkubbwzeYb0TRhhfek-RT663uVUo%3D-A%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/728FA1EA-014C-4242-8B34-33A17D7B9208%40gmail.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/CAOvivQyYyPzpT0Y04vi27gdg6Un147RkJ4tyPcCRC_Tsed5PMA%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/CAJGt_zH1qWjaQYy-jOGfuxm--cLw3AJ6y6WPheqHmA8Dr1B%2Bww%40mail.gmail.com. [-- Attachment #2: Type: text/html, Size: 6890 bytes --] ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [HoTT] (Beginner's question) Uses of HITs beyond homotopy theory 2019-08-08 22:09 ` Timothy Carstens @ 2019-08-09 10:36 ` Thorsten Altenkirch 0 siblings, 0 replies; 6+ messages in thread From: Thorsten Altenkirch @ 2019-08-09 10:36 UTC (permalink / raw) To: Timothy Carstens; +Cc: Homotopy Type Theory [-- Attachment #1: Type: text/plain, Size: 7798 bytes --] I think it is an excellent question. However, looking at the examples it may seem that we only need QITs, that is set-truncated HITs. However, this is not true when you are dealing with higher structures that arise naturally like the type of sets. For example when you define the integers as a quotient, or nicer as a QIT, you can only eliminate into types that are sets, for example you cannot define a function from the Integers into Set. However, this can be addressed by replacing set-truncation with a coherence law, in this case you basically say that integers have 0 and suc and suc is an equivalence. You can prove that the HIT constructed by these principles is a Set (this is actually harder than it seems) – Luis Soccola and I have recently written a paper about this (need to put it on arxiv). Another example is the intrinsic presentation of type theory as the initial Category with Families which was already mentioned. Again the problem is that you need to set-truncate but then you cannot even define the set-interpretation. This can be again addressed by adding some coherence laws (need to check the details) and you get a coherent version of CWFs which enable us to eliminate into any 1-type, including the universe of sets. Thorsten From: <homotopytypetheory@googlegroups.com> on behalf of Timothy Carstens <intoverflow@gmail.com> Date: Thursday, 8 August 2019 at 23:09 Cc: Homotopy Type Theory <homotopytypetheory@googlegroups.com> Subject: Re: [HoTT] (Beginner's question) Uses of HITs beyond homotopy theory Thank you for the excellent replies! It looks like I was struggling with a lack of imagination while the answer was staring me right in the face. On Thu, Aug 8, 2019 at 2:49 PM Michael Shulman <shulman@sandiego.edu<mailto:shulman@sandiego.edu>> wrote: More generally, all colimits other than coproducts are HITs (of the "non-recursive" variety). This includes both homotopy colimits and ordinary colimits of sets (obtained by 0-truncating homotopy colimits). Having colimits of sets is fairly essential for nearly all ordinary set-based mathematics, even for people who don't care about homotopy theory or higher category theory in the slightest. There aren't really papers specifically about this, because it's so vast, and because there's not much to say other than the observation that colimits exist, since at that point you can just appeal to the long-known fact that once the category of sets satisfies certain basic properties (Lawvere's "Elementary Theory of the Category of Sets") it suffices as a basis on which to develop a large amount of mathematics. The verification of these axioms in HoTT with HITs can be found in section 10.1 of the HoTT Book. (Before HITs, people formalizing set-based mathematics in type theory used "setoids" to mimic quotients and other colimits.) Beyond this, in set-based mathematics HITs are used to construct free algebraic structures, as Niels said. Some free algebraic structures (free monoids, free groups, free rings, etc.) can be constructed based only on the axioms of ETCS, but for fancier (and in particular, infinitary) algebraic structures one needs more. In fact there are algebraic theories for which free algebraic structures cannot be constructed in ZF (at least, under a large cardinal assumption): the idea is to use a theory to encode the existence of large regular cardinals, which cannot be constructed in ZF (see Blass's paper "Words, free algebras, and coequalizers"). But HITs suffice to construct even free infinitary algebras of this sort; see e.g. section 9 of my paper with Peter Lumsdaine, "Semantics of higher inductive types". Thus, HITs can be useful for doing (universal) algebra constructively, where here "constructively" can even mean "with classical logic but without the axiom of choice". On Thu, Aug 8, 2019 at 1:18 PM Steve Awodey <steveawodey@gmail.com<mailto:steveawodey@gmail.com>> wrote: > > quotients by equivalence relations. > see HoTT Book 6.10 > > On Aug 8, 2019, at 2:32 PM, Timothy Carstens <intoverflow@gmail.com<mailto:intoverflow@gmail.com>> wrote: > > Sorry for the broad & naive question. I'm a geometer by training but have been working in compsci for most of my career (with lots of time spent in Coq verifying programs). > > I've got a naive question that I hope isn't too inappropriate for this list: can anyone suggest some papers that show applications of HITs? I'm embarrassed to admit it, but I don't know any applications outside of synthetic homotopy theory and higher categories. > > Perhaps categorical semantics? But even still I'm not personally aware of any applied results from that domain (contrast with operational semantics; but I am extremely ignorant, so please correct me!) > > All my best and apologies in advance if this is off-topic for this list, > -t > > > -- > 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<mailto:HomotopyTypeTheory%2Bunsubscribe@googlegroups.com>. > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAJGt_zG%2B04Rfbs_py%3DPYkubbwzeYb0TRhhfek-RT663uVUo%3D-A%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<mailto:HomotopyTypeTheory%2Bunsubscribe@googlegroups.com>. > To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/728FA1EA-014C-4242-8B34-33A17D7B9208%40gmail.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<mailto:HomotopyTypeTheory%2Bunsubscribe@googlegroups.com>. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAOvivQyYyPzpT0Y04vi27gdg6Un147RkJ4tyPcCRC_Tsed5PMA%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<mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com>. To view this discussion on the web visit https://groups.google.com/d/msgid/HomotopyTypeTheory/CAJGt_zH1qWjaQYy-jOGfuxm--cLw3AJ6y6WPheqHmA8Dr1B%2Bww%40mail.gmail.com<https://groups.google.com/d/msgid/HomotopyTypeTheory/CAJGt_zH1qWjaQYy-jOGfuxm--cLw3AJ6y6WPheqHmA8Dr1B%2Bww%40mail.gmail.com?utm_medium=email&utm_source=footer>. This message and any attachment are intended solely for the addressee and may contain confidential information. If you have received this message in error, please contact the sender and delete the email and attachment. Any views or opinions expressed by the author of this email do not necessarily reflect the views of the University of Nottingham. Email communications with the University of Nottingham may be monitored where permitted by law. -- 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/85B0463F-8B1E-4677-924D-05162484B926%40nottingham.ac.uk. [-- Attachment #2: Type: text/html, Size: 12285 bytes --] ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2019-08-09 10:36 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-08-08 18:32 [HoTT] (Beginner's question) Uses of HITs beyond homotopy theory Timothy Carstens 2019-08-08 18:52 ` [HoTT] " Niels van der Weide 2019-08-08 20:18 ` [HoTT] " Steve Awodey 2019-08-08 21:49 ` Michael Shulman 2019-08-08 22:09 ` Timothy Carstens 2019-08-09 10:36 ` Thorsten Altenkirch
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).