src/HOL/Finite_Set.thy
changeset 49739 13aa6d8268ec
parent 49724 a5842f026d4c
child 49756 28e37eab4e6f
child 49757 73ab6d4a9236
equal deleted inserted replaced
49738:1e1611fd32df 49739:13aa6d8268ec
   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"