matita/matita/contribs/lambdadelta/ground/lib/ltc_ctc.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/lib/star.ma".
  16 include "ground/lib/ltc.ma".
  17
  18 (* LABELLED TRANSITIVE CLOSURE **********************************************)
  19
  20 alias symbol "subseteq" = "relation inclusion".
  21
  22 (* Properties with contextual transitive closure ****************************)
  23
  24 lemma ltc_CTC (C) (A) (i) (f) (B) (R:relation4 C A B B):
  25               left_identity … f i →
  26               ∀c. CTC … (λc. R c i) c ⊆ ltc … f … (R c) i.
  27 #C #A #i #f #B #R #Hf #c #b1 #b2 #H elim H -b2 /2 width=1 by ltc_rc/
  28 #b #b2 #_ #Hb2 #IH >(Hf i) -Hf /2 width=3 by ltc_dx/
  29 qed.
  30
  31 (* Inversion lemmas with contextual transitive closure **********************)
  32
  33 lemma ltc_inv_CTC (C) (A) (i) (f) (B) (R:relation4 C A B B):
  34                   associative … f → annulment_2 … f i →
  35                   ∀c. ltc … f … (R c) i ⊆ CTC … (λc. R c i) c.
  36 #C #A #i #f #B #R #H1f #H2f #c #b1 #b2
  37 @(insert_eq_0 … i) #a #H
  38 @(ltc_ind_dx A f B … H) -a -b2 /2 width=1 by inj/ -H1f
  39 #a1 #a2 #b #b2 #_ #IH #Hb2 #H <H
  40 elim (H2f … H) -H2f -H #H1 #H2 destruct
  41 /3 width=3 by step/
  42 qed-.