matita/matita/contribs/lambdadelta/ground/relocation/pr_eq.ma

   1 (**************************************************************************)
   2 (*       ___                                                              *)
   3 (*      ||M||                                                             *)
   4 (*      ||A||       A project by Andrea Asperti                           *)
   5 (*      ||T||                                                             *)
   6 (*      ||I||       Developers:                                           *)
   7 (*      ||T||         The HELM team.                                      *)
   8 (*      ||A||         http://helm.cs.unibo.it                             *)
   9 (*      \   /                                                             *)
  10 (*       \ /        This file is distributed under the terms of the       *)
  11 (*        v         GNU General Public License Version 2                  *)
  12 (*                                                                        *)
  13 (**************************************************************************)
  14
  15 include "ground/xoa/ex_3_2.ma".
  16 include "ground/notation/relations/ideq_2.ma".
  17 include "ground/lib/stream_eq.ma".
  18 include "ground/relocation/pr_map.ma".
  19
  20 (* EXTENSIONAL EQUIVALENCE FOR PARTIAL RELOCATION MAPS **********************)
  21
  22 (*** eq *)
  23 coinductive pr_eq: relation pr_map ≝
  24 (*** eq_push *)
  25 | pr_eq_push (f1) (f2) (g1) (g2):
  26   pr_eq f1 f2 → ⫯f1 = g1 → ⫯f2 = g2 → pr_eq g1 g2
  27 (*** eq_next *)
  28 | pr_eq_next (f1) (f2) (g1) (g2):
  29   pr_eq f1 f2 → ↑f1 = g1 → ↑f2 = g2 → pr_eq g1 g2
  30 .
  31
  32 interpretation
  33   "extensional equivalence (partial relocation maps)"
  34   'IdEq f1 f2 = (pr_eq f1 f2).
  35
  36 (*** eq_repl *)
  37 definition pr_eq_repl (R:relation …) ≝
  38            ∀f1,f2. f1 ≡ f2 → R f1 f2.
  39
  40 (*** eq_repl_back *)
  41 definition pr_eq_repl_back (R:predicate …) ≝
  42            ∀f1. R f1 → ∀f2. f1 ≡ f2 → R f2.
  43
  44 (*** eq_repl_fwd *)
  45 definition pr_eq_repl_fwd (R:predicate …) ≝
  46            ∀f1. R f1 → ∀f2. f2 ≡ f1 → R f2.
  47
  48 (* Basic constructions ******************************************************)
  49
  50 (*** eq_sym *)
  51 corec lemma pr_eq_sym: symmetric … pr_eq.
  52 #f1 #f2 * -f1 -f2
  53 #f1 #f2 #g1 #g2 #Hf #H1 #H2
  54 [ @(pr_eq_push … H2 H1) | @(pr_eq_next … H2 H1) ] -g2 -g1 /2 width=1 by/
  55 qed-.
  56
  57 (*** eq_repl_sym *)
  58 lemma pr_eq_repl_sym (R):
  59       pr_eq_repl_back R → pr_eq_repl_fwd R.
  60 /3 width=3 by pr_eq_sym/ qed-.
  61
  62 (* Alternative definition with stream_eq (specific) *************************)
  63
  64 alias symbol "subseteq" (instance 1) = "relation inclusion".
  65
  66 corec lemma stream_eq_pr_eq: stream_eq … ⊆ pr_eq.
  67 * #b1 #f1 * #b2 #f2 #H
  68 cases (stream_eq_inv_cons_bi … H) -H [|*: // ] * -b2 #Hf
  69 cases b1 /3 width=5 by pr_eq_next, pr_eq_push/
  70 qed.
  71
  72 corec lemma pr_eq_inv_stream_eq: pr_eq ⊆ stream_eq ….
  73 #g1 #g2 * -g1 -g2 #f1 #f2 #g1 #g2 #Hf * * -g1 -g2
  74 /3 width=1 by stream_eq_cons/
  75 qed-.