src/HOL/Finite_Set.thy
changeset 69593 3dda49e08b9d
parent 69312 e0f68a507683
child 69735 8230dca028eb
equal deleted inserted replaced
69592:a80d8ec6c998 69593:3dda49e08b9d
   775   unfolding Finite_Set.fold_def
   775   unfolding Finite_Set.fold_def
   776   by (subst fold_graph_closed_eq[where B=B and g=g]) (auto simp: that)
   776   by (subst fold_graph_closed_eq[where B=B and g=g]) (auto simp: that)
   777 
   777 
   778 text \<open>
   778 text \<open>
   779   A tempting alternative for the definiens is
   779   A tempting alternative for the definiens is
   780   @{term "if finite A then THE y. fold_graph f z A y else e"}.
   780   \<^term>\<open>if finite A then THE y. fold_graph f z A y else e\<close>.
   781   It allows the removal of finiteness assumptions from the theorems
   781   It allows the removal of finiteness assumptions from the theorems
   782   \<open>fold_comm\<close>, \<open>fold_reindex\<close> and \<open>fold_distrib\<close>.
   782   \<open>fold_comm\<close>, \<open>fold_reindex\<close> and \<open>fold_distrib\<close>.
   783   The proofs become ugly. It is not worth the effort. (???)
   783   The proofs become ugly. It is not worth the effort. (???)
   784 \<close>
   784 \<close>
   785 
   785 
   786 lemma finite_imp_fold_graph: "finite A \<Longrightarrow> \<exists>x. fold_graph f z A x"
   786 lemma finite_imp_fold_graph: "finite A \<Longrightarrow> \<exists>x. fold_graph f z A x"
   787   by (induct rule: finite_induct) auto
   787   by (induct rule: finite_induct) auto
   788 
   788 
   789 
   789 
   790 subsubsection \<open>From @{const fold_graph} to @{term fold}\<close>
   790 subsubsection \<open>From \<^const>\<open>fold_graph\<close> to \<^term>\<open>fold\<close>\<close>
   791 
   791 
   792 context comp_fun_commute
   792 context comp_fun_commute
   793 begin
   793 begin
   794 
   794 
   795 lemma fold_graph_finite:
   795 lemma fold_graph_finite:
   866   by (auto simp: fold_def)
   866   by (auto simp: fold_def)
   867 
   867 
   868 lemma (in -) fold_empty [simp]: "fold f z {} = z"
   868 lemma (in -) fold_empty [simp]: "fold f z {} = z"
   869   by (auto simp: fold_def)
   869   by (auto simp: fold_def)
   870 
   870 
   871 text \<open>The various recursion equations for @{const fold}:\<close>
   871 text \<open>The various recursion equations for \<^const>\<open>fold\<close>:\<close>
   872 
   872 
   873 lemma fold_insert [simp]:
   873 lemma fold_insert [simp]:
   874   assumes "finite A" and "x \<notin> A"
   874   assumes "finite A" and "x \<notin> A"
   875   shows "fold f z (insert x A) = f x (fold f z A)"
   875   shows "fold f z (insert x A) = f x (fold f z A)"
   876 proof (rule fold_equality)
   876 proof (rule fold_equality)
   931   shows "Finite_Set.fold f z (A \<union> B) = Finite_Set.fold f (Finite_Set.fold f z A) B"
   931   shows "Finite_Set.fold f z (A \<union> B) = Finite_Set.fold f (Finite_Set.fold f z A) B"
   932   using assms(2,1,3) by induct simp_all
   932   using assms(2,1,3) by induct simp_all
   933 
   933 
   934 end
   934 end
   935 
   935 
   936 text \<open>Other properties of @{const fold}:\<close>
   936 text \<open>Other properties of \<^const>\<open>fold\<close>:\<close>
   937 
   937 
   938 lemma fold_image:
   938 lemma fold_image:
   939   assumes "inj_on g A"
   939   assumes "inj_on g A"
   940   shows "fold f z (g ` A) = fold (f \<circ> g) z A"
   940   shows "fold f z (g ` A) = fold (f \<circ> g) z A"
   941 proof (cases "finite A")
   941 proof (cases "finite A")
  1099     qed
  1099     qed
  1100   qed
  1100   qed
  1101 qed
  1101 qed
  1102 
  1102 
  1103 
  1103 
  1104 subsubsection \<open>Expressing set operations via @{const fold}\<close>
  1104 subsubsection \<open>Expressing set operations via \<^const>\<open>fold\<close>\<close>
  1105 
  1105 
  1106 lemma comp_fun_commute_const: "comp_fun_commute (\<lambda>_. f)"
  1106 lemma comp_fun_commute_const: "comp_fun_commute (\<lambda>_. f)"
  1107   by standard rule
  1107   by standard rule
  1108 
  1108 
  1109 lemma comp_fun_idem_insert: "comp_fun_idem insert"
  1109 lemma comp_fun_idem_insert: "comp_fun_idem insert"
  1354 
  1354 
  1355 subsection \<open>Finite cardinality\<close>
  1355 subsection \<open>Finite cardinality\<close>
  1356 
  1356 
  1357 text \<open>
  1357 text \<open>
  1358   The traditional definition
  1358   The traditional definition
  1359   @{prop "card A \<equiv> LEAST n. \<exists>f. A = {f i |i. i < n}"}
  1359   \<^prop>\<open>card A \<equiv> LEAST n. \<exists>f. A = {f i |i. i < n}\<close>
  1360   is ugly to work with.
  1360   is ugly to work with.
  1361   But now that we have @{const fold} things are easy:
  1361   But now that we have \<^const>\<open>fold\<close> things are easy:
  1362 \<close>
  1362 \<close>
  1363 
  1363 
  1364 global_interpretation card: folding "\<lambda>_. Suc" 0
  1364 global_interpretation card: folding "\<lambda>_. Suc" 0
  1365   defines card = "folding.F (\<lambda>_. Suc) 0"
  1365   defines card = "folding.F (\<lambda>_. Suc) 0"
  1366   by standard rule
  1366   by standard rule