src/HOL/Order_Relation.thy
changeset 61799 4cf66f21b764
parent 60758 d8d85a8172b5
child 63561 fba08009ff3e
equal deleted inserted replaced
61798:27f3c10b0b50 61799:4cf66f21b764
   178 
   178 
   179 
   179 
   180 subsubsection \<open>The upper and lower bounds operators\<close>
   180 subsubsection \<open>The upper and lower bounds operators\<close>
   181 
   181 
   182 text\<open>Here we define upper (``above") and lower (``below") bounds operators.
   182 text\<open>Here we define upper (``above") and lower (``below") bounds operators.
   183 We think of @{text "r"} as a {\em non-strict} relation.  The suffix ``S"
   183 We think of \<open>r\<close> as a {\em non-strict} relation.  The suffix ``S"
   184 at the names of some operators indicates that the bounds are strict -- e.g.,
   184 at the names of some operators indicates that the bounds are strict -- e.g.,
   185 @{text "underS a"} is the set of all strict lower bounds of @{text "a"} (w.r.t. @{text "r"}).
   185 \<open>underS a\<close> is the set of all strict lower bounds of \<open>a\<close> (w.r.t. \<open>r\<close>).
   186 Capitalization of the first letter in the name reminds that the operator acts on sets, rather
   186 Capitalization of the first letter in the name reminds that the operator acts on sets, rather
   187 than on individual elements.\<close>
   187 than on individual elements.\<close>
   188 
   188 
   189 definition under::"'a rel \<Rightarrow> 'a \<Rightarrow> 'a set"
   189 definition under::"'a rel \<Rightarrow> 'a \<Rightarrow> 'a set"
   190 where "under r a \<equiv> {b. (b,a) \<in> r}"
   190 where "under r a \<equiv> {b. (b,a) \<in> r}"
   211 where "AboveS r A \<equiv> {b \<in> Field r. \<forall>a \<in> A. b \<noteq> a \<and> (a,b) \<in> r}"
   211 where "AboveS r A \<equiv> {b \<in> Field r. \<forall>a \<in> A. b \<noteq> a \<and> (a,b) \<in> r}"
   212 
   212 
   213 definition ofilter :: "'a rel \<Rightarrow> 'a set \<Rightarrow> bool"
   213 definition ofilter :: "'a rel \<Rightarrow> 'a set \<Rightarrow> bool"
   214 where "ofilter r A \<equiv> (A \<le> Field r) \<and> (\<forall>a \<in> A. under r a \<le> A)"
   214 where "ofilter r A \<equiv> (A \<le> Field r) \<and> (\<forall>a \<in> A. under r a \<le> A)"
   215 
   215 
   216 text\<open>Note:  In the definitions of @{text "Above[S]"} and @{text "Under[S]"},
   216 text\<open>Note:  In the definitions of \<open>Above[S]\<close> and \<open>Under[S]\<close>,
   217   we bounded comprehension by @{text "Field r"} in order to properly cover
   217   we bounded comprehension by \<open>Field r\<close> in order to properly cover
   218   the case of @{text "A"} being empty.\<close>
   218   the case of \<open>A\<close> being empty.\<close>
   219 
   219 
   220 lemma underS_subset_under: "underS r a \<le> under r a"
   220 lemma underS_subset_under: "underS r a \<le> under r a"
   221 by(auto simp add: underS_def under_def)
   221 by(auto simp add: underS_def under_def)
   222 
   222 
   223 lemma underS_notIn: "a \<notin> underS r a"
   223 lemma underS_notIn: "a \<notin> underS r a"
   360    qed
   360    qed
   361   }
   361   }
   362   ultimately show ?thesis using R_def by blast
   362   ultimately show ?thesis using R_def by blast
   363 qed
   363 qed
   364 
   364 
   365 text \<open>The next lemma is a variation of @{text "wf_eq_minimal"} from Wellfounded,
   365 text \<open>The next lemma is a variation of \<open>wf_eq_minimal\<close> from Wellfounded,
   366 allowing one to assume the set included in the field.\<close>
   366 allowing one to assume the set included in the field.\<close>
   367 
   367 
   368 lemma wf_eq_minimal2:
   368 lemma wf_eq_minimal2:
   369 "wf r = (\<forall>A. A <= Field r \<and> A \<noteq> {} \<longrightarrow> (\<exists>a \<in> A. \<forall>a' \<in> A. \<not> (a',a) \<in> r))"
   369 "wf r = (\<forall>A. A <= Field r \<and> A \<noteq> {} \<longrightarrow> (\<exists>a \<in> A. \<forall>a' \<in> A. \<not> (a',a) \<in> r))"
   370 proof-
   370 proof-