On Heterogeneous Equality

(guest post by Jesse McKeown)

A short narative of a brief confusion, leading to yet-another-reason-to-think-about-univalence, after which the Author exposes his vaguer thinking to derision.

The Back-story

In the comments to Abstract Types with Isomorphic Types, Dan Licata mentioned O(bservational)TT, originating in works of McBride, with Altenkirche, McKinna… One of the initially-strange features therein is a so-called "heterogeneous equality" type, which from my very cursory reading I see has something to do with coercing along equivalences. Of course, this piqued my curiosity and a short-while later I happened upon this book about using coq as a practical program verification assistant, by way of this section of the chapter "Equality".

The Types

A heterogeneous equality type is defined in standard Coq (in the library Coq.Logic.JMeq) more-or-less by

Inductive JMeq { A : Type } (a : A) : forall { B : Type }, B -> Type :=
 jm_refl : JMeq a a.

Andrej Bauer’s modified "hoq" omits this library, for what turn out to be very sensible reasons (that is, the file isn’t even present to tempt us); nonetheless, I was curious to see what would happen if one tried to reason directly about this sort of equality instead of the HoTT-usual sort; in my case, foolishly trying to hand-edit the Paths library to replace paths with this JMeq. The surprising result was a flurry of Universe.Inconsistency (warnings) as soon as I tried to prove the left- and right-unit laws. This was when I actually started looking for written things about heterogeneous equality types in Coq on the internet, landing on Chlipala’s book. He makes what seemed a curious remark about a possible axiom JMeq_eq of type

JMeq_eq_axiom := forall {A : Type} (x y : A), JMeq x y -> x = y .


It may be surprising that we cannot prove that heterogeneous equality implies normal equality. The difficulties are the same kind we have seen so far, based on limitations of match annotations.

Particularly, the second sentence struck me as odd, because the incompleteness of an axiomatic theory has nothing to do with the concrete syntax you use for talking about that theory — that would mean your metalanguage was inadequate, not that the theory itself was incomplete. What is actually going on is that an inhabitant of JMeq_eq_axiom is an anti-Univalence-axiom: it says that the Universe of types is totally-disconnected. It does not say much of anything about homotopy within types generically.

Heterogeneous Equality with Univalence

To clarify the preceding, if one attends to what is deliberately obscured by the implicit arguments of JMeq 1, you will see that "heterogeneous equality" is really "equality of pointed types". And so, some code.

Definition ptdType := { A : Type & A }.
Definition unptd : ptdType -> Type := pr1.
Definition basept : forall A' : ptdType, unptd A' := pr2.

Definition at_home { A : Type } (a : A) : ptdType := existT ( fun x => x) A a.

Notation "[ a ]" := (at_home a).

Of course, anyone who is interested in homotopy theory should think about pointed spaces from time to time, if only because of the hypotheses of Brown’s representability theorem. Two easy lemmas about basept and at_home; we only need one of them here; we’d probably want the other if proving equivalences in the other order below.

(* a beta *)
Definition b_a_b { A : Type } (a : A) : basept [a] = a.

(* an eta *)
Definition a_b_a (w : ptdType) : [ basept w ] = w.
  destruct w.

Mike, in email, reminded me that these are just eta and beta (or η and β, if you like), but I’m leaving these names in for now, because these are the sorts of observations that confuse me. And now we can really begin to consider what it means to identify two pointed types.

Lemma jme_to_ptEq : forall { A B } (a : A)(b : B), JMeq a b -> [a] = [b].
  induction X.
  auto. (* "apply idpath" *)

Lemma ptEq_to_jme : forall w v,  w = v -> JMeq (basept w) (basept v).
  induction X.
  apply jm_refl.

Really, that bit was quite trivial, which is why the next bit is so easy: these are (more-or-less) inverse equivalences.

Lemma ptdEquiv : forall w v, hequiv (w = v) (JMeq (basept w) (basept v)).
  intros. (* w v *)
  exists (ptEq_to_jme w v)
  (fun y => 
    ! a_b_a w @ (jme_to_ptEq (basept w) (basept v) y) @ a_b_a v).
(* proving hequiv_section *)
  intros. (* y : JMeq (basept w) (basept v) *)
  destruct w as [W w].
  destruct v as [V v]. simpl in *. (* now, y : JMeq w v *)
  induction y. 
   compute. auto.
(* hequiv_section done! now proving hequiv_retraction *)
  intros. (* x : w = v *)
  induction x. 
  destruct w.
  auto. (* that's all! *)

There, that was easy. The other side is even easier, now:

Definition JMEquiv : forall {A B} (a : A) (b : B), hequiv ([a] = [b]) (JMeq a b) :=
 fun A B (a : A)(b : B) => ptdEquiv [a] [b].

  1. You might say "obscured by me" because standard Coq defers this obscurantism to its local notation "==". It’s still there, just the same. (back)

This entry was posted in Uncategorized. Bookmark the permalink.