54474

1 
(* Title: HOL/Cardinals/Cardinal_Arithmetic_LFP.thy


2 
Author: Dmitriy Traytel, TU Muenchen


3 
Copyright 2012


4 


5 
Cardinal arithmetic.


6 
*)


7 


8 
header {* Cardinal Arithmetic *}


9 


10 
theory Cardinal_Arithmetic_LFP


11 
imports Cardinal_Order_Relation_LFP


12 
begin


13 


14 
(*library candidate*)


15 
lemma dir_image: "\<lbrakk>\<And>x y. (f x = f y) = (x = y); Card_order r\<rbrakk> \<Longrightarrow> r =o dir_image r f"


16 
by (rule dir_image_ordIso) (auto simp add: inj_on_def card_order_on_def)


17 


18 
(*should supersede a weaker lemma from the library*)


19 
lemma dir_image_Field: "Field (dir_image r f) = f ` Field r"


20 
unfolding dir_image_def Field_def Range_def Domain_def by fastforce


21 


22 
lemma card_order_dir_image:


23 
assumes bij: "bij f" and co: "card_order r"


24 
shows "card_order (dir_image r f)"


25 
proof 


26 
from assms have "Field (dir_image r f) = UNIV"


27 
using card_order_on_Card_order[of UNIV r] unfolding bij_def dir_image_Field by auto


28 
moreover from bij have "\<And>x y. (f x = f y) = (x = y)" unfolding bij_def inj_on_def by auto


29 
with co have "Card_order (dir_image r f)"


30 
using card_order_on_Card_order[of UNIV r] Card_order_ordIso2[OF _ dir_image] by blast


31 
ultimately show ?thesis by auto


32 
qed


33 


34 
(*library candidate*)


35 
lemma ordIso_refl: "Card_order r \<Longrightarrow> r =o r"


36 
by (rule card_order_on_ordIso)


37 


38 
(*library candidate*)


39 
lemma ordLeq_refl: "Card_order r \<Longrightarrow> r \<le>o r"


40 
by (rule ordIso_imp_ordLeq, rule card_order_on_ordIso)


41 


42 
(*library candidate*)


43 
lemma card_of_ordIso_subst: "A = B \<Longrightarrow> A =o B"


44 
by (simp only: ordIso_refl card_of_Card_order)


45 


46 
(*library candidate*)


47 
lemma Field_card_order: "card_order r \<Longrightarrow> Field r = UNIV"


48 
using card_order_on_Card_order[of UNIV r] by simp


49 


50 
(*library candidate*)


51 
lemma card_of_Times_Plus_distrib:


52 
"A <*> (B <+> C) =o A <*> B <+> A <*> C" (is "?RHS =o ?LHS")


53 
proof 


54 
let ?f = "\<lambda>(a, bc). case bc of Inl b \<Rightarrow> Inl (a, b)  Inr c \<Rightarrow> Inr (a, c)"


55 
have "bij_betw ?f ?RHS ?LHS" unfolding bij_betw_def inj_on_def by force


56 
thus ?thesis using card_of_ordIso by blast


57 
qed


58 


59 
(*library candidate*)


60 
lemma Func_Times_Range:


61 
"Func A (B <*> C) =o Func A B <*> Func A C" (is "?LHS =o ?RHS")


62 
proof 


63 
let ?F = "\<lambda>fg. (\<lambda>x. if x \<in> A then fst (fg x) else undefined,


64 
\<lambda>x. if x \<in> A then snd (fg x) else undefined)"


65 
let ?G = "\<lambda>(f, g) x. if x \<in> A then (f x, g x) else undefined"


66 
have "bij_betw ?F ?LHS ?RHS" unfolding bij_betw_def inj_on_def


67 
proof safe


68 
fix f g assume "f \<in> Func A B" "g \<in> Func A C"


69 
thus "(f, g) \<in> ?F ` Func A (B \<times> C)"


70 
by (intro image_eqI[of _ _ "?G (f, g)"]) (auto simp: Func_def)


71 
qed (auto simp: Func_def fun_eq_iff, metis pair_collapse)


72 
thus ?thesis using card_of_ordIso by blast


73 
qed


74 


75 


76 
subsection {* Zero *}


77 


78 
definition czero where


79 
"czero = card_of {}"


80 


81 
lemma czero_ordIso:


82 
"czero =o czero"


83 
using card_of_empty_ordIso by (simp add: czero_def)


84 


85 
lemma card_of_ordIso_czero_iff_empty:


86 
"A =o (czero :: 'b rel) \<longleftrightarrow> A = ({} :: 'a set)"


87 
unfolding czero_def by (rule iffI[OF card_of_empty2]) (auto simp: card_of_refl card_of_empty_ordIso)


88 


89 
(* A "not czero" Cardinal predicate *)


90 
abbreviation Cnotzero where


91 
"Cnotzero (r :: 'a rel) \<equiv> \<not>(r =o (czero :: 'a rel)) \<and> Card_order r"


92 


93 
(*helper*)


94 
lemma Cnotzero_imp_not_empty: "Cnotzero r \<Longrightarrow> Field r \<noteq> {}"


95 
by (metis Card_order_iff_ordIso_card_of czero_def)


96 


97 
lemma czeroI:


