author  traytel 
Mon, 25 Nov 2013 10:14:29 +0100  
changeset 54578  9387251b6a46 
parent 54482  a2874c8b3558 
child 54581  1502a1f707d9 
permissions  rwrr 
54481  1 
(* Title: HOL/Cardinals/Cardinal_Arithmetic_FP.thy 
54474  2 
Author: Dmitriy Traytel, TU Muenchen 
3 
Copyright 2012 

4 

54481  5 
Cardinal arithmetic (FP). 
54474  6 
*) 
7 

54481  8 
header {* Cardinal Arithmetic (FP) *} 
54474  9 

54481  10 
theory Cardinal_Arithmetic_FP 
11 
imports Cardinal_Order_Relation_FP 

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

54482  20 
unfolding dir_image_def Field_def Range_def Domain_def by fast 
54474  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 

54482  67 
apply safe 
68 
apply (simp add: Func_def fun_eq_iff) 

69 
apply (metis (no_types) pair_collapse) 

70 
apply (auto simp: Func_def fun_eq_iff)[2] 

71 
proof  

54474  72 
fix f g assume "f \<in> Func A B" "g \<in> Func A C" 
73 
thus "(f, g) \<in> ?F ` Func A (B \<times> C)" 

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

54482  75 
qed 
54474  76 
thus ?thesis using card_of_ordIso by blast 
77 
qed 

78 

79 

80 
subsection {* Zero *} 

81 

82 
definition czero where 

83 
"czero = card_of {}" 

84 

85 
lemma czero_ordIso: 

86 
"czero =o czero" 

87 
using card_of_empty_ordIso by (simp add: czero_def) 

88 

89 
lemma card_of_ordIso_czero_iff_empty: 

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

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

92 

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

94 
abbreviation Cnotzero where 

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

96 

97 
(*helper*) 

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

99 
by (metis Card_order_iff_ordIso_card_of czero_def) 

100 

101 
lemma czeroI: 

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

103 
using Cnotzero_imp_not_empty ordIso_transitive[OF _ czero_ordIso] by blast 

104 

105 
lemma czeroE: 

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

107 
unfolding czero_def 

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

109 

110 
lemma Cnotzero_mono: 

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

112 
apply (rule ccontr) 

113 
apply auto 

114 
apply (drule czeroE) 

115 
apply (erule notE) 

116 
apply (erule czeroI) 

117 
apply (drule card_of_mono2) 

118 
apply (simp only: card_of_empty3) 

119 
done 

120 

121 
subsection {* (In)finite cardinals *} 

122 

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  125 

126 
abbreviation Cinfinite where 

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

128 

129 
definition cfinite where 

130 
"cfinite r = finite (Field r)" 

131 

132 
abbreviation Cfinite where 

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

134 

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

136 
unfolding cfinite_def cinfinite_def 

137 
by (metis card_order_on_well_order_on finite_ordLess_infinite) 

138 

139 
lemma natLeq_ordLeq_cinfinite: 

140 
assumes inf: "Cinfinite r" 

141 
shows "natLeq \<le>o r" 

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  144 
also from inf have "Field r =o r" by (simp add: card_of_unique ordIso_symmetric) 
145 
finally show ?thesis . 

146 
qed 

147 

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

149 
unfolding cinfinite_def by (metis czeroE finite.emptyI) 

150 

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

152 
by (metis cinfinite_not_czero) 

153 

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

155 
by (metis Card_order_ordIso2 card_of_mono2 card_of_ordLeq_infinite cinfinite_def ordIso_iff_ordLeq) 

156 

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

158 
by (metis card_of_mono2 card_of_ordLeq_infinite cinfinite_def) 

159 

160 

161 
subsection {* Binary sum *} 

162 

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

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

165 

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

167 
unfolding csum_def Field_card_of by auto 

168 

169 
lemma Card_order_csum: 

170 
"Card_order (r1 +c r2)" 

171 
unfolding csum_def by (simp add: card_of_Card_order) 

172 

173 
lemma csum_Cnotzero1: 

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

175 
unfolding csum_def 

