45 |
45 |
46 goal Residuals.thy |
46 goal Residuals.thy |
47 "!!u.residuals(u,v,w) ==> ALL w1.residuals(u,v,w1) --> w1 = w"; |
47 "!!u.residuals(u,v,w) ==> ALL w1.residuals(u,v,w1) --> w1 = w"; |
48 by (etac Sres.induct 1); |
48 by (etac Sres.induct 1); |
49 by (ALLGOALS Fast_tac); |
49 by (ALLGOALS Fast_tac); |
50 val residuals_function = result(); |
50 qed_spec_mp "residuals_function"; |
51 val res_is_func = residuals_function RS spec RS mp; |
|
52 |
51 |
53 goal Residuals.thy |
52 goal Residuals.thy |
54 "!!u.u~v ==> regular(v) --> (EX w.residuals(u,v,w))"; |
53 "!!u.u~v ==> regular(v) --> (EX w.residuals(u,v,w))"; |
55 by (etac Scomp.induct 1); |
54 by (etac Scomp.induct 1); |
56 by (ALLGOALS Fast_tac); |
55 by (ALLGOALS Fast_tac); |
57 val residuals_intro = result(); |
56 qed "residuals_intro"; |
58 |
57 |
59 val prems = goal Residuals.thy |
58 val prems = goal Residuals.thy |
60 "[|u~v; residuals(u,v,THE w. residuals(u, v, w))==> R; \ |
59 "[|u~v; residuals(u,v,THE w. residuals(u, v, w))==> R; \ |
61 \ regular(v)|] ==> R"; |
60 \ regular(v)|] ==> R"; |
62 by (cut_facts_tac prems 1); |
61 by (cut_facts_tac prems 1); |
63 by (resolve_tac prems 1); |
62 by (resolve_tac prems 1); |
64 by (resolve_tac [residuals_intro RS mp RS exE] 1); |
63 by (resolve_tac [residuals_intro RS mp RS exE] 1); |
65 by (resolve_tac [the_equality RS ssubst] 3); |
64 by (resolve_tac [the_equality RS ssubst] 3); |
66 by (ALLGOALS (fast_tac (!claset addIs [res_is_func]))); |
65 by (ALLGOALS (fast_tac (!claset addIs [residuals_function]))); |
67 val comp_resfuncE = result(); |
66 qed "comp_resfuncE"; |
68 |
67 |
69 |
68 |
70 (* ------------------------------------------------------------------------- *) |
69 (* ------------------------------------------------------------------------- *) |
71 (* Residual function *) |
70 (* Residual function *) |
72 (* ------------------------------------------------------------------------- *) |
71 (* ------------------------------------------------------------------------- *) |
73 |
72 |
74 val resfunc_cs = (!claset addIs [the_equality,res_is_func] |
73 val resfunc_cs = (!claset addIs [the_equality,residuals_function] |
75 addSEs [comp_resfuncE]); |
74 addSEs [comp_resfuncE]); |
76 |
75 |
77 goalw Residuals.thy [res_func_def] |
76 goalw Residuals.thy [res_func_def] |
78 "!!n.n:nat ==> Var(n) |> Var(n) = Var(n)"; |
77 "!!n.n:nat ==> Var(n) |> Var(n) = Var(n)"; |
79 by (fast_tac resfunc_cs 1); |
78 by (fast_tac resfunc_cs 1); |
80 val res_Var = result(); |
79 qed "res_Var"; |
81 |
80 |
82 goalw Residuals.thy [res_func_def] |
81 goalw Residuals.thy [res_func_def] |
83 "!!n.[|s~t; regular(t)|]==> Fun(s) |> Fun(t) = Fun(s |> t)"; |
82 "!!n.[|s~t; regular(t)|]==> Fun(s) |> Fun(t) = Fun(s |> t)"; |
84 by (fast_tac resfunc_cs 1); |
83 by (fast_tac resfunc_cs 1); |
85 val res_Fun = result(); |
84 qed "res_Fun"; |
86 |
85 |
87 goalw Residuals.thy [res_func_def] |
86 goalw Residuals.thy [res_func_def] |
88 "!!n.[|s~u; regular(u); t~v; regular(v); b:bool|]==> \ |
87 "!!n.[|s~u; regular(u); t~v; regular(v); b:bool|]==> \ |
89 \ App(b,s,t) |> App(0,u,v) = App(b, s |> u, t |> v)"; |
88 \ App(b,s,t) |> App(0,u,v) = App(b, s |> u, t |> v)"; |
90 by (fast_tac resfunc_cs 1); |
89 by (fast_tac resfunc_cs 1); |
91 val res_App = result(); |
90 qed "res_App"; |
92 |
91 |
93 goalw Residuals.thy [res_func_def] |
92 goalw Residuals.thy [res_func_def] |
94 "!!n.[|s~u; regular(u); t~v; regular(v); b:bool|]==> \ |
93 "!!n.[|s~u; regular(u); t~v; regular(v); b:bool|]==> \ |
95 \ App(b,Fun(s),t) |> App(1,Fun(u),v) = (t |> v)/ (s |> u)"; |
94 \ App(b,Fun(s),t) |> App(1,Fun(u),v) = (t |> v)/ (s |> u)"; |
96 by (fast_tac resfunc_cs 1); |
95 by (fast_tac resfunc_cs 1); |
97 val res_redex = result(); |
96 qed "res_redex"; |
98 |
97 |
99 goal Residuals.thy |
98 goal Residuals.thy |
100 "!!n.[|s~t; regular(t)|]==> regular(t) --> s |> t:redexes"; |
99 "!!n.[|s~t; regular(t)|]==> regular(t) --> s |> t:redexes"; |
101 by (etac Scomp.induct 1); |
100 by (etac Scomp.induct 1); |
102 by (ALLGOALS (asm_full_simp_tac |
101 by (ALLGOALS (asm_full_simp_tac |
104 setloop (SELECT_GOAL (safe_tac (!claset)))))); |
103 setloop (SELECT_GOAL (safe_tac (!claset)))))); |
105 by (dres_inst_tac [("psi", "Fun(?u) |> ?v : redexes")] asm_rl 1); |
104 by (dres_inst_tac [("psi", "Fun(?u) |> ?v : redexes")] asm_rl 1); |
106 by (asm_full_simp_tac |
105 by (asm_full_simp_tac |
107 (!simpset addsimps [res_Fun] |
106 (!simpset addsimps [res_Fun] |
108 setloop (SELECT_GOAL (safe_tac (!claset)))) 1); |
107 setloop (SELECT_GOAL (safe_tac (!claset)))) 1); |
109 val resfunc_type = result(); |
108 qed "resfunc_type"; |
110 |
109 |
111 Addsimps ([res_Var, res_Fun, res_App, res_redex, lift_rec_preserve_comp, |
110 Addsimps ([res_Var, res_Fun, res_App, res_redex, lift_rec_preserve_comp, |
112 lift_rec_preserve_reg, subst_rec_preserve_comp, resfunc_type, |
111 lift_rec_preserve_reg, subst_rec_preserve_comp, resfunc_type, |
113 subst_rec_preserve_reg] @ |
112 subst_rec_preserve_reg] @ |
114 redexes.free_iffs); |
113 redexes.free_iffs); |
121 |
120 |
122 goal Residuals.thy |
121 goal Residuals.thy |
123 "!!u.u<==v ==> u~v"; |
122 "!!u.u<==v ==> u~v"; |
124 by (etac Ssub.induct 1); |
123 by (etac Ssub.induct 1); |
125 by (ALLGOALS Asm_simp_tac); |
124 by (ALLGOALS Asm_simp_tac); |
126 val sub_comp = result(); |
125 qed "sub_comp"; |
127 |
126 |
128 goal Residuals.thy |
127 goal Residuals.thy |
129 "!!u.u<==v ==> regular(v) --> regular(u)"; |
128 "!!u.u<==v ==> regular(v) --> regular(u)"; |
130 by (etac Ssub.induct 1); |
129 by (etac Ssub.induct 1); |
131 by (ALLGOALS (asm_simp_tac res1L_ss)); |
130 by (ALLGOALS (asm_simp_tac res1L_ss)); |
132 val sub_preserve_reg = result(); |
131 qed "sub_preserve_reg"; |
133 |
132 |
134 goal Residuals.thy |
133 goal Residuals.thy |
135 "!!u.[|u~v; k:nat|]==> regular(v)--> (ALL n:nat. \ |
134 "!!u.[|u~v; k:nat|]==> regular(v)--> (ALL n:nat. \ |
136 \ lift_rec(u,n) |> lift_rec(v,n) = lift_rec(u |> v,n))"; |
135 \ lift_rec(u,n) |> lift_rec(v,n) = lift_rec(u |> v,n))"; |
137 by (etac Scomp.induct 1); |
136 by (etac Scomp.induct 1); |
138 by (Step_tac 1); |
137 by Safe_tac; |
139 by (ALLGOALS (asm_full_simp_tac ((addsplit (!simpset)) addsimps [lift_subst]))); |
138 by (ALLGOALS (asm_full_simp_tac ((addsplit (!simpset)) addsimps [lift_subst]))); |
140 by (dres_inst_tac [("psi", "ALL x:nat.Fun(?u(x)) |> ?v(x) = ?w(x)")] asm_rl 1); |
139 by (dres_inst_tac [("psi", "ALL x:nat.Fun(?u(x)) |> ?v(x) = ?w(x)")] asm_rl 1); |
141 by (Asm_full_simp_tac 1); |
140 by (Asm_full_simp_tac 1); |
142 val residuals_lift_rec = result(); |
141 qed "residuals_lift_rec"; |
143 |
142 |
144 goal Residuals.thy |
143 goal Residuals.thy |
145 "!!u.u1~u2 ==> ALL v1 v2.v1~v2 --> regular(v2) --> regular(u2) -->\ |
144 "!!u.u1~u2 ==> ALL v1 v2.v1~v2 --> regular(v2) --> regular(u2) -->\ |
146 \ (ALL n:nat.subst_rec(v1,u1,n) |> subst_rec(v2,u2,n) = \ |
145 \ (ALL n:nat.subst_rec(v1,u1,n) |> subst_rec(v2,u2,n) = \ |
147 \ subst_rec(v1 |> v2, u1 |> u2,n))"; |
146 \ subst_rec(v1 |> v2, u1 |> u2,n))"; |
148 by (etac Scomp.induct 1); |
147 by (etac Scomp.induct 1); |
149 by (Step_tac 1); |
148 by Safe_tac; |
150 by (ALLGOALS |
149 by (ALLGOALS |
151 (asm_full_simp_tac ((addsplit (!simpset)) addsimps ([residuals_lift_rec])))); |
150 (asm_full_simp_tac ((addsplit (!simpset)) addsimps ([residuals_lift_rec])))); |
152 by (dres_inst_tac [("psi", "ALL x.?P(x)")] asm_rl 1); |
151 by (dres_inst_tac [("psi", "ALL x.?P(x)")] asm_rl 1); |
153 by (asm_full_simp_tac (!simpset addsimps ([substitution])) 1); |
152 by (asm_full_simp_tac (!simpset addsimps ([substitution])) 1); |
154 val residuals_subst_rec = result(); |
153 qed "residuals_subst_rec"; |
155 |
154 |
156 |
155 |
157 goal Residuals.thy |
156 goal Residuals.thy |
158 "!!u.[|u1~u2; v1~v2; regular(u2); regular(v2)|]==>\ |
157 "!!u.[|u1~u2; v1~v2; regular(u2); regular(v2)|]==>\ |
159 \ (v1/u1) |> (v2/u2) = (v1 |> v2)/(u1 |> u2)"; |
158 \ (v1/u1) |> (v2/u2) = (v1 |> v2)/(u1 |> u2)"; |
160 by (asm_simp_tac (!simpset addsimps ([residuals_subst_rec])) 1); |
159 by (asm_simp_tac (!simpset addsimps ([residuals_subst_rec])) 1); |
161 val commutation = result(); |
160 qed "commutation"; |
162 |
161 |
163 (* ------------------------------------------------------------------------- *) |
162 (* ------------------------------------------------------------------------- *) |
164 (* Residuals are comp and regular *) |
163 (* Residuals are comp and regular *) |
165 (* ------------------------------------------------------------------------- *) |
164 (* ------------------------------------------------------------------------- *) |
166 |
165 |
171 by (dresolve_tac [spec RS mp RS mp RS mp] 1 |
170 by (dresolve_tac [spec RS mp RS mp RS mp] 1 |
172 THEN resolve_tac Scomp.intrs 1 THEN resolve_tac Scomp.intrs 2 |
171 THEN resolve_tac Scomp.intrs 1 THEN resolve_tac Scomp.intrs 2 |
173 THEN resolve_tac Sreg.intrs 3); |
172 THEN resolve_tac Sreg.intrs 3); |
174 by (REPEAT(assume_tac 1)); |
173 by (REPEAT(assume_tac 1)); |
175 by (asm_full_simp_tac res1L_ss 1); |
174 by (asm_full_simp_tac res1L_ss 1); |
176 val residuals_preserve_comp = result(); |
175 qed_spec_mp "residuals_preserve_comp"; |
177 |
176 |
178 |
177 |
179 goal Residuals.thy |
178 goal Residuals.thy |
180 "!!u.u~v ==> regular(u) --> regular(v) --> regular(u|>v)"; |
179 "!!u.u~v ==> regular(u) --> regular(v) --> regular(u|>v)"; |
181 by (etac Scomp.induct 1); |
180 by (etac Scomp.induct 1); |
182 by (safe_tac (!claset)); |
181 by (safe_tac (!claset)); |
183 by (TRYALL (dres_inst_tac [("psi", "regular(Fun(?u) |> ?v)")] asm_rl)); |
182 by (TRYALL (dres_inst_tac [("psi", "regular(Fun(?u) |> ?v)")] asm_rl)); |
184 by (ALLGOALS (asm_full_simp_tac res1L_ss)); |
183 by (ALLGOALS (asm_full_simp_tac res1L_ss)); |
185 val residuals_preserve_reg = result(); |
184 qed "residuals_preserve_reg"; |
186 |
185 |
187 (* ------------------------------------------------------------------------- *) |
186 (* ------------------------------------------------------------------------- *) |
188 (* Preservation lemma *) |
187 (* Preservation lemma *) |
189 (* ------------------------------------------------------------------------- *) |
188 (* ------------------------------------------------------------------------- *) |
190 |
189 |
191 goal Residuals.thy |
190 goal Residuals.thy |
192 "!!u.u~v ==> v ~ (u un v)"; |
191 "!!u.u~v ==> v ~ (u un v)"; |
193 by (etac Scomp.induct 1); |
192 by (etac Scomp.induct 1); |
194 by (ALLGOALS Asm_full_simp_tac); |
193 by (ALLGOALS Asm_full_simp_tac); |
195 val union_preserve_comp = result(); |
194 qed "union_preserve_comp"; |
196 |
195 |
197 goal Residuals.thy |
196 goal Residuals.thy |
198 "!!u.u ~ v ==> regular(v) --> u|>v = (u un v)|>v"; |
197 "!!u.u ~ v ==> regular(v) --> u|>v = (u un v)|>v"; |
199 by (etac Scomp.induct 1); |
198 by (etac Scomp.induct 1); |
200 by (safe_tac (!claset)); |
199 by (safe_tac (!claset)); |