19 |
19 |
20 lemma wfrank: "wf(r) ==> wfrank(r,a) = (\<Union>y \<in> r-``{a}. succ(wfrank(r,y)))" |
20 lemma wfrank: "wf(r) ==> wfrank(r,a) = (\<Union>y \<in> r-``{a}. succ(wfrank(r,y)))" |
21 by (subst wfrank_def [THEN def_wfrec], simp_all) |
21 by (subst wfrank_def [THEN def_wfrec], simp_all) |
22 |
22 |
23 lemma Ord_wfrank: "wf(r) ==> Ord(wfrank(r,a))" |
23 lemma Ord_wfrank: "wf(r) ==> Ord(wfrank(r,a))" |
24 apply (rule_tac a="a" in wf_induct, assumption) |
24 apply (rule_tac a=a in wf_induct, assumption) |
25 apply (subst wfrank, assumption) |
25 apply (subst wfrank, assumption) |
26 apply (rule Ord_succ [THEN Ord_UN], blast) |
26 apply (rule Ord_succ [THEN Ord_UN], blast) |
27 done |
27 done |
28 |
28 |
29 lemma wfrank_lt: "[|wf(r); <a,b> \<in> r|] ==> wfrank(r,a) < wfrank(r,b)" |
29 lemma wfrank_lt: "[|wf(r); <a,b> \<in> r|] ==> wfrank(r,a) < wfrank(r,b)" |
30 apply (rule_tac a1 = "b" in wfrank [THEN ssubst], assumption) |
30 apply (rule_tac a1 = b in wfrank [THEN ssubst], assumption) |
31 apply (rule UN_I [THEN ltI]) |
31 apply (rule UN_I [THEN ltI]) |
32 apply (simp add: Ord_wfrank vimage_iff)+ |
32 apply (simp add: Ord_wfrank vimage_iff)+ |
33 done |
33 done |
34 |
34 |
35 lemma Ord_wftype: "wf(r) ==> Ord(wftype(r))" |
35 lemma Ord_wftype: "wf(r) ==> Ord(wftype(r))" |
139 (\<exists>n[M]. n\<in>nat & |
139 (\<exists>n[M]. n\<in>nat & |
140 (\<exists>f[M]. f \<in> succ(n) -> A & |
140 (\<exists>f[M]. f \<in> succ(n) -> A & |
141 (\<exists>x[M]. \<exists>y[M]. p = <x,y> & f`0 = x & f`n = y) & |
141 (\<exists>x[M]. \<exists>y[M]. p = <x,y> & f`0 = x & f`n = y) & |
142 (\<forall>i\<in>n. <f`i, f`succ(i)> \<in> r)))" |
142 (\<forall>i\<in>n. <f`i, f`succ(i)> \<in> r)))" |
143 apply (simp add: rtran_closure_mem_def typed_apply_abs |
143 apply (simp add: rtran_closure_mem_def typed_apply_abs |
144 Ord_succ_mem_iff nat_0_le [THEN ltD]) |
144 Ord_succ_mem_iff nat_0_le [THEN ltD], blast) |
145 apply (blast intro: elim:); |
|
146 done |
145 done |
147 |
146 |
148 locale M_trancl = M_axioms + |
147 locale M_trancl = M_axioms + |
149 assumes rtrancl_separation: |
148 assumes rtrancl_separation: |
150 "[| M(r); M(A) |] ==> separation (M, rtran_closure_mem(M,A,r))" |
149 "[| M(r); M(A) |] ==> separation (M, rtran_closure_mem(M,A,r))" |
157 |
156 |
158 lemma (in M_trancl) rtran_closure_rtrancl: |
157 lemma (in M_trancl) rtran_closure_rtrancl: |
159 "M(r) ==> rtran_closure(M,r,rtrancl(r))" |
158 "M(r) ==> rtran_closure(M,r,rtrancl(r))" |
160 apply (simp add: rtran_closure_def rtran_closure_mem_iff |
159 apply (simp add: rtran_closure_def rtran_closure_mem_iff |
161 rtrancl_alt_eq_rtrancl [symmetric] rtrancl_alt_def) |
160 rtrancl_alt_eq_rtrancl [symmetric] rtrancl_alt_def) |
162 apply (auto simp add: nat_0_le [THEN ltD] apply_funtype); |
161 apply (auto simp add: nat_0_le [THEN ltD] apply_funtype) |
163 done |
162 done |
164 |
163 |
165 lemma (in M_trancl) rtrancl_closed [intro,simp]: |
164 lemma (in M_trancl) rtrancl_closed [intro,simp]: |
166 "M(r) ==> M(rtrancl(r))" |
165 "M(r) ==> M(rtrancl(r))" |
167 apply (insert rtrancl_separation [of r "field(r)"]) |
166 apply (insert rtrancl_separation [of r "field(r)"]) |
175 txt{*Proving the right-to-left implication*} |
174 txt{*Proving the right-to-left implication*} |
176 prefer 2 apply (blast intro: rtran_closure_rtrancl) |
175 prefer 2 apply (blast intro: rtran_closure_rtrancl) |
177 apply (rule M_equalityI) |
176 apply (rule M_equalityI) |
178 apply (simp add: rtran_closure_def rtrancl_alt_eq_rtrancl [symmetric] |
177 apply (simp add: rtran_closure_def rtrancl_alt_eq_rtrancl [symmetric] |
179 rtrancl_alt_def rtran_closure_mem_iff) |
178 rtrancl_alt_def rtran_closure_mem_iff) |
180 apply (auto simp add: nat_0_le [THEN ltD] apply_funtype); |
179 apply (auto simp add: nat_0_le [THEN ltD] apply_funtype) |
181 done |
180 done |
182 |
181 |
183 lemma (in M_trancl) trancl_closed [intro,simp]: |
182 lemma (in M_trancl) trancl_closed [intro,simp]: |
184 "M(r) ==> M(trancl(r))" |
183 "M(r) ==> M(trancl(r))" |
185 by (simp add: trancl_def comp_closed rtrancl_closed) |
184 by (simp add: trancl_def comp_closed rtrancl_closed) |
233 rank function.*} |
232 rank function.*} |
234 |
233 |
235 |
234 |
236 (*NEEDS RELATIVIZATION*) |
235 (*NEEDS RELATIVIZATION*) |
237 locale M_wfrank = M_trancl + |
236 locale M_wfrank = M_trancl + |
238 assumes wfrank_separation': |
237 assumes wfrank_separation: |
239 "M(r) ==> |
238 "M(r) ==> |
240 separation |
239 separation (M, \<lambda>x. |
241 (M, \<lambda>x. ~ (\<exists>f[M]. is_recfun(r^+, x, %x f. range(f), f)))" |
240 ~ (\<exists>f[M]. M_is_recfun(M, r^+, x, %mm x f y. y = range(f), f)))" |
242 and wfrank_strong_replacement': |
241 and wfrank_strong_replacement': |
243 "M(r) ==> |
242 "M(r) ==> |
244 strong_replacement(M, \<lambda>x z. \<exists>y[M]. \<exists>f[M]. |
243 strong_replacement(M, \<lambda>x z. \<exists>y[M]. \<exists>f[M]. |
245 pair(M,x,y,z) & is_recfun(r^+, x, %x f. range(f), f) & |
244 pair(M,x,y,z) & is_recfun(r^+, x, %x f. range(f), f) & |
246 y = range(f))" |
245 y = range(f))" |
247 and Ord_wfrank_separation: |
246 and Ord_wfrank_separation: |
248 "M(r) ==> |
247 "M(r) ==> |
249 separation (M, \<lambda>x. ~ (\<forall>f. M(f) \<longrightarrow> |
248 separation (M, \<lambda>x. ~ (\<forall>f. M(f) \<longrightarrow> |
250 is_recfun(r^+, x, \<lambda>x. range, f) \<longrightarrow> Ord(range(f))))" |
249 is_recfun(r^+, x, \<lambda>x. range, f) \<longrightarrow> Ord(range(f))))" |
|
250 |
|
251 lemma (in M_wfrank) wfrank_separation': |
|
252 "M(r) ==> |
|
253 separation |
|
254 (M, \<lambda>x. ~ (\<exists>f[M]. is_recfun(r^+, x, %x f. range(f), f)))" |
|
255 apply (insert wfrank_separation [of r]) |
|
256 apply (simp add: is_recfun_iff_M [of concl: _ _ "%x. range", THEN iff_sym]) |
|
257 done |
251 |
258 |
252 text{*This function, defined using replacement, is a rank function for |
259 text{*This function, defined using replacement, is a rank function for |
253 well-founded relations within the class M.*} |
260 well-founded relations within the class M.*} |
254 constdefs |
261 constdefs |
255 wellfoundedrank :: "[i=>o,i,i] => i" |
262 wellfoundedrank :: "[i=>o,i,i] => i" |