54482  176 
by (metis Cnotzero_imp_not_empty Plus_eq_empty_conv card_of_Card_order card_of_ordIso_czero_iff_empty) 
54474  177 

178 
lemma card_order_csum: 

179 
assumes "card_order r1" "card_order r2" 

180 
shows "card_order (r1 +c r2)" 

181 
proof  

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

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

184 
qed 

185 

186 
lemma cinfinite_csum: 

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

188 
unfolding cinfinite_def csum_def by (auto simp: Field_card_of) 

189 

190 
lemma Cinfinite_csum1: 

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

192 
unfolding cinfinite_def csum_def by (metis Field_card_of card_of_Card_order finite_Plus_iff) 

193 

54480
57e781b711b5
no need for 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

194 
lemma Cinfinite_csum: 
57e781b711b5
no need for 3way 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 3way 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 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

197 

57e781b711b5
no need for 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

198 
lemma Cinfinite_csum_strong: 
57e781b711b5
no need for 3way 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 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

200 
by (metis Cinfinite_csum) 
57e781b711b5
no need for 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

201 

54474  202 
lemma csum_cong: "\<lbrakk>p1 =o r1; p2 =o r2\<rbrakk> \<Longrightarrow> p1 +c p2 =o r1 +c r2" 
203 
by (simp only: csum_def ordIso_Plus_cong) 

204 

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

206 
by (simp only: csum_def ordIso_Plus_cong1) 

207 

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

209 
by (simp only: csum_def ordIso_Plus_cong2) 

210 

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

212 
by (simp only: csum_def ordLeq_Plus_mono) 

213 

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

215 
by (simp only: csum_def ordLeq_Plus_mono1) 

216 

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

218 
by (simp only: csum_def ordLeq_Plus_mono2) 

219 

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

221 
by (simp only: csum_def Card_order_Plus1) 

222 

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

224 
by (simp only: csum_def Card_order_Plus2) 

225 

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

227 
by (simp only: csum_def card_of_Plus_commute) 

228 

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

230 
by (simp only: csum_def Field_card_of card_of_Plus_assoc) 

231 

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

233 
unfolding cfinite_def csum_def Field_card_of using card_of_card_order_on by simp 

234 

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

236 
proof  

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

238 
by (metis csum_assoc) 

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

240 
by (metis csum_assoc csum_cong2 ordIso_symmetric) 

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

242 
by (metis csum_com csum_cong1 csum_cong2) 

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

244 
by (metis csum_assoc csum_cong2 ordIso_symmetric) 

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

246 
by (metis csum_assoc ordIso_symmetric) 

247 
finally show ?thesis . 

248 
qed 

249 

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

251 
by (simp only: csum_def Field_card_of card_of_refl) 

252 

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

254 
using ordLeq_ordIso_trans[OF card_of_Un_Plus_ordLeq Plus_csum] by blast 

255 

256 

257 
subsection {* One *} 

258 

259 
definition cone where 

260 
"cone = card_of {()}" 

261 

262 
lemma Card_order_cone: "Card_order cone" 

263 
unfolding cone_def by (rule card_of_Card_order) 

264 

265 
lemma Cfinite_cone: "Cfinite cone" 

266 
unfolding cfinite_def by (simp add: Card_order_cone) 

267 

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

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

270 

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

272 
unfolding cone_def by (metis Card_order_singl_ordLeq czeroI) 

273 

274 

275 
subsection{* Two *} 

276 

277 
definition ctwo where 

278 
"ctwo = UNIV :: bool set" 

279 

280 
lemma Card_order_ctwo: "Card_order ctwo" 

281 
unfolding ctwo_def by (rule card_of_Card_order) 

282 

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

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

285 
unfolding czero_def ctwo_def by (metis UNIV_not_empty) 

286 

287 
lemma ctwo_Cnotzero: "Cnotzero ctwo" 

288 
by (simp add: ctwo_not_czero Card_order_ctwo) 

289 

290 

291 
subsection {* Family sum *} 

292 

293 
definition Csum where 

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

295 

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

