src/ZF/Resid/Residuals.ML
changeset 3734 33f355f56f82
parent 2469 b50b8c0eec01
child 3840 e0baea4d485a
equal deleted inserted replaced
3733:1baedb1d4627 3734:33f355f56f82
    45 
    45 
    46 goal Residuals.thy 
    46 goal Residuals.thy 
    47     "!!u.residuals(u,v,w) ==> ALL w1.residuals(u,v,w1) --> w1 = w";
    47     "!!u.residuals(u,v,w) ==> ALL w1.residuals(u,v,w1) --> w1 = w";
    48 by (etac Sres.induct 1);
    48 by (etac Sres.induct 1);
    49 by (ALLGOALS Fast_tac);
    49 by (ALLGOALS Fast_tac);
    50 val residuals_function = result();
    50 qed_spec_mp "residuals_function";
    51 val res_is_func  = residuals_function  RS spec RS mp;
       
    52 
    51 
    53 goal Residuals.thy 
    52 goal Residuals.thy 
    54     "!!u.u~v ==> regular(v) --> (EX w.residuals(u,v,w))";
    53     "!!u.u~v ==> regular(v) --> (EX w.residuals(u,v,w))";
    55 by (etac Scomp.induct 1);
    54 by (etac Scomp.induct 1);
    56 by (ALLGOALS Fast_tac);
    55 by (ALLGOALS Fast_tac);
    57 val residuals_intro = result();
    56 qed "residuals_intro";
    58 
    57 
    59 val prems = goal  Residuals.thy 
    58 val prems = goal  Residuals.thy 
    60     "[|u~v; residuals(u,v,THE w. residuals(u, v, w))==> R; \
    59     "[|u~v; residuals(u,v,THE w. residuals(u, v, w))==> R; \
    61 \      regular(v)|] ==> R";
    60 \      regular(v)|] ==> R";
    62 by (cut_facts_tac prems 1);
    61 by (cut_facts_tac prems 1);
    63 by (resolve_tac prems 1);
    62 by (resolve_tac prems 1);
    64 by (resolve_tac [residuals_intro RS mp RS exE] 1);
    63 by (resolve_tac [residuals_intro RS mp RS exE] 1);
    65 by (resolve_tac [the_equality RS ssubst] 3);
    64 by (resolve_tac [the_equality RS ssubst] 3);
    66 by (ALLGOALS (fast_tac (!claset addIs [res_is_func])));
    65 by (ALLGOALS (fast_tac (!claset addIs [residuals_function])));
    67 val comp_resfuncE = result();
    66 qed "comp_resfuncE";
    68 
    67 
    69 
    68 
    70 (* ------------------------------------------------------------------------- *)
    69 (* ------------------------------------------------------------------------- *)
    71 (*               Residual function                                           *)
    70 (*               Residual function                                           *)
    72 (* ------------------------------------------------------------------------- *)
    71 (* ------------------------------------------------------------------------- *)
    73 
    72 
    74 val resfunc_cs = (!claset addIs  [the_equality,res_is_func] 
    73 val resfunc_cs = (!claset addIs  [the_equality,residuals_function] 
    75                           addSEs [comp_resfuncE]);
    74                           addSEs [comp_resfuncE]);
    76 
    75 
    77 goalw Residuals.thy [res_func_def]
    76 goalw Residuals.thy [res_func_def]
    78     "!!n.n:nat ==> Var(n) |> Var(n) = Var(n)";
    77     "!!n.n:nat ==> Var(n) |> Var(n) = Var(n)";
    79 by (fast_tac resfunc_cs 1);
    78 by (fast_tac resfunc_cs 1);
    80 val res_Var = result();
    79 qed "res_Var";
    81 
    80 
    82 goalw Residuals.thy [res_func_def]
    81 goalw Residuals.thy [res_func_def]
    83     "!!n.[|s~t; regular(t)|]==> Fun(s) |> Fun(t) = Fun(s |> t)";
    82     "!!n.[|s~t; regular(t)|]==> Fun(s) |> Fun(t) = Fun(s |> t)";
    84 by (fast_tac resfunc_cs 1);
    83 by (fast_tac resfunc_cs 1);
    85 val res_Fun = result();
    84 qed "res_Fun";
    86 
    85 
    87 goalw Residuals.thy [res_func_def]
    86 goalw Residuals.thy [res_func_def]
    88     "!!n.[|s~u; regular(u); t~v; regular(v); b:bool|]==> \
    87     "!!n.[|s~u; regular(u); t~v; regular(v); b:bool|]==> \
    89 \           App(b,s,t) |> App(0,u,v) = App(b, s |> u, t |> v)";
    88 \           App(b,s,t) |> App(0,u,v) = App(b, s |> u, t |> v)";
    90 by (fast_tac resfunc_cs 1);
    89 by (fast_tac resfunc_cs 1);
    91 val res_App = result();
    90 qed "res_App";
    92 
    91 
    93 goalw Residuals.thy [res_func_def]
    92 goalw Residuals.thy [res_func_def]
    94     "!!n.[|s~u; regular(u); t~v; regular(v); b:bool|]==> \
    93     "!!n.[|s~u; regular(u); t~v; regular(v); b:bool|]==> \
    95 \           App(b,Fun(s),t) |> App(1,Fun(u),v) = (t |> v)/ (s |> u)";
    94 \           App(b,Fun(s),t) |> App(1,Fun(u),v) = (t |> v)/ (s |> u)";
    96 by (fast_tac resfunc_cs 1);
    95 by (fast_tac resfunc_cs 1);
    97 val res_redex = result();
    96 qed "res_redex";
    98 
    97 
    99 goal Residuals.thy
    98 goal Residuals.thy
   100     "!!n.[|s~t; regular(t)|]==> regular(t) --> s |> t:redexes";
    99     "!!n.[|s~t; regular(t)|]==> regular(t) --> s |> t:redexes";
   101 by (etac Scomp.induct 1);
   100 by (etac Scomp.induct 1);
   102 by (ALLGOALS (asm_full_simp_tac 
   101 by (ALLGOALS (asm_full_simp_tac 
   104               setloop (SELECT_GOAL (safe_tac (!claset))))));
   103               setloop (SELECT_GOAL (safe_tac (!claset))))));
   105 by (dres_inst_tac [("psi", "Fun(?u) |> ?v : redexes")] asm_rl 1);
   104 by (dres_inst_tac [("psi", "Fun(?u) |> ?v : redexes")] asm_rl 1);
   106 by (asm_full_simp_tac 
   105 by (asm_full_simp_tac 
   107              (!simpset addsimps [res_Fun] 
   106              (!simpset addsimps [res_Fun] 
   108               setloop (SELECT_GOAL (safe_tac (!claset)))) 1);
   107               setloop (SELECT_GOAL (safe_tac (!claset)))) 1);
   109 val resfunc_type = result();
   108 qed "resfunc_type";
   110 
   109 
   111 Addsimps ([res_Var, res_Fun, res_App, res_redex, lift_rec_preserve_comp,
   110 Addsimps ([res_Var, res_Fun, res_App, res_redex, lift_rec_preserve_comp,
   112 	  lift_rec_preserve_reg, subst_rec_preserve_comp, resfunc_type,
   111 	  lift_rec_preserve_reg, subst_rec_preserve_comp, resfunc_type,
   113 	  subst_rec_preserve_reg] @
   112 	  subst_rec_preserve_reg] @
   114 	  redexes.free_iffs);
   113 	  redexes.free_iffs);
   121 
   120 
   122 goal Residuals.thy 
   121 goal Residuals.thy 
   123     "!!u.u<==v ==> u~v";
   122     "!!u.u<==v ==> u~v";
   124 by (etac Ssub.induct 1);
   123 by (etac Ssub.induct 1);
   125 by (ALLGOALS Asm_simp_tac);
   124 by (ALLGOALS Asm_simp_tac);
   126 val sub_comp = result();
   125 qed "sub_comp";
   127 
   126 
   128 goal Residuals.thy 
   127 goal Residuals.thy 
   129     "!!u.u<==v  ==> regular(v) --> regular(u)";
   128     "!!u.u<==v  ==> regular(v) --> regular(u)";
   130 by (etac Ssub.induct 1);
   129 by (etac Ssub.induct 1);
   131 by (ALLGOALS (asm_simp_tac res1L_ss));
   130 by (ALLGOALS (asm_simp_tac res1L_ss));
   132 val sub_preserve_reg = result();
   131 qed "sub_preserve_reg";
   133 
   132 
   134 goal Residuals.thy 
   133 goal Residuals.thy 
   135     "!!u.[|u~v; k:nat|]==> regular(v)--> (ALL n:nat.  \
   134     "!!u.[|u~v; k:nat|]==> regular(v)--> (ALL n:nat.  \
   136 \        lift_rec(u,n) |> lift_rec(v,n) = lift_rec(u |> v,n))";
   135 \        lift_rec(u,n) |> lift_rec(v,n) = lift_rec(u |> v,n))";
   137 by (etac Scomp.induct 1);
   136 by (etac Scomp.induct 1);
   138 by (Step_tac 1);
   137 by Safe_tac;
   139 by (ALLGOALS (asm_full_simp_tac ((addsplit (!simpset)) addsimps [lift_subst])));
   138 by (ALLGOALS (asm_full_simp_tac ((addsplit (!simpset)) addsimps [lift_subst])));
   140 by (dres_inst_tac [("psi", "ALL x:nat.Fun(?u(x)) |> ?v(x) = ?w(x)")] asm_rl 1);
   139 by (dres_inst_tac [("psi", "ALL x:nat.Fun(?u(x)) |> ?v(x) = ?w(x)")] asm_rl 1);
   141 by (Asm_full_simp_tac 1);
   140 by (Asm_full_simp_tac 1);
   142 val residuals_lift_rec = result();
   141 qed "residuals_lift_rec";
   143 
   142 
   144 goal Residuals.thy 
   143 goal Residuals.thy 
   145     "!!u.u1~u2 ==>  ALL v1 v2.v1~v2 --> regular(v2) --> regular(u2) -->\
   144     "!!u.u1~u2 ==>  ALL v1 v2.v1~v2 --> regular(v2) --> regular(u2) -->\
   146 \   (ALL n:nat.subst_rec(v1,u1,n) |> subst_rec(v2,u2,n) = \
   145 \   (ALL n:nat.subst_rec(v1,u1,n) |> subst_rec(v2,u2,n) = \
   147 \              subst_rec(v1 |> v2, u1 |> u2,n))";
   146 \              subst_rec(v1 |> v2, u1 |> u2,n))";
   148 by (etac Scomp.induct 1);
   147 by (etac Scomp.induct 1);
   149 by (Step_tac 1);
   148 by Safe_tac;
   150 by (ALLGOALS
   149 by (ALLGOALS
   151     (asm_full_simp_tac ((addsplit (!simpset)) addsimps ([residuals_lift_rec]))));
   150     (asm_full_simp_tac ((addsplit (!simpset)) addsimps ([residuals_lift_rec]))));
   152 by (dres_inst_tac [("psi", "ALL x.?P(x)")] asm_rl 1);
   151 by (dres_inst_tac [("psi", "ALL x.?P(x)")] asm_rl 1);
   153 by (asm_full_simp_tac (!simpset addsimps ([substitution])) 1);
   152 by (asm_full_simp_tac (!simpset addsimps ([substitution])) 1);
   154 val residuals_subst_rec = result();
   153 qed "residuals_subst_rec";
   155 
   154 
   156 
   155 
   157 goal Residuals.thy 
   156 goal Residuals.thy 
   158     "!!u.[|u1~u2; v1~v2; regular(u2); regular(v2)|]==>\
   157     "!!u.[|u1~u2; v1~v2; regular(u2); regular(v2)|]==>\
   159 \       (v1/u1) |> (v2/u2) = (v1 |> v2)/(u1 |> u2)";
   158 \       (v1/u1) |> (v2/u2) = (v1 |> v2)/(u1 |> u2)";
   160 by (asm_simp_tac (!simpset addsimps ([residuals_subst_rec])) 1);
   159 by (asm_simp_tac (!simpset addsimps ([residuals_subst_rec])) 1);
   161 val commutation = result();
   160 qed "commutation";
   162 
   161 
   163 (* ------------------------------------------------------------------------- *)
   162 (* ------------------------------------------------------------------------- *)
   164 (*     Residuals are comp and regular                                        *)
   163 (*     Residuals are comp and regular                                        *)
   165 (* ------------------------------------------------------------------------- *)
   164 (* ------------------------------------------------------------------------- *)
   166 
   165 
   171 by (dresolve_tac [spec RS mp RS mp RS mp] 1 
   170 by (dresolve_tac [spec RS mp RS mp RS mp] 1 
   172     THEN resolve_tac Scomp.intrs 1 THEN resolve_tac Scomp.intrs 2 
   171     THEN resolve_tac Scomp.intrs 1 THEN resolve_tac Scomp.intrs 2 
   173     THEN resolve_tac Sreg.intrs 3);
   172     THEN resolve_tac Sreg.intrs 3);
   174 by (REPEAT(assume_tac 1));
   173 by (REPEAT(assume_tac 1));
   175 by (asm_full_simp_tac res1L_ss 1);
   174 by (asm_full_simp_tac res1L_ss 1);
   176 val residuals_preserve_comp = result();
   175 qed_spec_mp "residuals_preserve_comp";
   177 
   176 
   178 
   177 
   179 goal Residuals.thy 
   178 goal Residuals.thy 
   180     "!!u.u~v ==> regular(u) --> regular(v) --> regular(u|>v)";
   179     "!!u.u~v ==> regular(u) --> regular(v) --> regular(u|>v)";
   181 by (etac Scomp.induct 1);
   180 by (etac Scomp.induct 1);
   182 by (safe_tac (!claset));
   181 by (safe_tac (!claset));
   183 by (TRYALL (dres_inst_tac [("psi", "regular(Fun(?u) |> ?v)")] asm_rl));
   182 by (TRYALL (dres_inst_tac [("psi", "regular(Fun(?u) |> ?v)")] asm_rl));
   184 by (ALLGOALS (asm_full_simp_tac res1L_ss));
   183 by (ALLGOALS (asm_full_simp_tac res1L_ss));
   185 val residuals_preserve_reg = result();
   184 qed "residuals_preserve_reg";
   186 
   185 
   187 (* ------------------------------------------------------------------------- *)
   186 (* ------------------------------------------------------------------------- *)
   188 (*     Preservation lemma                                                    *)
   187 (*     Preservation lemma                                                    *)
   189 (* ------------------------------------------------------------------------- *)
   188 (* ------------------------------------------------------------------------- *)
   190 
   189 
   191 goal Residuals.thy 
   190 goal Residuals.thy 
   192     "!!u.u~v ==> v ~ (u un v)";
   191     "!!u.u~v ==> v ~ (u un v)";
   193 by (etac Scomp.induct 1);
   192 by (etac Scomp.induct 1);
   194 by (ALLGOALS Asm_full_simp_tac);
   193 by (ALLGOALS Asm_full_simp_tac);
   195 val union_preserve_comp = result();
   194 qed "union_preserve_comp";
   196 
   195 
   197 goal Residuals.thy 
   196 goal Residuals.thy 
   198     "!!u.u ~ v ==> regular(v) --> u|>v = (u un v)|>v";
   197     "!!u.u ~ v ==> regular(v) --> u|>v = (u un v)|>v";
   199 by (etac Scomp.induct 1);
   198 by (etac Scomp.induct 1);
   200 by (safe_tac (!claset));
   199 by (safe_tac (!claset));
   202 by (ALLGOALS (asm_full_simp_tac (res1L_ss addsimps 
   201 by (ALLGOALS (asm_full_simp_tac (res1L_ss addsimps 
   203                                  [union_preserve_comp,comp_sym_iff])));
   202                                  [union_preserve_comp,comp_sym_iff])));
   204 by (asm_full_simp_tac (!simpset addsimps 
   203 by (asm_full_simp_tac (!simpset addsimps 
   205                        [union_preserve_comp RS comp_sym,
   204                        [union_preserve_comp RS comp_sym,
   206                         comp_sym RS union_preserve_comp RS comp_sym]) 1);
   205                         comp_sym RS union_preserve_comp RS comp_sym]) 1);
   207 val preservation1 = result();
   206 qed_spec_mp "preservation";
   208 
       
   209 val preservation = preservation1 RS mp;