src/HOL/Library/FSet.thy
changeset 61585 a9599d3d7610
parent 61424 c3658c18b7bc
child 61952 546958347e05
equal deleted inserted replaced
61584:f06e5a5a4b46 61585:a9599d3d7610
   443 lemmas fequalityI = equalityI[Transfer.transferred]
   443 lemmas fequalityI = equalityI[Transfer.transferred]
   444 
   444 
   445 
   445 
   446 subsection \<open>Additional lemmas\<close>
   446 subsection \<open>Additional lemmas\<close>
   447 
   447 
   448 subsubsection \<open>@{text fsingleton}\<close>
   448 subsubsection \<open>\<open>fsingleton\<close>\<close>
   449 
   449 
   450 lemmas fsingletonE = fsingletonD [elim_format]
   450 lemmas fsingletonE = fsingletonD [elim_format]
   451 
   451 
   452 
   452 
   453 subsubsection \<open>@{text femepty}\<close>
   453 subsubsection \<open>\<open>femepty\<close>\<close>
   454 
   454 
   455 lemma fempty_ffilter[simp]: "ffilter (\<lambda>_. False) A = {||}"
   455 lemma fempty_ffilter[simp]: "ffilter (\<lambda>_. False) A = {||}"
   456 by transfer auto
   456 by transfer auto
   457 
   457 
   458 (* FIXME, transferred doesn't work here *)
   458 (* FIXME, transferred doesn't work here *)
   459 lemma femptyE [elim!]: "a |\<in>| {||} \<Longrightarrow> P"
   459 lemma femptyE [elim!]: "a |\<in>| {||} \<Longrightarrow> P"
   460   by simp
   460   by simp
   461 
   461 
   462 
   462 
   463 subsubsection \<open>@{text fset}\<close>
   463 subsubsection \<open>\<open>fset\<close>\<close>
   464 
   464 
   465 lemmas fset_simps[simp] = bot_fset.rep_eq finsert.rep_eq
   465 lemmas fset_simps[simp] = bot_fset.rep_eq finsert.rep_eq
   466 
   466 
   467 lemma finite_fset [simp]: 
   467 lemma finite_fset [simp]: 
   468   shows "finite (fset S)"
   468   shows "finite (fset S)"
   481 lemmas union_fset[simp] = sup_fset.rep_eq
   481 lemmas union_fset[simp] = sup_fset.rep_eq
   482 
   482 
   483 lemmas minus_fset[simp] = minus_fset.rep_eq
   483 lemmas minus_fset[simp] = minus_fset.rep_eq
   484 
   484 
   485 
   485 
   486 subsubsection \<open>@{text filter_fset}\<close>
   486 subsubsection \<open>\<open>filter_fset\<close>\<close>
   487 
   487 
   488 lemma subset_ffilter: 
   488 lemma subset_ffilter: 
   489   "ffilter P A |\<subseteq>| ffilter Q A = (\<forall> x. x |\<in>| A \<longrightarrow> P x \<longrightarrow> Q x)"
   489   "ffilter P A |\<subseteq>| ffilter Q A = (\<forall> x. x |\<in>| A \<longrightarrow> P x \<longrightarrow> Q x)"
   490   by transfer auto
   490   by transfer auto
   491 
   491 
   497   "(\<And>x. x |\<in>| A \<Longrightarrow> P x \<Longrightarrow> Q x) \<Longrightarrow> (x |\<in>| A & \<not> P x & Q x) \<Longrightarrow> 
   497   "(\<And>x. x |\<in>| A \<Longrightarrow> P x \<Longrightarrow> Q x) \<Longrightarrow> (x |\<in>| A & \<not> P x & Q x) \<Longrightarrow> 
   498     ffilter P A |\<subset>| ffilter Q A"
   498     ffilter P A |\<subset>| ffilter Q A"
   499   unfolding less_fset_def by (auto simp add: subset_ffilter eq_ffilter)
   499   unfolding less_fset_def by (auto simp add: subset_ffilter eq_ffilter)
   500 
   500 
   501 
   501 
   502 subsubsection \<open>@{text finsert}\<close>
   502 subsubsection \<open>\<open>finsert\<close>\<close>
   503 
   503 
   504 (* FIXME, transferred doesn't work here *)
   504 (* FIXME, transferred doesn't work here *)
   505 lemma set_finsert:
   505 lemma set_finsert:
   506   assumes "x |\<in>| A"
   506   assumes "x |\<in>| A"
   507   obtains B where "A = finsert x B" and "x |\<notin>| B"
   507   obtains B where "A = finsert x B" and "x |\<notin>| B"
   509 
   509 
   510 lemma mk_disjoint_finsert: "a |\<in>| A \<Longrightarrow> \<exists>B. A = finsert a B \<and> a |\<notin>| B"
   510 lemma mk_disjoint_finsert: "a |\<in>| A \<Longrightarrow> \<exists>B. A = finsert a B \<and> a |\<notin>| B"
   511   by (rule_tac x = "A |-| {|a|}" in exI, blast)
   511   by (rule_tac x = "A |-| {|a|}" in exI, blast)
   512 
   512 
   513 
   513 
   514 subsubsection \<open>@{text fimage}\<close>
   514 subsubsection \<open>\<open>fimage\<close>\<close>
   515 
   515 
   516 lemma subset_fimage_iff: "(B |\<subseteq>| f|`|A) = (\<exists> AA. AA |\<subseteq>| A \<and> B = f|`|AA)"
   516 lemma subset_fimage_iff: "(B |\<subseteq>| f|`|A) = (\<exists> AA. AA |\<subseteq>| A \<and> B = f|`|AA)"
   517 by transfer (metis mem_Collect_eq rev_finite_subset subset_image_iff)
   517 by transfer (metis mem_Collect_eq rev_finite_subset subset_image_iff)
   518 
   518 
   519 
   519 
   546 by (transfer, simp)+
   546 by (transfer, simp)+
   547 
   547 
   548 end
   548 end
   549 
   549 
   550 
   550 
   551 subsubsection \<open>@{text fcard}\<close>
   551 subsubsection \<open>\<open>fcard\<close>\<close>
   552 
   552 
   553 (* FIXME: improve transferred to handle bounded meta quantification *)
   553 (* FIXME: improve transferred to handle bounded meta quantification *)
   554 
   554 
   555 lemma fcard_fempty:
   555 lemma fcard_fempty:
   556   "fcard {||} = 0"
   556   "fcard {||} = 0"
   629 
   629 
   630 lemma fcard_pfsubset: "A |\<subseteq>| B \<Longrightarrow> fcard A < fcard B \<Longrightarrow> A < B"
   630 lemma fcard_pfsubset: "A |\<subseteq>| B \<Longrightarrow> fcard A < fcard B \<Longrightarrow> A < B"
   631 by transfer (rule card_psubset)
   631 by transfer (rule card_psubset)
   632 
   632 
   633 
   633 
   634 subsubsection \<open>@{text ffold}\<close>
   634 subsubsection \<open>\<open>ffold\<close>\<close>
   635 
   635 
   636 (* FIXME: improve transferred to handle bounded meta quantification *)
   636 (* FIXME: improve transferred to handle bounded meta quantification *)
   637 
   637 
   638 context comp_fun_commute
   638 context comp_fun_commute
   639 begin
   639 begin