matita/matita/contribs/lambdadelta/static_2/static/lsubf.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/notation/relations/lrsubeqf_4.ma".
  16 include "ground_2/relocation/nstream_sor.ma".
  17 include "static_2/static/frees.ma".
  18
  19 (* RESTRICTED REFINEMENT FOR CONTEXT-SENSITIVE FREE VARIABLES ***************)
  20
  21 inductive lsubf: relation4 lenv rtmap lenv rtmap ≝
  22 | lsubf_atom: ∀f1,f2. f1 ≡ f2 → lsubf (⋆) f1 (⋆) f2
  23 | lsubf_push: ∀f1,f2,I1,I2,L1,L2. lsubf L1 (f1) L2 (f2) →
  24               lsubf (L1.ⓘ{I1}) (⫯f1) (L2.ⓘ{I2}) (⫯f2)
  25 | lsubf_bind: ∀f1,f2,I,L1,L2. lsubf L1 f1 L2 f2 →
  26               lsubf (L1.ⓘ{I}) (↑f1) (L2.ⓘ{I}) (↑f2)
  27 | lsubf_beta: ∀f,f0,f1,f2,L1,L2,W,V. L1 ⊢ 𝐅+⦃V⦄ ≘ f → f0 ⋓ f ≘ f1 →
  28               lsubf L1 f0 L2 f2 → lsubf (L1.ⓓⓝW.V) (↑f1) (L2.ⓛW) (↑f2)
  29 | lsubf_unit: ∀f,f0,f1,f2,I1,I2,L1,L2,V. L1 ⊢ 𝐅+⦃V⦄ ≘ f → f0 ⋓ f ≘ f1 →
  30               lsubf L1 f0 L2 f2 → lsubf (L1.ⓑ{I1}V) (↑f1) (L2.ⓤ{I2}) (↑f2)
  31 .
  32
  33 interpretation
  34   "local environment refinement (context-sensitive free variables)"
  35   'LRSubEqF L1 f1 L2 f2 = (lsubf L1 f1 L2 f2).
  36
  37 (* Basic inversion lemmas ***************************************************)
  38
  39 fact lsubf_inv_atom1_aux:
  40      ∀f1,f2,L1,L2. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄ → L1 = ⋆ →
  41      ∧∧ f1 ≡ f2 & L2 = ⋆.
  42 #f1 #f2 #L1 #L2 * -f1 -f2 -L1 -L2
  43 [ /2 width=1 by conj/
  44 | #f1 #f2 #I1 #I2 #L1 #L2 #_ #H destruct
  45 | #f1 #f2 #I #L1 #L2 #_ #H destruct
  46 | #f #f0 #f1 #f2 #L1 #L2 #W #V #_ #_ #_ #H destruct
  47 | #f #f0 #f1 #f2 #I1 #I2 #L1 #L2 #V #_ #_ #_ #H destruct
  48 ]
  49 qed-.
  50
  51 lemma lsubf_inv_atom1: ∀f1,f2,L2. ⦃⋆,f1⦄ ⫃𝐅+ ⦃L2,f2⦄ → ∧∧ f1 ≡ f2 & L2 = ⋆.
  52 /2 width=3 by lsubf_inv_atom1_aux/ qed-.
  53
  54 fact lsubf_inv_push1_aux:
  55      ∀f1,f2,L1,L2. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄ →
  56      ∀g1,I1,K1. f1 = ⫯g1 → L1 = K1.ⓘ{I1} →
  57      ∃∃g2,I2,K2. ⦃K1,g1⦄ ⫃𝐅+ ⦃K2,g2⦄ & f2 = ⫯g2 & L2 = K2.ⓘ{I2}.
  58 #f1 #f2 #L1 #L2 * -f1 -f2 -L1 -L2
  59 [ #f1 #f2 #_ #g1 #J1 #K1 #_ #H destruct
  60 | #f1 #f2 #I1 #I2 #L1 #L2 #H12 #g1 #J1 #K1 #H1 #H2 destruct
  61   <(injective_push … H1) -g1 /2 width=6 by ex3_3_intro/
  62 | #f1 #f2 #I #L1 #L2 #_ #g1 #J1 #K1 #H elim (discr_next_push … H)
  63 | #f #f0 #f1 #f2 #L1 #L2 #W #V #_ #_ #_ #g1 #J1 #K1 #H elim (discr_next_push … H)
  64 | #f #f0 #f1 #f2 #I1 #I2 #L1 #L2 #V #_ #_ #_ #g1 #J1 #K1 #H elim (discr_next_push … H)
  65 ]
  66 qed-.
  67
  68 lemma lsubf_inv_push1:
  69       ∀g1,f2,I1,K1,L2. ⦃K1.ⓘ{I1},⫯g1⦄ ⫃𝐅+ ⦃L2,f2⦄ →
  70       ∃∃g2,I2,K2. ⦃K1,g1⦄ ⫃𝐅+ ⦃K2,g2⦄ & f2 = ⫯g2 & L2 = K2.ⓘ{I2}.
  71 /2 width=6 by lsubf_inv_push1_aux/ qed-.
  72
  73 fact lsubf_inv_pair1_aux:
  74      ∀f1,f2,L1,L2. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄ →
  75      ∀g1,I,K1,X. f1 = ↑g1 → L1 = K1.ⓑ{I}X →
  76      ∨∨ ∃∃g2,K2. ⦃K1,g1⦄ ⫃𝐅+ ⦃K2,g2⦄ & f2 = ↑g2 & L2 = K2.ⓑ{I}X
  77       | ∃∃g,g0,g2,K2,W,V. ⦃K1,g0⦄ ⫃𝐅+ ⦃K2,g2⦄ &
  78           K1 ⊢ 𝐅+⦃V⦄ ≘ g & g0 ⋓ g ≘ g1 & f2 = ↑g2 &
  79           I = Abbr & X = ⓝW.V & L2 = K2.ⓛW
  80       | ∃∃g,g0,g2,J,K2. ⦃K1,g0⦄ ⫃𝐅+ ⦃K2,g2⦄ &
  81           K1 ⊢ 𝐅+⦃X⦄ ≘ g & g0 ⋓ g ≘ g1 & f2 = ↑g2 & L2 = K2.ⓤ{J}.
  82 #f1 #f2 #L1 #L2 * -f1 -f2 -L1 -L2
  83 [ #f1 #f2 #_ #g1 #J #K1 #X #_ #H destruct
  84 | #f1 #f2 #I1 #I2 #L1 #L2 #H12 #g1 #J #K1 #X #H elim (discr_push_next … H)
  85 | #f1 #f2 #I #L1 #L2 #H12 #g1 #J #K1 #X #H1 #H2 destruct
  86   <(injective_next … H1) -g1 /3 width=5 by or3_intro0, ex3_2_intro/
  87 | #f #f0 #f1 #f2 #L1 #L2 #W #V #Hf #Hf1 #H12 #g1 #J #K1 #X #H1 #H2 destruct
  88   <(injective_next … H1) -g1 /3 width=12 by or3_intro1, ex7_6_intro/
  89 | #f #f0 #f1 #f2 #I1 #I2 #L1 #L2 #V #Hf #Hf1 #H12 #g1 #J #K1 #X #H1 #H2 destruct
  90   <(injective_next … H1) -g1 /3 width=10 by or3_intro2, ex5_5_intro/
  91 ]
  92 qed-.
  93
  94 lemma lsubf_inv_pair1:
  95       ∀g1,f2,I,K1,L2,X. ⦃K1.ⓑ{I}X,↑g1⦄ ⫃𝐅+ ⦃L2,f2⦄ →
  96       ∨∨ ∃∃g2,K2. ⦃K1,g1⦄ ⫃𝐅+ ⦃K2,g2⦄ & f2 = ↑g2 & L2 = K2.ⓑ{I}X
  97        | ∃∃g,g0,g2,K2,W,V. ⦃K1,g0⦄ ⫃𝐅+ ⦃K2,g2⦄ &
  98            K1 ⊢ 𝐅+⦃V⦄ ≘ g & g0 ⋓ g ≘ g1 & f2 = ↑g2 &
  99            I = Abbr & X = ⓝW.V & L2 = K2.ⓛW
 100        | ∃∃g,g0,g2,J,K2. ⦃K1,g0⦄ ⫃𝐅+ ⦃K2,g2⦄ &
 101            K1 ⊢ 𝐅+⦃X⦄ ≘ g & g0 ⋓ g ≘ g1 & f2 = ↑g2 & L2 = K2.ⓤ{J}.
 102 /2 width=5 by lsubf_inv_pair1_aux/ qed-.
 103
 104 fact lsubf_inv_unit1_aux:
 105      ∀f1,f2,L1,L2. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄ →
 106      ∀g1,I,K1. f1 = ↑g1 → L1 = K1.ⓤ{I} →
 107      ∃∃g2,K2. ⦃K1,g1⦄ ⫃𝐅+ ⦃K2,g2⦄ & f2 = ↑g2 & L2 = K2.ⓤ{I}.
 108 #f1 #f2 #L1 #L2 * -f1 -f2 -L1 -L2
 109 [ #f1 #f2 #_ #g1 #J #K1 #_ #H destruct
 110 | #f1 #f2 #I1 #I2 #L1 #L2 #H12 #g1 #J #K1 #H elim (discr_push_next … H)
 111 | #f1 #f2 #I #L1 #L2 #H12 #g1 #J #K1 #H1 #H2 destruct
 112   <(injective_next … H1) -g1 /2 width=5 by ex3_2_intro/
 113 | #f #f0 #f1 #f2 #L1 #L2 #W #V #_ #_ #_ #g1 #J #K1 #_ #H destruct
 114 | #f #f0 #f1 #f2 #I1 #I2 #L1 #L2 #V #_ #_ #_ #g1 #J #K1 #_ #H destruct
 115 ]
 116 qed-.
 117
 118 lemma lsubf_inv_unit1:
 119       ∀g1,f2,I,K1,L2. ⦃K1.ⓤ{I},↑g1⦄ ⫃𝐅+ ⦃L2,f2⦄ →
 120       ∃∃g2,K2. ⦃K1,g1⦄ ⫃𝐅+ ⦃K2,g2⦄ & f2 = ↑g2 & L2 = K2.ⓤ{I}.
 121 /2 width=5 by lsubf_inv_unit1_aux/ qed-.
 122
 123 fact lsubf_inv_atom2_aux:
 124      ∀f1,f2,L1,L2. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄ → L2 = ⋆ →
 125      ∧∧ f1 ≡ f2 & L1 = ⋆.
 126 #f1 #f2 #L1 #L2 * -f1 -f2 -L1 -L2
 127 [ /2 width=1 by conj/
 128 | #f1 #f2 #I1 #I2 #L1 #L2 #_ #H destruct
 129 | #f1 #f2 #I #L1 #L2 #_ #H destruct
 130 | #f #f0 #f1 #f2 #L1 #L2 #W #V #_ #_ #_ #H destruct
 131 | #f #f0 #f1 #f2 #I1 #I2 #L1 #L2 #V #_ #_ #_ #H destruct
 132 ]
 133 qed-.
 134
 135 lemma lsubf_inv_atom2: ∀f1,f2,L1. ⦃L1,f1⦄ ⫃𝐅+ ⦃⋆,f2⦄ → ∧∧f1 ≡ f2 & L1 = ⋆.
 136 /2 width=3 by lsubf_inv_atom2_aux/ qed-.
 137
 138 fact lsubf_inv_push2_aux:
 139      ∀f1,f2,L1,L2. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄ →
 140      ∀g2,I2,K2. f2 = ⫯g2 → L2 = K2.ⓘ{I2} →
 141      ∃∃g1,I1,K1. ⦃K1,g1⦄ ⫃𝐅+ ⦃K2,g2⦄ & f1 = ⫯g1 & L1 = K1.ⓘ{I1}.
 142 #f1 #f2 #L1 #L2 * -f1 -f2 -L1 -L2
 143 [ #f1 #f2 #_ #g2 #J2 #K2 #_ #H destruct
 144 | #f1 #f2 #I1 #I2 #L1 #L2 #H12 #g2 #J2 #K2 #H1 #H2 destruct
 145   <(injective_push … H1) -g2 /2 width=6 by ex3_3_intro/
 146 | #f1 #f2 #I #L1 #L2 #_ #g2 #J2 #K2 #H elim (discr_next_push … H)
 147 | #f #f0 #f1 #f2 #L1 #L2 #W #V #_ #_ #_ #g2 #J2 #K2 #H elim (discr_next_push … H)
 148 | #f #f0 #f1 #f2 #I1 #I2 #L1 #L2 #V #_ #_ #_ #g2 #J2 #K2 #H elim (discr_next_push … H)
 149 ]
 150 qed-.
 151
 152 lemma lsubf_inv_push2:
 153       ∀f1,g2,I2,L1,K2. ⦃L1,f1⦄ ⫃𝐅+ ⦃K2.ⓘ{I2},⫯g2⦄ →
 154       ∃∃g1,I1,K1. ⦃K1,g1⦄ ⫃𝐅+ ⦃K2,g2⦄ & f1 = ⫯g1 & L1 = K1.ⓘ{I1}.
 155 /2 width=6 by lsubf_inv_push2_aux/ qed-.
 156
 157 fact lsubf_inv_pair2_aux:
 158      ∀f1,f2,L1,L2. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄ →
 159      ∀g2,I,K2,W. f2 = ↑g2 → L2 = K2.ⓑ{I}W →
 160      ∨∨ ∃∃g1,K1. ⦃K1,g1⦄ ⫃𝐅+ ⦃K2,g2⦄ & f1 = ↑g1 & L1 = K1.ⓑ{I}W
 161       | ∃∃g,g0,g1,K1,V. ⦃K1,g0⦄ ⫃𝐅+ ⦃K2,g2⦄ &
 162           K1 ⊢ 𝐅+⦃V⦄ ≘ g & g0 ⋓ g ≘ g1 & f1 = ↑g1 &
 163           I = Abst & L1 = K1.ⓓⓝW.V.
 164 #f1 #f2 #L1 #L2 * -f1 -f2 -L1 -L2
 165 [ #f1 #f2 #_ #g2 #J #K2 #X #_ #H destruct
 166 | #f1 #f2 #I1 #I2 #L1 #L2 #H12 #g2 #J #K2 #X #H elim (discr_push_next … H)
 167 | #f1 #f2 #I #L1 #L2 #H12 #g2 #J #K2 #X #H1 #H2 destruct
 168   <(injective_next … H1) -g2 /3 width=5 by ex3_2_intro, or_introl/
 169 | #f #f0 #f1 #f2 #L1 #L2 #W #V #Hf #Hf1 #H12 #g2 #J #K2 #X #H1 #H2 destruct
 170   <(injective_next … H1) -g2 /3 width=10 by ex6_5_intro, or_intror/
 171 | #f #f0 #f1 #f2 #I1 #I2 #L1 #L2 #V #_ #_ #_ #g2 #J #K2 #X #_ #H destruct
 172 ]
 173 qed-.
 174
 175 lemma lsubf_inv_pair2:
 176       ∀f1,g2,I,L1,K2,W. ⦃L1,f1⦄ ⫃𝐅+ ⦃K2.ⓑ{I}W,↑g2⦄ →
 177       ∨∨ ∃∃g1,K1. ⦃K1,g1⦄ ⫃𝐅+ ⦃K2,g2⦄ & f1 = ↑g1 & L1 = K1.ⓑ{I}W
 178        | ∃∃g,g0,g1,K1,V. ⦃K1,g0⦄ ⫃𝐅+ ⦃K2,g2⦄ &
 179            K1 ⊢ 𝐅+⦃V⦄ ≘ g & g0 ⋓ g ≘ g1 & f1 = ↑g1 &
 180            I = Abst & L1 = K1.ⓓⓝW.V.
 181 /2 width=5 by lsubf_inv_pair2_aux/ qed-.
 182
 183 fact lsubf_inv_unit2_aux:
 184      ∀f1,f2,L1,L2. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄ →
 185      ∀g2,I,K2. f2 = ↑g2 → L2 = K2.ⓤ{I} →
 186      ∨∨ ∃∃g1,K1. ⦃K1,g1⦄ ⫃𝐅+ ⦃K2,g2⦄ & f1 = ↑g1 & L1 = K1.ⓤ{I}
 187       | ∃∃g,g0,g1,J,K1,V. ⦃K1,g0⦄ ⫃𝐅+ ⦃K2,g2⦄ &
 188           K1 ⊢ 𝐅+⦃V⦄ ≘ g & g0 ⋓ g ≘ g1 & f1 = ↑g1 & L1 = K1.ⓑ{J}V.
 189 #f1 #f2 #L1 #L2 * -f1 -f2 -L1 -L2
 190 [ #f1 #f2 #_ #g2 #J #K2 #_ #H destruct
 191 | #f1 #f2 #I1 #I2 #L1 #L2 #H12 #g2 #J #K2 #H elim (discr_push_next … H)
 192 | #f1 #f2 #I #L1 #L2 #H12 #g2 #J #K2 #H1 #H2 destruct
 193   <(injective_next … H1) -g2 /3 width=5 by ex3_2_intro, or_introl/
 194 | #f #f0 #f1 #f2 #L1 #L2 #W #V #_ #_ #_ #g2 #J #K2 #_ #H destruct
 195 | #f #f0 #f1 #f2 #I1 #I2 #L1 #L2 #V #Hf #Hf1 #H12 #g2 #J #K2 #H1 #H2 destruct
 196   <(injective_next … H1) -g2 /3 width=11 by ex5_6_intro, or_intror/
 197 ]
 198 qed-.
 199
 200 lemma lsubf_inv_unit2:
 201       ∀f1,g2,I,L1,K2. ⦃L1,f1⦄ ⫃𝐅+ ⦃K2.ⓤ{I},↑g2⦄ →
 202       ∨∨ ∃∃g1,K1. ⦃K1,g1⦄ ⫃𝐅+ ⦃K2,g2⦄ & f1 = ↑g1 & L1 = K1.ⓤ{I}
 203        | ∃∃g,g0,g1,J,K1,V. ⦃K1,g0⦄ ⫃𝐅+ ⦃K2,g2⦄ &
 204            K1 ⊢ 𝐅+⦃V⦄ ≘ g & g0 ⋓ g ≘ g1 & f1 = ↑g1 & L1 = K1.ⓑ{J}V.
 205 /2 width=5 by lsubf_inv_unit2_aux/ qed-.
 206
 207 (* Advanced inversion lemmas ************************************************)
 208
 209 lemma lsubf_inv_atom: ∀f1,f2. ⦃⋆,f1⦄ ⫃𝐅+ ⦃⋆,f2⦄ → f1 ≡ f2.
 210 #f1 #f2 #H elim (lsubf_inv_atom1 … H) -H //
 211 qed-.
 212
 213 lemma lsubf_inv_push_sn:
 214       ∀g1,f2,I1,I2,K1,K2. ⦃K1.ⓘ{I1},⫯g1⦄ ⫃𝐅+ ⦃K2.ⓘ{I2},f2⦄ →
 215       ∃∃g2. ⦃K1,g1⦄ ⫃𝐅+ ⦃K2,g2⦄ & f2 = ⫯g2.
 216 #g1 #f2 #I #K1 #K2 #X #H elim (lsubf_inv_push1 … H) -H
 217 #g2 #I #Y #H0 #H2 #H destruct /2 width=3 by ex2_intro/
 218 qed-.
 219
 220 lemma lsubf_inv_bind_sn:
 221       ∀g1,f2,I,K1,K2. ⦃K1.ⓘ{I},↑g1⦄ ⫃𝐅+ ⦃K2.ⓘ{I},f2⦄ →
 222       ∃∃g2. ⦃K1,g1⦄ ⫃𝐅+ ⦃K2,g2⦄ & f2 = ↑g2.
 223 #g1 #f2 * #I [2: #X ] #K1 #K2 #H
 224 [ elim (lsubf_inv_pair1 … H) -H *
 225   [ #z2 #Y2 #H2 #H #H0 destruct /2 width=3 by ex2_intro/
 226   | #z #z0 #z2 #Y2 #W #V #_ #_ #_ #_ #H0 #_ #H destruct
 227   | #z #z0 #z2 #Z2 #Y2 #_ #_ #_ #_ #H destruct
 228   ]
 229 | elim (lsubf_inv_unit1 … H) -H
 230   #z2 #Y2 #H2 #H #H0 destruct /2 width=3 by ex2_intro/
 231 ]
 232 qed-.
 233
 234 lemma lsubf_inv_beta_sn:
 235       ∀g1,f2,K1,K2,V,W. ⦃K1.ⓓⓝW.V,↑g1⦄ ⫃𝐅+ ⦃K2.ⓛW,f2⦄ →
 236       ∃∃g,g0,g2. ⦃K1,g0⦄ ⫃𝐅+ ⦃K2,g2⦄ & K1 ⊢ 𝐅+⦃V⦄ ≘ g & g0 ⋓ g ≘ g1 & f2 = ↑g2.
 237 #g1 #f2 #K1 #K2 #V #W #H elim (lsubf_inv_pair1 … H) -H *
 238 [ #z2 #Y2 #_ #_ #H destruct
 239 | #z #z0 #z2 #Y2 #X0 #X #H02 #Hz #Hg1 #H #_ #H0 #H1 destruct
 240   /2 width=7 by ex4_3_intro/
 241 | #z #z0 #z2 #Z2 #Y2 #_ #_ #_ #_ #H destruct
 242 ]
 243 qed-.
 244
 245 lemma lsubf_inv_unit_sn:
 246       ∀g1,f2,I,J,K1,K2,V. ⦃K1.ⓑ{I}V,↑g1⦄ ⫃𝐅+ ⦃K2.ⓤ{J},f2⦄ →
 247       ∃∃g,g0,g2. ⦃K1,g0⦄ ⫃𝐅+ ⦃K2,g2⦄ & K1 ⊢ 𝐅+⦃V⦄ ≘ g & g0 ⋓ g ≘ g1 & f2 = ↑g2.
 248 #g1 #f2 #I #J #K1 #K2 #V #H elim (lsubf_inv_pair1 … H) -H *
 249 [ #z2 #Y2 #_ #_ #H destruct
 250 | #z #z0 #z2 #Y2 #X0 #X #_ #_ #_ #_ #_ #_ #H destruct
 251 | #z #z0 #z2 #Z2 #Y2 #H02 #Hz #Hg1 #H0 #H1 destruct
 252   /2 width=7 by ex4_3_intro/
 253 ]
 254 qed-.
 255
 256 lemma lsubf_inv_refl: ∀L,f1,f2. ⦃L,f1⦄ ⫃𝐅+ ⦃L,f2⦄ → f1 ≡ f2.
 257 #L elim L -L /2 width=1 by lsubf_inv_atom/
 258 #L #I #IH #f1 #f2 #H12
 259 elim (pn_split f1) * #g1 #H destruct
 260 [ elim (lsubf_inv_push_sn … H12) | elim (lsubf_inv_bind_sn … H12) ] -H12
 261 #g2 #H12 #H destruct /3 width=5 by eq_next, eq_push/
 262 qed-.
 263
 264 (* Basic forward lemmas *****************************************************)
 265
 266 lemma lsubf_fwd_bind_tl:
 267       ∀f1,f2,I,L1,L2. ⦃L1.ⓘ{I},f1⦄ ⫃𝐅+ ⦃L2.ⓘ{I},f2⦄ → ⦃L1,⫱f1⦄ ⫃𝐅+ ⦃L2,⫱f2⦄.
 268 #f1 #f2 #I #L1 #L2 #H
 269 elim (pn_split f1) * #g1 #H0 destruct
 270 [ elim (lsubf_inv_push_sn … H) | elim (lsubf_inv_bind_sn … H) ] -H
 271 #g2 #H12 #H destruct //
 272 qed-.
 273
 274 lemma lsubf_fwd_isid_dx: ∀f1,f2,L1,L2. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄ → 𝐈⦃f2⦄ → 𝐈⦃f1⦄.
 275 #f1 #f2 #L1 #L2 #H elim H -f1 -f2 -L1 -L2
 276 [ /2 width=3 by isid_eq_repl_fwd/
 277 | /4 width=3 by isid_inv_push, isid_push/
 278 | #f1 #f2 #I #L1 #L2 #_ #_ #H elim (isid_inv_next … H) -H //
 279 | #f #f0 #f1 #f2 #L1 #L2 #W #V #_ #_ #_ #_ #H elim (isid_inv_next … H) -H //
 280 | #f #f0 #f1 #f2 #I1 #I2 #L1 #L2 #V #_ #_ #_ #_ #H elim (isid_inv_next … H) -H //
 281 ]
 282 qed-.
 283
 284 lemma lsubf_fwd_isid_sn: ∀f1,f2,L1,L2. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄ → 𝐈⦃f1⦄ → 𝐈⦃f2⦄.
 285 #f1 #f2 #L1 #L2 #H elim H -f1 -f2 -L1 -L2
 286 [ /2 width=3 by isid_eq_repl_back/
 287 | /4 width=3 by isid_inv_push, isid_push/
 288 | #f1 #f2 #I #L1 #L2 #_ #_ #H elim (isid_inv_next … H) -H //
 289 | #f #f0 #f1 #f2 #L1 #L2 #W #V #_ #_ #_ #_ #H elim (isid_inv_next … H) -H //
 290 | #f #f0 #f1 #f2 #I1 #I2 #L1 #L2 #V #_ #_ #_ #_ #H elim (isid_inv_next … H) -H //
 291 ]
 292 qed-.
 293
 294 lemma lsubf_fwd_sle: ∀f1,f2,L1,L2. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄ → f2 ⊆ f1.
 295 #f1 #f2 #L1 #L2 #H elim H -f1 -f2 -L1 -L2
 296 /3 width=5 by sor_inv_sle_sn_trans, sle_next, sle_push, sle_refl_eq, eq_sym/
 297 qed-.
 298
 299 (* Basic properties *********************************************************)
 300
 301 lemma lsubf_eq_repl_back1: ∀f2,L1,L2. eq_repl_back … (λf1. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄).
 302 #f2 #L1 #L2 #f #H elim H -f -f2 -L1 -L2
 303 [ #f1 #f2 #Hf12 #g1 #Hfg1
 304   /3 width=3 by lsubf_atom, eq_canc_sn/
 305 | #f1 #f2 #I1 #I2 #K1 #K2 #_ #IH #g #H
 306   elim (eq_inv_px … H) -H [|*: // ] #g1 #Hfg1 #H destruct
 307   /3 width=1 by lsubf_push/
 308 | #f1 #f2 #I #K1 #K2 #_ #IH #g #H
 309   elim (eq_inv_nx … H) -H [|*: // ] #g1 #Hfg1 #H destruct
 310   /3 width=1 by lsubf_bind/
 311 | #f #f0 #f1 #f2 #K1 #L2 #W #V #Hf #Hf1 #_ #IH #g #H
 312   elim (eq_inv_nx … H) -H [|*: // ] #g1 #Hfg1 #H destruct
 313   /3 width=5 by lsubf_beta, sor_eq_repl_back3/
 314 | #f #f0 #f1 #f2 #I1 #I2 #K1 #K2 #V #Hf #Hf1 #_ #IH #g #H
 315   elim (eq_inv_nx … H) -H [|*: // ] #g1 #Hfg1 #H destruct
 316   /3 width=5 by lsubf_unit, sor_eq_repl_back3/
 317 ]
 318 qed-.
 319
 320 lemma lsubf_eq_repl_fwd1: ∀f2,L1,L2. eq_repl_fwd … (λf1. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄).
 321 #f2 #L1 #L2 @eq_repl_sym /2 width=3 by lsubf_eq_repl_back1/
 322 qed-.
 323
 324 lemma lsubf_eq_repl_back2: ∀f1,L1,L2. eq_repl_back … (λf2. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄).
 325 #f1 #L1 #L2 #f #H elim H -f1 -f -L1 -L2
 326 [ #f1 #f2 #Hf12 #g2 #Hfg2
 327   /3 width=3 by lsubf_atom, eq_trans/
 328 | #f1 #f2 #I1 #I2 #K1 #K2 #_ #IH #g #H
 329   elim (eq_inv_px … H) -H [|*: // ] #g2 #Hfg2 #H destruct
 330   /3 width=1 by lsubf_push/
 331 | #f1 #f2 #I #K1 #K2 #_ #IH #g #H
 332   elim (eq_inv_nx … H) -H [|*: // ] #g2 #Hfg2 #H destruct
 333   /3 width=1 by lsubf_bind/
 334 | #f #f0 #f1 #f2 #K1 #L2 #W #V #Hf #Hf1 #_ #IH #g #H
 335   elim (eq_inv_nx … H) -H [|*: // ] #g2 #Hfg2 #H destruct
 336   /3 width=5 by lsubf_beta/
 337 | #f #f0 #f1 #f2 #I1 #I2 #K1 #K2 #V #Hf #Hf1 #_ #IH #g #H
 338   elim (eq_inv_nx … H) -H [|*: // ] #g2 #Hfg2 #H destruct
 339   /3 width=5 by lsubf_unit/
 340 ]
 341 qed-.
 342
 343 lemma lsubf_eq_repl_fwd2: ∀f1,L1,L2. eq_repl_fwd … (λf2. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄).
 344 #f1 #L1 #L2 @eq_repl_sym /2 width=3 by lsubf_eq_repl_back2/
 345 qed-.
 346
 347 lemma lsubf_refl: bi_reflexive … lsubf.
 348 #L elim L -L /2 width=1 by lsubf_atom, eq_refl/
 349 #L #I #IH #f elim (pn_split f) * #g #H destruct
 350 /2 width=1 by lsubf_push, lsubf_bind/
 351 qed.
 352
 353 lemma lsubf_refl_eq: ∀f1,f2,L. f1 ≡ f2 → ⦃L,f1⦄ ⫃𝐅+ ⦃L,f2⦄.
 354 /2 width=3 by lsubf_eq_repl_back2/ qed.
 355
 356 lemma lsubf_bind_tl_dx:
 357       ∀g1,f2,I,L1,L2. ⦃L1,g1⦄ ⫃𝐅+ ⦃L2,⫱f2⦄ →
 358       ∃∃f1. ⦃L1.ⓘ{I},f1⦄ ⫃𝐅+ ⦃L2.ⓘ{I},f2⦄ & g1 = ⫱f1.
 359 #g1 #f2 #I #L1 #L2 #H
 360 elim (pn_split f2) * #g2 #H2 destruct
 361 @ex2_intro [1,2,4,5: /2 width=2 by lsubf_push, lsubf_bind/ ] // (**) (* constructor needed *)
 362 qed-.
 363
 364 lemma lsubf_beta_tl_dx:
 365       ∀f,f0,g1,L1,V. L1 ⊢ 𝐅+⦃V⦄ ≘ f → f0 ⋓ f ≘ g1 →
 366       ∀f2,L2,W. ⦃L1,f0⦄ ⫃𝐅+ ⦃L2,⫱f2⦄ →
 367       ∃∃f1. ⦃L1.ⓓⓝW.V,f1⦄ ⫃𝐅+ ⦃L2.ⓛW,f2⦄ & ⫱f1 ⊆ g1.
 368 #f #f0 #g1 #L1 #V #Hf #Hg1 #f2
 369 elim (pn_split f2) * #x2 #H2 #L2 #W #HL12 destruct
 370 [ /3 width=4 by lsubf_push, sor_inv_sle_sn, ex2_intro/
 371 | @(ex2_intro … (↑g1)) /2 width=5 by lsubf_beta/ (**) (* full auto fails *)
 372 ]
 373 qed-.
 374
 375 (* Note: this might be moved *)
 376 lemma lsubf_inv_sor_dx:
 377       ∀f1,f2,L1,L2. ⦃L1,f1⦄ ⫃𝐅+ ⦃L2,f2⦄ →
 378       ∀f2l,f2r. f2l⋓f2r ≘ f2 →
 379       ∃∃f1l,f1r. ⦃L1,f1l⦄ ⫃𝐅+ ⦃L2,f2l⦄ & ⦃L1,f1r⦄ ⫃𝐅+ ⦃L2,f2r⦄ & f1l⋓f1r ≘ f1.
 380 #f1 #f2 #L1 #L2 #H elim H -f1 -f2 -L1 -L2
 381 [ /3 width=7 by sor_eq_repl_fwd3, ex3_2_intro/
 382 | #g1 #g2 #I1 #I2 #L1 #L2 #_ #IH #f2l #f2r #H
 383   elim (sor_inv_xxp … H) -H [|*: // ] #g2l #g2r #Hg2 #Hl #Hr destruct
 384   elim (IH … Hg2) -g2 /3 width=11 by lsubf_push, sor_pp, ex3_2_intro/
 385 | #g1 #g2 #I #L1 #L2 #_ #IH #f2l #f2r #H
 386   elim (sor_inv_xxn … H) -H [1,3,4: * |*: // ] #g2l #g2r #Hg2 #Hl #Hr destruct
 387   elim (IH … Hg2) -g2 /3 width=11 by lsubf_push, lsubf_bind, sor_np, sor_pn, sor_nn, ex3_2_intro/
 388 | #g #g0 #g1 #g2 #L1 #L2 #W #V #Hg #Hg1 #_ #IH #f2l #f2r #H
 389   elim (sor_inv_xxn … H) -H [1,3,4: * |*: // ] #g2l #g2r #Hg2 #Hl #Hr destruct
 390   elim (IH … Hg2) -g2 #g1l #g1r #Hl #Hr #Hg0
 391   [ lapply (sor_comm_23 … Hg0 Hg1 ?) -g0 [3: |*: // ] #Hg1
 392     /3 width=11 by lsubf_push, lsubf_beta, sor_np, ex3_2_intro/
 393   | lapply (sor_assoc_dx … Hg1 … Hg0 ??) -g0 [3: |*: // ] #Hg1
 394     /3 width=11 by lsubf_push, lsubf_beta, sor_pn, ex3_2_intro/
 395   | lapply (sor_distr_dx … Hg0 … Hg1) -g0 [5: |*: // ] #Hg1
 396     /3 width=11 by lsubf_beta, sor_nn, ex3_2_intro/
 397   ]
 398 | #g #g0 #g1 #g2 #I1 #I2 #L1 #L2 #V #Hg #Hg1 #_ #IH #f2l #f2r #H
 399   elim (sor_inv_xxn … H) -H [1,3,4: * |*: // ] #g2l #g2r #Hg2 #Hl #Hr destruct
 400   elim (IH … Hg2) -g2 #g1l #g1r #Hl #Hr #Hg0
 401   [ lapply (sor_comm_23 … Hg0 Hg1 ?) -g0 [3: |*: // ] #Hg1
 402     /3 width=11 by lsubf_push, lsubf_unit, sor_np, ex3_2_intro/
 403   | lapply (sor_assoc_dx … Hg1 … Hg0 ??) -g0 [3: |*: // ] #Hg1
 404     /3 width=11 by lsubf_push, lsubf_unit, sor_pn, ex3_2_intro/
 405   | lapply (sor_distr_dx … Hg0 … Hg1) -g0 [5: |*: // ] #Hg1
 406     /3 width=11 by lsubf_unit, sor_nn, ex3_2_intro/
 407   ]
 408 ]
 409 qed-.