Discussion of Homotopy Type Theory and Univalent Foundations
 help / color / Atom feed
From: Jasper Hugunin <jasperh@cs.washington.edu>
To: HomotopyTypeTheory@googlegroups.com
Subject: Re: [HoTT] Re: A question about the problem with regularity in CCHM cubical type theory
Date: Sun, 15 Sep 2019 18:38:57 -0400
Message-ID: <CAGTS-a9XATMbfyyp00M8kqiEoFyj7XsxahMa3AdzXth_=LbTiA@mail.gmail.com> (raw)
In-Reply-To: <16b3b92f-069b-468c-94f8-f3859e152338@googlegroups.com>

[-- Attachment #1: Type: text/plain, Size: 5326 bytes --]

In CCHM, my understanding is that composition for Glue [ phi |-> (T, f) ] A
is actually regular, and reduces to composition in T on (forall i. phi),
assuming composition is regular for A and T.
The regularity does seem to fail in ABCFHL, as you pointed out Anders, but
is perhaps repairable.

What Carlo told me was that the problem is getting composition for Glue [
phi |-> (T, f) ] A which is regular, reduces to composition in T on (forall
i. phi), *and* reduces to composition in A when (T, f) = (A, equivRefl).
We get the first two but not the third in CCHM.

The problem as Carlo explained it was that given a square of types i, j |-
A and a point a : A (i0) (j0), we can prove Path (coe^i A o coe^j A) (coe^j
A o coe^i A) (coercing around the square in right then up vs up then
right), and (assuming regularity for A), we can take this to be degenerate
when A is degenerate in i, or give a different path which is degenerate
when A is degenerate in j, but constructing a path which is degenerate when
A is degenerate in i or j is elusive.

I have an idea for how to add new terms/operations (a sort of
generalization of comp) such that such a path is constructible, but I
haven't yet checked that there is a univalent universe with these more
general operations.
I also don't understand the negative results from Andrew well enough to
tell if they rule out such an approach.

The idea is to add terms witnessing that for every square x, y |- A x y we
have Path (coe^i (A i i)) ((coe^i (A i 0)) o (coe^i (A 1 i))) which is
degenerate when A is degenerate in x OR y, plus similar terms for higher
cubes, since once you need dimensions one and two you probably need
dimension n, and a similar thing for hcomp, or you can do coe and hcomp
together in just comp.
Composing two of these paths then gives the needed proof that coercing
around the square either way is equal, in a degenerate fashion if A is
degenerate in x or y.

Best regards,
- Jasper Hugunin

On Sun, Sep 15, 2019 at 7:55 AM Andrew Swan <wakelin.swan@gmail.com> wrote:

> You might have already seen this, but I have a paper on some related
> issues at https://arxiv.org/abs/1808.00920 . In that paper I didn't look
> at the original version of regularity, but a more recent version ("all
> monomorphisms are cofibrations") that fits better with the general
> framework of Orton and Pitts. In that case it is definitely equality of
> objects that causes problems.
>
> Best,
> Andrew
>
> On Friday, 13 September 2019 08:10:42 UTC+2, Jasper Hugunin wrote:
>>
>> Hello all,
>>
>> I've been trying to understand better why composition for the universe
>> does not satisfy regularity.
>> Since comp^i [ phi |-> E ] A is defined as (roughly) Glue [ phi |->
>> equiv^i E ] A, I would expect regularity to follow from two parts:
>> 1. That Glue [ phi |-> equivRefl A ] A reduces to A (a sort of regularity
>> 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
>> argument.
>>
>> Context:
>> I've been studying and using CCHM cubical type theory recently, and often
>> finding myself wishing that J computed strictly.
>> If I understand correctly, early implementations of ctt did have strict 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
>> mailing list
>> <https://groups.google.com/d/msg/homotopytypetheory/oXQe5u_Mmtk/3HEDk5g5uq4J>,
>> the definition of composition for the universe was found to not satisfy
>> regularity.
>> I don't remember seeing the regularity condition defined anywhere, but my
>> understanding is that it requires that composition in a degenerate line of
>> types, with the system of constraints giving the sides of the box also
>> degenerate in that direction, reduces to just the bottom of the box. This
>> seems to be closed under the usual type formers, plus Glue, but not the
>> universe with computation defined as in the CCHM paper
>> <http://www.cse.chalmers.se/~coquand/cubicaltt.pdf> (for trivial reasons
>> and non-trivial reasons; it gets stuck at the start with Glue [ phi |->
>> equiv^i refl ] A not reducing to anything).
>>
>> Best regards,
>> - Jasper Hugunin
>>
> --
> You received this message because you are subscribed to the Google Groups
> "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/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com
> <https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.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/CAGTS-a9XATMbfyyp00M8kqiEoFyj7XsxahMa3AdzXth_%3DLbTiA%40mail.gmail.com.

[-- Attachment #2: Type: text/html, Size: 6717 bytes --]

<div dir="ltr"><div>In CCHM, my understanding is that composition for Glue [ phi |-&gt; (T, f) ] A is actually regular, and reduces to composition in T on (forall i. phi), assuming composition is regular for A and T.<br></div><div>The regularity does seem to fail in ABCFHL, as you pointed out Anders, but is perhaps repairable.</div><div><br></div><div>What Carlo told me was that the problem is getting composition for Glue [ phi |-&gt; (T, f) ] A which is regular, reduces to composition in T on (forall i. phi), *and* reduces to composition in A when (T, f) = (A, equivRefl).</div><div>We get the first two but not the third in CCHM.</div><div><br></div><div>The problem as Carlo explained it was that given a square of types i, j |- A and a point a : A (i0) (j0), we can prove Path (coe^i A o coe^j A) (coe^j A o coe^i A) (coercing around the square in right then up vs up then right), and (assuming regularity for A), we can take this to be degenerate when A is degenerate in i, or give a different path which is degenerate when A is degenerate in j, but constructing a path which is degenerate when A is degenerate in i or j is elusive.</div><div><br></div><div>I have an idea for how to add new terms/operations (a sort of generalization of comp) such that such a path is constructible, but I haven&#39;t yet checked that there is a univalent universe with these more general operations.</div><div>I also don&#39;t understand the negative results from Andrew well enough to tell if they rule out such an approach.</div><div><br></div><div>The idea is to add terms witnessing that for every square x, y |- A x y we have Path (coe^i (A i i)) ((coe^i (A i 0)) o (coe^i (A 1 i))) which is degenerate when A is degenerate in x OR y, plus similar terms for higher cubes, since once you need dimensions one and two you probably need dimension n, and a similar thing for hcomp, or you can do coe and hcomp together in just comp.</div><div>Composing two of these paths then gives the needed proof that coercing around the square either way is equal, in a degenerate fashion if A is degenerate in x or y.<br></div><div> </div><div>Best regards,</div><div>- Jasper Hugunin</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Sun, Sep 15, 2019 at 7:55 AM Andrew Swan &lt;<a href="mailto:wakelin.swan@gmail.com">wakelin.swan@gmail.com</a>&gt; wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">You might have already seen this, but I have a paper on some related issues at <a href="https://arxiv.org/abs/1808.00920" target="_blank">https://arxiv.org/abs/1808.00920</a> . In that paper I didn&#39;t look at the original version of regularity, but a more recent version (&quot;all monomorphisms are cofibrations&quot;) that fits better with the general framework of Orton and Pitts. In that case it is definitely equality of objects that causes problems.<div><br></div><div>Best,</div><div>Andrew<br><br>On Friday, 13 September 2019 08:10:42 UTC+2, Jasper Hugunin  wrote:<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr">Hello all,<div><br></div><div><div>I&#39;ve been trying to understand better why composition for the universe does not satisfy regularity.</div><div>Since comp^i [ phi |-&gt; E ] A is defined as (roughly) Glue [ phi |-&gt; equiv^i E ] A, I would expect regularity to follow from two parts:</div><div>1. That Glue [ phi |-&gt; equivRefl A ] A reduces to A (a sort of regularity condition for the Glue type constructor itself)</div><div>2. That equiv^i (refl A) reduces to equivRefl A</div><div>I&#39;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 argument.</div><div><br></div><div>Context:</div><div><div>I&#39;ve been studying and using CCHM cubical type theory recently, and often finding myself wishing that J computed strictly.</div><div>If I understand correctly, early implementations of ctt did have strict J for Path types, and this was justified by a &quot;regularity&quot; condition on the composition operation, but as discussed in <a href="https://groups.google.com/d/msg/homotopytypetheory/oXQe5u_Mmtk/3HEDk5g5uq4J" rel="nofollow" target="_blank">this thread on the HoTT mailing list</a>, the definition of composition for the universe was found to not satisfy regularity.</div><div>I don&#39;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 also degenerate in that direction, reduces to just the bottom of the box. This seems to be closed under the usual type formers, plus Glue, but not the universe with computation defined as in <a href="http://www.cse.chalmers.se/~coquand/cubicaltt.pdf" rel="nofollow" target="_blank">the CCHM paper</a> (for trivial reasons and non-trivial reasons; it gets stuck at the start with Glue [ phi |-&gt; equiv^i refl ] A not reducing to anything).</div><div><br></div></div></div><div>Best regards,</div><div>- Jasper Hugunin</div></div>
</blockquote></div></div>

<p></p>

-- <br>
You received this message because you are subscribed to the Google Groups &quot;Homotopy Type Theory&quot; group.<br>
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com" target="_blank">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br>
To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com?utm_medium=email&amp;utm_source=footer" target="_blank">https://groups.google.com/d/msgid/HomotopyTypeTheory/16b3b92f-069b-468c-94f8-f3859e152338%40googlegroups.com</a>.<br>
</blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &quot;Homotopy Type Theory&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an email to <a href="mailto:HomotopyTypeTheory+unsubscribe@googlegroups.com">HomotopyTypeTheory+unsubscribe@googlegroups.com</a>.<br />
To view this discussion on the web visit <a href="https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9XATMbfyyp00M8kqiEoFyj7XsxahMa3AdzXth_%3DLbTiA%40mail.gmail.com?utm_medium=email&utm_source=footer">https://groups.google.com/d/msgid/HomotopyTypeTheory/CAGTS-a9XATMbfyyp00M8kqiEoFyj7XsxahMa3AdzXth_%3DLbTiA%40mail.gmail.com</a>.<br />

  reply index

Thread overview: 13+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2019-09-13  6:10 [HoTT] " Jasper Hugunin
2019-09-15  5:57 ` [HoTT] " Jasper Hugunin
     [not found]   ` <CAMWCppk4PWzfZ1HKNLMdAZ=RBC-ARxtJXR8okvwO3raea5gC8Q@mail.gmail.com>
     [not found]     ` <CAGTS-a-SvWWF+br6sKxGj6ufVY=4m830FH9BDg06QJR1vbNFsw@mail.gmail.com>
2019-09-16  2:18       ` Fwd: " Jasper Hugunin
2019-09-16 16:18         ` [HoTT] " Licata, Dan
2019-09-16 17:09           ` Jasper Hugunin
2019-09-16 19:01             ` Licata, Dan
2019-09-16 20:17               ` Jasper Hugunin
2019-09-18 12:16                 ` Anders Mortberg
2019-09-18 12:52                   ` Thierry Coquand
2019-09-15 11:55 ` [HoTT] " Andrew Swan
2019-09-15 22:38   ` Jasper Hugunin [this message]
2019-09-16  1:04   ` Jon Sterling
     [not found]     ` <A605E6EE-0101-4390-B50D-A6AEB36FDCC2@icloud.com>
2019-09-16  1:44       ` Jon Sterling

Reply instructions:

You may reply publically to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAGTS-a9XATMbfyyp00M8kqiEoFyj7XsxahMa3AdzXth_=LbTiA@mail.gmail.com' \
    --to=jasperh@cs.washington.edu \
    --cc=HomotopyTypeTheory@googlegroups.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link

Discussion of Homotopy Type Theory and Univalent Foundations

Archives are clonable: git clone --mirror http://inbox.vuxu.org/hott

Example config snippet for mirrors

Newsgroup available over NNTP:
	nntp://inbox.vuxu.org/vuxu.archive.hott


AGPL code for this site: git clone https://public-inbox.org/public-inbox.git