35 |
35 |
36 goal Univ.thy "Vfrom(A,x) <= Vfrom(A,rank(x))"; |
36 goal Univ.thy "Vfrom(A,x) <= Vfrom(A,rank(x))"; |
37 by (eps_ind_tac "x" 1); |
37 by (eps_ind_tac "x" 1); |
38 by (stac Vfrom 1); |
38 by (stac Vfrom 1); |
39 by (stac Vfrom 1); |
39 by (stac Vfrom 1); |
40 by (blast_tac (!claset addSIs [rank_lt RS ltD]) 1); |
40 by (blast_tac (claset() addSIs [rank_lt RS ltD]) 1); |
41 qed "Vfrom_rank_subset1"; |
41 qed "Vfrom_rank_subset1"; |
42 |
42 |
43 goal Univ.thy "Vfrom(A,rank(x)) <= Vfrom(A,x)"; |
43 goal Univ.thy "Vfrom(A,rank(x)) <= Vfrom(A,x)"; |
44 by (eps_ind_tac "x" 1); |
44 by (eps_ind_tac "x" 1); |
45 by (stac Vfrom 1); |
45 by (stac Vfrom 1); |
91 |
91 |
92 (** Finite sets and ordered pairs **) |
92 (** Finite sets and ordered pairs **) |
93 |
93 |
94 goal Univ.thy "!!a. a: Vfrom(A,i) ==> {a} : Vfrom(A,succ(i))"; |
94 goal Univ.thy "!!a. a: Vfrom(A,i) ==> {a} : Vfrom(A,succ(i))"; |
95 by (rtac subset_mem_Vfrom 1); |
95 by (rtac subset_mem_Vfrom 1); |
96 by (safe_tac (!claset)); |
96 by (safe_tac (claset())); |
97 qed "singleton_in_Vfrom"; |
97 qed "singleton_in_Vfrom"; |
98 |
98 |
99 goal Univ.thy |
99 goal Univ.thy |
100 "!!A. [| a: Vfrom(A,i); b: Vfrom(A,i) |] ==> {a,b} : Vfrom(A,succ(i))"; |
100 "!!A. [| a: Vfrom(A,i); b: Vfrom(A,i) |] ==> {a,b} : Vfrom(A,succ(i))"; |
101 by (rtac subset_mem_Vfrom 1); |
101 by (rtac subset_mem_Vfrom 1); |
102 by (safe_tac (!claset)); |
102 by (safe_tac (claset())); |
103 qed "doubleton_in_Vfrom"; |
103 qed "doubleton_in_Vfrom"; |
104 |
104 |
105 goalw Univ.thy [Pair_def] |
105 goalw Univ.thy [Pair_def] |
106 "!!A. [| a: Vfrom(A,i); b: Vfrom(A,i) |] ==> \ |
106 "!!A. [| a: Vfrom(A,i); b: Vfrom(A,i) |] ==> \ |
107 \ <a,b> : Vfrom(A,succ(succ(i)))"; |
107 \ <a,b> : Vfrom(A,succ(succ(i)))"; |
253 "!!A b. [| b: Vfrom(A,i); Limit(i) |] ==> Inr(b) : Vfrom(A,i)"; |
253 "!!A b. [| b: Vfrom(A,i); Limit(i) |] ==> Inr(b) : Vfrom(A,i)"; |
254 by (REPEAT (ares_tac [one_in_VLimit, Pair_in_VLimit] 1)); |
254 by (REPEAT (ares_tac [one_in_VLimit, Pair_in_VLimit] 1)); |
255 qed "Inr_in_VLimit"; |
255 qed "Inr_in_VLimit"; |
256 |
256 |
257 goal Univ.thy "!!i. Limit(i) ==> Vfrom(C,i)+Vfrom(C,i) <= Vfrom(C,i)"; |
257 goal Univ.thy "!!i. Limit(i) ==> Vfrom(C,i)+Vfrom(C,i) <= Vfrom(C,i)"; |
258 by (blast_tac (!claset addSIs [Inl_in_VLimit, Inr_in_VLimit]) 1); |
258 by (blast_tac (claset() addSIs [Inl_in_VLimit, Inr_in_VLimit]) 1); |
259 qed "sum_VLimit"; |
259 qed "sum_VLimit"; |
260 |
260 |
261 bind_thm ("sum_subset_VLimit", [sum_mono, sum_VLimit] MRS subset_trans); |
261 bind_thm ("sum_subset_VLimit", [sum_mono, sum_VLimit] MRS subset_trans); |
262 |
262 |
263 |
263 |
265 (*** Properties assuming Transset(A) ***) |
265 (*** Properties assuming Transset(A) ***) |
266 |
266 |
267 goal Univ.thy "!!i A. Transset(A) ==> Transset(Vfrom(A,i))"; |
267 goal Univ.thy "!!i A. Transset(A) ==> Transset(Vfrom(A,i))"; |
268 by (eps_ind_tac "i" 1); |
268 by (eps_ind_tac "i" 1); |
269 by (stac Vfrom 1); |
269 by (stac Vfrom 1); |
270 by (blast_tac (!claset addSIs [Transset_Union_family, Transset_Un, |
270 by (blast_tac (claset() addSIs [Transset_Union_family, Transset_Un, |
271 Transset_Pow]) 1); |
271 Transset_Pow]) 1); |
272 qed "Transset_Vfrom"; |
272 qed "Transset_Vfrom"; |
273 |
273 |
274 goal Univ.thy "!!A i. Transset(A) ==> Vfrom(A, succ(i)) = Pow(Vfrom(A,i))"; |
274 goal Univ.thy "!!A i. Transset(A) ==> Vfrom(A, succ(i)) = Pow(Vfrom(A,i))"; |
275 by (rtac (Vfrom_succ RS trans) 1); |
275 by (rtac (Vfrom_succ RS trans) 1); |
321 "!!A. [| a: Vfrom(A,j); b: Vfrom(A,j); Transset(A) |] ==> \ |
321 "!!A. [| a: Vfrom(A,j); b: Vfrom(A,j); Transset(A) |] ==> \ |
322 \ a*b : Vfrom(A, succ(succ(succ(j))))"; |
322 \ a*b : Vfrom(A, succ(succ(succ(j))))"; |
323 by (dtac Transset_Vfrom 1); |
323 by (dtac Transset_Vfrom 1); |
324 by (rtac subset_mem_Vfrom 1); |
324 by (rtac subset_mem_Vfrom 1); |
325 by (rewtac Transset_def); |
325 by (rewtac Transset_def); |
326 by (blast_tac (!claset addIs [Pair_in_Vfrom]) 1); |
326 by (blast_tac (claset() addIs [Pair_in_Vfrom]) 1); |
327 qed "prod_in_Vfrom"; |
327 qed "prod_in_Vfrom"; |
328 |
328 |
329 val [aprem,bprem,limiti,transset] = goal Univ.thy |
329 val [aprem,bprem,limiti,transset] = goal Univ.thy |
330 "[| a: Vfrom(A,i); b: Vfrom(A,i); Limit(i); Transset(A) |] ==> \ |
330 "[| a: Vfrom(A,i); b: Vfrom(A,i); Limit(i); Transset(A) |] ==> \ |
331 \ a*b : Vfrom(A,i)"; |
331 \ a*b : Vfrom(A,i)"; |
340 "!!A. [| a: Vfrom(A,j); b: Vfrom(A,j); Transset(A); 1:j |] ==> \ |
340 "!!A. [| a: Vfrom(A,j); b: Vfrom(A,j); Transset(A); 1:j |] ==> \ |
341 \ a+b : Vfrom(A, succ(succ(succ(j))))"; |
341 \ a+b : Vfrom(A, succ(succ(succ(j))))"; |
342 by (dtac Transset_Vfrom 1); |
342 by (dtac Transset_Vfrom 1); |
343 by (rtac subset_mem_Vfrom 1); |
343 by (rtac subset_mem_Vfrom 1); |
344 by (rewtac Transset_def); |
344 by (rewtac Transset_def); |
345 by (blast_tac (!claset addIs [zero_in_Vfrom, Pair_in_Vfrom, |
345 by (blast_tac (claset() addIs [zero_in_Vfrom, Pair_in_Vfrom, |
346 i_subset_Vfrom RS subsetD]) 1); |
346 i_subset_Vfrom RS subsetD]) 1); |
347 qed "sum_in_Vfrom"; |
347 qed "sum_in_Vfrom"; |
348 |
348 |
349 val [aprem,bprem,limiti,transset] = goal Univ.thy |
349 val [aprem,bprem,limiti,transset] = goal Univ.thy |
350 "[| a: Vfrom(A,i); b: Vfrom(A,i); Limit(i); Transset(A) |] ==> \ |
350 "[| a: Vfrom(A,i); b: Vfrom(A,i); Limit(i); Transset(A) |] ==> \ |
366 by (rtac (subset_trans RS subset_trans) 1); |
366 by (rtac (subset_trans RS subset_trans) 1); |
367 by (rtac Un_upper2 3); |
367 by (rtac Un_upper2 3); |
368 by (rtac (succI1 RS UN_upper) 2); |
368 by (rtac (succI1 RS UN_upper) 2); |
369 by (rtac Pow_mono 1); |
369 by (rtac Pow_mono 1); |
370 by (rewtac Transset_def); |
370 by (rewtac Transset_def); |
371 by (blast_tac (!claset addIs [Pair_in_Vfrom]) 1); |
371 by (blast_tac (claset() addIs [Pair_in_Vfrom]) 1); |
372 qed "fun_in_Vfrom"; |
372 qed "fun_in_Vfrom"; |
373 |
373 |
374 val [aprem,bprem,limiti,transset] = goal Univ.thy |
374 val [aprem,bprem,limiti,transset] = goal Univ.thy |
375 "[| a: Vfrom(A,i); b: Vfrom(A,i); Limit(i); Transset(A) |] ==> \ |
375 "[| a: Vfrom(A,i); b: Vfrom(A,i); Limit(i); Transset(A) |] ==> \ |
376 \ a->b : Vfrom(A,i)"; |
376 \ a->b : Vfrom(A,i)"; |
389 by (Blast_tac 1); |
389 by (Blast_tac 1); |
390 qed "Pow_in_Vfrom"; |
390 qed "Pow_in_Vfrom"; |
391 |
391 |
392 goal Univ.thy |
392 goal Univ.thy |
393 "!!a. [| a: Vfrom(A,i); Limit(i); Transset(A) |] ==> Pow(a) : Vfrom(A,i)"; |
393 "!!a. [| a: Vfrom(A,i); Limit(i); Transset(A) |] ==> Pow(a) : Vfrom(A,i)"; |
394 by (blast_tac (!claset addEs [Limit_VfromE] |
394 by (blast_tac (claset() addEs [Limit_VfromE] |
395 addIs [Limit_has_succ, Pow_in_Vfrom, Limit_VfromI]) 1); |
395 addIs [Limit_has_succ, Pow_in_Vfrom, Limit_VfromI]) 1); |
396 qed "Pow_in_VLimit"; |
396 qed "Pow_in_VLimit"; |
397 |
397 |
398 |
398 |
399 (*** The set Vset(i) ***) |
399 (*** The set Vset(i) ***) |
410 (** Characterisation of the elements of Vset(i) **) |
410 (** Characterisation of the elements of Vset(i) **) |
411 |
411 |
412 val [ordi] = goal Univ.thy "Ord(i) ==> ALL b. b : Vset(i) --> rank(b) < i"; |
412 val [ordi] = goal Univ.thy "Ord(i) ==> ALL b. b : Vset(i) --> rank(b) < i"; |
413 by (rtac (ordi RS trans_induct) 1); |
413 by (rtac (ordi RS trans_induct) 1); |
414 by (stac Vset 1); |
414 by (stac Vset 1); |
415 by (safe_tac (!claset)); |
415 by (safe_tac (claset())); |
416 by (stac rank 1); |
416 by (stac rank 1); |
417 by (rtac UN_succ_least_lt 1); |
417 by (rtac UN_succ_least_lt 1); |
418 by (Blast_tac 2); |
418 by (Blast_tac 2); |
419 by (REPEAT (ares_tac [ltI] 1)); |
419 by (REPEAT (ares_tac [ltI] 1)); |
420 qed_spec_mp "VsetD"; |
420 qed_spec_mp "VsetD"; |
421 |
421 |
422 val [ordi] = goal Univ.thy "Ord(i) ==> ALL b. rank(b) : i --> b : Vset(i)"; |
422 val [ordi] = goal Univ.thy "Ord(i) ==> ALL b. rank(b) : i --> b : Vset(i)"; |
423 by (rtac (ordi RS trans_induct) 1); |
423 by (rtac (ordi RS trans_induct) 1); |
424 by (rtac allI 1); |
424 by (rtac allI 1); |
425 by (stac Vset 1); |
425 by (stac Vset 1); |
426 by (blast_tac (!claset addSIs [rank_lt RS ltD]) 1); |
426 by (blast_tac (claset() addSIs [rank_lt RS ltD]) 1); |
427 val lemma = result(); |
427 val lemma = result(); |
428 |
428 |
429 goal Univ.thy "!!x i. rank(x)<i ==> x : Vset(i)"; |
429 goal Univ.thy "!!x i. rank(x)<i ==> x : Vset(i)"; |
430 by (etac ltE 1); |
430 by (etac ltE 1); |
431 by (etac (lemma RS spec RS mp) 1); |
431 by (etac (lemma RS spec RS mp) 1); |
443 qed "Vset_rank_iff"; |
443 qed "Vset_rank_iff"; |
444 |
444 |
445 goal Univ.thy "!!i. Ord(i) ==> rank(Vset(i)) = i"; |
445 goal Univ.thy "!!i. Ord(i) ==> rank(Vset(i)) = i"; |
446 by (stac rank 1); |
446 by (stac rank 1); |
447 by (rtac equalityI 1); |
447 by (rtac equalityI 1); |
448 by (safe_tac (!claset)); |
448 by (safe_tac (claset())); |
449 by (EVERY' [rtac UN_I, |
449 by (EVERY' [rtac UN_I, |
450 etac (i_subset_Vfrom RS subsetD), |
450 etac (i_subset_Vfrom RS subsetD), |
451 etac (Ord_in_Ord RS rank_of_Ord RS ssubst), |
451 etac (Ord_in_Ord RS rank_of_Ord RS ssubst), |
452 assume_tac, |
452 assume_tac, |
453 rtac succI1] 3); |
453 rtac succI1] 3); |
479 qed "rank_Inr"; |
479 qed "rank_Inr"; |
480 |
480 |
481 val rank_rls = [rank_Inl, rank_Inr, rank_pair1, rank_pair2]; |
481 val rank_rls = [rank_Inl, rank_Inr, rank_pair1, rank_pair2]; |
482 val rank_trans_rls = rank_rls @ (rank_rls RLN (2, [lt_trans])); |
482 val rank_trans_rls = rank_rls @ (rank_rls RLN (2, [lt_trans])); |
483 |
483 |
484 val rank_ss = !simpset addsimps [VsetI] addsimps rank_trans_rls; |
484 val rank_ss = simpset() addsimps [VsetI] addsimps rank_trans_rls; |
485 |
485 |
486 (** Recursion over Vset levels! **) |
486 (** Recursion over Vset levels! **) |
487 |
487 |
488 (*NOT SUITABLE FOR REWRITING: recursive!*) |
488 (*NOT SUITABLE FOR REWRITING: recursive!*) |
489 goalw Univ.thy [Vrec_def] "Vrec(a,H) = H(a, lam x:Vset(rank(a)). Vrec(x,H))"; |
489 goalw Univ.thy [Vrec_def] "Vrec(a,H) = H(a, lam x:Vset(rank(a)). Vrec(x,H))"; |
490 by (stac transrec 1); |
490 by (stac transrec 1); |
491 by (simp_tac (!simpset addsimps [Ord_rank, Ord_succ, VsetD RS ltD RS beta, |
491 by (simp_tac (simpset() addsimps [Ord_rank, Ord_succ, VsetD RS ltD RS beta, |
492 VsetI RS beta, le_refl]) 1); |
492 VsetI RS beta, le_refl]) 1); |
493 qed "Vrec"; |
493 qed "Vrec"; |
494 |
494 |
495 (*This form avoids giant explosions in proofs. NOTE USE OF == *) |
495 (*This form avoids giant explosions in proofs. NOTE USE OF == *) |
496 val rew::prems = goal Univ.thy |
496 val rew::prems = goal Univ.thy |
595 goal Univ.thy "2 : univ(A)"; |
595 goal Univ.thy "2 : univ(A)"; |
596 by (REPEAT (ares_tac [nat_into_univ, nat_0I, nat_succI] 1)); |
596 by (REPEAT (ares_tac [nat_into_univ, nat_0I, nat_succI] 1)); |
597 qed "two_in_univ"; |
597 qed "two_in_univ"; |
598 |
598 |
599 goalw Univ.thy [bool_def] "bool <= univ(A)"; |
599 goalw Univ.thy [bool_def] "bool <= univ(A)"; |
600 by (blast_tac (!claset addSIs [zero_in_univ,one_in_univ]) 1); |
600 by (blast_tac (claset() addSIs [zero_in_univ,one_in_univ]) 1); |
601 qed "bool_subset_univ"; |
601 qed "bool_subset_univ"; |
602 |
602 |
603 bind_thm ("bool_into_univ", (bool_subset_univ RS subsetD)); |
603 bind_thm ("bool_into_univ", (bool_subset_univ RS subsetD)); |
604 |
604 |
605 |
605 |
630 (** Closure under finite powerset **) |
630 (** Closure under finite powerset **) |
631 |
631 |
632 goal Univ.thy |
632 goal Univ.thy |
633 "!!i. [| b: Fin(Vfrom(A,i)); Limit(i) |] ==> EX j. b <= Vfrom(A,j) & j<i"; |
633 "!!i. [| b: Fin(Vfrom(A,i)); Limit(i) |] ==> EX j. b <= Vfrom(A,j) & j<i"; |
634 by (etac Fin_induct 1); |
634 by (etac Fin_induct 1); |
635 by (blast_tac (!claset addSDs [Limit_has_0]) 1); |
635 by (blast_tac (claset() addSDs [Limit_has_0]) 1); |
636 by (safe_tac (!claset)); |
636 by (safe_tac (claset())); |
637 by (etac Limit_VfromE 1); |
637 by (etac Limit_VfromE 1); |
638 by (assume_tac 1); |
638 by (assume_tac 1); |
639 by (blast_tac (!claset addSIs [Un_least_lt] addIs [Vfrom_UnI1, Vfrom_UnI2]) 1); |
639 by (blast_tac (claset() addSIs [Un_least_lt] addIs [Vfrom_UnI1, Vfrom_UnI2]) 1); |
640 val Fin_Vfrom_lemma = result(); |
640 val Fin_Vfrom_lemma = result(); |
641 |
641 |
642 goal Univ.thy "!!i. Limit(i) ==> Fin(Vfrom(A,i)) <= Vfrom(A,i)"; |
642 goal Univ.thy "!!i. Limit(i) ==> Fin(Vfrom(A,i)) <= Vfrom(A,i)"; |
643 by (rtac subsetI 1); |
643 by (rtac subsetI 1); |
644 by (dtac Fin_Vfrom_lemma 1); |
644 by (dtac Fin_Vfrom_lemma 1); |
645 by (safe_tac (!claset)); |
645 by (safe_tac (claset())); |
646 by (resolve_tac [Vfrom RS ssubst] 1); |
646 by (resolve_tac [Vfrom RS ssubst] 1); |
647 by (blast_tac (!claset addSDs [ltD]) 1); |
647 by (blast_tac (claset() addSDs [ltD]) 1); |
648 val Fin_VLimit = result(); |
648 val Fin_VLimit = result(); |
649 |
649 |
650 bind_thm ("Fin_subset_VLimit", [Fin_mono, Fin_VLimit] MRS subset_trans); |
650 bind_thm ("Fin_subset_VLimit", [Fin_mono, Fin_VLimit] MRS subset_trans); |
651 |
651 |
652 goalw Univ.thy [univ_def] "Fin(univ(A)) <= univ(A)"; |
652 goalw Univ.thy [univ_def] "Fin(univ(A)) <= univ(A)"; |