98 
"\<lbrakk>Card_order r; Field r = {}\<rbrakk> \<Longrightarrow> r =o czero"


99 
using Cnotzero_imp_not_empty ordIso_transitive[OF _ czero_ordIso] by blast


100 


101 
lemma czeroE:


102 
"r =o czero \<Longrightarrow> Field r = {}"


103 
unfolding czero_def


104 
by (drule card_of_cong) (simp only: Field_card_of card_of_empty2)


105 


106 
lemma Cnotzero_mono:


107 
"\<lbrakk>Cnotzero r; Card_order q; r \<le>o q\<rbrakk> \<Longrightarrow> Cnotzero q"


108 
apply (rule ccontr)


109 
apply auto


110 
apply (drule czeroE)


111 
apply (erule notE)


112 
apply (erule czeroI)


113 
apply (drule card_of_mono2)


114 
apply (simp only: card_of_empty3)


115 
done


116 


117 
subsection {* (In)finite cardinals *}


118 


119 
definition cinfinite where


120 
"cinfinite r = infinite (Field r)"


121 


122 
abbreviation Cinfinite where


123 
"Cinfinite r \<equiv> cinfinite r \<and> Card_order r"


124 


125 
definition cfinite where


126 
"cfinite r = finite (Field r)"


127 


128 
abbreviation Cfinite where


129 
"Cfinite r \<equiv> cfinite r \<and> Card_order r"


130 


131 
lemma Cfinite_ordLess_Cinfinite: "\<lbrakk>Cfinite r; Cinfinite s\<rbrakk> \<Longrightarrow> r <o s"


132 
unfolding cfinite_def cinfinite_def


133 
by (metis card_order_on_well_order_on finite_ordLess_infinite)


134 


135 
lemma natLeq_ordLeq_cinfinite:


136 
assumes inf: "Cinfinite r"


137 
shows "natLeq \<le>o r"


138 
proof 


139 
from inf have "natLeq \<le>o Field r" by (simp add: cinfinite_def infinite_iff_natLeq_ordLeq)


140 
also from inf have "Field r =o r" by (simp add: card_of_unique ordIso_symmetric)


141 
finally show ?thesis .


142 
qed


143 


144 
lemma cinfinite_not_czero: "cinfinite r \<Longrightarrow> \<not> (r =o (czero :: 'a rel))"


145 
unfolding cinfinite_def by (metis czeroE finite.emptyI)


146 


147 
lemma Cinfinite_Cnotzero: "Cinfinite r \<Longrightarrow> Cnotzero r"


148 
by (metis cinfinite_not_czero)


149 


150 
lemma Cinfinite_cong: "\<lbrakk>r1 =o r2; Cinfinite r1\<rbrakk> \<Longrightarrow> Cinfinite r2"


151 
by (metis Card_order_ordIso2 card_of_mono2 card_of_ordLeq_infinite cinfinite_def ordIso_iff_ordLeq)


152 


153 
lemma cinfinite_mono: "\<lbrakk>r1 \<le>o r2; cinfinite r1\<rbrakk> \<Longrightarrow> cinfinite r2"


154 
by (metis card_of_mono2 card_of_ordLeq_infinite cinfinite_def)


155 


156 


157 
subsection {* Binary sum *}


158 


159 
definition csum (infixr "+c" 65) where


160 
"r1 +c r2 \<equiv> Field r1 <+> Field r2"


161 


162 
lemma Field_csum: "Field (r +c s) = Inl ` Field r \<union> Inr ` Field s"


163 
unfolding csum_def Field_card_of by auto


164 


165 
lemma Card_order_csum:


166 
"Card_order (r1 +c r2)"


167 
unfolding csum_def by (simp add: card_of_Card_order)


168 


169 
lemma csum_Cnotzero1:


170 
"Cnotzero r1 \<Longrightarrow> Cnotzero (r1 +c r2)"


171 
unfolding csum_def


172 
by (metis Cnotzero_imp_not_empty Field_card_of Plus_eq_empty_conv card_of_card_order_on czeroE)


173 


174 
lemma card_order_csum:


175 
assumes "card_order r1" "card_order r2"


176 
shows "card_order (r1 +c r2)"


177 
proof 


178 
have "Field r1 = UNIV" "Field r2 = UNIV" using assms card_order_on_Card_order by auto


179 
thus ?thesis unfolding csum_def by (auto simp: card_of_card_order_on)


180 
qed


181 


182 
lemma cinfinite_csum:


183 
"cinfinite r1 \<or> cinfinite r2 \<Longrightarrow> cinfinite (r1 +c r2)"


184 
unfolding cinfinite_def csum_def by (auto simp: Field_card_of)


185 


186 
lemma Cinfinite_csum1:


187 
"Cinfinite r1 \<Longrightarrow> Cinfinite (r1 +c r2)"


188 
unfolding cinfinite_def csum_def by (metis Field_card_of card_of_Card_order finite_Plus_iff)


189 


190 
lemma csum_cong: "\<lbrakk>p1 =o r1; p2 =o r2\<rbrakk> \<Longrightarrow> p1 +c p2 =o r1 +c r2"


191 
by (simp only: csum_def ordIso_Plus_cong)


192 


193 
lemma csum_cong1: "p1 =o r1 \<Longrightarrow> p1 +c q =o r1 +c q"


