Discussion of Homotopy Type Theory and Univalent Foundations
 help / Atom feed
From: "Martín Hötzel Escardó" <escardo.martin@gmail.com>
To: Homotopy Type Theory <HomotopyTypeTheory@googlegroups.com>
Subject: Re: [HoTT] Definitions of equivalence satisfying judgmental/strict groupoid laws?
Date: Wed, 11 Sep 2019 18:45:34 -0700 (PDT)
Message-ID: <142000b0-e2e8-42cb-9201-4d2dcbec3de7@googlegroups.com> (raw)
In-Reply-To: <CAKObCao60=RFWY=Cn0BTV9bWcRCQXRSqOjvCYbS37mHOeJ0Yqg@mail.gmail.com>

[-- Attachment #1.1: Type: text/plain, Size: 6134 bytes --]


On 17/08/2019 01:14, Jason Gross wrote:
> Resurrecting this thread from many years ago, because I was thinking
> about it again recently, it seems to me that although { f &
> isTrackedByRelEquiv(f) } satisfies the rule sym (sym e) = e
> judgmentally, it doesn't satisfy the rule that sym id = id
> judgmentally.  (In particular, I am not sure what relational equivalence
> to use for the identity equivalence which does not change judgmentally
> when I flip the order of its arguments.)  Is there a version of
> equivalence which simultaneously satisfies that the inverse of the
> identity is judgmentally the identity, and that inverting an equivalence
> twice judgmentally gives you what you started with?
>
> -Jason


I am not sure this answer will be of the kind you are expecting.

First I will consider the identity type and then the equivalence type
using the same idea.

I will use "=" for definitional equality.

(1) If you have some identity type (_≡_, refl , J) with

    _≡_ : {X : 𝓤} → X → X → 𝓤

    refl : {X : 𝓤 } (x : X) → x ≣ x

    J : (X : 𝓤) (A : (x y : X) → x ≡ y → 𝓤)
     → ((x : X) → A x x (refl x))
     → (x y : X) (p : x ≡ y) → A x y p

then you can define another identity type (_≡'_ , refl' , J') by


    x ≡' y = Σ (z : X), (z ≡ x) × (z ≡ y)

(which is equivalent to the diagonal fiber of (x,y) and also to x ≡ y
(both in pure MLTT))


    refl' x = x , refl x , refl x


    J' X A f x y (z , p , q) = γ z x p y q
     where
      φ :  (x y : X) (q : x ≡ y) → A x y (x , refl x , q)
      φ = J X (λ x y q → A x y (x , refl x , q)) f

      γ : (z x : X) (p : z ≡ x) (y : X) (q : z ≡ y) → A x y (z , p , q)
      γ = J X (λ z x p → (y : X) (q : z ≡ y) → A x y (z , p , q)) φ

so that

    J' X A f x x (refl' x) = f x

definitionally using the original J's computation rule.


For this new identity type, we can define

    ≡'-sym : {X : 𝓤 ̇ } {x y : X} → x ≡' y → y ≡' x
    ≡'-sym (a , p , q) = (a , q , p)

so that

   ≡'-sym (refl' x) = refl' x

and

  ≡'-sym (≡'-sym p') = p',

both definitionally.

(2) Similarly we can define an equivalence type _≃'_ from an equivalence 
type _≃_ by

    X ≃' Y = Σ (Z : 𝓤), (Z ≃ X) × (Z ≃ X)

with the analogous identity equivalence and symmetrization operation
so that the definitional equalities you want hold.

This is related to the relational definition of equivalence as
follows. The type

   X × Y → 𝓤

of type-valued relations is in canonical bijection with the "slice type"

  Σ (Z : 𝓤), Z → X × Y

by a well-known construction, and in turn to

  Σ (Z : 𝓤), (Z → X) × (Z → Y).

When you restrict to relations R such that for all x:X and y:Y the types

  Σ (x : X), R x y

and

  Σ (y : Y), R x y

are contractible, the type Σ (Z : 𝓤), (Z → X) × (Z → Y) gets restricted to

  Σ (Z : 𝓤), (Z ≃ X) × (Z ≃ X)

by the canonical equivalence

 (X × Y → 𝓤) ≃ Σ (Z : 𝓤), (Z → X) × (Z → Y).

(3) If you want composition of identifications to be definitionally
associative with refl definitionally neutral on both sides, you can
consider the alternative identity type defined by

   x ≡'' y  = (z : X) → (z ≡ x) → (z ≡ y)

