src/ZF/CardinalArith.ML
changeset 782 200a16083201
parent 767 a4fce3b94065
child 800 23f55b829ccb
equal deleted inserted replaced
781:9ab8873bf9b3 782:200a16083201
    94 (** Addition by another cardinal **)
    94 (** Addition by another cardinal **)
    95 
    95 
    96 goalw CardinalArith.thy [lepoll_def, inj_def] "A lepoll A+B";
    96 goalw CardinalArith.thy [lepoll_def, inj_def] "A lepoll A+B";
    97 by (res_inst_tac [("x", "lam x:A. Inl(x)")] exI 1);
    97 by (res_inst_tac [("x", "lam x:A. Inl(x)")] exI 1);
    98 by (asm_simp_tac (sum_ss addsimps [lam_type]) 1);
    98 by (asm_simp_tac (sum_ss addsimps [lam_type]) 1);
    99 val sum_lepoll_self = result();
    99 qed "sum_lepoll_self";
   100 
   100 
   101 (*Could probably weaken the premises to well_ord(K,r), or removing using AC*)
   101 (*Could probably weaken the premises to well_ord(K,r), or removing using AC*)
   102 goalw CardinalArith.thy [cadd_def]
   102 goalw CardinalArith.thy [cadd_def]
   103     "!!K. [| Card(K);  Ord(L) |] ==> K le (K |+| L)";
   103     "!!K. [| Card(K);  Ord(L) |] ==> K le (K |+| L)";
   104 by (rtac ([Card_cardinal_le, well_ord_lepoll_imp_Card_le] MRS le_trans) 1);
   104 by (rtac ([Card_cardinal_le, well_ord_lepoll_imp_Card_le] MRS le_trans) 1);
   105 by (rtac sum_lepoll_self 3);
   105 by (rtac sum_lepoll_self 3);
   106 by (REPEAT (ares_tac [well_ord_radd, well_ord_Memrel, Card_is_Ord] 1));
   106 by (REPEAT (ares_tac [well_ord_radd, well_ord_Memrel, Card_is_Ord] 1));
   107 val cadd_le_self = result();
   107 qed "cadd_le_self";
   108 
   108 
   109 (** Monotonicity of addition **)
   109 (** Monotonicity of addition **)
   110 
   110 
   111 goalw CardinalArith.thy [lepoll_def]
   111 goalw CardinalArith.thy [lepoll_def]
   112      "!!A B C D. [| A lepoll C;  B lepoll D |] ==> A + B  lepoll  C + D";
   112      "!!A B C D. [| A lepoll C;  B lepoll D |] ==> A + B  lepoll  C + D";
   117       [("d", "case(%w. Inl(converse(f)`w), %y. Inr(converse(fa)`y))")] 
   117       [("d", "case(%w. Inl(converse(f)`w), %y. Inr(converse(fa)`y))")] 
   118       lam_injective 1);
   118       lam_injective 1);
   119 by (typechk_tac ([inj_is_fun,case_type, InlI, InrI] @ ZF_typechecks));
   119 by (typechk_tac ([inj_is_fun,case_type, InlI, InrI] @ ZF_typechecks));
   120 by (eresolve_tac [sumE] 1);
   120 by (eresolve_tac [sumE] 1);
   121 by (ALLGOALS (asm_simp_tac (sum_ss addsimps [left_inverse])));
   121 by (ALLGOALS (asm_simp_tac (sum_ss addsimps [left_inverse])));
   122 val sum_lepoll_mono = result();
   122 qed "sum_lepoll_mono";
   123 
   123 
   124 goalw CardinalArith.thy [cadd_def]
   124 goalw CardinalArith.thy [cadd_def]
   125     "!!K. [| K' le K;  L' le L |] ==> (K' |+| L') le (K |+| L)";
   125     "!!K. [| K' le K;  L' le L |] ==> (K' |+| L') le (K |+| L)";
   126 by (safe_tac (ZF_cs addSDs [le_subset_iff RS iffD1]));
   126 by (safe_tac (ZF_cs addSDs [le_subset_iff RS iffD1]));
   127 by (resolve_tac [well_ord_lepoll_imp_Card_le] 1);
   127 by (resolve_tac [well_ord_lepoll_imp_Card_le] 1);
   128 by (REPEAT (ares_tac [sum_lepoll_mono, subset_imp_lepoll] 2));
   128 by (REPEAT (ares_tac [sum_lepoll_mono, subset_imp_lepoll] 2));
   129 by (REPEAT (ares_tac [well_ord_radd, well_ord_Memrel] 1));
   129 by (REPEAT (ares_tac [well_ord_radd, well_ord_Memrel] 1));
   130 val cadd_le_mono = result();
   130 qed "cadd_le_mono";
   131 
   131 
   132 (** Addition of finite cardinals is "ordinary" addition **)
   132 (** Addition of finite cardinals is "ordinary" addition **)
   133 
   133 
   134 goalw CardinalArith.thy [eqpoll_def] "succ(A)+B eqpoll succ(A+B)";
   134 goalw CardinalArith.thy [eqpoll_def] "succ(A)+B eqpoll succ(A+B)";
   135 by (rtac exI 1);
   135 by (rtac exI 1);
   260 (** Multiplication by a non-zero cardinal **)
   260 (** Multiplication by a non-zero cardinal **)
   261 
   261 
   262 goalw CardinalArith.thy [lepoll_def, inj_def] "!!b. b: B ==> A lepoll A*B";
   262 goalw CardinalArith.thy [lepoll_def, inj_def] "!!b. b: B ==> A lepoll A*B";
   263 by (res_inst_tac [("x", "lam x:A. <x,b>")] exI 1);
   263 by (res_inst_tac [("x", "lam x:A. <x,b>")] exI 1);
   264 by (asm_simp_tac (ZF_ss addsimps [lam_type]) 1);
   264 by (asm_simp_tac (ZF_ss addsimps [lam_type]) 1);
   265 val prod_lepoll_self = result();
   265 qed "prod_lepoll_self";
   266 
   266 
   267 (*Could probably weaken the premises to well_ord(K,r), or removing using AC*)
   267 (*Could probably weaken the premises to well_ord(K,r), or removing using AC*)
   268 goalw CardinalArith.thy [cmult_def]
   268 goalw CardinalArith.thy [cmult_def]
   269     "!!K. [| Card(K);  Ord(L);  0<L |] ==> K le (K |*| L)";
   269     "!!K. [| Card(K);  Ord(L);  0<L |] ==> K le (K |*| L)";
   270 by (rtac ([Card_cardinal_le, well_ord_lepoll_imp_Card_le] MRS le_trans) 1);
   270 by (rtac ([Card_cardinal_le, well_ord_lepoll_imp_Card_le] MRS le_trans) 1);
   271 by (rtac prod_lepoll_self 3);
   271 by (rtac prod_lepoll_self 3);
   272 by (REPEAT (ares_tac [well_ord_rmult, well_ord_Memrel, Card_is_Ord, ltD] 1));
   272 by (REPEAT (ares_tac [well_ord_rmult, well_ord_Memrel, Card_is_Ord, ltD] 1));
   273 val cmult_le_self = result();
   273 qed "cmult_le_self";
   274 
   274 
   275 (** Monotonicity of multiplication **)
   275 (** Monotonicity of multiplication **)
   276 
   276 
   277 (*Equivalent to KG's lepoll_SigmaI*)
   277 (*Equivalent to KG's lepoll_SigmaI*)
   278 goalw CardinalArith.thy [lepoll_def]
   278 goalw CardinalArith.thy [lepoll_def]
   282 by (res_inst_tac [("d", "split(%w y.<converse(f)`w, converse(fa)`y>)")] 
   282 by (res_inst_tac [("d", "split(%w y.<converse(f)`w, converse(fa)`y>)")] 
   283 		  lam_injective 1);
   283 		  lam_injective 1);
   284 by (typechk_tac (inj_is_fun::ZF_typechecks));
   284 by (typechk_tac (inj_is_fun::ZF_typechecks));
   285 by (eresolve_tac [SigmaE] 1);
   285 by (eresolve_tac [SigmaE] 1);
   286 by (asm_simp_tac (ZF_ss addsimps [left_inverse]) 1);
   286 by (asm_simp_tac (ZF_ss addsimps [left_inverse]) 1);
   287 val prod_lepoll_mono = result();
   287 qed "prod_lepoll_mono";
   288 
   288 
   289 goalw CardinalArith.thy [cmult_def]
   289 goalw CardinalArith.thy [cmult_def]
   290     "!!K. [| K' le K;  L' le L |] ==> (K' |*| L') le (K |*| L)";
   290     "!!K. [| K' le K;  L' le L |] ==> (K' |*| L') le (K |*| L)";
   291 by (safe_tac (ZF_cs addSDs [le_subset_iff RS iffD1]));
   291 by (safe_tac (ZF_cs addSDs [le_subset_iff RS iffD1]));
   292 by (resolve_tac [well_ord_lepoll_imp_Card_le] 1);
   292 by (resolve_tac [well_ord_lepoll_imp_Card_le] 1);
   293 by (REPEAT (ares_tac [prod_lepoll_mono, subset_imp_lepoll] 2));
   293 by (REPEAT (ares_tac [prod_lepoll_mono, subset_imp_lepoll] 2));
   294 by (REPEAT (ares_tac [well_ord_rmult, well_ord_Memrel] 1));
   294 by (REPEAT (ares_tac [well_ord_rmult, well_ord_Memrel] 1));
   295 val cmult_le_mono = result();
   295 qed "cmult_le_mono";
   296 
   296 
   297 (*** Multiplication of finite cardinals is "ordinary" multiplication ***)
   297 (*** Multiplication of finite cardinals is "ordinary" multiplication ***)
   298 
   298 
   299 goalw CardinalArith.thy [eqpoll_def] "succ(A)*B eqpoll B + A*B";
   299 goalw CardinalArith.thy [eqpoll_def] "succ(A)*B eqpoll B + A*B";
   300 by (rtac exI 1);
   300 by (rtac exI 1);
   327 (*Needs Krzysztof Grabczewski's macro "2" == "succ(1)"*)
   327 (*Needs Krzysztof Grabczewski's macro "2" == "succ(1)"*)
   328 goal CardinalArith.thy "!!m n. Card(n) ==> succ(1) |*| n = n |+| n";
   328 goal CardinalArith.thy "!!m n. Card(n) ==> succ(1) |*| n = n |+| n";
   329 by (asm_simp_tac 
   329 by (asm_simp_tac 
   330     (ZF_ss addsimps [Ord_0, Ord_succ, cmult_0, cmult_succ_lemma, Card_is_Ord,
   330     (ZF_ss addsimps [Ord_0, Ord_succ, cmult_0, cmult_succ_lemma, Card_is_Ord,
   331 		     read_instantiate [("j","0")] cadd_commute, cadd_0]) 1);
   331 		     read_instantiate [("j","0")] cadd_commute, cadd_0]) 1);
   332 val cmult_2 = result();
   332 qed "cmult_2";
   333 
   333 
   334 
   334 
   335 (*** Infinite Cardinals are Limit Ordinals ***)
   335 (*** Infinite Cardinals are Limit Ordinals ***)
   336 
   336 
   337 (*This proof is modelled upon one assuming nat<=A, with injection
   337 (*This proof is modelled upon one assuming nat<=A, with injection
   589 by (eresolve_tac [ltE] 2 THEN
   589 by (eresolve_tac [ltE] 2 THEN
   590     REPEAT (ares_tac [cmult_le_self, InfCard_is_Card] 2));
   590     REPEAT (ares_tac [cmult_le_self, InfCard_is_Card] 2));
   591 by (forward_tac [InfCard_is_Card RS Card_is_Ord RS le_refl] 1);
   591 by (forward_tac [InfCard_is_Card RS Card_is_Ord RS le_refl] 1);
   592 by (resolve_tac [cmult_le_mono RS le_trans] 1 THEN REPEAT (assume_tac 1));
   592 by (resolve_tac [cmult_le_mono RS le_trans] 1 THEN REPEAT (assume_tac 1));
   593 by (asm_simp_tac (ZF_ss addsimps [InfCard_csquare_eq]) 1);
   593 by (asm_simp_tac (ZF_ss addsimps [InfCard_csquare_eq]) 1);
   594 val InfCard_le_cmult_eq = result();
   594 qed "InfCard_le_cmult_eq";
   595 
   595 
   596 (*Corollary 10.13 (1), for cardinal multiplication*)
   596 (*Corollary 10.13 (1), for cardinal multiplication*)
   597 goal CardinalArith.thy
   597 goal CardinalArith.thy
   598     "!!K. [| InfCard(K);  InfCard(L) |] ==> K |*| L = K Un L";
   598     "!!K. [| InfCard(K);  InfCard(L) |] ==> K |*| L = K Un L";
   599 by (res_inst_tac [("i","K"),("j","L")] Ord_linear_le 1);
   599 by (res_inst_tac [("i","K"),("j","L")] Ord_linear_le 1);
   602 by (resolve_tac [Un_commute RS ssubst] 1);
   602 by (resolve_tac [Un_commute RS ssubst] 1);
   603 by (ALLGOALS
   603 by (ALLGOALS
   604     (asm_simp_tac 
   604     (asm_simp_tac 
   605      (ZF_ss addsimps [InfCard_is_Limit RS Limit_has_0, InfCard_le_cmult_eq,
   605      (ZF_ss addsimps [InfCard_is_Limit RS Limit_has_0, InfCard_le_cmult_eq,
   606 		      subset_Un_iff2 RS iffD1, le_imp_subset])));
   606 		      subset_Un_iff2 RS iffD1, le_imp_subset])));
   607 val InfCard_cmult_eq = result();
   607 qed "InfCard_cmult_eq";
   608 
   608 
   609 (*This proof appear to be the simplest!*)
   609 (*This proof appear to be the simplest!*)
   610 goal CardinalArith.thy "!!K. InfCard(K) ==> K |+| K = K";
   610 goal CardinalArith.thy "!!K. InfCard(K) ==> K |+| K = K";
   611 by (asm_simp_tac
   611 by (asm_simp_tac
   612     (ZF_ss addsimps [cmult_2 RS sym, InfCard_is_Card, cmult_commute]) 1);
   612     (ZF_ss addsimps [cmult_2 RS sym, InfCard_is_Card, cmult_commute]) 1);
   613 by (resolve_tac [InfCard_le_cmult_eq] 1);
   613 by (resolve_tac [InfCard_le_cmult_eq] 1);
   614 by (typechk_tac [Ord_0, le_refl, leI]);
   614 by (typechk_tac [Ord_0, le_refl, leI]);
   615 by (typechk_tac [InfCard_is_Limit, Limit_has_0, Limit_has_succ]);
   615 by (typechk_tac [InfCard_is_Limit, Limit_has_0, Limit_has_succ]);
   616 val InfCard_cdouble_eq = result();
   616 qed "InfCard_cdouble_eq";
   617 
   617 
   618 (*Corollary 10.13 (1), for cardinal addition*)
   618 (*Corollary 10.13 (1), for cardinal addition*)
   619 goal CardinalArith.thy "!!K. [| InfCard(K);  L le K |] ==> K |+| L = K";
   619 goal CardinalArith.thy "!!K. [| InfCard(K);  L le K |] ==> K |+| L = K";
   620 by (resolve_tac [le_anti_sym] 1);
   620 by (resolve_tac [le_anti_sym] 1);
   621 by (eresolve_tac [ltE] 2 THEN
   621 by (eresolve_tac [ltE] 2 THEN
   622     REPEAT (ares_tac [cadd_le_self, InfCard_is_Card] 2));
   622     REPEAT (ares_tac [cadd_le_self, InfCard_is_Card] 2));
   623 by (forward_tac [InfCard_is_Card RS Card_is_Ord RS le_refl] 1);
   623 by (forward_tac [InfCard_is_Card RS Card_is_Ord RS le_refl] 1);
   624 by (resolve_tac [cadd_le_mono RS le_trans] 1 THEN REPEAT (assume_tac 1));
   624 by (resolve_tac [cadd_le_mono RS le_trans] 1 THEN REPEAT (assume_tac 1));
   625 by (asm_simp_tac (ZF_ss addsimps [InfCard_cdouble_eq]) 1);
   625 by (asm_simp_tac (ZF_ss addsimps [InfCard_cdouble_eq]) 1);
   626 val InfCard_le_cadd_eq = result();
   626 qed "InfCard_le_cadd_eq";
   627 
   627 
   628 goal CardinalArith.thy
   628 goal CardinalArith.thy
   629     "!!K. [| InfCard(K);  InfCard(L) |] ==> K |+| L = K Un L";
   629     "!!K. [| InfCard(K);  InfCard(L) |] ==> K |+| L = K Un L";
   630 by (res_inst_tac [("i","K"),("j","L")] Ord_linear_le 1);
   630 by (res_inst_tac [("i","K"),("j","L")] Ord_linear_le 1);
   631 by (typechk_tac [InfCard_is_Card, Card_is_Ord]);
   631 by (typechk_tac [InfCard_is_Card, Card_is_Ord]);
   633 by (resolve_tac [Un_commute RS ssubst] 1);
   633 by (resolve_tac [Un_commute RS ssubst] 1);
   634 by (ALLGOALS
   634 by (ALLGOALS
   635     (asm_simp_tac 
   635     (asm_simp_tac 
   636      (ZF_ss addsimps [InfCard_le_cadd_eq,
   636      (ZF_ss addsimps [InfCard_le_cadd_eq,
   637 		      subset_Un_iff2 RS iffD1, le_imp_subset])));
   637 		      subset_Un_iff2 RS iffD1, le_imp_subset])));
   638 val InfCard_cadd_eq = result();
   638 qed "InfCard_cadd_eq";
   639 
   639 
   640 (*The other part, Corollary 10.13 (2), refers to the cardinality of the set
   640 (*The other part, Corollary 10.13 (2), refers to the cardinality of the set
   641   of all n-tuples of elements of K.  A better version for the Isabelle theory
   641   of all n-tuples of elements of K.  A better version for the Isabelle theory
   642   might be  InfCard(K) ==> |list(K)| = K.
   642   might be  InfCard(K) ==> |list(K)| = K.
   643 *)
   643 *)