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) |
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 |