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

prev parent reply indexThread 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 Gross2019-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-toswitches 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 theIn-Reply-Toheader 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