276 must refer to "a"*) |
276 must refer to "a"*) |
277 lemma the_equality_if: |
277 lemma the_equality_if: |
278 "P(a) ==> (THE x. P(x)) = (if (EX!x. P(x)) then a else 0)" |
278 "P(a) ==> (THE x. P(x)) = (if (EX!x. P(x)) then a else 0)" |
279 by (simp add: the_0 the_equality2) |
279 by (simp add: the_0 the_equality2) |
280 |
280 |
281 (*The premise is needed not just to fix i but to ensure f~=0*) |
281 (*The first premise not only fixs i but ensures f~=0. |
282 lemma rank_apply: "i : domain(f) ==> rank(f`i) < rank(f)" |
282 The second premise is now essential. Consider otherwise the relation |
283 apply (unfold apply_def, clarify) |
283 r = {<0,0>,<0,1>,<0,2>,...}. Then f`0 = Union(f``{0}) = Union(nat) = nat, |
284 apply (subgoal_tac "rank (y) < rank (f) ") |
284 whose rank equals that of r.*) |
285 prefer 2 apply (blast intro: lt_trans rank_lt rank_pair2) |
285 lemma rank_apply: "[|i : domain(f); function(f)|] ==> rank(f`i) < rank(f)" |
286 apply (subgoal_tac "0 < rank (f) ") |
286 apply (clarify ); |
287 apply (erule_tac [2] Ord_rank [THEN Ord_0_le, THEN lt_trans1]) |
287 apply (simp add: function_apply_equality); |
288 apply (simp add: the_equality_if) |
288 apply (blast intro: lt_trans rank_lt rank_pair2) |
289 done |
289 done |
290 |
290 |
291 |
291 |
292 (*** Corollaries of leastness ***) |
292 (*** Corollaries of leastness ***) |
293 |
293 |
321 apply (simp add: the_equality if_P) |
321 apply (simp add: the_equality if_P) |
322 done |
322 done |
323 |
323 |
324 lemma transrec2_Limit: |
324 lemma transrec2_Limit: |
325 "Limit(i) ==> transrec2(i,a,b) = (UN j<i. transrec2(j,a,b))" |
325 "Limit(i) ==> transrec2(i,a,b) = (UN j<i. transrec2(j,a,b))" |
326 apply (rule transrec2_def [THEN def_transrec, THEN trans], simp) |
326 apply (rule transrec2_def [THEN def_transrec, THEN trans]) |
327 apply (blast dest!: Limit_has_0 elim!: succ_LimitE) |
327 apply (auto simp add: OUnion_def); |
328 done |
328 done |
329 |
329 |
330 |
330 |
331 (** recursor -- better than nat_rec; the succ case has no type requirement! **) |
331 (** recursor -- better than nat_rec; the succ case has no type requirement! **) |
332 |
332 |