Equality of type with equal indices do not typecheck

by

Summary

This postmortem analyzes a typechecking failure in a Rocq/Coq development where a refinement proof between two labeled transition systems (B2 refining B1 under a function f) fails. The core issue is that the typechecker cannot see that h n = h (n+1) or h (n+1) = h n + 2 at the point where constructors are applied, even though the lemmas h_even and h_odd prove these equalities. The fix requires rewriting the goal’s type before applying constructors, not after.

Root Cause

The failure arises because:

  • Constructors of inductive types are not dependent on propositional equalities unless the goal is explicitly rewritten.
  • In the failing lemma, the goal expects a term of type B1 (h (n+1)).
  • The proof attempts to produce a term of type B1 (h n) and then rewrite using h_even.
  • But Coq does not retroactively change the type of a constructed term.
  • Therefore, the typechecker rejects the proof before the rewrite can take effect.

Why This Happens in Real Systems

Real proof assistants behave this way because:

  • Inductive constructors are rigid: their indices must match exactly.
  • Rewriting does not change already-constructed terms; it only transforms goals or hypotheses.
  • Dependent types require index alignment before constructor application, not after.
  • Automation (like auto) does not rewrite indices unless explicitly instructed.

These constraints prevent subtle logical inconsistencies and maintain definitional equality discipline.

Real-World Impact

This type of issue commonly leads to:

  • Unexpected proof failures even when the mathematics is correct.
  • Confusing error messages about mismatched indices.
  • Long debugging sessions where the engineer must manually rewrite goals.
  • Fragile proofs if rewriting is not done in the right order.

Example or Code (if necessary and relevant)

A correct version of the problematic lemma looks like this:

Lemma RefineIncrEven :
  ∀ n (b2 : B2 n) (ev : Nat.Even n),
    f (incr2_even ev b2) = stutter1 (f b2).
Proof.
  intros n b2 ev.
  simpl.
  rewrite h_even by exact ev.
  reflexivity.
Qed.

And for the odd case:

Lemma RefineIncrOdd :
  ∀ n (b2 : B2 n) (od : Nat.Odd n),
    f (incr2_odd od b2) = incr1 (f b2).
Proof.
  intros n b2 od.
  simpl.
  rewrite h_odd by exact od.
  reflexivity.
Qed.

The key move is:

Rewrite the goal’s index before applying the constructor.

How Senior Engineers Fix It

Experienced Rocq/Coq engineers apply several reliable techniques:

  • Rewrite the goal index first:
    • rewrite (h_even ev).
    • rewrite (h_odd od).
  • Use dependent destruction or eq_rect only when necessary, but avoid them when a simple rewrite suffices.
  • Inspect the goal before constructing anything.
  • Avoid building terms whose indices do not yet match the goal.
  • Use simpl and cbn to expose the index before rewriting.

The general rule they follow:

Never apply a dependent constructor until the index matches exactly.

Why Juniors Miss It

Less experienced engineers often struggle because:

  • They assume rewriting after constructor application will fix the type mismatch.
  • They do not realize that constructor indices must match definitionally, not propositionally.
  • They rely too heavily on automation (auto, trivial) that does not rewrite dependent indices.
  • They underestimate how strict Coq is about definitional equality.
  • They do not inspect the goal’s type before constructing terms.

A junior engineer typically thinks: “I proved h n = h (n+1), so Coq should accept this,” but Coq requires the rewrite to occur before the constructor is used.

If you want, I can walk through how to generalize this pattern so you never hit this class of error again.

Leave a Comment