194 
by (simp only: csum_def ordIso_Plus_cong1)


195 


196 
lemma csum_cong2: "p2 =o r2 \<Longrightarrow> q +c p2 =o q +c r2"


197 
by (simp only: csum_def ordIso_Plus_cong2)


198 


199 
lemma csum_mono: "\<lbrakk>p1 \<le>o r1; p2 \<le>o r2\<rbrakk> \<Longrightarrow> p1 +c p2 \<le>o r1 +c r2"


200 
by (simp only: csum_def ordLeq_Plus_mono)


201 


202 
lemma csum_mono1: "p1 \<le>o r1 \<Longrightarrow> p1 +c q \<le>o r1 +c q"


203 
by (simp only: csum_def ordLeq_Plus_mono1)


204 


205 
lemma csum_mono2: "p2 \<le>o r2 \<Longrightarrow> q +c p2 \<le>o q +c r2"


206 
by (simp only: csum_def ordLeq_Plus_mono2)


207 


208 
lemma ordLeq_csum1: "Card_order p1 \<Longrightarrow> p1 \<le>o p1 +c p2"


209 
by (simp only: csum_def Card_order_Plus1)


210 


211 
lemma ordLeq_csum2: "Card_order p2 \<Longrightarrow> p2 \<le>o p1 +c p2"


212 
by (simp only: csum_def Card_order_Plus2)


213 


214 
lemma csum_com: "p1 +c p2 =o p2 +c p1"


215 
by (simp only: csum_def card_of_Plus_commute)


216 


217 
lemma csum_assoc: "(p1 +c p2) +c p3 =o p1 +c p2 +c p3"


218 
by (simp only: csum_def Field_card_of card_of_Plus_assoc)


219 


220 
lemma Cfinite_csum: "\<lbrakk>Cfinite r; Cfinite s\<rbrakk> \<Longrightarrow> Cfinite (r +c s)"


221 
unfolding cfinite_def csum_def Field_card_of using card_of_card_order_on by simp


222 


223 
lemma csum_csum: "(r1 +c r2) +c (r3 +c r4) =o (r1 +c r3) +c (r2 +c r4)"


224 
proof 


225 
have "(r1 +c r2) +c (r3 +c r4) =o r1 +c r2 +c (r3 +c r4)"


226 
by (metis csum_assoc)


227 
also have "r1 +c r2 +c (r3 +c r4) =o r1 +c (r2 +c r3) +c r4"


228 
by (metis csum_assoc csum_cong2 ordIso_symmetric)


229 
also have "r1 +c (r2 +c r3) +c r4 =o r1 +c (r3 +c r2) +c r4"


230 
by (metis csum_com csum_cong1 csum_cong2)


231 
also have "r1 +c (r3 +c r2) +c r4 =o r1 +c r3 +c r2 +c r4"


232 
by (metis csum_assoc csum_cong2 ordIso_symmetric)


233 
also have "r1 +c r3 +c r2 +c r4 =o (r1 +c r3) +c (r2 +c r4)"


234 
by (metis csum_assoc ordIso_symmetric)


235 
finally show ?thesis .


236 
qed


237 


238 
lemma Plus_csum: "A <+> B =o A +c B"


239 
by (simp only: csum_def Field_card_of card_of_refl)


240 


241 
lemma Un_csum: "A \<union> B \<le>o A +c B"


242 
using ordLeq_ordIso_trans[OF card_of_Un_Plus_ordLeq Plus_csum] by blast


243 


244 


245 
subsection {* One *}


246 


247 
definition cone where


248 
"cone = card_of {()}"


249 


250 
lemma Card_order_cone: "Card_order cone"


251 
unfolding cone_def by (rule card_of_Card_order)


252 


253 
lemma Cfinite_cone: "Cfinite cone"


254 
unfolding cfinite_def by (simp add: Card_order_cone)


255 


256 
lemma cone_not_czero: "\<not> (cone =o czero)"


257 
unfolding czero_def cone_def by (metis empty_not_insert card_of_empty3[of "{()}"] ordIso_iff_ordLeq)


258 


259 
lemma cone_ordLeq_Cnotzero: "Cnotzero r \<Longrightarrow> cone \<le>o r"


260 
unfolding cone_def by (metis Card_order_singl_ordLeq czeroI)


261 


262 


263 
subsection{* Two *}


264 


265 
definition ctwo where


266 
"ctwo = UNIV :: bool set"


267 


268 
lemma Card_order_ctwo: "Card_order ctwo"


269 
unfolding ctwo_def by (rule card_of_Card_order)


270 


271 
lemma ctwo_not_czero: "\<not> (ctwo =o czero)"


272 
using card_of_empty3[of "UNIV :: bool set"] ordIso_iff_ordLeq


273 
unfolding czero_def ctwo_def by (metis UNIV_not_empty)


274 


275 
lemma ctwo_Cnotzero: "Cnotzero ctwo"


276 
by (simp add: ctwo_not_czero Card_order_ctwo)


277 


278 


279 
subsection {* Family sum *}


280 


281 
definition Csum where


282 
"Csum r rs \<equiv> SIGMA i : Field r. Field (rs i)"


283 


284 
(* Similar setup to the one for SIGMA from theory Big_Operators: *)


