src/ZF/Ordinal.ML
changeset 2493 bdeb5024353a
parent 2469 b50b8c0eec01
child 2717 b29c45ef3d86
equal deleted inserted replaced
2492:88f15198950f 2493:bdeb5024353a
    15 goalw Ordinal.thy [Transset_def] "Transset(A) <-> A<=Pow(A)";
    15 goalw Ordinal.thy [Transset_def] "Transset(A) <-> A<=Pow(A)";
    16 by (Fast_tac 1);
    16 by (Fast_tac 1);
    17 qed "Transset_iff_Pow";
    17 qed "Transset_iff_Pow";
    18 
    18 
    19 goalw Ordinal.thy [Transset_def] "Transset(A) <-> Union(succ(A)) = A";
    19 goalw Ordinal.thy [Transset_def] "Transset(A) <-> Union(succ(A)) = A";
    20 by (fast_tac (eq_cs addSEs [equalityE]) 1);
    20 by (fast_tac (!claset addSEs [equalityE]) 1);
    21 qed "Transset_iff_Union_succ";
    21 qed "Transset_iff_Union_succ";
    22 
    22 
    23 (** Consequences of downwards closure **)
    23 (** Consequences of downwards closure **)
    24 
    24 
    25 goalw Ordinal.thy [Transset_def]
    25 goalw Ordinal.thy [Transset_def]
   312 goalw Ordinal.thy [Memrel_def] "!!A B. A<=B ==> Memrel(A) <= Memrel(B)";
   312 goalw Ordinal.thy [Memrel_def] "!!A B. A<=B ==> Memrel(A) <= Memrel(B)";
   313 by (Fast_tac 1);
   313 by (Fast_tac 1);
   314 qed "Memrel_mono";
   314 qed "Memrel_mono";
   315 
   315 
   316 goalw Ordinal.thy [Memrel_def] "Memrel(0) = 0";
   316 goalw Ordinal.thy [Memrel_def] "Memrel(0) = 0";
   317 by (fast_tac eq_cs 1);
   317 by (Fast_tac 1);
   318 qed "Memrel_0";
   318 qed "Memrel_0";
   319 
   319 
   320 goalw Ordinal.thy [Memrel_def] "Memrel(1) = 0";
   320 goalw Ordinal.thy [Memrel_def] "Memrel(1) = 0";
   321 by (fast_tac eq_cs 1);
   321 by (Fast_tac 1);
   322 qed "Memrel_1";
   322 qed "Memrel_1";
   323 
   323 
   324 Addsimps [Memrel_0, Memrel_1];
   324 Addsimps [Memrel_0, Memrel_1];
   325 
   325 
   326 (*The membership relation (as a set) is well-founded.
   326 (*The membership relation (as a set) is well-founded.
   394 val prems = goal Ordinal.thy
   394 val prems = goal Ordinal.thy
   395     "Ord(i) ==> (ALL j. Ord(j) --> i:j | i=j | j:i)";
   395     "Ord(i) ==> (ALL j. Ord(j) --> i:j | i=j | j:i)";
   396 by (trans_ind_tac "i" prems 1);
   396 by (trans_ind_tac "i" prems 1);
   397 by (rtac (impI RS allI) 1);
   397 by (rtac (impI RS allI) 1);
   398 by (trans_ind_tac "j" [] 1);
   398 by (trans_ind_tac "j" [] 1);
   399 by (DEPTH_SOLVE (step_tac eq_cs 1 ORELSE Ord_trans_tac 1));
   399 by (DEPTH_SOLVE (Step_tac 1 ORELSE Ord_trans_tac 1));
   400 qed "Ord_linear_lemma";
   400 qed "Ord_linear_lemma";
   401 
   401 
   402 (*"[| Ord(i); Ord(x) |] ==> i:x | i=x | x:i"*)
   402 (*"[| Ord(i); Ord(x) |] ==> i:x | i=x | x:i"*)
   403 bind_thm ("Ord_linear", Ord_linear_lemma RS spec RS mp);
   403 bind_thm ("Ord_linear", Ord_linear_lemma RS spec RS mp);
   404 
   404 
   621 by (REPEAT (eresolve_tac [asm_rl, leprem RS ltE] 1
   621 by (REPEAT (eresolve_tac [asm_rl, leprem RS ltE] 1
   622      ORELSE dtac Ord_succD 1));
   622      ORELSE dtac Ord_succD 1));
   623 qed "le_implies_UN_le_UN";
   623 qed "le_implies_UN_le_UN";
   624 
   624 
   625 goal Ordinal.thy "!!i. Ord(i) ==> (UN y:i. succ(y)) = i";
   625 goal Ordinal.thy "!!i. Ord(i) ==> (UN y:i. succ(y)) = i";
   626 by (fast_tac (eq_cs addEs [Ord_trans]) 1);
   626 by (fast_tac (!claset addEs [Ord_trans]) 1);
   627 qed "Ord_equality";
   627 qed "Ord_equality";
   628 
   628 
   629 (*Holds for all transitive sets, not just ordinals*)
   629 (*Holds for all transitive sets, not just ordinals*)
   630 goal Ordinal.thy "!!i. Ord(i) ==> Union(i) <= i";
   630 goal Ordinal.thy "!!i. Ord(i) ==> Union(i) <= i";
   631 by (fast_tac (!claset addSEs [Ord_trans]) 1);
   631 by (fast_tac (!claset addSEs [Ord_trans]) 1);
   633 
   633 
   634 
   634 
   635 (*** Limit ordinals -- general properties ***)
   635 (*** Limit ordinals -- general properties ***)
   636 
   636 
   637 goalw Ordinal.thy [Limit_def] "!!i. Limit(i) ==> Union(i) = i";
   637 goalw Ordinal.thy [Limit_def] "!!i. Limit(i) ==> Union(i) = i";
   638 by (fast_tac (eq_cs addSIs [ltI] addSEs [ltE] addEs [Ord_trans]) 1);
   638 by (fast_tac (!claset addSIs [ltI] addSEs [ltE] addEs [Ord_trans]) 1);
   639 qed "Limit_Union_eq";
   639 qed "Limit_Union_eq";
   640 
   640 
   641 goalw Ordinal.thy [Limit_def] "!!i. Limit(i) ==> Ord(i)";
   641 goalw Ordinal.thy [Limit_def] "!!i. Limit(i) ==> Ord(i)";
   642 by (etac conjunct1 1);
   642 by (etac conjunct1 1);
   643 qed "Limit_is_Ord";
   643 qed "Limit_is_Ord";
   671 
   671 
   672 (** Traditional 3-way case analysis on ordinals **)
   672 (** Traditional 3-way case analysis on ordinals **)
   673 
   673 
   674 goal Ordinal.thy "!!i. Ord(i) ==> i=0 | (EX j. Ord(j) & i=succ(j)) | Limit(i)";
   674 goal Ordinal.thy "!!i. Ord(i) ==> i=0 | (EX j. Ord(j) & i=succ(j)) | Limit(i)";
   675 by (fast_tac (!claset addSIs [non_succ_LimitI, Ord_0_lt]
   675 by (fast_tac (!claset addSIs [non_succ_LimitI, Ord_0_lt]
   676          	      addSDs [Ord_succD]) 1);
   676                       addSDs [Ord_succD]) 1);
   677 qed "Ord_cases_disj";
   677 qed "Ord_cases_disj";
   678 
   678 
   679 val major::prems = goal Ordinal.thy
   679 val major::prems = goal Ordinal.thy
   680     "[| Ord(i);                 \
   680     "[| Ord(i);                 \
   681 \       i=0                          ==> P;     \
   681 \       i=0                          ==> P;     \