matita/matita/contribs/lambdadelta/apps_2/models/li.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 "static_2/syntax/lenv.ma".
  16 include "apps_2/models/veq.ma".
  17 include "apps_2/notation/models/inwbrackets_4.ma".
  18
  19 (* LOCAL ENVIRONMENT INTERPRETATION  ****************************************)
  20
  21 inductive li (M) (gv): relation2 lenv (evaluation M) ≝
  22 | li_atom: ∀lv. li M gv (⋆) lv
  23 | li_abbr: ∀lv,d,L,V. li M gv L lv → ⟦V⟧[gv,lv] = d → li M gv (L.ⓓV) (⫯[0←d]lv)
  24 | li_abst: ∀lv,d,L,W. li M gv L lv → li M gv (L.ⓛW) (⫯[0←d]lv)
  25 | li_unit: ∀lv,d,I,L. li M gv L lv → li M gv (L.ⓤ[I]) (⫯[0←d]lv)
  26 | li_veq : ∀lv1,lv2,L. li M gv L lv1 → lv1 ≗ lv2 → li M gv L lv2
  27 .
  28
  29 interpretation "local environment interpretation (model)"
  30    'InWBrackets M gv L lv  = (li M gv L lv).
  31
  32 (* Basic inversion lemmas ***************************************************)
  33
  34 fact li_inv_abbr_aux (M) (gv): is_model M →
  35                                ∀v,Y. v ϵ ⟦Y⟧{M}[gv] → ∀L,V. Y = L.ⓓV →
  36                                ∃∃lv. lv ϵ ⟦L⟧[gv] & ⫯[0←⟦V⟧[gv,lv]]lv ≗ v.
  37 #M #gv #HM #v #Y #H elim H -v -Y
  38 [ #lv #K #W #H destruct
  39 | #lv #d #L #V #HL #HV #_ #K #W #H destruct
  40   /3 width=3 by veq_refl, ex2_intro/
  41 | #lv #d #L #V #_ #_ #K #W #H destruct
  42 | #lv #d #I #L #_ #_ #K #W #H destruct
  43 | #lv1 #lv2 #L #_ #Hlv12 #IH #K #W #H destruct
  44   elim IH -IH [|*: // ] #lv #HK #HW
  45   /3 width=5 by veq_trans, ex2_intro/
  46 ]
  47 qed-.
  48
  49 lemma li_inv_abbr (M) (gv): is_model M →
  50                             ∀v,L,V. v ϵ ⟦L.ⓓV⟧{M}[gv] →
  51                             ∃∃lv. lv ϵ ⟦L⟧[gv] & ⫯[0←⟦V⟧[gv,lv]]lv ≗ v.
  52 /2 width=3 by li_inv_abbr_aux/ qed-.
  53
  54 fact li_inv_abst_aux (M) (gv): is_model M →
  55                                ∀v,Y. v ϵ ⟦Y⟧{M}[gv] → ∀L,W. Y = L.ⓛW →
  56                                ∃∃lv,d. lv ϵ ⟦L⟧[gv] & ⫯[0←d]lv ≗ v.
  57 #M #gv #HM #v #Y #H elim H -v -Y
  58 [ #lv #K #U #H destruct
  59 | #lv #d #L #V #_ #_ #_ #K #U #H destruct
  60 | #lv #d #L #V #HL #_ #K #U #H destruct
  61   /3 width=4 by veq_refl, ex2_2_intro/
  62 | #lv #d #I #L #_ #_ #K #U #H destruct
  63 | #lv1 #lv2 #L #_ #Hlv12 #IH #K #U #H destruct
  64   elim IH -IH [|*: // ] #lv #d #HK #Hlv
  65   /3 width=6 by veq_trans, ex2_2_intro/
  66 ]
  67 qed-.
  68
  69 lemma li_inv_abst (M) (gv): is_model M →
  70                             ∀v,L,W. v ϵ ⟦L.ⓛW⟧{M}[gv] →
  71                             ∃∃lv,d. lv ϵ ⟦L⟧[gv] & ⫯[0←d]lv ≗ v.
  72 /2 width=4 by li_inv_abst_aux/ qed-.
  73
  74 fact li_inv_unit_aux (M) (gv): is_model M →
  75                                ∀v,Y. v ϵ ⟦Y⟧{M}[gv] → ∀I,L. Y = L.ⓤ[I] →
  76                                ∃∃lv,d. lv ϵ ⟦L⟧[gv] & ⫯[0←d]lv ≗ v.
  77 #M #gv #HM #v #Y #H elim H -v -Y
  78 [ #lv #J #K #H destruct
  79 | #lv #d #L #V #_ #_ #_ #J #K #H destruct
  80 | #lv #d #L #V #_ #_ #J #K #H destruct
  81 | #lv #d #I #L #HL #_ #J #K #H destruct
  82   /3 width=4 by veq_refl, ex2_2_intro/
  83 | #lv1 #lv2 #L #_ #Hlv12 #IH #J #K #H destruct
  84   elim IH -IH [|*: // ] #lv #d #HK #Hlv
  85   /3 width=6 by veq_trans, ex2_2_intro/
  86 ]
  87 qed-.
  88
  89 lemma li_inv_unit (M) (gv): is_model M →
  90                             ∀v,I,L. v ϵ ⟦L.ⓤ[I]⟧{M}[gv] →
  91                             ∃∃lv,d. lv ϵ ⟦L⟧[gv] & ⫯[0←d]lv ≗ v.
  92 /2 width=4 by li_inv_unit_aux/ qed-.
  93
  94 (* Advanced forward lemmas **************************************************)
  95
  96 lemma li_fwd_bind (M) (gv): is_model M →
  97                             ∀v,I,L. v ϵ ⟦L.ⓘ[I]⟧{M}[gv] →
  98                             ∃∃lv,d. lv ϵ ⟦L⟧[gv] & ⫯[0←d]lv ≗ v.
  99 #M #gv #HM #v * [ #I | * #V ] #L #H
 100 [ /2 width=2 by li_inv_unit/
 101 | elim (li_inv_abbr … H) // -H #lv #HL #Hv
 102   /2 width=4 by ex2_2_intro/
 103 | /2 width=2 by li_inv_abst/
 104 ]
 105 qed-.
 106
 107 (* Basic_properties *********************************************************)
 108
 109 lemma li_repl (M) (L): is_model M ->
 110                        replace_2 … (λgv.li M gv L) (veq …) (veq …).
 111 #M #L #HM #gv1 #lv1 #H elim H -L -lv1
 112 [ #lv1 #gv2 #Hgv #lv2 #Hlv /2 width=1 by li_atom/
 113 | #lv1 #d #K #V #_ #Hd #IH #gv2 #Hgv #lv2 #Hlv destruct
 114   @li_veq [2: /4 width=4 by li_abbr, veq_refl/ | skip ] -IH
 115   @(veq_canc_sn … Hlv) -Hlv //
 116   /4 width=1 by ti_comp, vpush_comp, (* 2x *) veq_refl/
 117 | #lv1 #d #K #W #_ #IH #gv2 #Hgv #lv2 #Hlv
 118   @li_veq /4 width=3 by li_abst, veq_refl/
 119 | #lv1 #d #I #K #_ #IH #gv2 #Hgv #lv2 #Hlv
 120   @li_veq /4 width=3 by li_unit, veq_refl/
 121 | #lv1 #lv #L #_ #Hlv1 #IH #gv2 #Hgv #lv2 #Hlv
 122   /3 width=3 by veq_trans/
 123 ]
 124 qed.