src/HOL/MicroJava/BV/Semilat.thy
changeset 12566 fe20540bcf93
parent 12542 ff5e3f11e1ef
child 12773 a47f51daa6dc
equal deleted inserted replaced
12565:9df4b3934487 12566:fe20540bcf93
   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>