src/HOL/Library/Permutations.thy
changeset 72304 6fdeef6d6335
parent 72302 d7d90ed4c74e
child 73328 ff24fe85ee57
equal deleted inserted replaced
72303:4e649ea1f76b 72304:6fdeef6d6335
   332   then show ?case by simp
   332   then show ?case by simp
   333 next
   333 next
   334   case (insert x F)
   334   case (insert x F)
   335   {
   335   {
   336     fix n
   336     fix n
   337     assume card.insert_remove: "card (insert x F) = n"
   337     assume card_insert: "card (insert x F) = n"
   338     let ?xF = "{p. p permutes insert x F}"
   338     let ?xF = "{p. p permutes insert x F}"
   339     let ?pF = "{p. p permutes F}"
   339     let ?pF = "{p. p permutes F}"
   340     let ?pF' = "{(b, p). b \<in> insert x F \<and> p \<in> ?pF}"
   340     let ?pF' = "{(b, p). b \<in> insert x F \<and> p \<in> ?pF}"
   341     let ?g = "(\<lambda>(b, p). Fun.swap x b id \<circ> p)"
   341     let ?g = "(\<lambda>(b, p). Fun.swap x b id \<circ> p)"
   342     have xfgpF': "?xF = ?g ` ?pF'"
   342     have xfgpF': "?xF = ?g ` ?pF'"
   343       by (rule permutes_insert[of x F])
   343       by (rule permutes_insert[of x F])
   344     from \<open>x \<notin> F\<close> \<open>finite F\<close> card.insert_remove have Fs: "card F = n - 1"
   344     from \<open>x \<notin> F\<close> \<open>finite F\<close> card_insert have Fs: "card F = n - 1"
   345       by auto
   345       by auto
   346     from \<open>finite F\<close> insert.hyps Fs have pFs: "card ?pF = fact (n - 1)"
   346     from \<open>finite F\<close> insert.hyps Fs have pFs: "card ?pF = fact (n - 1)"
   347       by auto
   347       by auto
   348     then have "finite ?pF"
   348     then have "finite ?pF"
   349       by (auto intro: card_ge_0_finite)
   349       by (auto intro: card_ge_0_finite)
   381           by simp
   381           by simp
   382       }
   382       }
   383       then show ?thesis
   383       then show ?thesis
   384         unfolding inj_on_def by blast
   384         unfolding inj_on_def by blast
   385     qed
   385     qed
   386     from \<open>x \<notin> F\<close> \<open>finite F\<close> card.insert_remove have "n \<noteq> 0"
   386     from \<open>x \<notin> F\<close> \<open>finite F\<close> card_insert have "n \<noteq> 0"
   387       by auto
   387       by auto
   388     then have "\<exists>m. n = Suc m"
   388     then have "\<exists>m. n = Suc m"
   389       by presburger
   389       by presburger
   390     then obtain m where n: "n = Suc m"
   390     then obtain m where n: "n = Suc m"
   391       by blast
   391       by blast
   392     from pFs card.insert_remove have *: "card ?xF = fact n"
   392     from pFs card_insert have *: "card ?xF = fact n"
   393       unfolding xfgpF' card_image[OF ginj]
   393       unfolding xfgpF' card_image[OF ginj]
   394       using \<open>finite F\<close> \<open>finite ?pF\<close>
   394       using \<open>finite F\<close> \<open>finite ?pF\<close>
   395       by (simp only: Collect_case_prod Collect_mem_eq card_cartesian_product) (simp add: n)
   395       by (simp only: Collect_case_prod Collect_mem_eq card_cartesian_product) (simp add: n)
   396     from finite_imageI[OF pF'f, of ?g] have xFf: "finite ?xF"
   396     from finite_imageI[OF pF'f, of ?g] have xFf: "finite ?xF"
   397       by (simp add: xfgpF' n)
   397       by (simp add: xfgpF' n)