'else' 在定义中 - Coq

Question

首先，我是证明论和 coq 的新手，所以我希望答案简单易懂。

我正在尝试建立定义以最终定义素数；我目前正在尝试定义可分性，并且在我的定义中我已经写了真实的案例。

每个 nat 都可以被 1 整除。
每个 nat 都可以与其自身整除。

还有我的归纳案例（适用于'(i > j)'）：

每个 nat 'i' 都可以被 'j' 整除，如果 '(i - j)' 可以被 'j' 整除。

现在在我随后的一些引理中，我需要所有不满足这个的都是假的。

我将如何在我的定义中对其进行编码？我在想类似的事情，当上述 none 适用时 --> 错误。 - 在某种意义上是定义的 else 语句。

Answer 1

在构建 Coq 的 constructive logic 中，一个命题只有当我们有直接证据（即证明）时才会被考虑 "true"。所以，不需要这样的 "else" 部分，因为任何无法构造的东西在某种意义上都是错误的。如果您的 "is divisible by" 关系的 none 个案例适用，您将能够通过矛盾来证明您的陈述，即推导 False.

例如，如果我们有这样的可除性定义：

(* we assume 0 divides 0 *)
Inductive divides (m : nat) : nat -> Prop :=
  | div_zero: divides m 0
  | div_add: forall n, divides m n -> divides m (m + n).
Notation "( x | y )" := (divides x y) (at level 0).

然后我们可以用inversion证明3不能整除5的事实，它处理不可能的情况：

Fact three_does_not_divide_five:
  ~(3 | 5).
Proof.
  intro H. inversion H. inversion H2.
Qed.

注意：我们可以检查我们的 divides 关系是否通过引入替代 ("obvious") 定义来捕获可分性的概念：

Definition divides' x y := exists z, y = z*x.
Notation "( x |' y )" := (divides' x y) (at level 0).

并证明它们的等价性：

Theorem divides_iff_divides' (m n : nat) :
    (m | n) <-> (m |' n).
Admitted. (* it's not hard *)

Answer 2

另一种方法是用除法和余数来定义可整除性：

定义一个 divn : nat -> nat -> nat * nat 运算，将两个数相除并 returns 余数。
那么，可分性表示为"remainder is equal to 0"。您需要计算出一些细节，例如 0.
然后，一个伪造的可分性假设相当于一个假等式，通常可以通过 congruence 来解决。您可以使用标准理论来操纵余数的相等性。

这是 math-comp 库中使用的方法，请参阅 http://math-comp.github.io/math-comp/htmldoc/mathcomp.ssreflect.div.html

'else' 在定义中 - Coq

'else' in definitions - Coq

coq