443 lemma femptyE [elim!]: "a |\<in>| {||} \<Longrightarrow> P" |
445 lemma femptyE [elim!]: "a |\<in>| {||} \<Longrightarrow> P" |
444 by simp |
446 by simp |
445 |
447 |
446 subsubsection {* fset *} |
448 subsubsection {* fset *} |
447 |
449 |
448 lemmas fset_simp[simp] = bot_fset.rep_eq finsert.rep_eq |
450 lemmas fset_simps[simp] = bot_fset.rep_eq finsert.rep_eq |
449 |
451 |
450 lemma finite_fset [simp]: |
452 lemma finite_fset [simp]: |
451 shows "finite (fset S)" |
453 shows "finite (fset S)" |
452 by transfer simp |
454 by transfer simp |
453 |
455 |
454 lemmas fset_cong[simp] = fset_inject |
456 lemmas fset_cong = fset_inject |
455 |
457 |
456 lemma filter_fset [simp]: |
458 lemma filter_fset [simp]: |
457 shows "fset (ffilter P xs) = Collect P \<inter> fset xs" |
459 shows "fset (ffilter P xs) = Collect P \<inter> fset xs" |
458 by transfer auto |
460 by transfer auto |
459 |
461 |
460 lemmas inter_fset [simp] = inf_fset.rep_eq |
462 lemma notin_fset: "x |\<notin>| S \<longleftrightarrow> x \<notin> fset S" by (simp add: fmember.rep_eq) |
461 |
463 |
462 lemmas union_fset [simp] = sup_fset.rep_eq |
464 lemmas inter_fset[simp] = inf_fset.rep_eq |
463 |
465 |
464 lemmas minus_fset [simp] = minus_fset.rep_eq |
466 lemmas union_fset[simp] = sup_fset.rep_eq |
|
467 |
|
468 lemmas minus_fset[simp] = minus_fset.rep_eq |
465 |
469 |
466 subsubsection {* filter_fset *} |
470 subsubsection {* filter_fset *} |
467 |
471 |
468 lemma subset_ffilter: |
472 lemma subset_ffilter: |
469 "ffilter P A |\<subseteq>| ffilter Q A = (\<forall> x. x |\<in>| A \<longrightarrow> P x \<longrightarrow> Q x)" |
473 "ffilter P A |\<subseteq>| ffilter Q A = (\<forall> x. x |\<in>| A \<longrightarrow> P x \<longrightarrow> Q x)" |
476 lemma psubset_ffilter: |
480 lemma psubset_ffilter: |
477 "(\<And>x. x |\<in>| A \<Longrightarrow> P x \<Longrightarrow> Q x) \<Longrightarrow> (x |\<in>| A & \<not> P x & Q x) \<Longrightarrow> |
481 "(\<And>x. x |\<in>| A \<Longrightarrow> P x \<Longrightarrow> Q x) \<Longrightarrow> (x |\<in>| A & \<not> P x & Q x) \<Longrightarrow> |
478 ffilter P A |\<subset>| ffilter Q A" |
482 ffilter P A |\<subset>| ffilter Q A" |
479 unfolding less_fset_def by (auto simp add: subset_ffilter eq_ffilter) |
483 unfolding less_fset_def by (auto simp add: subset_ffilter eq_ffilter) |
480 |
484 |
481 subsubsection {* insert *} |
485 subsubsection {* finsert *} |
482 |
486 |
483 (* FIXME, transferred doesn't work here *) |
487 (* FIXME, transferred doesn't work here *) |
484 lemma set_finsert: |
488 lemma set_finsert: |
485 assumes "x |\<in>| A" |
489 assumes "x |\<in>| A" |
486 obtains B where "A = finsert x B" and "x |\<notin>| B" |
490 obtains B where "A = finsert x B" and "x |\<notin>| B" |
487 using assms by transfer (metis Set.set_insert finite_insert) |
491 using assms by transfer (metis Set.set_insert finite_insert) |
488 |
492 |
489 lemma mk_disjoint_finsert: "a |\<in>| A \<Longrightarrow> \<exists>B. A = finsert a B \<and> a |\<notin>| B" |
493 lemma mk_disjoint_finsert: "a |\<in>| A \<Longrightarrow> \<exists>B. A = finsert a B \<and> a |\<notin>| B" |
490 by (rule_tac x = "A |-| {|a|}" in exI, blast) |
494 by (rule_tac x = "A |-| {|a|}" in exI, blast) |
491 |
495 |
492 subsubsection {* image *} |
496 subsubsection {* fimage *} |
493 |
497 |
494 lemma subset_fimage_iff: "(B |\<subseteq>| f|`|A) = (\<exists> AA. AA |\<subseteq>| A \<and> B = f|`|AA)" |
498 lemma subset_fimage_iff: "(B |\<subseteq>| f|`|A) = (\<exists> AA. AA |\<subseteq>| A \<and> B = f|`|AA)" |
495 by transfer (metis mem_Collect_eq rev_finite_subset subset_image_iff) |
499 by transfer (metis mem_Collect_eq rev_finite_subset subset_image_iff) |
496 |
500 |
497 subsubsection {* bounded quantification *} |
501 subsubsection {* bounded quantification *} |
519 lemma atomize_fBall: |
523 lemma atomize_fBall: |
520 "(\<And>x. x |\<in>| A ==> P x) == Trueprop (fBall A (\<lambda>x. P x))" |
524 "(\<And>x. x |\<in>| A ==> P x) == Trueprop (fBall A (\<lambda>x. P x))" |
521 apply (simp only: atomize_all atomize_imp) |
525 apply (simp only: atomize_all atomize_imp) |
522 apply (rule equal_intr_rule) |
526 apply (rule equal_intr_rule) |
523 by (transfer, simp)+ |
527 by (transfer, simp)+ |
|
528 |
|
529 end |
|
530 |
|
531 subsubsection {* fcard *} |
|
532 |
|
533 lemma fcard_fempty: |
|
534 "fcard {||} = 0" |
|
535 by transfer (rule card_empty) |
|
536 |
|
537 lemma fcard_finsert_disjoint: |
|
538 "x |\<notin>| A \<Longrightarrow> fcard (finsert x A) = Suc (fcard A)" |
|
539 by transfer (rule card_insert_disjoint) |
|
540 |
|
541 lemma fcard_finsert_if: |
|
542 "fcard (finsert x A) = (if x |\<in>| A then fcard A else Suc (fcard A))" |
|
543 by transfer (rule card_insert_if) |
|
544 |
|
545 lemma card_0_eq [simp, no_atp]: |
|
546 "fcard A = 0 \<longleftrightarrow> A = {||}" |
|
547 by transfer (rule card_0_eq) |
|
548 |
|
549 lemma fcard_Suc_fminus1: |
|
550 "x |\<in>| A \<Longrightarrow> Suc (fcard (A |-| {|x|})) = fcard A" |
|
551 by transfer (rule card_Suc_Diff1) |
|
552 |
|
553 lemma fcard_fminus_fsingleton: |
|
554 "x |\<in>| A \<Longrightarrow> fcard (A |-| {|x|}) = fcard A - 1" |
|
555 by transfer (rule card_Diff_singleton) |
|
556 |
|
557 lemma fcard_fminus_fsingleton_if: |
|
558 "fcard (A |-| {|x|}) = (if x |\<in>| A then fcard A - 1 else fcard A)" |
|
559 by transfer (rule card_Diff_singleton_if) |
|
560 |
|
561 lemma fcard_fminus_finsert[simp]: |
|
562 assumes "a |\<in>| A" and "a |\<notin>| B" |
|
563 shows "fcard (A |-| finsert a B) = fcard (A |-| B) - 1" |
|
564 using assms by transfer (rule card_Diff_insert) |
|
565 |
|
566 lemma fcard_finsert: "fcard (finsert x A) = Suc (fcard (A |-| {|x|}))" |
|
567 by transfer (rule card_insert) |
|
568 |
|
569 lemma fcard_finsert_le: "fcard A \<le> fcard (finsert x A)" |
|
570 by transfer (rule card_insert_le) |
|
571 |
|
572 lemma fcard_mono: |
|
573 "A |\<subseteq>| B \<Longrightarrow> fcard A \<le> fcard B" |
|
574 by transfer (rule card_mono) |
|
575 |
|
576 lemma fcard_seteq: "A |\<subseteq>| B \<Longrightarrow> fcard B \<le> fcard A \<Longrightarrow> A = B" |
|
577 by transfer (rule card_seteq) |
|
578 |
|
579 lemma pfsubset_fcard_mono: "A |\<subset>| B \<Longrightarrow> fcard A < fcard B" |
|
580 by transfer (rule psubset_card_mono) |
|
581 |
|
582 lemma fcard_funion_finter: |
|
583 "fcard A + fcard B = fcard (A |\<union>| B) + fcard (A |\<inter>| B)" |
|
584 by transfer (rule card_Un_Int) |
|
585 |
|
586 lemma fcard_funion_disjoint: |
|
587 "A |\<inter>| B = {||} \<Longrightarrow> fcard (A |\<union>| B) = fcard A + fcard B" |
|
588 by transfer (rule card_Un_disjoint) |
|
589 |
|
590 lemma fcard_funion_fsubset: |
|
591 "B |\<subseteq>| A \<Longrightarrow> fcard (A |-| B) = fcard A - fcard B" |
|
592 by transfer (rule card_Diff_subset) |
|
593 |
|
594 lemma diff_fcard_le_fcard_fminus: |
|
595 "fcard A - fcard B \<le> fcard(A |-| B)" |
|
596 by transfer (rule diff_card_le_card_Diff) |
|
597 |
|
598 lemma fcard_fminus1_less: "x |\<in>| A \<Longrightarrow> fcard (A |-| {|x|}) < fcard A" |
|
599 by transfer (rule card_Diff1_less) |
|
600 |
|
601 lemma fcard_fminus2_less: |
|
602 "x |\<in>| A \<Longrightarrow> y |\<in>| A \<Longrightarrow> fcard (A |-| {|x|} |-| {|y|}) < fcard A" |
|
603 by transfer (rule card_Diff2_less) |
|
604 |
|
605 lemma fcard_fminus1_le: "fcard (A |-| {|x|}) \<le> fcard A" |
|
606 by transfer (rule card_Diff1_le) |
|
607 |
|
608 lemma fcard_pfsubset: "A |\<subseteq>| B \<Longrightarrow> fcard A < fcard B \<Longrightarrow> A < B" |
|
609 by transfer (rule card_psubset) |
|
610 |
|
611 subsubsection {* ffold *} |
|
612 |
|
613 (* FIXME: improve transferred to handle bounded meta quantification *) |
|
614 |
|
615 context comp_fun_commute |
|
616 begin |
|
617 lemmas ffold_empty[simp] = fold_empty[Transfer.transferred] |
|
618 |
|
619 lemma ffold_finsert [simp]: |
|
620 assumes "x |\<notin>| A" |
|
621 shows "ffold f z (finsert x A) = f x (ffold f z A)" |
|
622 using assms by (transfer fixing: f) (rule fold_insert) |
|
623 |
|
624 lemma ffold_fun_left_comm: |
|
625 "f x (ffold f z A) = ffold f (f x z) A" |
|
626 by (transfer fixing: f) (rule fold_fun_left_comm) |
|
627 |
|
628 lemma ffold_finsert2: |
|
629 "x |\<notin>| A \<Longrightarrow> ffold f z (finsert x A) = ffold f (f x z) A" |
|
630 by (transfer fixing: f) (rule fold_insert2) |
|
631 |
|
632 lemma ffold_rec: |
|
633 assumes "x |\<in>| A" |
|
634 shows "ffold f z A = f x (ffold f z (A |-| {|x|}))" |
|
635 using assms by (transfer fixing: f) (rule fold_rec) |
|
636 |
|
637 lemma ffold_finsert_fremove: |
|
638 "ffold f z (finsert x A) = f x (ffold f z (A |-| {|x|}))" |
|
639 by (transfer fixing: f) (rule fold_insert_remove) |
|
640 end |
|
641 |
|
642 lemma ffold_fimage: |
|
643 assumes "inj_on g (fset A)" |
|
644 shows "ffold f z (g |`| A) = ffold (f \<circ> g) z A" |
|
645 using assms by transfer' (rule fold_image) |
|
646 |
|
647 lemma ffold_cong: |
|
648 assumes "comp_fun_commute f" "comp_fun_commute g" |
|
649 "\<And>x. x |\<in>| A \<Longrightarrow> f x = g x" |
|
650 and "s = t" and "A = B" |
|
651 shows "ffold f s A = ffold g t B" |
|
652 using assms by transfer (metis Finite_Set.fold_cong) |
|
653 |
|
654 context comp_fun_idem |
|
655 begin |
|
656 |
|
657 lemma ffold_finsert_idem: |
|
658 "ffold f z (finsert x A) = f x (ffold f z A)" |
|
659 by (transfer fixing: f) (rule fold_insert_idem) |
|
660 |
|
661 declare ffold_finsert [simp del] ffold_finsert_idem [simp] |
|
662 |
|
663 lemma ffold_finsert_idem2: |
|
664 "ffold f z (finsert x A) = ffold f (f x z) A" |
|
665 by (transfer fixing: f) (rule fold_insert_idem2) |
|
666 |
|
667 end |
524 |
668 |
525 subsection {* Choice in fsets *} |
669 subsection {* Choice in fsets *} |
526 |
670 |
527 lemma fset_choice: |
671 lemma fset_choice: |
528 assumes "\<forall>x. x |\<in>| A \<longrightarrow> (\<exists>y. P x y)" |
672 assumes "\<forall>x. x |\<in>| A \<longrightarrow> (\<exists>y. P x y)" |
761 assumes "bi_unique A" |
910 assumes "bi_unique A" |
762 shows "(fset_rel A ===> fset_rel A ===> fset_rel A) finter finter" |
911 shows "(fset_rel A ===> fset_rel A ===> fset_rel A) finter finter" |
763 using assms unfolding fun_rel_def |
912 using assms unfolding fun_rel_def |
764 using inter_transfer[unfolded fun_rel_def, rule_format, Transfer.transferred] by blast |
913 using inter_transfer[unfolded fun_rel_def, rule_format, Transfer.transferred] by blast |
765 |
914 |
766 lemma fDiff_transfer [transfer_rule]: |
915 lemma fminus_transfer [transfer_rule]: |
767 assumes "bi_unique A" |
916 assumes "bi_unique A" |
768 shows "(fset_rel A ===> fset_rel A ===> fset_rel A) (op |-|) (op |-|)" |
917 shows "(fset_rel A ===> fset_rel A ===> fset_rel A) (op |-|) (op |-|)" |
769 using assms unfolding fun_rel_def |
918 using assms unfolding fun_rel_def |
770 using Diff_transfer[unfolded fun_rel_def, rule_format, Transfer.transferred] by blast |
919 using Diff_transfer[unfolded fun_rel_def, rule_format, Transfer.transferred] by blast |
771 |
920 |