which is again equivalent to the original identity type x ≡ y (which
amounts to Yoneda),

   refl'' x = (z : X) → λ (p : x ≡ z) , p

because composition of identifications is given by function
composition, which is definitionally associative with the identity
function as its definitionally neutral element (assuming the η rule).

  (Exercise: write down J''.)

(4) I don't know how to get the definitional equalities of (1) and (3)
together by a suitable modification of the identity type. The
constructions (1) and (3) are kind of dual.

Martin

On Thu, Nov 13, 2014 at 12:59 PM Vladimir Voevodsky <vlad...@ias.edu 
> <javascript:>> wrote:
>
>> In general no. But their model is essentially syntactic and more or less 
>> complete. Or, to be more precise, I would expect it to 
>> be more or less complete. 
>>
>> V.
>>
>>
>> On Nov 13, 2014, at 9:55 PM, Peter LeFanu Lumsdaine <p.l.l...@gmail.com 
>> <javascript:>> wrote:
>>
>> On Thu, Nov 13, 2014 at 12:04 PM, Vladimir Voevodsky <vlad...@ias.edu 
>> <javascript:>> wrote:
>>
>>> The question is about how you interpret this operation for the univalent 
>>> universe. If there is an interpretation of such an operation then there is 
>>> a way to define equivalences between types in an involutionary way.
>>>
>>
>> I don’t follow why this should be the case.  This shows that there is 
>> some notion of equivalence *in the model* (i.e. constructed in the 
>> meta-theory) which is strictly involutive.  But there is no reason that 
>> this notion need be definable in the syntax of the object theory, is there?
>>
>> –p. 
>>
>> -- 
>> 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 <javascript:>.
>> For more options, visit https://groups.google.com/d/optout.
>>
>>
>> -- 
>> 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 <javascript:>.
>> For more options, visit https://groups.google.com/d/optout.
>>
>

-- 
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/142000b0-e2e8-42cb-9201-4d2dcbec3de7%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 10258 bytes --]

      reply index

Thread overview: 2+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
     [not found] <CAKObCarykcu9p=1VB5YkBPjm3sVzKk9DO9oNYBFthr-jWOGptw@mail.gmail.com>
     [not found] ` <50f257f8-f6a0-410e-9f32-512ebcef1e05@googlegroups.com>
     [not found]   ` <CAOvivQw2sDUx+TVp3RSEL2kFdLzyharBXA-zwB3=o9820NUsnA@mail.gmail.com>
     [not found]     ` <CAAkwb-=sivUFQ5TRCohcykU2Tg49mE38h-6Q-7zUHUaJ5eXMhg@mail.gmail.com>
     [not found]       ` <CAOvivQxmb-gC8gFhVtDnOwxtcYTDH1tXv3B47fpfVwJxtOdgvQ@mail.gmail.com>
     [not found]         ` <CAAkwb-nq7Y142fbiEeC1MQ4n-H66xBc0NaycK2-=nObxbutjXA@mail.gmail.com>
     [not found]           ` <CAGqv1ODSYp-R2W1xvZeP8m04JO_CSbS8ZePL9+cu=mdXQXZRjQ@mail.gmail.com>
     [not found]             ` <CAAkwb-kwaAWfd27doQ6VbMm85Lbs6=Y8p_MCSQc6r0K6_RLyBw@mail.gmail.com>
     [not found]               ` <68F509C8-C1BC-40B9-BE23-B930C801AF1D@ias.edu>
     [not found]                 ` <BD2EF3CB-2A9C-4A7D-9C39-94B25A95DB4B@chalmers.se>
     [not found]                   ` <4957EC32-97FE-4383-AA07-C1ADF4EAF243@ias.edu>
     [not found]                     ` <CAAkwb-n85XxXVNB-V8OdH73qzPgFa50XiNGMbRjASTcLZ_BVRw@mail.gmail.com>
     [not found]                       ` <435F59BF-DD90-43E0-926A-D197D38B94B4@ias.edu>
2019-08-17  0:14                         ` Jason Gross
2019-09-12  1:45                           ` Martín Hötzel Escardó [this message]

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=142000b0-e2e8-42cb-9201-4d2dcbec3de7@googlegroups.com \
    --to=escardo.martin@gmail.com \
    --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

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


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