X-Git-Url: http://matita.cs.unibo.it/gitweb/?p=helm.git;a=blobdiff_plain;f=matita%2Fmatita%2Fcontribs%2Flambdadelta%2Fbasic_2%2Fsyntax%2Flveq_lveq.ma;h=40a5fb5c86152316956817fe42f548133bdcebf6;hp=12b6f0cb65d81d21d5f0f5f8a5e967298ab0f81b;hb=222044da28742b24584549ba86b1805a87def070;hpb=1c8e230b1d81491b38126900d76201fb84303ced diff --git a/matita/matita/contribs/lambdadelta/basic_2/syntax/lveq_lveq.ma b/matita/matita/contribs/lambdadelta/basic_2/syntax/lveq_lveq.ma index 12b6f0cb6..40a5fb5c8 100644 --- a/matita/matita/contribs/lambdadelta/basic_2/syntax/lveq_lveq.ma +++ b/matita/matita/contribs/lambdadelta/basic_2/syntax/lveq_lveq.ma @@ -18,110 +18,36 @@ include "basic_2/syntax/lveq_length.ma". (* Main inversion lemmas ****************************************************) -theorem lveq_inv_pair_sn: ∀K1,K2,n. K1 ≋ⓧ*[n, n] K2 → - ∀I1,I2,V,m1,m2. K1.ⓑ{I1}V ≋ⓧ*[m1, m2] K2.ⓘ{I2} → - ∧∧ 0 = m1 & 0 = m2. -#K1 #K2 #n #HK #I1 #I2 #V #m1 #m2 #H +theorem lveq_inv_bind: ∀K1,K2. K1 ≋ⓧ*[0, 0] K2 → + ∀I1,I2,m1,m2. K1.ⓘ{I1} ≋ⓧ*[m1, m2] K2.ⓘ{I2} → + ∧∧ 0 = m1 & 0 = m2. +#K1 #K2 #HK #I1 #I2 #m1 #m2 #H lapply (lveq_fwd_length_eq … HK) -HK #HK -lapply (lveq_fwd_pair_sn … H) #H0 destruct -<(lveq_inj_length … H) -H normalize /3 width=1 by conj, eq_f/ +elim (lveq_inj_length … H) -H normalize /3 width=1 by conj, eq_f/ qed-. -theorem lveq_inv_pair_dx: ∀K1,K2,n. K1 ≋ⓧ*[n, n] K2 → - ∀I1,I2,V,m1,m2. K1.ⓘ{I1} ≋ⓧ*[m1, m2] K2.ⓑ{I2}V → - ∧∧ 0 = m1 & 0 = m2. -/4 width=8 by lveq_inv_pair_sn, lveq_sym, commutative_and/ qed-. -(* -theorem lveq_inv_void_sn: ∀K1,K2,n1,n2. K1 ≋ⓧ*[n1, n2] K2 → - ∀m1,m2. K1.ⓧ ≋ⓧ*[m1, m2] K2 → - 0 < m1. -*) -(* theorem lveq_inj: ∀L1,L2,n1,n2. L1 ≋ⓧ*[n1, n2] L2 → ∀m1,m2. L1 ≋ⓧ*[m1, m2] L2 → ∧∧ n1 = m1 & n2 = m2. -#L1 #L2 @(f2_ind ?? length2 ?? L1 L2) -L1 -L2 -#x #IH #L1 #L2 #Hx #n1 #n2 #H -generalize in match Hx; -Hx -cases H -L1 -L2 -n1 -n2 -/2 width=8 by lveq_inv_pair_dx, lveq_inv_pair_sn, lveq_inv_atom/ -#K1 #K2 #n1 #n2 #HK #Hx #m1 #m2 #H destruct - - - -[ #_ #m1 #m2 #HL -x /2 width=1 by lveq_inv_atom/ -| #I1 #I2 #K1 #K2 #V1 #n #HK #_ #m1 #m2 #H -x - - - -theorem lveq_inj: ∀L1,L2,n1,n2. L1 ≋ⓧ*[n1, n2] L2 → - ∀m1,m2. L1 ≋ⓧ*[m1, m2] L2 → - ∧∧ n1 = m1 & n2 = m2. -#L1 #L2 #n1 #n2 #H @(lveq_ind_voids … H) -H -L1 -L2 -n1 -n2 -[ #n1 #n2 #m1 #m2 #H elim (lveq_inv_voids … H) -H * - [ /3 width=1 by voids_inj, conj/ ] - #J1 #J2 #K1 #K2 #W #m #_ [ #H #_ | #_ #H ] - elim (voids_inv_pair_sn … H) -H #H #_ - elim (voids_atom_inv … H) -H #H #_ destruct -] -#I1 #I2 #L1 #L2 #V #n1 #n2 #n #HL #IH #m1 #m2 #H -elim (lveq_inv_voids … H) -H * -[1,4: [ #H #_ | #_ #H ] - elim (voids_inv_atom_sn … H) -H #H #_ - elim (voids_pair_inv … H) -H #H #_ destruct -] -#J1 #J2 #K1 #K2 #W #m #HK [1,3: #H1 #H2 |*: #H2 #H1 ] -elim (voids_inv_pair_sn … H1) -H1 #H #Hnm -[1,4: -IH -Hnm elim (voids_pair_inv … H) -H #H1 #H2 destruct -|2,3: elim (voids_inv_pair_dx … H2) -H2 #H2 #_ - - elim (IH … HK) - - -(* -/3 width=3 by lveq_inv_atom, lveq_inv_voids/ -| - lapply (lveq_inv_voids … H) -H #H - elim (lveq_inv_pair_sn … H) -H * /2 width=1 by conj/ - #Y2 #y2 #HY2 #H1 #H2 #H3 destruct -*) - -(* -fact lveq_inv_pair_bind_aux: ∀L1,L2,n1,n2. L1 ≋ ⓧ*[n1, n2] L2 → - ∀I1,I2,K1,K2,V1. K1.ⓑ{I1}V1 = L1 → K2.ⓘ{I2} = L2 → - ∨∨ ∃∃m. K1 ≋ ⓧ*[m, m] K2 & 0 = n1 & 0 = n2 - | ∃∃m1,m2. K1 ≋ ⓧ*[m1, m2] K2 & - BUnit Void = I2 & ⫯m2 = n2. -#L1 #L2 #n1 #n2 #H elim H -L1 -L2 -n1 -n2 -[ #J1 #J2 #L1 #L2 #V1 #H1 #H2 destruct -|2,3: #I1 #I2 #K1 #K2 #V #n #HK #_ #J1 #J2 #L1 #L2 #V1 #H1 #H2 destruct /3 width=2 by or_introl, ex3_intro/ -|4,5: #K1 #K2 #n1 #n2 #HK #IH #J1 #J2 #L1 #L2 #V1 #H1 #H2 destruct - /3 width=4 by _/ -] +#L1 #L2 #n1 #n2 #Hn #m1 #m2 #Hm +elim (lveq_fwd_length … Hn) -Hn #H1 #H2 destruct +elim (lveq_fwd_length … Hm) -Hm #H1 #H2 destruct +/2 width=1 by conj/ qed-. -lemma voids_inv_pair_bind: ∀I1,I2,K1,K2,V1,n1,n2. ⓧ*[n1]K1.ⓑ{I1}V1 ≋ ⓧ*[n2]K2.ⓘ{I2} → - ∨∨ ∃∃n. ⓧ*[n]K1 ≋ ⓧ*[n]K2 & 0 = n1 & 0 = n2 - | ∃∃m2. ⓧ*[n1]K1.ⓑ{I1}V1 ≋ ⓧ*[m2]K2 & - BUnit Void = I2 & ⫯m2 = n2. -/2 width=5 by voids_inv_pair_bind_aux/ qed-. - -fact voids_inv_bind_pair_aux: ∀L1,L2,n1,n2. ⓧ*[n1]L1 ≋ ⓧ*[n2]L2 → - ∀I1,I2,K1,K2,V2. K1.ⓘ{I1} = L1 → K2.ⓑ{I2}V2 = L2 → - ∨∨ ∃∃n. ⓧ*[n]K1 ≋ ⓧ*[n]K2 & 0 = n1 & 0 = n2 - | ∃∃m1. ⓧ*[m1]K1 ≋ ⓧ*[n2]K2.ⓑ{I2}V2 & - BUnit Void = I1 & ⫯m1 = n1. -#L1 #L2 #n1 #n2 * -L1 -L2 -n1 -n2 -[ #J1 #J2 #L1 #L2 #V1 #H1 #H2 destruct -|2,3: #I1 #I2 #K1 #K2 #V #n #HK #J1 #J2 #L1 #L2 #V2 #H1 #H2 destruct /3 width=2 by or_introl, ex3_intro/ -|4,5: #K1 #K2 #n1 #n2 #HK #J1 #J2 #L1 #L2 #V2 #H1 #H2 destruct /3 width=3 by or_intror, ex3_intro/ -] +theorem lveq_inj_void_sn_ge: ∀K1,K2. |K2| ≤ |K1| → + ∀n1,n2. K1 ≋ⓧ*[n1, n2] K2 → + ∀m1,m2. K1.ⓧ ≋ⓧ*[m1, m2] K2 → + ∧∧ ↑n1 = m1 & 0 = m2 & 0 = n2. +#L1 #L2 #HL #n1 #n2 #Hn #m1 #m2 #Hm +elim (lveq_fwd_length … Hn) -Hn #H1 #H2 destruct +elim (lveq_fwd_length … Hm) -Hm #H1 #H2 destruct +>length_bind >eq_minus_S_pred >(eq_minus_O … HL) +/3 width=4 by plus_minus, and3_intro/ qed-. -lemma voids_inv_bind_pair: ∀I1,I2,K1,K2,V2,n1,n2. ⓧ*[n1]K1.ⓘ{I1} ≋ ⓧ*[n2]K2.ⓑ{I2}V2 → - ∨∨ ∃∃n. ⓧ*[n]K1 ≋ ⓧ*[n]K2 & 0 = n1 & 0 = n2 - | ∃∃m1. ⓧ*[m1]K1 ≋ ⓧ*[n2]K2.ⓑ{I2}V2 & - BUnit Void = I1 & ⫯m1 = n1. -/2 width=5 by voids_inv_bind_pair_aux/ qed-. -*) -*) \ No newline at end of file +theorem lveq_inj_void_dx_le: ∀K1,K2. |K1| ≤ |K2| → + ∀n1,n2. K1 ≋ⓧ*[n1, n2] K2 → + ∀m1,m2. K1 ≋ⓧ*[m1, m2] K2.ⓧ → + ∧∧ ↑n2 = m2 & 0 = m1 & 0 = n1. +/3 width=5 by lveq_inj_void_sn_ge, lveq_sym/ qed-. (* auto: 2x lveq_sym *)