src/ZF/Univ.ML
changeset 4091 771b1f6422a8
parent 3889 59bab7a52b4c
child 4152 451104c223e2
equal deleted inserted replaced
4090:9f1eaab75e8c 4091:771b1f6422a8
    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)";