假设和证明关于不同类型相等性的定理（证明具有依赖类型的两个偶数之和的交换性）

Question

简短的问题是：如何从下面的代码

Inductive even : nat -> Type :=
| EZ : even 0
| ES : forall n, odd n -> even (S n)
with odd : nat -> Type :=
| OS : forall n, even n -> odd (S n).

Fixpoint even_sum n1 n2 (e1 : even n1) : even n2 -> even (n1 + n2) :=
  match e1 with
  | EZ => fun e2 => e2
  | ES _ o1 => fun e2 => ES (odd_sum o1 e2)
  end
with odd_sum n1 n2 (o : odd n1) : even n2 -> odd (n1 + n2) :=
  match o with
  | OS _ e => fun e2 => OS (even_sum e e2)
  end.

Theorem add_comm_right_0 : forall n, n = n + 0.
    induction n; crush.
Defined.

Theorem add_comm : forall (n m : nat), n + m = m + n.
  induction n; intros.
  apply add_comm_right_0.
  crush.
Defined.  

Theorem even_sum_commut' : forall n1 n2, even (n1 + n2) -> even (n2 + n1).
  intros.  
  rewrite add_comm.
  apply H.
Defined.
 
Theorem odd_sum_commut' : forall n1 n2, odd (n1 + n2) -> odd (n2 + n1).
  intros. rewrite add_comm. assumption.
Defined.

Scheme even_mut := Induction for even Sort Prop
  with odd_mut := Induction for odd Sort Prop.

Theorem even_sum_right_0 : forall n1 (e1 : even n1),
    e1 = even_sum_commut' n1 0 (even_sum e1 EZ).
Proof.
   apply (even_mut (fun n en => en = even_sum_commut' n 0 (even_sum en EZ)) 
                   (fun n on => on = odd_sum_commut' n 0 (odd_sum on EZ))). 
   - simpl. reflexivity. 
   - intros. simpl.
Admitted.

Theorem even_sum_commut : forall n1 n2 (e1 : even n1) (e2 : even n2),
    even_sum e1 e2 = even_sum_commut' _ _ (even_sum e2 e1).
Proof.
Admitted.

如我所见，even_sum e1 e2 和 even_sum e2 e1 是同一个词（根据 even_sum 的定义）。所以，在我看来定理应该是可证明的。但我不确定（类型不同，在我看来这是问题的一部分）。

下面是长话短说

我正在阅读 Adam Chlipala 的 cpdt (great thanks to the author!). And also I'm trying to solve exercises he provides。前 4 个练习对我来说很高兴解决它们（因为这是相当快的事情）。但是我遇到了一个练习，如果修改它会变得更有趣。

第 0.1 章来自 InductiveTypes，练习 5。

Define mutually inductive types of even and odd natural numbers, such that any natural number is isomorphic to a value of one of the two types. (This problem does not ask you to prove that correspondence, though some interpretations of the task may be interesting exercises.) Write a function that computes the sum of two even numbers, such that the function type guarantees that the output is even as well. Prove that this function is commutative.

使用下一个定义可以轻松解决此任务：

Inductive nat_even : Type :=
  | EZ' : nat_even
  | EN' : nat_odd -> nat_even
with nat_odd : Type :=
  | ON' : nat_even -> nat_odd.

但我想尝试一下上面给出的另一个定义（灵感来自书中给出的定义）。

一个小的解释。请注意：这不是教科书练习，这是（我自己的）修改，使任务有点难以解决（至少对我来说）。本书的原始任务相当简单（好吧，你需要考虑一下，但仍然如此）。所以，这里没有任何可能的“违反荣誉守则”......

欢迎任何想法，我很想知道“如何以更好的方式做到这一点”或“如何以另一种方式做到这一点”。我的意思是“如何为不同类型制定和证明定理，这可能吗”。

可能有人可以给我 link 到 textbook/paper 阅读。这也太棒了。

Answer 1

解决此类问题的最佳方法是忘记类型依赖性。在这种情况下，even n 和 odd n 的证明完全由 n 表征，如下引理所示。

From Coq Require Import ssreflect ssrfun.
Require Import Coq.Arith.Arith.

Set Implicit Arguments.

Inductive even : nat -> Type :=
| EZ : even 0
| ES : forall n, odd n -> even (S n)
with odd : nat -> Type :=
| OS : forall n, even n -> odd (S n).

Fixpoint even_or_odd (n : nat) : even n + odd n :=
  match n with
  | 0   => inl EZ
  | S m => match even_or_odd m with
           | inl p => inr (OS p)
           | inr p => inl (ES p)
           end
  end.

Fixpoint nat_of_evenK n (p : even n) : even_or_odd n = inl p :=
  match p with
  | EZ      => erefl
  | @ES m p => congr1 (fun r : even m + odd m =>
                         match r with
                         | inl q => inr (OS q)
                         | inr q => inl (ES q)
                         end)
                      (nat_of_oddK p)
  end

with nat_of_oddK n (p : odd n) : even_or_odd n = inr p :=
  match p with
  | @OS m p => congr1 (fun r : even m + odd m =>
                         match r with
                         | inl q => inr (OS q)
                         | inr q => inl (ES q)
                         end)
                      (nat_of_evenK p)
  end.

Lemma even_irrel n (p q : even n) : p = q.
Proof.
suff [//] : inl p = inl q :> even n + odd n.
by rewrite -2!nat_of_evenK.
Qed.

Lemma odd_irrel n (p q : odd n) : p = q.
Proof.
suff [//] : inr p = inr q :> even n + odd n.
by rewrite -2!nat_of_oddK.
Qed.

特别是，

Definition even_comm_cast n m : even (n + m) -> even (m + n) :=
  let: erefl := Nat.add_comm n m in id.

Lemma even_addC n m (p : even (n + m)) (q : even (m + n)) :
  p = even_comm_cast m n q.
Proof.
rewrite /even_comm_cast.
case: (n + m) / Nat.add_comm p => //= p; exact: even_irrel.
Qed.

假设和证明关于不同类型相等性的定理（证明具有依赖类型的两个偶数之和的交换性）

Postulate and prove theorem about equality for different types (Prove commutativity for the sum of two even numbers with dependent types)

coq