证明后继者的替换属性优于相等性

Question

我正在尝试从 chapter 7 of "theorem proving in lean" 中理解归纳类型。

我给自己定下了一项任务，即证明自然数的后继可以替代属性而不是等式：

inductive natural : Type
| zero : natural
| succ : natural -> natural

lemma succ_over_equality (a b : natural) (H : a = b) :
  (natural.succ a) = (natural.succ b) := sorry

经过一些猜测和相当详尽的搜索后，我能够用两种可能性满足编译器的要求：

lemma succ_over_equality (a b : natural) (H : a = b) :
  (natural.succ a) = (natural.succ b) :=
    eq.rec_on H (eq.refl (natural.succ a))
    --eq.rec_on H rfl
    --eq.subst H rfl
    --eq.subst H (eq.refl (natural.succ a))
    --congr_arg (λ (n : natural), (natural.succ n)) H

我不明白我刚刚给出的任何证明实际上是如何工作的。

eq（归纳）类型的完整定义是什么？在 VSCode 中，我可以看到 eq 的类型签名为 eq Π {α : Type} α → α → Prop，但我看不到单个（归纳）构造函数（zero 和 succ 的类似物来自 natural）。我能在源代码中找到的最好的 doesn't look quite right.
为什么 eq.subst 乐于接受 (natural.succ a) = (natural.succ a) 的证明来提供 (natural.succ a) = (natural.succ b) 的证明？
什么是以及它如何应用于这个特定示例？
我输入 #check (eq.rec_on H (eq.refl (natural.succ a))) 时得到的错误是什么意思，即 [Lean] invalid 'eq.rec_on' application, elaborator has special support for this kind of application (it is handled as an "eliminator"), but the expected type must be known eq.rec_on : Π {α : Sort u} {a : α} {C : α → Sort l} {a_1 : α}, a = a_1 → C a → C a_1

Answer 1

eq 是 defined 是
```
inductive eq {α : Sort u} (a : α) : α → Prop
| refl : eq a
```
这个想法是任何项都等于它自己，两个项相等的唯一方法是它们是同一个项。这可能有点像是 ITT 的魔法。美感来自这个定义自动生成的递归：
```
eq.rec : Π {α : Sort u_2} {a : α} {C : α → Sort u_1}, C a → Π {a_1 : α}, a = a_1 → C a_1
```
这是平等的替代原则。 "If C holds of a, and a = a_1, then C holds of a_1."（如果 C 是类型值而不是 Prop 值，则有类似的解释。）
eq.subst 正在使用 a = b 的证明以及 succ a = succ a 的证明。请注意 eq.subst 基本上是对上面 eq.rec 的重新表述。假设属性 C 参数化为变量 x，是 succ a = succ x。 C 通过自反性对 a 成立，并且由于 a = b，我们有 C 对 b.
当你写 eq.subst H rfl 时，Lean 需要弄清楚属性（或 "motive"）C 应该是什么。这是高阶合一的例子：未知变量需要与 lambda 表达式合一。 https://leanprover.github.io/theorem_proving_in_lean/theorem_proving_in_lean.pdf, and some general information at https://en.wikipedia.org/wiki/Unification_(computer_science)#Higher-order_unification.
您要求 Lean 将 a = b 替换为 succ a = succ a，而没有告诉它您要证明什么。您可能试图证明 succ b = succ b，或 succ b = succ a，甚至 succ a = succ a（无处替换）。精益无法推断动机 C 除非它有这些信息。

一般来说，进行替换 "manually"（使用 eq.rec、subst 等）很困难，因为高阶统一既挑剔又昂贵。您经常会发现使用 rw（重写）这样的策略会更好：

lemma succ_over_equality (a b : natural) (H : a = b) :
  (natural.succ a) = (natural.succ b) := by rw H

如果你想变聪明，可以利用 Lean 的方程编译器，a=b 的 "only" 证明是 rfl:

lemma succ_over_equality : Π (a b : natural),
   a = b → (natural.succ a) = (natural.succ b)
| ._ _ rfl := rfl

证明后继者的替换属性优于相等性

Proving substitution property of successor over equality

dependent-type

theorem-proving

formal-verification

lean

证明后继者的替换 属性 优于相等性

Proving substitution property of successor over equality

dependent-type

theorem-proving

formal-verification

lean

证明后继者的替换属性优于相等性