src/HOL/Lambda/Eta.ML
changeset 1465 5d7a7e439cec
parent 1431 be7c6d77e19c
child 1486 7b95d7b49f7a
equal deleted inserted replaced
1464:a608f83e3421 1465:5d7a7e439cec
    57 \                   (i < k & free t i | k < i & free t (pred i))";
    57 \                   (i < k & free t i | k < i & free t (pred i))";
    58 by(db.induct_tac "t" 1);
    58 by(db.induct_tac "t" 1);
    59 by(ALLGOALS(asm_full_simp_tac (addsplit (!simpset) addcongs [conj_cong])));
    59 by(ALLGOALS(asm_full_simp_tac (addsplit (!simpset) addcongs [conj_cong])));
    60 by(fast_tac HOL_cs 2);
    60 by(fast_tac HOL_cs 2);
    61 by(safe_tac (HOL_cs addSIs [iffI]));
    61 by(safe_tac (HOL_cs addSIs [iffI]));
    62 bd Suc_mono 1;
    62 by (dtac Suc_mono 1);
    63 by(ALLGOALS(Asm_full_simp_tac));
    63 by(ALLGOALS(Asm_full_simp_tac));
    64 by(dtac less_trans_Suc 1 THEN atac 1);
    64 by(dtac less_trans_Suc 1 THEN atac 1);
    65 by(dtac less_trans_Suc 2 THEN atac 2);
    65 by(dtac less_trans_Suc 2 THEN atac 2);
    66 by(ALLGOALS(Asm_full_simp_tac));
    66 by(ALLGOALS(Asm_full_simp_tac));
    67 qed "free_lift";
    67 qed "free_lift";
    75 by(fast_tac HOL_cs 2);
    75 by(fast_tac HOL_cs 2);
    76 by(safe_tac (HOL_cs addSIs [iffI]));
    76 by(safe_tac (HOL_cs addSIs [iffI]));
    77 by(ALLGOALS(Asm_simp_tac));
    77 by(ALLGOALS(Asm_simp_tac));
    78 by(fast_tac (HOL_cs addEs [less_imp_not_pred_less RS notE]) 1);
    78 by(fast_tac (HOL_cs addEs [less_imp_not_pred_less RS notE]) 1);
    79 by(fast_tac (HOL_cs addDs [less_not_sym]) 1);
    79 by(fast_tac (HOL_cs addDs [less_not_sym]) 1);
    80 bd Suc_mono 1;
    80 by (dtac Suc_mono 1);
    81 by(dtac less_interval1 1 THEN atac 1);
    81 by(dtac less_interval1 1 THEN atac 1);
    82 by(asm_full_simp_tac (simpset_of "Nat" addsimps [eq_sym_conv]) 1);
    82 by(asm_full_simp_tac (simpset_of "Nat" addsimps [eq_sym_conv]) 1);
    83 by(dtac less_trans_Suc 1 THEN atac 1);
    83 by(dtac less_trans_Suc 1 THEN atac 1);
    84 by(Asm_full_simp_tac 1);
    84 by(Asm_full_simp_tac 1);
    85 qed "free_subst";
    85 qed "free_subst";
    86 Addsimps [free_subst];
    86 Addsimps [free_subst];
    87 
    87 
    88 goal Eta.thy "!!s. s -e> t ==> !i. free t i = free s i";
    88 goal Eta.thy "!!s. s -e> t ==> !i. free t i = free s i";
    89 be (eta.mutual_induct RS spec RS spec RSN (2,rev_mp)) 1;
    89 by (etac (eta.mutual_induct RS spec RS spec RSN (2,rev_mp)) 1);
    90 by(ALLGOALS(asm_simp_tac (!simpset addsimps [decr_def] addcongs [conj_cong])));
    90 by(ALLGOALS(asm_simp_tac (!simpset addsimps [decr_def] addcongs [conj_cong])));
    91 bind_thm("free_eta",result() RS spec);
    91 bind_thm("free_eta",result() RS spec);
    92 
    92 
    93 goal Eta.thy "!!s. [| s -e> t; ~free s i |] ==> ~free t i";
    93 goal Eta.thy "!!s. [| s -e> t; ~free s i |] ==> ~free t i";
    94 by(asm_simp_tac (!simpset addsimps [free_eta]) 1);
    94 by(asm_simp_tac (!simpset addsimps [free_eta]) 1);
   100 by(fast_tac HOL_cs 1);
   100 by(fast_tac HOL_cs 1);
   101 by(fast_tac HOL_cs 1);
   101 by(fast_tac HOL_cs 1);
   102 bind_thm("subst_not_free", result() RS spec RS spec RS spec RS mp);
   102 bind_thm("subst_not_free", result() RS spec RS spec RS spec RS mp);
   103 
   103 
   104 goalw Eta.thy [decr_def] "!!s. ~free s i ==> s[t/i] = decr s i";
   104 goalw Eta.thy [decr_def] "!!s. ~free s i ==> s[t/i] = decr s i";
   105 be subst_not_free 1;
   105 by (etac subst_not_free 1);
   106 qed "subst_decr";
   106 qed "subst_decr";
   107 
   107 
   108 goal Eta.thy "!!s. s -e> t ==> !u i. s[u/i] -e> t[u/i]";
   108 goal Eta.thy "!!s. s -e> t ==> !u i. s[u/i] -e> t[u/i]";
   109 be (eta.mutual_induct RS spec RS spec RSN (2,rev_mp)) 1;
   109 by (etac (eta.mutual_induct RS spec RS spec RSN (2,rev_mp)) 1);
   110 by(ALLGOALS(asm_simp_tac (!simpset addsimps [subst_subst RS sym,decr_def])));
   110 by(ALLGOALS(asm_simp_tac (!simpset addsimps [subst_subst RS sym,decr_def])));
   111 by(asm_simp_tac (!simpset addsimps [subst_decr]) 1);
   111 by(asm_simp_tac (!simpset addsimps [subst_decr]) 1);
   112 bind_thm("eta_subst",result() RS spec RS spec);
   112 bind_thm("eta_subst",result() RS spec RS spec);
   113 Addsimps [eta_subst];
   113 Addsimps [eta_subst];
   114 
   114 
   115 goalw Eta.thy [decr_def] "!!s. s -e> t ==> decr s i -e> decr t i";
   115 goalw Eta.thy [decr_def] "!!s. s -e> t ==> decr s i -e> decr t i";
   116 be eta_subst 1;
   116 by (etac eta_subst 1);
   117 qed "eta_decr";
   117 qed "eta_decr";
   118 
   118 
   119 (*** Confluence of eta ***)
   119 (*** Confluence of eta ***)
   120 
   120 
   121 goalw Eta.thy [square_def,id_def]  "square eta eta (eta^=) (eta^=)";
   121 goalw Eta.thy [square_def,id_def]  "square eta eta (eta^=) (eta^=)";
   122 br eta.mutual_induct 1;
   122 by (rtac eta.mutual_induct 1);
   123 by(ALLGOALS(fast_tac (eta_cs addSEs [eta_decr,not_free_eta] addss !simpset)));
   123 by(ALLGOALS(fast_tac (eta_cs addSEs [eta_decr,not_free_eta] addss !simpset)));
   124 val lemma = result();
   124 val lemma = result();
   125 
   125 
   126 goal Eta.thy "confluent(eta)";
   126 goal Eta.thy "confluent(eta)";
   127 by(rtac (lemma RS square_reflcl_confluent) 1);
   127 by(rtac (lemma RS square_reflcl_confluent) 1);
   128 qed "eta_confluent";
   128 qed "eta_confluent";
   129 
   129 
   130 (*** Congruence rules for -e>> ***)
   130 (*** Congruence rules for -e>> ***)
   131 
   131 
   132 goal Eta.thy "!!s. s -e>> s' ==> Fun s -e>> Fun s'";
   132 goal Eta.thy "!!s. s -e>> s' ==> Fun s -e>> Fun s'";
   133 be rtrancl_induct 1;
   133 by (etac rtrancl_induct 1);
   134 by (ALLGOALS(fast_tac (eta_cs addIs [rtrancl_refl,rtrancl_into_rtrancl])));
   134 by (ALLGOALS(fast_tac (eta_cs addIs [rtrancl_refl,rtrancl_into_rtrancl])));
   135 qed "rtrancl_eta_Fun";
   135 qed "rtrancl_eta_Fun";
   136 
   136 
   137 goal Eta.thy "!!s. s -e>> s' ==> s @ t -e>> s' @ t";
   137 goal Eta.thy "!!s. s -e>> s' ==> s @ t -e>> s' @ t";
   138 be rtrancl_induct 1;
   138 by (etac rtrancl_induct 1);
   139 by (ALLGOALS(fast_tac (eta_cs addIs [rtrancl_refl,rtrancl_into_rtrancl])));
   139 by (ALLGOALS(fast_tac (eta_cs addIs [rtrancl_refl,rtrancl_into_rtrancl])));
   140 qed "rtrancl_eta_AppL";
   140 qed "rtrancl_eta_AppL";
   141 
   141 
   142 goal Eta.thy "!!s. t -e>> t' ==> s @ t -e>> s @ t'";
   142 goal Eta.thy "!!s. t -e>> t' ==> s @ t -e>> s @ t'";
   143 be rtrancl_induct 1;
   143 by (etac rtrancl_induct 1);
   144 by (ALLGOALS(fast_tac (eta_cs addIs [rtrancl_refl,rtrancl_into_rtrancl])));
   144 by (ALLGOALS(fast_tac (eta_cs addIs [rtrancl_refl,rtrancl_into_rtrancl])));
   145 qed "rtrancl_eta_AppR";
   145 qed "rtrancl_eta_AppR";
   146 
   146 
   147 goal Eta.thy "!!s. [| s -e>> s'; t -e>> t' |] ==> s @ t -e>> s' @ t'";
   147 goal Eta.thy "!!s. [| s -e>> s'; t -e>> t' |] ==> s @ t -e>> s' @ t'";
   148 by (fast_tac (eta_cs addSIs [rtrancl_eta_AppL,rtrancl_eta_AppR]
   148 by (fast_tac (eta_cs addSIs [rtrancl_eta_AppL,rtrancl_eta_AppR]
   150 qed "rtrancl_eta_App";
   150 qed "rtrancl_eta_App";
   151 
   151 
   152 (*** Commutation of beta and eta ***)
   152 (*** Commutation of beta and eta ***)
   153 
   153 
   154 goal Eta.thy "!s t. s -> t --> (!i. free t i --> free s i)";
   154 goal Eta.thy "!s t. s -> t --> (!i. free t i --> free s i)";
   155 br beta.mutual_induct 1;
   155 by (rtac beta.mutual_induct 1);
   156 by(ALLGOALS(Asm_full_simp_tac));
   156 by(ALLGOALS(Asm_full_simp_tac));
   157 bind_thm("free_beta", result() RS spec RS spec RS mp RS spec RS mp);
   157 bind_thm("free_beta", result() RS spec RS spec RS mp RS spec RS mp);
   158 
   158 
   159 goalw Eta.thy [decr_def] "!s t. s -> t --> (!i. decr s i -> decr t i)";
   159 goalw Eta.thy [decr_def] "!s t. s -> t --> (!i. decr s i -> decr t i)";
   160 br beta.mutual_induct 1;
   160 by (rtac beta.mutual_induct 1);
   161 by(ALLGOALS(asm_full_simp_tac (!simpset addsimps [subst_subst RS sym])));
   161 by(ALLGOALS(asm_full_simp_tac (!simpset addsimps [subst_subst RS sym])));
   162 bind_thm("beta_decr", result() RS spec RS spec RS mp RS spec);
   162 bind_thm("beta_decr", result() RS spec RS spec RS mp RS spec);
   163 
   163 
   164 goalw Eta.thy [decr_def]
   164 goalw Eta.thy [decr_def]
   165   "decr (Var i) k = (if i<=k then Var i else Var(pred i))";
   165   "decr (Var i) k = (if i<=k then Var i else Var(pred i))";
   184 by(fast_tac HOL_cs 1);
   184 by(fast_tac HOL_cs 1);
   185 qed "decr_not_free";
   185 qed "decr_not_free";
   186 Addsimps [decr_not_free];
   186 Addsimps [decr_not_free];
   187 
   187 
   188 goal Eta.thy "!s t. s -e> t --> (!i. lift s i -e> lift t i)";
   188 goal Eta.thy "!s t. s -e> t --> (!i. lift s i -e> lift t i)";
   189 br eta.mutual_induct 1;
   189 by (rtac eta.mutual_induct 1);
   190 by(ALLGOALS(asm_simp_tac (addsplit (!simpset) addsimps [decr_def])));
   190 by(ALLGOALS(asm_simp_tac (addsplit (!simpset) addsimps [decr_def])));
   191 by(asm_simp_tac (addsplit (!simpset) addsimps [subst_decr]) 1);
   191 by(asm_simp_tac (addsplit (!simpset) addsimps [subst_decr]) 1);
   192 bind_thm("eta_lift",result() RS spec RS spec RS mp RS spec);
   192 bind_thm("eta_lift",result() RS spec RS spec RS mp RS spec);
   193 Addsimps [eta_lift];
   193 Addsimps [eta_lift];
   194 
   194 
   199 by(fast_tac (eta_cs addSIs [rtrancl_eta_App]) 1);
   199 by(fast_tac (eta_cs addSIs [rtrancl_eta_App]) 1);
   200 by(fast_tac (eta_cs addSIs [rtrancl_eta_Fun,eta_lift]) 1);
   200 by(fast_tac (eta_cs addSIs [rtrancl_eta_Fun,eta_lift]) 1);
   201 bind_thm("rtrancl_eta_subst", result() RS spec RS spec RS spec RS mp);
   201 bind_thm("rtrancl_eta_subst", result() RS spec RS spec RS spec RS mp);
   202 
   202 
   203 goalw Eta.thy [square_def] "square beta eta (eta^*) (beta^=)";
   203 goalw Eta.thy [square_def] "square beta eta (eta^*) (beta^=)";
   204 br beta.mutual_induct 1;
   204 by (rtac beta.mutual_induct 1);
   205 by(strip_tac 1);
   205 by(strip_tac 1);
   206 bes eta_cases 1;
   206 by (eresolve_tac eta_cases 1);
   207 bes eta_cases 1;
   207 by (eresolve_tac eta_cases 1);
   208 by(fast_tac (eta_cs addss (!simpset addsimps [subst_decr])) 1);
   208 by(fast_tac (eta_cs addss (!simpset addsimps [subst_decr])) 1);
   209 by(fast_tac (eta_cs addIs [r_into_rtrancl,eta_subst]) 1);
   209 by(fast_tac (eta_cs addIs [r_into_rtrancl,eta_subst]) 1);
   210 by(fast_tac (eta_cs addIs [rtrancl_eta_subst]) 1);
   210 by(fast_tac (eta_cs addIs [rtrancl_eta_subst]) 1);
   211 by(fast_tac (eta_cs addIs [r_into_rtrancl,rtrancl_eta_AppL]) 1);
   211 by(fast_tac (eta_cs addIs [r_into_rtrancl,rtrancl_eta_AppL]) 1);
   212 by(fast_tac (eta_cs addIs [r_into_rtrancl,rtrancl_eta_AppR]) 1);
   212 by(fast_tac (eta_cs addIs [r_into_rtrancl,rtrancl_eta_AppR]) 1);