src/HOL/HOLCF/IOA/meta_theory/Sequence.thy
changeset 62000 8cba509ace9c
parent 61424 c3658c18b7bc
child 62001 1f2788fb0b8b
equal deleted inserted replaced
61999:89291b5d0ede 62000:8cba509ace9c
   790 subsection "coinductive characterizations of Filter"
   790 subsection "coinductive characterizations of Filter"
   791 
   791 
   792 
   792 
   793 lemma divide_Seq_lemma:
   793 lemma divide_Seq_lemma:
   794  "HD$(Filter P$y) = Def x
   794  "HD$(Filter P$y) = Def x
   795     --> y = ((Takewhile (%x. ~P x)$y) @@ (x >> TL$(Dropwhile (%a.~P a)$y))) 
   795     --> y = ((Takewhile (%x. ~P x)$y) @@ (x >> TL$(Dropwhile (%a. ~P a)$y)))
   796              & Finite (Takewhile (%x. ~ P x)$y)  & P x"
   796              & Finite (Takewhile (%x. ~ P x)$y)  & P x"
   797 
   797 
   798 (* FIX: pay attention: is only admissible with chain-finite package to be added to
   798 (* FIX: pay attention: is only admissible with chain-finite package to be added to
   799         adm test and Finite f x admissibility *)
   799         adm test and Finite f x admissibility *)
   800 apply (rule_tac x="y" in Seq_induct)
   800 apply (rule_tac x="y" in Seq_induct)
   807 (* ~ P a *)
   807 (* ~ P a *)
   808 apply simp
   808 apply simp
   809 done
   809 done
   810 
   810 
   811 lemma divide_Seq: "(x>>xs) << Filter P$y 
   811 lemma divide_Seq: "(x>>xs) << Filter P$y 
   812    ==> y = ((Takewhile (%a. ~ P a)$y) @@ (x >> TL$(Dropwhile (%a.~P a)$y)))
   812    ==> y = ((Takewhile (%a. ~ P a)$y) @@ (x >> TL$(Dropwhile (%a. ~ P a)$y)))
   813       & Finite (Takewhile (%a. ~ P a)$y)  & P x"
   813       & Finite (Takewhile (%a. ~ P a)$y)  & P x"
   814 apply (rule divide_Seq_lemma [THEN mp])
   814 apply (rule divide_Seq_lemma [THEN mp])
   815 apply (drule_tac f="HD" and x="x>>xs" in  monofun_cfun_arg)
   815 apply (drule_tac f="HD" and x="x>>xs" in  monofun_cfun_arg)
   816 apply simp
   816 apply simp
   817 done
   817 done
  1028 declare FilterPQ [simp del]
  1028 declare FilterPQ [simp del]
  1029 
  1029 
  1030 
  1030 
  1031 (* In general: How to do this case without the same adm problems
  1031 (* In general: How to do this case without the same adm problems
  1032    as for the entire proof ? *)
  1032    as for the entire proof ? *)
  1033 lemma Filter_lemma1: "Forall (%x.~(P x & Q x)) s
  1033 lemma Filter_lemma1: "Forall (%x. ~(P x & Q x)) s
  1034           --> Filter P$(Filter Q$s) =
  1034           --> Filter P$(Filter Q$s) =
  1035               Filter (%x. P x & Q x)$s"
  1035               Filter (%x. P x & Q x)$s"
  1036 
  1036 
  1037 apply (rule_tac x="s" in Seq_induct)
  1037 apply (rule_tac x="s" in Seq_induct)
  1038 apply (simp add: Forall_def sforall_def)
  1038 apply (simp add: Forall_def sforall_def)
  1052 done
  1052 done
  1053 
  1053 
  1054 
  1054 
  1055 lemma FilterPQ_takelemma: "Filter P$(Filter Q$s) = Filter (%x. P x & Q x)$s"
  1055 lemma FilterPQ_takelemma: "Filter P$(Filter Q$s) = Filter (%x. P x & Q x)$s"
  1056 apply (rule_tac A1="%x. True" and
  1056 apply (rule_tac A1="%x. True" and
  1057                  Q1="%x.~(P x & Q x)" and x1="s" in
  1057                  Q1="%x. ~(P x & Q x)" and x1="s" in
  1058                  take_lemma_induct [THEN mp])
  1058                  take_lemma_induct [THEN mp])
  1059 (* better support for A = %x. True *)
  1059 (* better support for A = %x. True *)
  1060 apply (simp add: Filter_lemma1)
  1060 apply (simp add: Filter_lemma1)
  1061 apply (simp add: Filter_lemma2 Filter_lemma3)
  1061 apply (simp add: Filter_lemma2 Filter_lemma3)
  1062 apply simp
  1062 apply simp