src/HOLCF/IOA/meta_theory/Sequence.ML
changeset 3457 a8ab7c64817c
parent 3433 2de17c994071
child 3461 7bf1e7c40a0c
equal deleted inserted replaced
3456:fdb1768ebd3e 3457:a8ab7c64817c
    11 
    11 
    12 goal thy "!! P. [| adm (%x. P x --> Q x); adm (%x.Q x --> P x) |] \
    12 goal thy "!! P. [| adm (%x. P x --> Q x); adm (%x.Q x --> P x) |] \
    13 \           ==> adm (%x. P x = Q x)";
    13 \           ==> adm (%x. P x = Q x)";
    14 by (res_inst_tac [("P2","(%x.(P x --> Q x) & (Q x --> P x))")] (adm_cong RS iffD1) 1);
    14 by (res_inst_tac [("P2","(%x.(P x --> Q x) & (Q x --> P x))")] (adm_cong RS iffD1) 1);
    15 by (Fast_tac 1);
    15 by (Fast_tac 1);
    16 be adm_conj 1;
    16 by (etac adm_conj 1);
    17 ba 1;
    17 by (assume_tac 1);
    18 qed"adm_iff";
    18 qed"adm_iff";
    19 
    19 
    20 Addsimps [adm_iff];
    20 Addsimps [adm_iff];
    21 
    21 
    22 
    22 
   167 \                                      Undef  => UU \
   167 \                                      Undef  => UU \
   168 \                                    | Def a => (case y of \
   168 \                                    | Def a => (case y of \
   169 \                                                  Undef => UU \
   169 \                                                  Undef => UU \
   170 \                                                | Def b => Def (a,b)##(Zip`xs`ys)))))";
   170 \                                                | Def b => Def (a,b)##(Zip`xs`ys)))))";
   171 by (rtac trans 1);
   171 by (rtac trans 1);
   172 br fix_eq2 1;
   172 by (rtac fix_eq2 1);
   173 br Zip_def 1;
   173 by (rtac Zip_def 1);
   174 br beta_cfun 1;
   174 by (rtac beta_cfun 1);
   175 by (Simp_tac 1);
   175 by (Simp_tac 1);
   176 qed"Zip_unfold";
   176 qed"Zip_unfold";
   177 
   177 
   178 goal thy "Zip`UU`y =UU";
   178 goal thy "Zip`UU`y =UU";
   179 by (stac Zip_unfold 1);
   179 by (stac Zip_unfold 1);
   196 by (stac Zip_unfold 1);
   196 by (stac Zip_unfold 1);
   197 by (simp_tac (!simpset addsimps [Cons_def]) 1);
   197 by (simp_tac (!simpset addsimps [Cons_def]) 1);
   198 qed"Zip_cons_nil";
   198 qed"Zip_cons_nil";
   199 
   199 
   200 goal thy "Zip`(x>>xs)`(y>>ys)= (x,y) >> Zip`xs`ys"; 
   200 goal thy "Zip`(x>>xs)`(y>>ys)= (x,y) >> Zip`xs`ys"; 
   201 br trans 1;
   201 by (rtac trans 1);
   202 by (stac Zip_unfold 1);
   202 by (stac Zip_unfold 1);
   203 by (Simp_tac 1);
   203 by (Simp_tac 1);
   204 (* FIX: Why Simp_tac 2 times. Does continuity in simpflication make job sometimes not 
   204 (* FIX: Why Simp_tac 2 times. Does continuity in simpflication make job sometimes not 
   205   completely ready ? *)
   205   completely ready ? *)
   206 by (simp_tac (!simpset addsimps [Cons_def]) 1);
   206 by (simp_tac (!simpset addsimps [Cons_def]) 1);
   234 goal thy "Filter2 P = (LAM tr. case tr of  \
   234 goal thy "Filter2 P = (LAM tr. case tr of  \
   235  \         nil   => nil \
   235  \         nil   => nil \
   236  \       | x##xs => (case x of Undef => UU | Def y => \
   236  \       | x##xs => (case x of Undef => UU | Def y => \
   237 \                   (if P y then y>>(Filter2 P`xs) else Filter2 P`xs)))";
   237 \                   (if P y then y>>(Filter2 P`xs) else Filter2 P`xs)))";
   238 by (rtac trans 1);
   238 by (rtac trans 1);
   239 br fix_eq2 1;
   239 by (rtac fix_eq2 1);
   240 br Filter2_def 1;
   240 by (rtac Filter2_def 1);
   241 br beta_cfun 1;
   241 by (rtac beta_cfun 1);
   242 by (Simp_tac 1);
   242 by (Simp_tac 1);
   243 
   243 
   244 is also possible, if then else has to be proven continuous and it would be nice if a case for 
   244 is also possible, if then else has to be proven continuous and it would be nice if a case for 
   245 Seq would be available.
   245 Seq would be available.
   246 
   246 
   263 qed"Seq_exhaust";
   263 qed"Seq_exhaust";
   264 
   264 
   265 
   265 
   266 goal thy "!!P. [| x = UU ==> P; x = nil ==> P; !!a s. x = a >> s  ==> P |] ==> P";
   266 goal thy "!!P. [| x = UU ==> P; x = nil ==> P; !!a s. x = a >> s  ==> P |] ==> P";
   267 by (cut_inst_tac [("x","x")] Seq_exhaust 1);
   267 by (cut_inst_tac [("x","x")] Seq_exhaust 1);
   268 be disjE 1;
   268 by (etac disjE 1);
   269 by (Asm_full_simp_tac 1);
   269 by (Asm_full_simp_tac 1);
   270 be disjE 1;
   270 by (etac disjE 1);
   271 by (Asm_full_simp_tac 1);
   271 by (Asm_full_simp_tac 1);
   272 by (REPEAT (etac exE 1));
   272 by (REPEAT (etac exE 1));
   273 by (Asm_full_simp_tac 1);
   273 by (Asm_full_simp_tac 1);
   274 qed"Seq_cases";
   274 qed"Seq_cases";
   275 
   275 
   282                                              THEN Asm_full_simp_tac i;
   282                                              THEN Asm_full_simp_tac i;
   283 
   283 
   284 goal thy "a>>s ~= UU";
   284 goal thy "a>>s ~= UU";
   285 by (stac Cons_def2 1);
   285 by (stac Cons_def2 1);
   286 by (resolve_tac seq.con_rews 1);
   286 by (resolve_tac seq.con_rews 1);
   287 br Def_not_UU 1;
   287 by (rtac Def_not_UU 1);
   288 qed"Cons_not_UU";
   288 qed"Cons_not_UU";
   289 
   289 
   290 
   290 
   291 goal thy "~(a>>x) << UU";
   291 goal thy "~(a>>x) << UU";
   292 by (rtac notI 1);
   292 by (rtac notI 1);
   296 qed"Cons_not_less_UU";
   296 qed"Cons_not_less_UU";
   297 
   297 
   298 goal thy "~a>>s << nil";
   298 goal thy "~a>>s << nil";
   299 by (stac Cons_def2 1);
   299 by (stac Cons_def2 1);
   300 by (resolve_tac seq.rews 1);
   300 by (resolve_tac seq.rews 1);
   301 br Def_not_UU 1;
   301 by (rtac Def_not_UU 1);
   302 qed"Cons_not_less_nil";
   302 qed"Cons_not_less_nil";
   303 
   303 
   304 goal thy "a>>s ~= nil";
   304 goal thy "a>>s ~= nil";
   305 by (stac Cons_def2 1);
   305 by (stac Cons_def2 1);
   306 by (resolve_tac seq.rews 1);
   306 by (resolve_tac seq.rews 1);
   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 
   440 by (Asm_full_simp_tac 1);
   440 by (Asm_full_simp_tac 1);
   441 qed"FiniteConc_2";
   441 qed"FiniteConc_2";
   442 
   442 
   443 goal thy "Finite(x@@y) = (Finite (x::'a Seq) & Finite y)";
   443 goal thy "Finite(x@@y) = (Finite (x::'a Seq) & Finite y)";
   444 by (rtac iffI 1);
   444 by (rtac iffI 1);
   445 be (FiniteConc_2 RS spec RS spec RS mp) 1;
   445 by (etac (FiniteConc_2 RS spec RS spec RS mp) 1);
   446 br refl 1;
   446 by (rtac refl 1);
   447 br (FiniteConc_1 RS mp) 1;
   447 by (rtac (FiniteConc_1 RS mp) 1);
   448 auto();
   448 by (Auto_tac());
   449 qed"FiniteConc";
   449 qed"FiniteConc";
   450 
   450 
   451 Addsimps [FiniteConc];
   451 Addsimps [FiniteConc];
   452 
   452 
   453 
   453 
   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 
   541 Addsimps [nilConc];
   541 Addsimps [nilConc];
   542 
   542 
   543 (* FIX: should be same as nil_is_Conc2 when all nils are turned to right side !! *)
   543 (* FIX: should be same as nil_is_Conc2 when all nils are turned to right side !! *)
   544 goal thy "(nil = x @@ y) = ((x::'a Seq)= nil & y = nil)";
   544 goal thy "(nil = x @@ y) = ((x::'a Seq)= nil & y = nil)";
   545 by (Seq_case_simp_tac "x" 1);
   545 by (Seq_case_simp_tac "x" 1);
   546 auto();
   546 by (Auto_tac());
   547 qed"nil_is_Conc";
   547 qed"nil_is_Conc";
   548 
   548 
   549 goal thy "(x @@ y = nil) = ((x::'a Seq)= nil & y = nil)";
   549 goal thy "(x @@ y = nil) = ((x::'a Seq)= nil & y = nil)";
   550 by (Seq_case_simp_tac "x" 1);
   550 by (Seq_case_simp_tac "x" 1);
   551 auto();
   551 by (Auto_tac());
   552 qed"nil_is_Conc2";
   552 qed"nil_is_Conc2";
   553 
   553 
   554 
   554 
   555 (* ------------------------------------------------------------------------------------ *)
   555 (* ------------------------------------------------------------------------------------ *)
   556 
   556 
   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);
   713 goal thy "!! ys . Filter P`ys = nil --> \
   713 goal thy "!! ys . Filter P`ys = nil --> \
   714 \   (Forall (%x. ~P x) ys & Finite ys)";
   714 \   (Forall (%x. ~P x) ys & Finite ys)";
   715 by (res_inst_tac[("x","ys")] Seq_induct 1);
   715 by (res_inst_tac[("x","ys")] Seq_induct 1);
   716 (* adm *)
   716 (* adm *)
   717 (* FIX: not admissible, search other proof!! *)
   717 (* FIX: not admissible, search other proof!! *)
   718 br adm_all 1;
   718 by (rtac adm_all 1);
   719 (* base cases *)
   719 (* base cases *)
   720 by (Simp_tac 1);
   720 by (Simp_tac 1);
   721 by (Simp_tac 1);
   721 by (Simp_tac 1);
   722 (* main case *)
   722 (* main case *)
   723 by (asm_full_simp_tac (!simpset setloop split_tac [expand_if] ) 1);
   723 by (asm_full_simp_tac (!simpset setloop split_tac [expand_if] ) 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 (* ------------------------------------------------------------------------------------ *)
  1179 
  1179 
  1180 
  1180 
  1181 
  1181 
  1182 goal thy "Map f`(x@@y) = (Map f`x) @@ (Map f`y)";
  1182 goal thy "Map f`(x@@y) = (Map f`x) @@ (Map f`y)";
  1183 by (res_inst_tac [("A1","%x.True"),("x1","x")] (take_lemma_in_eq_out RS mp) 1);
  1183 by (res_inst_tac [("A1","%x.True"),("x1","x")] (take_lemma_in_eq_out RS mp) 1);
  1184 auto();
  1184 by (Auto_tac());
  1185 qed"MapConc_takelemma";
  1185 qed"MapConc_takelemma";
  1186 
  1186 
  1187 
  1187