866 qed |
875 qed |
867 } |
876 } |
868 then show "l \<approx> r \<Longrightarrow> list_eq2 l r" by blast |
877 then show "l \<approx> r \<Longrightarrow> list_eq2 l r" by blast |
869 qed |
878 qed |
870 |
879 |
|
880 text {* Raw theorems of ffilter *} |
|
881 |
|
882 lemma sub_list_filter: "sub_list (filter P xs) (filter Q xs) = (\<forall> x. memb x xs \<longrightarrow> P x \<longrightarrow> Q x)" |
|
883 unfolding sub_list_def memb_def by auto |
|
884 |
|
885 lemma list_eq_filter: "list_eq (filter P xs) (filter Q xs) = (\<forall>x. memb x xs \<longrightarrow> P x = Q x)" |
|
886 unfolding memb_def by auto |
|
887 |
871 text {* Lifted theorems *} |
888 text {* Lifted theorems *} |
872 |
889 |
873 lemma not_fin_fnil: "x |\<notin>| {||}" |
890 lemma not_fin_fnil: "x |\<notin>| {||}" |
874 by (lifting not_memb_nil) |
891 by (lifting not_memb_nil) |
875 |
892 |
1140 by (lifting concat.simps(2)) |
1157 by (lifting concat.simps(2)) |
1141 |
1158 |
1142 lemma "fconcat (xs |\<union>| ys) = fconcat xs |\<union>| fconcat ys" |
1159 lemma "fconcat (xs |\<union>| ys) = fconcat xs |\<union>| fconcat ys" |
1143 by (lifting concat_append) |
1160 by (lifting concat_append) |
1144 |
1161 |
|
1162 text {* ffilter *} |
|
1163 |
|
1164 lemma subseteq_filter: "ffilter P xs <= ffilter Q xs = (\<forall> x. x |\<in>| xs \<longrightarrow> P x \<longrightarrow> Q x)" |
|
1165 by (lifting sub_list_filter) |
|
1166 |
|
1167 lemma eq_ffilter: "(ffilter P xs = ffilter Q xs) = (\<forall>x. x |\<in>| xs \<longrightarrow> P x = Q x)" |
|
1168 by (lifting list_eq_filter) |
|
1169 |
|
1170 lemma subset_ffilter: "(\<And>x. x |\<in>| xs \<Longrightarrow> P x \<Longrightarrow> Q x) \<Longrightarrow> (x |\<in>| xs & \<not> P x & Q x) \<Longrightarrow> ffilter P xs < ffilter Q xs" |
|
1171 unfolding less_fset by (auto simp add: subseteq_filter eq_ffilter) |
|
1172 |
|
1173 |
|
1174 section {* lemmas transferred from Finite_Set theory *} |
|
1175 |
|
1176 text {* finiteness for finite sets holds *} |
|
1177 lemma finite_fset: "finite (fset_to_set S)" |
|
1178 by (induct S) auto |
|
1179 |
|
1180 text {* @{thm subset_empty} transferred is: *} |
|
1181 lemma fsubseteq_fnil: "xs |\<subseteq>| {||} = (xs = {||})" |
|
1182 by (cases xs) (auto simp add: fsubset_finsert not_fin_fnil) |
|
1183 |
|
1184 text {* @{thm not_psubset_empty} transferred is: *} |
|
1185 lemma not_fsubset_fnil: "\<not> xs |\<subset>| {||}" |
|
1186 unfolding less_fset by (auto simp add: fsubseteq_fnil) |
|
1187 |
|
1188 text {* @{thm card_mono} transferred is: *} |
|
1189 lemma fcard_mono: "xs |\<subseteq>| ys \<Longrightarrow> fcard xs \<le> fcard ys" |
|
1190 proof (induct xs arbitrary: ys) |
|
1191 case fempty |
|
1192 thus ?case by simp |
|
1193 next |
|
1194 case (finsert x xs ys) |
|
1195 from finsert(1,3) have "xs |\<subseteq>| fdelete ys x" |
|
1196 by (auto simp add: fsubset_fin fin_fdelete) |
|
1197 from finsert(2) this have hyp: "fcard xs \<le> fcard (fdelete ys x)" by simp |
|
1198 from finsert(3) have "x |\<in>| ys" by (auto simp add: fsubset_fin) |
|
1199 from this have ys_is: "ys = finsert x (fdelete ys x)" |
|
1200 unfolding expand_fset_eq by (auto simp add: fin_fdelete) |
|
1201 from finsert(1) hyp have "fcard (finsert x xs) \<le> fcard (finsert x (fdelete ys x))" |
|
1202 by (auto simp add: fin_fdelete_ident) |
|
1203 from ys_is this show ?case by auto |
|
1204 qed |
|
1205 |
|
1206 text {* @{thm card_seteq} transferred is: *} |
|
1207 lemma fcard_fseteq: "xs |\<subseteq>| ys \<Longrightarrow> fcard ys \<le> fcard xs \<Longrightarrow> xs = ys" |
|
1208 proof (induct xs arbitrary: ys) |
|
1209 case fempty |
|
1210 thus ?case by (simp add: fcard_0) |
|
1211 next |
|
1212 case (finsert x xs ys) |
|
1213 from finsert have subset: "xs |\<subseteq>| fdelete ys x" |
|
1214 by (auto simp add: fsubset_fin fin_fdelete) |
|
1215 from finsert have x: "x |\<in>| ys" |
|
1216 by (auto simp add: fsubset_fin fin_fdelete) |
|
1217 from finsert(1,4) this have "fcard (fdelete ys x) \<le> fcard xs" |
|
1218 by (auto simp add: fcard_delete) |
|
1219 from finsert(2) this subset have hyp: "xs = fdelete ys x" by auto |
|
1220 from finsert have "x |\<in>| ys" |
|
1221 by (auto simp add: fsubset_fin fin_fdelete) |
|
1222 from this hyp show ?case |
|
1223 unfolding expand_fset_eq by (auto simp add: fin_fdelete) |
|
1224 qed |
|
1225 |
|
1226 text {* @{thm psubset_card_mono} transferred is: *} |
|
1227 lemma psubset_fcard_mono: "xs |\<subset>| ys \<Longrightarrow> fcard xs < fcard ys" |
|
1228 unfolding less_fset linorder_not_le[symmetric] |
|
1229 by (auto simp add: fcard_fseteq) |
|
1230 |
|
1231 |
1145 ML {* |
1232 ML {* |
1146 fun dest_fsetT (Type (@{type_name fset}, [T])) = T |
1233 fun dest_fsetT (Type (@{type_name fset}, [T])) = T |
1147 | dest_fsetT T = raise TYPE ("dest_fsetT: fset type expected", [T], []); |
1234 | dest_fsetT T = raise TYPE ("dest_fsetT: fset type expected", [T], []); |
1148 *} |
1235 *} |
1149 |
1236 |