Discussion of Homotopy Type Theory and Univalent Foundations
 help / color / mirror / Atom feed
* Re: [HoTT] Definitions of equivalence satisfying judgmental/strict groupoid laws?
       [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ó
  0 siblings, 1 reply; 2+ messages in thread
From: Jason Gross @ 2019-08-17  0:14 UTC (permalink / raw)
  To: Vladimir Voevodsky
  Cc: Peter LeFanu Lumsdaine, Thierry Coquand, HomotopyTypeTheory

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

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

On Thu, Nov 13, 2014 at 12:59 PM Vladimir Voevodsky <vladimir@ias.edu>
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.lumsdaine@gmail.com> wrote:
>
> On Thu, Nov 13, 2014 at 12:04 PM, Vladimir Voevodsky <vladimir@ias.edu>
> 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.
> 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.
> 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/CAKObCao60%3DRFWY%3DCn0BTV9bWcRCQXRSqOjvCYbS37mHOeJ0Yqg%40mail.gmail.com.

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

^ permalink raw reply	[flat|nested] 2+ messages in thread

* Re: [HoTT] Definitions of equivalence satisfying judgmental/strict groupoid laws?
  2019-08-17  0:14                         ` [HoTT] Definitions of equivalence satisfying judgmental/strict groupoid laws? Jason Gross
@ 2019-09-12  1:45                           ` Martín Hötzel Escardó
  0 siblings, 0 replies; 2+ messages in thread
From: Martín Hötzel Escardó @ 2019-09-12  1:45 UTC (permalink / raw)
  To: Homotopy Type Theory


[-- 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 --]

^ permalink raw reply	[flat|nested] 2+ messages in thread

end of thread, other threads:[~2019-09-12  1:45 UTC | newest]

Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
     [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                         ` [HoTT] Definitions of equivalence satisfying judgmental/strict groupoid laws? Jason Gross
2019-09-12  1:45                           ` Martín Hötzel Escardó

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).