如何在 Coq 中使用 HoTT 路径归纳？

Question

在 Coq 我有

Definition f (s:Unit) : tt=tt := match s with tt => idpath end.
Definition g (p:tt=tt) : Unit := match p with idpath => tt end.

我想证明 forall (p:tt=tt), (f o g) p = p。

我想用HoTT书中1.12.1中描述的路径归纳来做。

显然对于p是idpath的情况，我们可以证明

assert( (f o g) idpath = idpath).
simpl.
reflexivity.

但是如何在 Coq 中使用路径归纳来打包整个证明？

到目前为止的整个证明：（用什么代替 admit？）

Require Import HoTT.
Definition f (s:Unit) : tt=tt := match s with tt => idpath end.
Definition g (p:tt=tt) : Unit := match p with idpath => tt end.
Theorem myTheorem : forall (p:tt=tt), (f o g) p = p.
  assert( (f o g) idpath = idpath).
  simpl.
  reflexivity.
admit.

Answer 1

Coq 中路径归纳的模拟是 match 结构。以下是我们如何使用它来定义（基于）路径归纳，如 HoTT 书中所述。

Set Implicit Arguments.

Definition J {A} {x : A} (P : forall y, x = y -> Type)
                 (H : P x eq_refl) : forall y p, P y p :=
  fun y p => match p with eq_refl => H end.

这个定义的类型是这样说的，每当我们想证明P y p，其中

y : A,
p : x = y，以及
P : forall y, x = y -> Type,

足以证明 P x eq_refl 成立。我们可以用 J 来证明你的 g 函数是常量。（我改写了定义以匹配 Coq 标准库给出的定义。）

Definition f (s : unit) : tt = tt := match s with tt => eq_refl end.
Definition g (p : tt = tt) : unit := match p return unit with eq_refl => tt end.

Definition g_tt p : g p = tt :=
  J (fun y q => match q return unit with eq_refl => tt end = tt)
    eq_refl p.

这个证明的棘手部分是找出 J 的 P 参数应该是什么，这也是通过路径归纳进行的其他证明的情况。在这里，我不得不展开 g 的定义，因为它需要一个类型为 tt = tt 的参数，而上面使用的 q 的类型为 tt = y。无论如何，你可以看到 P tt p 在定义上等于 g p = tt，这就是我们要证明的。

我们可以玩把戏来证明 p = eq_refl 对任何 p : tt = tt。结合前面的结果，它会给出你想要的。

Definition result (p : tt = tt) : p = eq_refl :=
  J (fun y q =>
       unit_rect (fun z => tt = z -> Prop)
                 (fun u => u = eq_refl)
                 y q)
    eq_refl p.

再一次，关键是P参数。我们利用 unit 的归纳原理，它表示只要我们可以找到 T x 类型的东西（对于 T : unit -> Type 和 x : tt） =39=].回想一下 J 这个应用程序的结果应该有类型

P tt p

在这种情况下只是

unit_rect (fun z => tt = z -> Prop)
          (fun u => u = eq_refl)
          tt p
= (p = eq_refl)

根据unit_rect的计算规则。

不幸的是，这种证明很难用 Coq 的策略语言复制，因为它经常难以推断 P 应该是什么。通常更容易弄清楚这个值应该是什么，然后明确地写下证明项。

我不太明白为什么，但是如果你用 match 写下证明项，Coq 也更擅长弄清楚这个注释。比较：

Definition result' (p : tt = tt) : p = eq_refl :=
  match p with eq_refl => eq_refl end.

虽然这看起来简单得多，但当您尝试打印它时，您会发现 Coq 推断的实际术语要复杂得多。试试吧！

编辑

啊，我刚刚意识到您正在尝试使用 Coq 的 HoTT 版本。我没有安装那个版本，但我认为让我的解决方案适应它应该不会太难。

Answer 2

我知道这个问题太老了，早就解决了，但我确实想指出，HoTT 路径归纳与 Arthur 的回答规定略有不同。我认为这有助于理解，原因有二：(i) HoTT 设置的方式稍微不那么复杂，(ii) 它更符合 HoTT 中路径归纳的实际使用方式，因此更容易翻译成他们的图书馆。这两点主要针对像我这样多年后才想到这个问题的人。

首先，HoTT中重新定义符号等号来表示路径space，定义为类型A中每个点一个生成器refl x的归纳类型。

所以在 HoTT 中我们有

Inductive paths {A : UU} (x : A) := A -> UU
   | refl : paths a a.

基于路径归纳就是 Coq 系统自动生成的函数 paths_rect。然后可以将路径归纳定义为基于路径归纳的实例，就像在 The HoTT Book 中所做的那样。

这些都可以在Foundations目录下的UniMath文件“序言”中看到。

如何在 Coq 中使用 HoTT 路径归纳？

How to use HoTT path induction in Coq?

coq

type-theory

编辑