matita/matita/contribs/lambdadelta/static_2/static/frees.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/relocation/rtmap_sor.ma".
  16 include "static_2/notation/relations/freeplus_3.ma".
  17 include "static_2/syntax/lenv.ma".
  18
  19 (* CONTEXT-SENSITIVE FREE VARIABLES *****************************************)
  20
  21 inductive frees: relation3 lenv term rtmap ≝
  22 | frees_sort: ∀f,L,s. 𝐈❪f❫ → frees L (⋆s) f
  23 | frees_atom: ∀f,i. 𝐈❪f❫ → frees (⋆) (#i) (⫯*[i]↑f)
  24 | frees_pair: ∀f,I,L,V. frees L V f →
  25               frees (L.ⓑ[I]V) (#0) (↑f)
  26 | frees_unit: ∀f,I,L. 𝐈❪f❫ → frees (L.ⓤ[I]) (#0) (↑f)
  27 | frees_lref: ∀f,I,L,i. frees L (#i) f →
  28               frees (L.ⓘ[I]) (#↑i) (⫯f)
  29 | frees_gref: ∀f,L,l. 𝐈❪f❫ → frees L (§l) f
  30 | frees_bind: ∀f1,f2,f,p,I,L,V,T. frees L V f1 → frees (L.ⓑ[I]V) T f2 →
  31               f1 ⋓ ⫰f2 ≘ f → frees L (ⓑ[p,I]V.T) f
  32 | frees_flat: ∀f1,f2,f,I,L,V,T. frees L V f1 → frees L T f2 →
  33               f1 ⋓ f2 ≘ f → frees L (ⓕ[I]V.T) f
  34 .
  35
  36 interpretation
  37    "context-sensitive free variables (term)"
  38    'FreePlus L T f = (frees L T f).
  39
  40 (* Basic inversion lemmas ***************************************************)
  41
  42 fact frees_inv_sort_aux: ∀f,L,X. L ⊢ 𝐅+❪X❫ ≘ f → ∀x. X = ⋆x → 𝐈❪f❫.
  43 #L #X #f #H elim H -f -L -X //
  44 [ #f #i #_ #x #H destruct
  45 | #f #_ #L #V #_ #_ #x #H destruct
  46 | #f #_ #L #_ #x #H destruct
  47 | #f #_ #L #i #_ #_ #x #H destruct
  48 | #f1 #f2 #f #p #I #L #V #T #_ #_ #_ #_ #_ #x #H destruct
  49 | #f1 #f2 #f #I #L #V #T #_ #_ #_ #_ #_ #x #H destruct
  50 ]
  51 qed-.
  52
  53 lemma frees_inv_sort: ∀f,L,s. L ⊢ 𝐅+❪⋆s❫ ≘ f → 𝐈❪f❫.
  54 /2 width=5 by frees_inv_sort_aux/ qed-.
  55
  56 fact frees_inv_atom_aux:
  57      ∀f,L,X. L ⊢ 𝐅+❪X❫ ≘ f → ∀i. L = ⋆ → X = #i →
  58      ∃∃g. 𝐈❪g❫ & f = ⫯*[i]↑g.
  59 #f #L #X #H elim H -f -L -X
  60 [ #f #L #s #_ #j #_ #H destruct
  61 | #f #i #Hf #j #_ #H destruct /2 width=3 by ex2_intro/
  62 | #f #I #L #V #_ #_ #j #H destruct
  63 | #f #I #L #_ #j #H destruct
  64 | #f #I #L #i #_ #_ #j #H destruct
  65 | #f #L #l #_ #j #_ #H destruct
  66 | #f1 #f2 #f #p #I #L #V #T #_ #_ #_ #_ #_ #j #_ #H destruct
  67 | #f1 #f2 #f #I #L #V #T #_ #_ #_ #_ #_ #j #_ #H destruct
  68 ]
  69 qed-.
  70
  71 lemma frees_inv_atom: ∀f,i. ⋆ ⊢ 𝐅+❪#i❫ ≘ f → ∃∃g. 𝐈❪g❫ & f = ⫯*[i]↑g.
  72 /2 width=5 by frees_inv_atom_aux/ qed-.
  73
  74 fact frees_inv_pair_aux:
  75      ∀f,L,X. L ⊢ 𝐅+❪X❫ ≘ f → ∀I,K,V. L = K.ⓑ[I]V → X = #0 →
  76      ∃∃g. K ⊢ 𝐅+❪V❫ ≘ g & f = ↑g.
  77 #f #L #X * -f -L -X
  78 [ #f #L #s #_ #Z #Y #X #_ #H destruct
  79 | #f #i #_ #Z #Y #X #H destruct
  80 | #f #I #L #V #Hf #Z #Y #X #H #_ destruct /2 width=3 by ex2_intro/
  81 | #f #I #L #_ #Z #Y #X #H destruct
  82 | #f #I #L #i #_ #Z #Y #X #_ #H destruct
  83 | #f #L #l #_ #Z #Y #X #_ #H destruct
  84 | #f1 #f2 #f #p #I #L #V #T #_ #_ #_ #Z #Y #X #_ #H destruct
  85 | #f1 #f2 #f #I #L #V #T #_ #_ #_ #Z #Y #X #_ #H destruct
  86 ]
  87 qed-.
  88
  89 lemma frees_inv_pair: ∀f,I,K,V. K.ⓑ[I]V ⊢ 𝐅+❪#0❫ ≘ f → ∃∃g. K ⊢ 𝐅+❪V❫ ≘ g & f = ↑g.
  90 /2 width=6 by frees_inv_pair_aux/ qed-.
  91
  92 fact frees_inv_unit_aux:
  93      ∀f,L,X. L ⊢ 𝐅+❪X❫ ≘ f → ∀I,K. L = K.ⓤ[I] → X = #0 →
  94      ∃∃g. 𝐈❪g❫ & f = ↑g.
  95 #f #L #X * -f -L -X
  96 [ #f #L #s #_ #Z #Y #_ #H destruct
  97 | #f #i #_ #Z #Y #H destruct
  98 | #f #I #L #V #_ #Z #Y #H destruct
  99 | #f #I #L #Hf #Z #Y #H destruct /2 width=3 by ex2_intro/
 100 | #f #I #L #i #_ #Z #Y #_ #H destruct
 101 | #f #L #l #_ #Z #Y #_ #H destruct
 102 | #f1 #f2 #f #p #I #L #V #T #_ #_ #_ #Z #Y #_ #H destruct
 103 | #f1 #f2 #f #I #L #V #T #_ #_ #_ #Z #Y #_ #H destruct
 104 ]
 105 qed-.
 106
 107 lemma frees_inv_unit: ∀f,I,K. K.ⓤ[I] ⊢ 𝐅+❪#0❫ ≘ f → ∃∃g. 𝐈❪g❫ & f = ↑g.
 108 /2 width=7 by frees_inv_unit_aux/ qed-.
 109
 110 fact frees_inv_lref_aux:
 111      ∀f,L,X. L ⊢ 𝐅+❪X❫ ≘ f → ∀I,K,j. L = K.ⓘ[I] → X = #(↑j) →
 112      ∃∃g. K ⊢ 𝐅+❪#j❫ ≘ g & f = ⫯g.
 113 #f #L #X * -f -L -X
 114 [ #f #L #s #_ #Z #Y #j #_ #H destruct
 115 | #f #i #_ #Z #Y #j #H destruct
 116 | #f #I #L #V #_ #Z #Y #j #_ #H destruct
 117 | #f #I #L #_ #Z #Y #j #_ #H destruct
 118 | #f #I #L #i #Hf #Z #Y #j #H1 #H2 destruct /2 width=3 by ex2_intro/
 119 | #f #L #l #_ #Z #Y #j #_ #H destruct
 120 | #f1 #f2 #f #p #I #L #V #T #_ #_ #_ #Z #Y #j #_ #H destruct
 121 | #f1 #f2 #f #I #L #V #T #_ #_ #_ #Z #Y #j #_ #H destruct
 122 ]
 123 qed-.
 124
 125 lemma frees_inv_lref:
 126       ∀f,I,K,i. K.ⓘ[I] ⊢ 𝐅+❪#(↑i)❫ ≘ f →
 127       ∃∃g. K ⊢ 𝐅+❪#i❫ ≘ g & f = ⫯g.
 128 /2 width=6 by frees_inv_lref_aux/ qed-.
 129
 130 fact frees_inv_gref_aux: ∀f,L,X. L ⊢ 𝐅+❪X❫ ≘ f → ∀x. X = §x → 𝐈❪f❫.
 131 #f #L #X #H elim H -f -L -X //
 132 [ #f #i #_ #x #H destruct
 133 | #f #_ #L #V #_ #_ #x #H destruct
 134 | #f #_ #L #_ #x #H destruct
 135 | #f #_ #L #i #_ #_ #x #H destruct
 136 | #f1 #f2 #f #p #I #L #V #T #_ #_ #_ #_ #_ #x #H destruct
 137 | #f1 #f2 #f #I #L #V #T #_ #_ #_ #_ #_ #x #H destruct
 138 ]
 139 qed-.
 140
 141 lemma frees_inv_gref: ∀f,L,l. L ⊢ 𝐅+❪§l❫ ≘ f → 𝐈❪f❫.
 142 /2 width=5 by frees_inv_gref_aux/ qed-.
 143
 144 fact frees_inv_bind_aux:
 145      ∀f,L,X. L ⊢ 𝐅+❪X❫ ≘ f → ∀p,I,V,T. X = ⓑ[p,I]V.T →
 146      ∃∃f1,f2. L ⊢ 𝐅+❪V❫ ≘ f1 & L.ⓑ[I]V ⊢ 𝐅+❪T❫ ≘ f2 & f1 ⋓ ⫰f2 ≘ f.
 147 #f #L #X * -f -L -X
 148 [ #f #L #s #_ #q #J #W #U #H destruct
 149 | #f #i #_ #q #J #W #U #H destruct
 150 | #f #I #L #V #_ #q #J #W #U #H destruct
 151 | #f #I #L #_ #q #J #W #U #H destruct
 152 | #f #I #L #i #_ #q #J #W #U #H destruct
 153 | #f #L #l #_ #q #J #W #U #H destruct
 154 | #f1 #f2 #f #p #I #L #V #T #HV #HT #Hf #q #J #W #U #H destruct /2 width=5 by ex3_2_intro/
 155 | #f1 #f2 #f #I #L #V #T #_ #_ #_ #q #J #W #U #H destruct
 156 ]
 157 qed-.
 158
 159 lemma frees_inv_bind:
 160       ∀f,p,I,L,V,T. L ⊢ 𝐅+❪ⓑ[p,I]V.T❫ ≘ f →
 161       ∃∃f1,f2. L ⊢ 𝐅+❪V❫ ≘ f1 & L.ⓑ[I]V ⊢ 𝐅+❪T❫ ≘ f2 & f1 ⋓ ⫰f2 ≘ f.
 162 /2 width=4 by frees_inv_bind_aux/ qed-.
 163
 164 fact frees_inv_flat_aux: ∀f,L,X. L ⊢ 𝐅+❪X❫ ≘ f → ∀I,V,T. X = ⓕ[I]V.T →
 165                          ∃∃f1,f2. L ⊢ 𝐅+❪V❫ ≘ f1 & L ⊢ 𝐅+❪T❫ ≘ f2 & f1 ⋓ f2 ≘ f.
 166 #f #L #X * -f -L -X
 167 [ #f #L #s #_ #J #W #U #H destruct
 168 | #f #i #_ #J #W #U #H destruct
 169 | #f #I #L #V #_ #J #W #U #H destruct
 170 | #f #I #L #_ #J #W #U #H destruct
 171 | #f #I #L #i #_ #J #W #U #H destruct
 172 | #f #L #l #_ #J #W #U #H destruct
 173 | #f1 #f2 #f #p #I #L #V #T #_ #_ #_ #J #W #U #H destruct
 174 | #f1 #f2 #f #I #L #V #T #HV #HT #Hf #J #W #U #H destruct /2 width=5 by ex3_2_intro/
 175 ]
 176 qed-.
 177
 178 lemma frees_inv_flat:
 179       ∀f,I,L,V,T. L ⊢ 𝐅+❪ⓕ[I]V.T❫ ≘ f →
 180       ∃∃f1,f2. L ⊢ 𝐅+❪V❫ ≘ f1 & L ⊢ 𝐅+❪T❫ ≘ f2 & f1 ⋓ f2 ≘ f.
 181 /2 width=4 by frees_inv_flat_aux/ qed-.
 182
 183 (* Basic properties ********************************************************)
 184
 185 lemma frees_eq_repl_back: ∀L,T. eq_repl_back … (λf. L ⊢ 𝐅+❪T❫ ≘ f).
 186 #L #T #f1 #H elim H -f1 -L -T
 187 [ /3 width=3 by frees_sort, isid_eq_repl_back/
 188 | #f1 #i #Hf1 #g2 #H
 189   elim (eq_inv_pushs_sn … H) -H #g #Hg #H destruct
 190   elim (eq_inv_nx … Hg) -Hg
 191   /3 width=3 by frees_atom, isid_eq_repl_back/
 192 | #f1 #I #L #V #_ #IH #g2 #H
 193   elim (eq_inv_nx … H) -H
 194   /3 width=3 by frees_pair/
 195 | #f1 #I #L #Hf1 #g2 #H
 196   elim (eq_inv_nx … H) -H
 197   /3 width=3 by frees_unit, isid_eq_repl_back/
 198 | #f1 #I #L #i #_ #IH #g2 #H
 199   elim (eq_inv_px … H) -H /3 width=3 by frees_lref/
 200 | /3 width=3 by frees_gref, isid_eq_repl_back/
 201 | /3 width=7 by frees_bind, sor_eq_repl_back3/
 202 | /3 width=7 by frees_flat, sor_eq_repl_back3/
 203 ]
 204 qed-.
 205
 206 lemma frees_eq_repl_fwd: ∀L,T. eq_repl_fwd … (λf. L ⊢ 𝐅+❪T❫ ≘ f).
 207 #L #T @eq_repl_sym /2 width=3 by frees_eq_repl_back/
 208 qed-.
 209
 210 lemma frees_lref_push: ∀f,i. ⋆ ⊢ 𝐅+❪#i❫ ≘ f → ⋆ ⊢ 𝐅+❪#↑i❫ ≘ ⫯f.
 211 #f #i #H
 212 elim (frees_inv_atom … H) -H #g #Hg #H destruct
 213 /2 width=1 by frees_atom/
 214 qed.
 215
 216 (* Forward lemmas with test for finite colength *****************************)
 217
 218 lemma frees_fwd_isfin: ∀f,L,T. L ⊢ 𝐅+❪T❫ ≘ f → 𝐅❪f❫.
 219 #f #L #T #H elim H -f -L -T
 220 /4 width=5 by sor_isfin, isfin_isid, isfin_tl, isfin_pushs, isfin_push, isfin_next/
 221 qed-.
 222
 223 (* Basic_2A1: removed theorems 30:
 224               frees_eq frees_be frees_inv
 225               frees_inv_sort frees_inv_gref frees_inv_lref frees_inv_lref_free
 226               frees_inv_lref_skip frees_inv_lref_ge frees_inv_lref_lt
 227               frees_inv_bind frees_inv_flat frees_inv_bind_O
 228               frees_lref_eq frees_lref_be frees_weak
 229               frees_bind_sn frees_bind_dx frees_flat_sn frees_flat_dx
 230               frees_lift_ge frees_inv_lift_be frees_inv_lift_ge
 231               lreq_frees_trans frees_lreq_conf
 232               llor_atom llor_skip llor_total
 233               llor_tail_frees llor_tail_cofrees
 234 *)