Coq中自然数的加法

Question

Coq 的标准库给出了 Peano 自然数和加法：

Inductive nat : Set :=
  | O : nat
  | S : nat -> nat.

Fixpoint add n m :=
  match n with
  | 0 => m
  | S p => S (add p m)
  end.

我很好奇如果把加法的fix_definition改成

Fixpoint add n m :=
  match n with
  | 0 => m
  | S p => add p (S m)
  end.

新增的和老的一样吗？我试图通过证明 forall n m, add (S n) m = S (add n m) 来证明它们的等价性，但失败了。

Answer 1

是的，这两个加法是等价的，您可以使用标准库中的引理 plus_n_Sm : forall n m : nat, S (n + m) = n + S m（使用 Search "+" (S _). 找到）和适当的归纳假设（例如 P(n) := forall m, n + m = add n m）来证明它.

Answer 2

为了证明你的辅助引理，你需要小心引入什么。如果你不引入 m，你会得到一个更一般的归纳假设，如：

Require Import Nat.

Print add.

Fixpoint my_add n m :=
  match n with
  | 0 => m
  | S p => my_add p (S m)
  end.

Lemma my_add_S_r: forall n m, my_add n (S m) = S (my_add n m).
Proof.
  (* Note: don't introduce m here - you get a more general induction hypothesis this way *)
  intros n.
  induction n.
  - intros; reflexivity.
  - intros; cbn. rewrite IHn. reflexivity.
Qed.

Lemma my_add_equiv: forall n m, add n m = my_add n m.
intros.
induction n.
- reflexivity.
- cbn. rewrite my_add_S_r. rewrite IHn. reflexivity.
Qed.

Coq中自然数的加法

Addition of natural numbers in Coq

coq