src/HOL/Lattices_Big.thy
changeset 67613 ce654b0e6d69
parent 67566 c555f1778dd8
child 67969 83c8cafdebe8
equal deleted inserted replaced
67610:4939494ed791 67613:ce654b0e6d69
   709   next
   709   next
   710     let ?B = "A - {Max A}" 
   710     let ?B = "A - {Max A}" 
   711     let ?A = "insert (Max A) ?B"
   711     let ?A = "insert (Max A) ?B"
   712     have "finite ?B" using \<open>finite A\<close> by simp
   712     have "finite ?B" using \<open>finite A\<close> by simp
   713     assume "A \<noteq> {}"
   713     assume "A \<noteq> {}"
   714     with \<open>finite A\<close> have "Max A : A" by auto
   714     with \<open>finite A\<close> have "Max A \<in> A" by auto
   715     then have A: "?A = A" using insert_Diff_single insert_absorb by auto
   715     then have A: "?A = A" using insert_Diff_single insert_absorb by auto
   716     then have "P ?B" using \<open>P {}\<close> step IH [of ?B] by blast
   716     then have "P ?B" using \<open>P {}\<close> step IH [of ?B] by blast
   717     moreover 
   717     moreover 
   718     have "\<forall>a\<in>?B. a < Max A" using Max_ge [OF \<open>finite A\<close>] by fastforce
   718     have "\<forall>a\<in>?B. a < Max A" using Max_ge [OF \<open>finite A\<close>] by fastforce
   719     ultimately show "P A" using A insert_Diff_single step [OF \<open>finite ?B\<close>] by fastforce
   719     ultimately show "P A" using A insert_Diff_single step [OF \<open>finite ?B\<close>] by fastforce
   903 lemma ex_min_if_finite:
   903 lemma ex_min_if_finite:
   904   "\<lbrakk> finite S; S \<noteq> {} \<rbrakk> \<Longrightarrow> \<exists>m\<in>S. \<not>(\<exists>x\<in>S. x < (m::'a::order))"
   904   "\<lbrakk> finite S; S \<noteq> {} \<rbrakk> \<Longrightarrow> \<exists>m\<in>S. \<not>(\<exists>x\<in>S. x < (m::'a::order))"
   905 by(induction rule: finite.induct) (auto intro: order.strict_trans)
   905 by(induction rule: finite.induct) (auto intro: order.strict_trans)
   906 
   906 
   907 lemma ex_is_arg_min_if_finite: fixes f :: "'a \<Rightarrow> 'b :: order"
   907 lemma ex_is_arg_min_if_finite: fixes f :: "'a \<Rightarrow> 'b :: order"
   908 shows "\<lbrakk> finite S; S \<noteq> {} \<rbrakk> \<Longrightarrow> \<exists>x. is_arg_min f (\<lambda>x. x : S) x"
   908 shows "\<lbrakk> finite S; S \<noteq> {} \<rbrakk> \<Longrightarrow> \<exists>x. is_arg_min f (\<lambda>x. x \<in> S) x"
   909 unfolding is_arg_min_def
   909 unfolding is_arg_min_def
   910 using ex_min_if_finite[of "f ` S"]
   910 using ex_min_if_finite[of "f ` S"]
   911 by auto
   911 by auto
   912 
   912 
   913 lemma arg_min_SOME_Min:
   913 lemma arg_min_SOME_Min: