索引相等的归纳类型意味着索引相等

Question

让我们有一个归纳类型为的foo索引x : X。

Parameter X : Type.

Inductive foo : X -> Type :=
| constr : forall (x : X), foo x.

如果foo x = foo y暗示的话，我很好奇x = y。我不知道如何证明这一点。

Lemma type_equality_implies_index_equality : forall (x y : X), foo x = foo y -> x = y.

如果无法证明，为什么？

Answer 1

无法证明。设置时，请考虑以下定理的特殊情况X := bool：

foo true = foo false -> true = false

鉴于true和false是不同的，如果定理是可证明的，则应该有可能证明foo true和foo false是不同的。问题在于这两种类型是同构的：

Inductive foo : bool -> Type :=
| constr : forall (x : bool), foo x.

(* An isomorphism between foo true and foo false *)
Definition foo_t_f (x : foo true) : foo false := constr false.
Definition foo_f_t (x : foo false) : foo true := constr true.

(* Proofs that the functions are inverses of each other *)
Lemma foo_t_fK x : foo_f_t (foo_t_f x) = x.
Proof. unfold foo_f_t, foo_t_f. now destruct x. Qed.

Lemma foo_f_tK x : foo_t_f (foo_f_t x) = x.
Proof. unfold foo_f_t, foo_t_f. now destruct x. Qed.

在Coq的理论中，如果不假设额外的公理就不可能证明两个同构类型是不同的。这就是为什么对Coq理论（例如同伦类型理论）进行扩展是合理的。在HoTT中，同构类型可以显示为相等，并且如果可以证明您的定理，则HoTT会不一致。