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