791 def h \<equiv> "\<lambda>z. g z - 1" |
791 def h \<equiv> "\<lambda>z. g z - 1" |
792 with Suc have "n = h y" by simp |
792 with Suc have "n = h y" by simp |
793 with Suc have hyp: "f y ^^ h y \<circ> f x = f x \<circ> f y ^^ h y" |
793 with Suc have hyp: "f y ^^ h y \<circ> f x = f x \<circ> f y ^^ h y" |
794 by auto |
794 by auto |
795 from Suc h_def have "g y = Suc (h y)" by simp |
795 from Suc h_def have "g y = Suc (h y)" by simp |
796 then show ?case by (simp add: o_assoc [symmetric] hyp) |
796 then show ?case by (simp add: comp_assoc hyp) |
797 (simp add: o_assoc comp_fun_commute) |
797 (simp add: o_assoc comp_fun_commute) |
798 qed |
798 qed |
799 def h \<equiv> "\<lambda>z. if z = x then g x - 1 else g z" |
799 def h \<equiv> "\<lambda>z. if z = x then g x - 1 else g z" |
800 with Suc have "n = h x" by simp |
800 with Suc have "n = h x" by simp |
801 with Suc have "f y ^^ h y \<circ> f x ^^ h x = f x ^^ h x \<circ> f y ^^ h y" |
801 with Suc have "f y ^^ h y \<circ> f x ^^ h x = f x ^^ h x \<circ> f y ^^ h y" |
802 by auto |
802 by auto |
803 with False h_def have hyp2: "f y ^^ g y \<circ> f x ^^ h x = f x ^^ h x \<circ> f y ^^ g y" by simp |
803 with False h_def have hyp2: "f y ^^ g y \<circ> f x ^^ h x = f x ^^ h x \<circ> f y ^^ g y" by simp |
804 from Suc h_def have "g x = Suc (h x)" by simp |
804 from Suc h_def have "g x = Suc (h x)" by simp |
805 then show ?case by (simp del: funpow.simps add: funpow_Suc_right o_assoc hyp2) |
805 then show ?case by (simp del: funpow.simps add: funpow_Suc_right o_assoc hyp2) |
806 (simp add: o_assoc [symmetric] hyp1) |
806 (simp add: comp_assoc hyp1) |
807 qed |
807 qed |
808 qed |
808 qed |
809 qed |
809 qed |
810 |
810 |
811 |
811 |
1505 |
1505 |
1506 lemma comp_fun_commute': |
1506 lemma comp_fun_commute': |
1507 assumes "finite A" |
1507 assumes "finite A" |
1508 shows "f x \<circ> F A = F A \<circ> f x" |
1508 shows "f x \<circ> F A = F A \<circ> f x" |
1509 using assms by (induct A) |
1509 using assms by (induct A) |
1510 (simp, simp del: o_apply add: o_assoc, simp del: o_apply add: o_assoc [symmetric] comp_fun_commute) |
1510 (simp, simp del: o_apply add: o_assoc, simp del: o_apply add: comp_assoc comp_fun_commute) |
1511 |
1511 |
1512 lemma commute_left_comp': |
1512 lemma commute_left_comp': |
1513 assumes "finite A" |
1513 assumes "finite A" |
1514 shows "f x \<circ> (F A \<circ> g) = F A \<circ> (f x \<circ> g)" |
1514 shows "f x \<circ> (F A \<circ> g) = F A \<circ> (f x \<circ> g)" |
1515 using assms by (simp add: o_assoc comp_fun_commute') |
1515 using assms by (simp add: o_assoc comp_fun_commute') |
1516 |
1516 |
1517 lemma comp_fun_commute'': |
1517 lemma comp_fun_commute'': |
1518 assumes "finite A" and "finite B" |
1518 assumes "finite A" and "finite B" |
1519 shows "F B \<circ> F A = F A \<circ> F B" |
1519 shows "F B \<circ> F A = F A \<circ> F B" |
1520 using assms by (induct A) |
1520 using assms by (induct A) |
1521 (simp_all add: o_assoc, simp add: o_assoc [symmetric] comp_fun_commute') |
1521 (simp_all add: o_assoc, simp add: comp_assoc comp_fun_commute') |
1522 |
1522 |
1523 lemma commute_left_comp'': |
1523 lemma commute_left_comp'': |
1524 assumes "finite A" and "finite B" |
1524 assumes "finite A" and "finite B" |
1525 shows "F B \<circ> (F A \<circ> g) = F A \<circ> (F B \<circ> g)" |
1525 shows "F B \<circ> (F A \<circ> g) = F A \<circ> (F B \<circ> g)" |
1526 using assms by (simp add: o_assoc comp_fun_commute'') |
1526 using assms by (simp add: o_assoc comp_fun_commute'') |
1527 |
1527 |
1528 lemmas comp_fun_commutes = o_assoc [symmetric] comp_fun_commute commute_left_comp |
1528 lemmas comp_fun_commutes = comp_assoc comp_fun_commute commute_left_comp |
1529 comp_fun_commute' commute_left_comp' comp_fun_commute'' commute_left_comp'' |
1529 comp_fun_commute' commute_left_comp' comp_fun_commute'' commute_left_comp'' |
1530 |
1530 |
1531 lemma union_inter: |
1531 lemma union_inter: |
1532 assumes "finite A" and "finite B" |
1532 assumes "finite A" and "finite B" |
1533 shows "F (A \<union> B) \<circ> F (A \<inter> B) = F A \<circ> F B" |
1533 shows "F (A \<union> B) \<circ> F (A \<inter> B) = F A \<circ> F B" |