297 
syntax "_Csum" :: 

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

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

300 

301 
translations 

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

303 

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

305 
by (auto simp: Csum_def Field_card_of) 

306 

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

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

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

310 

311 

312 
subsection {* Product *} 

313 

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

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

316 

317 
lemma card_order_cprod: 

318 
assumes "card_order r1" "card_order r2" 

319 
shows "card_order (r1 *c r2)" 

320 
proof  

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

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

323 
qed 

324 

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

326 
by (simp only: cprod_def Field_card_of card_of_card_order_on) 

327 

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

329 
by (simp only: cprod_def ordLeq_Times_mono1) 

330 

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

332 
by (simp only: cprod_def ordLeq_Times_mono2) 

333 

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

335 
unfolding cprod_def by (metis Card_order_Times2 czeroI) 

336 

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

338 
by (simp add: cinfinite_def cprod_def Field_card_of infinite_cartesian_product) 

339 

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

341 
by (metis cinfinite_mono ordLeq_cprod2) 

342 

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

344 
by (blast intro: cinfinite_cprod2 Card_order_cprod) 

345 

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

347 
by (simp only: cprod_def card_of_Times_commute) 

348 

349 
lemma card_of_Csum_Times: 

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

351 
by (simp only: Csum_def cprod_def Field_card_of card_of_Sigma_Times) 

352 

353 
lemma card_of_Csum_Times': 

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

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

356 
proof  

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

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

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

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

361 
by (simp only: Field_card_of card_of_refl cprod_def ordIso_imp_ordLeq) 

362 
finally show ?thesis . 

363 
qed 

364 

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

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

367 

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

369 
unfolding csum_def by (metis Card_order_Plus_infinite cinfinite_def cinfinite_mono) 

370 

371 
lemma csum_absorb1': 

372 
assumes card: "Card_order r2" 

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

374 
shows "r2 +c r1 =o r2" 

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

376 

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

