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