Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save ComFreek/00ac776c1419a81e0964fb06ca829b72 to your computer and use it in GitHub Desktop.
Save ComFreek/00ac776c1419a81e0964fb06ca829b72 to your computer and use it in GitHub Desktop.
Rewrite equality in type definitions in Coq
From Coq Require Import Init.Logic.
Axiom X: Type.
Axiom a b: X.
Axiom P: X -> Prop.
Axiom Q: P b -> Prop.
(*
Our goal is to state an axiom like `forall (pa: P a), a = b -> Q pa`.
However, that won't typecheck since Q expects an argument of type `P b`, but
we feed it an argument of type `P a`.
We need to rewrite a to b using the equality from the implication's antecedence
somehow.
Here's how:
*)
Axiom ax : forall (pa: P a) (e: a = b), Q (match e in (eq _ y) return (P y) with
| eq_refl => pa
end).
(* shorter with some notations: *)
Import EqNotations.
Axiom ax' : forall (pa: P a) (e: a = b), Q (rew e in pa).
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment