src/HOL/Relation.thy
changeset 73832 9db620f007fa
parent 71935 82b00b8f1871
child 74806 ba59c691b3ee
equal deleted inserted replaced
73793:26c0ccf17f31 73832:9db620f007fa
  1240 
  1240 
  1241 lemma relcomp_fold:
  1241 lemma relcomp_fold:
  1242   assumes "finite R" "finite S"
  1242   assumes "finite R" "finite S"
  1243   shows "R O S = Finite_Set.fold
  1243   shows "R O S = Finite_Set.fold
  1244     (\<lambda>(x,y) A. Finite_Set.fold (\<lambda>(w,z) A'. if y = w then Set.insert (x,z) A' else A') A S) {} R"
  1244     (\<lambda>(x,y) A. Finite_Set.fold (\<lambda>(w,z) A'. if y = w then Set.insert (x,z) A' else A') A S) {} R"
  1245   using assms
  1245 proof -
  1246   by (induct R)
  1246   interpret commute_relcomp_fold: comp_fun_commute
  1247     (auto simp: comp_fun_commute.fold_insert comp_fun_commute_relcomp_fold insert_relcomp_fold
  1247     "(\<lambda>(x, y) A. Finite_Set.fold (\<lambda>(w, z) A'. if y = w then insert (x, z) A' else A') A S)"
  1248       cong: if_cong)
  1248     by (fact comp_fun_commute_relcomp_fold[OF \<open>finite S\<close>])
       
  1249   from assms show ?thesis
       
  1250     by (induct R) (auto simp: comp_fun_commute_relcomp_fold insert_relcomp_fold cong: if_cong)
       
  1251 qed
  1249 
  1252 
  1250 end
  1253 end