src/HOL/BNF_Cardinal_Order_Relation.thy
changeset 67091 1393c2340eec
parent 63980 f8e556c8ad6f
child 67613 ce654b0e6d69
equal deleted inserted replaced
67090:0ec94bb9cec4 67091:1393c2340eec
   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