11 imports BNF_Cardinal_Order_Relation |
11 imports BNF_Cardinal_Order_Relation |
12 begin |
12 begin |
13 |
13 |
14 lemma dir_image: "\<lbrakk>\<And>x y. (f x = f y) = (x = y); Card_order r\<rbrakk> \<Longrightarrow> r =o dir_image r f" |
14 lemma dir_image: "\<lbrakk>\<And>x y. (f x = f y) = (x = y); Card_order r\<rbrakk> \<Longrightarrow> r =o dir_image r f" |
15 by (rule dir_image_ordIso) (auto simp add: inj_on_def card_order_on_def) |
15 by (rule dir_image_ordIso) (auto simp add: inj_on_def card_order_on_def) |
16 |
|
17 (*should supersede a weaker lemma from the library*) |
|
18 lemma dir_image_Field: "Field (dir_image r f) = f ` Field r" |
|
19 unfolding dir_image_def Field_def Range_def Domain_def by fast |
|
20 |
16 |
21 lemma card_order_dir_image: |
17 lemma card_order_dir_image: |
22 assumes bij: "bij f" and co: "card_order r" |
18 assumes bij: "bij f" and co: "card_order r" |
23 shows "card_order (dir_image r f)" |
19 shows "card_order (dir_image r f)" |
24 proof - |
20 proof - |
39 lemma card_of_ordIso_subst: "A = B \<Longrightarrow> |A| =o |B|" |
35 lemma card_of_ordIso_subst: "A = B \<Longrightarrow> |A| =o |B|" |
40 by (simp only: ordIso_refl card_of_Card_order) |
36 by (simp only: ordIso_refl card_of_Card_order) |
41 |
37 |
42 lemma Field_card_order: "card_order r \<Longrightarrow> Field r = UNIV" |
38 lemma Field_card_order: "card_order r \<Longrightarrow> Field r = UNIV" |
43 using card_order_on_Card_order[of UNIV r] by simp |
39 using card_order_on_Card_order[of UNIV r] by simp |
44 |
|
45 lemma card_of_Times_Plus_distrib: |
|
46 "|A <*> (B <+> C)| =o |A <*> B <+> A <*> C|" (is "|?RHS| =o |?LHS|") |
|
47 proof - |
|
48 let ?f = "\<lambda>(a, bc). case bc of Inl b \<Rightarrow> Inl (a, b) | Inr c \<Rightarrow> Inr (a, c)" |
|
49 have "bij_betw ?f ?RHS ?LHS" unfolding bij_betw_def inj_on_def by force |
|
50 thus ?thesis using card_of_ordIso by blast |
|
51 qed |
|
52 |
|
53 lemma Func_Times_Range: |
|
54 "|Func A (B <*> C)| =o |Func A B <*> Func A C|" (is "|?LHS| =o |?RHS|") |
|
55 proof - |
|
56 let ?F = "\<lambda>fg. (\<lambda>x. if x \<in> A then fst (fg x) else undefined, |
|
57 \<lambda>x. if x \<in> A then snd (fg x) else undefined)" |
|
58 let ?G = "\<lambda>(f, g) x. if x \<in> A then (f x, g x) else undefined" |
|
59 have "bij_betw ?F ?LHS ?RHS" unfolding bij_betw_def inj_on_def |
|
60 proof (intro conjI impI ballI equalityI subsetI) |
|
61 fix f g assume *: "f \<in> Func A (B \<times> C)" "g \<in> Func A (B \<times> C)" "?F f = ?F g" |
|
62 show "f = g" |
|
63 proof |
|
64 fix x from * have "fst (f x) = fst (g x) \<and> snd (f x) = snd (g x)" |
|
65 by (case_tac "x \<in> A") (auto simp: Func_def fun_eq_iff split: if_splits) |
|
66 then show "f x = g x" by (subst (1 2) surjective_pairing) simp |
|
67 qed |
|
68 next |
|
69 fix fg assume "fg \<in> Func A B \<times> Func A C" |
|
70 thus "fg \<in> ?F ` Func A (B \<times> C)" |
|
71 by (intro image_eqI[of _ _ "?G fg"]) (auto simp: Func_def) |
|
72 qed (auto simp: Func_def fun_eq_iff) |
|
73 thus ?thesis using card_of_ordIso by blast |
|
74 qed |
|
75 |
40 |
76 |
41 |
77 subsection {* Zero *} |
42 subsection {* Zero *} |
78 |
43 |
79 definition czero where |
44 definition czero where |
362 lemma cprod_com: "p1 *c p2 =o p2 *c p1" |
327 lemma cprod_com: "p1 *c p2 =o p2 *c p1" |
363 by (simp only: cprod_def card_of_Times_commute) |
328 by (simp only: cprod_def card_of_Times_commute) |
364 |
329 |
365 lemma card_of_Csum_Times: |
330 lemma card_of_Csum_Times: |
366 "\<forall>i \<in> I. |A i| \<le>o |B| \<Longrightarrow> (CSUM i : |I|. |A i| ) \<le>o |I| *c |B|" |
331 "\<forall>i \<in> I. |A i| \<le>o |B| \<Longrightarrow> (CSUM i : |I|. |A i| ) \<le>o |I| *c |B|" |
367 by (simp only: Csum_def cprod_def Field_card_of card_of_Sigma_Times) |
332 by (simp only: Csum_def cprod_def Field_card_of card_of_Sigma_mono1) |
368 |
333 |
369 lemma card_of_Csum_Times': |
334 lemma card_of_Csum_Times': |
370 assumes "Card_order r" "\<forall>i \<in> I. |A i| \<le>o r" |
335 assumes "Card_order r" "\<forall>i \<in> I. |A i| \<le>o r" |
371 shows "(CSUM i : |I|. |A i| ) \<le>o |I| *c r" |
336 shows "(CSUM i : |I|. |A i| ) \<le>o |I| *c r" |
372 proof - |
337 proof - |