X-Git-Url: http://matita.cs.unibo.it/gitweb/?a=blobdiff_plain;f=matita%2Fmatita%2Fcontribs%2Flambdadelta%2Fground_2%2Frelocation%2Frtmap_coafter.ma;h=0eb098301ceca87f2f6a1daf1b8705e3eb2139b7;hb=1fd63df4c77f5c24024769432ea8492748b4ac79;hp=8354c3d77563719db9b6583bcccbcac4a578f33a;hpb=75f395f0febd02de8e0f881d918a8812b1425c8d;p=helm.git diff --git a/matita/matita/contribs/lambdadelta/ground_2/relocation/rtmap_coafter.ma b/matita/matita/contribs/lambdadelta/ground_2/relocation/rtmap_coafter.ma index 8354c3d77..0eb098301 100644 --- a/matita/matita/contribs/lambdadelta/ground_2/relocation/rtmap_coafter.ma +++ b/matita/matita/contribs/lambdadelta/ground_2/relocation/rtmap_coafter.ma @@ -20,30 +20,30 @@ include "ground_2/relocation/rtmap_after.ma". coinductive coafter: relation3 rtmap rtmap rtmap ≝ | coafter_refl: ∀f1,f2,f,g1,g2,g. coafter f1 f2 f → - ↑f1 = g1 → ↑f2 = g2 → ↑f = g → coafter g1 g2 g + ⫯f1 = g1 → ⫯f2 = g2 → ⫯f = g → coafter g1 g2 g | coafter_push: ∀f1,f2,f,g1,g2,g. coafter f1 f2 f → - ↑f1 = g1 → ⫯f2 = g2 → ⫯f = g → coafter g1 g2 g + ⫯f1 = g1 → ↑f2 = g2 → ↑f = g → coafter g1 g2 g | coafter_next: ∀f1,f2,f,g1,g. coafter f1 f2 f → - ⫯f1 = g1 → ↑f = g → coafter g1 f2 g + ↑f1 = g1 → ⫯f = g → coafter g1 f2 g . interpretation "relational co-composition (rtmap)" 'RCoAfter f1 f2 f = (coafter f1 f2 f). definition H_coafter_inj: predicate rtmap ≝ - λf1. 𝐓⦃f1⦄ → - ∀f,f21,f22. f1 ~⊚ f21 ≘ f → f1 ~⊚ f22 ≘ f → f21 ≗ f22. + λf1. 𝐓❪f1❫ → + ∀f,f21,f22. f1 ~⊚ f21 ≘ f → f1 ~⊚ f22 ≘ f → f21 ≡ f22. definition H_coafter_fwd_isid2: predicate rtmap ≝ - λf1. ∀f2,f. f1 ~⊚ f2 ≘ f → 𝐓⦃f1⦄ → 𝐈⦃f⦄ → 𝐈⦃f2⦄. + λf1. ∀f2,f. f1 ~⊚ f2 ≘ f → 𝐓❪f1❫ → 𝐈❪f❫ → 𝐈❪f2❫. definition H_coafter_isfin2_fwd: predicate rtmap ≝ - λf1. ∀f2. 𝐅⦃f2⦄ → 𝐓⦃f1⦄ → ∀f. f1 ~⊚ f2 ≘ f → 𝐅⦃f⦄. + λf1. ∀f2. 𝐅❪f2❫ → 𝐓❪f1❫ → ∀f. f1 ~⊚ f2 ≘ f → 𝐅❪f❫. (* Basic inversion lemmas ***************************************************) -lemma coafter_inv_ppx: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → ∀f1,f2. ↑f1 = g1 → ↑f2 = g2 → - ∃∃f. f1 ~⊚ f2 ≘ f & ↑f = g. +lemma coafter_inv_ppx: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → ∀f1,f2. ⫯f1 = g1 → ⫯f2 = g2 → + ∃∃f. f1 ~⊚ f2 ≘ f & ⫯f = g. #g1 #g2 #g * -g1 -g2 -g #f1 #f2 #f #g1 [ #g2 #g #Hf #H1 #H2 #H #x1 #x2 #Hx1 #Hx2 destruct >(injective_push … Hx1) >(injective_push … Hx2) -x2 -x1 @@ -55,8 +55,8 @@ lemma coafter_inv_ppx: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → ∀f1,f2. ↑f1 = g1 → ] qed-. -lemma coafter_inv_pnx: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → ∀f1,f2. ↑f1 = g1 → ⫯f2 = g2 → - ∃∃f. f1 ~⊚ f2 ≘ f & ⫯f = g. +lemma coafter_inv_pnx: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → ∀f1,f2. ⫯f1 = g1 → ↑f2 = g2 → + ∃∃f. f1 ~⊚ f2 ≘ f & ↑f = g. #g1 #g2 #g * -g1 -g2 -g #f1 #f2 #f #g1 [ #g2 #g #_ #_ #H2 #_ #x1 #x2 #_ #Hx2 destruct elim (discr_next_push … Hx2) @@ -68,8 +68,8 @@ lemma coafter_inv_pnx: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → ∀f1,f2. ↑f1 = g1 → ] qed-. -lemma coafter_inv_nxx: ∀g1,f2,g. g1 ~⊚ f2 ≘ g → ∀f1. ⫯f1 = g1 → - ∃∃f. f1 ~⊚ f2 ≘ f & ↑f = g. +lemma coafter_inv_nxx: ∀g1,f2,g. g1 ~⊚ f2 ≘ g → ∀f1. ↑f1 = g1 → + ∃∃f. f1 ~⊚ f2 ≘ f & ⫯f = g. #g1 #f2 #g * -g1 -f2 -g #f1 #f2 #f #g1 [ #g2 #g #_ #H1 #_ #_ #x1 #Hx1 destruct elim (discr_next_push … Hx1) @@ -84,50 +84,50 @@ qed-. (* Advanced inversion lemmas ************************************************) lemma coafter_inv_ppp: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → - ∀f1,f2,f. ↑f1 = g1 → ↑f2 = g2 → ↑f = g → f1 ~⊚ f2 ≘ f. + ∀f1,f2,f. ⫯f1 = g1 → ⫯f2 = g2 → ⫯f = g → f1 ~⊚ f2 ≘ f. #g1 #g2 #g #Hg #f1 #f2 #f #H1 #H2 #H elim (coafter_inv_ppx … Hg … H1 H2) -g1 -g2 #x #Hf #Hx destruct <(injective_push … Hx) -f // qed-. lemma coafter_inv_ppn: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → - ∀f1,f2,f. ↑f1 = g1 → ↑f2 = g2 → ⫯f = g → ⊥. + ∀f1,f2,f. ⫯f1 = g1 → ⫯f2 = g2 → ↑f = g → ⊥. #g1 #g2 #g #Hg #f1 #f2 #f #H1 #H2 #H elim (coafter_inv_ppx … Hg … H1 H2) -g1 -g2 #x #Hf #Hx destruct elim (discr_push_next … Hx) qed-. lemma coafter_inv_pnn: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → - ∀f1,f2,f. ↑f1 = g1 → ⫯f2 = g2 → ⫯f = g → f1 ~⊚ f2 ≘ f. + ∀f1,f2,f. ⫯f1 = g1 → ↑f2 = g2 → ↑f = g → f1 ~⊚ f2 ≘ f. #g1 #g2 #g #Hg #f1 #f2 #f #H1 #H2 #H elim (coafter_inv_pnx … Hg … H1 H2) -g1 -g2 #x #Hf #Hx destruct <(injective_next … Hx) -f // qed-. lemma coafter_inv_pnp: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → - ∀f1,f2,f. ↑f1 = g1 → ⫯f2 = g2 → ↑f = g → ⊥. + ∀f1,f2,f. ⫯f1 = g1 → ↑f2 = g2 → ⫯f = g → ⊥. #g1 #g2 #g #Hg #f1 #f2 #f #H1 #H2 #H elim (coafter_inv_pnx … Hg … H1 H2) -g1 -g2 #x #Hf #Hx destruct elim (discr_next_push … Hx) qed-. lemma coafter_inv_nxp: ∀g1,f2,g. g1 ~⊚ f2 ≘ g → - ∀f1,f. ⫯f1 = g1 → ↑f = g → f1 ~⊚ f2 ≘ f. + ∀f1,f. ↑f1 = g1 → ⫯f = g → f1 ~⊚ f2 ≘ f. #g1 #f2 #g #Hg #f1 #f #H1 #H elim (coafter_inv_nxx … Hg … H1) -g1 #x #Hf #Hx destruct <(injective_push … Hx) -f // qed-. lemma coafter_inv_nxn: ∀g1,f2,g. g1 ~⊚ f2 ≘ g → - ∀f1,f. ⫯f1 = g1 → ⫯f = g → ⊥. + ∀f1,f. ↑f1 = g1 → ↑f = g → ⊥. #g1 #f2 #g #Hg #f1 #f #H1 #H elim (coafter_inv_nxx … Hg … H1) -g1 #x #Hf #Hx destruct elim (discr_push_next … Hx) qed-. lemma coafter_inv_pxp: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → - ∀f1,f. ↑f1 = g1 → ↑f = g → - ∃∃f2. f1 ~⊚ f2 ≘ f & ↑f2 = g2. + ∀f1,f. ⫯f1 = g1 → ⫯f = g → + ∃∃f2. f1 ~⊚ f2 ≘ f & ⫯f2 = g2. #g1 #g2 #g #Hg #f1 #f #H1 #H elim (pn_split g2) * #f2 #H2 [ lapply (coafter_inv_ppp … Hg … H1 H2 H) -g1 -g /2 width=3 by ex2_intro/ | elim (coafter_inv_pnp … Hg … H1 H2 H) @@ -135,16 +135,16 @@ lemma coafter_inv_pxp: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → qed-. lemma coafter_inv_pxn: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → - ∀f1,f. ↑f1 = g1 → ⫯f = g → - ∃∃f2. f1 ~⊚ f2 ≘ f & ⫯f2 = g2. + ∀f1,f. ⫯f1 = g1 → ↑f = g → + ∃∃f2. f1 ~⊚ f2 ≘ f & ↑f2 = g2. #g1 #g2 #g #Hg #f1 #f #H1 #H elim (pn_split g2) * #f2 #H2 [ elim (coafter_inv_ppn … Hg … H1 H2 H) | lapply (coafter_inv_pnn … Hg … H1 … H) -g1 -g /2 width=3 by ex2_intro/ ] qed-. -lemma coafter_inv_xxn: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → ∀f. ⫯f = g → - ∃∃f1,f2. f1 ~⊚ f2 ≘ f & ↑f1 = g1 & ⫯f2 = g2. +lemma coafter_inv_xxn: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → ∀f. ↑f = g → + ∃∃f1,f2. f1 ~⊚ f2 ≘ f & ⫯f1 = g1 & ↑f2 = g2. #g1 #g2 #g #Hg #f #H elim (pn_split g1) * #f1 #H1 [ elim (coafter_inv_pxn … Hg … H1 H) -g /2 width=5 by ex3_2_intro/ | elim (coafter_inv_nxn … Hg … H1 H) @@ -152,16 +152,16 @@ lemma coafter_inv_xxn: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → ∀f. ⫯f = g → qed-. lemma coafter_inv_xnn: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → - ∀f2,f. ⫯f2 = g2 → ⫯f = g → - ∃∃f1. f1 ~⊚ f2 ≘ f & ↑f1 = g1. + ∀f2,f. ↑f2 = g2 → ↑f = g → + ∃∃f1. f1 ~⊚ f2 ≘ f & ⫯f1 = g1. #g1 #g2 #g #Hg #f2 #f #H2 destruct #H elim (coafter_inv_xxn … Hg … H) -g #z1 #z2 #Hf #H1 #H2 destruct /2 width=3 by ex2_intro/ qed-. -lemma coafter_inv_xxp: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → ∀f. ↑f = g → - (∃∃f1,f2. f1 ~⊚ f2 ≘ f & ↑f1 = g1 & ↑f2 = g2) ∨ - ∃∃f1. f1 ~⊚ g2 ≘ f & ⫯f1 = g1. +lemma coafter_inv_xxp: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → ∀f. ⫯f = g → + (∃∃f1,f2. f1 ~⊚ f2 ≘ f & ⫯f1 = g1 & ⫯f2 = g2) ∨ + ∃∃f1. f1 ~⊚ g2 ≘ f & ↑f1 = g1. #g1 #g2 #g #Hg #f #H elim (pn_split g1) * #f1 #H1 [ elim (coafter_inv_pxp … Hg … H1 H) -g /3 width=5 by or_introl, ex3_2_intro/ @@ -169,9 +169,9 @@ lemma coafter_inv_xxp: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → ∀f. ↑f = g → ] qed-. -lemma coafter_inv_pxx: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → ∀f1. ↑f1 = g1 → - (∃∃f2,f. f1 ~⊚ f2 ≘ f & ↑f2 = g2 & ↑f = g) ∨ - (∃∃f2,f. f1 ~⊚ f2 ≘ f & ⫯f2 = g2 & ⫯f = g). +lemma coafter_inv_pxx: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → ∀f1. ⫯f1 = g1 → + (∃∃f2,f. f1 ~⊚ f2 ≘ f & ⫯f2 = g2 & ⫯f = g) ∨ + (∃∃f2,f. f1 ~⊚ f2 ≘ f & ↑f2 = g2 & ↑f = g). #g1 #g2 #g #Hg #f1 #H1 elim (pn_split g2) * #f2 #H2 [ elim (coafter_inv_ppx … Hg … H1 H2) -g1 /3 width=5 by or_introl, ex3_2_intro/ @@ -223,7 +223,7 @@ qed-. (* Main inversion lemmas ****************************************************) -corec theorem coafter_mono: ∀f1,f2,x,y. f1 ~⊚ f2 ≘ x → f1 ~⊚ f2 ≘ y → x ≗ y. +corec theorem coafter_mono: ∀f1,f2,x,y. f1 ~⊚ f2 ≘ x → f1 ~⊚ f2 ≘ y → x ≡ y. #f1 #f2 #x #y * -f1 -f2 -x #f1 #f2 #x #g1 [1,2: #g2 ] #g #Hx #H1 [1,2: #H2 ] #H0x #Hy [ cases (coafter_inv_ppx … Hy … H1 H2) -g1 -g2 /3 width=8 by eq_push/ @@ -233,13 +233,13 @@ corec theorem coafter_mono: ∀f1,f2,x,y. f1 ~⊚ f2 ≘ x → f1 ~⊚ f2 ≘ y qed-. lemma coafter_mono_eq: ∀f1,f2,f. f1 ~⊚ f2 ≘ f → ∀g1,g2,g. g1 ~⊚ g2 ≘ g → - f1 ≗ g1 → f2 ≗ g2 → f ≗ g. + f1 ≡ g1 → f2 ≡ g2 → f ≡ g. /4 width=4 by coafter_mono, coafter_eq_repl_back1, coafter_eq_repl_back2/ qed-. (* Forward lemmas with pushs ************************************************) -lemma coafter_fwd_pushs: ∀j,i,g2,f1,g. g2 ~⊚ ↑*[i]f1 ≘ g → @⦃i, g2⦄ ≘ j → - ∃f. ↑*[j] f = g. +lemma coafter_fwd_pushs: ∀j,i,g2,f1,g. g2 ~⊚ ⫯*[i]f1 ≘ g → @❪i, g2❫ ≘ j → + ∃f. ⫯*[j] f = g. #j elim j -j [ #i #g2 #f1 #g #Hg #H elim (at_inv_xxp … H) -H [|*: // ] #f2 #H1 #H2 destruct @@ -261,24 +261,24 @@ qed-. (* Inversion lemmas with tail ***********************************************) lemma coafter_inv_tl1: ∀g2,g1,g. g2 ~⊚ ⫱g1 ≘ g → - ∃∃f. ↑g2 ~⊚ g1 ≘ f & ⫱f = g. + ∃∃f. ⫯g2 ~⊚ g1 ≘ f & ⫱f = g. #g2 #g1 #g elim (pn_split g1) * #f1 #H1 #H destruct [ /3 width=7 by coafter_refl, ex2_intro/ -| @(ex2_intro … (⫯g)) /2 width=7 by coafter_push/ (**) (* full auto fails *) +| @(ex2_intro … (↑g)) /2 width=7 by coafter_push/ (**) (* full auto fails *) ] qed-. lemma coafter_inv_tl0: ∀g2,g1,g. g2 ~⊚ g1 ≘ ⫱g → - ∃∃f1. ↑g2 ~⊚ f1 ≘ g & ⫱f1 = g1. + ∃∃f1. ⫯g2 ~⊚ f1 ≘ g & ⫱f1 = g1. #g2 #g1 #g elim (pn_split g) * #f #H0 #H destruct [ /3 width=7 by coafter_refl, ex2_intro/ -| @(ex2_intro … (⫯g1)) /2 width=7 by coafter_push/ (**) (* full auto fails *) +| @(ex2_intro … (↑g1)) /2 width=7 by coafter_push/ (**) (* full auto fails *) ] qed-. (* Properties with iterated tail ********************************************) -lemma coafter_tls: ∀j,i,f1,f2,f. @⦃i, f1⦄ ≘ j → +lemma coafter_tls: ∀j,i,f1,f2,f. @❪i, f1❫ ≘ j → f1 ~⊚ f2 ≘ f → ⫱*[j]f1 ~⊚ ⫱*[i]f2 ≘ ⫱*[j]f. #j elim j -j [ #i | #j #IH * [| #i ] ] #f1 #f2 #f #Hf1 #Hf [ elim (at_inv_xxp … Hf1) -Hf1 [ |*: // ] #g1 #Hg1 #H1 destruct // @@ -294,12 +294,12 @@ lemma coafter_tls: ∀j,i,f1,f2,f. @⦃i, f1⦄ ≘ j → ] qed. -lemma coafter_tls_O: ∀n,f1,f2,f. @⦃0, f1⦄ ≘ n → +lemma coafter_tls_O: ∀n,f1,f2,f. @❪0, f1❫ ≘ n → f1 ~⊚ f2 ≘ f → ⫱*[n]f1 ~⊚ f2 ≘ ⫱*[n]f. /2 width=1 by coafter_tls/ qed. lemma coafter_tls_succ: ∀g2,g1,g. g2 ~⊚ g1 ≘ g → - ∀n. @⦃0, g2⦄ ≘ n → ⫱*[⫯n]g2 ~⊚ ⫱g1 ≘ ⫱*[⫯n]g. + ∀n. @❪0, g2❫ ≘ n → ⫱*[↑n]g2 ~⊚ ⫱g1 ≘ ⫱*[↑n]g. #g2 #g1 #g #Hg #n #Hg2 lapply (coafter_tls … Hg2 … Hg) -Hg #Hg lapply (at_pxx_tls … Hg2) -Hg2 #H @@ -308,8 +308,8 @@ elim (coafter_inv_pxx … Hg … H2) -Hg * #f1 #f #Hf #H1 #H0 destruct