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