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