我正在研究以下定理的证明 Sn_le_Sm__n_le_m
在 IndProp.v
的 Software Foundations (Vol 1: Logical Foundations) .
Theorem Sn_le_Sm__n_le_m : ∀n m,
S n ≤ S m → n ≤ m.
Proof.
intros n m HS.
induction HS as [ | m' Hm' IHm'].
- (* le_n *) (* Failed Here *)
- (* le_S *) apply IHSm'.
Admitted.
其中,
le (i.e., ≤)
的定义是:Inductive le : nat → nat → Prop :=
| le_n n : le n n
| le_S n m (H : le n m) : le n (S m).
Notation "m ≤ n" := (le m n).
之前
induction HS
,上下文和目标如下:n, m : nat
HS : S n <= S m
______________________________________(1/1)
n <= m
在第一个子弹点
-
,上下文以及目标是:n, m : nat
______________________________________(1/1)
n <= m
我们必须证明的地方
n <= m
没有任何上下文,这显然是不可能的。为什么不生成
S n = S m
(然后 n = m
)用于 le_n
案例在 induction HS
?
最佳答案
这里的主要问题 - 我认为 - 不可能在 HS
上使用归纳证明定理因为没有办法说 n
只有关于 S n
的假设因为不是 le
的构造函数不要改变 n
的值.但无论如何,在第一个子弹之后的原因-
没有假设是因为调用 induction
具有用对应于每个构造函数的值替换所有出现的属性参数的效果,在这种情况下它没有帮助,因为被替换的术语 S n
任何地方都没有提到。有一些技巧可以避免这种情况。例如,您可以将 n 替换为 pred(S n)
如下。
Theorem Sn_le_Sm__n_le_m : forall n m,
S n <= S m -> n <= m.
Proof.
intros n m HS.
assert(Hn: n=pred (S n)). reflexivity. rewrite Hn.
assert(Hm: m=pred (S m)). reflexivity. rewrite Hm.
induction HS.
- (* le_n *) apply le_n.
- (* le_S *) (* Stucks! *) Abort.
但正如我上面提到的,不可能走得更远。另一种方法是使用
inversion
这更聪明,但在某些情况下它可能无济于事,因为归纳假设是必要的。但值得了解一下。Theorem Sn_le_Sm__n_le_m : forall n m,
S n <= S m -> n <= m.
Proof.
intros n m HS.
inversion HS.
- (* le_n *) apply le_n.
- (* le_S *) (* Stucks! *) Abort.
解决问题的最佳方法是使用
remember
战术如下。Theorem Sn_le_Sm__n_le_m : forall n m,
S n <= S m -> n <= m.
Proof.
intros n m HS.
remember (S n) as Sn.
remember (S m) as Sm.
induction HS as [ n' | n' m' H IH].
- (* le_n *)
rewrite HeqSn in HeqSm. injection HeqSm as Heq.
rewrite <- Heq. apply le_n.
- (* le_S *) (* Stucks! *) Abort.
根据 Software Foundations (Vol 1: Logical Foundations)
The tactic
remember e as x
causes Coq to (1) replace all occurrences of the expression e by the variable x, and (2) add an equation x = e to the context.
无论如何,虽然不可能在
HS
上用归纳法证明这一事实。 -imo-,对 m
进行归纳将解决此案。 (注意 inversion
的使用。)Theorem Sn_le_Sm__n_le_m : forall n m,
S n <= S m -> n <= m.
Proof.
intros n.
induction m as [|m' IHm'].
- intros H. inversion H as [Hn | n' contra Hn'].
+ apply le_n.
+ inversion contra.
- intros H. inversion H as [HnSm' | n' HSnSm' Heq].
+ apply le_n.
+ apply le_S. apply IHm'. apply HSnSm'.
Qed.
关于coq - coq 中 "less than"关系的证据归纳,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56292483/