我怎样才能证明对于所有的 a b，a <=？ b = 真 -> a <=?在 Coq 中 S b = true

Question

是否可以在 Coq 中证明这个 forall (a b : nat), a <=? b = true -> a <=? S b = true.？

到目前为止我试过了

Lemma leb_0_r : forall x, x <=? 0 = true -> x = 0.
  intros. induction x. reflexivity. discriminate H. 
Qed.

Lemma leb_S : forall a b, a <=? b = true -> a <=? S b = true.
  intros a b Hab. induction b. apply leb_0_r in Hab. now rewrite Hab.

但在这里我陷入了归纳假设

1 subgoal

a, b : nat
Hab : (a <=? S b) = true
IHb : (a <=? b) = true -> (a <=? S b) = true

========================= (1 / 1)

(a <=? S (S b)) = true

我也试过感应

Lemma leb_S : forall a b, a <=? b = true -> a <=? S b = true.
  intros a b Hab. induction a. reflexivity. simpl. destruct b.
  discriminate Hab. simpl in Hab.


1 subgoal

a, b : nat
Hab : (a <=? b) = true
IHa : (a <=? S b) = true -> (a <=? S (S b)) = true

========================= (1 / 1)

(a <=? S b) = true

问题是我总是到达 S a <= b 或 a <= S b 而我无法简化它。

在这里发帖后，我意识到IHa的结论等于第二次尝试的目标，反之亦然:thinking:

Answer 1

您可以尝试不使用归纳法，而是使用 <= 关系的传递性。

Answer 2

我不确定您是在学习 Coq 并且这是一个练习，还是您在使用 Coq。在后一种情况下，答案是：我原以为 lia 策略可以做到这一点，但它需要一些按摩：

Require Import PeanoNat.
Require Import Lia.

Lemma leb_0_r : forall x, x <=? 0 = true -> x = 0.
Proof.
  intros.
  Fail lia.
  Search (_ <=? _ = true).
  apply Nat.leb_le in H.
  lia.
Qed.

在前一种情况下，我需要知道您可以使用什么。例如。这有效：

Require Import PeanoNat.

Lemma leb_0_r : forall x, x <=? 0 = true -> x = 0.
Proof.
  intros.
  apply Nat.leb_le in H.
  inversion H.
  reflexivity.
Qed.

我怎样才能证明对于所有的 a b，a <=？ b = 真 -> a <=?在 Coq 中 S b = true

How can I proove forall a b, a <=? b = true -> a <=? S b = true in Coq

coq