src/HOL/Lifting_Set.thy
changeset 67399 eab6ce8368fa
parent 64272 f76b6dda2e56
child 68521 1bad08165162
equal deleted inserted replaced
67398:5eb932e604a2 67399:eab6ce8368fa
    15   by (simp_all add: rel_set_def)
    15   by (simp_all add: rel_set_def)
    16 
    16 
    17 lemma rel_set_conversep [simp]: "rel_set A\<inverse>\<inverse> = (rel_set A)\<inverse>\<inverse>"
    17 lemma rel_set_conversep [simp]: "rel_set A\<inverse>\<inverse> = (rel_set A)\<inverse>\<inverse>"
    18   unfolding rel_set_def by auto
    18   unfolding rel_set_def by auto
    19 
    19 
    20 lemma rel_set_eq [relator_eq]: "rel_set (op =) = (op =)"
    20 lemma rel_set_eq [relator_eq]: "rel_set (=) = (=)"
    21   unfolding rel_set_def fun_eq_iff by auto
    21   unfolding rel_set_def fun_eq_iff by auto
    22 
    22 
    23 lemma rel_set_mono[relator_mono]:
    23 lemma rel_set_mono[relator_mono]:
    24   assumes "A \<le> B"
    24   assumes "A \<le> B"
    25   shows "rel_set A \<le> rel_set B"
    25   shows "rel_set A \<le> rel_set B"
   137 lemma UNION_transfer [transfer_rule]:
   137 lemma UNION_transfer [transfer_rule]:
   138   "(rel_set A ===> (A ===> rel_set B) ===> rel_set B) UNION UNION"
   138   "(rel_set A ===> (A ===> rel_set B) ===> rel_set B) UNION UNION"
   139   by transfer_prover
   139   by transfer_prover
   140 
   140 
   141 lemma Ball_transfer [transfer_rule]:
   141 lemma Ball_transfer [transfer_rule]:
   142   "(rel_set A ===> (A ===> op =) ===> op =) Ball Ball"
   142   "(rel_set A ===> (A ===> (=)) ===> (=)) Ball Ball"
   143   unfolding rel_set_def rel_fun_def by fast
   143   unfolding rel_set_def rel_fun_def by fast
   144 
   144 
   145 lemma Bex_transfer [transfer_rule]:
   145 lemma Bex_transfer [transfer_rule]:
   146   "(rel_set A ===> (A ===> op =) ===> op =) Bex Bex"
   146   "(rel_set A ===> (A ===> (=)) ===> (=)) Bex Bex"
   147   unfolding rel_set_def rel_fun_def by fast
   147   unfolding rel_set_def rel_fun_def by fast
   148 
   148 
   149 lemma Pow_transfer [transfer_rule]:
   149 lemma Pow_transfer [transfer_rule]:
   150   "(rel_set A ===> rel_set (rel_set A)) Pow Pow"
   150   "(rel_set A ===> rel_set (rel_set A)) Pow Pow"
   151   apply (rule rel_funI)
   151   apply (rule rel_funI)
   163     apply fast
   163     apply fast
   164     done
   164     done
   165   done
   165   done
   166 
   166 
   167 lemma rel_set_transfer [transfer_rule]:
   167 lemma rel_set_transfer [transfer_rule]:
   168   "((A ===> B ===> op =) ===> rel_set A ===> rel_set B ===> op =) rel_set rel_set"
   168   "((A ===> B ===> (=)) ===> rel_set A ===> rel_set B ===> (=)) rel_set rel_set"
   169   unfolding rel_fun_def rel_set_def by fast
   169   unfolding rel_fun_def rel_set_def by fast
   170 
   170 
   171 lemma bind_transfer [transfer_rule]:
   171 lemma bind_transfer [transfer_rule]:
   172   "(rel_set A ===> (A ===> rel_set B) ===> rel_set B) Set.bind Set.bind"
   172   "(rel_set A ===> (A ===> rel_set B) ===> rel_set B) Set.bind Set.bind"
   173   unfolding bind_UNION [abs_def] by transfer_prover
   173   unfolding bind_UNION [abs_def] by transfer_prover
   183 
   183 
   184 subsubsection \<open>Rules requiring bi-unique, bi-total or right-total relations\<close>
   184 subsubsection \<open>Rules requiring bi-unique, bi-total or right-total relations\<close>
   185 
   185 
   186 lemma member_transfer [transfer_rule]:
   186 lemma member_transfer [transfer_rule]:
   187   assumes "bi_unique A"
   187   assumes "bi_unique A"
   188   shows "(A ===> rel_set A ===> op =) (op \<in>) (op \<in>)"
   188   shows "(A ===> rel_set A ===> (=)) (\<in>) (\<in>)"
   189   using assms unfolding rel_fun_def rel_set_def bi_unique_def by fast
   189   using assms unfolding rel_fun_def rel_set_def bi_unique_def by fast
   190 
   190 
   191 lemma right_total_Collect_transfer[transfer_rule]:
   191 lemma right_total_Collect_transfer[transfer_rule]:
   192   assumes "right_total A"
   192   assumes "right_total A"
   193   shows "((A ===> op =) ===> rel_set A) (\<lambda>P. Collect (\<lambda>x. P x \<and> Domainp A x)) Collect"
   193   shows "((A ===> (=)) ===> rel_set A) (\<lambda>P. Collect (\<lambda>x. P x \<and> Domainp A x)) Collect"
   194   using assms unfolding right_total_def rel_set_def rel_fun_def Domainp_iff by fast
   194   using assms unfolding right_total_def rel_set_def rel_fun_def Domainp_iff by fast
   195 
   195 
   196 lemma Collect_transfer [transfer_rule]:
   196 lemma Collect_transfer [transfer_rule]:
   197   assumes "bi_total A"
   197   assumes "bi_total A"
   198   shows "((A ===> op =) ===> rel_set A) Collect Collect"
   198   shows "((A ===> (=)) ===> rel_set A) Collect Collect"
   199   using assms unfolding rel_fun_def rel_set_def bi_total_def by fast
   199   using assms unfolding rel_fun_def rel_set_def bi_total_def by fast
   200 
   200 
   201 lemma inter_transfer [transfer_rule]:
   201 lemma inter_transfer [transfer_rule]:
   202   assumes "bi_unique A"
   202   assumes "bi_unique A"
   203   shows "(rel_set A ===> rel_set A ===> rel_set A) inter inter"
   203   shows "(rel_set A ===> rel_set A ===> rel_set A) inter inter"
   204   using assms unfolding rel_fun_def rel_set_def bi_unique_def by fast
   204   using assms unfolding rel_fun_def rel_set_def bi_unique_def by fast
   205 
   205 
   206 lemma Diff_transfer [transfer_rule]:
   206 lemma Diff_transfer [transfer_rule]:
   207   assumes "bi_unique A"
   207   assumes "bi_unique A"
   208   shows "(rel_set A ===> rel_set A ===> rel_set A) (op -) (op -)"
   208   shows "(rel_set A ===> rel_set A ===> rel_set A) (-) (-)"
   209   using assms unfolding rel_fun_def rel_set_def bi_unique_def
   209   using assms unfolding rel_fun_def rel_set_def bi_unique_def
   210   unfolding Ball_def Bex_def Diff_eq
   210   unfolding Ball_def Bex_def Diff_eq
   211   by (safe, simp, metis, simp, metis)
   211   by (safe, simp, metis, simp, metis)
   212 
   212 
   213 lemma subset_transfer [transfer_rule]:
   213 lemma subset_transfer [transfer_rule]:
   214   assumes [transfer_rule]: "bi_unique A"
   214   assumes [transfer_rule]: "bi_unique A"
   215   shows "(rel_set A ===> rel_set A ===> op =) (op \<subseteq>) (op \<subseteq>)"
   215   shows "(rel_set A ===> rel_set A ===> (=)) (\<subseteq>) (\<subseteq>)"
   216   unfolding subset_eq [abs_def] by transfer_prover
   216   unfolding subset_eq [abs_def] by transfer_prover
   217 
   217 
   218 declare right_total_UNIV_transfer[transfer_rule]
   218 declare right_total_UNIV_transfer[transfer_rule]
   219 
   219 
   220 lemma UNIV_transfer [transfer_rule]:
   220 lemma UNIV_transfer [transfer_rule]:
   244   shows "(rel_set (rel_set A) ===> rel_set A) Inter Inter"
   244   shows "(rel_set (rel_set A) ===> rel_set A) Inter Inter"
   245   unfolding Inter_eq [abs_def] by transfer_prover
   245   unfolding Inter_eq [abs_def] by transfer_prover
   246 
   246 
   247 lemma filter_transfer [transfer_rule]:
   247 lemma filter_transfer [transfer_rule]:
   248   assumes [transfer_rule]: "bi_unique A"
   248   assumes [transfer_rule]: "bi_unique A"
   249   shows "((A ===> op=) ===> rel_set A ===> rel_set A) Set.filter Set.filter"
   249   shows "((A ===> (=)) ===> rel_set A ===> rel_set A) Set.filter Set.filter"
   250   unfolding Set.filter_def[abs_def] rel_fun_def rel_set_def by blast
   250   unfolding Set.filter_def[abs_def] rel_fun_def rel_set_def by blast
   251 
   251 
   252 lemma finite_transfer [transfer_rule]:
   252 lemma finite_transfer [transfer_rule]:
   253   "bi_unique A \<Longrightarrow> (rel_set A ===> op =) finite finite"
   253   "bi_unique A \<Longrightarrow> (rel_set A ===> (=)) finite finite"
   254   by (rule rel_funI, erule (1) bi_unique_rel_set_lemma)
   254   by (rule rel_funI, erule (1) bi_unique_rel_set_lemma)
   255      (auto dest: finite_imageD)
   255      (auto dest: finite_imageD)
   256 
   256 
   257 lemma card_transfer [transfer_rule]:
   257 lemma card_transfer [transfer_rule]:
   258   "bi_unique A \<Longrightarrow> (rel_set A ===> op =) card card"
   258   "bi_unique A \<Longrightarrow> (rel_set A ===> (=)) card card"
   259   by (rule rel_funI, erule (1) bi_unique_rel_set_lemma)
   259   by (rule rel_funI, erule (1) bi_unique_rel_set_lemma)
   260      (simp add: card_image)
   260      (simp add: card_image)
   261 
   261 
   262 lemma vimage_parametric [transfer_rule]:
   262 lemma vimage_parametric [transfer_rule]:
   263   assumes [transfer_rule]: "bi_total A" "bi_unique B"
   263   assumes [transfer_rule]: "bi_total A" "bi_unique B"
   264   shows "((A ===> B) ===> rel_set B ===> rel_set A) vimage vimage"
   264   shows "((A ===> B) ===> rel_set B ===> rel_set A) vimage vimage"
   265   unfolding vimage_def[abs_def] by transfer_prover
   265   unfolding vimage_def[abs_def] by transfer_prover
   266 
   266 
   267 lemma Image_parametric [transfer_rule]:
   267 lemma Image_parametric [transfer_rule]:
   268   assumes "bi_unique A"
   268   assumes "bi_unique A"
   269   shows "(rel_set (rel_prod A B) ===> rel_set A ===> rel_set B) op `` op ``"
   269   shows "(rel_set (rel_prod A B) ===> rel_set A ===> rel_set B) (``) (``)"
   270   by (intro rel_funI rel_setI)
   270   by (intro rel_funI rel_setI)
   271     (force dest: rel_setD1 bi_uniqueDr[OF assms], force dest: rel_setD2 bi_uniqueDl[OF assms])
   271     (force dest: rel_setD1 bi_uniqueDr[OF assms], force dest: rel_setD2 bi_uniqueDl[OF assms])
   272 
   272 
   273 end
   273 end
   274 
   274 
   275 lemma (in comm_monoid_set) F_parametric [transfer_rule]:
   275 lemma (in comm_monoid_set) F_parametric [transfer_rule]:
   276   fixes A :: "'b \<Rightarrow> 'c \<Rightarrow> bool"
   276   fixes A :: "'b \<Rightarrow> 'c \<Rightarrow> bool"
   277   assumes "bi_unique A"
   277   assumes "bi_unique A"
   278   shows "rel_fun (rel_fun A (op =)) (rel_fun (rel_set A) (op =)) F F"
   278   shows "rel_fun (rel_fun A (=)) (rel_fun (rel_set A) (=)) F F"
   279 proof (rule rel_funI)+
   279 proof (rule rel_funI)+
   280   fix f :: "'b \<Rightarrow> 'a" and g S T
   280   fix f :: "'b \<Rightarrow> 'a" and g S T
   281   assume "rel_fun A (op =) f g" "rel_set A S T"
   281   assume "rel_fun A (=) f g" "rel_set A S T"
   282   with \<open>bi_unique A\<close> obtain i where "bij_betw i S T" "\<And>x. x \<in> S \<Longrightarrow> f x = g (i x)"
   282   with \<open>bi_unique A\<close> obtain i where "bij_betw i S T" "\<And>x. x \<in> S \<Longrightarrow> f x = g (i x)"
   283     by (auto elim: bi_unique_rel_set_lemma simp: rel_fun_def bij_betw_def)
   283     by (auto elim: bi_unique_rel_set_lemma simp: rel_fun_def bij_betw_def)
   284   then show "F f S = F g T"
   284   then show "F f S = F g T"
   285     by (simp add: reindex_bij_betw)
   285     by (simp add: reindex_bij_betw)
   286 qed
   286 qed