Is this a generalised path induction in COQ?

Question

I am learning Homotopic Type Theory (HoTT) and its relation to COQ. Especially the path induction concept of the identity type is still mysterious to me.
Therefore I made some experiments with COQ.

Let's start with a simple Lemma for the standard equality type using path induction:

Lemma eq_sym: forall (x y:nat), x = y -> y = x.
intros.
apply (match H in (_ = y0) return y0 = x with eq_refl => eq_refl end).
Defined.

Now let's see if that is a special handling of the COQ "eq" type. Therefore let's define a new equality type (only for nat) with an analogous symmetry lemma:

Inductive est  (x : nat) : nat -> Prop :=
    est_refl:  est x x.  

Lemma est_sym: forall (x y:nat), est x y -> est y x.
intros.
apply (match H in (est _ y0) return est y0 x with est_refl => est_refl x end).
Defined.

Ok, this works in the same way like the standard "=" type.
Now let's generalise it:

Inductive tri  (x : nat) : nat->nat->Prop :=
    tri_refl:  tri x x x.

Lemma tri_sym: forall (x y z:nat), tri x y z -> tri z x y.
intros.
apply (match H in (tri _ y0 z0) return tri z0 x y0  with tri_refl => tri_refl x end).
Defined.

My question is:
How does this relate to the theory of HoTT?
Is this a generalised path induction which is not part of HoTT?

Arthur Azevedo De Amorim Arthur Azevedo De Amorim · Accepted Answer · 2016-02-02T00:15:50

Your "three-ended equality" is equivalent to a pair of equality proofs, in the sense that we can write Coq functions that convert back and forth between the two forms. (These are the eq_of_teq and teq_of_eq terms in the excerpt below.)

Section Teq.

Variable T : Type.

Inductive teq (x : T) : T -> T -> Prop :=
| teq_refl : teq x x x.

Definition teq_of_eq {x y z} (e1 : x = y) (e2 : x = z) : teq x y z :=
  match e1 in _ = y' return x = z -> teq x y' z with
  | eq_refl => fun e2 =>
    match e2 in _ = z' return teq x x z' with
    | eq_refl => teq_refl x
    end
  end e2.

Definition eq_of_teq1 {x y z} (te : teq x y z) : x = y :=
  match te in teq _ y' z' return x = y' with
  | teq_refl => eq_refl
  end.

Definition eq_of_teq2 {x y z} (te : teq x y z) : x = z :=
  match te in teq _ y' z' return x = z' with
  | teq_refl => eq_refl
  end.

Definition teq_eq_teq x y z (te : teq x y z) :
  teq_of_eq (eq_of_teq1 te) (eq_of_teq2 te) = te :=
  match te as te' in teq _ y' z' return teq_of_eq (eq_of_teq1 te') (eq_of_teq2 te') = te' with
  | teq_refl => eq_refl
  end.

Definition eq_teq_eq1 x y z (e1 : x = y) (e2 : x = z) :
  eq_of_teq1 (teq_of_eq e1 e2) = e1 :=
  match e1 as e1' in _ = y' return eq_of_teq1 (teq_of_eq e1' e2) = e1' with
  | eq_refl =>
    match e2 as e2' in _ = z' return eq_of_teq1 (teq_of_eq eq_refl e2') = eq_refl with
    | eq_refl => eq_refl
    end
  end.

Definition eq_teq_eq2 x y z (e1 : x = y) (e2 : x = z) :
  eq_of_teq2 (teq_of_eq e1 e2) = e2 :=
  match e1 as e1' in _ = y' return eq_of_teq2 (teq_of_eq e1' e2) = e2 with
  | eq_refl =>
    match e2 as e2' in _ = z' return eq_of_teq2 (teq_of_eq eq_refl e2') = e2' with
    | eq_refl => eq_refl
    end
  end.

End Teq.

The teq_eq_teq, eq_teq_eq1 and eq_teq_eq2 lemmas show that the converting back and forth does not change the terms we start with; hence, both representations are equivalent. In this sense, Coq does not have more expressive power than HoTT just because we can define a teq.

In basic Martin-Löf type theory (the formal system upon which HoTT is based), you don't gain much by carrying a pair of equalities between the same terms, since the only thing you can do with such equalities is to perform casts on the types of the terms you manipulate. Thus, it doesn't really matter usually whether you have only one or two equality proofs between terms.

The situation changes a little bit in HoTT because of the addition of the univalence axiom, which allows us to use equality proofs between types in a computationally interesting way. This is because a proof of A = B in HoTT can be any bijection between the types A = B. In that setting, a proof of teq A B C would be equivalent to two bijections: one between A and B, and the other one between A and C.

Is this a generalised path induction in COQ?

1 Answers