# HG changeset patch # User haftmann # Date 1614543187 0 # Node ID 7a88313895d57696a6f4d1593f6f8a88f8d75d38 # Parent a89f56ab26863844d640938259ebee12905eca2b dissolve theory with duplicated name from afp diff -r a89f56ab2686 -r 7a88313895d5 src/HOL/Fun.thy --- a/src/HOL/Fun.thy Sun Feb 28 21:31:35 2021 +0100 +++ b/src/HOL/Fun.thy Sun Feb 28 20:13:07 2021 +0000 @@ -468,6 +468,38 @@ with that show thesis by blast qed +lemma bij_iff: \<^marker>\contributor \Amine Chaieb\\ + \bij f \ (\x. \!y. f y = x)\ (is \?P \ ?Q\) +proof + assume ?P + then have \inj f\ \surj f\ + by (simp_all add: bij_def) + show ?Q + proof + fix y + from \surj f\ obtain x where \y = f x\ + by (auto simp add: surj_def) + with \inj f\ show \\!x. f x = y\ + by (auto simp add: inj_def) + qed +next + assume ?Q + then have \inj f\ + by (auto simp add: inj_def) + moreover have \\x. y = f x\ for y + proof - + from \?Q\ obtain x where \f x = y\ + by blast + then have \y = f x\ + by simp + then show ?thesis .. + qed + then have \surj f\ + by (auto simp add: surj_def) + ultimately show ?P + by (rule bijI) +qed + lemma surj_image_vimage_eq: "surj f \ f ` (f -` A) = A" by simp diff -r a89f56ab2686 -r 7a88313895d5 src/HOL/Lattices_Big.thy --- a/src/HOL/Lattices_Big.thy Sun Feb 28 21:31:35 2021 +0100 +++ b/src/HOL/Lattices_Big.thy Sun Feb 28 20:13:07 2021 +0000 @@ -872,6 +872,10 @@ end +lemma disjnt_ge_max: \<^marker>\contributor \Lars Hupel\\ + \disjnt X Y\ if \finite Y\ \\x. x \ X \ x > Max Y\ + using that by (auto simp add: disjnt_def) (use Max_less_iff in blast) + subsection \Arg Min\ diff -r a89f56ab2686 -r 7a88313895d5 src/HOL/Library/Disjoint_FSets.thy --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/HOL/Library/Disjoint_FSets.thy Sun Feb 28 20:13:07 2021 +0000 @@ -0,0 +1,72 @@ +(* Title: HOL/Library/Disjoint_FSets.thy + Author: Lars Hupel, TU München +*) + +section \Disjoint FSets\ + +theory Disjoint_FSets + imports + "HOL-Library.Finite_Map" + "HOL-Library.Disjoint_Sets" +begin + +context + includes fset.lifting +begin + +lift_definition fdisjnt :: "'a fset \ 'a fset \ bool" is disjnt . + +lemma fdisjnt_alt_def: "fdisjnt M N \ (M |\| N = {||})" +by transfer (simp add: disjnt_def) + +lemma fdisjnt_insert: "x |\| N \ fdisjnt M N \ fdisjnt (finsert x M) N" +by transfer' (rule disjnt_insert) + +lemma fdisjnt_subset_right: "N' |\| N \ fdisjnt M N \ fdisjnt M N'" +unfolding fdisjnt_alt_def by auto + +lemma fdisjnt_subset_left: "N' |\| N \ fdisjnt N M \ fdisjnt N' M" +unfolding fdisjnt_alt_def by auto + +lemma fdisjnt_union_right: "fdisjnt M A \ fdisjnt M B \ fdisjnt M (A |\| B)" +unfolding fdisjnt_alt_def by auto + +lemma fdisjnt_union_left: "fdisjnt A M \ fdisjnt B M \ fdisjnt (A |\| B) M" +unfolding fdisjnt_alt_def by auto + +lemma fdisjnt_swap: "fdisjnt M N \ fdisjnt N M" +including fset.lifting by transfer' (auto simp: disjnt_def) + +lemma distinct_append_fset: + assumes "distinct xs" "distinct ys" "fdisjnt (fset_of_list xs) (fset_of_list ys)" + shows "distinct (xs @ ys)" +using assms +by transfer' (simp add: disjnt_def) + +lemma fdisjnt_contrI: + assumes "\x. x |\| M \ x |\| N \ False" + shows "fdisjnt M N" +using assms +by transfer' (auto simp: disjnt_def) + +lemma fdisjnt_Union_left: "fdisjnt (ffUnion S) T \ fBall S (\S. fdisjnt S T)" +by transfer' (auto simp: disjnt_def) + +lemma fdisjnt_Union_right: "fdisjnt T (ffUnion S) \ fBall S (\S. fdisjnt T S)" +by transfer' (auto simp: disjnt_def) + +lemma fdisjnt_ge_max: "fBall X (\x. x > fMax Y) \ fdisjnt X Y" +by transfer (auto intro: disjnt_ge_max) + +end + +(* FIXME should be provable without lifting *) +lemma fmadd_disjnt: "fdisjnt (fmdom m) (fmdom n) \ m ++\<^sub>f n = n ++\<^sub>f m" +unfolding fdisjnt_alt_def +including fset.lifting fmap.lifting +apply transfer +apply (rule ext) +apply (auto simp: map_add_def split: option.splits) +done + +end diff -r a89f56ab2686 -r 7a88313895d5 src/HOL/Library/Library.thy --- a/src/HOL/Library/Library.thy Sun Feb 28 21:31:35 2021 +0100 +++ b/src/HOL/Library/Library.thy Sun Feb 28 20:13:07 2021 +0000 @@ -24,6 +24,7 @@ Diagonal_Subsequence Discrete Disjoint_Sets + Disjoint_FSets Dlist Dual_Ordered_Lattice Equipollence diff -r a89f56ab2686 -r 7a88313895d5 src/HOL/Set.thy --- a/src/HOL/Set.thy Sun Feb 28 21:31:35 2021 +0100 +++ b/src/HOL/Set.thy Sun Feb 28 20:13:07 2021 +0000 @@ -1949,6 +1949,10 @@ lemma pairwise_disjnt_iff: "pairwise disjnt \ \ (\x. \\<^sub>\\<^sub>1 X. X \ \ \ x \ X)" by (auto simp: Uniq_def disjnt_iff pairwise_def) +lemma disjnt_insert: \<^marker>\contributor \Lars Hupel\\ + \disjnt (insert x M) N\ if \x \ N\ \disjnt M N\ + using that by (simp add: disjnt_def) + lemma Int_emptyI: "(\x. x \ A \ x \ B \ False) \ A \ B = {}" by blast