* 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