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); |
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); |