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