The Coq mailing list

[Laurent Théry <Laurent.Thery AT sophia.inria.fr>]

Pierre-Marie Pédrot wrote:
> Dear Coq users,
>
> I've fighting for some days with equality and dependent types for very
> simple cases. I'm currently trying to fiddle with Fin, which defined as
> in CPDT :
>
> Inductive Fin : nat -> Type :=
> | Fin0 : forall n, Fin (S n)
> | FinS : forall n, Fin n -> Fin (S n).
>
> and I would like to find an axiom-free proof of decidability of equality
> for Fin :
>
> Lemma Fin_eq_dec : forall n (x y : Fin n), {x = y} + {x <> y}.
>
>   
Following Adam's convoy pattern but in a more tactic-base construction 
this gives:

Inductive Fin : nat -> Type :=
| Fin0 : forall n, Fin (S n)
| FinS : forall n, Fin n -> Fin (S n).

Definition prev n (x: Fin n) :=
 match x in Fin n return option (Fin (pred n)) with
 | Fin0 _ => None
 | FinS _ y => Some y
 end.

Lemma prev_eq n (x y: Fin n) : prev n x = prev n y -> x = y.
intros n x; case x; simpl; clear n x.
intros n y.
change
 ((fun (n : nat) =>
       match n return Fin n -> Prop with
       | O => fun _ => True
       | S n2 => fun y => None = prev _ y -> Fin0 n2 = y
       end) (S n) y).
case y; simpl; auto.
intros; discriminate.
intros n x y; generalize x.
change
 ((fun (n : nat) =>
       match n return Fin n -> Prop with
       | O => fun _  => True
       | S n2 => fun y => forall f, Some f = prev _ y -> FinS n2 f = y
       end) (S n) y).
case y; simpl; auto.
intros; discriminate.
intros n1 f0 f1 HH; injection HH; intros; subst; auto.
Qed.

Definition Fin_eq_dec : forall n (x y : Fin n), {x = y} + {x <> y}.
fix 1.
intros n; case n.
intros x; inversion x.
intros n1 x1 y1.
case_eq (prev (S n1) x1); [intros x2 Hx1 | intros Hx1];
(case_eq (prev (S n1) y1); [intros y2 Hy1 | intros Hy1]).
case (Fin_eq_dec n1 x2 y2).
intros Heq.
left.
apply prev_eq.
rewrite Hx1, Hy1, Heq; auto.
intros HH; right; intros HH1; case HH.
generalize Hx1; rewrite HH1, Hy1; intros HH2; injection HH2; auto.
right.
intros HH; generalize Hx1.
rewrite HH, Hy1; discriminate.
right.
intros HH; generalize Hx1.
rewrite HH, Hy1; discriminate.
left.
apply prev_eq.
rewrite Hx1, Hy1; auto.
Defined.