66 "[| <a,b> : r^*; \ |
66 "[| <a,b> : r^*; \ |
67 \ !!x. x: field(r) ==> P(<x,x>); \ |
67 \ !!x. x: field(r) ==> P(<x,x>); \ |
68 \ !!x y z.[| P(<x,y>); <x,y>: r^*; <y,z>: r |] ==> P(<x,z>) |] \ |
68 \ !!x y z.[| P(<x,y>); <x,y>: r^*; <y,z>: r |] ==> P(<x,z>) |] \ |
69 \ ==> P(<a,b>)"; |
69 \ ==> P(<a,b>)"; |
70 by (rtac ([rtrancl_def, rtrancl_bnd_mono, major] MRS def_induct) 1); |
70 by (rtac ([rtrancl_def, rtrancl_bnd_mono, major] MRS def_induct) 1); |
71 by (fast_tac (!claset addIs prems) 1); |
71 by (blast_tac (!claset addIs prems) 1); |
72 qed "rtrancl_full_induct"; |
72 qed "rtrancl_full_induct"; |
73 |
73 |
74 (*nice induction rule. |
74 (*nice induction rule. |
75 Tried adding the typing hypotheses y,z:field(r), but these |
75 Tried adding the typing hypotheses y,z:field(r), but these |
76 caused expensive case splits!*) |
76 caused expensive case splits!*) |
83 by (subgoal_tac "ALL y. <a,b> = <a,y> --> P(y)" 1); |
83 by (subgoal_tac "ALL y. <a,b> = <a,y> --> P(y)" 1); |
84 (*now solve first subgoal: this formula is sufficient*) |
84 (*now solve first subgoal: this formula is sufficient*) |
85 by (EVERY1 [etac (spec RS mp), rtac refl]); |
85 by (EVERY1 [etac (spec RS mp), rtac refl]); |
86 (*now do the induction*) |
86 (*now do the induction*) |
87 by (resolve_tac [major RS rtrancl_full_induct] 1); |
87 by (resolve_tac [major RS rtrancl_full_induct] 1); |
88 by (ALLGOALS (fast_tac (!claset addIs prems))); |
88 by (ALLGOALS (blast_tac (!claset addIs prems))); |
89 qed "rtrancl_induct"; |
89 qed "rtrancl_induct"; |
90 |
90 |
91 (*transitivity of transitive closure!! -- by induction.*) |
91 (*transitivity of transitive closure!! -- by induction.*) |
92 goalw Trancl.thy [trans_def] "trans(r^*)"; |
92 goalw Trancl.thy [trans_def] "trans(r^*)"; |
93 by (REPEAT (resolve_tac [allI,impI] 1)); |
93 by (REPEAT (resolve_tac [allI,impI] 1)); |
109 |
109 |
110 (**** The relation trancl ****) |
110 (**** The relation trancl ****) |
111 |
111 |
112 (*Transitivity of r^+ is proved by transitivity of r^* *) |
112 (*Transitivity of r^+ is proved by transitivity of r^* *) |
113 goalw Trancl.thy [trans_def,trancl_def] "trans(r^+)"; |
113 goalw Trancl.thy [trans_def,trancl_def] "trans(r^+)"; |
114 by (safe_tac (!claset)); |
114 by (blast_tac (!claset addIs [rtrancl_into_rtrancl RS |
115 by (rtac (rtrancl_into_rtrancl RS (trans_rtrancl RS transD RS compI)) 1); |
115 (trans_rtrancl RS transD RS compI)]) 1); |
116 by (REPEAT (assume_tac 1)); |
|
117 qed "trans_trancl"; |
116 qed "trans_trancl"; |
118 |
117 |
119 (** Conversions between trancl and rtrancl **) |
118 (** Conversions between trancl and rtrancl **) |
120 |
119 |
121 val [major] = goalw Trancl.thy [trancl_def] "<a,b> : r^+ ==> <a,b> : r^*"; |
120 goalw Trancl.thy [trancl_def] "!!r. <a,b> : r^+ ==> <a,b> : r^*"; |
122 by (resolve_tac [major RS compEpair] 1); |
121 by (blast_tac (!claset addIs [rtrancl_into_rtrancl]) 1); |
123 by (REPEAT (ares_tac [rtrancl_into_rtrancl] 1)); |
|
124 qed "trancl_into_rtrancl"; |
122 qed "trancl_into_rtrancl"; |
125 |
123 |
126 (*r^+ contains all pairs in r *) |
124 (*r^+ contains all pairs in r *) |
127 val [prem] = goalw Trancl.thy [trancl_def] "<a,b> : r ==> <a,b> : r^+"; |
125 goalw Trancl.thy [trancl_def] "!!r. <a,b> : r ==> <a,b> : r^+"; |
128 by (REPEAT (ares_tac [prem,compI,rtrancl_refl,fieldI1] 1)); |
126 by (blast_tac (!claset addSIs [rtrancl_refl]) 1); |
129 qed "r_into_trancl"; |
127 qed "r_into_trancl"; |
130 |
128 |
131 (*The premise ensures that r consists entirely of pairs*) |
129 (*The premise ensures that r consists entirely of pairs*) |
132 val prems = goal Trancl.thy "r <= Sigma(A,B) ==> r <= r^+"; |
130 goal Trancl.thy "!!r. r <= Sigma(A,B) ==> r <= r^+"; |
133 by (cut_facts_tac prems 1); |
|
134 by (blast_tac (!claset addIs [r_into_trancl]) 1); |
131 by (blast_tac (!claset addIs [r_into_trancl]) 1); |
135 qed "r_subset_trancl"; |
132 qed "r_subset_trancl"; |
136 |
133 |
137 (*intro rule by definition: from r^* and r *) |
134 (*intro rule by definition: from r^* and r *) |
138 val prems = goalw Trancl.thy [trancl_def] |
135 goalw Trancl.thy [trancl_def] |
139 "[| <a,b> : r^*; <b,c> : r |] ==> <a,c> : r^+"; |
136 "!!r. [| <a,b> : r^*; <b,c> : r |] ==> <a,c> : r^+"; |
140 by (REPEAT (resolve_tac ([compI]@prems) 1)); |
137 by (Blast_tac 1); |
141 qed "rtrancl_into_trancl1"; |
138 qed "rtrancl_into_trancl1"; |
142 |
139 |
143 (*intro rule from r and r^* *) |
140 (*intro rule from r and r^* *) |
144 val prems = goal Trancl.thy |
141 val prems = goal Trancl.thy |
145 "[| <a,b> : r; <b,c> : r^* |] ==> <a,c> : r^+"; |
142 "[| <a,b> : r; <b,c> : r^* |] ==> <a,c> : r^+"; |