src/HOL/Lambda/Lambda.ML
changeset 5184 9b8547a9496a
parent 5146 1ea751ae62b2
child 5261 ce3c25c8a694
equal deleted inserted replaced
5183:89f162de39cf 5184:9b8547a9496a
    64 
    64 
    65 Addsimps [subst_eq,subst_gt,subst_lt];
    65 Addsimps [subst_eq,subst_gt,subst_lt];
    66 
    66 
    67 Goal
    67 Goal
    68   "!i k. i < Suc k --> lift (lift t i) (Suc k) = lift (lift t k) i";
    68   "!i k. i < Suc k --> lift (lift t i) (Suc k) = lift (lift t k) i";
    69 by (dB.induct_tac "t" 1);
    69 by (induct_tac "t" 1);
    70 by (ALLGOALS(asm_simp_tac (simpset() addSolver cut_trans_tac)));
    70 by (ALLGOALS(asm_simp_tac (simpset() addSolver cut_trans_tac)));
    71 by (safe_tac HOL_cs);
    71 by (safe_tac HOL_cs);
    72 by (ALLGOALS trans_tac);
    72 by (ALLGOALS trans_tac);
    73 qed_spec_mp "lift_lift";
    73 qed_spec_mp "lift_lift";
    74 
    74 
    75 Goal "!i j s. j < Suc i --> lift (t[s/j]) i = (lift t (Suc i)) [lift s i / j]";
    75 Goal "!i j s. j < Suc i --> lift (t[s/j]) i = (lift t (Suc i)) [lift s i / j]";
    76 by (dB.induct_tac "t" 1);
    76 by (induct_tac "t" 1);
    77 by (ALLGOALS(asm_simp_tac (simpset() addsimps [diff_Suc,subst_Var,lift_lift]
    77 by (ALLGOALS(asm_simp_tac (simpset() addsimps [diff_Suc,subst_Var,lift_lift]
    78                                 addsplits [split_nat_case]
    78                                 addsplits [nat.split]
    79                                 addSolver cut_trans_tac)));
    79                                 addSolver cut_trans_tac)));
    80 by (safe_tac HOL_cs);
    80 by (safe_tac HOL_cs);
    81 by (ALLGOALS trans_tac);
    81 by (ALLGOALS trans_tac);
    82 qed "lift_subst";
    82 qed "lift_subst";
    83 Addsimps [lift_subst];
    83 Addsimps [lift_subst];
    84 
    84 
    85 Goal
    85 Goal
    86   "!i j s. i < Suc j --> lift (t[s/j]) i = (lift t i) [lift s i / Suc j]";
    86   "!i j s. i < Suc j --> lift (t[s/j]) i = (lift t i) [lift s i / Suc j]";
    87 by (dB.induct_tac "t" 1);
    87 by (induct_tac "t" 1);
    88 by (ALLGOALS(asm_simp_tac (simpset() addsimps [subst_Var,lift_lift]
    88 by (ALLGOALS(asm_simp_tac (simpset() addsimps [subst_Var,lift_lift]
    89                                 addSolver cut_trans_tac)));
    89                                 addSolver cut_trans_tac)));
    90 by (safe_tac (HOL_cs addSEs [nat_neqE]));
    90 by (safe_tac (HOL_cs addSEs [nat_neqE]));
    91 by (ALLGOALS trans_tac);
    91 by (ALLGOALS trans_tac);
    92 qed "lift_subst_lt";
    92 qed "lift_subst_lt";
    93 
    93 
    94 Goal "!k s. (lift t k)[s/k] = t";
    94 Goal "!k s. (lift t k)[s/k] = t";
    95 by (dB.induct_tac "t" 1);
    95 by (induct_tac "t" 1);
    96 by (ALLGOALS Asm_full_simp_tac);
    96 by (ALLGOALS Asm_full_simp_tac);
    97 qed "subst_lift";
    97 qed "subst_lift";
    98 Addsimps [subst_lift];
    98 Addsimps [subst_lift];
    99 
    99 
   100 
   100 
   101 Goal "!i j u v. i < Suc j --> t[lift v i / Suc j][u[v/j]/i] = t[u/i][v/j]";
   101 Goal "!i j u v. i < Suc j --> t[lift v i / Suc j][u[v/j]/i] = t[u/i][v/j]";
   102 by (dB.induct_tac "t" 1);
   102 by (induct_tac "t" 1);
   103 by (ALLGOALS(asm_simp_tac
   103 by (ALLGOALS(asm_simp_tac
   104       (simpset() addsimps [diff_Suc,subst_Var,lift_lift RS sym,lift_subst_lt]
   104       (simpset() addsimps [diff_Suc,subst_Var,lift_lift RS sym,lift_subst_lt]
   105                  delsplits [split_if]
   105                  delsplits [split_if]
   106                  addsplits [split_nat_case]
   106                  addsplits [nat.split]
   107                  addloop ("if",split_inside_tac[split_if])
   107                  addloop ("if",split_inside_tac[split_if])
   108                 addSolver cut_trans_tac)));
   108                 addSolver cut_trans_tac)));
   109 by (safe_tac (HOL_cs addSEs [nat_neqE]));
   109 by (safe_tac (HOL_cs addSEs [nat_neqE]));
   110 by (ALLGOALS trans_tac);
   110 by (ALLGOALS trans_tac);
   111 qed_spec_mp "subst_subst";
   111 qed_spec_mp "subst_subst";
   112 
   112 
   113 
   113 
   114 (*** Equivalence proof for optimized substitution ***)
   114 (*** Equivalence proof for optimized substitution ***)
   115 
   115 
   116 Goal "!k. liftn 0 t k = t";
   116 Goal "!k. liftn 0 t k = t";
   117 by (dB.induct_tac "t" 1);
   117 by (induct_tac "t" 1);
   118 by (ALLGOALS(asm_simp_tac(addsplit(simpset()))));
   118 by (ALLGOALS(asm_simp_tac(addsplit(simpset()))));
   119 qed "liftn_0";
   119 qed "liftn_0";
   120 Addsimps [liftn_0];
   120 Addsimps [liftn_0];
   121 
   121 
   122 Goal "!k. liftn (Suc n) t k = lift (liftn n t k) k";
   122 Goal "!k. liftn (Suc n) t k = lift (liftn n t k) k";
   123 by (dB.induct_tac "t" 1);
   123 by (induct_tac "t" 1);
   124 by (ALLGOALS(asm_simp_tac(addsplit(simpset()))));
   124 by (ALLGOALS(asm_simp_tac(addsplit(simpset()))));
   125 by (blast_tac (claset() addDs [add_lessD1]) 1);
   125 by (blast_tac (claset() addDs [add_lessD1]) 1);
   126 qed "liftn_lift";
   126 qed "liftn_lift";
   127 Addsimps [liftn_lift];
   127 Addsimps [liftn_lift];
   128 
   128 
   129 Goal "!n. substn t s n = t[liftn n s 0 / n]";
   129 Goal "!n. substn t s n = t[liftn n s 0 / n]";
   130 by (dB.induct_tac "t" 1);
   130 by (induct_tac "t" 1);
   131 by (ALLGOALS(asm_simp_tac(addsplit(simpset()))));
   131 by (ALLGOALS(asm_simp_tac(addsplit(simpset()))));
   132 qed "substn_subst_n";
   132 qed "substn_subst_n";
   133 Addsimps [substn_subst_n];
   133 Addsimps [substn_subst_n];
   134 
   134 
   135 Goal "substn t s 0 = t[s/0]";
   135 Goal "substn t s 0 = t[s/0]";