385 using card_of_ordIso unfolding bij_betw_def inj_on_def by blast |
385 using card_of_ordIso unfolding bij_betw_def inj_on_def by blast |
386 |
386 |
387 lemma card_of_image: |
387 lemma card_of_image: |
388 "|f ` A| <=o |A|" |
388 "|f ` A| <=o |A|" |
389 proof(cases "A = {}", simp add: card_of_empty) |
389 proof(cases "A = {}", simp add: card_of_empty) |
390 assume "A ~= {}" |
390 assume "A \<noteq> {}" |
391 hence "f ` A ~= {}" by auto |
391 hence "f ` A \<noteq> {}" by auto |
392 thus "|f ` A| \<le>o |A|" |
392 thus "|f ` A| \<le>o |A|" |
393 using card_of_ordLeq2[of "f ` A" A] by auto |
393 using card_of_ordLeq2[of "f ` A" A] by auto |
394 qed |
394 qed |
395 |
395 |
396 lemma surj_imp_ordLeq: |
396 lemma surj_imp_ordLeq: |
884 have "Field r \<noteq> under r a" |
884 have "Field r \<noteq> under r a" |
885 using assms Card_order_infinite_not_under by blast |
885 using assms Card_order_infinite_not_under by blast |
886 moreover have "under r a \<le> Field r" |
886 moreover have "under r a \<le> Field r" |
887 using under_Field . |
887 using under_Field . |
888 ultimately have "under r a < Field r" by blast |
888 ultimately have "under r a < Field r" by blast |
889 then obtain b where 1: "b : Field r \<and> ~ (b,a) : r" |
889 then obtain b where 1: "b \<in> Field r \<and> \<not> (b,a) \<in> r" |
890 unfolding under_def by blast |
890 unfolding under_def by blast |
891 moreover have ba: "b \<noteq> a" |
891 moreover have ba: "b \<noteq> a" |
892 using 1 r unfolding card_order_on_def well_order_on_def |
892 using 1 r unfolding card_order_on_def well_order_on_def |
893 linear_order_on_def partial_order_on_def preorder_on_def refl_on_def by auto |
893 linear_order_on_def partial_order_on_def preorder_on_def refl_on_def by auto |
894 ultimately have "(a,b) : r" |
894 ultimately have "(a,b) : r" |
1098 let ?A' = "?Inl ` A \<union> {?Inr b1}" |
1098 let ?A' = "?Inl ` A \<union> {?Inr b1}" |
1099 obtain g where "bij_betw g (?Inl ` A) ?A'" |
1099 obtain g where "bij_betw g (?Inl ` A) ?A'" |
1100 using 3 infinite_imp_bij_betw2[of "?Inl ` A"] by auto |
1100 using 3 infinite_imp_bij_betw2[of "?Inl ` A"] by auto |
1101 moreover have "?A' = A <+> B" using Case1 by blast |
1101 moreover have "?A' = A <+> B" using Case1 by blast |
1102 ultimately have "bij_betw g (?Inl ` A) (A <+> B)" by simp |
1102 ultimately have "bij_betw g (?Inl ` A) (A <+> B)" by simp |
1103 hence "bij_betw (g o ?Inl) A (A <+> B)" |
1103 hence "bij_betw (g \<circ> ?Inl) A (A <+> B)" |
1104 using 2 by (auto simp add: bij_betw_trans) |
1104 using 2 by (auto simp add: bij_betw_trans) |
1105 thus ?thesis using card_of_ordIso ordIso_symmetric by blast |
1105 thus ?thesis using card_of_ordIso ordIso_symmetric by blast |
1106 next |
1106 next |
1107 assume Case2: "B \<noteq> {b1}" |
1107 assume Case2: "B \<noteq> {b1}" |
1108 with * 1 obtain b2 where 3: "b1 \<noteq> b2 \<and> {b1,b2} \<le> B" by fastforce |
1108 with * 1 obtain b2 where 3: "b1 \<noteq> b2 \<and> {b1,b2} \<le> B" by fastforce |
1508 "cofinal A r \<equiv> |
1508 "cofinal A r \<equiv> |
1509 ALL a : Field r. EX b : A. a \<noteq> b \<and> (a,b) : r" |
1509 ALL a : Field r. EX b : A. a \<noteq> b \<and> (a,b) : r" |
1510 |
1510 |
1511 definition regularCard where |
1511 definition regularCard where |
1512 "regularCard r \<equiv> |
1512 "regularCard r \<equiv> |
1513 ALL K. K \<le> Field r \<and> cofinal K r \<longrightarrow> |K| =o r" |
1513 \<forall>K. K \<le> Field r \<and> cofinal K r \<longrightarrow> |K| =o r" |
1514 |
1514 |
1515 definition relChain where |
1515 definition relChain where |
1516 "relChain r As \<equiv> |
1516 "relChain r As \<equiv> |
1517 ALL i j. (i,j) \<in> r \<longrightarrow> As i \<le> As j" |
1517 \<forall>i j. (i,j) \<in> r \<longrightarrow> As i \<le> As j" |
1518 |
1518 |
1519 lemma regularCard_UNION: |
1519 lemma regularCard_UNION: |
1520 assumes r: "Card_order r" "regularCard r" |
1520 assumes r: "Card_order r" "regularCard r" |
1521 and As: "relChain r As" |
1521 and As: "relChain r As" |
1522 and Bsub: "B \<le> (UN i : Field r. As i)" |
1522 and Bsub: "B \<le> (UN i : Field r. As i)" |
1523 and cardB: "|B| <o r" |
1523 and cardB: "|B| <o r" |
1524 shows "EX i : Field r. B \<le> As i" |
1524 shows "EX i : Field r. B \<le> As i" |
1525 proof- |
1525 proof- |
1526 let ?phi = "%b j. j : Field r \<and> b : As j" |
1526 let ?phi = "\<lambda>b j. j \<in> Field r \<and> b \<in> As j" |
1527 have "ALL b : B. EX j. ?phi b j" using Bsub by blast |
1527 have "\<forall>b\<in>B. \<exists>j. ?phi b j" using Bsub by blast |
1528 then obtain f where f: "!! b. b : B \<Longrightarrow> ?phi b (f b)" |
1528 then obtain f where f: "!! b. b : B \<Longrightarrow> ?phi b (f b)" |
1529 using bchoice[of B ?phi] by blast |
1529 using bchoice[of B ?phi] by blast |
1530 let ?K = "f ` B" |
1530 let ?K = "f ` B" |
1531 {assume 1: "!! i. i : Field r \<Longrightarrow> ~ B \<le> As i" |
1531 {assume 1: "\<And>i. i \<in> Field r \<Longrightarrow> \<not> B \<le> As i" |
1532 have 2: "cofinal ?K r" |
1532 have 2: "cofinal ?K r" |
1533 unfolding cofinal_def proof auto |
1533 unfolding cofinal_def proof auto |
1534 fix i assume i: "i : Field r" |
1534 fix i assume i: "i : Field r" |
1535 with 1 obtain b where b: "b : B \<and> b \<notin> As i" by blast |
1535 with 1 obtain b where b: "b : B \<and> b \<notin> As i" by blast |
1536 hence "i \<noteq> f b \<and> ~ (f b,i) : r" |
1536 hence "i \<noteq> f b \<and> \<not> (f b,i) \<in> r" |
1537 using As f unfolding relChain_def by auto |
1537 using As f unfolding relChain_def by auto |
1538 hence "i \<noteq> f b \<and> (i, f b) : r" using r |
1538 hence "i \<noteq> f b \<and> (i, f b) : r" using r |
1539 unfolding card_order_on_def well_order_on_def linear_order_on_def |
1539 unfolding card_order_on_def well_order_on_def linear_order_on_def |
1540 total_on_def using i f b by auto |
1540 total_on_def using i f b by auto |
1541 with b show "\<exists>b\<in>B. i \<noteq> f b \<and> (i, f b) \<in> r" by blast |
1541 with b show "\<exists>b\<in>B. i \<noteq> f b \<and> (i, f b) \<in> r" by blast |