285 
syntax "_Csum" ::


286 
"pttrn => ('a * 'a) set => 'b * 'b set => (('a * 'b) * ('a * 'b)) set"


287 
("(3CSUM _:_. _)" [0, 51, 10] 10)


288 


289 
translations


290 
"CSUM i:r. rs" == "CONST Csum r (%i. rs)"


291 


292 
lemma SIGMA_CSUM: "SIGMA i : I. As i = (CSUM i : I. As i )"


293 
by (auto simp: Csum_def Field_card_of)


294 


295 
(* NB: Always, under the cardinal operator,


296 
operations on sets are reduced automatically to operations on cardinals.


297 
This should make cardinal reasoning more direct and natural. *)


298 


299 


300 
subsection {* Product *}


301 


302 
definition cprod (infixr "*c" 80) where


303 
"r1 *c r2 = Field r1 <*> Field r2"


304 


305 
lemma card_order_cprod:


306 
assumes "card_order r1" "card_order r2"


307 
shows "card_order (r1 *c r2)"


308 
proof 


309 
have "Field r1 = UNIV" "Field r2 = UNIV" using assms card_order_on_Card_order by auto


310 
thus ?thesis by (auto simp: cprod_def card_of_card_order_on)


311 
qed


312 


313 
lemma Card_order_cprod: "Card_order (r1 *c r2)"


314 
by (simp only: cprod_def Field_card_of card_of_card_order_on)


315 


316 
lemma cprod_mono1: "p1 \<le>o r1 \<Longrightarrow> p1 *c q \<le>o r1 *c q"


317 
by (simp only: cprod_def ordLeq_Times_mono1)


318 


319 
lemma cprod_mono2: "p2 \<le>o r2 \<Longrightarrow> q *c p2 \<le>o q *c r2"


320 
by (simp only: cprod_def ordLeq_Times_mono2)


321 


322 
lemma ordLeq_cprod2: "\<lbrakk>Cnotzero p1; Card_order p2\<rbrakk> \<Longrightarrow> p2 \<le>o p1 *c p2"


323 
unfolding cprod_def by (metis Card_order_Times2 czeroI)


324 


325 
lemma cinfinite_cprod: "\<lbrakk>cinfinite r1; cinfinite r2\<rbrakk> \<Longrightarrow> cinfinite (r1 *c r2)"


326 
by (simp add: cinfinite_def cprod_def Field_card_of infinite_cartesian_product)


327 


328 
lemma cinfinite_cprod2: "\<lbrakk>Cnotzero r1; Cinfinite r2\<rbrakk> \<Longrightarrow> cinfinite (r1 *c r2)"


329 
by (metis cinfinite_mono ordLeq_cprod2)


330 


331 
lemma Cinfinite_cprod2: "\<lbrakk>Cnotzero r1; Cinfinite r2\<rbrakk> \<Longrightarrow> Cinfinite (r1 *c r2)"


332 
by (blast intro: cinfinite_cprod2 Card_order_cprod)


333 


334 
lemma cprod_com: "p1 *c p2 =o p2 *c p1"


335 
by (simp only: cprod_def card_of_Times_commute)


336 


337 
lemma card_of_Csum_Times:


338 
"\<forall>i \<in> I. A i \<le>o B \<Longrightarrow> (CSUM i : I. A i ) \<le>o I *c B"


339 
by (simp only: Csum_def cprod_def Field_card_of card_of_Sigma_Times)


340 


341 
lemma card_of_Csum_Times':


342 
assumes "Card_order r" "\<forall>i \<in> I. A i \<le>o r"


343 
shows "(CSUM i : I. A i ) \<le>o I *c r"


344 
proof 


345 
from assms(1) have *: "r =o Field r" by (simp add: card_of_unique)


346 
with assms(2) have "\<forall>i \<in> I. A i \<le>o Field r" by (blast intro: ordLeq_ordIso_trans)


347 
hence "(CSUM i : I. A i ) \<le>o I *c Field r" by (simp only: card_of_Csum_Times)


348 
also from * have "I *c Field r \<le>o I *c r"


349 
by (simp only: Field_card_of card_of_refl cprod_def ordIso_imp_ordLeq)


350 
finally show ?thesis .


351 
qed


352 


353 
lemma cprod_csum_distrib1: "r1 *c r2 +c r1 *c r3 =o r1 *c (r2 +c r3)"


354 
unfolding csum_def cprod_def by (simp add: Field_card_of card_of_Times_Plus_distrib ordIso_symmetric)


355 


356 
lemma csum_absorb2': "\<lbrakk>Card_order r2; r1 \<le>o r2; cinfinite r1 \<or> cinfinite r2\<rbrakk> \<Longrightarrow> r1 +c r2 =o r2"


357 
unfolding csum_def by (metis Card_order_Plus_infinite cinfinite_def cinfinite_mono)


358 


359 
lemma csum_absorb1':


360 
assumes card: "Card_order r2"


361 
and r12: "r1 \<le>o r2" and cr12: "cinfinite r1 \<or> cinfinite r2"


362 
shows "r2 +c r1 =o r2"


