20 definition |
20 definition |
21 recfunAC16 :: "[i,i,i,i] => i" where |
21 recfunAC16 :: "[i,i,i,i] => i" where |
22 "recfunAC16(f,h,i,a) == |
22 "recfunAC16(f,h,i,a) == |
23 transrec2(i, 0, |
23 transrec2(i, 0, |
24 %g r. if (\<exists>y \<in> r. h`g \<subseteq> y) then r |
24 %g r. if (\<exists>y \<in> r. h`g \<subseteq> y) then r |
25 else r \<union> {f`(LEAST i. h`g \<subseteq> f`i & |
25 else r \<union> {f`(\<mu> i. h`g \<subseteq> f`i & |
26 (\<forall>b<a. (h`b \<subseteq> f`i \<longrightarrow> (\<forall>t \<in> r. ~ h`b \<subseteq> t))))})" |
26 (\<forall>b<a. (h`b \<subseteq> f`i \<longrightarrow> (\<forall>t \<in> r. ~ h`b \<subseteq> t))))})" |
27 |
27 |
28 (* ********************************************************************** *) |
28 (* ********************************************************************** *) |
29 (* Basic properties of recfunAC16 *) |
29 (* Basic properties of recfunAC16 *) |
30 (* ********************************************************************** *) |
30 (* ********************************************************************** *) |
34 |
34 |
35 lemma recfunAC16_succ: |
35 lemma recfunAC16_succ: |
36 "recfunAC16(f,h,succ(i),a) = |
36 "recfunAC16(f,h,succ(i),a) = |
37 (if (\<exists>y \<in> recfunAC16(f,h,i,a). h ` i \<subseteq> y) then recfunAC16(f,h,i,a) |
37 (if (\<exists>y \<in> recfunAC16(f,h,i,a). h ` i \<subseteq> y) then recfunAC16(f,h,i,a) |
38 else recfunAC16(f,h,i,a) \<union> |
38 else recfunAC16(f,h,i,a) \<union> |
39 {f ` (LEAST j. h ` i \<subseteq> f ` j & |
39 {f ` (\<mu> j. h ` i \<subseteq> f ` j & |
40 (\<forall>b<a. (h`b \<subseteq> f`j |
40 (\<forall>b<a. (h`b \<subseteq> f`j |
41 \<longrightarrow> (\<forall>t \<in> recfunAC16(f,h,i,a). ~ h`b \<subseteq> t))))})" |
41 \<longrightarrow> (\<forall>t \<in> recfunAC16(f,h,i,a). ~ h`b \<subseteq> t))))})" |
42 apply (simp add: recfunAC16_def) |
42 apply (simp add: recfunAC16_def) |
43 done |
43 done |
44 |
44 |
230 singleton_eqpoll_1 [THEN eqpoll_imp_lepoll] lepoll_trans) |
230 singleton_eqpoll_1 [THEN eqpoll_imp_lepoll] lepoll_trans) |
231 done |
231 done |
232 |
232 |
233 lemma in_Least_Diff: |
233 lemma in_Least_Diff: |
234 "[| z \<in> F(x); Ord(x) |] |
234 "[| z \<in> F(x); Ord(x) |] |
235 ==> z \<in> F(LEAST i. z \<in> F(i)) - (\<Union>j<(LEAST i. z \<in> F(i)). F(j))" |
235 ==> z \<in> F(\<mu> i. z \<in> F(i)) - (\<Union>j<(\<mu> i. z \<in> F(i)). F(j))" |
236 by (fast elim: less_LeastE elim!: LeastI) |
236 by (fast elim: less_LeastE elim!: LeastI) |
237 |
237 |
238 lemma Least_eq_imp_ex: |
238 lemma Least_eq_imp_ex: |
239 "[| (LEAST i. w \<in> F(i)) = (LEAST i. z \<in> F(i)); |
239 "[| (\<mu> i. w \<in> F(i)) = (\<mu> i. z \<in> F(i)); |
240 w \<in> (\<Union>i<a. F(i)); z \<in> (\<Union>i<a. F(i)) |] |
240 w \<in> (\<Union>i<a. F(i)); z \<in> (\<Union>i<a. F(i)) |] |
241 ==> \<exists>b<a. w \<in> (F(b) - (\<Union>c<b. F(c))) & z \<in> (F(b) - (\<Union>c<b. F(c)))" |
241 ==> \<exists>b<a. w \<in> (F(b) - (\<Union>c<b. F(c))) & z \<in> (F(b) - (\<Union>c<b. F(c)))" |
242 apply (elim OUN_E) |
242 apply (elim OUN_E) |
243 apply (drule in_Least_Diff, erule lt_Ord) |
243 apply (drule in_Least_Diff, erule lt_Ord) |
244 apply (frule in_Least_Diff, erule lt_Ord) |
244 apply (frule in_Least_Diff, erule lt_Ord) |
253 |
253 |
254 lemma UN_lepoll_index: |
254 lemma UN_lepoll_index: |
255 "[| \<forall>i<a. F(i)-(\<Union>j<i. F(j)) \<lesssim> 1; Limit(a) |] |
255 "[| \<forall>i<a. F(i)-(\<Union>j<i. F(j)) \<lesssim> 1; Limit(a) |] |
256 ==> (\<Union>x<a. F(x)) \<lesssim> a" |
256 ==> (\<Union>x<a. F(x)) \<lesssim> a" |
257 apply (rule lepoll_def [THEN def_imp_iff [THEN iffD2]]) |
257 apply (rule lepoll_def [THEN def_imp_iff [THEN iffD2]]) |
258 apply (rule_tac x = "\<lambda>z \<in> (\<Union>x<a. F (x)). LEAST i. z \<in> F (i) " in exI) |
258 apply (rule_tac x = "\<lambda>z \<in> (\<Union>x<a. F (x)). \<mu> i. z \<in> F (i) " in exI) |
259 apply (unfold inj_def) |
259 apply (unfold inj_def) |
260 apply (rule CollectI) |
260 apply (rule CollectI) |
261 apply (rule lam_type) |
261 apply (rule lam_type) |
262 apply (erule OUN_E) |
262 apply (erule OUN_E) |
263 apply (erule Least_in_Ord) |
263 apply (erule Least_in_Ord) |