351 (* ----------------------------------------------------------------------------------- *) |
351 (* ----------------------------------------------------------------------------------- *) |
352 |
352 |
353 section "induction"; |
353 section "induction"; |
354 |
354 |
355 goal thy "!! P. [| adm P; P UU; P nil; !! a s. P s ==> P (a>>s)|] ==> P x"; |
355 goal thy "!! P. [| adm P; P UU; P nil; !! a s. P s ==> P (a>>s)|] ==> P x"; |
356 be seq.ind 1; |
356 by (etac seq.ind 1); |
357 by (REPEAT (atac 1)); |
357 by (REPEAT (atac 1)); |
358 by (def_tac 1); |
358 by (def_tac 1); |
359 by (asm_full_simp_tac (!simpset addsimps [Cons_def]) 1); |
359 by (asm_full_simp_tac (!simpset addsimps [Cons_def]) 1); |
360 qed"Seq_induct"; |
360 qed"Seq_induct"; |
361 |
361 |
362 goal thy "!! P.[|P UU;P nil; !! a s. P s ==> P(a>>s) |] \ |
362 goal thy "!! P.[|P UU;P nil; !! a s. P s ==> P(a>>s) |] \ |
363 \ ==> seq_finite x --> P x"; |
363 \ ==> seq_finite x --> P x"; |
364 be seq_finite_ind 1; |
364 by (etac seq_finite_ind 1); |
365 by (REPEAT (atac 1)); |
365 by (REPEAT (atac 1)); |
366 by (def_tac 1); |
366 by (def_tac 1); |
367 by (asm_full_simp_tac (!simpset addsimps [Cons_def]) 1); |
367 by (asm_full_simp_tac (!simpset addsimps [Cons_def]) 1); |
368 qed"Seq_FinitePartial_ind"; |
368 qed"Seq_FinitePartial_ind"; |
369 |
369 |
370 goal thy "!! P.[| Finite x; P nil; !! a s. [| Finite s; P s|] ==> P (a>>s) |] ==> P x"; |
370 goal thy "!! P.[| Finite x; P nil; !! a s. [| Finite s; P s|] ==> P (a>>s) |] ==> P x"; |
371 be sfinite.induct 1; |
371 by (etac sfinite.induct 1); |
372 ba 1; |
372 by (assume_tac 1); |
373 by (def_tac 1); |
373 by (def_tac 1); |
374 by (asm_full_simp_tac (!simpset addsimps [Cons_def]) 1); |
374 by (asm_full_simp_tac (!simpset addsimps [Cons_def]) 1); |
375 qed"Seq_Finite_ind"; |
375 qed"Seq_Finite_ind"; |
376 |
376 |
377 |
377 |
459 by (Seq_Finite_induct_tac 1); |
459 by (Seq_Finite_induct_tac 1); |
460 by (strip_tac 1); |
460 by (strip_tac 1); |
461 by (Seq_case_simp_tac "t" 1); |
461 by (Seq_case_simp_tac "t" 1); |
462 by (Asm_full_simp_tac 1); |
462 by (Asm_full_simp_tac 1); |
463 (* main case *) |
463 (* main case *) |
464 auto(); |
464 by (Auto_tac()); |
465 by (Seq_case_simp_tac "t" 1); |
465 by (Seq_case_simp_tac "t" 1); |
466 by (Asm_full_simp_tac 1); |
466 by (Asm_full_simp_tac 1); |
467 qed"FiniteMap2"; |
467 qed"FiniteMap2"; |
468 |
468 |
469 goal thy "Finite (Map f`s) = Finite s"; |
469 goal thy "Finite (Map f`s) = Finite s"; |
470 auto(); |
470 by (Auto_tac()); |
471 be (FiniteMap2 RS spec RS mp) 1; |
471 by (etac (FiniteMap2 RS spec RS mp) 1); |
472 br refl 1; |
472 by (rtac refl 1); |
473 be FiniteMap1 1; |
473 by (etac FiniteMap1 1); |
474 qed"Map2Finite"; |
474 qed"Map2Finite"; |
475 |
475 |
476 |
476 |
477 goal thy "!! s. Finite s ==> Finite (Filter P`s)"; |
477 goal thy "!! s. Finite s ==> Finite (Filter P`s)"; |
478 by (Seq_Finite_induct_tac 1); |
478 by (Seq_Finite_induct_tac 1); |
490 to Finite_flat *) |
490 to Finite_flat *) |
491 |
491 |
492 goal thy "!! (x:: 'a Seq). Finite x ==> !y. Finite (y:: 'a Seq) & x<<y --> x=y"; |
492 goal thy "!! (x:: 'a Seq). Finite x ==> !y. Finite (y:: 'a Seq) & x<<y --> x=y"; |
493 by (Seq_Finite_induct_tac 1); |
493 by (Seq_Finite_induct_tac 1); |
494 by (strip_tac 1); |
494 by (strip_tac 1); |
495 be conjE 1; |
495 by (etac conjE 1); |
496 be nil_less_is_nil 1; |
496 by (etac nil_less_is_nil 1); |
497 (* main case *) |
497 (* main case *) |
498 auto(); |
498 by (Auto_tac()); |
499 by (Seq_case_simp_tac "y" 1); |
499 by (Seq_case_simp_tac "y" 1); |
500 auto(); |
500 by (Auto_tac()); |
501 qed_spec_mp"Finite_flat"; |
501 qed_spec_mp"Finite_flat"; |
502 |
502 |
503 |
503 |
504 goal thy "adm(%(x:: 'a Seq).Finite x)"; |
504 goal thy "adm(%(x:: 'a Seq).Finite x)"; |
505 br admI 1; |
505 by (rtac admI 1); |
506 by (eres_inst_tac [("x","0")] allE 1); |
506 by (eres_inst_tac [("x","0")] allE 1); |
507 back(); |
507 back(); |
508 be exE 1; |
508 by (etac exE 1); |
509 by (REPEAT (etac conjE 1)); |
509 by (REPEAT (etac conjE 1)); |
510 by (res_inst_tac [("x","0")] allE 1); |
510 by (res_inst_tac [("x","0")] allE 1); |
511 ba 1; |
511 by (assume_tac 1); |
512 by (eres_inst_tac [("x","j")] allE 1); |
512 by (eres_inst_tac [("x","j")] allE 1); |
513 by (cut_inst_tac [("x","Y 0"),("y","Y j")] Finite_flat 1); |
513 by (cut_inst_tac [("x","Y 0"),("y","Y j")] Finite_flat 1); |
514 (* Generates a contradiction in subgoal 3 *) |
514 (* Generates a contradiction in subgoal 3 *) |
515 auto(); |
515 by (Auto_tac()); |
516 qed"adm_Finite"; |
516 qed"adm_Finite"; |
517 |
517 |
518 Addsimps [adm_Finite]; |
518 Addsimps [adm_Finite]; |
519 |
519 |
520 |
520 |
653 goal thy "! s. Forall P s --> t<<s --> Forall P t"; |
653 goal thy "! s. Forall P s --> t<<s --> Forall P t"; |
654 by (Seq_induct_tac "t" [Forall_def,sforall_def] 1); |
654 by (Seq_induct_tac "t" [Forall_def,sforall_def] 1); |
655 by (strip_tac 1); |
655 by (strip_tac 1); |
656 by (Seq_case_simp_tac "sa" 1); |
656 by (Seq_case_simp_tac "sa" 1); |
657 by (Asm_full_simp_tac 1); |
657 by (Asm_full_simp_tac 1); |
658 auto(); |
658 by (Auto_tac()); |
659 qed"Forall_prefix"; |
659 qed"Forall_prefix"; |
660 |
660 |
661 bind_thm ("Forall_prefixclosed",Forall_prefix RS spec RS mp RS mp); |
661 bind_thm ("Forall_prefixclosed",Forall_prefix RS spec RS mp RS mp); |
662 |
662 |
663 |
663 |
664 goal thy "!! h. [| Finite h; Forall P s; s= h @@ t |] ==> Forall P t"; |
664 goal thy "!! h. [| Finite h; Forall P s; s= h @@ t |] ==> Forall P t"; |
665 auto(); |
665 by (Auto_tac()); |
666 qed"Forall_postfixclosed"; |
666 qed"Forall_postfixclosed"; |
667 |
667 |
668 |
668 |
669 goal thy "((! x. P x --> (Q x = R x)) & Forall P tr) --> Filter Q`tr = Filter R`tr"; |
669 goal thy "((! x. P x --> (Q x = R x)) & Forall P tr) --> Filter Q`tr = Filter R`tr"; |
670 by (Seq_induct_tac "tr" [Forall_def,sforall_def] 1); |
670 by (Seq_induct_tac "tr" [Forall_def,sforall_def] 1); |
739 |
739 |
740 goal thy "!! P. Filter P`ys = UU ==> \ |
740 goal thy "!! P. Filter P`ys = UU ==> \ |
741 \ (Forall (%x. ~P x) ys & ~Finite ys)"; |
741 \ (Forall (%x. ~P x) ys & ~Finite ys)"; |
742 by (rtac conjI 1); |
742 by (rtac conjI 1); |
743 by (cut_inst_tac [] (FilterUU_nFinite_lemma2 RS mp COMP rev_contrapos) 1); |
743 by (cut_inst_tac [] (FilterUU_nFinite_lemma2 RS mp COMP rev_contrapos) 1); |
744 auto(); |
744 by (Auto_tac()); |
745 by (blast_tac (!claset addSDs [FilterUU_nFinite_lemma1]) 1); |
745 by (blast_tac (!claset addSDs [FilterUU_nFinite_lemma1]) 1); |
746 qed"FilternPUUForallP"; |
746 qed"FilternPUUForallP"; |
747 |
747 |
748 |
748 |
749 goal thy "!! Q P.[| Forall Q ys; Finite ys; !!x. Q x ==> ~P x|] \ |
749 goal thy "!! Q P.[| Forall Q ys; Finite ys; !!x. Q x ==> ~P x|] \ |
750 \ ==> Filter P`ys = nil"; |
750 \ ==> Filter P`ys = nil"; |
751 be ForallnPFilterPnil 1; |
751 by (etac ForallnPFilterPnil 1); |
752 be ForallPForallQ 1; |
752 by (etac ForallPForallQ 1); |
753 auto(); |
753 by (Auto_tac()); |
754 qed"ForallQFilterPnil"; |
754 qed"ForallQFilterPnil"; |
755 |
755 |
756 goal thy "!! Q P. [| ~Finite ys; Forall Q ys; !!x. Q x ==> ~P x|] \ |
756 goal thy "!! Q P. [| ~Finite ys; Forall Q ys; !!x. Q x ==> ~P x|] \ |
757 \ ==> Filter P`ys = UU "; |
757 \ ==> Filter P`ys = UU "; |
758 be ForallnPFilterPUU 1; |
758 by (etac ForallnPFilterPUU 1); |
759 be ForallPForallQ 1; |
759 by (etac ForallPForallQ 1); |
760 auto(); |
760 by (Auto_tac()); |
761 qed"ForallQFilterPUU"; |
761 qed"ForallQFilterPUU"; |
762 |
762 |
763 |
763 |
764 |
764 |
765 (* ------------------------------------------------------------------------------------- *) |
765 (* ------------------------------------------------------------------------------------- *) |
771 by (simp_tac (!simpset addsimps [Forall_def,Takewhile_def,sforallPstakewhileP]) 1); |
771 by (simp_tac (!simpset addsimps [Forall_def,Takewhile_def,sforallPstakewhileP]) 1); |
772 qed"ForallPTakewhileP"; |
772 qed"ForallPTakewhileP"; |
773 |
773 |
774 |
774 |
775 goal thy"!! P. [| !!x. Q x==> P x |] ==> Forall P (Takewhile Q`x)"; |
775 goal thy"!! P. [| !!x. Q x==> P x |] ==> Forall P (Takewhile Q`x)"; |
776 br ForallPForallQ 1; |
776 by (rtac ForallPForallQ 1); |
777 br ForallPTakewhileP 1; |
777 by (rtac ForallPTakewhileP 1); |
778 auto(); |
778 by (Auto_tac()); |
779 qed"ForallPTakewhileQ"; |
779 qed"ForallPTakewhileQ"; |
780 |
780 |
781 |
781 |
782 goal thy "!! Q P.[| Finite (Takewhile Q`ys); !!x. Q x ==> ~P x |] \ |
782 goal thy "!! Q P.[| Finite (Takewhile Q`ys); !!x. Q x ==> ~P x |] \ |
783 \ ==> Filter P`(Takewhile Q`ys) = nil"; |
783 \ ==> Filter P`(Takewhile Q`ys) = nil"; |
784 be ForallnPFilterPnil 1; |
784 by (etac ForallnPFilterPnil 1); |
785 br ForallPForallQ 1; |
785 by (rtac ForallPForallQ 1); |
786 br ForallPTakewhileP 1; |
786 by (rtac ForallPTakewhileP 1); |
787 auto(); |
787 by (Auto_tac()); |
788 qed"FilterPTakewhileQnil"; |
788 qed"FilterPTakewhileQnil"; |
789 |
789 |
790 goal thy "!! Q P. [| !!x. Q x ==> P x |] ==> \ |
790 goal thy "!! Q P. [| !!x. Q x ==> P x |] ==> \ |
791 \ Filter P`(Takewhile Q`ys) = (Takewhile Q`ys)"; |
791 \ Filter P`(Takewhile Q`ys) = (Takewhile Q`ys)"; |
792 br ForallPFilterPid 1; |
792 by (rtac ForallPFilterPid 1); |
793 br ForallPForallQ 1; |
793 by (rtac ForallPForallQ 1); |
794 br ForallPTakewhileP 1; |
794 by (rtac ForallPTakewhileP 1); |
795 auto(); |
795 by (Auto_tac()); |
796 qed"FilterPTakewhileQid"; |
796 qed"FilterPTakewhileQid"; |
797 |
797 |
798 Addsimps [ForallPTakewhileP,ForallPTakewhileQ, |
798 Addsimps [ForallPTakewhileP,ForallPTakewhileQ, |
799 FilterPTakewhileQnil,FilterPTakewhileQid]; |
799 FilterPTakewhileQnil,FilterPTakewhileQid]; |
800 |
800 |
838 \ & Finite (Takewhile (%x. ~ P x)`y) & P x"; |
838 \ & Finite (Takewhile (%x. ~ P x)`y) & P x"; |
839 |
839 |
840 (* FIX: pay attention: is only admissible with chain-finite package to be added to |
840 (* FIX: pay attention: is only admissible with chain-finite package to be added to |
841 adm test *) |
841 adm test *) |
842 by (Seq_induct_tac "y" [] 1); |
842 by (Seq_induct_tac "y" [] 1); |
843 br adm_all 1; |
843 by (rtac adm_all 1); |
844 by (Asm_full_simp_tac 1); |
844 by (Asm_full_simp_tac 1); |
845 by (case_tac "P a" 1); |
845 by (case_tac "P a" 1); |
846 by (Asm_full_simp_tac 1); |
846 by (Asm_full_simp_tac 1); |
847 br impI 1; |
847 by (rtac impI 1); |
848 by (hyp_subst_tac 1); |
848 by (hyp_subst_tac 1); |
849 by (Asm_full_simp_tac 1); |
849 by (Asm_full_simp_tac 1); |
850 (* ~ P a *) |
850 (* ~ P a *) |
851 by (Asm_full_simp_tac 1); |
851 by (Asm_full_simp_tac 1); |
852 br impI 1; |
852 by (rtac impI 1); |
853 by (rotate_tac ~1 1); |
853 by (rotate_tac ~1 1); |
854 by (Asm_full_simp_tac 1); |
854 by (Asm_full_simp_tac 1); |
855 by (REPEAT (etac conjE 1)); |
855 by (REPEAT (etac conjE 1)); |
856 ba 1; |
856 by (assume_tac 1); |
857 qed"divide_Seq_lemma"; |
857 qed"divide_Seq_lemma"; |
858 |
858 |
859 goal thy "!! x. (x>>xs) << Filter P`y \ |
859 goal thy "!! x. (x>>xs) << Filter P`y \ |
860 \ ==> y = ((Takewhile (%a. ~ P a)`y) @@ (x >> TL`(Dropwhile (%a.~P a)`y))) \ |
860 \ ==> y = ((Takewhile (%a. ~ P a)`y) @@ (x >> TL`(Dropwhile (%a.~P a)`y))) \ |
861 \ & Finite (Takewhile (%a. ~ P a)`y) & P x"; |
861 \ & Finite (Takewhile (%a. ~ P a)`y) & P x"; |
862 br (divide_Seq_lemma RS mp) 1; |
862 by (rtac (divide_Seq_lemma RS mp) 1); |
863 by (dres_inst_tac [("fo","HD"),("xa","x>>xs")] monofun_cfun_arg 1); |
863 by (dres_inst_tac [("fo","HD"),("xa","x>>xs")] monofun_cfun_arg 1); |
864 by (Asm_full_simp_tac 1); |
864 by (Asm_full_simp_tac 1); |
865 qed"divide_Seq"; |
865 qed"divide_Seq"; |
866 |
866 |
867 |
867 |
868 goal thy "~Forall P y --> (? x. HD`(Filter (%a. ~P a)`y) = Def x)"; |
868 goal thy "~Forall P y --> (? x. HD`(Filter (%a. ~P a)`y) = Def x)"; |
869 (* FIX: pay attention: is only admissible with chain-finite package to be added to |
869 (* FIX: pay attention: is only admissible with chain-finite package to be added to |
870 adm test *) |
870 adm test *) |
871 by (Seq_induct_tac "y" [] 1); |
871 by (Seq_induct_tac "y" [] 1); |
872 br adm_all 1; |
872 by (rtac adm_all 1); |
873 by (case_tac "P a" 1); |
873 by (case_tac "P a" 1); |
874 by (Asm_full_simp_tac 1); |
874 by (Asm_full_simp_tac 1); |
875 by (Asm_full_simp_tac 1); |
875 by (Asm_full_simp_tac 1); |
876 qed"nForall_HDFilter"; |
876 qed"nForall_HDFilter"; |
877 |
877 |
878 |
878 |
879 goal thy "!!y. ~Forall P y \ |
879 goal thy "!!y. ~Forall P y \ |
880 \ ==> ? x. y= (Takewhile P`y @@ (x >> TL`(Dropwhile P`y))) & \ |
880 \ ==> ? x. y= (Takewhile P`y @@ (x >> TL`(Dropwhile P`y))) & \ |
881 \ Finite (Takewhile P`y) & (~ P x)"; |
881 \ Finite (Takewhile P`y) & (~ P x)"; |
882 bd (nForall_HDFilter RS mp) 1; |
882 by (dtac (nForall_HDFilter RS mp) 1); |
883 by (safe_tac set_cs); |
883 by (safe_tac set_cs); |
884 by (res_inst_tac [("x","x")] exI 1); |
884 by (res_inst_tac [("x","x")] exI 1); |
885 by (cut_inst_tac [("P1","%x. ~ P x")] (divide_Seq_lemma RS mp) 1); |
885 by (cut_inst_tac [("P1","%x. ~ P x")] (divide_Seq_lemma RS mp) 1); |
886 auto(); |
886 by (Auto_tac()); |
887 qed"divide_Seq2"; |
887 qed"divide_Seq2"; |
888 |
888 |
889 |
889 |
890 goal thy "!! y. ~Forall P y \ |
890 goal thy "!! y. ~Forall P y \ |
891 \ ==> ? x bs rs. y= (bs @@ (x>>rs)) & Finite bs & Forall P bs & (~ P x)"; |
891 \ ==> ? x bs rs. y= (bs @@ (x>>rs)) & Finite bs & Forall P bs & (~ P x)"; |
892 by (cut_inst_tac [] divide_Seq2 1); |
892 by (cut_inst_tac [] divide_Seq2 1); |
893 auto(); |
893 by (Auto_tac()); |
894 qed"divide_Seq3"; |
894 qed"divide_Seq3"; |
895 |
895 |
896 Addsimps [FilterPQ,FilterConc,Conc_cong]; |
896 Addsimps [FilterPQ,FilterConc,Conc_cong]; |
897 |
897 |
898 |
898 |
901 |
901 |
902 section "take_lemma"; |
902 section "take_lemma"; |
903 |
903 |
904 goal thy "(!n. seq_take n`x = seq_take n`x') = (x = x')"; |
904 goal thy "(!n. seq_take n`x = seq_take n`x') = (x = x')"; |
905 by (rtac iffI 1); |
905 by (rtac iffI 1); |
906 br seq.take_lemma 1; |
906 by (rtac seq.take_lemma 1); |
907 auto(); |
907 by (Auto_tac()); |
908 qed"seq_take_lemma"; |
908 qed"seq_take_lemma"; |
909 |
909 |
910 goal thy |
910 goal thy |
911 " ! n. ((! k. k < n --> seq_take k`y1 = seq_take k`y2) \ |
911 " ! n. ((! k. k < n --> seq_take k`y1 = seq_take k`y2) \ |
912 \ --> seq_take n`(x @@ (t>>y1)) = seq_take n`(x @@ (t>>y2)))"; |
912 \ --> seq_take n`(x @@ (t>>y1)) = seq_take n`(x @@ (t>>y2)))"; |
913 by (Seq_induct_tac "x" [] 1); |
913 by (Seq_induct_tac "x" [] 1); |
914 by (strip_tac 1); |
914 by (strip_tac 1); |
915 by (res_inst_tac [("n","n")] natE 1); |
915 by (res_inst_tac [("n","n")] natE 1); |
916 auto(); |
916 by (Auto_tac()); |
917 by (res_inst_tac [("n","n")] natE 1); |
917 by (res_inst_tac [("n","n")] natE 1); |
918 auto(); |
918 by (Auto_tac()); |
919 qed"take_reduction1"; |
919 qed"take_reduction1"; |
920 |
920 |
921 |
921 |
922 goal thy "!! n.[| x=y; s=t;!! k.k<n ==> seq_take k`y1 = seq_take k`y2|] \ |
922 goal thy "!! n.[| x=y; s=t;!! k.k<n ==> seq_take k`y1 = seq_take k`y2|] \ |
923 \ ==> seq_take n`(x @@ (s>>y1)) = seq_take n`(y @@ (t>>y2))"; |
923 \ ==> seq_take n`(x @@ (s>>y1)) = seq_take n`(y @@ (t>>y2))"; |
933 " ! n. ((! k. k < n --> seq_take k`y1 << seq_take k`y2) \ |
933 " ! n. ((! k. k < n --> seq_take k`y1 << seq_take k`y2) \ |
934 \ --> seq_take n`(x @@ (t>>y1)) << seq_take n`(x @@ (t>>y2)))"; |
934 \ --> seq_take n`(x @@ (t>>y1)) << seq_take n`(x @@ (t>>y2)))"; |
935 by (Seq_induct_tac "x" [] 1); |
935 by (Seq_induct_tac "x" [] 1); |
936 by (strip_tac 1); |
936 by (strip_tac 1); |
937 by (res_inst_tac [("n","n")] natE 1); |
937 by (res_inst_tac [("n","n")] natE 1); |
938 auto(); |
938 by (Auto_tac()); |
939 by (res_inst_tac [("n","n")] natE 1); |
939 by (res_inst_tac [("n","n")] natE 1); |
940 auto(); |
940 by (Auto_tac()); |
941 qed"take_reduction_less1"; |
941 qed"take_reduction_less1"; |
942 |
942 |
943 |
943 |
944 goal thy "!! n.[| x=y; s=t;!! k.k<n ==> seq_take k`y1 << seq_take k`y2|] \ |
944 goal thy "!! n.[| x=y; s=t;!! k.k<n ==> seq_take k`y1 << seq_take k`y2|] \ |
945 \ ==> seq_take n`(x @@ (s>>y1)) << seq_take n`(y @@ (t>>y2))"; |
945 \ ==> seq_take n`(x @@ (s>>y1)) << seq_take n`(y @@ (t>>y2))"; |
951 "(!! n. seq_take n`s1 << seq_take n`s2) ==> s1<<s2"; |
951 "(!! n. seq_take n`s1 << seq_take n`s2) ==> s1<<s2"; |
952 |
952 |
953 by (res_inst_tac [("t","s1")] (seq.reach RS subst) 1); |
953 by (res_inst_tac [("t","s1")] (seq.reach RS subst) 1); |
954 by (res_inst_tac [("t","s2")] (seq.reach RS subst) 1); |
954 by (res_inst_tac [("t","s2")] (seq.reach RS subst) 1); |
955 by (rtac (fix_def2 RS ssubst ) 1); |
955 by (rtac (fix_def2 RS ssubst ) 1); |
956 by (rtac (contlub_cfun_fun RS ssubst) 1); |
956 by (stac contlub_cfun_fun 1); |
957 by (rtac is_chain_iterate 1); |
957 by (rtac is_chain_iterate 1); |
958 by (rtac (contlub_cfun_fun RS ssubst) 1); |
958 by (stac contlub_cfun_fun 1); |
959 by (rtac is_chain_iterate 1); |
959 by (rtac is_chain_iterate 1); |
960 by (rtac lub_mono 1); |
960 by (rtac lub_mono 1); |
961 by (rtac (is_chain_iterate RS ch2ch_fappL) 1); |
961 by (rtac (is_chain_iterate RS ch2ch_fappL) 1); |
962 by (rtac (is_chain_iterate RS ch2ch_fappL) 1); |
962 by (rtac (is_chain_iterate RS ch2ch_fappL) 1); |
963 by (rtac allI 1); |
963 by (rtac allI 1); |
965 qed"take_lemma_less1"; |
965 qed"take_lemma_less1"; |
966 |
966 |
967 |
967 |
968 goal thy "(!n. seq_take n`x << seq_take n`x') = (x << x')"; |
968 goal thy "(!n. seq_take n`x << seq_take n`x') = (x << x')"; |
969 by (rtac iffI 1); |
969 by (rtac iffI 1); |
970 br take_lemma_less1 1; |
970 by (rtac take_lemma_less1 1); |
971 auto(); |
971 by (Auto_tac()); |
972 be monofun_cfun_arg 1; |
972 by (etac monofun_cfun_arg 1); |
973 qed"take_lemma_less"; |
973 qed"take_lemma_less"; |
974 |
974 |
975 (* ------------------------------------------------------------------ |
975 (* ------------------------------------------------------------------ |
976 take-lemma proof principles |
976 take-lemma proof principles |
977 ------------------------------------------------------------------ *) |
977 ------------------------------------------------------------------ *) |
989 \ ==> ! n. seq_take n`(f (s1 @@ y>>s2)) \ |
989 \ ==> ! n. seq_take n`(f (s1 @@ y>>s2)) \ |
990 \ = seq_take n`(g (s1 @@ y>>s2)) |] \ |
990 \ = seq_take n`(g (s1 @@ y>>s2)) |] \ |
991 \ ==> A x --> (f x)=(g x)"; |
991 \ ==> A x --> (f x)=(g x)"; |
992 by (case_tac "Forall Q x" 1); |
992 by (case_tac "Forall Q x" 1); |
993 by (auto_tac (!claset addSDs [divide_Seq3],!simpset)); |
993 by (auto_tac (!claset addSDs [divide_Seq3],!simpset)); |
994 br seq.take_lemma 1; |
994 by (rtac seq.take_lemma 1); |
995 auto(); |
995 by (Auto_tac()); |
996 qed"take_lemma_principle2"; |
996 qed"take_lemma_principle2"; |
997 |
997 |
998 |
998 |
999 (* Note: in the following proofs the ordering of proof steps is very |
999 (* Note: in the following proofs the ordering of proof steps is very |
1000 important, as otherwise either (Forall Q s1) would be in the IH as |
1000 important, as otherwise either (Forall Q s1) would be in the IH as |
1009 \ !! s1 s2 y n. [| ! t. A t --> seq_take n`(f t) = seq_take n`(g t);\ |
1009 \ !! s1 s2 y n. [| ! t. A t --> seq_take n`(f t) = seq_take n`(g t);\ |
1010 \ Forall Q s1; Finite s1; ~ Q y; A (s1 @@ y>>s2) |] \ |
1010 \ Forall Q s1; Finite s1; ~ Q y; A (s1 @@ y>>s2) |] \ |
1011 \ ==> seq_take (Suc n)`(f (s1 @@ y>>s2)) \ |
1011 \ ==> seq_take (Suc n)`(f (s1 @@ y>>s2)) \ |
1012 \ = seq_take (Suc n)`(g (s1 @@ y>>s2)) |] \ |
1012 \ = seq_take (Suc n)`(g (s1 @@ y>>s2)) |] \ |
1013 \ ==> A x --> (f x)=(g x)"; |
1013 \ ==> A x --> (f x)=(g x)"; |
1014 br impI 1; |
1014 by (rtac impI 1); |
1015 br seq.take_lemma 1; |
1015 by (rtac seq.take_lemma 1); |
1016 br mp 1; |
1016 by (rtac mp 1); |
1017 ba 2; |
1017 by (assume_tac 2); |
1018 by (res_inst_tac [("x","x")] spec 1); |
1018 by (res_inst_tac [("x","x")] spec 1); |
1019 br nat_induct 1; |
1019 by (rtac nat_induct 1); |
1020 by (Simp_tac 1); |
1020 by (Simp_tac 1); |
1021 br allI 1; |
1021 by (rtac allI 1); |
1022 by (case_tac "Forall Q xa" 1); |
1022 by (case_tac "Forall Q xa" 1); |
1023 by (SELECT_GOAL (auto_tac (!claset addSIs [seq_take_lemma RS iffD2 RS spec], |
1023 by (SELECT_GOAL (auto_tac (!claset addSIs [seq_take_lemma RS iffD2 RS spec], |
1024 !simpset)) 1); |
1024 !simpset)) 1); |
1025 by (auto_tac (!claset addSDs [divide_Seq3],!simpset)); |
1025 by (auto_tac (!claset addSDs [divide_Seq3],!simpset)); |
1026 qed"take_lemma_induct"; |
1026 qed"take_lemma_induct"; |
1031 \ !! s1 s2 y n. [| ! t m. m < n --> A t --> seq_take m`(f t) = seq_take m`(g t);\ |
1031 \ !! s1 s2 y n. [| ! t m. m < n --> A t --> seq_take m`(f t) = seq_take m`(g t);\ |
1032 \ Forall Q s1; Finite s1; ~ Q y; A (s1 @@ y>>s2) |] \ |
1032 \ Forall Q s1; Finite s1; ~ Q y; A (s1 @@ y>>s2) |] \ |
1033 \ ==> seq_take n`(f (s1 @@ y>>s2)) \ |
1033 \ ==> seq_take n`(f (s1 @@ y>>s2)) \ |
1034 \ = seq_take n`(g (s1 @@ y>>s2)) |] \ |
1034 \ = seq_take n`(g (s1 @@ y>>s2)) |] \ |
1035 \ ==> A x --> (f x)=(g x)"; |
1035 \ ==> A x --> (f x)=(g x)"; |
1036 br impI 1; |
1036 by (rtac impI 1); |
1037 br seq.take_lemma 1; |
1037 by (rtac seq.take_lemma 1); |
1038 br mp 1; |
1038 by (rtac mp 1); |
1039 ba 2; |
1039 by (assume_tac 2); |
1040 by (res_inst_tac [("x","x")] spec 1); |
1040 by (res_inst_tac [("x","x")] spec 1); |
1041 br less_induct 1; |
1041 by (rtac less_induct 1); |
1042 br allI 1; |
1042 by (rtac allI 1); |
1043 by (case_tac "Forall Q xa" 1); |
1043 by (case_tac "Forall Q xa" 1); |
1044 by (SELECT_GOAL (auto_tac (!claset addSIs [seq_take_lemma RS iffD2 RS spec], |
1044 by (SELECT_GOAL (auto_tac (!claset addSIs [seq_take_lemma RS iffD2 RS spec], |
1045 !simpset)) 1); |
1045 !simpset)) 1); |
1046 by (auto_tac (!claset addSDs [divide_Seq3],!simpset)); |
1046 by (auto_tac (!claset addSDs [divide_Seq3],!simpset)); |
1047 qed"take_lemma_less_induct"; |
1047 qed"take_lemma_less_induct"; |
1055 \ Forall Q s1; Finite s1; ~ Q y; A (s1 @@ y>>s2) h1 h2|] \ |
1055 \ Forall Q s1; Finite s1; ~ Q y; A (s1 @@ y>>s2) h1 h2|] \ |
1056 \ ==> seq_take n`(f (s1 @@ y>>s2) h1 h2) \ |
1056 \ ==> seq_take n`(f (s1 @@ y>>s2) h1 h2) \ |
1057 \ = seq_take n`(g (s1 @@ y>>s2) h1 h2) |] \ |
1057 \ = seq_take n`(g (s1 @@ y>>s2) h1 h2) |] \ |
1058 \ ==> ! h1 h2. (A x h1 h2) --> (f x h1 h2)=(g x h1 h2)"; |
1058 \ ==> ! h1 h2. (A x h1 h2) --> (f x h1 h2)=(g x h1 h2)"; |
1059 by (strip_tac 1); |
1059 by (strip_tac 1); |
1060 br seq.take_lemma 1; |
1060 by (rtac seq.take_lemma 1); |
1061 br mp 1; |
1061 by (rtac mp 1); |
1062 ba 2; |
1062 by (assume_tac 2); |
1063 by (res_inst_tac [("x","h2a")] spec 1); |
1063 by (res_inst_tac [("x","h2a")] spec 1); |
1064 by (res_inst_tac [("x","h1a")] spec 1); |
1064 by (res_inst_tac [("x","h1a")] spec 1); |
1065 by (res_inst_tac [("x","x")] spec 1); |
1065 by (res_inst_tac [("x","x")] spec 1); |
1066 br less_induct 1; |
1066 by (rtac less_induct 1); |
1067 br allI 1; |
1067 by (rtac allI 1); |
1068 by (case_tac "Forall Q xa" 1); |
1068 by (case_tac "Forall Q xa" 1); |
1069 by (SELECT_GOAL (auto_tac (!claset addSIs [seq_take_lemma RS iffD2 RS spec], |
1069 by (SELECT_GOAL (auto_tac (!claset addSIs [seq_take_lemma RS iffD2 RS spec], |
1070 !simpset)) 1); |
1070 !simpset)) 1); |
1071 by (auto_tac (!claset addSDs [divide_Seq3],!simpset)); |
1071 by (auto_tac (!claset addSDs [divide_Seq3],!simpset)); |
1072 qed"take_lemma_less_induct"; |
1072 qed"take_lemma_less_induct"; |
1081 \ = seq_take n`(g (s1 @@ y>>s2))) |] \ |
1081 \ = seq_take n`(g (s1 @@ y>>s2))) |] \ |
1082 \ ==> P ((f x)=(g x))"; |
1082 \ ==> P ((f x)=(g x))"; |
1083 |
1083 |
1084 by (res_inst_tac [("t","f x = g x"), |
1084 by (res_inst_tac [("t","f x = g x"), |
1085 ("s","!n. seq_take n`(f x) = seq_take n`(g x)")] subst 1); |
1085 ("s","!n. seq_take n`(f x) = seq_take n`(g x)")] subst 1); |
1086 br seq_take_lemma 1; |
1086 by (rtac seq_take_lemma 1); |
1087 |
1087 |
1088 wie ziehe ich n durch P, d.h. evtl. ns in P muessen umbenannt werden..... |
1088 wie ziehe ich n durch P, d.h. evtl. ns in P muessen umbenannt werden..... |
1089 |
1089 |
1090 |
1090 |
1091 FIX |
1091 FIX |
1092 |
1092 |
1093 br less_induct 1; |
1093 by (rtac less_induct 1); |
1094 br allI 1; |
1094 by (rtac allI 1); |
1095 by (case_tac "Forall Q xa" 1); |
1095 by (case_tac "Forall Q xa" 1); |
1096 by (SELECT_GOAL (auto_tac (!claset addSIs [seq_take_lemma RS iffD2 RS spec], |
1096 by (SELECT_GOAL (auto_tac (!claset addSIs [seq_take_lemma RS iffD2 RS spec], |
1097 !simpset)) 1); |
1097 !simpset)) 1); |
1098 by (auto_tac (!claset addSDs [divide_Seq3],!simpset)); |
1098 by (auto_tac (!claset addSDs [divide_Seq3],!simpset)); |
1099 qed"take_lemma_less_induct"; |
1099 qed"take_lemma_less_induct"; |
1108 \ !! s y n. [| ! t. A t --> seq_take n`(f t) = seq_take n`(g t);\ |
1108 \ !! s y n. [| ! t. A t --> seq_take n`(f t) = seq_take n`(g t);\ |
1109 \ A (y>>s) |] \ |
1109 \ A (y>>s) |] \ |
1110 \ ==> seq_take (Suc n)`(f (y>>s)) \ |
1110 \ ==> seq_take (Suc n)`(f (y>>s)) \ |
1111 \ = seq_take (Suc n)`(g (y>>s)) |] \ |
1111 \ = seq_take (Suc n)`(g (y>>s)) |] \ |
1112 \ ==> A x --> (f x)=(g x)"; |
1112 \ ==> A x --> (f x)=(g x)"; |
1113 br impI 1; |
1113 by (rtac impI 1); |
1114 br seq.take_lemma 1; |
1114 by (rtac seq.take_lemma 1); |
1115 br mp 1; |
1115 by (rtac mp 1); |
1116 ba 2; |
1116 by (assume_tac 2); |
1117 by (res_inst_tac [("x","x")] spec 1); |
1117 by (res_inst_tac [("x","x")] spec 1); |
1118 br nat_induct 1; |
1118 by (rtac nat_induct 1); |
1119 by (Simp_tac 1); |
1119 by (Simp_tac 1); |
1120 br allI 1; |
1120 by (rtac allI 1); |
1121 by (Seq_case_simp_tac "xa" 1); |
1121 by (Seq_case_simp_tac "xa" 1); |
1122 qed"take_lemma_in_eq_out"; |
1122 qed"take_lemma_in_eq_out"; |
1123 |
1123 |
1124 |
1124 |
1125 (* ------------------------------------------------------------------------------------ *) |
1125 (* ------------------------------------------------------------------------------------ *) |