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 *) |