Bonak.νType.RewLemmas

A few rewriting lemmas not in the standard library

Import Logic.EqNotations.
From Bonak Require Import Notation.

Lemma rew_rew {A} {x y: A} (H : x = y) P {a: P x} :
rew <- [P] H in rew [P] H in a = a.
  now destruct H.
Qed.

Lemma rew_rew' {A} {x y: A} (H: x = y) P {a: P y} :
rew [P] H in rew <- [P] H in a = a.
  now destruct H.
Qed.

Lemma rew_context {A} {x y: A} (eq: x = y) {P} {a: P x}
{Q: a, P a Type}: Q y (rew eq in a) = Q x a.
  now destruct eq.
Qed.

Lemma rew_pair: A {a} (P Q: A Type) (x: P a) (y: Q a)
  {b} (H: a = b), (rew H in x, rew H in y) =
                   rew [fun a ⇒ (P a × Q a)%type] H in (x, y).
Proof.
  now destruct H.
Qed.

Lemma rew_sigT {A x} {P: A Type} (Q: a, P a Type)
  (u: { p: P x & Q x p }) {y} (H: x = y)
    : rew [fun x{ p : P x & Q x p }] H in u
      = (rew H in u.1; rew dependent [fun x H Q x (rew H in u.1)] H in u.2).
Proof.
  now destruct H, u.
Qed.

Lemma rew_existT_curried {A x} {P: A Type} {Q: {a & P a} Type}
   {y} {H: x = y}
   {u: P x} {v: Q (x; u)}
   {u': P y} {v': Q (y; u')}
   {Hu: rew H in u = u'} {Hv: rew (=H; Hu) in v = v'}:
   rew [fun x{a: P x & Q (x; a)}] H in (u; v) = (u'; v').
Proof.
   now destruct Hu, Hv, H.
Qed.

Theorem rew_permute A (P Q: A Type) (x y: A) (H: z, Q z = P z)
  (H': x = y) (a: P x) :
  rew <- [id] H y in rew [P] H' in a =
  rew [Q] H' in rew <- [id] H x in a.
Proof.
  now destruct H'.
Qed.

Theorem rew_permute' A (P Q: A Type) (x y: A) (H: z, P z = Q z)
  (H': x = y) (a: P x) :
  rew [id] H y in rew [P] H' in a =
  rew [Q] H' in rew [id] H x in a.
Proof.
  now destruct H'.
Qed.

Lemma rew_swap : A (P : A Type) a b (H: a = b) (x : P a) (y : P b),
  x = rew <- H in y rew H in x = y.
Proof.
  now destruct H.
Qed.

Lemma rew_app A (P : A Type) (x y : A) (H H' : x = y) (a : P x) :
  H = H' rew <- [P] H in rew [P] H' in a = a.
Proof.
  intros × →. now destruct H'.
Qed.

Lemma eq_ind_r_refl {A} {x y: A} {H: x = y} :
  eq_ind_r (fun xeq x y) eq_refl H = H.
Proof.
  now destruct H.
Qed.

Lemma map_subst_app {A B} {x y} {𝛉: A} (H: x = y :> B) (P: A B Type)
  (f: 𝛉, P 𝛉 x):
  rew [P 𝛉] H in f 𝛉 = (rew [fun x 𝛉, P 𝛉 x] H in f) 𝛉.
Proof.
  now destruct H.
Defined.

Lemma sigT_commute A (P : A Type) B (Q : B Type) C c
  (d : a, P a { b & Q b}) (e : b, Q b C) :
  match match c with (a; p)d a p end with
  | (b; q)e b q
  end =
  match c with
  | (a; p)match d a p with (b; q)e b q end
  end.
Proof.
  now destruct c.
Defined.