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