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