3 *) |
3 *) |
4 |
4 |
5 section \<open>More on finite products\<close> |
5 section \<open>More on finite products\<close> |
6 |
6 |
7 theory More_Finite_Product |
7 theory More_Finite_Product |
8 imports |
8 imports More_Group |
9 More_Group |
|
10 begin |
9 begin |
11 |
10 |
12 lemma (in comm_monoid) finprod_UN_disjoint: |
11 lemma (in comm_monoid) finprod_UN_disjoint: |
13 "finite I \<Longrightarrow> (ALL i:I. finite (A i)) \<longrightarrow> (ALL i:I. ALL j:I. i ~= j \<longrightarrow> |
12 "finite I \<Longrightarrow> (\<forall>i\<in>I. finite (A i)) \<longrightarrow> (\<forall>i\<in>I. \<forall>j\<in>I. i \<noteq> j \<longrightarrow> A i \<inter> A j = {}) \<longrightarrow> |
14 (A i) Int (A j) = {}) \<longrightarrow> |
13 (\<forall>i\<in>I. \<forall>x \<in> A i. g x \<in> carrier G) \<longrightarrow> |
15 (ALL i:I. ALL x: (A i). g x : carrier G) \<longrightarrow> |
14 finprod G g (UNION I A) = finprod G (\<lambda>i. finprod G g (A i)) I" |
16 finprod G g (UNION I A) = finprod G (%i. finprod G g (A i)) I" |
|
17 apply (induct set: finite) |
15 apply (induct set: finite) |
18 apply force |
16 apply force |
19 apply clarsimp |
17 apply clarsimp |
20 apply (subst finprod_Un_disjoint) |
18 apply (subst finprod_Un_disjoint) |
21 apply blast |
19 apply blast |
22 apply (erule finite_UN_I) |
20 apply (erule finite_UN_I) |
23 apply blast |
21 apply blast |
24 apply (fastforce) |
22 apply (fastforce) |
25 apply (auto intro!: funcsetI finprod_closed) |
23 apply (auto intro!: funcsetI finprod_closed) |
26 done |
24 done |
27 |
25 |
28 lemma (in comm_monoid) finprod_Union_disjoint: |
26 lemma (in comm_monoid) finprod_Union_disjoint: |
29 "[| finite C; (ALL A:C. finite A & (ALL x:A. f x : carrier G)); |
27 "finite C \<Longrightarrow> |
30 (ALL A:C. ALL B:C. A ~= B --> A Int B = {}) |] |
28 \<forall>A\<in>C. finite A \<and> (\<forall>x\<in>A. f x \<in> carrier G) \<Longrightarrow> |
31 ==> finprod G f (\<Union>C) = finprod G (finprod G f) C" |
29 \<forall>A\<in>C. \<forall>B\<in>C. A \<noteq> B \<longrightarrow> A \<inter> B = {} \<Longrightarrow> |
|
30 finprod G f (\<Union>C) = finprod G (finprod G f) C" |
32 apply (frule finprod_UN_disjoint [of C id f]) |
31 apply (frule finprod_UN_disjoint [of C id f]) |
33 apply auto |
32 apply auto |
34 done |
33 done |
35 |
34 |
36 lemma (in comm_monoid) finprod_one: |
35 lemma (in comm_monoid) finprod_one: "finite A \<Longrightarrow> (\<And>x. x \<in> A \<Longrightarrow> f x = \<one>) \<Longrightarrow> finprod G f A = \<one>" |
37 "finite A \<Longrightarrow> (\<And>x. x:A \<Longrightarrow> f x = \<one>) \<Longrightarrow> finprod G f A = \<one>" |
|
38 by (induct set: finite) auto |
36 by (induct set: finite) auto |
39 |
37 |
40 |
38 |
41 (* need better simplification rules for rings *) |
39 (* need better simplification rules for rings *) |
42 (* the next one holds more generally for abelian groups *) |
40 (* the next one holds more generally for abelian groups *) |
43 |
41 |
44 lemma (in cring) sum_zero_eq_neg: "x : carrier R \<Longrightarrow> y : carrier R \<Longrightarrow> x \<oplus> y = \<zero> \<Longrightarrow> x = \<ominus> y" |
42 lemma (in cring) sum_zero_eq_neg: "x \<in> carrier R \<Longrightarrow> y \<in> carrier R \<Longrightarrow> x \<oplus> y = \<zero> \<Longrightarrow> x = \<ominus> y" |
45 by (metis minus_equality) |
43 by (metis minus_equality) |
46 |
44 |
47 lemma (in domain) square_eq_one: |
45 lemma (in domain) square_eq_one: |
48 fixes x |
46 fixes x |
49 assumes [simp]: "x : carrier R" |
47 assumes [simp]: "x \<in> carrier R" |
50 and "x \<otimes> x = \<one>" |
48 and "x \<otimes> x = \<one>" |
51 shows "x = \<one> | x = \<ominus>\<one>" |
49 shows "x = \<one> \<or> x = \<ominus>\<one>" |
52 proof - |
50 proof - |
53 have "(x \<oplus> \<one>) \<otimes> (x \<oplus> \<ominus> \<one>) = x \<otimes> x \<oplus> \<ominus> \<one>" |
51 have "(x \<oplus> \<one>) \<otimes> (x \<oplus> \<ominus> \<one>) = x \<otimes> x \<oplus> \<ominus> \<one>" |
54 by (simp add: ring_simprules) |
52 by (simp add: ring_simprules) |
55 also from \<open>x \<otimes> x = \<one>\<close> have "\<dots> = \<zero>" |
53 also from \<open>x \<otimes> x = \<one>\<close> have "\<dots> = \<zero>" |
56 by (simp add: ring_simprules) |
54 by (simp add: ring_simprules) |
57 finally have "(x \<oplus> \<one>) \<otimes> (x \<oplus> \<ominus> \<one>) = \<zero>" . |
55 finally have "(x \<oplus> \<one>) \<otimes> (x \<oplus> \<ominus> \<one>) = \<zero>" . |
58 then have "(x \<oplus> \<one>) = \<zero> | (x \<oplus> \<ominus> \<one>) = \<zero>" |
56 then have "(x \<oplus> \<one>) = \<zero> \<or> (x \<oplus> \<ominus> \<one>) = \<zero>" |
59 by (intro integral, auto) |
57 by (intro integral) auto |
60 then show ?thesis |
58 then show ?thesis |
61 apply auto |
59 apply auto |
62 apply (erule notE) |
60 apply (erule notE) |
|
61 apply (rule sum_zero_eq_neg) |
|
62 apply auto |
|
63 apply (subgoal_tac "x = \<ominus> (\<ominus> \<one>)") |
|
64 apply (simp add: ring_simprules) |
63 apply (rule sum_zero_eq_neg) |
65 apply (rule sum_zero_eq_neg) |
64 apply auto |
66 apply auto |
65 apply (subgoal_tac "x = \<ominus> (\<ominus> \<one>)") |
|
66 apply (simp add: ring_simprules) |
|
67 apply (rule sum_zero_eq_neg) |
|
68 apply auto |
|
69 done |
67 done |
70 qed |
68 qed |
71 |
69 |
72 lemma (in Ring.domain) inv_eq_self: "x : Units R \<Longrightarrow> x = inv x \<Longrightarrow> x = \<one> \<or> x = \<ominus>\<one>" |
70 lemma (in domain) inv_eq_self: "x \<in> Units R \<Longrightarrow> x = inv x \<Longrightarrow> x = \<one> \<or> x = \<ominus>\<one>" |
73 by (metis Units_closed Units_l_inv square_eq_one) |
71 by (metis Units_closed Units_l_inv square_eq_one) |
74 |
72 |
75 |
73 |
76 text \<open> |
74 text \<open> |
77 The following translates theorems about groups to the facts about |
75 The following translates theorems about groups to the facts about |
88 apply (induct n) |
86 apply (induct n) |
89 apply (auto simp add: units_group group.is_monoid |
87 apply (auto simp add: units_group group.is_monoid |
90 monoid.nat_pow_0 monoid.nat_pow_Suc units_of_one units_of_mult) |
88 monoid.nat_pow_0 monoid.nat_pow_Suc units_of_one units_of_mult) |
91 done |
89 done |
92 |
90 |
93 lemma (in cring) units_power_order_eq_one: "finite (Units R) \<Longrightarrow> a : Units R |
91 lemma (in cring) units_power_order_eq_one: |
94 \<Longrightarrow> a (^) card(Units R) = \<one>" |
92 "finite (Units R) \<Longrightarrow> a \<in> Units R \<Longrightarrow> a (^) card(Units R) = \<one>" |
95 apply (subst units_of_carrier [symmetric]) |
93 apply (subst units_of_carrier [symmetric]) |
96 apply (subst units_of_one [symmetric]) |
94 apply (subst units_of_one [symmetric]) |
97 apply (subst units_of_pow [symmetric]) |
95 apply (subst units_of_pow [symmetric]) |
98 apply assumption |
96 apply assumption |
99 apply (rule comm_group.power_order_eq_one) |
97 apply (rule comm_group.power_order_eq_one) |
100 apply (rule units_comm_group) |
98 apply (rule units_comm_group) |
101 apply (unfold units_of_def, auto) |
99 apply (unfold units_of_def, auto) |
102 done |
100 done |
103 |
101 |
104 end |
102 end |