363 
by (rule ordIso_transitive, rule csum_com, rule csum_absorb2', (simp only: assms)+)


364 


365 
lemma csum_absorb1: "\<lbrakk>Cinfinite r2; r1 \<le>o r2\<rbrakk> \<Longrightarrow> r2 +c r1 =o r2"


366 
by (rule csum_absorb1') auto


367 


368 


369 
subsection {* Exponentiation *}


370 


371 
definition cexp (infixr "^c" 90) where


372 
"r1 ^c r2 \<equiv> Func (Field r2) (Field r1)"


373 


374 
lemma Card_order_cexp: "Card_order (r1 ^c r2)"


375 
unfolding cexp_def by (rule card_of_Card_order)


376 


377 
lemma cexp_mono':


378 
assumes 1: "p1 \<le>o r1" and 2: "p2 \<le>o r2"


379 
and n: "Field p2 = {} \<Longrightarrow> Field r2 = {}"


380 
shows "p1 ^c p2 \<le>o r1 ^c r2"


381 
proof(cases "Field p1 = {}")


382 
case True


383 
hence "Field Func (Field p2) (Field p1) \<le>o cone"


384 
unfolding cone_def Field_card_of


385 
by (cases "Field p2 = {}", auto intro: card_of_ordLeqI2 simp: Func_empty)


386 
(metis Func_is_emp card_of_empty ex_in_conv)


387 
hence "Func (Field p2) (Field p1) \<le>o cone" by (simp add: Field_card_of cexp_def)


388 
hence "p1 ^c p2 \<le>o cone" unfolding cexp_def .


389 
thus ?thesis


390 
proof (cases "Field p2 = {}")


391 
case True


392 
with n have "Field r2 = {}" .


393 
hence "cone \<le>o r1 ^c r2" unfolding cone_def cexp_def Func_def by (auto intro: card_of_ordLeqI)


394 
thus ?thesis using `p1 ^c p2 \<le>o cone` ordLeq_transitive by auto


395 
next


396 
case False with True have "Field (p1 ^c p2) =o czero"


397 
unfolding card_of_ordIso_czero_iff_empty cexp_def Field_card_of Func_def by auto


398 
thus ?thesis unfolding cexp_def card_of_ordIso_czero_iff_empty Field_card_of


399 
by (simp add: card_of_empty)


400 
qed


401 
next


402 
case False


403 
have 1: "Field p1 \<le>o Field r1" and 2: "Field p2 \<le>o Field r2"


404 
using 1 2 by (auto simp: card_of_mono2)


405 
obtain f1 where f1: "f1 ` Field r1 = Field p1"


406 
using 1 unfolding card_of_ordLeq2[OF False, symmetric] by auto


407 
obtain f2 where f2: "inj_on f2 (Field p2)" "f2 ` Field p2 \<subseteq> Field r2"


408 
using 2 unfolding card_of_ordLeq[symmetric] by blast


409 
have 0: "Func_map (Field p2) f1 f2 ` (Field (r1 ^c r2)) = Field (p1 ^c p2)"


410 
unfolding cexp_def Field_card_of using Func_map_surj[OF f1 f2 n, symmetric] .


411 
have 00: "Field (p1 ^c p2) \<noteq> {}" unfolding cexp_def Field_card_of Func_is_emp


412 
using False by simp


413 
show ?thesis


414 
using 0 card_of_ordLeq2[OF 00] unfolding cexp_def Field_card_of by blast


415 
qed


416 


417 
lemma cexp_mono:


418 
assumes 1: "p1 \<le>o r1" and 2: "p2 \<le>o r2"


419 
and n: "p2 =o czero \<Longrightarrow> r2 =o czero" and card: "Card_order p2"


420 
shows "p1 ^c p2 \<le>o r1 ^c r2"


421 
by (metis (full_types) "1" "2" card cexp_mono' czeroE czeroI n)


422 


423 
lemma cexp_mono1:


424 
assumes 1: "p1 \<le>o r1" and q: "Card_order q"


425 
shows "p1 ^c q \<le>o r1 ^c q"


426 
using ordLeq_refl[OF q] by (rule cexp_mono[OF 1]) (auto simp: q)


427 


428 
lemma cexp_mono2':


429 
assumes 2: "p2 \<le>o r2" and q: "Card_order q"


430 
and n: "Field p2 = {} \<Longrightarrow> Field r2 = {}"


431 
shows "q ^c p2 \<le>o q ^c r2"


432 
using ordLeq_refl[OF q] by (rule cexp_mono'[OF _ 2 n]) auto


433 


434 
lemma cexp_mono2:


435 
assumes 2: "p2 \<le>o r2" and q: "Card_order q"


436 
and n: "p2 =o czero \<Longrightarrow> r2 =o czero" and card: "Card_order p2"


437 
shows "q ^c p2 \<le>o q ^c r2"


438 
using ordLeq_refl[OF q] by (rule cexp_mono[OF _ 2 n card]) auto


439 


440 
lemma cexp_mono2_Cnotzero:


441 
assumes "p2 \<le>o r2" "Card_order q" "Cnotzero p2"


442 
shows "q ^c p2 \<le>o q ^c r2"


443 
by (metis assms cexp_mono2' czeroI)


444 


445 
lemma cexp_cong:


446 
assumes 1: "p1 =o r1" and 2: "p2 =o r2"


447 
and Cr: "Card_order r2"


448 
and Cp: "Card_order p2"


449 
shows "p1 ^c p2 =o r1 ^c r2"


450 
proof 


451 
obtain f where "bij_betw f (Field p2) (Field r2)"


452 
using 2 card_of_ordIso[of "Field p2" "Field r2"] card_of_cong by auto


453 
hence 0: "Field p2 = {} \<longleftrightarrow> Field r2 = {}" unfolding bij_betw_def by auto


454 
have r: "p2 =o czero \<Longrightarrow> r2 =o czero"


455 
and p: "r2 =o czero \<Longrightarrow> p2 =o czero"


456 
using 0 Cr Cp czeroE czeroI by auto


457 
show ?thesis using 0 1 2 unfolding ordIso_iff_ordLeq


458 
using r p cexp_mono[OF _ _ _ Cp] cexp_mono[OF _ _ _ Cr] by blast


459 
qed


460 


461 
lemma cexp_cong1:


462 
assumes 1: "p1 =o r1" and q: "Card_order q"


463 
shows "p1 ^c q =o r1 ^c q"


464 
by (rule cexp_cong[OF 1 _ q q]) (rule ordIso_refl[OF q])


465 


466 
lemma cexp_cong2:


467 
assumes 2: "p2 =o r2" and q: "Card_order q" and p: "Card_order p2"


468 
shows "q ^c p2 =o q ^c r2"


469 
by (rule cexp_cong[OF _ 2]) (auto simp only: ordIso_refl Card_order_ordIso2[OF p 2] q p)


470 


471 
lemma cexp_cone:


472 
assumes "Card_order r"


473 
shows "r ^c cone =o r"


474 
proof 


475 
have "r ^c cone =o Field r"


476 
unfolding cexp_def cone_def Field_card_of Func_empty


477 
card_of_ordIso[symmetric] bij_betw_def Func_def inj_on_def image_def


478 
by (rule exI[of _ "\<lambda>f. f ()"]) auto


479 
also have "Field r =o r" by (rule card_of_Field_ordIso[OF assms])


480 
finally show ?thesis .


481 
qed


482 


483 
lemma cexp_cprod:


484 
assumes r1: "Card_order r1"


485 
shows "(r1 ^c r2) ^c r3 =o r1 ^c (r2 *c r3)" (is "?L =o ?R")


486 
proof 


487 
have "?L =o r1 ^c (r3 *c r2)"


488 
unfolding cprod_def cexp_def Field_card_of


489 
using card_of_Func_Times by(rule ordIso_symmetric)


490 
also have "r1 ^c (r3 *c r2) =o ?R"


491 
apply(rule cexp_cong2) using cprod_com r1 by (auto simp: Card_order_cprod)


492 
finally show ?thesis .


493 
qed


494 


495 
lemma cprod_infinite1': "\<lbrakk>Cinfinite r; Cnotzero p; p \<le>o r\<rbrakk> \<Longrightarrow> r *c p =o r"


496 
unfolding cinfinite_def cprod_def


497 
by (rule Card_order_Times_infinite[THEN conjunct1]) (blast intro: czeroI)+


498 


499 
lemma cexp_cprod_ordLeq:


500 
assumes r1: "Card_order r1" and r2: "Cinfinite r2"


501 
and r3: "Cnotzero r3" "r3 \<le>o r2"


502 
shows "(r1 ^c r2) ^c r3 =o r1 ^c r2" (is "?L =o ?R")


503 
proof


504 
have "?L =o r1 ^c (r2 *c r3)" using cexp_cprod[OF r1] .


505 
also have "r1 ^c (r2 *c r3) =o ?R"


506 
apply(rule cexp_cong2)


507 
apply(rule cprod_infinite1'[OF r2 r3]) using r1 r2 by (fastforce simp: Card_order_cprod)+


508 
finally show ?thesis .


509 
qed


510 


511 
lemma Cnotzero_UNIV: "Cnotzero UNIV"


512 
by (auto simp: card_of_Card_order card_of_ordIso_czero_iff_empty)


513 


514 
lemma ordLess_ctwo_cexp:


515 
assumes "Card_order r"


516 
shows "r <o ctwo ^c r"


517 
proof 


518 
have "r <o Pow (Field r)" using assms by (rule Card_order_Pow)


519 
also have "Pow (Field r) =o ctwo ^c r"


520 
unfolding ctwo_def cexp_def Field_card_of by (rule card_of_Pow_Func)


521 
finally show ?thesis .


522 
qed


523 


524 
lemma ordLeq_cexp1:


525 
assumes "Cnotzero r" "Card_order q"


526 
shows "q \<le>o q ^c r"


527 
proof (cases "q =o (czero :: 'a rel)")


528 
case True thus ?thesis by (simp only: card_of_empty cexp_def czero_def ordIso_ordLeq_trans)


529 
next


530 
case False


531 
thus ?thesis


532 
apply 


533 
apply (rule ordIso_ordLeq_trans)


534 
apply (rule ordIso_symmetric)


535 
apply (rule cexp_cone)


536 
apply (rule assms(2))


537 
apply (rule cexp_mono2)


538 
apply (rule cone_ordLeq_Cnotzero)


539 
apply (rule assms(1))


540 
apply (rule assms(2))


541 
apply (rule notE)


542 
apply (rule cone_not_czero)


543 
apply assumption


544 
apply (rule Card_order_cone)


545 
done


546 
qed


547 


548 
lemma ordLeq_cexp2:


549 
assumes "ctwo \<le>o q" "Card_order r"


550 
shows "r \<le>o q ^c r"


551 
proof (cases "r =o (czero :: 'a rel)")


552 
case True thus ?thesis by (simp only: card_of_empty cexp_def czero_def ordIso_ordLeq_trans)


553 
next


554 
case False thus ?thesis


555 
apply 


556 
apply (rule ordLess_imp_ordLeq)


557 
apply (rule ordLess_ordLeq_trans)


558 
apply (rule ordLess_ctwo_cexp)


559 
apply (rule assms(2))


560 
apply (rule cexp_mono1)


561 
apply (rule assms(1))


562 
apply (rule assms(2))


563 
done


564 
qed


565 


566 
lemma cinfinite_cexp: "\<lbrakk>ctwo \<le>o q; Cinfinite r\<rbrakk> \<Longrightarrow> cinfinite (q ^c r)"


567 
by (metis assms cinfinite_mono ordLeq_cexp2)


568 


569 
lemma Cinfinite_cexp:


570 
"\<lbrakk>ctwo \<le>o q; Cinfinite r\<rbrakk> \<Longrightarrow> Cinfinite (q ^c r)"


571 
by (simp add: cinfinite_cexp Card_order_cexp)


572 


573 
lemma ctwo_ordLess_natLeq: "ctwo <o natLeq"


574 
unfolding ctwo_def using finite_iff_ordLess_natLeq finite_UNIV by fast


575 


576 
lemma ctwo_ordLess_Cinfinite: "Cinfinite r \<Longrightarrow> ctwo <o r"


577 
by (metis ctwo_ordLess_natLeq natLeq_ordLeq_cinfinite ordLess_ordLeq_trans)


578 


579 
lemma ctwo_ordLeq_Cinfinite:


580 
assumes "Cinfinite r"


581 
shows "ctwo \<le>o r"


582 
by (rule ordLess_imp_ordLeq[OF ctwo_ordLess_Cinfinite[OF assms]])


583 


584 
lemma Un_Cinfinite_bound: "\<lbrakk>A \<le>o r; B \<le>o r; Cinfinite r\<rbrakk> \<Longrightarrow> A \<union> B \<le>o r"


585 
by (auto simp add: cinfinite_def card_of_Un_ordLeq_infinite_Field)


586 


587 
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"


588 
by (auto simp add: card_of_UNION_ordLeq_infinite_Field cinfinite_def)


589 


590 
lemma csum_cinfinite_bound:


591 
assumes "p \<le>o r" "q \<le>o r" "Card_order p" "Card_order q" "Cinfinite r"


592 
shows "p +c q \<le>o r"


593 
proof 


594 
from assms(14) have "Field p \<le>o r" "Field q \<le>o r"


595 
unfolding card_order_on_def using card_of_least ordLeq_transitive by blast+


596 
with assms show ?thesis unfolding cinfinite_def csum_def


597 
by (blast intro: card_of_Plus_ordLeq_infinite_Field)


598 
qed


599 


600 
lemma cprod_cinfinite_bound:


601 
assumes "p \<le>o r" "q \<le>o r" "Card_order p" "Card_order q" "Cinfinite r"


602 
shows "p *c q \<le>o r"


603 
proof 


604 
from assms(14) have "Field p \<le>o r" "Field q \<le>o r"


605 
unfolding card_order_on_def using card_of_least ordLeq_transitive by blast+


606 
with assms show ?thesis unfolding cinfinite_def cprod_def


607 
by (blast intro: card_of_Times_ordLeq_infinite_Field)


608 
qed


609 


610 
lemma cprod_csum_cexp:


611 
"r1 *c r2 \<le>o (r1 +c r2) ^c ctwo"


612 
unfolding cprod_def csum_def cexp_def ctwo_def Field_card_of


613 
proof 


614 
let ?f = "\<lambda>(a, b). %x. if x then Inl a else Inr b"


615 
have "inj_on ?f (Field r1 \<times> Field r2)" (is "inj_on _ ?LHS")


616 
by (auto simp: inj_on_def fun_eq_iff split: bool.split)


617 
moreover


618 
have "?f ` ?LHS \<subseteq> Func (UNIV :: bool set) (Field r1 <+> Field r2)" (is "_ \<subseteq> ?RHS")


619 
by (auto simp: Func_def)


620 
ultimately show "?LHS \<le>o ?RHS" using card_of_ordLeq by blast


621 
qed


622 


623 
lemma Cfinite_cprod_Cinfinite: "\<lbrakk>Cfinite r; Cinfinite s\<rbrakk> \<Longrightarrow> r *c s \<le>o s"


624 
by (intro cprod_cinfinite_bound)


625 
(auto intro: ordLeq_refl ordLess_imp_ordLeq[OF Cfinite_ordLess_Cinfinite])


626 


627 
lemma cprod_cexp: "(r *c s) ^c t =o r ^c t *c s ^c t"


628 
unfolding cprod_def cexp_def Field_card_of by (rule Func_Times_Range)


629 


630 
lemma cprod_cexp_csum_cexp_Cinfinite:


631 
assumes t: "Cinfinite t"


632 
shows "(r *c s) ^c t \<le>o (r +c s) ^c t"


633 
proof 


634 
have "(r *c s) ^c t \<le>o ((r +c s) ^c ctwo) ^c t"


635 
by (rule cexp_mono1[OF cprod_csum_cexp conjunct2[OF t]])


636 
also have "((r +c s) ^c ctwo) ^c t =o (r +c s) ^c (ctwo *c t)"


637 
by (rule cexp_cprod[OF Card_order_csum])


638 
also have "(r +c s) ^c (ctwo *c t) =o (r +c s) ^c (t *c ctwo)"


639 
by (rule cexp_cong2[OF cprod_com Card_order_csum Card_order_cprod])


640 
also have "(r +c s) ^c (t *c ctwo) =o ((r +c s) ^c t) ^c ctwo"


641 
by (rule ordIso_symmetric[OF cexp_cprod[OF Card_order_csum]])


642 
also have "((r +c s) ^c t) ^c ctwo =o (r +c s) ^c t"


643 
by (rule cexp_cprod_ordLeq[OF Card_order_csum t ctwo_Cnotzero ctwo_ordLeq_Cinfinite[OF t]])


644 
finally show ?thesis .


645 
qed


646 


647 
lemma Cfinite_cexp_Cinfinite:


648 
assumes s: "Cfinite s" and t: "Cinfinite t"


649 
shows "s ^c t \<le>o ctwo ^c t"


650 
proof (cases "s \<le>o ctwo")


651 
case True thus ?thesis using t by (blast intro: cexp_mono1)


652 
next


653 
case False


654 
hence "ctwo \<le>o s" by (metis card_order_on_well_order_on ctwo_Cnotzero ordLeq_total s)


655 
hence "Cnotzero s" by (metis Cnotzero_mono ctwo_Cnotzero s)


656 
hence st: "Cnotzero (s *c t)" by (metis Cinfinite_cprod2 cinfinite_not_czero t)


657 
have "s ^c t \<le>o (ctwo ^c s) ^c t"


658 
using assms by (blast intro: cexp_mono1 ordLess_imp_ordLeq[OF ordLess_ctwo_cexp])


659 
also have "(ctwo ^c s) ^c t =o ctwo ^c (s *c t)"


660 
by (blast intro: Card_order_ctwo cexp_cprod)


661 
also have "ctwo ^c (s *c t) \<le>o ctwo ^c t"


662 
using assms st by (intro cexp_mono2_Cnotzero Cfinite_cprod_Cinfinite Card_order_ctwo)


663 
finally show ?thesis .


664 
qed


665 


666 
lemma csum_Cfinite_cexp_Cinfinite:


667 
assumes r: "Card_order r" and s: "Cfinite s" and t: "Cinfinite t"


668 
shows "(r +c s) ^c t \<le>o (r +c ctwo) ^c t"


669 
proof (cases "Cinfinite r")


670 
case True


671 
hence "r +c s =o r" by (intro csum_absorb1 ordLess_imp_ordLeq[OF Cfinite_ordLess_Cinfinite] s)


672 
hence "(r +c s) ^c t =o r ^c t" using t by (blast intro: cexp_cong1)


673 
also have "r ^c t \<le>o (r +c ctwo) ^c t" using t by (blast intro: cexp_mono1 ordLeq_csum1 r)


674 
finally show ?thesis .


675 
next


676 
case False


677 
with r have "Cfinite r" unfolding cinfinite_def cfinite_def by auto


678 
hence "Cfinite (r +c s)" by (intro Cfinite_csum s)


679 
hence "(r +c s) ^c t \<le>o ctwo ^c t" by (intro Cfinite_cexp_Cinfinite t)


680 
also have "ctwo ^c t \<le>o (r +c ctwo) ^c t" using t


681 
by (blast intro: cexp_mono1 ordLeq_csum2 Card_order_ctwo)


682 
finally show ?thesis .


683 
qed


684 


685 


686 
(* cardSuc *)


687 


688 
lemma Cinfinite_cardSuc: "Cinfinite r \<Longrightarrow> Cinfinite (cardSuc r)"


689 
by (simp add: cinfinite_def cardSuc_Card_order cardSuc_finite)


690 


691 
lemma cardSuc_UNION_Cinfinite:


692 
assumes "Cinfinite r" "relChain (cardSuc r) As" "B \<le> (UN i : Field (cardSuc r). As i)" "B <=o r"


693 
shows "EX i : Field (cardSuc r). B \<le> As i"


694 
using cardSuc_UNION assms unfolding cinfinite_def by blast


695 


696 
subsection {* Powerset *}


697 


698 
definition cpow where "cpow r = Pow (Field r)"


699 


700 
lemma card_order_cpow: "card_order r \<Longrightarrow> card_order (cpow r)"


701 
by (simp only: cpow_def Field_card_order Pow_UNIV card_of_card_order_on)


702 


703 
lemma cpow_greater_eq: "Card_order r \<Longrightarrow> r \<le>o cpow r"


704 
by (rule ordLess_imp_ordLeq) (simp only: cpow_def Card_order_Pow)


705 


706 
subsection {* Lists *}


707 


708 
definition clists where "clists r = lists (Field r)"


709 


710 
end
