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