378 
by (rule csum_absorb1') auto 

379 

380 

381 
subsection {* Exponentiation *} 

382 

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

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

385 

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

387 
unfolding cexp_def by (rule card_of_Card_order) 

388 

389 
lemma cexp_mono': 

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

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

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

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

394 
case True 

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

396 
unfolding cone_def Field_card_of 

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

398 
(metis Func_is_emp card_of_empty ex_in_conv) 

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

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

401 
thus ?thesis 

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

403 
case True 

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

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

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

407 
next 

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

409 
unfolding card_of_ordIso_czero_iff_empty cexp_def Field_card_of Func_def by auto 

410 
thus ?thesis unfolding cexp_def card_of_ordIso_czero_iff_empty Field_card_of 

411 
by (simp add: card_of_empty) 

412 
qed 

413 
next 

414 
case False 

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

416 
using 1 2 by (auto simp: card_of_mono2) 

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

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

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

420 
using 2 unfolding card_of_ordLeq[symmetric] by blast 

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

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

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

424 
using False by simp 

425 
show ?thesis 

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

427 
qed 

428 

429 
lemma cexp_mono: 

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

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

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

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

434 

435 
lemma cexp_mono1: 

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

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

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

439 

440 
lemma cexp_mono2': 

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

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

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

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

445 

446 
lemma cexp_mono2: 

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

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

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

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

451 

452 
lemma cexp_mono2_Cnotzero: 

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

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

455 
by (metis assms cexp_mono2' czeroI) 

456 

457 
lemma cexp_cong: 

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

459 
and Cr: "Card_order r2" 

460 
and Cp: "Card_order p2" 

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

462 
proof  

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

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

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

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

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

468 
using 0 Cr Cp czeroE czeroI by auto 

469 
show ?thesis using 0 1 2 unfolding ordIso_iff_ordLeq 

54482  470 
using r p cexp_mono[OF _ _ _ Cp] cexp_mono[OF _ _ _ Cr] by metis 
54474  471 
qed 
472 

473 
lemma cexp_cong1: 

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

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

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

477 

478 
lemma cexp_cong2: 

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

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

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

482 

483 
lemma cexp_cone: 

484 
assumes "Card_order r" 

485 
shows "r ^c cone =o r" 

486 
proof  

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

488 
unfolding cexp_def cone_def Field_card_of Func_empty 

489 
card_of_ordIso[symmetric] bij_betw_def Func_def inj_on_def image_def 

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

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

492 
finally show ?thesis . 

493 
qed 

494 

495 
lemma cexp_cprod: 

496 
assumes r1: "Card_order r1" 

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

498 
proof  

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

500 
unfolding cprod_def cexp_def Field_card_of 

501 
using card_of_Func_Times by(rule ordIso_symmetric) 

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

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

504 
finally show ?thesis . 

505 
qed 

506 

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

508 
unfolding cinfinite_def cprod_def 

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

510 

511 
lemma cexp_cprod_ordLeq: 

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

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

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

515 
proof 

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

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

518 
apply(rule cexp_cong2) 

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

520 
finally show ?thesis . 

521 
qed 

522 

523 
lemma Cnotzero_UNIV: "Cnotzero UNIV" 

524 
by (auto simp: card_of_Card_order card_of_ordIso_czero_iff_empty) 

525 

526 
lemma ordLess_ctwo_cexp: 

527 
assumes "Card_order r" 

528 
shows "r <o ctwo ^c r" 

529 
proof  

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

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

532 
unfolding ctwo_def cexp_def Field_card_of by (rule card_of_Pow_Func) 

533 
finally show ?thesis . 

534 
qed 

535 

536 
lemma ordLeq_cexp1: 

537 
assumes "Cnotzero r" "Card_order q" 

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

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

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

541 
next 

542 
case False 

543 
thus ?thesis 

544 
apply  

545 
apply (rule ordIso_ordLeq_trans) 

546 
apply (rule ordIso_symmetric) 

547 
apply (rule cexp_cone) 

548 
apply (rule assms(2)) 

549 
apply (rule cexp_mono2) 

550 
apply (rule cone_ordLeq_Cnotzero) 

551 
apply (rule assms(1)) 

552 
apply (rule assms(2)) 

553 
apply (rule notE) 

554 
apply (rule cone_not_czero) 

555 
apply assumption 

556 
apply (rule Card_order_cone) 

557 
done 

558 
qed 

559 

560 
lemma ordLeq_cexp2: 

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

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

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

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

565 
next 

566 
case False thus ?thesis 

567 
apply  

568 
apply (rule ordLess_imp_ordLeq) 

569 
apply (rule ordLess_ordLeq_trans) 

570 
apply (rule ordLess_ctwo_cexp) 

571 
apply (rule assms(2)) 

572 
apply (rule cexp_mono1) 

573 
apply (rule assms(1)) 

574 
apply (rule assms(2)) 

575 
done 

576 
qed 

577 

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

579 
by (metis assms cinfinite_mono ordLeq_cexp2) 

580 

581 
lemma Cinfinite_cexp: 

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

583 
by (simp add: cinfinite_cexp Card_order_cexp) 

584 

585 
lemma ctwo_ordLess_natLeq: "ctwo <o natLeq" 

586 
unfolding ctwo_def using finite_iff_ordLess_natLeq finite_UNIV by fast 

587 

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

589 
by (metis ctwo_ordLess_natLeq natLeq_ordLeq_cinfinite ordLess_ordLeq_trans) 

590 

591 
lemma ctwo_ordLeq_Cinfinite: 

592 
assumes "Cinfinite r" 

593 
shows "ctwo \<le>o r" 

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

595 

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

597 
by (auto simp add: cinfinite_def card_of_Un_ordLeq_infinite_Field) 

598 

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" 

600 
by (auto simp add: card_of_UNION_ordLeq_infinite_Field cinfinite_def) 

601 

602 
lemma csum_cinfinite_bound: 

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

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

605 
proof  

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

607 
unfolding card_order_on_def using card_of_least ordLeq_transitive by blast+ 

608 
with assms show ?thesis unfolding cinfinite_def csum_def 

609 
by (blast intro: card_of_Plus_ordLeq_infinite_Field) 

610 
qed 

611 

612 
lemma cprod_cinfinite_bound: 

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

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

615 
proof  

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

617 
unfolding card_order_on_def using card_of_least ordLeq_transitive by blast+ 

618 
with assms show ?thesis unfolding cinfinite_def cprod_def 

619 
by (blast intro: card_of_Times_ordLeq_infinite_Field) 

620 
qed 

621 

622 
lemma cprod_csum_cexp: 

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

624 
unfolding cprod_def csum_def cexp_def ctwo_def Field_card_of 

625 
proof  

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

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

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

629 
moreover 

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

631 
by (auto simp: Func_def) 

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

633 
qed 

634 

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

636 
by (intro cprod_cinfinite_bound) 

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

638 

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

640 
unfolding cprod_def cexp_def Field_card_of by (rule Func_Times_Range) 

641 

642 
lemma cprod_cexp_csum_cexp_Cinfinite: 

643 
assumes t: "Cinfinite t" 

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

645 
proof  

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

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

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

649 
by (rule cexp_cprod[OF Card_order_csum]) 

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

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

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

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

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

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

656 
finally show ?thesis . 

657 
qed 

658 

659 
lemma Cfinite_cexp_Cinfinite: 

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

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

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

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

664 
next 

665 
case False 

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

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

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

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

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

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

672 
by (blast intro: Card_order_ctwo cexp_cprod) 

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

674 
using assms st by (intro cexp_mono2_Cnotzero Cfinite_cprod_Cinfinite Card_order_ctwo) 

675 
finally show ?thesis . 

676 
qed 

677 

678 
lemma csum_Cfinite_cexp_Cinfinite: 

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

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

681 
proof (cases "Cinfinite r") 

682 
case True 

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

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

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

686 
finally show ?thesis . 

687 
next 

688 
case False 

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

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

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

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

693 
by (blast intro: cexp_mono1 ordLeq_csum2 Card_order_ctwo) 

694 
finally show ?thesis . 

695 
qed 

696 

54480
57e781b711b5
no need for 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

697 
lemma card_order_cexp: 
57e781b711b5
no need for 3way 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 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

699 
shows "card_order (r1 ^c r2)" 
57e781b711b5
no need for 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

700 
proof  
57e781b711b5
no need for 3way 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 3way 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 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

703 
qed 
57e781b711b5
no need for 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

704 

57e781b711b5
no need for 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

705 
lemma Cinfinite_ordLess_cexp: 
57e781b711b5
no need for 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

706 
assumes r: "Cinfinite r" 
57e781b711b5
no need for 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

707 
shows "r <o r ^c r" 
57e781b711b5
no need for 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

708 
proof  
57e781b711b5
no need for 3way 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 3way 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 3way 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 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

712 
finally show ?thesis . 
57e781b711b5
no need for 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

713 
qed 
57e781b711b5
no need for 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

714 

57e781b711b5
no need for 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

715 
lemma infinite_ordLeq_cexp: 
57e781b711b5
no need for 3way split with GFP for a handful of theorems
blanchet
parents:
54474
diff
changeset

716 
assumes "Cinfinite r" 
57e781b711b5
no need for 3way 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 3way 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  719 

720 
(* cardSuc *) 

721 

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

723 
by (simp add: cinfinite_def cardSuc_Card_order cardSuc_finite) 

724 

725 
lemma cardSuc_UNION_Cinfinite: 

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

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

728 
using cardSuc_UNION assms unfolding cinfinite_def by blast 

729 

730 
subsection {* Powerset *} 

731 

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

733 

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

735 
by (simp only: cpow_def Field_card_order Pow_UNIV card_of_card_order_on) 

736 

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

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

739 

54481  740 
lemma Cinfinite_cpow: "Cinfinite r \<Longrightarrow> Cinfinite (cpow r)" 
741 
unfolding cpow_def cinfinite_def by (metis Field_card_of card_of_Card_order infinite_Pow) 

742 

54474  743 
subsection {* Lists *} 
744 

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

746 

747 
end 