196 apply (case_tac "(y,x') : r^*") |
196 apply (case_tac "(y,x') : r^*") |
197 apply blast |
197 apply blast |
198 apply (blast elim: converse_rtranclE dest: single_valuedD) |
198 apply (blast elim: converse_rtranclE dest: single_valuedD) |
199 apply (rule exI) |
199 apply (rule exI) |
200 apply (rule conjI) |
200 apply (rule conjI) |
201 apply (blast intro: rtrancl_into_rtrancl2 dest: single_valuedD) |
201 apply (blast intro: converse_rtrancl_into_rtrancl dest: single_valuedD) |
202 apply (blast intro: rtrancl_into_rtrancl rtrancl_into_rtrancl2 |
202 apply (blast intro: rtrancl_into_rtrancl converse_rtrancl_into_rtrancl |
203 elim: converse_rtranclE dest: single_valuedD) |
203 elim: converse_rtranclE dest: single_valuedD) |
204 done |
204 done |
205 |
205 |
206 lemma single_valued_has_lubs [rule_format]: |
206 lemma single_valued_has_lubs [rule_format]: |
207 "[| single_valued r; (x,u) : r^* |] ==> (!y. (y,u) : r^* --> |
207 "[| single_valued r; (x,u) : r^* |] ==> (!y. (y,u) : r^* --> |
208 (EX z. is_lub (r^* ) x y z))" |
208 (EX z. is_lub (r^* ) x y z))" |
209 apply (erule converse_rtrancl_induct) |
209 apply (erule converse_rtrancl_induct) |
210 apply clarify |
210 apply clarify |
211 apply (erule converse_rtrancl_induct) |
211 apply (erule converse_rtrancl_induct) |
212 apply blast |
212 apply blast |
213 apply (blast intro: rtrancl_into_rtrancl2) |
213 apply (blast intro: converse_rtrancl_into_rtrancl) |
214 apply (blast intro: extend_lub) |
214 apply (blast intro: extend_lub) |
215 done |
215 done |
216 |
216 |
217 lemma some_lub_conv: |
217 lemma some_lub_conv: |
218 "[| acyclic r; is_lub (r^* ) x y u |] ==> some_lub (r^* ) x y = u" |
218 "[| acyclic r; is_lub (r^* ) x y u |] ==> some_lub (r^* ) x y = u" |
244 apply simp |
244 apply simp |
245 apply(rename_tac x x') |
245 apply(rename_tac x x') |
246 apply(subgoal_tac "r \<inter> {a. (x,a) \<in> r\<^sup>*} \<times> {b. (b,y) \<in> r\<^sup>*} = |
246 apply(subgoal_tac "r \<inter> {a. (x,a) \<in> r\<^sup>*} \<times> {b. (b,y) \<in> r\<^sup>*} = |
247 insert (x,x') (r \<inter> {a. (x', a) \<in> r\<^sup>*} \<times> {b. (b, y) \<in> r\<^sup>*})") |
247 insert (x,x') (r \<inter> {a. (x', a) \<in> r\<^sup>*} \<times> {b. (b, y) \<in> r\<^sup>*})") |
248 apply simp |
248 apply simp |
249 apply(blast intro:rtrancl_into_rtrancl2 |
249 apply(blast intro:converse_rtrancl_into_rtrancl |
250 elim:converse_rtranclE dest:single_valuedD) |
250 elim:converse_rtranclE dest:single_valuedD) |
251 done |
251 done |
252 |
252 |
253 |
253 |
254 lemma "\<lbrakk> acyclic r; !x y. (x,y) \<in> r \<longrightarrow> f x = y; is_lub (r\<^sup>*) x y u \<rbrakk> \<Longrightarrow> |
254 lemma "\<lbrakk> acyclic r; !x y. (x,y) \<in> r \<longrightarrow> f x = y; is_lub (r\<^sup>*) x y u \<rbrakk> \<Longrightarrow> |