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=bd53c4e895203eb049e75434f638f26b5a161a2b;hp=cb5ede22b61de36de2ab149c6d9711148486000a;hpb=0c7cb3c503c0fcab104ad89ebc88683dc9830d06;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 cb5ede22b..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) @@ -83,77 +83,85 @@ 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. +lemma coafter_inv_ppp: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → + ∀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 → ⊥. +lemma coafter_inv_ppn: ∀g1,g2,g. g1 ~⊚ g2 ≘ 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. +lemma coafter_inv_pnn: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → + ∀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 → ⊥. +lemma coafter_inv_pnp: ∀g1,g2,g. g1 ~⊚ g2 ≘ 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. +lemma coafter_inv_nxp: ∀g1,f2,g. g1 ~⊚ f2 ≘ g → + ∀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 → ⊥. +lemma coafter_inv_nxn: ∀g1,f2,g. g1 ~⊚ f2 ≘ 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. +lemma coafter_inv_pxp: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → + ∀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) ] qed-. -lemma coafter_inv_pxn: ∀g1,g2,g. g1 ~⊚ g2 ≡ g → - ∀f1,f. ↑f1 = g1 → ⫯f = g → - ∃∃f2. f1 ~⊚ f2 ≡ f & ⫯f2 = g2. +lemma coafter_inv_pxn: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → + ∀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) ] 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_xnn: ∀g1,g2,g. g1 ~⊚ g2 ≘ g → + ∀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. #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/ @@ -161,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/ @@ -174,7 +182,7 @@ qed-. (* Basic properties *********************************************************) -corec lemma coafter_eq_repl_back2: ∀f1,f. eq_repl_back (λf2. f2 ~⊚ f1 ≡ f). +corec lemma coafter_eq_repl_back2: ∀f1,f. eq_repl_back (λf2. f2 ~⊚ f1 ≘ f). #f1 #f #f2 * -f2 -f1 -f #f21 #f1 #f #g21 [1,2: #g1 ] #g #Hf #H21 [1,2: #H1 ] #H #g22 #H0 [ cases (eq_inv_px … H0 … H21) -g21 /3 width=7 by coafter_refl/ @@ -183,11 +191,11 @@ corec lemma coafter_eq_repl_back2: ∀f1,f. eq_repl_back (λf2. f2 ~⊚ f1 ≡ f ] qed-. -lemma coafter_eq_repl_fwd2: ∀f1,f. eq_repl_fwd (λf2. f2 ~⊚ f1 ≡ f). +lemma coafter_eq_repl_fwd2: ∀f1,f. eq_repl_fwd (λf2. f2 ~⊚ f1 ≘ f). #f1 #f @eq_repl_sym /2 width=3 by coafter_eq_repl_back2/ qed-. -corec lemma coafter_eq_repl_back1: ∀f2,f. eq_repl_back (λf1. f2 ~⊚ f1 ≡ f). +corec lemma coafter_eq_repl_back1: ∀f2,f. eq_repl_back (λf1. f2 ~⊚ f1 ≘ f). #f2 #f #f1 * -f2 -f1 -f #f2 #f11 #f #g2 [1,2: #g11 ] #g #Hf #H2 [1,2: #H11 ] #H #g2 #H0 [ cases (eq_inv_px … H0 … H11) -g11 /3 width=7 by coafter_refl/ @@ -196,11 +204,11 @@ corec lemma coafter_eq_repl_back1: ∀f2,f. eq_repl_back (λf1. f2 ~⊚ f1 ≡ f ] qed-. -lemma coafter_eq_repl_fwd1: ∀f2,f. eq_repl_fwd (λf1. f2 ~⊚ f1 ≡ f). +lemma coafter_eq_repl_fwd1: ∀f2,f. eq_repl_fwd (λf1. f2 ~⊚ f1 ≘ f). #f2 #f @eq_repl_sym /2 width=3 by coafter_eq_repl_back1/ qed-. -corec lemma coafter_eq_repl_back0: ∀f1,f2. eq_repl_back (λf. f2 ~⊚ f1 ≡ f). +corec lemma coafter_eq_repl_back0: ∀f1,f2. eq_repl_back (λf. f2 ~⊚ f1 ≘ f). #f2 #f1 #f * -f2 -f1 -f #f2 #f1 #f01 #g2 [1,2: #g1 ] #g01 #Hf01 #H2 [1,2: #H1 ] #H01 #g02 #H0 [ cases (eq_inv_px … H0 … H01) -g01 /3 width=7 by coafter_refl/ @@ -209,13 +217,13 @@ corec lemma coafter_eq_repl_back0: ∀f1,f2. eq_repl_back (λf. f2 ~⊚ f1 ≡ f ] qed-. -lemma coafter_eq_repl_fwd0: ∀f2,f1. eq_repl_fwd (λf. f2 ~⊚ f1 ≡ f). +lemma coafter_eq_repl_fwd0: ∀f2,f1. eq_repl_fwd (λf. f2 ~⊚ f1 ≘ f). #f2 #f1 @eq_repl_sym /2 width=3 by coafter_eq_repl_back0/ 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/ @@ -224,52 +232,74 @@ 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. +lemma coafter_mono_eq: ∀f1,f2,f. f1 ~⊚ f2 ≘ f → ∀g1,g2,g. g1 ~⊚ g2 ≘ g → + f1 ≡ g1 → f2 ≡ g2 → f ≡ g. /4 width=4 by coafter_mono, coafter_eq_repl_back1, coafter_eq_repl_back2/ qed-. -(* Inversion lemmas with pushs **********************************************) - -lemma coafter_fwd_pushs: ∀n,g2,g1,g. g2 ~⊚ g1 ≡ g → @⦃0, g2⦄ ≡ n → - ∃f. ↑*[n]f = g. -#n elim n -n /2 width=2 by ex_intro/ -#n #IH #g2 #g1 #g #Hg #Hg2 -cases (at_inv_pxn … Hg2) -Hg2 [ |*: // ] #f2 #Hf2 #H2 -cases (coafter_inv_nxx … Hg … H2) -Hg -H2 #f #Hf #H0 destruct -elim (IH … Hf Hf2) -g1 -g2 -f2 /2 width=2 by ex_intro/ +(* Forward lemmas with pushs ************************************************) + +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 + /2 width=2 by ex_intro/ +| #j #IH * [| #i ] #g2 #f1 #g #Hg #H + [ elim (at_inv_pxn … H) -H [|*: // ] #f2 #Hij #H destruct + elim (coafter_inv_nxx … Hg) -Hg [|*: // ] #f #Hf #H destruct + elim (IH … Hf Hij) -f1 -f2 -IH /2 width=2 by ex_intro/ + | elim (at_inv_nxn … H) -H [1,4: * |*: // ] #f2 #Hij #H destruct + [ elim (coafter_inv_ppx … Hg) -Hg [|*: // ] #f #Hf #H destruct + elim (IH … Hf Hij) -f1 -f2 -i /2 width=2 by ex_intro/ + | elim (coafter_inv_nxx … Hg) -Hg [|*: // ] #f #Hf #H destruct + elim (IH … Hf Hij) -f1 -f2 -i /2 width=2 by ex_intro/ + ] + ] +] qed-. (* Inversion lemmas with tail ***********************************************) -lemma coafter_inv_tl1: ∀g2,g1,g. g2 ~⊚ ⫱g1 ≡ g → - ∃∃f. ↑g2 ~⊚ g1 ≡ f & ⫱f = g. +lemma coafter_inv_tl1: ∀g2,g1,g. g2 ~⊚ ⫱g1 ≘ 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. +lemma coafter_inv_tl0: ∀g2,g1,g. g2 ~⊚ g1 ≘ ⫱g → + ∃∃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 on tls ********************************************************) - -lemma coafter_tls: ∀n,f1,f2,f. @⦃0, f1⦄ ≡ n → - f1 ~⊚ f2 ≡ f → ⫱*[n]f1 ~⊚ f2 ≡ ⫱*[n]f. -#n elim n -n // -#n #IH #f1 #f2 #f #Hf1 #Hf -cases (at_inv_pxn … Hf1) -Hf1 [ |*: // ] #g1 #Hg1 #H1 -cases (coafter_inv_nxx … Hf … H1) -Hf #g #Hg #H0 destruct -