src/ZF/Trancl.thy
changeset 45602 2a858377c3d2
parent 35762 af3ff2ba4c54
child 46820 c656222c4dc1
equal deleted inserted replaced
45601:d5178f19b671 45602:2a858377c3d2
   107 apply blast 
   107 apply blast 
   108 done
   108 done
   109 
   109 
   110 (* r^* = id(field(r)) Un ( r O r^* )    *)
   110 (* r^* = id(field(r)) Un ( r O r^* )    *)
   111 lemmas rtrancl_unfold =
   111 lemmas rtrancl_unfold =
   112      rtrancl_bnd_mono [THEN rtrancl_def [THEN def_lfp_unfold], standard]
   112      rtrancl_bnd_mono [THEN rtrancl_def [THEN def_lfp_unfold]]
   113 
   113 
   114 (** The relation rtrancl **)
   114 (** The relation rtrancl **)
   115 
   115 
   116 (*  r^* <= field(r) * field(r)  *)
   116 (*  r^* <= field(r) * field(r)  *)
   117 lemmas rtrancl_type = rtrancl_def [THEN def_lfp_subset, standard]
   117 lemmas rtrancl_type = rtrancl_def [THEN def_lfp_subset]
   118 
   118 
   119 lemma relation_rtrancl: "relation(r^*)"
   119 lemma relation_rtrancl: "relation(r^*)"
   120 apply (simp add: relation_def) 
   120 apply (simp add: relation_def) 
   121 apply (blast dest: rtrancl_type [THEN subsetD]) 
   121 apply (blast dest: rtrancl_type [THEN subsetD]) 
   122 done
   122 done
   176 apply (intro allI impI)
   176 apply (intro allI impI)
   177 apply (erule_tac b = z in rtrancl_induct, assumption)
   177 apply (erule_tac b = z in rtrancl_induct, assumption)
   178 apply (blast intro: rtrancl_into_rtrancl) 
   178 apply (blast intro: rtrancl_into_rtrancl) 
   179 done
   179 done
   180 
   180 
   181 lemmas rtrancl_trans = trans_rtrancl [THEN transD, standard]
   181 lemmas rtrancl_trans = trans_rtrancl [THEN transD]
   182 
   182 
   183 (*elimination of rtrancl -- by induction on a special formula*)
   183 (*elimination of rtrancl -- by induction on a special formula*)
   184 lemma rtranclE:
   184 lemma rtranclE:
   185     "[| <a,b> : r^*;  (a=b) ==> P;                        
   185     "[| <a,b> : r^*;  (a=b) ==> P;                        
   186         !!y.[| <a,y> : r^*;   <y,b> : r |] ==> P |]       
   186         !!y.[| <a,y> : r^*;   <y,b> : r |] ==> P |]       
   201                     trans_rtrancl [THEN transD, THEN compI])
   201                     trans_rtrancl [THEN transD, THEN compI])
   202 done
   202 done
   203 
   203 
   204 lemmas trans_on_trancl = trans_trancl [THEN trans_imp_trans_on]
   204 lemmas trans_on_trancl = trans_trancl [THEN trans_imp_trans_on]
   205 
   205 
   206 lemmas trancl_trans = trans_trancl [THEN transD, standard]
   206 lemmas trancl_trans = trans_trancl [THEN transD]
   207 
   207 
   208 (** Conversions between trancl and rtrancl **)
   208 (** Conversions between trancl and rtrancl **)
   209 
   209 
   210 lemma trancl_into_rtrancl: "<a,b> : r^+ ==> <a,b> : r^*"
   210 lemma trancl_into_rtrancl: "<a,b> : r^+ ==> <a,b> : r^*"
   211 apply (unfold trancl_def)
   211 apply (unfold trancl_def)