传入相等的 coq 归纳法
coq induction with passing in equality
我有一个包含已知值的列表，我想对其进行归纳，跟踪原始列表的内容，并按元素引用它。也就是说，我需要通过 l[i] 和不同的 i 来引用它，而不仅仅是 (a :: l).
我试图制定一个归纳原理来让我做到这一点。这是一个程序，其中所有不必要的定理都替换为 Admitted，并使用了一个简化的示例。 objective 是用 countDown_nth 证明 allLE_countDown，并且有 list_nth_rect 的一种方便的形式。 （没有这些，定理很容易直接证明。）
Require Import Arith.
Require Import List.
Definition countDown1 := fix f a i := match i with
| 0 => nil
| S i0 => (a + i0) :: f a i0
end.
(* countDown from a number to another, excluding greatest. *)
Definition countDown a b := countDown1 b (a - b).
Theorem countDown_nth a b i d (boundi : i < length (countDown a b))
: nth i (countDown a b) d = a - i - 1.
Admitted.
Definition allLE := fix f l m := match l with
| nil => true
| a :: l0 => if Nat.leb a m then f l0 m else false
end.
Definition drop {A} := fix f (l : list A) n := match n with
| 0 => l
| S a => match l with
| nil => nil
| _ :: l2 => f l2 a
end
end.
Theorem list_nth_rect_aux {A : Type} (P : list A -> list A -> nat -> Type)
(Pnil : forall l, P l nil (length l))
(Pcons : forall i s l d (boundi : i < length l), P l s (S i) -> P l ((nth i l d) :: s) i)
l s i (size : length l = i + length s) (sub : s = drop l i) : P l s i.
Admitted.
Theorem list_nth_rect {A : Type} (P : list A -> list A -> nat -> Type)
(Pnil : forall l, P l nil (length l))
(Pcons : forall i s l d (boundi : i < length l), P l s (S i) -> P l ((nth i l d) :: s) i)
l s (leqs : l = s): P l s 0.
Admitted.
Theorem allLE_countDown a b : allLE (countDown a b) a = true.
remember (countDown a b) as l.
refine (list_nth_rect (fun l s _ => l = countDown a b -> allLE s a = true) _ _ l l eq_refl Heql);
intros; subst; [ apply eq_refl | ].
rewrite countDown_nth; [ | apply boundi ].
pose proof (Nat.le_sub_l a (i + 1)).
rewrite Nat.sub_add_distr in H0.
apply leb_correct in H0.
simpl; rewrite H0; clear H0.
apply (H eq_refl).
Qed.
所以，我有 list_nth_rect 并且能够根据需要使用它和 refine 通过引用第 n 个元素来证明定理。但是，我必须自己构建命题 P。通常，您想使用归纳法。
这需要区分哪些元素是原始列表 l，哪些是引入的子列表 s。所以，我可以使用 remember.
Theorem allLE_countDown a b : allLE (countDown a b) a = true.
remember (countDown a b) as s.
remember s as l.
rewrite Heql.
这让我处于
a, b : nat
s, l : list nat
Heql : l = s
Heqs : l = countDown a b
============================
allLE s a = true
但是，我好像不能像上面那样通过等式。当我尝试
induction l, s, Heql using list_nth_rect.
我收到错误
Error: Abstracting over the terms "l", "s" and "0" leads to a term
fun (l0 : list ?X133@{__:=a; __:=b; __:=s; __:=l; __:=Heql; __:=Heqs})
(s0 : list ?X133@{__:=a; __:=b; __:=s; __:=l0; __:=Heql; __:=Heqs})
(_ : nat) =>
(fun (l1 l2 : list nat) (_ : l1 = l2) =>
l1 = countDown a b -> allLE l2 a = true) l0 s0 Heql
which is ill-typed.
Reason is: Illegal application:
The term
"fun (l l0 : list nat) (_ : l = l0) =>
l = countDown a b -> allLE l0 a = true" of type
"forall l l0 : list nat, l = l0 -> Prop"
cannot be applied to the terms
"l0" : "list nat"
"s0" : "list nat"
"Heql" : "l = s"
The 3rd term has type "l = s" which should be coercible to
"l0 = s0".
那么，我该如何改变归纳原理
这样它就可以与归纳策略一起使用？
看起来它在两者之间变得混乱
外部变量和内部变量
功能。但是，我没有办法说话
关于不在范围内的内部变量。
这很奇怪，因为用
毫无问题地完善作品。
我知道匹配，有子句，但是
我不知道如何在这里应用它。
或者，有没有办法让 list_nth_rect 使用
P l l 0 还是指出l和s对应哪些变量？
首先，您可以通过重用更基本的结果更容易地证明这个结果。这是一个基于 ssreflect 库定义的版本：
From mathcomp
Require Import ssreflect ssrfun ssrbool ssrnat eqtype seq.
Definition countDown n m := rev (iota m (n - m)).
Lemma allLE_countDown n m : all (fun k => k <= n) (countDown n m).
Proof.
rewrite /countDown all_rev; apply/allP=> k; rewrite mem_iota.
have [mn|/ltnW] := leqP m n.
by rewrite subnKC //; case/andP => _; apply/leqW.
by rewrite -subn_eq0 => /eqP ->; rewrite addn0 ltnNge andbN.
Qed.
此处，iota n m 是从 n 开始计算的 m 个元素的列表，all 是 allLE 的通用版本。标准库中存在类似的函数和结果。
回到你原来的问题，确实有时我们需要在记住我们开始的整个列表的同时在列表中进行归纳。我不知道是否有办法用标准的归纳策略得到你想要的东西；我什至不知道它有一个多参数变体。当我想用这个策略证明P l时，我通常是这样进行的：
找到一个谓词 Q : nat -> Prop 使得 Q (length l) 蕴含 P l。通常，Q n 的形式为 n <= length l -> R (take n l) (drop n l)，其中 R : list A -> list A -> Prop.
通过归纳证明所有 n 的 Q n。
我不知道这是否回答了您的问题，但 induction 似乎接受 with 条款。因此，您可以编写以下内容。
Theorem allLE_countDown a b : allLE (countDown a b) a = true.
remember (countDown a b) as s.
remember s as l.
rewrite Heql.
induction l, s, Heql using list_nth_rect
with (P:=fun l s _ => l = countDown a b -> allLE s a = true).
但好处非常有限w.r.t。 refine 版本，因为您需要手动指定谓词。
现在，我将如何使用标准库中的对象来证明这样的结果。
Require Import List. Import ListNotations.
Require Import Omega.
Definition countDown1 := fix f a i := match i with
| 0 => nil
| S i0 => (a + i0) :: f a i0
end.
(* countDown from a number to another, excluding greatest. *)
Definition countDown a b := countDown1 b (a - b).
Theorem countDown1_nth a i k d (boundi : k < i) :
nth k (countDown1 a i) d = a + i -k - 1.
Proof.
revert k boundi.
induction i; intros.
- inversion boundi.
- simpl. destruct k.
+ omega.
+ rewrite IHi; omega.
Qed.
Lemma countDown1_length a i : length (countDown1 a i) = i.
Proof.
induction i.
- reflexivity.
- simpl. rewrite IHi. reflexivity.
Qed.
Theorem countDown_nth a b i d (boundi : i < length (countDown a b))
: nth i (countDown a b) d = a - i - 1.
Proof.
unfold countDown in *.
rewrite countDown1_length in boundi.
rewrite countDown1_nth.
replace (b+(a-b)) with a by omega. reflexivity. assumption.
Qed.
Theorem allLE_countDown a b : Forall (ge a) (countDown a b).
Proof.
apply Forall_forall. intros.
apply In_nth with (d:=0) in H.
destruct H as (n & H & H0).
rewrite countDown_nth in H0 by assumption. omega.
Qed.
编辑：
你可以陈述一个辅助引理来做出更简洁的证明。
Lemma Forall_nth : forall {A} (P:A->Prop) l,
(forall d i, i < length l -> P (nth i l d)) ->
Forall P l.
Proof.
intros. apply Forall_forall.
intros. apply In_nth with (d:=x) in H0.
destruct H0 as (n & H0 & H1).
rewrite <- H1. apply H. assumption.
Qed.
Theorem allLE_countDown a b : Forall (ge a) (countDown a b).
Proof.
apply Forall_nth.
intros. rewrite countDown_nth. omega. assumption.
Qed.
问题在于，无论好坏，induction 似乎都假设其论点是独立的。那么，解决方案就是让 induction 从 Heql:
自动推断出 l 和 s
Theorem list_nth_rect {A : Type} {l s : list A} (P : list A -> list A -> nat -> Type)
(Pnil : P l nil (length l))
(Pcons : forall i s d (boundi : i < length l), P l s (S i) -> P l ((nth i l d) :: s) i)
(leqs : l = s): P l s 0.
Admitted.
Theorem allLE_countDown a b : allLE (countDown a b) a = true.
remember (countDown a b) as s.
remember s as l.
rewrite Heql.
induction Heql using list_nth_rect;
intros; subst; [ apply eq_refl | ].
rewrite countDown_nth; [ | apply boundi ].
pose proof (Nat.le_sub_l a (i + 1)).
rewrite Nat.sub_add_distr in H.
apply leb_correct in H.
simpl; rewrite H; clear H.
assumption.
Qed.
我不得不稍微改变 list_nth_rect 的类型；希望我没有弄错。
我有一个包含已知值的列表，我想对其进行归纳，跟踪原始列表的内容，并按元素引用它。也就是说，我需要通过 l[i] 和不同的 i 来引用它，而不仅仅是 (a :: l).
我试图制定一个归纳原理来让我做到这一点。这是一个程序，其中所有不必要的定理都替换为 Admitted，并使用了一个简化的示例。 objective 是用 countDown_nth 证明 allLE_countDown，并且有 list_nth_rect 的一种方便的形式。 （没有这些，定理很容易直接证明。）
Require Import Arith.
Require Import List.
Definition countDown1 := fix f a i := match i with
| 0 => nil
| S i0 => (a + i0) :: f a i0
end.
(* countDown from a number to another, excluding greatest. *)
Definition countDown a b := countDown1 b (a - b).
Theorem countDown_nth a b i d (boundi : i < length (countDown a b))
: nth i (countDown a b) d = a - i - 1.
Admitted.
Definition allLE := fix f l m := match l with
| nil => true
| a :: l0 => if Nat.leb a m then f l0 m else false
end.
Definition drop {A} := fix f (l : list A) n := match n with
| 0 => l
| S a => match l with
| nil => nil
| _ :: l2 => f l2 a
end
end.
Theorem list_nth_rect_aux {A : Type} (P : list A -> list A -> nat -> Type)
(Pnil : forall l, P l nil (length l))
(Pcons : forall i s l d (boundi : i < length l), P l s (S i) -> P l ((nth i l d) :: s) i)
l s i (size : length l = i + length s) (sub : s = drop l i) : P l s i.
Admitted.
Theorem list_nth_rect {A : Type} (P : list A -> list A -> nat -> Type)
(Pnil : forall l, P l nil (length l))
(Pcons : forall i s l d (boundi : i < length l), P l s (S i) -> P l ((nth i l d) :: s) i)
l s (leqs : l = s): P l s 0.
Admitted.
Theorem allLE_countDown a b : allLE (countDown a b) a = true.
remember (countDown a b) as l.
refine (list_nth_rect (fun l s _ => l = countDown a b -> allLE s a = true) _ _ l l eq_refl Heql);
intros; subst; [ apply eq_refl | ].
rewrite countDown_nth; [ | apply boundi ].
pose proof (Nat.le_sub_l a (i + 1)).
rewrite Nat.sub_add_distr in H0.
apply leb_correct in H0.
simpl; rewrite H0; clear H0.
apply (H eq_refl).
Qed.
所以，我有 list_nth_rect 并且能够根据需要使用它和 refine 通过引用第 n 个元素来证明定理。但是，我必须自己构建命题 P。通常，您想使用归纳法。
这需要区分哪些元素是原始列表 l，哪些是引入的子列表 s。所以，我可以使用 remember.
Theorem allLE_countDown a b : allLE (countDown a b) a = true.
remember (countDown a b) as s.
remember s as l.
rewrite Heql.
这让我处于
a, b : nat
s, l : list nat
Heql : l = s
Heqs : l = countDown a b
============================
allLE s a = true
但是，我好像不能像上面那样通过等式。当我尝试
induction l, s, Heql using list_nth_rect.
我收到错误
Error: Abstracting over the terms "l", "s" and "0" leads to a term
fun (l0 : list ?X133@{__:=a; __:=b; __:=s; __:=l; __:=Heql; __:=Heqs})
(s0 : list ?X133@{__:=a; __:=b; __:=s; __:=l0; __:=Heql; __:=Heqs})
(_ : nat) =>
(fun (l1 l2 : list nat) (_ : l1 = l2) =>
l1 = countDown a b -> allLE l2 a = true) l0 s0 Heql
which is ill-typed.
Reason is: Illegal application:
The term
"fun (l l0 : list nat) (_ : l = l0) =>
l = countDown a b -> allLE l0 a = true" of type
"forall l l0 : list nat, l = l0 -> Prop"
cannot be applied to the terms
"l0" : "list nat"
"s0" : "list nat"
"Heql" : "l = s"
The 3rd term has type "l = s" which should be coercible to
"l0 = s0".
那么，我该如何改变归纳原理
这样它就可以与归纳策略一起使用？
看起来它在两者之间变得混乱
外部变量和内部变量
功能。但是，我没有办法说话
关于不在范围内的内部变量。
这很奇怪，因为用
毫无问题地完善作品。
我知道匹配，有子句，但是
我不知道如何在这里应用它。
或者，有没有办法让 list_nth_rect 使用
P l l 0 还是指出l和s对应哪些变量？
首先，您可以通过重用更基本的结果更容易地证明这个结果。这是一个基于 ssreflect 库定义的版本：
From mathcomp
Require Import ssreflect ssrfun ssrbool ssrnat eqtype seq.
Definition countDown n m := rev (iota m (n - m)).
Lemma allLE_countDown n m : all (fun k => k <= n) (countDown n m).
Proof.
rewrite /countDown all_rev; apply/allP=> k; rewrite mem_iota.
have [mn|/ltnW] := leqP m n.
by rewrite subnKC //; case/andP => _; apply/leqW.
by rewrite -subn_eq0 => /eqP ->; rewrite addn0 ltnNge andbN.
Qed.
此处，iota n m 是从 n 开始计算的 m 个元素的列表，all 是 allLE 的通用版本。标准库中存在类似的函数和结果。
回到你原来的问题，确实有时我们需要在记住我们开始的整个列表的同时在列表中进行归纳。我不知道是否有办法用标准的归纳策略得到你想要的东西；我什至不知道它有一个多参数变体。当我想用这个策略证明P l时，我通常是这样进行的：
找到一个谓词
Q : nat -> Prop使得Q (length l)蕴含P l。通常，Q n的形式为n <= length l -> R (take n l) (drop n l)，其中R : list A -> list A -> Prop.通过归纳证明所有
n的Q n。
我不知道这是否回答了您的问题，但 induction 似乎接受 with 条款。因此，您可以编写以下内容。
Theorem allLE_countDown a b : allLE (countDown a b) a = true.
remember (countDown a b) as s.
remember s as l.
rewrite Heql.
induction l, s, Heql using list_nth_rect
with (P:=fun l s _ => l = countDown a b -> allLE s a = true).
但好处非常有限w.r.t。 refine 版本，因为您需要手动指定谓词。
现在，我将如何使用标准库中的对象来证明这样的结果。
Require Import List. Import ListNotations.
Require Import Omega.
Definition countDown1 := fix f a i := match i with
| 0 => nil
| S i0 => (a + i0) :: f a i0
end.
(* countDown from a number to another, excluding greatest. *)
Definition countDown a b := countDown1 b (a - b).
Theorem countDown1_nth a i k d (boundi : k < i) :
nth k (countDown1 a i) d = a + i -k - 1.
Proof.
revert k boundi.
induction i; intros.
- inversion boundi.
- simpl. destruct k.
+ omega.
+ rewrite IHi; omega.
Qed.
Lemma countDown1_length a i : length (countDown1 a i) = i.
Proof.
induction i.
- reflexivity.
- simpl. rewrite IHi. reflexivity.
Qed.
Theorem countDown_nth a b i d (boundi : i < length (countDown a b))
: nth i (countDown a b) d = a - i - 1.
Proof.
unfold countDown in *.
rewrite countDown1_length in boundi.
rewrite countDown1_nth.
replace (b+(a-b)) with a by omega. reflexivity. assumption.
Qed.
Theorem allLE_countDown a b : Forall (ge a) (countDown a b).
Proof.
apply Forall_forall. intros.
apply In_nth with (d:=0) in H.
destruct H as (n & H & H0).
rewrite countDown_nth in H0 by assumption. omega.
Qed.
编辑： 你可以陈述一个辅助引理来做出更简洁的证明。
Lemma Forall_nth : forall {A} (P:A->Prop) l,
(forall d i, i < length l -> P (nth i l d)) ->
Forall P l.
Proof.
intros. apply Forall_forall.
intros. apply In_nth with (d:=x) in H0.
destruct H0 as (n & H0 & H1).
rewrite <- H1. apply H. assumption.
Qed.
Theorem allLE_countDown a b : Forall (ge a) (countDown a b).
Proof.
apply Forall_nth.
intros. rewrite countDown_nth. omega. assumption.
Qed.
问题在于，无论好坏，induction 似乎都假设其论点是独立的。那么，解决方案就是让 induction 从 Heql:
l 和 s
Theorem list_nth_rect {A : Type} {l s : list A} (P : list A -> list A -> nat -> Type)
(Pnil : P l nil (length l))
(Pcons : forall i s d (boundi : i < length l), P l s (S i) -> P l ((nth i l d) :: s) i)
(leqs : l = s): P l s 0.
Admitted.
Theorem allLE_countDown a b : allLE (countDown a b) a = true.
remember (countDown a b) as s.
remember s as l.
rewrite Heql.
induction Heql using list_nth_rect;
intros; subst; [ apply eq_refl | ].
rewrite countDown_nth; [ | apply boundi ].
pose proof (Nat.le_sub_l a (i + 1)).
rewrite Nat.sub_add_distr in H.
apply leb_correct in H.
simpl; rewrite H; clear H.
assumption.
Qed.
我不得不稍微改变 list_nth_rect 的类型；希望我没有弄错。