equal
deleted
inserted
replaced
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 |