src/ZF/Trancl.ML
changeset 3016 15763781afb0
parent 2929 4eefc6c22d41
child 4091 771b1f6422a8
equal deleted inserted replaced
3015:65778b9d865f 3016:15763781afb0
    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^+";