"Abstracting over the terms … is ill-defined" when destructuring

Question

I have been frequently running into an error in Coq when attempting to destruct a term of a dependent type. I am aware that there are two questions on Stack Overflow related to this issue, but neither of them are general enough for me to grasp in the context of my own proofs.

Here is a simple example of where the error occurs.

We define a type family t:

Inductive t: nat -> Set :=
| t_S: forall (n: nat), t (S n).

We will now try to prove that every member t (S n) of this type family is inhabited by a single term, namely t_S n.

Goal forall (n: nat) (p: t (S n)), p = t_S n.

We start with:

intros n p.

The next step to me would be to destruct p:

destruct p.

…but this runs into the following error:

Abstracting over the terms "n0" and "p" leads to a term fun (n1 : nat) (p0 : t n1) => p0 = t_S n
which is ill-typed.
Reason is: Illegal application: 
The term "@eq" of type "forall A : Type, A -> A -> Prop"
cannot be applied to the terms
 "t n1" : "Set"
 "p0" : "t n1"
 "t_S n" : "t (S n)"
The 3rd term has type "t (S n)" which should be coercible to "t n1".

It seems to me that it is trying to convert p into t_S n1, but somehow fails to reconcile the fact that n1 must be equal to n, thus causing opposite sides of = to have mismatching types.

Why does this occur and how does one get around this?

SCappella SCappella · Accepted Answer · 2019-12-07T07:52:56

A simple proof of that fact is

Goal forall (n: nat) (p: t (S n)), p = t_S n.
Proof.
  intros n p.
  refine (
    match p with
    | t_S n => _
    end
  ).
  reflexivity.
Qed.

To understand how this works, it'll help to see the proof term that Coq constructs here.



Goal forall (n: nat) (p: t (S n)), p = t_S n.
Proof.
  intros n p.
  refine (
    match p with
    | t_S n => _
    end
  ).
  reflexivity.
  Show Proof.

(fun (n : nat) (p : t (S n)) =>
 match
   p as p0 in (t n0)
   return
     (match n0 as x return (t x -> Type) with
      | 0 => fun _ : t 0 => IDProp
      | S n1 => fun p1 : t (S n1) => p1 = t_S n1
      end p0)
 with
 | t_S n0 => eq_refl
 end)

So the proof term isn't a simple match on p. Instead, Coq cleverly generalizes the S n in p: t (S n) while changing the type of the goal to that it still matches in the S n case.

Specifically, the proof term above uses the type

match (S n) as n' return (t n' -> Type) with
| 0 => fun p => IDProp (* Basically the same as `unit`; a singleton type *)
| S n' => fun p => p = t_S n'
end p

So obviously this is the same as p = t_S n, but it allows S n to be generalized. Every instance of n is now of the form S n, so it can be universally replaced with some n'. Here's how it would be written in individual tactics.

Goal forall (n: nat) (p: t (S n)), p = t_S n.
Proof.
  intro n.
  change (
    forall p: t (S n),
      match (S n) as n' return (t n' -> Type) with
      | 0 => fun p => Empty_set (* This can actually be any type. We may as well use the simplest possible type. *)
      | S n' => fun p => p = t_S n'
      end p
  ).
  generalize (S n); clear n.
  intros n p.
  (* p: t n, not t (S n), so we can destruct it *)
  destruct p.
  reflexivity.
Qed.

So why is all this necessary? Induction (and as a special case, case matching) requires that any indices in the inductive type be general. This can be seen by looking at the induction principle for t: t_rect: forall (P: forall n: nat, t n -> Type), (forall n: nat, P (S n) (t_S n)) -> forall (n: nat) (x: t n), P n x.

When using induction, we need P to be defined for all natural numbers. Even though the other hypothesis for the induction, forall n: nat, P (S n) (t_S n), only uses P (S n), it still needs to have a value at zero. For the goal you had, P (S n) p := (p = t_S n), but P wasn't defined for 0. What the clever trick of changing the goal does is extend P to 0 in a way that agrees with the definition at S n.

"Abstracting over the terms … is ill-defined" when destructuring

1 Answers