我如何在 Coq 中证明 0 <= a < b -> r a b = a？

Question

我正在尝试证明这个引理

Require Import ZArith.
Require Import Lia.

Open Scope Z_scope.
Import Z.

Ltac Zify.zify_post_hook ::= Z.to_euclidean_division_equations.

Lemma rem_pos : forall {a b : Z},
  0 <= a < b ->
  rem a b = a.
 intros. lia.

此时我从 lia 收到 Tactic failure: Cannot find witness.。

我是不是做错了什么？

Answer 1

搜索是你的朋友：

Require Import ZArith.

Open Scope Z_scope.
Import Z.

Lemma rem_pos : forall {a b : Z},
  0 <= a < b ->
  rem a b = a.
Proof.
  intros a b H.
  Search (rem ?a ?b = ?a).
  apply rem_small.
  assumption.
Qed.

据我所知，模运算没有专门的自动化证明。 Coq-hammer 能够使用 e-prover 和 Z3 后端解决它（即将在 Coq 平台中推出）：

Require Import ZArith.
From Hammer Require Import Hammer.

Open Scope Z_scope.
Import Z.

Lemma rem_pos : forall {a b : Z},
  0 <= a < b ->
  rem a b = a.
Proof.
  hammer.
Qed.

但这对于 ATP 来说是微不足道的，因此不是一个合理的测试。问题是不能轻易地将 ATP 与 lia 的力量结合起来。

根据我的经验，你最好的选择是 Search 一个充分的引理并用 lia 解决先决条件。

我如何在 Coq 中证明 0 <= a < b -> r a b = a？

How can I proove 0 <= a < b -> rem a b = a in Coq?

coq