src/HOL/Trancl.ML
changeset 1921 56a77911efe4
parent 1786 8a31d85d27b8
child 1985 84cf16192e03
equal deleted inserted replaced
1920:df683ce7aad8 1921:56a77911efe4
    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; \
   274 qed "trancl_subset_Sigma";
   277 qed "trancl_subset_Sigma";
   275 
   278 
   276 (* Don't add r_into_rtrancl: it messes up the proofs in Lambda *)
   279 (* Don't add r_into_rtrancl: it messes up the proofs in Lambda *)
   277 val trancl_cs = rel_cs addIs [rtrancl_refl];
   280 val trancl_cs = rel_cs addIs [rtrancl_refl];
   278 
   281 
   279 AddIs [rtrancl_refl];