coq - Coq定理证明：Peano算术中的简单分数定律(Coq theorem proving: Simple fraction law in peano arithmetic)

Question

I am learning coq and am trying to prove equalities in peano arithmetic.

(我正在学习coq，并试图证明Peano算术中的相等性。)

I got stuck on a simple fraction law.

(我陷入了简单的分数定律。)

We know that (n + m) / 2 = n / 2 + m / 2 from primary school.

(我们从小学知道（n + m）/ 2 = n / 2 + m / 2。)

In peano arithmetic this does only hold if n and m are even (because then division produces correct results).

(在Peano算术中，仅当n和m为偶数时才成立（因为除法会产生正确的结果）。)

Compute (3 / 2) + (5 / 2). (*3*)
Compute (3 + 5) / 2. (*4*)

So we define:

(因此我们定义：)

Theorem fraction_addition: forall n m: nat , 
    even n -> even m ->  Nat.div2 n + Nat.div2 m = Nat.div2 (n + m).

From my understanding this is a correct and provable theorem.

(据我了解，这是一个正确且可证明的定理。)

I tried an inductive proof, eg

(我尝试了归纳证明，例如)

intros n m en em.
induction n.
- reflexivity.
- ???

Which gets me into the situation that

(这使我陷入这种情况)

en = even (S n) and IHn : even n -> Nat.div2 n + Nat.div2 m = Nat.div2 (n + m) , so i don't find a way to apply the induction hypothesis.

(en = even (S n)和IHn : even n -> Nat.div2 n + Nat.div2 m = Nat.div2 (n + m) ，所以我没有找到适用归纳假设的方法。)

After long research of the standard library and documentation, i don't find an answer.

(经过对标准库和文档的长期研究，我没有找到答案。)

  ask by Falco Winkler translate from so

Answer 1

You need to strengthen your induction hypothesis in cases like this.

(在这种情况下，您需要加强归纳假设。)

One way of doing this is by proving an induction principle like this one:

(一种实现方法是证明这样的归纳原理：)

From Coq Require Import Arith Even.
Lemma nat_ind2 (P : nat -> Prop) :
  P 0 ->
  P 1 ->
  (forall n, P n -> P (S n) -> P (S (S n))) ->
  forall n, P n.
Proof.
now intros P0 P1 IH n; enough (H : P n / P (S n)); [|induction n]; intuition.
Qed.

nat_ind2 can be used as follows:

(nat_ind2可以如下使用：)

Theorem fraction_addition n m :
  even n -> even m ->
  Nat.div2 n + Nat.div2 m = Nat.div2 (n + m).
Proof.
  induction n using nat_ind2.
  (* here goes the rest of the proof *)
Qed.