src/HOL/BNF_Cardinal_Arithmetic.thy
changeset 55056 b5c94200d081
parent 55055 3f0dfce0e27a
child 55059 ef2e0fb783c6
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/HOL/BNF_Cardinal_Arithmetic.thy	Mon Jan 20 18:24:55 2014 +0100
     1.3 @@ -0,0 +1,706 @@
     1.4 +(*  Title:      HOL/BNF_Cardinal_Arithmetic.thy
     1.5 +    Author:     Dmitriy Traytel, TU Muenchen
     1.6 +    Copyright   2012
     1.7 +
     1.8 +Cardinal arithmetic (BNF).
     1.9 +*)
    1.10 +
    1.11 +header {* Cardinal Arithmetic (BNF) *}
    1.12 +
    1.13 +theory BNF_Cardinal_Arithmetic
    1.14 +imports BNF_Cardinal_Order_Relation
    1.15 +begin
    1.16 +
    1.17 +lemma dir_image: "\<lbrakk>\<And>x y. (f x = f y) = (x = y); Card_order r\<rbrakk> \<Longrightarrow> r =o dir_image r f"
    1.18 +by (rule dir_image_ordIso) (auto simp add: inj_on_def card_order_on_def)
    1.19 +
    1.20 +(*should supersede a weaker lemma from the library*)
    1.21 +lemma dir_image_Field: "Field (dir_image r f) = f ` Field r"
    1.22 +unfolding dir_image_def Field_def Range_def Domain_def by fast
    1.23 +
    1.24 +lemma card_order_dir_image:
    1.25 +  assumes bij: "bij f" and co: "card_order r"
    1.26 +  shows "card_order (dir_image r f)"
    1.27 +proof -
    1.28 +  from assms have "Field (dir_image r f) = UNIV"
    1.29 +    using card_order_on_Card_order[of UNIV r] unfolding bij_def dir_image_Field by auto
    1.30 +  moreover from bij have "\<And>x y. (f x = f y) = (x = y)" unfolding bij_def inj_on_def by auto
    1.31 +  with co have "Card_order (dir_image r f)"
    1.32 +    using card_order_on_Card_order[of UNIV r] Card_order_ordIso2[OF _ dir_image] by blast
    1.33 +  ultimately show ?thesis by auto
    1.34 +qed
    1.35 +
    1.36 +lemma ordIso_refl: "Card_order r \<Longrightarrow> r =o r"
    1.37 +by (rule card_order_on_ordIso)
    1.38 +
    1.39 +lemma ordLeq_refl: "Card_order r \<Longrightarrow> r \<le>o r"
    1.40 +by (rule ordIso_imp_ordLeq, rule card_order_on_ordIso)
    1.41 +
    1.42 +lemma card_of_ordIso_subst: "A = B \<Longrightarrow> |A| =o |B|"
    1.43 +by (simp only: ordIso_refl card_of_Card_order)
    1.44 +
    1.45 +lemma Field_card_order: "card_order r \<Longrightarrow> Field r = UNIV"
    1.46 +using card_order_on_Card_order[of UNIV r] by simp
    1.47 +
    1.48 +lemma card_of_Times_Plus_distrib:
    1.49 +  "|A <*> (B <+> C)| =o |A <*> B <+> A <*> C|" (is "|?RHS| =o |?LHS|")
    1.50 +proof -
    1.51 +  let ?f = "\<lambda>(a, bc). case bc of Inl b \<Rightarrow> Inl (a, b) | Inr c \<Rightarrow> Inr (a, c)"
    1.52 +  have "bij_betw ?f ?RHS ?LHS" unfolding bij_betw_def inj_on_def by force
    1.53 +  thus ?thesis using card_of_ordIso by blast
    1.54 +qed
    1.55 +
    1.56 +lemma Func_Times_Range:
    1.57 +  "|Func A (B <*> C)| =o |Func A B <*> Func A C|" (is "|?LHS| =o |?RHS|")
    1.58 +proof -
    1.59 +  let ?F = "\<lambda>fg. (\<lambda>x. if x \<in> A then fst (fg x) else undefined,
    1.60 +                  \<lambda>x. if x \<in> A then snd (fg x) else undefined)"
    1.61 +  let ?G = "\<lambda>(f, g) x. if x \<in> A then (f x, g x) else undefined"
    1.62 +  have "bij_betw ?F ?LHS ?RHS" unfolding bij_betw_def inj_on_def
    1.63 +  apply safe
    1.64 +     apply (simp add: Func_def fun_eq_iff)
    1.65 +     apply (metis (no_types) pair_collapse)
    1.66 +    apply (auto simp: Func_def fun_eq_iff)[2]
    1.67 +  proof -
    1.68 +    fix f g assume "f \<in> Func A B" "g \<in> Func A C"
    1.69 +    thus "(f, g) \<in> ?F ` Func A (B \<times> C)"
    1.70 +      by (intro image_eqI[of _ _ "?G (f, g)"]) (auto simp: Func_def)
    1.71 +  qed
    1.72 +  thus ?thesis using card_of_ordIso by blast
    1.73 +qed
    1.74 +
    1.75 +
    1.76 +subsection {* Zero *}
    1.77 +
    1.78 +definition czero where
    1.79 +  "czero = card_of {}"
    1.80 +
    1.81 +lemma czero_ordIso:
    1.82 +  "czero =o czero"
    1.83 +using card_of_empty_ordIso by (simp add: czero_def)
    1.84 +
    1.85 +lemma card_of_ordIso_czero_iff_empty:
    1.86 +  "|A| =o (czero :: 'b rel) \<longleftrightarrow> A = ({} :: 'a set)"
    1.87 +unfolding czero_def by (rule iffI[OF card_of_empty2]) (auto simp: card_of_refl card_of_empty_ordIso)
    1.88 +
    1.89 +(* A "not czero" Cardinal predicate *)
    1.90 +abbreviation Cnotzero where
    1.91 +  "Cnotzero (r :: 'a rel) \<equiv> \<not>(r =o (czero :: 'a rel)) \<and> Card_order r"
    1.92 +
    1.93 +(*helper*)
    1.94 +lemma Cnotzero_imp_not_empty: "Cnotzero r \<Longrightarrow> Field r \<noteq> {}"
    1.95 +by (metis Card_order_iff_ordIso_card_of czero_def)
    1.96 +
    1.97 +lemma czeroI:
    1.98 +  "\<lbrakk>Card_order r; Field r = {}\<rbrakk> \<Longrightarrow> r =o czero"
    1.99 +using Cnotzero_imp_not_empty ordIso_transitive[OF _ czero_ordIso] by blast
   1.100 +
   1.101 +lemma czeroE:
   1.102 +  "r =o czero \<Longrightarrow> Field r = {}"
   1.103 +unfolding czero_def
   1.104 +by (drule card_of_cong) (simp only: Field_card_of card_of_empty2)
   1.105 +
   1.106 +lemma Cnotzero_mono:
   1.107 +  "\<lbrakk>Cnotzero r; Card_order q; r \<le>o q\<rbrakk> \<Longrightarrow> Cnotzero q"
   1.108 +apply (rule ccontr)
   1.109 +apply auto
   1.110 +apply (drule czeroE)
   1.111 +apply (erule notE)
   1.112 +apply (erule czeroI)
   1.113 +apply (drule card_of_mono2)
   1.114 +apply (simp only: card_of_empty3)
   1.115 +done
   1.116 +
   1.117 +subsection {* (In)finite cardinals *}
   1.118 +
   1.119 +definition cinfinite where
   1.120 +  "cinfinite r = (\<not> finite (Field r))"
   1.121 +
   1.122 +abbreviation Cinfinite where
   1.123 +  "Cinfinite r \<equiv> cinfinite r \<and> Card_order r"
   1.124 +
   1.125 +definition cfinite where
   1.126 +  "cfinite r = finite (Field r)"
   1.127 +
   1.128 +abbreviation Cfinite where
   1.129 +  "Cfinite r \<equiv> cfinite r \<and> Card_order r"
   1.130 +
   1.131 +lemma Cfinite_ordLess_Cinfinite: "\<lbrakk>Cfinite r; Cinfinite s\<rbrakk> \<Longrightarrow> r <o s"
   1.132 +  unfolding cfinite_def cinfinite_def
   1.133 +  by (metis card_order_on_well_order_on finite_ordLess_infinite)
   1.134 +
   1.135 +lemmas natLeq_card_order = natLeq_Card_order[unfolded Field_natLeq]
   1.136 +
   1.137 +lemma natLeq_cinfinite: "cinfinite natLeq"
   1.138 +unfolding cinfinite_def Field_natLeq by (metis infinite_UNIV_nat)
   1.139 +
   1.140 +lemma natLeq_ordLeq_cinfinite:
   1.141 +  assumes inf: "Cinfinite r"
   1.142 +  shows "natLeq \<le>o r"
   1.143 +proof -
   1.144 +  from inf have "natLeq \<le>o |Field r|" by (metis cinfinite_def infinite_iff_natLeq_ordLeq)
   1.145 +  also from inf have "|Field r| =o r" by (simp add: card_of_unique ordIso_symmetric)
   1.146 +  finally show ?thesis .
   1.147 +qed
   1.148 +
   1.149 +lemma cinfinite_not_czero: "cinfinite r \<Longrightarrow> \<not> (r =o (czero :: 'a rel))"
   1.150 +unfolding cinfinite_def by (metis czeroE finite.emptyI)
   1.151 +
   1.152 +lemma Cinfinite_Cnotzero: "Cinfinite r \<Longrightarrow> Cnotzero r"
   1.153 +by (metis cinfinite_not_czero)
   1.154 +
   1.155 +lemma Cinfinite_cong: "\<lbrakk>r1 =o r2; Cinfinite r1\<rbrakk> \<Longrightarrow> Cinfinite r2"
   1.156 +by (metis Card_order_ordIso2 card_of_mono2 card_of_ordLeq_infinite cinfinite_def ordIso_iff_ordLeq)
   1.157 +
   1.158 +lemma cinfinite_mono: "\<lbrakk>r1 \<le>o r2; cinfinite r1\<rbrakk> \<Longrightarrow> cinfinite r2"
   1.159 +by (metis card_of_mono2 card_of_ordLeq_infinite cinfinite_def)
   1.160 +
   1.161 +
   1.162 +subsection {* Binary sum *}
   1.163 +
   1.164 +definition csum (infixr "+c" 65) where
   1.165 +  "r1 +c r2 \<equiv> |Field r1 <+> Field r2|"
   1.166 +
   1.167 +lemma Field_csum: "Field (r +c s) = Inl ` Field r \<union> Inr ` Field s"
   1.168 +  unfolding csum_def Field_card_of by auto
   1.169 +
   1.170 +lemma Card_order_csum:
   1.171 +  "Card_order (r1 +c r2)"
   1.172 +unfolding csum_def by (simp add: card_of_Card_order)
   1.173 +
   1.174 +lemma csum_Cnotzero1:
   1.175 +  "Cnotzero r1 \<Longrightarrow> Cnotzero (r1 +c r2)"
   1.176 +unfolding csum_def
   1.177 +by (metis Cnotzero_imp_not_empty Plus_eq_empty_conv card_of_Card_order card_of_ordIso_czero_iff_empty)
   1.178 +
   1.179 +lemma card_order_csum:
   1.180 +  assumes "card_order r1" "card_order r2"
   1.181 +  shows "card_order (r1 +c r2)"
   1.182 +proof -
   1.183 +  have "Field r1 = UNIV" "Field r2 = UNIV" using assms card_order_on_Card_order by auto
   1.184 +  thus ?thesis unfolding csum_def by (auto simp: card_of_card_order_on)
   1.185 +qed
   1.186 +
   1.187 +lemma cinfinite_csum:
   1.188 +  "cinfinite r1 \<or> cinfinite r2 \<Longrightarrow> cinfinite (r1 +c r2)"
   1.189 +unfolding cinfinite_def csum_def by (auto simp: Field_card_of)
   1.190 +
   1.191 +lemma Cinfinite_csum1:
   1.192 +  "Cinfinite r1 \<Longrightarrow> Cinfinite (r1 +c r2)"
   1.193 +unfolding cinfinite_def csum_def by (metis Field_card_of card_of_Card_order finite_Plus_iff)
   1.194 +
   1.195 +lemma Cinfinite_csum:
   1.196 +  "Cinfinite r1 \<or> Cinfinite r2 \<Longrightarrow> Cinfinite (r1 +c r2)"
   1.197 +unfolding cinfinite_def csum_def by (metis Field_card_of card_of_Card_order finite_Plus_iff)
   1.198 +
   1.199 +lemma Cinfinite_csum_strong:
   1.200 +  "\<lbrakk>Cinfinite r1; Cinfinite r2\<rbrakk> \<Longrightarrow> Cinfinite (r1 +c r2)"
   1.201 +by (metis Cinfinite_csum)
   1.202 +
   1.203 +lemma csum_cong: "\<lbrakk>p1 =o r1; p2 =o r2\<rbrakk> \<Longrightarrow> p1 +c p2 =o r1 +c r2"
   1.204 +by (simp only: csum_def ordIso_Plus_cong)
   1.205 +
   1.206 +lemma csum_cong1: "p1 =o r1 \<Longrightarrow> p1 +c q =o r1 +c q"
   1.207 +by (simp only: csum_def ordIso_Plus_cong1)
   1.208 +
   1.209 +lemma csum_cong2: "p2 =o r2 \<Longrightarrow> q +c p2 =o q +c r2"
   1.210 +by (simp only: csum_def ordIso_Plus_cong2)
   1.211 +
   1.212 +lemma csum_mono: "\<lbrakk>p1 \<le>o r1; p2 \<le>o r2\<rbrakk> \<Longrightarrow> p1 +c p2 \<le>o r1 +c r2"
   1.213 +by (simp only: csum_def ordLeq_Plus_mono)
   1.214 +
   1.215 +lemma csum_mono1: "p1 \<le>o r1 \<Longrightarrow> p1 +c q \<le>o r1 +c q"
   1.216 +by (simp only: csum_def ordLeq_Plus_mono1)
   1.217 +
   1.218 +lemma csum_mono2: "p2 \<le>o r2 \<Longrightarrow> q +c p2 \<le>o q +c r2"
   1.219 +by (simp only: csum_def ordLeq_Plus_mono2)
   1.220 +
   1.221 +lemma ordLeq_csum1: "Card_order p1 \<Longrightarrow> p1 \<le>o p1 +c p2"
   1.222 +by (simp only: csum_def Card_order_Plus1)
   1.223 +
   1.224 +lemma ordLeq_csum2: "Card_order p2 \<Longrightarrow> p2 \<le>o p1 +c p2"
   1.225 +by (simp only: csum_def Card_order_Plus2)
   1.226 +
   1.227 +lemma csum_com: "p1 +c p2 =o p2 +c p1"
   1.228 +by (simp only: csum_def card_of_Plus_commute)
   1.229 +
   1.230 +lemma csum_assoc: "(p1 +c p2) +c p3 =o p1 +c p2 +c p3"
   1.231 +by (simp only: csum_def Field_card_of card_of_Plus_assoc)
   1.232 +
   1.233 +lemma Cfinite_csum: "\<lbrakk>Cfinite r; Cfinite s\<rbrakk> \<Longrightarrow> Cfinite (r +c s)"
   1.234 +  unfolding cfinite_def csum_def Field_card_of using card_of_card_order_on by simp
   1.235 +
   1.236 +lemma csum_csum: "(r1 +c r2) +c (r3 +c r4) =o (r1 +c r3) +c (r2 +c r4)"
   1.237 +proof -
   1.238 +  have "(r1 +c r2) +c (r3 +c r4) =o r1 +c r2 +c (r3 +c r4)"
   1.239 +    by (metis csum_assoc)
   1.240 +  also have "r1 +c r2 +c (r3 +c r4) =o r1 +c (r2 +c r3) +c r4"
   1.241 +    by (metis csum_assoc csum_cong2 ordIso_symmetric)
   1.242 +  also have "r1 +c (r2 +c r3) +c r4 =o r1 +c (r3 +c r2) +c r4"
   1.243 +    by (metis csum_com csum_cong1 csum_cong2)
   1.244 +  also have "r1 +c (r3 +c r2) +c r4 =o r1 +c r3 +c r2 +c r4"
   1.245 +    by (metis csum_assoc csum_cong2 ordIso_symmetric)
   1.246 +  also have "r1 +c r3 +c r2 +c r4 =o (r1 +c r3) +c (r2 +c r4)"
   1.247 +    by (metis csum_assoc ordIso_symmetric)
   1.248 +  finally show ?thesis .
   1.249 +qed
   1.250 +
   1.251 +lemma Plus_csum: "|A <+> B| =o |A| +c |B|"
   1.252 +by (simp only: csum_def Field_card_of card_of_refl)
   1.253 +
   1.254 +lemma Un_csum: "|A \<union> B| \<le>o |A| +c |B|"
   1.255 +using ordLeq_ordIso_trans[OF card_of_Un_Plus_ordLeq Plus_csum] by blast
   1.256 +
   1.257 +
   1.258 +subsection {* One *}
   1.259 +
   1.260 +definition cone where
   1.261 +  "cone = card_of {()}"
   1.262 +
   1.263 +lemma Card_order_cone: "Card_order cone"
   1.264 +unfolding cone_def by (rule card_of_Card_order)
   1.265 +
   1.266 +lemma Cfinite_cone: "Cfinite cone"
   1.267 +  unfolding cfinite_def by (simp add: Card_order_cone)
   1.268 +
   1.269 +lemma cone_not_czero: "\<not> (cone =o czero)"
   1.270 +unfolding czero_def cone_def by (metis empty_not_insert card_of_empty3[of "{()}"] ordIso_iff_ordLeq)
   1.271 +
   1.272 +lemma cone_ordLeq_Cnotzero: "Cnotzero r \<Longrightarrow> cone \<le>o r"
   1.273 +unfolding cone_def by (metis Card_order_singl_ordLeq czeroI)
   1.274 +
   1.275 +
   1.276 +subsection {* Two *}
   1.277 +
   1.278 +definition ctwo where
   1.279 +  "ctwo = |UNIV :: bool set|"
   1.280 +
   1.281 +lemma Card_order_ctwo: "Card_order ctwo"
   1.282 +unfolding ctwo_def by (rule card_of_Card_order)
   1.283 +
   1.284 +lemma ctwo_not_czero: "\<not> (ctwo =o czero)"
   1.285 +using card_of_empty3[of "UNIV :: bool set"] ordIso_iff_ordLeq
   1.286 +unfolding czero_def ctwo_def by (metis UNIV_not_empty)
   1.287 +
   1.288 +lemma ctwo_Cnotzero: "Cnotzero ctwo"
   1.289 +by (simp add: ctwo_not_czero Card_order_ctwo)
   1.290 +
   1.291 +
   1.292 +subsection {* Family sum *}
   1.293 +
   1.294 +definition Csum where
   1.295 +  "Csum r rs \<equiv> |SIGMA i : Field r. Field (rs i)|"
   1.296 +
   1.297 +(* Similar setup to the one for SIGMA from theory Big_Operators: *)
   1.298 +syntax "_Csum" ::
   1.299 +  "pttrn => ('a * 'a) set => 'b * 'b set => (('a * 'b) * ('a * 'b)) set"
   1.300 +  ("(3CSUM _:_. _)" [0, 51, 10] 10)
   1.301 +
   1.302 +translations
   1.303 +  "CSUM i:r. rs" == "CONST Csum r (%i. rs)"
   1.304 +
   1.305 +lemma SIGMA_CSUM: "|SIGMA i : I. As i| = (CSUM i : |I|. |As i| )"
   1.306 +by (auto simp: Csum_def Field_card_of)
   1.307 +
   1.308 +(* NB: Always, under the cardinal operator,
   1.309 +operations on sets are reduced automatically to operations on cardinals.
   1.310 +This should make cardinal reasoning more direct and natural.  *)
   1.311 +
   1.312 +
   1.313 +subsection {* Product *}
   1.314 +
   1.315 +definition cprod (infixr "*c" 80) where
   1.316 +  "r1 *c r2 = |Field r1 <*> Field r2|"
   1.317 +
   1.318 +lemma card_order_cprod:
   1.319 +  assumes "card_order r1" "card_order r2"
   1.320 +  shows "card_order (r1 *c r2)"
   1.321 +proof -
   1.322 +  have "Field r1 = UNIV" "Field r2 = UNIV" using assms card_order_on_Card_order by auto
   1.323 +  thus ?thesis by (auto simp: cprod_def card_of_card_order_on)
   1.324 +qed
   1.325 +
   1.326 +lemma Card_order_cprod: "Card_order (r1 *c r2)"
   1.327 +by (simp only: cprod_def Field_card_of card_of_card_order_on)
   1.328 +
   1.329 +lemma cprod_mono1: "p1 \<le>o r1 \<Longrightarrow> p1 *c q \<le>o r1 *c q"
   1.330 +by (simp only: cprod_def ordLeq_Times_mono1)
   1.331 +
   1.332 +lemma cprod_mono2: "p2 \<le>o r2 \<Longrightarrow> q *c p2 \<le>o q *c r2"
   1.333 +by (simp only: cprod_def ordLeq_Times_mono2)
   1.334 +
   1.335 +lemma ordLeq_cprod2: "\<lbrakk>Cnotzero p1; Card_order p2\<rbrakk> \<Longrightarrow> p2 \<le>o p1 *c p2"
   1.336 +unfolding cprod_def by (metis Card_order_Times2 czeroI)
   1.337 +
   1.338 +lemma cinfinite_cprod: "\<lbrakk>cinfinite r1; cinfinite r2\<rbrakk> \<Longrightarrow> cinfinite (r1 *c r2)"
   1.339 +by (simp add: cinfinite_def cprod_def Field_card_of infinite_cartesian_product)
   1.340 +
   1.341 +lemma cinfinite_cprod2: "\<lbrakk>Cnotzero r1; Cinfinite r2\<rbrakk> \<Longrightarrow> cinfinite (r1 *c r2)"
   1.342 +by (metis cinfinite_mono ordLeq_cprod2)
   1.343 +
   1.344 +lemma Cinfinite_cprod2: "\<lbrakk>Cnotzero r1; Cinfinite r2\<rbrakk> \<Longrightarrow> Cinfinite (r1 *c r2)"
   1.345 +by (blast intro: cinfinite_cprod2 Card_order_cprod)
   1.346 +
   1.347 +lemma cprod_com: "p1 *c p2 =o p2 *c p1"
   1.348 +by (simp only: cprod_def card_of_Times_commute)
   1.349 +
   1.350 +lemma card_of_Csum_Times:
   1.351 +  "\<forall>i \<in> I. |A i| \<le>o |B| \<Longrightarrow> (CSUM i : |I|. |A i| ) \<le>o |I| *c |B|"
   1.352 +by (simp only: Csum_def cprod_def Field_card_of card_of_Sigma_Times)
   1.353 +
   1.354 +lemma card_of_Csum_Times':
   1.355 +  assumes "Card_order r" "\<forall>i \<in> I. |A i| \<le>o r"
   1.356 +  shows "(CSUM i : |I|. |A i| ) \<le>o |I| *c r"
   1.357 +proof -
   1.358 +  from assms(1) have *: "r =o |Field r|" by (simp add: card_of_unique)
   1.359 +  with assms(2) have "\<forall>i \<in> I. |A i| \<le>o |Field r|" by (blast intro: ordLeq_ordIso_trans)
   1.360 +  hence "(CSUM i : |I|. |A i| ) \<le>o |I| *c |Field r|" by (simp only: card_of_Csum_Times)
   1.361 +  also from * have "|I| *c |Field r| \<le>o |I| *c r"
   1.362 +    by (simp only: Field_card_of card_of_refl cprod_def ordIso_imp_ordLeq)
   1.363 +  finally show ?thesis .
   1.364 +qed
   1.365 +
   1.366 +lemma cprod_csum_distrib1: "r1 *c r2 +c r1 *c r3 =o r1 *c (r2 +c r3)"
   1.367 +unfolding csum_def cprod_def by (simp add: Field_card_of card_of_Times_Plus_distrib ordIso_symmetric)
   1.368 +
   1.369 +lemma csum_absorb2': "\<lbrakk>Card_order r2; r1 \<le>o r2; cinfinite r1 \<or> cinfinite r2\<rbrakk> \<Longrightarrow> r1 +c r2 =o r2"
   1.370 +unfolding csum_def by (metis Card_order_Plus_infinite cinfinite_def cinfinite_mono)
   1.371 +
   1.372 +lemma csum_absorb1':
   1.373 +  assumes card: "Card_order r2"
   1.374 +  and r12: "r1 \<le>o r2" and cr12: "cinfinite r1 \<or> cinfinite r2"
   1.375 +  shows "r2 +c r1 =o r2"
   1.376 +by (rule ordIso_transitive, rule csum_com, rule csum_absorb2', (simp only: assms)+)
   1.377 +
   1.378 +lemma csum_absorb1: "\<lbrakk>Cinfinite r2; r1 \<le>o r2\<rbrakk> \<Longrightarrow> r2 +c r1 =o r2"
   1.379 +by (rule csum_absorb1') auto
   1.380 +
   1.381 +
   1.382 +subsection {* Exponentiation *}
   1.383 +
   1.384 +definition cexp (infixr "^c" 90) where
   1.385 +  "r1 ^c r2 \<equiv> |Func (Field r2) (Field r1)|"
   1.386 +
   1.387 +lemma Card_order_cexp: "Card_order (r1 ^c r2)"
   1.388 +unfolding cexp_def by (rule card_of_Card_order)
   1.389 +
   1.390 +lemma cexp_mono':
   1.391 +  assumes 1: "p1 \<le>o r1" and 2: "p2 \<le>o r2"
   1.392 +  and n: "Field p2 = {} \<Longrightarrow> Field r2 = {}"
   1.393 +  shows "p1 ^c p2 \<le>o r1 ^c r2"
   1.394 +proof(cases "Field p1 = {}")
   1.395 +  case True
   1.396 +  hence "|Field |Func (Field p2) (Field p1)|| \<le>o cone"
   1.397 +    unfolding cone_def Field_card_of
   1.398 +    by (cases "Field p2 = {}", auto intro: card_of_ordLeqI2 simp: Func_empty)
   1.399 +       (metis Func_is_emp card_of_empty ex_in_conv)
   1.400 +  hence "|Func (Field p2) (Field p1)| \<le>o cone" by (simp add: Field_card_of cexp_def)
   1.401 +  hence "p1 ^c p2 \<le>o cone" unfolding cexp_def .
   1.402 +  thus ?thesis
   1.403 +  proof (cases "Field p2 = {}")
   1.404 +    case True
   1.405 +    with n have "Field r2 = {}" .
   1.406 +    hence "cone \<le>o r1 ^c r2" unfolding cone_def cexp_def Func_def by (auto intro: card_of_ordLeqI)
   1.407 +    thus ?thesis using `p1 ^c p2 \<le>o cone` ordLeq_transitive by auto
   1.408 +  next
   1.409 +    case False with True have "|Field (p1 ^c p2)| =o czero"
   1.410 +      unfolding card_of_ordIso_czero_iff_empty cexp_def Field_card_of Func_def by auto
   1.411 +    thus ?thesis unfolding cexp_def card_of_ordIso_czero_iff_empty Field_card_of
   1.412 +      by (simp add: card_of_empty)
   1.413 +  qed
   1.414 +next
   1.415 +  case False
   1.416 +  have 1: "|Field p1| \<le>o |Field r1|" and 2: "|Field p2| \<le>o |Field r2|"
   1.417 +    using 1 2 by (auto simp: card_of_mono2)
   1.418 +  obtain f1 where f1: "f1 ` Field r1 = Field p1"
   1.419 +    using 1 unfolding card_of_ordLeq2[OF False, symmetric] by auto
   1.420 +  obtain f2 where f2: "inj_on f2 (Field p2)" "f2 ` Field p2 \<subseteq> Field r2"
   1.421 +    using 2 unfolding card_of_ordLeq[symmetric] by blast
   1.422 +  have 0: "Func_map (Field p2) f1 f2 ` (Field (r1 ^c r2)) = Field (p1 ^c p2)"
   1.423 +    unfolding cexp_def Field_card_of using Func_map_surj[OF f1 f2 n, symmetric] .
   1.424 +  have 00: "Field (p1 ^c p2) \<noteq> {}" unfolding cexp_def Field_card_of Func_is_emp
   1.425 +    using False by simp
   1.426 +  show ?thesis
   1.427 +    using 0 card_of_ordLeq2[OF 00] unfolding cexp_def Field_card_of by blast
   1.428 +qed
   1.429 +
   1.430 +lemma cexp_mono:
   1.431 +  assumes 1: "p1 \<le>o r1" and 2: "p2 \<le>o r2"
   1.432 +  and n: "p2 =o czero \<Longrightarrow> r2 =o czero" and card: "Card_order p2"
   1.433 +  shows "p1 ^c p2 \<le>o r1 ^c r2"
   1.434 +  by (metis (full_types) "1" "2" card cexp_mono' czeroE czeroI n)
   1.435 +
   1.436 +lemma cexp_mono1:
   1.437 +  assumes 1: "p1 \<le>o r1" and q: "Card_order q"
   1.438 +  shows "p1 ^c q \<le>o r1 ^c q"
   1.439 +using ordLeq_refl[OF q] by (rule cexp_mono[OF 1]) (auto simp: q)
   1.440 +
   1.441 +lemma cexp_mono2':
   1.442 +  assumes 2: "p2 \<le>o r2" and q: "Card_order q"
   1.443 +  and n: "Field p2 = {} \<Longrightarrow> Field r2 = {}"
   1.444 +  shows "q ^c p2 \<le>o q ^c r2"
   1.445 +using ordLeq_refl[OF q] by (rule cexp_mono'[OF _ 2 n]) auto
   1.446 +
   1.447 +lemma cexp_mono2:
   1.448 +  assumes 2: "p2 \<le>o r2" and q: "Card_order q"
   1.449 +  and n: "p2 =o czero \<Longrightarrow> r2 =o czero" and card: "Card_order p2"
   1.450 +  shows "q ^c p2 \<le>o q ^c r2"
   1.451 +using ordLeq_refl[OF q] by (rule cexp_mono[OF _ 2 n card]) auto
   1.452 +
   1.453 +lemma cexp_mono2_Cnotzero:
   1.454 +  assumes "p2 \<le>o r2" "Card_order q" "Cnotzero p2"
   1.455 +  shows "q ^c p2 \<le>o q ^c r2"
   1.456 +by (metis assms cexp_mono2' czeroI)
   1.457 +
   1.458 +lemma cexp_cong:
   1.459 +  assumes 1: "p1 =o r1" and 2: "p2 =o r2"
   1.460 +  and Cr: "Card_order r2"
   1.461 +  and Cp: "Card_order p2"
   1.462 +  shows "p1 ^c p2 =o r1 ^c r2"
   1.463 +proof -
   1.464 +  obtain f where "bij_betw f (Field p2) (Field r2)"
   1.465 +    using 2 card_of_ordIso[of "Field p2" "Field r2"] card_of_cong by auto
   1.466 +  hence 0: "Field p2 = {} \<longleftrightarrow> Field r2 = {}" unfolding bij_betw_def by auto
   1.467 +  have r: "p2 =o czero \<Longrightarrow> r2 =o czero"
   1.468 +    and p: "r2 =o czero \<Longrightarrow> p2 =o czero"
   1.469 +     using 0 Cr Cp czeroE czeroI by auto
   1.470 +  show ?thesis using 0 1 2 unfolding ordIso_iff_ordLeq
   1.471 +    using r p cexp_mono[OF _ _ _ Cp] cexp_mono[OF _ _ _ Cr] by metis
   1.472 +qed
   1.473 +
   1.474 +lemma cexp_cong1:
   1.475 +  assumes 1: "p1 =o r1" and q: "Card_order q"
   1.476 +  shows "p1 ^c q =o r1 ^c q"
   1.477 +by (rule cexp_cong[OF 1 _ q q]) (rule ordIso_refl[OF q])
   1.478 +
   1.479 +lemma cexp_cong2:
   1.480 +  assumes 2: "p2 =o r2" and q: "Card_order q" and p: "Card_order p2"
   1.481 +  shows "q ^c p2 =o q ^c r2"
   1.482 +by (rule cexp_cong[OF _ 2]) (auto simp only: ordIso_refl Card_order_ordIso2[OF p 2] q p)
   1.483 +
   1.484 +lemma cexp_cone:
   1.485 +  assumes "Card_order r"
   1.486 +  shows "r ^c cone =o r"
   1.487 +proof -
   1.488 +  have "r ^c cone =o |Field r|"
   1.489 +    unfolding cexp_def cone_def Field_card_of Func_empty
   1.490 +      card_of_ordIso[symmetric] bij_betw_def Func_def inj_on_def image_def
   1.491 +    by (rule exI[of _ "\<lambda>f. f ()"]) auto
   1.492 +  also have "|Field r| =o r" by (rule card_of_Field_ordIso[OF assms])
   1.493 +  finally show ?thesis .
   1.494 +qed
   1.495 +
   1.496 +lemma cexp_cprod:
   1.497 +  assumes r1: "Card_order r1"
   1.498 +  shows "(r1 ^c r2) ^c r3 =o r1 ^c (r2 *c r3)" (is "?L =o ?R")
   1.499 +proof -
   1.500 +  have "?L =o r1 ^c (r3 *c r2)"
   1.501 +    unfolding cprod_def cexp_def Field_card_of
   1.502 +    using card_of_Func_Times by(rule ordIso_symmetric)
   1.503 +  also have "r1 ^c (r3 *c r2) =o ?R"
   1.504 +    apply(rule cexp_cong2) using cprod_com r1 by (auto simp: Card_order_cprod)
   1.505 +  finally show ?thesis .
   1.506 +qed
   1.507 +
   1.508 +lemma cprod_infinite1': "\<lbrakk>Cinfinite r; Cnotzero p; p \<le>o r\<rbrakk> \<Longrightarrow> r *c p =o r"
   1.509 +unfolding cinfinite_def cprod_def
   1.510 +by (rule Card_order_Times_infinite[THEN conjunct1]) (blast intro: czeroI)+
   1.511 +
   1.512 +lemma cexp_cprod_ordLeq:
   1.513 +  assumes r1: "Card_order r1" and r2: "Cinfinite r2"
   1.514 +  and r3: "Cnotzero r3" "r3 \<le>o r2"
   1.515 +  shows "(r1 ^c r2) ^c r3 =o r1 ^c r2" (is "?L =o ?R")
   1.516 +proof-
   1.517 +  have "?L =o r1 ^c (r2 *c r3)" using cexp_cprod[OF r1] .
   1.518 +  also have "r1 ^c (r2 *c r3) =o ?R"
   1.519 +  apply(rule cexp_cong2)
   1.520 +  apply(rule cprod_infinite1'[OF r2 r3]) using r1 r2 by (fastforce simp: Card_order_cprod)+
   1.521 +  finally show ?thesis .
   1.522 +qed
   1.523 +
   1.524 +lemma Cnotzero_UNIV: "Cnotzero |UNIV|"
   1.525 +by (auto simp: card_of_Card_order card_of_ordIso_czero_iff_empty)
   1.526 +
   1.527 +lemma ordLess_ctwo_cexp:
   1.528 +  assumes "Card_order r"
   1.529 +  shows "r <o ctwo ^c r"
   1.530 +proof -
   1.531 +  have "r <o |Pow (Field r)|" using assms by (rule Card_order_Pow)
   1.532 +  also have "|Pow (Field r)| =o ctwo ^c r"
   1.533 +    unfolding ctwo_def cexp_def Field_card_of by (rule card_of_Pow_Func)
   1.534 +  finally show ?thesis .
   1.535 +qed
   1.536 +
   1.537 +lemma ordLeq_cexp1:
   1.538 +  assumes "Cnotzero r" "Card_order q"
   1.539 +  shows "q \<le>o q ^c r"
   1.540 +proof (cases "q =o (czero :: 'a rel)")
   1.541 +  case True thus ?thesis by (simp only: card_of_empty cexp_def czero_def ordIso_ordLeq_trans)
   1.542 +next
   1.543 +  case False
   1.544 +  thus ?thesis
   1.545 +    apply -
   1.546 +    apply (rule ordIso_ordLeq_trans)
   1.547 +    apply (rule ordIso_symmetric)
   1.548 +    apply (rule cexp_cone)
   1.549 +    apply (rule assms(2))
   1.550 +    apply (rule cexp_mono2)
   1.551 +    apply (rule cone_ordLeq_Cnotzero)
   1.552 +    apply (rule assms(1))
   1.553 +    apply (rule assms(2))
   1.554 +    apply (rule notE)
   1.555 +    apply (rule cone_not_czero)
   1.556 +    apply assumption
   1.557 +    apply (rule Card_order_cone)
   1.558 +  done
   1.559 +qed
   1.560 +
   1.561 +lemma ordLeq_cexp2:
   1.562 +  assumes "ctwo \<le>o q" "Card_order r"
   1.563 +  shows "r \<le>o q ^c r"
   1.564 +proof (cases "r =o (czero :: 'a rel)")
   1.565 +  case True thus ?thesis by (simp only: card_of_empty cexp_def czero_def ordIso_ordLeq_trans)
   1.566 +next
   1.567 +  case False thus ?thesis
   1.568 +    apply -
   1.569 +    apply (rule ordLess_imp_ordLeq)
   1.570 +    apply (rule ordLess_ordLeq_trans)
   1.571 +    apply (rule ordLess_ctwo_cexp)
   1.572 +    apply (rule assms(2))
   1.573 +    apply (rule cexp_mono1)
   1.574 +    apply (rule assms(1))
   1.575 +    apply (rule assms(2))
   1.576 +  done
   1.577 +qed
   1.578 +
   1.579 +lemma cinfinite_cexp: "\<lbrakk>ctwo \<le>o q; Cinfinite r\<rbrakk> \<Longrightarrow> cinfinite (q ^c r)"
   1.580 +by (metis assms cinfinite_mono ordLeq_cexp2)
   1.581 +
   1.582 +lemma Cinfinite_cexp:
   1.583 +  "\<lbrakk>ctwo \<le>o q; Cinfinite r\<rbrakk> \<Longrightarrow> Cinfinite (q ^c r)"
   1.584 +by (simp add: cinfinite_cexp Card_order_cexp)
   1.585 +
   1.586 +lemma ctwo_ordLess_natLeq: "ctwo <o natLeq"
   1.587 +unfolding ctwo_def using finite_UNIV natLeq_cinfinite natLeq_Card_order
   1.588 +by (intro Cfinite_ordLess_Cinfinite) (auto simp: cfinite_def card_of_Card_order)
   1.589 +
   1.590 +lemma ctwo_ordLess_Cinfinite: "Cinfinite r \<Longrightarrow> ctwo <o r"
   1.591 +by (metis ctwo_ordLess_natLeq natLeq_ordLeq_cinfinite ordLess_ordLeq_trans)
   1.592 +
   1.593 +lemma ctwo_ordLeq_Cinfinite:
   1.594 +  assumes "Cinfinite r"
   1.595 +  shows "ctwo \<le>o r"
   1.596 +by (rule ordLess_imp_ordLeq[OF ctwo_ordLess_Cinfinite[OF assms]])
   1.597 +
   1.598 +lemma Un_Cinfinite_bound: "\<lbrakk>|A| \<le>o r; |B| \<le>o r; Cinfinite r\<rbrakk> \<Longrightarrow> |A \<union> B| \<le>o r"
   1.599 +by (auto simp add: cinfinite_def card_of_Un_ordLeq_infinite_Field)
   1.600 +
   1.601 +lemma UNION_Cinfinite_bound: "\<lbrakk>|I| \<le>o r; \<forall>i \<in> I. |A i| \<le>o r; Cinfinite r\<rbrakk> \<Longrightarrow> |\<Union>i \<in> I. A i| \<le>o r"
   1.602 +by (auto simp add: card_of_UNION_ordLeq_infinite_Field cinfinite_def)
   1.603 +
   1.604 +lemma csum_cinfinite_bound:
   1.605 +  assumes "p \<le>o r" "q \<le>o r" "Card_order p" "Card_order q" "Cinfinite r"
   1.606 +  shows "p +c q \<le>o r"
   1.607 +proof -
   1.608 +  from assms(1-4) have "|Field p| \<le>o r" "|Field q| \<le>o r"
   1.609 +    unfolding card_order_on_def using card_of_least ordLeq_transitive by blast+
   1.610 +  with assms show ?thesis unfolding cinfinite_def csum_def
   1.611 +    by (blast intro: card_of_Plus_ordLeq_infinite_Field)
   1.612 +qed
   1.613 +
   1.614 +lemma cprod_cinfinite_bound:
   1.615 +  assumes "p \<le>o r" "q \<le>o r" "Card_order p" "Card_order q" "Cinfinite r"
   1.616 +  shows "p *c q \<le>o r"
   1.617 +proof -
   1.618 +  from assms(1-4) have "|Field p| \<le>o r" "|Field q| \<le>o r"
   1.619 +    unfolding card_order_on_def using card_of_least ordLeq_transitive by blast+
   1.620 +  with assms show ?thesis unfolding cinfinite_def cprod_def
   1.621 +    by (blast intro: card_of_Times_ordLeq_infinite_Field)
   1.622 +qed
   1.623 +
   1.624 +lemma cprod_csum_cexp:
   1.625 +  "r1 *c r2 \<le>o (r1 +c r2) ^c ctwo"
   1.626 +unfolding cprod_def csum_def cexp_def ctwo_def Field_card_of
   1.627 +proof -
   1.628 +  let ?f = "\<lambda>(a, b). %x. if x then Inl a else Inr b"
   1.629 +  have "inj_on ?f (Field r1 \<times> Field r2)" (is "inj_on _ ?LHS")
   1.630 +    by (auto simp: inj_on_def fun_eq_iff split: bool.split)
   1.631 +  moreover
   1.632 +  have "?f ` ?LHS \<subseteq> Func (UNIV :: bool set) (Field r1 <+> Field r2)" (is "_ \<subseteq> ?RHS")
   1.633 +    by (auto simp: Func_def)
   1.634 +  ultimately show "|?LHS| \<le>o |?RHS|" using card_of_ordLeq by blast
   1.635 +qed
   1.636 +
   1.637 +lemma Cfinite_cprod_Cinfinite: "\<lbrakk>Cfinite r; Cinfinite s\<rbrakk> \<Longrightarrow> r *c s \<le>o s"
   1.638 +by (intro cprod_cinfinite_bound)
   1.639 +  (auto intro: ordLeq_refl ordLess_imp_ordLeq[OF Cfinite_ordLess_Cinfinite])
   1.640 +
   1.641 +lemma cprod_cexp: "(r *c s) ^c t =o r ^c t *c s ^c t"
   1.642 +  unfolding cprod_def cexp_def Field_card_of by (rule Func_Times_Range)
   1.643 +
   1.644 +lemma cprod_cexp_csum_cexp_Cinfinite:
   1.645 +  assumes t: "Cinfinite t"
   1.646 +  shows "(r *c s) ^c t \<le>o (r +c s) ^c t"
   1.647 +proof -
   1.648 +  have "(r *c s) ^c t \<le>o ((r +c s) ^c ctwo) ^c t"
   1.649 +    by (rule cexp_mono1[OF cprod_csum_cexp conjunct2[OF t]])
   1.650 +  also have "((r +c s) ^c ctwo) ^c t =o (r +c s) ^c (ctwo *c t)"
   1.651 +    by (rule cexp_cprod[OF Card_order_csum])
   1.652 +  also have "(r +c s) ^c (ctwo *c t) =o (r +c s) ^c (t *c ctwo)"
   1.653 +    by (rule cexp_cong2[OF cprod_com Card_order_csum Card_order_cprod])
   1.654 +  also have "(r +c s) ^c (t *c ctwo) =o ((r +c s) ^c t) ^c ctwo"
   1.655 +    by (rule ordIso_symmetric[OF cexp_cprod[OF Card_order_csum]])
   1.656 +  also have "((r +c s) ^c t) ^c ctwo =o (r +c s) ^c t"
   1.657 +    by (rule cexp_cprod_ordLeq[OF Card_order_csum t ctwo_Cnotzero ctwo_ordLeq_Cinfinite[OF t]])
   1.658 +  finally show ?thesis .
   1.659 +qed
   1.660 +
   1.661 +lemma Cfinite_cexp_Cinfinite:
   1.662 +  assumes s: "Cfinite s" and t: "Cinfinite t"
   1.663 +  shows "s ^c t \<le>o ctwo ^c t"
   1.664 +proof (cases "s \<le>o ctwo")
   1.665 +  case True thus ?thesis using t by (blast intro: cexp_mono1)
   1.666 +next
   1.667 +  case False
   1.668 +  hence "ctwo \<le>o s" by (metis card_order_on_well_order_on ctwo_Cnotzero ordLeq_total s)
   1.669 +  hence "Cnotzero s" by (metis Cnotzero_mono ctwo_Cnotzero s)
   1.670 +  hence st: "Cnotzero (s *c t)" by (metis Cinfinite_cprod2 cinfinite_not_czero t)
   1.671 +  have "s ^c t \<le>o (ctwo ^c s) ^c t"
   1.672 +    using assms by (blast intro: cexp_mono1 ordLess_imp_ordLeq[OF ordLess_ctwo_cexp])
   1.673 +  also have "(ctwo ^c s) ^c t =o ctwo ^c (s *c t)"
   1.674 +    by (blast intro: Card_order_ctwo cexp_cprod)
   1.675 +  also have "ctwo ^c (s *c t) \<le>o ctwo ^c t"
   1.676 +    using assms st by (intro cexp_mono2_Cnotzero Cfinite_cprod_Cinfinite Card_order_ctwo)
   1.677 +  finally show ?thesis .
   1.678 +qed
   1.679 +
   1.680 +lemma csum_Cfinite_cexp_Cinfinite:
   1.681 +  assumes r: "Card_order r" and s: "Cfinite s" and t: "Cinfinite t"
   1.682 +  shows "(r +c s) ^c t \<le>o (r +c ctwo) ^c t"
   1.683 +proof (cases "Cinfinite r")
   1.684 +  case True
   1.685 +  hence "r +c s =o r" by (intro csum_absorb1 ordLess_imp_ordLeq[OF Cfinite_ordLess_Cinfinite] s)
   1.686 +  hence "(r +c s) ^c t =o r ^c t" using t by (blast intro: cexp_cong1)
   1.687 +  also have "r ^c t \<le>o (r +c ctwo) ^c t" using t by (blast intro: cexp_mono1 ordLeq_csum1 r)
   1.688 +  finally show ?thesis .
   1.689 +next
   1.690 +  case False
   1.691 +  with r have "Cfinite r" unfolding cinfinite_def cfinite_def by auto
   1.692 +  hence "Cfinite (r +c s)" by (intro Cfinite_csum s)
   1.693 +  hence "(r +c s) ^c t \<le>o ctwo ^c t" by (intro Cfinite_cexp_Cinfinite t)
   1.694 +  also have "ctwo ^c t \<le>o (r +c ctwo) ^c t" using t
   1.695 +    by (blast intro: cexp_mono1 ordLeq_csum2 Card_order_ctwo)
   1.696 +  finally show ?thesis .
   1.697 +qed
   1.698 +
   1.699 +(* cardSuc *)
   1.700 +
   1.701 +lemma Cinfinite_cardSuc: "Cinfinite r \<Longrightarrow> Cinfinite (cardSuc r)"
   1.702 +by (simp add: cinfinite_def cardSuc_Card_order cardSuc_finite)
   1.703 +
   1.704 +lemma cardSuc_UNION_Cinfinite:
   1.705 +  assumes "Cinfinite r" "relChain (cardSuc r) As" "B \<le> (UN i : Field (cardSuc r). As i)" "|B| <=o r"
   1.706 +  shows "EX i : Field (cardSuc r). B \<le> As i"
   1.707 +using cardSuc_UNION assms unfolding cinfinite_def by blast
   1.708 +
   1.709 +end