src/HOL/Quotient_Examples/FSet.thy
changeset 55945 e96383acecf9
parent 55584 a879f14b6f95
child 57816 d8bbb97689d3
equal deleted inserted replaced
55944:7ab8f003fe41 55945:e96383acecf9
   401   shows "(list_all2 op \<approx> OOO op \<approx>) Nil Nil"
   401   shows "(list_all2 op \<approx> OOO op \<approx>) Nil Nil"
   402   by (rule compose_list_refl, rule list_eq_equivp)
   402   by (rule compose_list_refl, rule list_eq_equivp)
   403 
   403 
   404 lemma Cons_rsp2 [quot_respect]:
   404 lemma Cons_rsp2 [quot_respect]:
   405   shows "(op \<approx> ===> list_all2 op \<approx> OOO op \<approx> ===> list_all2 op \<approx> OOO op \<approx>) Cons Cons"
   405   shows "(op \<approx> ===> list_all2 op \<approx> OOO op \<approx> ===> list_all2 op \<approx> OOO op \<approx>) Cons Cons"
   406   apply (auto intro!: fun_relI)
   406   apply (auto intro!: rel_funI)
   407   apply (rule_tac b="x # b" in relcomppI)
   407   apply (rule_tac b="x # b" in relcomppI)
   408   apply auto
   408   apply auto
   409   apply (rule_tac b="x # ba" in relcomppI)
   409   apply (rule_tac b="x # ba" in relcomppI)
   410   apply auto
   410   apply auto
   411   done
   411   done
   457   using assms by (rule list_all2_appendI)
   457   using assms by (rule list_all2_appendI)
   458 
   458 
   459 lemma compositional_rsp3:
   459 lemma compositional_rsp3:
   460   assumes "(R1 ===> R2 ===> R3) C C" and "(R4 ===> R5 ===> R6) C C"
   460   assumes "(R1 ===> R2 ===> R3) C C" and "(R4 ===> R5 ===> R6) C C"
   461   shows "(R1 OOO R4 ===> R2 OOO R5 ===> R3 OOO R6) C C"
   461   shows "(R1 OOO R4 ===> R2 OOO R5 ===> R3 OOO R6) C C"
   462   by (auto intro!: fun_relI)
   462   by (auto intro!: rel_funI)
   463      (metis (full_types) assms fun_relE relcomppI)
   463      (metis (full_types) assms rel_funE relcomppI)
   464 
   464 
   465 lemma append_rsp2 [quot_respect]:
   465 lemma append_rsp2 [quot_respect]:
   466   "(list_all2 op \<approx> OOO op \<approx> ===> list_all2 op \<approx> OOO op \<approx> ===> list_all2 op \<approx> OOO op \<approx>) append append"
   466   "(list_all2 op \<approx> OOO op \<approx> ===> list_all2 op \<approx> OOO op \<approx> ===> list_all2 op \<approx> OOO op \<approx>) append append"
   467   by (intro compositional_rsp3)
   467   by (intro compositional_rsp3)
   468      (auto intro!: fun_relI simp add: append_rsp2_pre)
   468      (auto intro!: rel_funI simp add: append_rsp2_pre)
   469 
   469 
   470 lemma map_rsp2 [quot_respect]:
   470 lemma map_rsp2 [quot_respect]:
   471   "((op \<approx> ===> op \<approx>) ===> list_all2 op \<approx> OOO op \<approx> ===> list_all2 op \<approx> OOO op \<approx>) map map"
   471   "((op \<approx> ===> op \<approx>) ===> list_all2 op \<approx> OOO op \<approx> ===> list_all2 op \<approx> OOO op \<approx>) map map"
   472 proof (auto intro!: fun_relI)
   472 proof (auto intro!: rel_funI)
   473   fix f f' :: "'a list \<Rightarrow> 'b list"
   473   fix f f' :: "'a list \<Rightarrow> 'b list"
   474   fix xa ya x y :: "'a list list"
   474   fix xa ya x y :: "'a list list"
   475   assume fs: "(op \<approx> ===> op \<approx>) f f'" and x: "list_all2 op \<approx> xa x" and xy: "set x = set y" and y: "list_all2 op \<approx> y ya"
   475   assume fs: "(op \<approx> ===> op \<approx>) f f'" and x: "list_all2 op \<approx> xa x" and xy: "set x = set y" and y: "list_all2 op \<approx> y ya"
   476   have a: "(list_all2 op \<approx>) (map f xa) (map f x)"
   476   have a: "(list_all2 op \<approx>) (map f xa) (map f x)"
   477     using x
   477     using x
   478     by (induct xa x rule: list_induct2')
   478     by (induct xa x rule: list_induct2')
   479        (simp_all, metis fs fun_relE list_eq_def)
   479        (simp_all, metis fs rel_funE list_eq_def)
   480   have b: "set (map f x) = set (map f y)"
   480   have b: "set (map f x) = set (map f y)"
   481     using xy fs
   481     using xy fs
   482     by (induct x y rule: list_induct2')
   482     by (induct x y rule: list_induct2')
   483        (simp_all, metis image_insert)
   483        (simp_all, metis image_insert)
   484   have c: "(list_all2 op \<approx>) (map f y) (map f' ya)"
   484   have c: "(list_all2 op \<approx>) (map f y) (map f' ya)"