src/HOL/Lambda/Eta.ML
changeset 2891 d8f254ad1ab9
parent 2159 e650a3f6f600
child 2922 580647a879cf
equal deleted inserted replaced
2890:f27002fc531d 2891:d8f254ad1ab9
    25 section "eta, subst and free";
    25 section "eta, subst and free";
    26 
    26 
    27 goal Eta.thy "!i t u. ~free s i --> s[t/i] = s[u/i]";
    27 goal Eta.thy "!i t u. ~free s i --> s[t/i] = s[u/i]";
    28 by (dB.induct_tac "s" 1);
    28 by (dB.induct_tac "s" 1);
    29 by (ALLGOALS(simp_tac (addsplit (!simpset))));
    29 by (ALLGOALS(simp_tac (addsplit (!simpset))));
    30 by (fast_tac HOL_cs 1);
    30 by (Blast_tac 1);
    31 by (fast_tac HOL_cs 1);
    31 by (Blast_tac 1);
    32 qed_spec_mp "subst_not_free";
    32 qed_spec_mp "subst_not_free";
    33 Addsimps [subst_not_free RS eqTrueI];
    33 Addsimps [subst_not_free RS eqTrueI];
    34 
    34 
    35 goal Eta.thy "!i k. free (lift t k) i = \
    35 goal Eta.thy "!i k. free (lift t k) i = \
    36 \                   (i < k & free t i | k < i & free t (pred i))";
    36 \                   (i < k & free t i | k < i & free t (pred i))";
    37 by (dB.induct_tac "t" 1);
    37 by (dB.induct_tac "t" 1);
    38 by (ALLGOALS(asm_full_simp_tac (addsplit (!simpset) addcongs [conj_cong])));
    38 by (ALLGOALS(asm_full_simp_tac (addsplit (!simpset) addcongs [conj_cong])));
    39 by (fast_tac HOL_cs 2);
    39 by (Blast_tac 2);
    40 by(simp_tac (!simpset addsimps [pred_def]
    40 by(simp_tac (!simpset addsimps [pred_def]
    41                       setloop (split_tac [expand_nat_case])) 1);
    41                       setloop (split_tac [expand_nat_case])) 1);
    42 by (safe_tac HOL_cs);
    42 by (safe_tac HOL_cs);
    43 by (ALLGOALS trans_tac);
    43 by (ALLGOALS trans_tac);
    44 qed "free_lift";
    44 qed "free_lift";
    46 
    46 
    47 goal Eta.thy "!i k t. free (s[t/k]) i = \
    47 goal Eta.thy "!i k t. free (s[t/k]) i = \
    48 \              (free s k & free t i | free s (if i<k then i else Suc i))";
    48 \              (free s k & free t i | free s (if i<k then i else Suc i))";
    49 by (dB.induct_tac "s" 1);
    49 by (dB.induct_tac "s" 1);
    50 by (Asm_simp_tac 2);
    50 by (Asm_simp_tac 2);
    51 by (Fast_tac 2);
    51 by (Blast_tac 2);
    52 by (asm_full_simp_tac (addsplit (!simpset)) 2);
    52 by (asm_full_simp_tac (addsplit (!simpset)) 2);
    53 by(simp_tac (!simpset addsimps [pred_def,subst_Var]
    53 by(simp_tac (!simpset addsimps [pred_def,subst_Var]
    54                       setloop (split_tac [expand_if,expand_nat_case])) 1);
    54                       setloop (split_tac [expand_if,expand_nat_case])) 1);
    55 by (safe_tac (HOL_cs addSEs [nat_neqE]));
    55 by (safe_tac (HOL_cs addSEs [nat_neqE]));
    56 by (ALLGOALS trans_tac);
    56 by (ALLGOALS trans_tac);
    92 
    92 
    93 section "Congruence rules for -e>>";
    93 section "Congruence rules for -e>>";
    94 
    94 
    95 goal Eta.thy "!!s. s -e>> s' ==> Abs s -e>> Abs s'";
    95 goal Eta.thy "!!s. s -e>> s' ==> Abs s -e>> Abs s'";
    96 by (etac rtrancl_induct 1);
    96 by (etac rtrancl_induct 1);
    97 by (ALLGOALS(fast_tac (!claset addIs [rtrancl_refl,rtrancl_into_rtrancl])));
    97 by (ALLGOALS(blast_tac (!claset addIs [rtrancl_refl,rtrancl_into_rtrancl])));
    98 qed "rtrancl_eta_Abs";
    98 qed "rtrancl_eta_Abs";
    99 
    99 
   100 goal Eta.thy "!!s. s -e>> s' ==> s @ t -e>> s' @ t";
   100 goal Eta.thy "!!s. s -e>> s' ==> s @ t -e>> s' @ t";
   101 by (etac rtrancl_induct 1);
   101 by (etac rtrancl_induct 1);
   102 by (ALLGOALS(fast_tac (!claset addIs [rtrancl_refl,rtrancl_into_rtrancl])));
   102 by (ALLGOALS(blast_tac (!claset addIs [rtrancl_refl,rtrancl_into_rtrancl])));
   103 qed "rtrancl_eta_AppL";
   103 qed "rtrancl_eta_AppL";
   104 
   104 
   105 goal Eta.thy "!!s. t -e>> t' ==> s @ t -e>> s @ t'";
   105 goal Eta.thy "!!s. t -e>> t' ==> s @ t -e>> s @ t'";
   106 by (etac rtrancl_induct 1);
   106 by (etac rtrancl_induct 1);
   107 by (ALLGOALS(fast_tac (!claset addIs [rtrancl_refl,rtrancl_into_rtrancl])));
   107 by (ALLGOALS(blast_tac (!claset addIs [rtrancl_refl,rtrancl_into_rtrancl])));
   108 qed "rtrancl_eta_AppR";
   108 qed "rtrancl_eta_AppR";
   109 
   109 
   110 goal Eta.thy "!!s. [| s -e>> s'; t -e>> t' |] ==> s @ t -e>> s' @ t'";
   110 goal Eta.thy "!!s. [| s -e>> s'; t -e>> t' |] ==> s @ t -e>> s' @ t'";
   111 by (deepen_tac (!claset addSIs [rtrancl_eta_AppL,rtrancl_eta_AppR]
   111 by (deepen_tac (!claset addSIs [rtrancl_eta_AppL,rtrancl_eta_AppR]
   112                      addIs [rtrancl_trans]) 2 1);
   112                      addIs [rtrancl_trans]) 2 1);
   140 Addsimps [eta_lift];
   140 Addsimps [eta_lift];
   141 
   141 
   142 goal Eta.thy "!s t i. s -e> t --> u[s/i] -e>> u[t/i]";
   142 goal Eta.thy "!s t i. s -e> t --> u[s/i] -e>> u[t/i]";
   143 by (dB.induct_tac "u" 1);
   143 by (dB.induct_tac "u" 1);
   144 by (ALLGOALS(asm_simp_tac (addsplit (!simpset))));
   144 by (ALLGOALS(asm_simp_tac (addsplit (!simpset))));
   145 by (fast_tac (!claset addIs [r_into_rtrancl]) 1);
   145 by (blast_tac (!claset addIs [r_into_rtrancl]) 1);
   146 by (fast_tac (!claset addSIs [rtrancl_eta_App]) 1);
   146 by (blast_tac (!claset addSIs [rtrancl_eta_App]) 1);
   147 by (fast_tac (!claset addSIs [rtrancl_eta_Abs,eta_lift]) 1);
   147 by (blast_tac (!claset addSIs [rtrancl_eta_Abs,eta_lift]) 1);
   148 qed_spec_mp "rtrancl_eta_subst";
   148 qed_spec_mp "rtrancl_eta_subst";
   149 
   149 
   150 goalw Eta.thy [square_def] "square beta eta (eta^*) (beta^=)";
   150 goalw Eta.thy [square_def] "square beta eta (eta^*) (beta^=)";
   151 by (rtac (impI RS allI RS allI) 1);
   151 by (rtac (impI RS allI RS allI) 1);
   152 by (etac beta.induct 1);
   152 by (etac beta.induct 1);
   177   by (rtac notE 1);
   177   by (rtac notE 1);
   178    by (assume_tac 2);
   178    by (assume_tac 2);
   179   by (etac thin_rl 1);
   179   by (etac thin_rl 1);
   180   by (res_inst_tac [("dB","t")] dB_case_distinction 1);
   180   by (res_inst_tac [("dB","t")] dB_case_distinction 1);
   181     by (simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   181     by (simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   182     by (fast_tac (HOL_cs addDs [less_not_refl2]) 1);
   182     by (blast_tac (HOL_cs addDs [less_not_refl2]) 1);
   183    by (Simp_tac 1);
   183    by (Simp_tac 1);
   184   by (Simp_tac 1);
   184   by (Simp_tac 1);
   185  by (Asm_simp_tac 1);
   185  by (Asm_simp_tac 1);
   186  by (etac thin_rl 1);
   186  by (etac thin_rl 1);
   187  by (etac thin_rl 1);
   187  by (etac thin_rl 1);
   194  by (etac exE 1);
   194  by (etac exE 1);
   195  by (etac rev_mp 1);
   195  by (etac rev_mp 1);
   196  by (res_inst_tac [("dB","t")] dB_case_distinction 1);
   196  by (res_inst_tac [("dB","t")] dB_case_distinction 1);
   197    by (simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   197    by (simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   198   by (Simp_tac 1);
   198   by (Simp_tac 1);
   199   by (fast_tac HOL_cs 1);
   199   by (Blast_tac 1);
   200  by (Simp_tac 1);
   200  by (Simp_tac 1);
   201 by (Asm_simp_tac 1);
   201 by (Asm_simp_tac 1);
   202 by (etac thin_rl 1);
   202 by (etac thin_rl 1);
   203 by (rtac allI 1);
   203 by (rtac allI 1);
   204 by (rtac iffI 1);
   204 by (rtac iffI 1);
   209 by (etac rev_mp 1);
   209 by (etac rev_mp 1);
   210 by (res_inst_tac [("dB","t")] dB_case_distinction 1);
   210 by (res_inst_tac [("dB","t")] dB_case_distinction 1);
   211   by (simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   211   by (simp_tac (!simpset setloop (split_tac [expand_if])) 1);
   212  by (Simp_tac 1);
   212  by (Simp_tac 1);
   213 by (Simp_tac 1);
   213 by (Simp_tac 1);
   214 by (fast_tac HOL_cs 1);
   214 by (Blast_tac 1);
   215 qed_spec_mp "not_free_iff_lifted";
   215 qed_spec_mp "not_free_iff_lifted";
   216 
   216 
   217 goal Eta.thy "(!s u. (~free s 0) --> R(Abs(s @ Var 0))(s[u/0])) = \
   217 goal Eta.thy "(!s u. (~free s 0) --> R(Abs(s @ Var 0))(s[u/0])) = \
   218 \             (!s. R(Abs(lift s 0 @ Var 0))(s))";
   218 \             (!s. R(Abs(lift s 0 @ Var 0))(s))";
   219 by (fast_tac (HOL_cs addss (!simpset addsimps [not_free_iff_lifted])) 1);
   219 by (fast_tac (HOL_cs addss (!simpset addsimps [not_free_iff_lifted])) 1);