21 goal Trancl.thy "(a,a) : r^*"; |
21 goal Trancl.thy "(a,a) : r^*"; |
22 by (stac rtrancl_unfold 1); |
22 by (stac rtrancl_unfold 1); |
23 by (Fast_tac 1); |
23 by (Fast_tac 1); |
24 qed "rtrancl_refl"; |
24 qed "rtrancl_refl"; |
25 |
25 |
|
26 Addsimps [rtrancl_refl]; |
|
27 AddSIs [rtrancl_refl]; |
|
28 |
|
29 |
26 (*Closure under composition with r*) |
30 (*Closure under composition with r*) |
27 val prems = goal Trancl.thy |
31 goal Trancl.thy "!!r. [| (a,b) : r^*; (b,c) : r |] ==> (a,c) : r^*"; |
28 "[| (a,b) : r^*; (b,c) : r |] ==> (a,c) : r^*"; |
|
29 by (stac rtrancl_unfold 1); |
32 by (stac rtrancl_unfold 1); |
30 by (fast_tac (!claset addIs prems) 1); |
33 by (Fast_tac 1); |
31 qed "rtrancl_into_rtrancl"; |
34 qed "rtrancl_into_rtrancl"; |
32 |
35 |
33 (*rtrancl of r contains r*) |
36 (*rtrancl of r contains r*) |
34 goal Trancl.thy "!!p. p : r ==> p : r^*"; |
37 goal Trancl.thy "!!p. p : r ==> p : r^*"; |
35 by (split_all_tac 1); |
38 by (split_all_tac 1); |
137 |
140 |
138 goal Trancl.thy "!!r. (x,y) : (converse r)^* ==> (x,y) : converse(r^*)"; |
141 goal Trancl.thy "!!r. (x,y) : (converse r)^* ==> (x,y) : converse(r^*)"; |
139 by (rtac converseI 1); |
142 by (rtac converseI 1); |
140 by (etac rtrancl_induct 1); |
143 by (etac rtrancl_induct 1); |
141 by (rtac rtrancl_refl 1); |
144 by (rtac rtrancl_refl 1); |
142 by (fast_tac (!claset addIs [r_into_rtrancl,rtrancl_trans]) 1); |
145 by (deepen_tac (!claset addIs [r_into_rtrancl,rtrancl_trans]) 0 1); |
143 qed "rtrancl_converseD"; |
146 qed "rtrancl_converseD"; |
144 |
147 |
145 goal Trancl.thy "!!r. (x,y) : converse(r^*) ==> (x,y) : (converse r)^*"; |
148 goal Trancl.thy "!!r. (x,y) : converse(r^*) ==> (x,y) : (converse r)^*"; |
146 by (dtac converseD 1); |
149 by (dtac converseD 1); |
147 by (etac rtrancl_induct 1); |
150 by (etac rtrancl_induct 1); |
148 by (rtac rtrancl_refl 1); |
151 by (rtac rtrancl_refl 1); |
149 by (fast_tac (!claset addIs [r_into_rtrancl,rtrancl_trans]) 1); |
152 by (deepen_tac (!claset addIs [r_into_rtrancl,rtrancl_trans]) 0 1); |
150 qed "rtrancl_converseI"; |
153 qed "rtrancl_converseI"; |
151 |
154 |
152 goal Trancl.thy "(converse r)^* = converse(r^*)"; |
155 goal Trancl.thy "(converse r)^* = converse(r^*)"; |
153 by (safe_tac (!claset addSIs [rtrancl_converseI])); |
156 by (safe_tac (!claset addSIs [rtrancl_converseI])); |
154 by (res_inst_tac [("p","x")] PairE 1); |
157 by (res_inst_tac [("p","x")] PairE 1); |
159 val major::prems = goal Trancl.thy |
162 val major::prems = goal Trancl.thy |
160 "[| (a,b) : r^*; P(b); \ |
163 "[| (a,b) : r^*; P(b); \ |
161 \ !!y z.[| (y,z) : r; (z,b) : r^*; P(z) |] ==> P(y) |] \ |
164 \ !!y z.[| (y,z) : r; (z,b) : r^*; P(z) |] ==> P(y) |] \ |
162 \ ==> P(a)"; |
165 \ ==> P(a)"; |
163 br ((major RS converseI RS rtrancl_converseI) RS rtrancl_induct) 1; |
166 br ((major RS converseI RS rtrancl_converseI) RS rtrancl_induct) 1; |
164 brs prems 1; |
167 brs prems 1; |
165 by(fast_tac (!claset addIs prems addSEs[converseD]addSDs[rtrancl_converseD])1); |
168 by(fast_tac (!claset addIs prems addSEs[converseD]addSDs[rtrancl_converseD])1); |
166 qed "converse_rtrancl_induct"; |
169 qed "converse_rtrancl_induct"; |
167 |
170 |
168 val prems = goal Trancl.thy |
171 val prems = goal Trancl.thy |
169 "[| ((a,b),(c,d)) : r^*; P c d; \ |
172 "[| ((a,b),(c,d)) : r^*; P c d; \ |