src/ZF/Univ.ML
changeset 2925 b0ae2e13db93
parent 2493 bdeb5024353a
child 3016 15763781afb0
equal deleted inserted replaced
2924:af506c35b4ed 2925:b0ae2e13db93
    38 
    38 
    39 goal Univ.thy "Vfrom(A,x) <= Vfrom(A,rank(x))";
    39 goal Univ.thy "Vfrom(A,x) <= Vfrom(A,rank(x))";
    40 by (eps_ind_tac "x" 1);
    40 by (eps_ind_tac "x" 1);
    41 by (stac Vfrom 1);
    41 by (stac Vfrom 1);
    42 by (stac Vfrom 1);
    42 by (stac Vfrom 1);
    43 by (fast_tac (!claset addSIs [rank_lt RS ltD]) 1);
    43 by (blast_tac (!claset addSIs [rank_lt RS ltD]) 1);
    44 qed "Vfrom_rank_subset1";
    44 qed "Vfrom_rank_subset1";
    45 
    45 
    46 goal Univ.thy "Vfrom(A,rank(x)) <= Vfrom(A,x)";
    46 goal Univ.thy "Vfrom(A,rank(x)) <= Vfrom(A,x)";
    47 by (eps_ind_tac "x" 1);
    47 by (eps_ind_tac "x" 1);
    48 by (stac Vfrom 1);
    48 by (stac Vfrom 1);
    69 
    69 
    70 (*** Basic closure properties ***)
    70 (*** Basic closure properties ***)
    71 
    71 
    72 goal Univ.thy "!!x y. y:x ==> 0 : Vfrom(A,x)";
    72 goal Univ.thy "!!x y. y:x ==> 0 : Vfrom(A,x)";
    73 by (stac Vfrom 1);
    73 by (stac Vfrom 1);
    74 by (Fast_tac 1);
    74 by (Blast_tac 1);
    75 qed "zero_in_Vfrom";
    75 qed "zero_in_Vfrom";
    76 
    76 
    77 goal Univ.thy "i <= Vfrom(A,i)";
    77 goal Univ.thy "i <= Vfrom(A,i)";
    78 by (eps_ind_tac "i" 1);
    78 by (eps_ind_tac "i" 1);
    79 by (stac Vfrom 1);
    79 by (stac Vfrom 1);
    80 by (Fast_tac 1);
    80 by (Blast_tac 1);
    81 qed "i_subset_Vfrom";
    81 qed "i_subset_Vfrom";
    82 
    82 
    83 goal Univ.thy "A <= Vfrom(A,i)";
    83 goal Univ.thy "A <= Vfrom(A,i)";
    84 by (stac Vfrom 1);
    84 by (stac Vfrom 1);
    85 by (rtac Un_upper1 1);
    85 by (rtac Un_upper1 1);
    87 
    87 
    88 bind_thm ("A_into_Vfrom", A_subset_Vfrom RS subsetD);
    88 bind_thm ("A_into_Vfrom", A_subset_Vfrom RS subsetD);
    89 
    89 
    90 goal Univ.thy "!!A a i. a <= Vfrom(A,i) ==> a: Vfrom(A,succ(i))";
    90 goal Univ.thy "!!A a i. a <= Vfrom(A,i) ==> a: Vfrom(A,succ(i))";
    91 by (stac Vfrom 1);
    91 by (stac Vfrom 1);
    92 by (Fast_tac 1);
    92 by (Blast_tac 1);
    93 qed "subset_mem_Vfrom";
    93 qed "subset_mem_Vfrom";
    94 
    94 
    95 (** Finite sets and ordered pairs **)
    95 (** Finite sets and ordered pairs **)
    96 
    96 
    97 goal Univ.thy "!!a. a: Vfrom(A,i) ==> {a} : Vfrom(A,succ(i))";
    97 goal Univ.thy "!!a. a: Vfrom(A,i) ==> {a} : Vfrom(A,succ(i))";
   120 
   120 
   121 (*** 0, successor and limit equations fof Vfrom ***)
   121 (*** 0, successor and limit equations fof Vfrom ***)
   122 
   122 
   123 goal Univ.thy "Vfrom(A,0) = A";
   123 goal Univ.thy "Vfrom(A,0) = A";
   124 by (stac Vfrom 1);
   124 by (stac Vfrom 1);
   125 by (Fast_tac 1);
   125 by (Blast_tac 1);
   126 qed "Vfrom_0";
   126 qed "Vfrom_0";
   127 
   127 
   128 goal Univ.thy "!!i. Ord(i) ==> Vfrom(A,succ(i)) = A Un Pow(Vfrom(A,i))";
   128 goal Univ.thy "!!i. Ord(i) ==> Vfrom(A,succ(i)) = A Un Pow(Vfrom(A,i))";
   129 by (rtac (Vfrom RS trans) 1);
   129 by (rtac (Vfrom RS trans) 1);
   130 by (rtac (succI1 RS RepFunI RS Union_upper RSN
   130 by (rtac (succI1 RS RepFunI RS Union_upper RSN
   158 by (stac Vfrom 1);
   158 by (stac Vfrom 1);
   159 by (etac ([UN_upper, Un_upper2] MRS subset_trans) 1);
   159 by (etac ([UN_upper, Un_upper2] MRS subset_trans) 1);
   160 (*opposite inclusion*)
   160 (*opposite inclusion*)
   161 by (rtac UN_least 1);
   161 by (rtac UN_least 1);
   162 by (stac Vfrom 1);
   162 by (stac Vfrom 1);
   163 by (Fast_tac 1);
   163 by (Blast_tac 1);
   164 qed "Vfrom_Union";
   164 qed "Vfrom_Union";
   165 
   165 
   166 (*** Vfrom applied to Limit ordinals ***)
   166 (*** Vfrom applied to Limit ordinals ***)
   167 
   167 
   168 (*NB. limit ordinals are non-empty;
   168 (*NB. limit ordinals are non-empty;
   256     "!!A b. [| b: Vfrom(A,i); Limit(i) |] ==> Inr(b) : Vfrom(A,i)";
   256     "!!A b. [| b: Vfrom(A,i); Limit(i) |] ==> Inr(b) : Vfrom(A,i)";
   257 by (REPEAT (ares_tac [one_in_VLimit, Pair_in_VLimit] 1));
   257 by (REPEAT (ares_tac [one_in_VLimit, Pair_in_VLimit] 1));
   258 qed "Inr_in_VLimit";
   258 qed "Inr_in_VLimit";
   259 
   259 
   260 goal Univ.thy "!!i. Limit(i) ==> Vfrom(C,i)+Vfrom(C,i) <= Vfrom(C,i)";
   260 goal Univ.thy "!!i. Limit(i) ==> Vfrom(C,i)+Vfrom(C,i) <= Vfrom(C,i)";
   261 by (fast_tac (!claset addSIs [Inl_in_VLimit, Inr_in_VLimit]) 1);
   261 by (blast_tac (!claset addSIs [Inl_in_VLimit, Inr_in_VLimit]) 1);
   262 qed "sum_VLimit";
   262 qed "sum_VLimit";
   263 
   263 
   264 bind_thm ("sum_subset_VLimit", [sum_mono, sum_VLimit] MRS subset_trans);
   264 bind_thm ("sum_subset_VLimit", [sum_mono, sum_VLimit] MRS subset_trans);
   265 
   265 
   266 
   266 
   268 (*** Properties assuming Transset(A) ***)
   268 (*** Properties assuming Transset(A) ***)
   269 
   269 
   270 goal Univ.thy "!!i A. Transset(A) ==> Transset(Vfrom(A,i))";
   270 goal Univ.thy "!!i A. Transset(A) ==> Transset(Vfrom(A,i))";
   271 by (eps_ind_tac "i" 1);
   271 by (eps_ind_tac "i" 1);
   272 by (stac Vfrom 1);
   272 by (stac Vfrom 1);
   273 by (fast_tac (!claset addSIs [Transset_Union_family, Transset_Un,
   273 by (blast_tac (!claset addSIs [Transset_Union_family, Transset_Un,
   274                             Transset_Pow]) 1);
   274                             Transset_Pow]) 1);
   275 qed "Transset_Vfrom";
   275 qed "Transset_Vfrom";
   276 
   276 
   277 goal Univ.thy "!!A i. Transset(A) ==> Vfrom(A, succ(i)) = Pow(Vfrom(A,i))";
   277 goal Univ.thy "!!A i. Transset(A) ==> Vfrom(A, succ(i)) = Pow(Vfrom(A,i))";
   278 by (rtac (Vfrom_succ RS trans) 1);
   278 by (rtac (Vfrom_succ RS trans) 1);
   282 by (etac (Transset_Vfrom RS (Transset_iff_Pow RS iffD1)) 1);
   282 by (etac (Transset_Vfrom RS (Transset_iff_Pow RS iffD1)) 1);
   283 qed "Transset_Vfrom_succ";
   283 qed "Transset_Vfrom_succ";
   284 
   284 
   285 goalw Ordinal.thy [Pair_def,Transset_def]
   285 goalw Ordinal.thy [Pair_def,Transset_def]
   286     "!!C. [| <a,b> <= C; Transset(C) |] ==> a: C & b: C";
   286     "!!C. [| <a,b> <= C; Transset(C) |] ==> a: C & b: C";
   287 by (Best_tac 1);
   287 by (Blast_tac 1);
   288 qed "Transset_Pair_subset";
   288 qed "Transset_Pair_subset";
   289 
   289 
   290 goal Univ.thy
   290 goal Univ.thy
   291     "!!a b.[| <a,b> <= Vfrom(A,i);  Transset(A);  Limit(i) |] ==> \
   291     "!!a b.[| <a,b> <= Vfrom(A,i);  Transset(A);  Limit(i) |] ==> \
   292 \          <a,b> : Vfrom(A,i)";
   292 \          <a,b> : Vfrom(A,i)";
   324     "!!A. [| a: Vfrom(A,j);  b: Vfrom(A,j);  Transset(A) |] ==> \
   324     "!!A. [| a: Vfrom(A,j);  b: Vfrom(A,j);  Transset(A) |] ==> \
   325 \         a*b : Vfrom(A, succ(succ(succ(j))))";
   325 \         a*b : Vfrom(A, succ(succ(succ(j))))";
   326 by (dtac Transset_Vfrom 1);
   326 by (dtac Transset_Vfrom 1);
   327 by (rtac subset_mem_Vfrom 1);
   327 by (rtac subset_mem_Vfrom 1);
   328 by (rewtac Transset_def);
   328 by (rewtac Transset_def);
   329 by (fast_tac (!claset addIs [Pair_in_Vfrom]) 1);
   329 by (blast_tac (!claset addIs [Pair_in_Vfrom]) 1);
   330 qed "prod_in_Vfrom";
   330 qed "prod_in_Vfrom";
   331 
   331 
   332 val [aprem,bprem,limiti,transset] = goal Univ.thy
   332 val [aprem,bprem,limiti,transset] = goal Univ.thy
   333   "[| a: Vfrom(A,i);  b: Vfrom(A,i);  Limit(i);  Transset(A) |] ==> \
   333   "[| a: Vfrom(A,i);  b: Vfrom(A,i);  Limit(i);  Transset(A) |] ==> \
   334 \  a*b : Vfrom(A,i)";
   334 \  a*b : Vfrom(A,i)";
   343     "!!A. [| a: Vfrom(A,j);  b: Vfrom(A,j);  Transset(A);  1:j |] ==> \
   343     "!!A. [| a: Vfrom(A,j);  b: Vfrom(A,j);  Transset(A);  1:j |] ==> \
   344 \         a+b : Vfrom(A, succ(succ(succ(j))))";
   344 \         a+b : Vfrom(A, succ(succ(succ(j))))";
   345 by (dtac Transset_Vfrom 1);
   345 by (dtac Transset_Vfrom 1);
   346 by (rtac subset_mem_Vfrom 1);
   346 by (rtac subset_mem_Vfrom 1);
   347 by (rewtac Transset_def);
   347 by (rewtac Transset_def);
   348 by (fast_tac (!claset addIs [zero_in_Vfrom, Pair_in_Vfrom, 
   348 by (blast_tac (!claset addIs [zero_in_Vfrom, Pair_in_Vfrom, 
   349                            i_subset_Vfrom RS subsetD]) 1);
   349                            i_subset_Vfrom RS subsetD]) 1);
   350 qed "sum_in_Vfrom";
   350 qed "sum_in_Vfrom";
   351 
   351 
   352 val [aprem,bprem,limiti,transset] = goal Univ.thy
   352 val [aprem,bprem,limiti,transset] = goal Univ.thy
   353   "[| a: Vfrom(A,i);  b: Vfrom(A,i);  Limit(i);  Transset(A) |] ==> \
   353   "[| a: Vfrom(A,i);  b: Vfrom(A,i);  Limit(i);  Transset(A) |] ==> \
   369 by (rtac (subset_trans RS subset_trans) 1);
   369 by (rtac (subset_trans RS subset_trans) 1);
   370 by (rtac Un_upper2 3);
   370 by (rtac Un_upper2 3);
   371 by (rtac (succI1 RS UN_upper) 2);
   371 by (rtac (succI1 RS UN_upper) 2);
   372 by (rtac Pow_mono 1);
   372 by (rtac Pow_mono 1);
   373 by (rewtac Transset_def);
   373 by (rewtac Transset_def);
   374 by (fast_tac (!claset addIs [Pair_in_Vfrom]) 1);
   374 by (blast_tac (!claset addIs [Pair_in_Vfrom]) 1);
   375 qed "fun_in_Vfrom";
   375 qed "fun_in_Vfrom";
   376 
   376 
   377 val [aprem,bprem,limiti,transset] = goal Univ.thy
   377 val [aprem,bprem,limiti,transset] = goal Univ.thy
   378   "[| a: Vfrom(A,i);  b: Vfrom(A,i);  Limit(i);  Transset(A) |] ==> \
   378   "[| a: Vfrom(A,i);  b: Vfrom(A,i);  Limit(i);  Transset(A) |] ==> \
   379 \  a->b : Vfrom(A,i)";
   379 \  a->b : Vfrom(A,i)";
   385 
   385 
   386 (*** The set Vset(i) ***)
   386 (*** The set Vset(i) ***)
   387 
   387 
   388 goal Univ.thy "Vset(i) = (UN j:i. Pow(Vset(j)))";
   388 goal Univ.thy "Vset(i) = (UN j:i. Pow(Vset(j)))";
   389 by (stac Vfrom 1);
   389 by (stac Vfrom 1);
   390 by (Fast_tac 1);
   390 by (Blast_tac 1);
   391 qed "Vset";
   391 qed "Vset";
   392 
   392 
   393 val Vset_succ = Transset_0 RS Transset_Vfrom_succ;
   393 val Vset_succ = Transset_0 RS Transset_Vfrom_succ;
   394 
   394 
   395 val Transset_Vset = Transset_0 RS Transset_Vfrom;
   395 val Transset_Vset = Transset_0 RS Transset_Vfrom;
   400 by (rtac (ordi RS trans_induct) 1);
   400 by (rtac (ordi RS trans_induct) 1);
   401 by (stac Vset 1);
   401 by (stac Vset 1);
   402 by (safe_tac (!claset));
   402 by (safe_tac (!claset));
   403 by (stac rank 1);
   403 by (stac rank 1);
   404 by (rtac UN_succ_least_lt 1);
   404 by (rtac UN_succ_least_lt 1);
   405 by (Fast_tac 2);
   405 by (Blast_tac 2);
   406 by (REPEAT (ares_tac [ltI] 1));
   406 by (REPEAT (ares_tac [ltI] 1));
   407 qed "Vset_rank_imp1";
   407 qed "Vset_rank_imp1";
   408 
   408 
   409 (*  [| Ord(i); x : Vset(i) |] ==> rank(x) < i  *)
   409 (*  [| Ord(i); x : Vset(i) |] ==> rank(x) < i  *)
   410 bind_thm ("VsetD", (Vset_rank_imp1 RS spec RS mp));
   410 bind_thm ("VsetD", (Vset_rank_imp1 RS spec RS mp));
   411 
   411 
   412 val [ordi] = goal Univ.thy "Ord(i) ==> ALL b. rank(b) : i --> b : Vset(i)";
   412 val [ordi] = goal Univ.thy "Ord(i) ==> ALL b. rank(b) : i --> b : Vset(i)";
   413 by (rtac (ordi RS trans_induct) 1);
   413 by (rtac (ordi RS trans_induct) 1);
   414 by (rtac allI 1);
   414 by (rtac allI 1);
   415 by (stac Vset 1);
   415 by (stac Vset 1);
   416 by (fast_tac (!claset addSIs [rank_lt RS ltD]) 1);
   416 by (blast_tac (!claset addSIs [rank_lt RS ltD]) 1);
   417 qed "Vset_rank_imp2";
   417 qed "Vset_rank_imp2";
   418 
   418 
   419 goal Univ.thy "!!x i. rank(x)<i ==> x : Vset(i)";
   419 goal Univ.thy "!!x i. rank(x)<i ==> x : Vset(i)";
   420 by (etac ltE 1);
   420 by (etac ltE 1);
   421 by (etac (Vset_rank_imp2 RS spec RS mp) 1);
   421 by (etac (Vset_rank_imp2 RS spec RS mp) 1);
   577 goal Univ.thy "2 : univ(A)";
   577 goal Univ.thy "2 : univ(A)";
   578 by (REPEAT (ares_tac [nat_into_univ, nat_0I, nat_succI] 1));
   578 by (REPEAT (ares_tac [nat_into_univ, nat_0I, nat_succI] 1));
   579 qed "two_in_univ";
   579 qed "two_in_univ";
   580 
   580 
   581 goalw Univ.thy [bool_def] "bool <= univ(A)";
   581 goalw Univ.thy [bool_def] "bool <= univ(A)";
   582 by (fast_tac (!claset addSIs [zero_in_univ,one_in_univ]) 1);
   582 by (blast_tac (!claset addSIs [zero_in_univ,one_in_univ]) 1);
   583 qed "bool_subset_univ";
   583 qed "bool_subset_univ";
   584 
   584 
   585 bind_thm ("bool_into_univ", (bool_subset_univ RS subsetD));
   585 bind_thm ("bool_into_univ", (bool_subset_univ RS subsetD));
   586 
   586 
   587 
   587 
   612 (** Closure under finite powerset **)
   612 (** Closure under finite powerset **)
   613 
   613 
   614 goal Univ.thy
   614 goal Univ.thy
   615    "!!i. [| b: Fin(Vfrom(A,i));  Limit(i) |] ==> EX j. b <= Vfrom(A,j) & j<i";
   615    "!!i. [| b: Fin(Vfrom(A,i));  Limit(i) |] ==> EX j. b <= Vfrom(A,j) & j<i";
   616 by (etac Fin_induct 1);
   616 by (etac Fin_induct 1);
   617 by (fast_tac (!claset addSDs [Limit_has_0]) 1);
   617 by (blast_tac (!claset addSDs [Limit_has_0]) 1);
   618 by (safe_tac (!claset));
   618 by (safe_tac (!claset));
   619 by (etac Limit_VfromE 1);
   619 by (etac Limit_VfromE 1);
   620 by (assume_tac 1);
   620 by (assume_tac 1);
   621 by (res_inst_tac [("x", "xa Un j")] exI 1);
   621 by (res_inst_tac [("x", "xa Un j")] exI 1);
   622 by (best_tac (!claset addIs [subset_refl RS Vfrom_mono RS subsetD, 
   622 by (best_tac (!claset addIs [subset_refl RS Vfrom_mono RS subsetD, 
   623                            Un_least_lt]) 1);
   623 			     Un_least_lt]) 1);
   624 val Fin_Vfrom_lemma = result();
   624 val Fin_Vfrom_lemma = result();
   625 
   625 
   626 goal Univ.thy "!!i. Limit(i) ==> Fin(Vfrom(A,i)) <= Vfrom(A,i)";
   626 goal Univ.thy "!!i. Limit(i) ==> Fin(Vfrom(A,i)) <= Vfrom(A,i)";
   627 by (rtac subsetI 1);
   627 by (rtac subsetI 1);
   628 by (dtac Fin_Vfrom_lemma 1);
   628 by (dtac Fin_Vfrom_lemma 1);
   629 by (safe_tac (!claset));
   629 by (safe_tac (!claset));
   630 by (resolve_tac [Vfrom RS ssubst] 1);
   630 by (resolve_tac [Vfrom RS ssubst] 1);
   631 by (fast_tac (!claset addSDs [ltD]) 1);
   631 by (blast_tac (!claset addSDs [ltD]) 1);
   632 val Fin_VLimit = result();
   632 val Fin_VLimit = result();
   633 
   633 
   634 bind_thm ("Fin_subset_VLimit", [Fin_mono, Fin_VLimit] MRS subset_trans);
   634 bind_thm ("Fin_subset_VLimit", [Fin_mono, Fin_VLimit] MRS subset_trans);
   635 
   635 
   636 goalw Univ.thy [univ_def] "Fin(univ(A)) <= univ(A)";
   636 goalw Univ.thy [univ_def] "Fin(univ(A)) <= univ(A)";