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]"; |