src/HOL/BNF_Cardinal_Arithmetic.thy
author wenzelm
Fri Mar 07 22:30:58 2014 +0100 (2014-03-07)
changeset 55990 41c6b99c5fb7
parent 55866 a6fa341a6d66
child 56191 159b0c88b4a4
permissions -rw-r--r--
more antiquotations;
     1 (*  Title:      HOL/BNF_Cardinal_Arithmetic.thy
     2     Author:     Dmitriy Traytel, TU Muenchen
     3     Copyright   2012
     4 
     5 Cardinal arithmetic as needed by bounded natural functors.
     6 *)
     7 
     8 header {* Cardinal Arithmetic as Needed by Bounded Natural Functors *}
     9 
    10 theory BNF_Cardinal_Arithmetic
    11 imports BNF_Cardinal_Order_Relation
    12 begin
    13 
    14 lemma dir_image: "\<lbrakk>\<And>x y. (f x = f y) = (x = y); Card_order r\<rbrakk> \<Longrightarrow> r =o dir_image r f"
    15 by (rule dir_image_ordIso) (auto simp add: inj_on_def card_order_on_def)
    16 
    17 (*should supersede a weaker lemma from the library*)
    18 lemma dir_image_Field: "Field (dir_image r f) = f ` Field r"
    19 unfolding dir_image_def Field_def Range_def Domain_def by fast
    20 
    21 lemma card_order_dir_image:
    22   assumes bij: "bij f" and co: "card_order r"
    23   shows "card_order (dir_image r f)"
    24 proof -
    25   from assms have "Field (dir_image r f) = UNIV"
    26     using card_order_on_Card_order[of UNIV r] unfolding bij_def dir_image_Field by auto
    27   moreover from bij have "\<And>x y. (f x = f y) = (x = y)" unfolding bij_def inj_on_def by auto
    28   with co have "Card_order (dir_image r f)"
    29     using card_order_on_Card_order[of UNIV r] Card_order_ordIso2[OF _ dir_image] by blast
    30   ultimately show ?thesis by auto
    31 qed
    32 
    33 lemma ordIso_refl: "Card_order r \<Longrightarrow> r =o r"
    34 by (rule card_order_on_ordIso)
    35 
    36 lemma ordLeq_refl: "Card_order r \<Longrightarrow> r \<le>o r"
    37 by (rule ordIso_imp_ordLeq, rule card_order_on_ordIso)
    38 
    39 lemma card_of_ordIso_subst: "A = B \<Longrightarrow> |A| =o |B|"
    40 by (simp only: ordIso_refl card_of_Card_order)
    41 
    42 lemma Field_card_order: "card_order r \<Longrightarrow> Field r = UNIV"
    43 using card_order_on_Card_order[of UNIV r] by simp
    44 
    45 lemma card_of_Times_Plus_distrib:
    46   "|A <*> (B <+> C)| =o |A <*> B <+> A <*> C|" (is "|?RHS| =o |?LHS|")
    47 proof -
    48   let ?f = "\<lambda>(a, bc). case bc of Inl b \<Rightarrow> Inl (a, b) | Inr c \<Rightarrow> Inr (a, c)"
    49   have "bij_betw ?f ?RHS ?LHS" unfolding bij_betw_def inj_on_def by force
    50   thus ?thesis using card_of_ordIso by blast
    51 qed
    52 
    53 lemma Func_Times_Range:
    54   "|Func A (B <*> C)| =o |Func A B <*> Func A C|" (is "|?LHS| =o |?RHS|")
    55 proof -
    56   let ?F = "\<lambda>fg. (\<lambda>x. if x \<in> A then fst (fg x) else undefined,
    57                   \<lambda>x. if x \<in> A then snd (fg x) else undefined)"
    58   let ?G = "\<lambda>(f, g) x. if x \<in> A then (f x, g x) else undefined"
    59   have "bij_betw ?F ?LHS ?RHS" unfolding bij_betw_def inj_on_def
    60   proof (intro conjI impI ballI equalityI subsetI)
    61     fix f g assume *: "f \<in> Func A (B \<times> C)" "g \<in> Func A (B \<times> C)" "?F f = ?F g"
    62     show "f = g"
    63     proof
    64       fix x from * have "fst (f x) = fst (g x) \<and> snd (f x) = snd (g x)"
    65         by (case_tac "x \<in> A") (auto simp: Func_def fun_eq_iff split: if_splits)
    66       then show "f x = g x" by (subst (1 2) surjective_pairing) simp
    67     qed
    68   next
    69     fix fg assume "fg \<in> Func A B \<times> Func A C"
    70     thus "fg \<in> ?F ` Func A (B \<times> C)"
    71       by (intro image_eqI[of _ _ "?G fg"]) (auto simp: Func_def)
    72   qed (auto simp: Func_def fun_eq_iff)
    73   thus ?thesis using card_of_ordIso by blast
    74 qed
    75 
    76 
    77 subsection {* Zero *}
    78 
    79 definition czero where
    80   "czero = card_of {}"
    81 
    82 lemma czero_ordIso:
    83   "czero =o czero"
    84 using card_of_empty_ordIso by (simp add: czero_def)
    85 
    86 lemma card_of_ordIso_czero_iff_empty:
    87   "|A| =o (czero :: 'b rel) \<longleftrightarrow> A = ({} :: 'a set)"
    88 unfolding czero_def by (rule iffI[OF card_of_empty2]) (auto simp: card_of_refl card_of_empty_ordIso)
    89 
    90 (* A "not czero" Cardinal predicate *)
    91 abbreviation Cnotzero where
    92   "Cnotzero (r :: 'a rel) \<equiv> \<not>(r =o (czero :: 'a rel)) \<and> Card_order r"
    93 
    94 (*helper*)
    95 lemma Cnotzero_imp_not_empty: "Cnotzero r \<Longrightarrow> Field r \<noteq> {}"
    96   unfolding Card_order_iff_ordIso_card_of czero_def by force
    97 
    98 lemma czeroI:
    99   "\<lbrakk>Card_order r; Field r = {}\<rbrakk> \<Longrightarrow> r =o czero"
   100 using Cnotzero_imp_not_empty ordIso_transitive[OF _ czero_ordIso] by blast
   101 
   102 lemma czeroE:
   103   "r =o czero \<Longrightarrow> Field r = {}"
   104 unfolding czero_def
   105 by (drule card_of_cong) (simp only: Field_card_of card_of_empty2)
   106 
   107 lemma Cnotzero_mono:
   108   "\<lbrakk>Cnotzero r; Card_order q; r \<le>o q\<rbrakk> \<Longrightarrow> Cnotzero q"
   109 apply (rule ccontr)
   110 apply auto
   111 apply (drule czeroE)
   112 apply (erule notE)
   113 apply (erule czeroI)
   114 apply (drule card_of_mono2)
   115 apply (simp only: card_of_empty3)
   116 done
   117 
   118 subsection {* (In)finite cardinals *}
   119 
   120 definition cinfinite where
   121   "cinfinite r = (\<not> finite (Field r))"
   122 
   123 abbreviation Cinfinite where
   124   "Cinfinite r \<equiv> cinfinite r \<and> Card_order r"
   125 
   126 definition cfinite where
   127   "cfinite r = finite (Field r)"
   128 
   129 abbreviation Cfinite where
   130   "Cfinite r \<equiv> cfinite r \<and> Card_order r"
   131 
   132 lemma Cfinite_ordLess_Cinfinite: "\<lbrakk>Cfinite r; Cinfinite s\<rbrakk> \<Longrightarrow> r <o s"
   133   unfolding cfinite_def cinfinite_def
   134   by (blast intro: finite_ordLess_infinite card_order_on_well_order_on)
   135 
   136 lemmas natLeq_card_order = natLeq_Card_order[unfolded Field_natLeq]
   137 
   138 lemma natLeq_cinfinite: "cinfinite natLeq"
   139 unfolding cinfinite_def Field_natLeq by (rule infinite_UNIV_nat)
   140 
   141 lemma natLeq_ordLeq_cinfinite:
   142   assumes inf: "Cinfinite r"
   143   shows "natLeq \<le>o r"
   144 proof -
   145   from inf have "natLeq \<le>o |Field r|" unfolding cinfinite_def
   146     using infinite_iff_natLeq_ordLeq by blast
   147   also from inf have "|Field r| =o r" by (simp add: card_of_unique ordIso_symmetric)
   148   finally show ?thesis .
   149 qed
   150 
   151 lemma cinfinite_not_czero: "cinfinite r \<Longrightarrow> \<not> (r =o (czero :: 'a rel))"
   152 unfolding cinfinite_def by (cases "Field r = {}") (auto dest: czeroE)
   153 
   154 lemma Cinfinite_Cnotzero: "Cinfinite r \<Longrightarrow> Cnotzero r"
   155 by (rule conjI[OF cinfinite_not_czero]) simp_all
   156 
   157 lemma Cinfinite_cong: "\<lbrakk>r1 =o r2; Cinfinite r1\<rbrakk> \<Longrightarrow> Cinfinite r2"
   158 using Card_order_ordIso2[of r1 r2] unfolding cinfinite_def ordIso_iff_ordLeq
   159 by (auto dest: card_of_ordLeq_infinite[OF card_of_mono2])
   160 
   161 lemma cinfinite_mono: "\<lbrakk>r1 \<le>o r2; cinfinite r1\<rbrakk> \<Longrightarrow> cinfinite r2"
   162 unfolding cinfinite_def by (auto dest: card_of_ordLeq_infinite[OF card_of_mono2])
   163 
   164 
   165 subsection {* Binary sum *}
   166 
   167 definition csum (infixr "+c" 65) where
   168   "r1 +c r2 \<equiv> |Field r1 <+> Field r2|"
   169 
   170 lemma Field_csum: "Field (r +c s) = Inl ` Field r \<union> Inr ` Field s"
   171   unfolding csum_def Field_card_of by auto
   172 
   173 lemma Card_order_csum:
   174   "Card_order (r1 +c r2)"
   175 unfolding csum_def by (simp add: card_of_Card_order)
   176 
   177 lemma csum_Cnotzero1:
   178   "Cnotzero r1 \<Longrightarrow> Cnotzero (r1 +c r2)"
   179 unfolding csum_def using Cnotzero_imp_not_empty[of r1] Plus_eq_empty_conv[of "Field r1" "Field r2"]
   180    card_of_ordIso_czero_iff_empty[of "Field r1 <+> Field r2"] by (auto intro: card_of_Card_order)
   181 
   182 lemma card_order_csum:
   183   assumes "card_order r1" "card_order r2"
   184   shows "card_order (r1 +c r2)"
   185 proof -
   186   have "Field r1 = UNIV" "Field r2 = UNIV" using assms card_order_on_Card_order by auto
   187   thus ?thesis unfolding csum_def by (auto simp: card_of_card_order_on)
   188 qed
   189 
   190 lemma cinfinite_csum:
   191   "cinfinite r1 \<or> cinfinite r2 \<Longrightarrow> cinfinite (r1 +c r2)"
   192 unfolding cinfinite_def csum_def by (auto simp: Field_card_of)
   193 
   194 lemma Cinfinite_csum1:
   195   "Cinfinite r1 \<Longrightarrow> Cinfinite (r1 +c r2)"
   196 unfolding cinfinite_def csum_def by (rule conjI[OF _ card_of_Card_order]) (auto simp: Field_card_of)
   197 
   198 lemma Cinfinite_csum:
   199   "Cinfinite r1 \<or> Cinfinite r2 \<Longrightarrow> Cinfinite (r1 +c r2)"
   200 unfolding cinfinite_def csum_def by (rule conjI[OF _ card_of_Card_order]) (auto simp: Field_card_of)
   201 
   202 lemma Cinfinite_csum_weak:
   203   "\<lbrakk>Cinfinite r1; Cinfinite r2\<rbrakk> \<Longrightarrow> Cinfinite (r1 +c r2)"
   204 by (erule Cinfinite_csum1)
   205 
   206 lemma csum_cong: "\<lbrakk>p1 =o r1; p2 =o r2\<rbrakk> \<Longrightarrow> p1 +c p2 =o r1 +c r2"
   207 by (simp only: csum_def ordIso_Plus_cong)
   208 
   209 lemma csum_cong1: "p1 =o r1 \<Longrightarrow> p1 +c q =o r1 +c q"
   210 by (simp only: csum_def ordIso_Plus_cong1)
   211 
   212 lemma csum_cong2: "p2 =o r2 \<Longrightarrow> q +c p2 =o q +c r2"
   213 by (simp only: csum_def ordIso_Plus_cong2)
   214 
   215 lemma csum_mono: "\<lbrakk>p1 \<le>o r1; p2 \<le>o r2\<rbrakk> \<Longrightarrow> p1 +c p2 \<le>o r1 +c r2"
   216 by (simp only: csum_def ordLeq_Plus_mono)
   217 
   218 lemma csum_mono1: "p1 \<le>o r1 \<Longrightarrow> p1 +c q \<le>o r1 +c q"
   219 by (simp only: csum_def ordLeq_Plus_mono1)
   220 
   221 lemma csum_mono2: "p2 \<le>o r2 \<Longrightarrow> q +c p2 \<le>o q +c r2"
   222 by (simp only: csum_def ordLeq_Plus_mono2)
   223 
   224 lemma ordLeq_csum1: "Card_order p1 \<Longrightarrow> p1 \<le>o p1 +c p2"
   225 by (simp only: csum_def Card_order_Plus1)
   226 
   227 lemma ordLeq_csum2: "Card_order p2 \<Longrightarrow> p2 \<le>o p1 +c p2"
   228 by (simp only: csum_def Card_order_Plus2)
   229 
   230 lemma csum_com: "p1 +c p2 =o p2 +c p1"
   231 by (simp only: csum_def card_of_Plus_commute)
   232 
   233 lemma csum_assoc: "(p1 +c p2) +c p3 =o p1 +c p2 +c p3"
   234 by (simp only: csum_def Field_card_of card_of_Plus_assoc)
   235 
   236 lemma Cfinite_csum: "\<lbrakk>Cfinite r; Cfinite s\<rbrakk> \<Longrightarrow> Cfinite (r +c s)"
   237   unfolding cfinite_def csum_def Field_card_of using card_of_card_order_on by simp
   238 
   239 lemma csum_csum: "(r1 +c r2) +c (r3 +c r4) =o (r1 +c r3) +c (r2 +c r4)"
   240 proof -
   241   have "(r1 +c r2) +c (r3 +c r4) =o r1 +c r2 +c (r3 +c r4)"
   242     by (rule csum_assoc)
   243   also have "r1 +c r2 +c (r3 +c r4) =o r1 +c (r2 +c r3) +c r4"
   244     by (intro csum_assoc csum_cong2 ordIso_symmetric)
   245   also have "r1 +c (r2 +c r3) +c r4 =o r1 +c (r3 +c r2) +c r4"
   246     by (intro csum_com csum_cong1 csum_cong2)
   247   also have "r1 +c (r3 +c r2) +c r4 =o r1 +c r3 +c r2 +c r4"
   248     by (intro csum_assoc csum_cong2 ordIso_symmetric)
   249   also have "r1 +c r3 +c r2 +c r4 =o (r1 +c r3) +c (r2 +c r4)"
   250     by (intro csum_assoc ordIso_symmetric)
   251   finally show ?thesis .
   252 qed
   253 
   254 lemma Plus_csum: "|A <+> B| =o |A| +c |B|"
   255 by (simp only: csum_def Field_card_of card_of_refl)
   256 
   257 lemma Un_csum: "|A \<union> B| \<le>o |A| +c |B|"
   258 using ordLeq_ordIso_trans[OF card_of_Un_Plus_ordLeq Plus_csum] by blast
   259 
   260 
   261 subsection {* One *}
   262 
   263 definition cone where
   264   "cone = card_of {()}"
   265 
   266 lemma Card_order_cone: "Card_order cone"
   267 unfolding cone_def by (rule card_of_Card_order)
   268 
   269 lemma Cfinite_cone: "Cfinite cone"
   270   unfolding cfinite_def by (simp add: Card_order_cone)
   271 
   272 lemma cone_not_czero: "\<not> (cone =o czero)"
   273 unfolding czero_def cone_def ordIso_iff_ordLeq using card_of_empty3 empty_not_insert by blast
   274 
   275 lemma cone_ordLeq_Cnotzero: "Cnotzero r \<Longrightarrow> cone \<le>o r"
   276 unfolding cone_def by (rule Card_order_singl_ordLeq) (auto intro: czeroI)
   277 
   278 
   279 subsection {* Two *}
   280 
   281 definition ctwo where
   282   "ctwo = |UNIV :: bool set|"
   283 
   284 lemma Card_order_ctwo: "Card_order ctwo"
   285 unfolding ctwo_def by (rule card_of_Card_order)
   286 
   287 lemma ctwo_not_czero: "\<not> (ctwo =o czero)"
   288 using card_of_empty3[of "UNIV :: bool set"] ordIso_iff_ordLeq
   289 unfolding czero_def ctwo_def using UNIV_not_empty by auto
   290 
   291 lemma ctwo_Cnotzero: "Cnotzero ctwo"
   292 by (simp add: ctwo_not_czero Card_order_ctwo)
   293 
   294 
   295 subsection {* Family sum *}
   296 
   297 definition Csum where
   298   "Csum r rs \<equiv> |SIGMA i : Field r. Field (rs i)|"
   299 
   300 (* Similar setup to the one for SIGMA from theory Big_Operators: *)
   301 syntax "_Csum" ::
   302   "pttrn => ('a * 'a) set => 'b * 'b set => (('a * 'b) * ('a * 'b)) set"
   303   ("(3CSUM _:_. _)" [0, 51, 10] 10)
   304 
   305 translations
   306   "CSUM i:r. rs" == "CONST Csum r (%i. rs)"
   307 
   308 lemma SIGMA_CSUM: "|SIGMA i : I. As i| = (CSUM i : |I|. |As i| )"
   309 by (auto simp: Csum_def Field_card_of)
   310 
   311 (* NB: Always, under the cardinal operator,
   312 operations on sets are reduced automatically to operations on cardinals.
   313 This should make cardinal reasoning more direct and natural.  *)
   314 
   315 
   316 subsection {* Product *}
   317 
   318 definition cprod (infixr "*c" 80) where
   319   "r1 *c r2 = |Field r1 <*> Field r2|"
   320 
   321 lemma card_order_cprod:
   322   assumes "card_order r1" "card_order r2"
   323   shows "card_order (r1 *c r2)"
   324 proof -
   325   have "Field r1 = UNIV" "Field r2 = UNIV" using assms card_order_on_Card_order by auto
   326   thus ?thesis by (auto simp: cprod_def card_of_card_order_on)
   327 qed
   328 
   329 lemma Card_order_cprod: "Card_order (r1 *c r2)"
   330 by (simp only: cprod_def Field_card_of card_of_card_order_on)
   331 
   332 lemma cprod_mono1: "p1 \<le>o r1 \<Longrightarrow> p1 *c q \<le>o r1 *c q"
   333 by (simp only: cprod_def ordLeq_Times_mono1)
   334 
   335 lemma cprod_mono2: "p2 \<le>o r2 \<Longrightarrow> q *c p2 \<le>o q *c r2"
   336 by (simp only: cprod_def ordLeq_Times_mono2)
   337 
   338 lemma cprod_mono: "\<lbrakk>p1 \<le>o r1; p2 \<le>o r2\<rbrakk> \<Longrightarrow> p1 *c p2 \<le>o r1 *c r2"
   339 by (rule ordLeq_transitive[OF cprod_mono1 cprod_mono2])
   340 
   341 lemma ordLeq_cprod2: "\<lbrakk>Cnotzero p1; Card_order p2\<rbrakk> \<Longrightarrow> p2 \<le>o p1 *c p2"
   342 unfolding cprod_def by (rule Card_order_Times2) (auto intro: czeroI)
   343 
   344 lemma cinfinite_cprod: "\<lbrakk>cinfinite r1; cinfinite r2\<rbrakk> \<Longrightarrow> cinfinite (r1 *c r2)"
   345 by (simp add: cinfinite_def cprod_def Field_card_of infinite_cartesian_product)
   346 
   347 lemma cinfinite_cprod2: "\<lbrakk>Cnotzero r1; Cinfinite r2\<rbrakk> \<Longrightarrow> cinfinite (r1 *c r2)"
   348 by (rule cinfinite_mono) (auto intro: ordLeq_cprod2)
   349 
   350 lemma Cinfinite_cprod2: "\<lbrakk>Cnotzero r1; Cinfinite r2\<rbrakk> \<Longrightarrow> Cinfinite (r1 *c r2)"
   351 by (blast intro: cinfinite_cprod2 Card_order_cprod)
   352 
   353 lemma cprod_cong: "\<lbrakk>p1 =o r1; p2 =o r2\<rbrakk> \<Longrightarrow> p1 *c p2 =o r1 *c r2"
   354 unfolding ordIso_iff_ordLeq by (blast intro: cprod_mono)
   355 
   356 lemma cprod_cong1: "\<lbrakk>p1 =o r1\<rbrakk> \<Longrightarrow> p1 *c p2 =o r1 *c p2"
   357 unfolding ordIso_iff_ordLeq by (blast intro: cprod_mono1)
   358 
   359 lemma cprod_cong2: "p2 =o r2 \<Longrightarrow> q *c p2 =o q *c r2"
   360 unfolding ordIso_iff_ordLeq by (blast intro: cprod_mono2)
   361 
   362 lemma cprod_com: "p1 *c p2 =o p2 *c p1"
   363 by (simp only: cprod_def card_of_Times_commute)
   364 
   365 lemma card_of_Csum_Times:
   366   "\<forall>i \<in> I. |A i| \<le>o |B| \<Longrightarrow> (CSUM i : |I|. |A i| ) \<le>o |I| *c |B|"
   367 by (simp only: Csum_def cprod_def Field_card_of card_of_Sigma_Times)
   368 
   369 lemma card_of_Csum_Times':
   370   assumes "Card_order r" "\<forall>i \<in> I. |A i| \<le>o r"
   371   shows "(CSUM i : |I|. |A i| ) \<le>o |I| *c r"
   372 proof -
   373   from assms(1) have *: "r =o |Field r|" by (simp add: card_of_unique)
   374   with assms(2) have "\<forall>i \<in> I. |A i| \<le>o |Field r|" by (blast intro: ordLeq_ordIso_trans)
   375   hence "(CSUM i : |I|. |A i| ) \<le>o |I| *c |Field r|" by (simp only: card_of_Csum_Times)
   376   also from * have "|I| *c |Field r| \<le>o |I| *c r"
   377     by (simp only: Field_card_of card_of_refl cprod_def ordIso_imp_ordLeq)
   378   finally show ?thesis .
   379 qed
   380 
   381 lemma cprod_csum_distrib1: "r1 *c r2 +c r1 *c r3 =o r1 *c (r2 +c r3)"
   382 unfolding csum_def cprod_def by (simp add: Field_card_of card_of_Times_Plus_distrib ordIso_symmetric)
   383 
   384 lemma csum_absorb2': "\<lbrakk>Card_order r2; r1 \<le>o r2; cinfinite r1 \<or> cinfinite r2\<rbrakk> \<Longrightarrow> r1 +c r2 =o r2"
   385 unfolding csum_def by (rule conjunct2[OF Card_order_Plus_infinite])
   386   (auto simp: cinfinite_def dest: cinfinite_mono)
   387 
   388 lemma csum_absorb1':
   389   assumes card: "Card_order r2"
   390   and r12: "r1 \<le>o r2" and cr12: "cinfinite r1 \<or> cinfinite r2"
   391   shows "r2 +c r1 =o r2"
   392 by (rule ordIso_transitive, rule csum_com, rule csum_absorb2', (simp only: assms)+)
   393 
   394 lemma csum_absorb1: "\<lbrakk>Cinfinite r2; r1 \<le>o r2\<rbrakk> \<Longrightarrow> r2 +c r1 =o r2"
   395 by (rule csum_absorb1') auto
   396 
   397 
   398 subsection {* Exponentiation *}
   399 
   400 definition cexp (infixr "^c" 90) where
   401   "r1 ^c r2 \<equiv> |Func (Field r2) (Field r1)|"
   402 
   403 lemma Card_order_cexp: "Card_order (r1 ^c r2)"
   404 unfolding cexp_def by (rule card_of_Card_order)
   405 
   406 lemma cexp_mono':
   407   assumes 1: "p1 \<le>o r1" and 2: "p2 \<le>o r2"
   408   and n: "Field p2 = {} \<Longrightarrow> Field r2 = {}"
   409   shows "p1 ^c p2 \<le>o r1 ^c r2"
   410 proof(cases "Field p1 = {}")
   411   case True
   412   hence "Field p2 \<noteq> {} \<Longrightarrow> Func (Field p2) {} = {}" unfolding Func_is_emp by simp
   413   with True have "|Field |Func (Field p2) (Field p1)|| \<le>o cone"
   414     unfolding cone_def Field_card_of
   415     by (cases "Field p2 = {}", auto intro: surj_imp_ordLeq simp: Func_empty)
   416   hence "|Func (Field p2) (Field p1)| \<le>o cone" by (simp add: Field_card_of cexp_def)
   417   hence "p1 ^c p2 \<le>o cone" unfolding cexp_def .
   418   thus ?thesis
   419   proof (cases "Field p2 = {}")
   420     case True
   421     with n have "Field r2 = {}" .
   422     hence "cone \<le>o r1 ^c r2" unfolding cone_def cexp_def Func_def
   423       by (auto intro: card_of_ordLeqI[where f="\<lambda>_ _. undefined"])
   424     thus ?thesis using `p1 ^c p2 \<le>o cone` ordLeq_transitive by auto
   425   next
   426     case False with True have "|Field (p1 ^c p2)| =o czero"
   427       unfolding card_of_ordIso_czero_iff_empty cexp_def Field_card_of Func_def by auto
   428     thus ?thesis unfolding cexp_def card_of_ordIso_czero_iff_empty Field_card_of
   429       by (simp add: card_of_empty)
   430   qed
   431 next
   432   case False
   433   have 1: "|Field p1| \<le>o |Field r1|" and 2: "|Field p2| \<le>o |Field r2|"
   434     using 1 2 by (auto simp: card_of_mono2)
   435   obtain f1 where f1: "f1 ` Field r1 = Field p1"
   436     using 1 unfolding card_of_ordLeq2[OF False, symmetric] by auto
   437   obtain f2 where f2: "inj_on f2 (Field p2)" "f2 ` Field p2 \<subseteq> Field r2"
   438     using 2 unfolding card_of_ordLeq[symmetric] by blast
   439   have 0: "Func_map (Field p2) f1 f2 ` (Field (r1 ^c r2)) = Field (p1 ^c p2)"
   440     unfolding cexp_def Field_card_of using Func_map_surj[OF f1 f2 n, symmetric] .
   441   have 00: "Field (p1 ^c p2) \<noteq> {}" unfolding cexp_def Field_card_of Func_is_emp
   442     using False by simp
   443   show ?thesis
   444     using 0 card_of_ordLeq2[OF 00] unfolding cexp_def Field_card_of by blast
   445 qed
   446 
   447 lemma cexp_mono:
   448   assumes 1: "p1 \<le>o r1" and 2: "p2 \<le>o r2"
   449   and n: "p2 =o czero \<Longrightarrow> r2 =o czero" and card: "Card_order p2"
   450   shows "p1 ^c p2 \<le>o r1 ^c r2"
   451   by (rule cexp_mono'[OF 1 2 czeroE[OF n[OF czeroI[OF card]]]])
   452 
   453 lemma cexp_mono1:
   454   assumes 1: "p1 \<le>o r1" and q: "Card_order q"
   455   shows "p1 ^c q \<le>o r1 ^c q"
   456 using ordLeq_refl[OF q] by (rule cexp_mono[OF 1]) (auto simp: q)
   457 
   458 lemma cexp_mono2':
   459   assumes 2: "p2 \<le>o r2" and q: "Card_order q"
   460   and n: "Field p2 = {} \<Longrightarrow> Field r2 = {}"
   461   shows "q ^c p2 \<le>o q ^c r2"
   462 using ordLeq_refl[OF q] by (rule cexp_mono'[OF _ 2 n]) auto
   463 
   464 lemma cexp_mono2:
   465   assumes 2: "p2 \<le>o r2" and q: "Card_order q"
   466   and n: "p2 =o czero \<Longrightarrow> r2 =o czero" and card: "Card_order p2"
   467   shows "q ^c p2 \<le>o q ^c r2"
   468 using ordLeq_refl[OF q] by (rule cexp_mono[OF _ 2 n card]) auto
   469 
   470 lemma cexp_mono2_Cnotzero:
   471   assumes "p2 \<le>o r2" "Card_order q" "Cnotzero p2"
   472   shows "q ^c p2 \<le>o q ^c r2"
   473 using assms(3) czeroI by (blast intro: cexp_mono2'[OF assms(1,2)])
   474 
   475 lemma cexp_cong:
   476   assumes 1: "p1 =o r1" and 2: "p2 =o r2"
   477   and Cr: "Card_order r2"
   478   and Cp: "Card_order p2"
   479   shows "p1 ^c p2 =o r1 ^c r2"
   480 proof -
   481   obtain f where "bij_betw f (Field p2) (Field r2)"
   482     using 2 card_of_ordIso[of "Field p2" "Field r2"] card_of_cong by auto
   483   hence 0: "Field p2 = {} \<longleftrightarrow> Field r2 = {}" unfolding bij_betw_def by auto
   484   have r: "p2 =o czero \<Longrightarrow> r2 =o czero"
   485     and p: "r2 =o czero \<Longrightarrow> p2 =o czero"
   486      using 0 Cr Cp czeroE czeroI by auto
   487   show ?thesis using 0 1 2 unfolding ordIso_iff_ordLeq
   488     using r p cexp_mono[OF _ _ _ Cp] cexp_mono[OF _ _ _ Cr] by blast
   489 qed
   490 
   491 lemma cexp_cong1:
   492   assumes 1: "p1 =o r1" and q: "Card_order q"
   493   shows "p1 ^c q =o r1 ^c q"
   494 by (rule cexp_cong[OF 1 _ q q]) (rule ordIso_refl[OF q])
   495 
   496 lemma cexp_cong2:
   497   assumes 2: "p2 =o r2" and q: "Card_order q" and p: "Card_order p2"
   498   shows "q ^c p2 =o q ^c r2"
   499 by (rule cexp_cong[OF _ 2]) (auto simp only: ordIso_refl Card_order_ordIso2[OF p 2] q p)
   500 
   501 lemma cexp_cone:
   502   assumes "Card_order r"
   503   shows "r ^c cone =o r"
   504 proof -
   505   have "r ^c cone =o |Field r|"
   506     unfolding cexp_def cone_def Field_card_of Func_empty
   507       card_of_ordIso[symmetric] bij_betw_def Func_def inj_on_def image_def
   508     by (rule exI[of _ "\<lambda>f. f ()"]) auto
   509   also have "|Field r| =o r" by (rule card_of_Field_ordIso[OF assms])
   510   finally show ?thesis .
   511 qed
   512 
   513 lemma cexp_cprod:
   514   assumes r1: "Card_order r1"
   515   shows "(r1 ^c r2) ^c r3 =o r1 ^c (r2 *c r3)" (is "?L =o ?R")
   516 proof -
   517   have "?L =o r1 ^c (r3 *c r2)"
   518     unfolding cprod_def cexp_def Field_card_of
   519     using card_of_Func_Times by(rule ordIso_symmetric)
   520   also have "r1 ^c (r3 *c r2) =o ?R"
   521     apply(rule cexp_cong2) using cprod_com r1 by (auto simp: Card_order_cprod)
   522   finally show ?thesis .
   523 qed
   524 
   525 lemma cprod_infinite1': "\<lbrakk>Cinfinite r; Cnotzero p; p \<le>o r\<rbrakk> \<Longrightarrow> r *c p =o r"
   526 unfolding cinfinite_def cprod_def
   527 by (rule Card_order_Times_infinite[THEN conjunct1]) (blast intro: czeroI)+
   528 
   529 lemma cprod_infinite: "Cinfinite r \<Longrightarrow> r *c r =o r"
   530 using cprod_infinite1' Cinfinite_Cnotzero ordLeq_refl by blast
   531 
   532 lemma cexp_cprod_ordLeq:
   533   assumes r1: "Card_order r1" and r2: "Cinfinite r2"
   534   and r3: "Cnotzero r3" "r3 \<le>o r2"
   535   shows "(r1 ^c r2) ^c r3 =o r1 ^c r2" (is "?L =o ?R")
   536 proof-
   537   have "?L =o r1 ^c (r2 *c r3)" using cexp_cprod[OF r1] .
   538   also have "r1 ^c (r2 *c r3) =o ?R"
   539   apply(rule cexp_cong2)
   540   apply(rule cprod_infinite1'[OF r2 r3]) using r1 r2 by (fastforce simp: Card_order_cprod)+
   541   finally show ?thesis .
   542 qed
   543 
   544 lemma Cnotzero_UNIV: "Cnotzero |UNIV|"
   545 by (auto simp: card_of_Card_order card_of_ordIso_czero_iff_empty)
   546 
   547 lemma ordLess_ctwo_cexp:
   548   assumes "Card_order r"
   549   shows "r <o ctwo ^c r"
   550 proof -
   551   have "r <o |Pow (Field r)|" using assms by (rule Card_order_Pow)
   552   also have "|Pow (Field r)| =o ctwo ^c r"
   553     unfolding ctwo_def cexp_def Field_card_of by (rule card_of_Pow_Func)
   554   finally show ?thesis .
   555 qed
   556 
   557 lemma ordLeq_cexp1:
   558   assumes "Cnotzero r" "Card_order q"
   559   shows "q \<le>o q ^c r"
   560 proof (cases "q =o (czero :: 'a rel)")
   561   case True thus ?thesis by (simp only: card_of_empty cexp_def czero_def ordIso_ordLeq_trans)
   562 next
   563   case False
   564   thus ?thesis
   565     apply -
   566     apply (rule ordIso_ordLeq_trans)
   567     apply (rule ordIso_symmetric)
   568     apply (rule cexp_cone)
   569     apply (rule assms(2))
   570     apply (rule cexp_mono2)
   571     apply (rule cone_ordLeq_Cnotzero)
   572     apply (rule assms(1))
   573     apply (rule assms(2))
   574     apply (rule notE)
   575     apply (rule cone_not_czero)
   576     apply assumption
   577     apply (rule Card_order_cone)
   578   done
   579 qed
   580 
   581 lemma ordLeq_cexp2:
   582   assumes "ctwo \<le>o q" "Card_order r"
   583   shows "r \<le>o q ^c r"
   584 proof (cases "r =o (czero :: 'a rel)")
   585   case True thus ?thesis by (simp only: card_of_empty cexp_def czero_def ordIso_ordLeq_trans)
   586 next
   587   case False thus ?thesis
   588     apply -
   589     apply (rule ordLess_imp_ordLeq)
   590     apply (rule ordLess_ordLeq_trans)
   591     apply (rule ordLess_ctwo_cexp)
   592     apply (rule assms(2))
   593     apply (rule cexp_mono1)
   594     apply (rule assms(1))
   595     apply (rule assms(2))
   596   done
   597 qed
   598 
   599 lemma cinfinite_cexp: "\<lbrakk>ctwo \<le>o q; Cinfinite r\<rbrakk> \<Longrightarrow> cinfinite (q ^c r)"
   600 by (rule cinfinite_mono[OF ordLeq_cexp2]) simp_all
   601 
   602 lemma Cinfinite_cexp:
   603   "\<lbrakk>ctwo \<le>o q; Cinfinite r\<rbrakk> \<Longrightarrow> Cinfinite (q ^c r)"
   604 by (simp add: cinfinite_cexp Card_order_cexp)
   605 
   606 lemma ctwo_ordLess_natLeq: "ctwo <o natLeq"
   607 unfolding ctwo_def using finite_UNIV natLeq_cinfinite natLeq_Card_order
   608 by (intro Cfinite_ordLess_Cinfinite) (auto simp: cfinite_def card_of_Card_order)
   609 
   610 lemma ctwo_ordLess_Cinfinite: "Cinfinite r \<Longrightarrow> ctwo <o r"
   611 by (rule ordLess_ordLeq_trans[OF ctwo_ordLess_natLeq natLeq_ordLeq_cinfinite])
   612 
   613 lemma ctwo_ordLeq_Cinfinite:
   614   assumes "Cinfinite r"
   615   shows "ctwo \<le>o r"
   616 by (rule ordLess_imp_ordLeq[OF ctwo_ordLess_Cinfinite[OF assms]])
   617 
   618 lemma Un_Cinfinite_bound: "\<lbrakk>|A| \<le>o r; |B| \<le>o r; Cinfinite r\<rbrakk> \<Longrightarrow> |A \<union> B| \<le>o r"
   619 by (auto simp add: cinfinite_def card_of_Un_ordLeq_infinite_Field)
   620 
   621 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"
   622 by (auto simp add: card_of_UNION_ordLeq_infinite_Field cinfinite_def)
   623 
   624 lemma csum_cinfinite_bound:
   625   assumes "p \<le>o r" "q \<le>o r" "Card_order p" "Card_order q" "Cinfinite r"
   626   shows "p +c q \<le>o r"
   627 proof -
   628   from assms(1-4) have "|Field p| \<le>o r" "|Field q| \<le>o r"
   629     unfolding card_order_on_def using card_of_least ordLeq_transitive by blast+
   630   with assms show ?thesis unfolding cinfinite_def csum_def
   631     by (blast intro: card_of_Plus_ordLeq_infinite_Field)
   632 qed
   633 
   634 lemma cprod_cinfinite_bound:
   635   assumes "p \<le>o r" "q \<le>o r" "Card_order p" "Card_order q" "Cinfinite r"
   636   shows "p *c q \<le>o r"
   637 proof -
   638   from assms(1-4) have "|Field p| \<le>o r" "|Field q| \<le>o r"
   639     unfolding card_order_on_def using card_of_least ordLeq_transitive by blast+
   640   with assms show ?thesis unfolding cinfinite_def cprod_def
   641     by (blast intro: card_of_Times_ordLeq_infinite_Field)
   642 qed
   643 
   644 lemma cprod_csum_cexp:
   645   "r1 *c r2 \<le>o (r1 +c r2) ^c ctwo"
   646 unfolding cprod_def csum_def cexp_def ctwo_def Field_card_of
   647 proof -
   648   let ?f = "\<lambda>(a, b). %x. if x then Inl a else Inr b"
   649   have "inj_on ?f (Field r1 \<times> Field r2)" (is "inj_on _ ?LHS")
   650     by (auto simp: inj_on_def fun_eq_iff split: bool.split)
   651   moreover
   652   have "?f ` ?LHS \<subseteq> Func (UNIV :: bool set) (Field r1 <+> Field r2)" (is "_ \<subseteq> ?RHS")
   653     by (auto simp: Func_def)
   654   ultimately show "|?LHS| \<le>o |?RHS|" using card_of_ordLeq by blast
   655 qed
   656 
   657 lemma Cfinite_cprod_Cinfinite: "\<lbrakk>Cfinite r; Cinfinite s\<rbrakk> \<Longrightarrow> r *c s \<le>o s"
   658 by (intro cprod_cinfinite_bound)
   659   (auto intro: ordLeq_refl ordLess_imp_ordLeq[OF Cfinite_ordLess_Cinfinite])
   660 
   661 lemma cprod_cexp: "(r *c s) ^c t =o r ^c t *c s ^c t"
   662   unfolding cprod_def cexp_def Field_card_of by (rule Func_Times_Range)
   663 
   664 lemma cprod_cexp_csum_cexp_Cinfinite:
   665   assumes t: "Cinfinite t"
   666   shows "(r *c s) ^c t \<le>o (r +c s) ^c t"
   667 proof -
   668   have "(r *c s) ^c t \<le>o ((r +c s) ^c ctwo) ^c t"
   669     by (rule cexp_mono1[OF cprod_csum_cexp conjunct2[OF t]])
   670   also have "((r +c s) ^c ctwo) ^c t =o (r +c s) ^c (ctwo *c t)"
   671     by (rule cexp_cprod[OF Card_order_csum])
   672   also have "(r +c s) ^c (ctwo *c t) =o (r +c s) ^c (t *c ctwo)"
   673     by (rule cexp_cong2[OF cprod_com Card_order_csum Card_order_cprod])
   674   also have "(r +c s) ^c (t *c ctwo) =o ((r +c s) ^c t) ^c ctwo"
   675     by (rule ordIso_symmetric[OF cexp_cprod[OF Card_order_csum]])
   676   also have "((r +c s) ^c t) ^c ctwo =o (r +c s) ^c t"
   677     by (rule cexp_cprod_ordLeq[OF Card_order_csum t ctwo_Cnotzero ctwo_ordLeq_Cinfinite[OF t]])
   678   finally show ?thesis .
   679 qed
   680 
   681 lemma Cfinite_cexp_Cinfinite:
   682   assumes s: "Cfinite s" and t: "Cinfinite t"
   683   shows "s ^c t \<le>o ctwo ^c t"
   684 proof (cases "s \<le>o ctwo")
   685   case True thus ?thesis using t by (blast intro: cexp_mono1)
   686 next
   687   case False
   688   hence "ctwo \<le>o s" using ordLeq_total[of s ctwo] Card_order_ctwo s
   689     by (auto intro: card_order_on_well_order_on)
   690   hence "Cnotzero s" using Cnotzero_mono[OF ctwo_Cnotzero] s by blast
   691   hence st: "Cnotzero (s *c t)" by (intro Cinfinite_Cnotzero[OF Cinfinite_cprod2]) (auto simp: t)
   692   have "s ^c t \<le>o (ctwo ^c s) ^c t"
   693     using assms by (blast intro: cexp_mono1 ordLess_imp_ordLeq[OF ordLess_ctwo_cexp])
   694   also have "(ctwo ^c s) ^c t =o ctwo ^c (s *c t)"
   695     by (blast intro: Card_order_ctwo cexp_cprod)
   696   also have "ctwo ^c (s *c t) \<le>o ctwo ^c t"
   697     using assms st by (intro cexp_mono2_Cnotzero Cfinite_cprod_Cinfinite Card_order_ctwo)
   698   finally show ?thesis .
   699 qed
   700 
   701 lemma csum_Cfinite_cexp_Cinfinite:
   702   assumes r: "Card_order r" and s: "Cfinite s" and t: "Cinfinite t"
   703   shows "(r +c s) ^c t \<le>o (r +c ctwo) ^c t"
   704 proof (cases "Cinfinite r")
   705   case True
   706   hence "r +c s =o r" by (intro csum_absorb1 ordLess_imp_ordLeq[OF Cfinite_ordLess_Cinfinite] s)
   707   hence "(r +c s) ^c t =o r ^c t" using t by (blast intro: cexp_cong1)
   708   also have "r ^c t \<le>o (r +c ctwo) ^c t" using t by (blast intro: cexp_mono1 ordLeq_csum1 r)
   709   finally show ?thesis .
   710 next
   711   case False
   712   with r have "Cfinite r" unfolding cinfinite_def cfinite_def by auto
   713   hence "Cfinite (r +c s)" by (intro Cfinite_csum s)
   714   hence "(r +c s) ^c t \<le>o ctwo ^c t" by (intro Cfinite_cexp_Cinfinite t)
   715   also have "ctwo ^c t \<le>o (r +c ctwo) ^c t" using t
   716     by (blast intro: cexp_mono1 ordLeq_csum2 Card_order_ctwo)
   717   finally show ?thesis .
   718 qed
   719 
   720 (* cardSuc *)
   721 
   722 lemma Cinfinite_cardSuc: "Cinfinite r \<Longrightarrow> Cinfinite (cardSuc r)"
   723 by (simp add: cinfinite_def cardSuc_Card_order cardSuc_finite)
   724 
   725 lemma cardSuc_UNION_Cinfinite:
   726   assumes "Cinfinite r" "relChain (cardSuc r) As" "B \<le> (UN i : Field (cardSuc r). As i)" "|B| <=o r"
   727   shows "EX i : Field (cardSuc r). B \<le> As i"
   728 using cardSuc_UNION assms unfolding cinfinite_def by blast
   729 
   730 end