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