了解 Coq 中的 "well founded" 证明
Understanding "well founded" proofs in Coq
我正在编写一个固定点，它要求整数在每次迭代时递增 "towards" 为零。这对于 Coq 来说太复杂了，无法自动识别为递减参数，我正在尝试证明我的定点将终止。
我一直在复制（我认为是）标准库中 Z 上阶跃函数的充分性证明示例。 (Here)
Require Import ZArith.Zwf.
Section wf_proof_wf_inc.
Variable c : Z.
Let Z_increment (z:Z) := (z + ((Z.sgn c) * (-1)))%Z.
Lemma Zwf_wf_inc : well_founded (Zwf c).
Proof.
unfold well_founded.
intros a.
Qed.
End wf_proof_wf_inc.
创建以下上下文：
c : Z
wf_inc := fun z : Z => (z + Z.sgn c * -1)%Z : Z -> Z
a : Z
============================
Acc (Zwf c) a
我的问题是这个目标究竟意味着什么？
我认为我必须为此证明的目标至少涉及我想展示的阶跃函数具有 "well founded" 属性、"Z_increment".
我看过的最有用的解释是 this，但我从未使用过它使用的列表类型，它没有解释 "accessible" 等术语的含义。
基本上，你不需要做有根据的证明，你只需要证明你的函数减少了（自然数）abs(z)。更具体地说，您可以实施 abs (z:Z) : nat := z_to_nat (z * Z.sgn z)（适当转换为 nat），然后将其用作 Function 的度量，例如 Function foo z {measure abs z} := ....
The well founded business is for showing relations are well-founded：想法是你可以通过展示"decreases"一些有根据的来证明你的函数终止关系 R（将其视为 <）；也就是说，f x 的定义仅在 R y x 时才进行递归子调用 f y。为此，R 必须 有充分根据 ，这直观地意味着它没有无限下降的链。 CPDT general recursion chapter 很好地解释了它的工作原理。
这与您的工作有什么关系？标准库证明，对于所有下界 c，如果 x < y 仅应用于 y >= c，则 x < y 是 Z 中的有根据的关系。我不认为这适用于你 - 相反你向零移动，所以你可以减少 abs z 与 nats 上通常的 < 关系。标准库已经证明这种关系是有根据的，这就是 Function ... {measure ...} 使用的。
我正在编写一个固定点，它要求整数在每次迭代时递增 "towards" 为零。这对于 Coq 来说太复杂了，无法自动识别为递减参数，我正在尝试证明我的定点将终止。
我一直在复制（我认为是）标准库中 Z 上阶跃函数的充分性证明示例。 (Here)
Require Import ZArith.Zwf.
Section wf_proof_wf_inc.
Variable c : Z.
Let Z_increment (z:Z) := (z + ((Z.sgn c) * (-1)))%Z.
Lemma Zwf_wf_inc : well_founded (Zwf c).
Proof.
unfold well_founded.
intros a.
Qed.
End wf_proof_wf_inc.
创建以下上下文：
c : Z
wf_inc := fun z : Z => (z + Z.sgn c * -1)%Z : Z -> Z
a : Z
============================
Acc (Zwf c) a
我的问题是这个目标究竟意味着什么？
我认为我必须为此证明的目标至少涉及我想展示的阶跃函数具有 "well founded" 属性、"Z_increment".
我看过的最有用的解释是 this，但我从未使用过它使用的列表类型，它没有解释 "accessible" 等术语的含义。
基本上，你不需要做有根据的证明，你只需要证明你的函数减少了（自然数）abs(z)。更具体地说，您可以实施 abs (z:Z) : nat := z_to_nat (z * Z.sgn z)（适当转换为 nat），然后将其用作 Function 的度量，例如 Function foo z {measure abs z} := ....
The well founded business is for showing relations are well-founded：想法是你可以通过展示"decreases"一些有根据的来证明你的函数终止关系 R（将其视为 <）；也就是说，f x 的定义仅在 R y x 时才进行递归子调用 f y。为此，R 必须 有充分根据 ，这直观地意味着它没有无限下降的链。 CPDT general recursion chapter 很好地解释了它的工作原理。
这与您的工作有什么关系？标准库证明，对于所有下界 c，如果 x < y 仅应用于 y >= c，则 x < y 是 Z 中的有根据的关系。我不认为这适用于你 - 相反你向零移动，所以你可以减少 abs z 与 nats 上通常的 < 关系。标准库已经证明这种关系是有根据的，这就是 Function ... {measure ...} 使用的。