列表上的强归纳法

Question

我试图证明命题 P 对类型 A 的每个元素都成立。不幸的是，如果我可以访问所有 a' 小于 a 的 P 的证明，我只知道如何为给定的 a:A 证明 P。

这应该可以通过对包含 A 的所有元素的列表进行归纳来证明，从 A 中的最小元素开始，然后逐步证明 P 对所有其他元素成立，但我无法让它工作。

形式上，问题如下：

Parameter A : Type.
Parameter lt : A -> A -> Prop.
Notation "a < b" := (lt a b).
Parameter P : A -> Prop.
Parameter lma : forall a, (forall a', a' < a -> P a') -> P a.

Goal forall a, P a.

我可能在形式化这个问题时犯了一个错误。随意假设对输入的合理限制，例如A可以假定为可枚举的，lt可以传递的，可判定的...

Answer 1

你还必须证明这种关系是有根据的。有一个相关的 standard library 模块。从那里，您应该为您的 A 类型证明 well_founded A，然后您可以使用 well_founded_ind 为所有值证明 P。

Answer 2

这看起来很像 well founded induction. If you can prove that your lt function is well-founded, then your goal becomes trivial. You can find example of such proofs on naturals here

列表上的强归纳法

Strong Induction on Lists

coq

theorem-proving