author | ballarin |
Wed, 04 Nov 2015 08:13:49 +0100 | |
changeset 61565 | 352c73a689da |
parent 61384 | 9f5145281888 |
child 61628 | 8dd2bd4fe30b |
permissions | -rw-r--r-- |
35849 | 1 |
(* Title: HOL/Algebra/Group.thy |
2 |
Author: Clemens Ballarin, started 4 February 2003 |
|
13813 | 3 |
|
4 |
Based on work by Florian Kammueller, L C Paulson and Markus Wenzel. |
|
5 |
*) |
|
6 |
||
28823 | 7 |
theory Group |
41413
64cd30d6b0b8
explicit file specifications -- avoid secondary load path;
wenzelm
parents:
35850
diff
changeset
|
8 |
imports Lattice "~~/src/HOL/Library/FuncSet" |
28823 | 9 |
begin |
13813 | 10 |
|
61382 | 11 |
section \<open>Monoids and Groups\<close> |
13936 | 12 |
|
61382 | 13 |
subsection \<open>Definitions\<close> |
20318
0e0ea63fe768
Restructured algebra library, added ideals and quotient rings.
ballarin
parents:
19984
diff
changeset
|
14 |
|
61382 | 15 |
text \<open> |
58622 | 16 |
Definitions follow @{cite "Jacobson:1985"}. |
61382 | 17 |
\<close> |
13813 | 18 |
|
14963 | 19 |
record 'a monoid = "'a partial_object" + |
20 |
mult :: "['a, 'a] \<Rightarrow> 'a" (infixl "\<otimes>\<index>" 70) |
|
21 |
one :: 'a ("\<one>\<index>") |
|
13817 | 22 |
|
35847 | 23 |
definition |
14852 | 24 |
m_inv :: "('a, 'b) monoid_scheme => 'a => 'a" ("inv\<index> _" [81] 80) |
35848
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
25 |
where "inv\<^bsub>G\<^esub> x = (THE y. y \<in> carrier G & x \<otimes>\<^bsub>G\<^esub> y = \<one>\<^bsub>G\<^esub> & y \<otimes>\<^bsub>G\<^esub> x = \<one>\<^bsub>G\<^esub>)" |
13936 | 26 |
|
35847 | 27 |
definition |
14651 | 28 |
Units :: "_ => 'a set" |
61382 | 29 |
--\<open>The set of invertible elements\<close> |
35848
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
30 |
where "Units G = {y. y \<in> carrier G & (\<exists>x \<in> carrier G. x \<otimes>\<^bsub>G\<^esub> y = \<one>\<^bsub>G\<^esub> & y \<otimes>\<^bsub>G\<^esub> x = \<one>\<^bsub>G\<^esub>)}" |
13936 | 31 |
|
32 |
consts |
|
47108
2a1953f0d20d
merged fork with new numeral representation (see NEWS)
huffman
parents:
46559
diff
changeset
|
33 |
pow :: "[('a, 'm) monoid_scheme, 'a, 'b::semiring_1] => 'a" (infixr "'(^')\<index>" 75) |
35850 | 34 |
|
35 |
overloading nat_pow == "pow :: [_, 'a, nat] => 'a" |
|
36 |
begin |
|
55415 | 37 |
definition "nat_pow G a n = rec_nat \<one>\<^bsub>G\<^esub> (%u b. b \<otimes>\<^bsub>G\<^esub> a) n" |
35850 | 38 |
end |
13936 | 39 |
|
35850 | 40 |
overloading int_pow == "pow :: [_, 'a, int] => 'a" |
41 |
begin |
|
42 |
definition "int_pow G a z = |
|
55415 | 43 |
(let p = rec_nat \<one>\<^bsub>G\<^esub> (%u b. b \<otimes>\<^bsub>G\<^esub> a) |
46559 | 44 |
in if z < 0 then inv\<^bsub>G\<^esub> (p (nat (-z))) else p (nat z))" |
35850 | 45 |
end |
13813 | 46 |
|
19783 | 47 |
locale monoid = |
48 |
fixes G (structure) |
|
13813 | 49 |
assumes m_closed [intro, simp]: |
14963 | 50 |
"\<lbrakk>x \<in> carrier G; y \<in> carrier G\<rbrakk> \<Longrightarrow> x \<otimes> y \<in> carrier G" |
51 |
and m_assoc: |
|
52 |
"\<lbrakk>x \<in> carrier G; y \<in> carrier G; z \<in> carrier G\<rbrakk> |
|
53 |
\<Longrightarrow> (x \<otimes> y) \<otimes> z = x \<otimes> (y \<otimes> z)" |
|
54 |
and one_closed [intro, simp]: "\<one> \<in> carrier G" |
|
55 |
and l_one [simp]: "x \<in> carrier G \<Longrightarrow> \<one> \<otimes> x = x" |
|
56 |
and r_one [simp]: "x \<in> carrier G \<Longrightarrow> x \<otimes> \<one> = x" |
|
13817 | 57 |
|
13936 | 58 |
lemma monoidI: |
19783 | 59 |
fixes G (structure) |
13936 | 60 |
assumes m_closed: |
14693 | 61 |
"!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> x \<otimes> y \<in> carrier G" |
62 |
and one_closed: "\<one> \<in> carrier G" |
|
13936 | 63 |
and m_assoc: |
64 |
"!!x y z. [| x \<in> carrier G; y \<in> carrier G; z \<in> carrier G |] ==> |
|
14693 | 65 |
(x \<otimes> y) \<otimes> z = x \<otimes> (y \<otimes> z)" |
66 |
and l_one: "!!x. x \<in> carrier G ==> \<one> \<otimes> x = x" |
|
67 |
and r_one: "!!x. x \<in> carrier G ==> x \<otimes> \<one> = x" |
|
13936 | 68 |
shows "monoid G" |
27714
27b4d7c01f8b
Tuned (for the sake of a meaningless log entry).
ballarin
parents:
27713
diff
changeset
|
69 |
by (fast intro!: monoid.intro intro: assms) |
13936 | 70 |
|
71 |
lemma (in monoid) Units_closed [dest]: |
|
72 |
"x \<in> Units G ==> x \<in> carrier G" |
|
73 |
by (unfold Units_def) fast |
|
74 |
||
75 |
lemma (in monoid) inv_unique: |
|
14693 | 76 |
assumes eq: "y \<otimes> x = \<one>" "x \<otimes> y' = \<one>" |
77 |
and G: "x \<in> carrier G" "y \<in> carrier G" "y' \<in> carrier G" |
|
13936 | 78 |
shows "y = y'" |
79 |
proof - |
|
80 |
from G eq have "y = y \<otimes> (x \<otimes> y')" by simp |
|
81 |
also from G have "... = (y \<otimes> x) \<otimes> y'" by (simp add: m_assoc) |
|
82 |
also from G eq have "... = y'" by simp |
|
83 |
finally show ?thesis . |
|
84 |
qed |
|
85 |
||
27698 | 86 |
lemma (in monoid) Units_m_closed [intro, simp]: |
87 |
assumes x: "x \<in> Units G" and y: "y \<in> Units G" |
|
88 |
shows "x \<otimes> y \<in> Units G" |
|
89 |
proof - |
|
90 |
from x obtain x' where x: "x \<in> carrier G" "x' \<in> carrier G" and xinv: "x \<otimes> x' = \<one>" "x' \<otimes> x = \<one>" |
|
91 |
unfolding Units_def by fast |
|
92 |
from y obtain y' where y: "y \<in> carrier G" "y' \<in> carrier G" and yinv: "y \<otimes> y' = \<one>" "y' \<otimes> y = \<one>" |
|
93 |
unfolding Units_def by fast |
|
94 |
from x y xinv yinv have "y' \<otimes> (x' \<otimes> x) \<otimes> y = \<one>" by simp |
|
95 |
moreover from x y xinv yinv have "x \<otimes> (y \<otimes> y') \<otimes> x' = \<one>" by simp |
|
96 |
moreover note x y |
|
97 |
ultimately show ?thesis unfolding Units_def |
|
98 |
-- "Must avoid premature use of @{text hyp_subst_tac}." |
|
99 |
apply (rule_tac CollectI) |
|
100 |
apply (rule) |
|
101 |
apply (fast) |
|
102 |
apply (rule bexI [where x = "y' \<otimes> x'"]) |
|
103 |
apply (auto simp: m_assoc) |
|
104 |
done |
|
105 |
qed |
|
106 |
||
13940 | 107 |
lemma (in monoid) Units_one_closed [intro, simp]: |
108 |
"\<one> \<in> Units G" |
|
109 |
by (unfold Units_def) auto |
|
110 |
||
13936 | 111 |
lemma (in monoid) Units_inv_closed [intro, simp]: |
112 |
"x \<in> Units G ==> inv x \<in> carrier G" |
|
13943 | 113 |
apply (unfold Units_def m_inv_def, auto) |
13936 | 114 |
apply (rule theI2, fast) |
13943 | 115 |
apply (fast intro: inv_unique, fast) |
13936 | 116 |
done |
117 |
||
19981 | 118 |
lemma (in monoid) Units_l_inv_ex: |
119 |
"x \<in> Units G ==> \<exists>y \<in> carrier G. y \<otimes> x = \<one>" |
|
120 |
by (unfold Units_def) auto |
|
121 |
||
122 |
lemma (in monoid) Units_r_inv_ex: |
|
123 |
"x \<in> Units G ==> \<exists>y \<in> carrier G. x \<otimes> y = \<one>" |
|
124 |
by (unfold Units_def) auto |
|
125 |
||
27698 | 126 |
lemma (in monoid) Units_l_inv [simp]: |
13936 | 127 |
"x \<in> Units G ==> inv x \<otimes> x = \<one>" |
13943 | 128 |
apply (unfold Units_def m_inv_def, auto) |
13936 | 129 |
apply (rule theI2, fast) |
13943 | 130 |
apply (fast intro: inv_unique, fast) |
13936 | 131 |
done |
132 |
||
27698 | 133 |
lemma (in monoid) Units_r_inv [simp]: |
13936 | 134 |
"x \<in> Units G ==> x \<otimes> inv x = \<one>" |
13943 | 135 |
apply (unfold Units_def m_inv_def, auto) |
13936 | 136 |
apply (rule theI2, fast) |
13943 | 137 |
apply (fast intro: inv_unique, fast) |
13936 | 138 |
done |
139 |
||
140 |
lemma (in monoid) Units_inv_Units [intro, simp]: |
|
141 |
"x \<in> Units G ==> inv x \<in> Units G" |
|
142 |
proof - |
|
143 |
assume x: "x \<in> Units G" |
|
144 |
show "inv x \<in> Units G" |
|
145 |
by (auto simp add: Units_def |
|
146 |
intro: Units_l_inv Units_r_inv x Units_closed [OF x]) |
|
147 |
qed |
|
148 |
||
149 |
lemma (in monoid) Units_l_cancel [simp]: |
|
150 |
"[| x \<in> Units G; y \<in> carrier G; z \<in> carrier G |] ==> |
|
151 |
(x \<otimes> y = x \<otimes> z) = (y = z)" |
|
152 |
proof |
|
153 |
assume eq: "x \<otimes> y = x \<otimes> z" |
|
14693 | 154 |
and G: "x \<in> Units G" "y \<in> carrier G" "z \<in> carrier G" |
13936 | 155 |
then have "(inv x \<otimes> x) \<otimes> y = (inv x \<otimes> x) \<otimes> z" |
27698 | 156 |
by (simp add: m_assoc Units_closed del: Units_l_inv) |
44472 | 157 |
with G show "y = z" by simp |
13936 | 158 |
next |
159 |
assume eq: "y = z" |
|
14693 | 160 |
and G: "x \<in> Units G" "y \<in> carrier G" "z \<in> carrier G" |
13936 | 161 |
then show "x \<otimes> y = x \<otimes> z" by simp |
162 |
qed |
|
163 |
||
164 |
lemma (in monoid) Units_inv_inv [simp]: |
|
165 |
"x \<in> Units G ==> inv (inv x) = x" |
|
166 |
proof - |
|
167 |
assume x: "x \<in> Units G" |
|
27698 | 168 |
then have "inv x \<otimes> inv (inv x) = inv x \<otimes> x" by simp |
169 |
with x show ?thesis by (simp add: Units_closed del: Units_l_inv Units_r_inv) |
|
13936 | 170 |
qed |
171 |
||
172 |
lemma (in monoid) inv_inj_on_Units: |
|
173 |
"inj_on (m_inv G) (Units G)" |
|
174 |
proof (rule inj_onI) |
|
175 |
fix x y |
|
14693 | 176 |
assume G: "x \<in> Units G" "y \<in> Units G" and eq: "inv x = inv y" |
13936 | 177 |
then have "inv (inv x) = inv (inv y)" by simp |
178 |
with G show "x = y" by simp |
|
179 |
qed |
|
180 |
||
13940 | 181 |
lemma (in monoid) Units_inv_comm: |
182 |
assumes inv: "x \<otimes> y = \<one>" |
|
14693 | 183 |
and G: "x \<in> Units G" "y \<in> Units G" |
13940 | 184 |
shows "y \<otimes> x = \<one>" |
185 |
proof - |
|
186 |
from G have "x \<otimes> y \<otimes> x = x \<otimes> \<one>" by (auto simp add: inv Units_closed) |
|
187 |
with G show ?thesis by (simp del: r_one add: m_assoc Units_closed) |
|
188 |
qed |
|
189 |
||
61382 | 190 |
text \<open>Power\<close> |
13936 | 191 |
|
192 |
lemma (in monoid) nat_pow_closed [intro, simp]: |
|
193 |
"x \<in> carrier G ==> x (^) (n::nat) \<in> carrier G" |
|
194 |
by (induct n) (simp_all add: nat_pow_def) |
|
195 |
||
196 |
lemma (in monoid) nat_pow_0 [simp]: |
|
197 |
"x (^) (0::nat) = \<one>" |
|
198 |
by (simp add: nat_pow_def) |
|
199 |
||
200 |
lemma (in monoid) nat_pow_Suc [simp]: |
|
201 |
"x (^) (Suc n) = x (^) n \<otimes> x" |
|
202 |
by (simp add: nat_pow_def) |
|
203 |
||
204 |
lemma (in monoid) nat_pow_one [simp]: |
|
205 |
"\<one> (^) (n::nat) = \<one>" |
|
206 |
by (induct n) simp_all |
|
207 |
||
208 |
lemma (in monoid) nat_pow_mult: |
|
209 |
"x \<in> carrier G ==> x (^) (n::nat) \<otimes> x (^) m = x (^) (n + m)" |
|
210 |
by (induct m) (simp_all add: m_assoc [THEN sym]) |
|
211 |
||
212 |
lemma (in monoid) nat_pow_pow: |
|
213 |
"x \<in> carrier G ==> (x (^) n) (^) m = x (^) (n * m::nat)" |
|
57512
cc97b347b301
reduced name variants for assoc and commute on plus and mult
haftmann
parents:
57271
diff
changeset
|
214 |
by (induct m) (simp, simp add: nat_pow_mult add.commute) |
13936 | 215 |
|
27698 | 216 |
|
217 |
(* Jacobson defines submonoid here. *) |
|
218 |
(* Jacobson defines the order of a monoid here. *) |
|
219 |
||
220 |
||
61382 | 221 |
subsection \<open>Groups\<close> |
27698 | 222 |
|
61382 | 223 |
text \<open> |
13936 | 224 |
A group is a monoid all of whose elements are invertible. |
61382 | 225 |
\<close> |
13936 | 226 |
|
227 |
locale group = monoid + |
|
228 |
assumes Units: "carrier G <= Units G" |
|
229 |
||
26199 | 230 |
lemma (in group) is_group: "group G" by (rule group_axioms) |
14761 | 231 |
|
13936 | 232 |
theorem groupI: |
19783 | 233 |
fixes G (structure) |
13936 | 234 |
assumes m_closed [simp]: |
14693 | 235 |
"!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> x \<otimes> y \<in> carrier G" |
236 |
and one_closed [simp]: "\<one> \<in> carrier G" |
|
13936 | 237 |
and m_assoc: |
238 |
"!!x y z. [| x \<in> carrier G; y \<in> carrier G; z \<in> carrier G |] ==> |
|
14693 | 239 |
(x \<otimes> y) \<otimes> z = x \<otimes> (y \<otimes> z)" |
240 |
and l_one [simp]: "!!x. x \<in> carrier G ==> \<one> \<otimes> x = x" |
|
14963 | 241 |
and l_inv_ex: "!!x. x \<in> carrier G ==> \<exists>y \<in> carrier G. y \<otimes> x = \<one>" |
13936 | 242 |
shows "group G" |
243 |
proof - |
|
244 |
have l_cancel [simp]: |
|
245 |
"!!x y z. [| x \<in> carrier G; y \<in> carrier G; z \<in> carrier G |] ==> |
|
14693 | 246 |
(x \<otimes> y = x \<otimes> z) = (y = z)" |
13936 | 247 |
proof |
248 |
fix x y z |
|
14693 | 249 |
assume eq: "x \<otimes> y = x \<otimes> z" |
250 |
and G: "x \<in> carrier G" "y \<in> carrier G" "z \<in> carrier G" |
|
13936 | 251 |
with l_inv_ex obtain x_inv where xG: "x_inv \<in> carrier G" |
14693 | 252 |
and l_inv: "x_inv \<otimes> x = \<one>" by fast |
253 |
from G eq xG have "(x_inv \<otimes> x) \<otimes> y = (x_inv \<otimes> x) \<otimes> z" |
|
13936 | 254 |
by (simp add: m_assoc) |
255 |
with G show "y = z" by (simp add: l_inv) |
|
256 |
next |
|
257 |
fix x y z |
|
258 |
assume eq: "y = z" |
|
14693 | 259 |
and G: "x \<in> carrier G" "y \<in> carrier G" "z \<in> carrier G" |
260 |
then show "x \<otimes> y = x \<otimes> z" by simp |
|
13936 | 261 |
qed |
262 |
have r_one: |
|
14693 | 263 |
"!!x. x \<in> carrier G ==> x \<otimes> \<one> = x" |
13936 | 264 |
proof - |
265 |
fix x |
|
266 |
assume x: "x \<in> carrier G" |
|
267 |
with l_inv_ex obtain x_inv where xG: "x_inv \<in> carrier G" |
|
14693 | 268 |
and l_inv: "x_inv \<otimes> x = \<one>" by fast |
269 |
from x xG have "x_inv \<otimes> (x \<otimes> \<one>) = x_inv \<otimes> x" |
|
13936 | 270 |
by (simp add: m_assoc [symmetric] l_inv) |
14693 | 271 |
with x xG show "x \<otimes> \<one> = x" by simp |
13936 | 272 |
qed |
273 |
have inv_ex: |
|
14963 | 274 |
"!!x. x \<in> carrier G ==> \<exists>y \<in> carrier G. y \<otimes> x = \<one> & x \<otimes> y = \<one>" |
13936 | 275 |
proof - |
276 |
fix x |
|
277 |
assume x: "x \<in> carrier G" |
|
278 |
with l_inv_ex obtain y where y: "y \<in> carrier G" |
|
14693 | 279 |
and l_inv: "y \<otimes> x = \<one>" by fast |
280 |
from x y have "y \<otimes> (x \<otimes> y) = y \<otimes> \<one>" |
|
13936 | 281 |
by (simp add: m_assoc [symmetric] l_inv r_one) |
14693 | 282 |
with x y have r_inv: "x \<otimes> y = \<one>" |
13936 | 283 |
by simp |
14963 | 284 |
from x y show "\<exists>y \<in> carrier G. y \<otimes> x = \<one> & x \<otimes> y = \<one>" |
13936 | 285 |
by (fast intro: l_inv r_inv) |
286 |
qed |
|
287 |
then have carrier_subset_Units: "carrier G <= Units G" |
|
288 |
by (unfold Units_def) fast |
|
61169 | 289 |
show ?thesis |
290 |
by standard (auto simp: r_one m_assoc carrier_subset_Units) |
|
13936 | 291 |
qed |
292 |
||
27698 | 293 |
lemma (in monoid) group_l_invI: |
13936 | 294 |
assumes l_inv_ex: |
14963 | 295 |
"!!x. x \<in> carrier G ==> \<exists>y \<in> carrier G. y \<otimes> x = \<one>" |
13936 | 296 |
shows "group G" |
297 |
by (rule groupI) (auto intro: m_assoc l_inv_ex) |
|
298 |
||
299 |
lemma (in group) Units_eq [simp]: |
|
300 |
"Units G = carrier G" |
|
301 |
proof |
|
302 |
show "Units G <= carrier G" by fast |
|
303 |
next |
|
304 |
show "carrier G <= Units G" by (rule Units) |
|
305 |
qed |
|
306 |
||
307 |
lemma (in group) inv_closed [intro, simp]: |
|
308 |
"x \<in> carrier G ==> inv x \<in> carrier G" |
|
309 |
using Units_inv_closed by simp |
|
310 |
||
19981 | 311 |
lemma (in group) l_inv_ex [simp]: |
312 |
"x \<in> carrier G ==> \<exists>y \<in> carrier G. y \<otimes> x = \<one>" |
|
313 |
using Units_l_inv_ex by simp |
|
314 |
||
315 |
lemma (in group) r_inv_ex [simp]: |
|
316 |
"x \<in> carrier G ==> \<exists>y \<in> carrier G. x \<otimes> y = \<one>" |
|
317 |
using Units_r_inv_ex by simp |
|
318 |
||
14963 | 319 |
lemma (in group) l_inv [simp]: |
13936 | 320 |
"x \<in> carrier G ==> inv x \<otimes> x = \<one>" |
321 |
using Units_l_inv by simp |
|
13813 | 322 |
|
20318
0e0ea63fe768
Restructured algebra library, added ideals and quotient rings.
ballarin
parents:
19984
diff
changeset
|
323 |
|
61382 | 324 |
subsection \<open>Cancellation Laws and Basic Properties\<close> |
13813 | 325 |
|
326 |
lemma (in group) l_cancel [simp]: |
|
327 |
"[| x \<in> carrier G; y \<in> carrier G; z \<in> carrier G |] ==> |
|
328 |
(x \<otimes> y = x \<otimes> z) = (y = z)" |
|
13936 | 329 |
using Units_l_inv by simp |
13940 | 330 |
|
14963 | 331 |
lemma (in group) r_inv [simp]: |
13813 | 332 |
"x \<in> carrier G ==> x \<otimes> inv x = \<one>" |
333 |
proof - |
|
334 |
assume x: "x \<in> carrier G" |
|
335 |
then have "inv x \<otimes> (x \<otimes> inv x) = inv x \<otimes> \<one>" |
|
44472 | 336 |
by (simp add: m_assoc [symmetric]) |
13813 | 337 |
with x show ?thesis by (simp del: r_one) |
338 |
qed |
|
339 |
||
340 |
lemma (in group) r_cancel [simp]: |
|
341 |
"[| x \<in> carrier G; y \<in> carrier G; z \<in> carrier G |] ==> |
|
342 |
(y \<otimes> x = z \<otimes> x) = (y = z)" |
|
343 |
proof |
|
344 |
assume eq: "y \<otimes> x = z \<otimes> x" |
|
14693 | 345 |
and G: "x \<in> carrier G" "y \<in> carrier G" "z \<in> carrier G" |
13813 | 346 |
then have "y \<otimes> (x \<otimes> inv x) = z \<otimes> (x \<otimes> inv x)" |
27698 | 347 |
by (simp add: m_assoc [symmetric] del: r_inv Units_r_inv) |
14963 | 348 |
with G show "y = z" by simp |
13813 | 349 |
next |
350 |
assume eq: "y = z" |
|
14693 | 351 |
and G: "x \<in> carrier G" "y \<in> carrier G" "z \<in> carrier G" |
13813 | 352 |
then show "y \<otimes> x = z \<otimes> x" by simp |
353 |
qed |
|
354 |
||
13854
91c9ab25fece
First distributed version of Group and Ring theory.
ballarin
parents:
13835
diff
changeset
|
355 |
lemma (in group) inv_one [simp]: |
91c9ab25fece
First distributed version of Group and Ring theory.
ballarin
parents:
13835
diff
changeset
|
356 |
"inv \<one> = \<one>" |
91c9ab25fece
First distributed version of Group and Ring theory.
ballarin
parents:
13835
diff
changeset
|
357 |
proof - |
27698 | 358 |
have "inv \<one> = \<one> \<otimes> (inv \<one>)" by (simp del: r_inv Units_r_inv) |
14963 | 359 |
moreover have "... = \<one>" by simp |
13854
91c9ab25fece
First distributed version of Group and Ring theory.
ballarin
parents:
13835
diff
changeset
|
360 |
finally show ?thesis . |
91c9ab25fece
First distributed version of Group and Ring theory.
ballarin
parents:
13835
diff
changeset
|
361 |
qed |
91c9ab25fece
First distributed version of Group and Ring theory.
ballarin
parents:
13835
diff
changeset
|
362 |
|
13813 | 363 |
lemma (in group) inv_inv [simp]: |
364 |
"x \<in> carrier G ==> inv (inv x) = x" |
|
13936 | 365 |
using Units_inv_inv by simp |
366 |
||
367 |
lemma (in group) inv_inj: |
|
368 |
"inj_on (m_inv G) (carrier G)" |
|
369 |
using inv_inj_on_Units by simp |
|
13813 | 370 |
|
13854
91c9ab25fece
First distributed version of Group and Ring theory.
ballarin
parents:
13835
diff
changeset
|
371 |
lemma (in group) inv_mult_group: |
13813 | 372 |
"[| x \<in> carrier G; y \<in> carrier G |] ==> inv (x \<otimes> y) = inv y \<otimes> inv x" |
373 |
proof - |
|
14693 | 374 |
assume G: "x \<in> carrier G" "y \<in> carrier G" |
13813 | 375 |
then have "inv (x \<otimes> y) \<otimes> (x \<otimes> y) = (inv y \<otimes> inv x) \<otimes> (x \<otimes> y)" |
44472 | 376 |
by (simp add: m_assoc) (simp add: m_assoc [symmetric]) |
27698 | 377 |
with G show ?thesis by (simp del: l_inv Units_l_inv) |
13813 | 378 |
qed |
379 |
||
13940 | 380 |
lemma (in group) inv_comm: |
381 |
"[| x \<otimes> y = \<one>; x \<in> carrier G; y \<in> carrier G |] ==> y \<otimes> x = \<one>" |
|
14693 | 382 |
by (rule Units_inv_comm) auto |
13940 | 383 |
|
13944 | 384 |
lemma (in group) inv_equality: |
13943 | 385 |
"[|y \<otimes> x = \<one>; x \<in> carrier G; y \<in> carrier G|] ==> inv x = y" |
386 |
apply (simp add: m_inv_def) |
|
387 |
apply (rule the_equality) |
|
14693 | 388 |
apply (simp add: inv_comm [of y x]) |
389 |
apply (rule r_cancel [THEN iffD1], auto) |
|
13943 | 390 |
done |
391 |
||
57271 | 392 |
(* Contributed by Joachim Breitner *) |
393 |
lemma (in group) inv_solve_left: |
|
394 |
"\<lbrakk> a \<in> carrier G; b \<in> carrier G; c \<in> carrier G \<rbrakk> \<Longrightarrow> a = inv b \<otimes> c \<longleftrightarrow> c = b \<otimes> a" |
|
395 |
by (metis inv_equality l_inv_ex l_one m_assoc r_inv) |
|
396 |
lemma (in group) inv_solve_right: |
|
397 |
"\<lbrakk> a \<in> carrier G; b \<in> carrier G; c \<in> carrier G \<rbrakk> \<Longrightarrow> a = b \<otimes> inv c \<longleftrightarrow> b = a \<otimes> c" |
|
398 |
by (metis inv_equality l_inv_ex l_one m_assoc r_inv) |
|
399 |
||
61382 | 400 |
text \<open>Power\<close> |
13936 | 401 |
|
402 |
lemma (in group) int_pow_def2: |
|
46559 | 403 |
"a (^) (z::int) = (if z < 0 then inv (a (^) (nat (-z))) else a (^) (nat z))" |
13936 | 404 |
by (simp add: int_pow_def nat_pow_def Let_def) |
405 |
||
406 |
lemma (in group) int_pow_0 [simp]: |
|
407 |
"x (^) (0::int) = \<one>" |
|
408 |
by (simp add: int_pow_def2) |
|
409 |
||
410 |
lemma (in group) int_pow_one [simp]: |
|
411 |
"\<one> (^) (z::int) = \<one>" |
|
412 |
by (simp add: int_pow_def2) |
|
413 |
||
57271 | 414 |
(* The following are contributed by Joachim Breitner *) |
20318
0e0ea63fe768
Restructured algebra library, added ideals and quotient rings.
ballarin
parents:
19984
diff
changeset
|
415 |
|
57271 | 416 |
lemma (in group) int_pow_closed [intro, simp]: |
417 |
"x \<in> carrier G ==> x (^) (i::int) \<in> carrier G" |
|
418 |
by (simp add: int_pow_def2) |
|
419 |
||
420 |
lemma (in group) int_pow_1 [simp]: |
|
421 |
"x \<in> carrier G \<Longrightarrow> x (^) (1::int) = x" |
|
422 |
by (simp add: int_pow_def2) |
|
423 |
||
424 |
lemma (in group) int_pow_neg: |
|
425 |
"x \<in> carrier G \<Longrightarrow> x (^) (-i::int) = inv (x (^) i)" |
|
426 |
by (simp add: int_pow_def2) |
|
427 |
||
428 |
lemma (in group) int_pow_mult: |
|
429 |
"x \<in> carrier G \<Longrightarrow> x (^) (i + j::int) = x (^) i \<otimes> x (^) j" |
|
430 |
proof - |
|
431 |
have [simp]: "-i - j = -j - i" by simp |
|
432 |
assume "x : carrier G" then |
|
433 |
show ?thesis |
|
434 |
by (auto simp add: int_pow_def2 inv_solve_left inv_solve_right nat_add_distrib [symmetric] nat_pow_mult ) |
|
435 |
qed |
|
436 |
||
437 |
||
61382 | 438 |
subsection \<open>Subgroups\<close> |
13813 | 439 |
|
19783 | 440 |
locale subgroup = |
441 |
fixes H and G (structure) |
|
14963 | 442 |
assumes subset: "H \<subseteq> carrier G" |
443 |
and m_closed [intro, simp]: "\<lbrakk>x \<in> H; y \<in> H\<rbrakk> \<Longrightarrow> x \<otimes> y \<in> H" |
|
20318
0e0ea63fe768
Restructured algebra library, added ideals and quotient rings.
ballarin
parents:
19984
diff
changeset
|
444 |
and one_closed [simp]: "\<one> \<in> H" |
14963 | 445 |
and m_inv_closed [intro,simp]: "x \<in> H \<Longrightarrow> inv x \<in> H" |
13813 | 446 |
|
20318
0e0ea63fe768
Restructured algebra library, added ideals and quotient rings.
ballarin
parents:
19984
diff
changeset
|
447 |
lemma (in subgroup) is_subgroup: |
26199 | 448 |
"subgroup H G" by (rule subgroup_axioms) |
20318
0e0ea63fe768
Restructured algebra library, added ideals and quotient rings.
ballarin
parents:
19984
diff
changeset
|
449 |
|
13813 | 450 |
declare (in subgroup) group.intro [intro] |
13949
0ce528cd6f19
HOL-Algebra complete for release Isabelle2003 (modulo section headers).
ballarin
parents:
13944
diff
changeset
|
451 |
|
14963 | 452 |
lemma (in subgroup) mem_carrier [simp]: |
453 |
"x \<in> H \<Longrightarrow> x \<in> carrier G" |
|
454 |
using subset by blast |
|
13813 | 455 |
|
14963 | 456 |
lemma subgroup_imp_subset: |
457 |
"subgroup H G \<Longrightarrow> H \<subseteq> carrier G" |
|
458 |
by (rule subgroup.subset) |
|
459 |
||
460 |
lemma (in subgroup) subgroup_is_group [intro]: |
|
27611 | 461 |
assumes "group G" |
462 |
shows "group (G\<lparr>carrier := H\<rparr>)" |
|
463 |
proof - |
|
29237 | 464 |
interpret group G by fact |
27611 | 465 |
show ?thesis |
27698 | 466 |
apply (rule monoid.group_l_invI) |
467 |
apply (unfold_locales) [1] |
|
468 |
apply (auto intro: m_assoc l_inv mem_carrier) |
|
469 |
done |
|
27611 | 470 |
qed |
13813 | 471 |
|
61382 | 472 |
text \<open> |
13813 | 473 |
Since @{term H} is nonempty, it contains some element @{term x}. Since |
474 |
it is closed under inverse, it contains @{text "inv x"}. Since |
|
475 |
it is closed under product, it contains @{text "x \<otimes> inv x = \<one>"}. |
|
61382 | 476 |
\<close> |
13813 | 477 |
|
478 |
lemma (in group) one_in_subset: |
|
479 |
"[| H \<subseteq> carrier G; H \<noteq> {}; \<forall>a \<in> H. inv a \<in> H; \<forall>a\<in>H. \<forall>b\<in>H. a \<otimes> b \<in> H |] |
|
480 |
==> \<one> \<in> H" |
|
44472 | 481 |
by force |
13813 | 482 |
|
61382 | 483 |
text \<open>A characterization of subgroups: closed, non-empty subset.\<close> |
13813 | 484 |
|
485 |
lemma (in group) subgroupI: |
|
486 |
assumes subset: "H \<subseteq> carrier G" and non_empty: "H \<noteq> {}" |
|
14963 | 487 |
and inv: "!!a. a \<in> H \<Longrightarrow> inv a \<in> H" |
488 |
and mult: "!!a b. \<lbrakk>a \<in> H; b \<in> H\<rbrakk> \<Longrightarrow> a \<otimes> b \<in> H" |
|
13813 | 489 |
shows "subgroup H G" |
27714
27b4d7c01f8b
Tuned (for the sake of a meaningless log entry).
ballarin
parents:
27713
diff
changeset
|
490 |
proof (simp add: subgroup_def assms) |
27b4d7c01f8b
Tuned (for the sake of a meaningless log entry).
ballarin
parents:
27713
diff
changeset
|
491 |
show "\<one> \<in> H" by (rule one_in_subset) (auto simp only: assms) |
13813 | 492 |
qed |
493 |
||
13936 | 494 |
declare monoid.one_closed [iff] group.inv_closed [simp] |
495 |
monoid.l_one [simp] monoid.r_one [simp] group.inv_inv [simp] |
|
13813 | 496 |
|
497 |
lemma subgroup_nonempty: |
|
498 |
"~ subgroup {} G" |
|
499 |
by (blast dest: subgroup.one_closed) |
|
500 |
||
501 |
lemma (in subgroup) finite_imp_card_positive: |
|
502 |
"finite (carrier G) ==> 0 < card H" |
|
503 |
proof (rule classical) |
|
41528 | 504 |
assume "finite (carrier G)" and a: "~ 0 < card H" |
14963 | 505 |
then have "finite H" by (blast intro: finite_subset [OF subset]) |
41528 | 506 |
with is_subgroup a have "subgroup {} G" by simp |
13813 | 507 |
with subgroup_nonempty show ?thesis by contradiction |
508 |
qed |
|
509 |
||
13936 | 510 |
(* |
511 |
lemma (in monoid) Units_subgroup: |
|
512 |
"subgroup (Units G) G" |
|
513 |
*) |
|
514 |
||
20318
0e0ea63fe768
Restructured algebra library, added ideals and quotient rings.
ballarin
parents:
19984
diff
changeset
|
515 |
|
61382 | 516 |
subsection \<open>Direct Products\<close> |
13813 | 517 |
|
35848
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
518 |
definition |
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
519 |
DirProd :: "_ \<Rightarrow> _ \<Rightarrow> ('a \<times> 'b) monoid" (infixr "\<times>\<times>" 80) where |
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
520 |
"G \<times>\<times> H = |
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
521 |
\<lparr>carrier = carrier G \<times> carrier H, |
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
522 |
mult = (\<lambda>(g, h) (g', h'). (g \<otimes>\<^bsub>G\<^esub> g', h \<otimes>\<^bsub>H\<^esub> h')), |
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
523 |
one = (\<one>\<^bsub>G\<^esub>, \<one>\<^bsub>H\<^esub>)\<rparr>" |
13813 | 524 |
|
14963 | 525 |
lemma DirProd_monoid: |
27611 | 526 |
assumes "monoid G" and "monoid H" |
14963 | 527 |
shows "monoid (G \<times>\<times> H)" |
528 |
proof - |
|
30729
461ee3e49ad3
interpretation/interpret: prefixes are mandatory by default;
wenzelm
parents:
29240
diff
changeset
|
529 |
interpret G: monoid G by fact |
461ee3e49ad3
interpretation/interpret: prefixes are mandatory by default;
wenzelm
parents:
29240
diff
changeset
|
530 |
interpret H: monoid H by fact |
27714
27b4d7c01f8b
Tuned (for the sake of a meaningless log entry).
ballarin
parents:
27713
diff
changeset
|
531 |
from assms |
14963 | 532 |
show ?thesis by (unfold monoid_def DirProd_def, auto) |
533 |
qed |
|
13813 | 534 |
|
535 |
||
61382 | 536 |
text\<open>Does not use the previous result because it's easier just to use auto.\<close> |
14963 | 537 |
lemma DirProd_group: |
27611 | 538 |
assumes "group G" and "group H" |
14963 | 539 |
shows "group (G \<times>\<times> H)" |
27611 | 540 |
proof - |
30729
461ee3e49ad3
interpretation/interpret: prefixes are mandatory by default;
wenzelm
parents:
29240
diff
changeset
|
541 |
interpret G: group G by fact |
461ee3e49ad3
interpretation/interpret: prefixes are mandatory by default;
wenzelm
parents:
29240
diff
changeset
|
542 |
interpret H: group H by fact |
27611 | 543 |
show ?thesis by (rule groupI) |
14963 | 544 |
(auto intro: G.m_assoc H.m_assoc G.l_inv H.l_inv |
545 |
simp add: DirProd_def) |
|
27611 | 546 |
qed |
13813 | 547 |
|
14963 | 548 |
lemma carrier_DirProd [simp]: |
549 |
"carrier (G \<times>\<times> H) = carrier G \<times> carrier H" |
|
550 |
by (simp add: DirProd_def) |
|
13944 | 551 |
|
14963 | 552 |
lemma one_DirProd [simp]: |
553 |
"\<one>\<^bsub>G \<times>\<times> H\<^esub> = (\<one>\<^bsub>G\<^esub>, \<one>\<^bsub>H\<^esub>)" |
|
554 |
by (simp add: DirProd_def) |
|
13944 | 555 |
|
14963 | 556 |
lemma mult_DirProd [simp]: |
557 |
"(g, h) \<otimes>\<^bsub>(G \<times>\<times> H)\<^esub> (g', h') = (g \<otimes>\<^bsub>G\<^esub> g', h \<otimes>\<^bsub>H\<^esub> h')" |
|
558 |
by (simp add: DirProd_def) |
|
13944 | 559 |
|
14963 | 560 |
lemma inv_DirProd [simp]: |
27611 | 561 |
assumes "group G" and "group H" |
13944 | 562 |
assumes g: "g \<in> carrier G" |
563 |
and h: "h \<in> carrier H" |
|
14963 | 564 |
shows "m_inv (G \<times>\<times> H) (g, h) = (inv\<^bsub>G\<^esub> g, inv\<^bsub>H\<^esub> h)" |
27611 | 565 |
proof - |
30729
461ee3e49ad3
interpretation/interpret: prefixes are mandatory by default;
wenzelm
parents:
29240
diff
changeset
|
566 |
interpret G: group G by fact |
461ee3e49ad3
interpretation/interpret: prefixes are mandatory by default;
wenzelm
parents:
29240
diff
changeset
|
567 |
interpret H: group H by fact |
461ee3e49ad3
interpretation/interpret: prefixes are mandatory by default;
wenzelm
parents:
29240
diff
changeset
|
568 |
interpret Prod: group "G \<times>\<times> H" |
27714
27b4d7c01f8b
Tuned (for the sake of a meaningless log entry).
ballarin
parents:
27713
diff
changeset
|
569 |
by (auto intro: DirProd_group group.intro group.axioms assms) |
14963 | 570 |
show ?thesis by (simp add: Prod.inv_equality g h) |
571 |
qed |
|
27698 | 572 |
|
14963 | 573 |
|
61382 | 574 |
subsection \<open>Homomorphisms and Isomorphisms\<close> |
13813 | 575 |
|
35847 | 576 |
definition |
577 |
hom :: "_ => _ => ('a => 'b) set" where |
|
35848
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
578 |
"hom G H = |
61384 | 579 |
{h. h \<in> carrier G \<rightarrow> carrier H & |
14693 | 580 |
(\<forall>x \<in> carrier G. \<forall>y \<in> carrier G. h (x \<otimes>\<^bsub>G\<^esub> y) = h x \<otimes>\<^bsub>H\<^esub> h y)}" |
13813 | 581 |
|
14761 | 582 |
lemma (in group) hom_compose: |
31754 | 583 |
"[|h \<in> hom G H; i \<in> hom H I|] ==> compose (carrier G) i h \<in> hom G I" |
44890
22f665a2e91c
new fastforce replacing fastsimp - less confusing name
nipkow
parents:
44655
diff
changeset
|
584 |
by (fastforce simp add: hom_def compose_def) |
13943 | 585 |
|
35848
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
586 |
definition |
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
587 |
iso :: "_ => _ => ('a => 'b) set" (infixr "\<cong>" 60) |
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
588 |
where "G \<cong> H = {h. h \<in> hom G H & bij_betw h (carrier G) (carrier H)}" |
14761 | 589 |
|
14803 | 590 |
lemma iso_refl: "(%x. x) \<in> G \<cong> G" |
31727 | 591 |
by (simp add: iso_def hom_def inj_on_def bij_betw_def Pi_def) |
14761 | 592 |
|
593 |
lemma (in group) iso_sym: |
|
33057 | 594 |
"h \<in> G \<cong> H \<Longrightarrow> inv_into (carrier G) h \<in> H \<cong> G" |
595 |
apply (simp add: iso_def bij_betw_inv_into) |
|
596 |
apply (subgoal_tac "inv_into (carrier G) h \<in> carrier H \<rightarrow> carrier G") |
|
597 |
prefer 2 apply (simp add: bij_betw_imp_funcset [OF bij_betw_inv_into]) |
|
598 |
apply (simp add: hom_def bij_betw_def inv_into_f_eq f_inv_into_f Pi_def) |
|
14761 | 599 |
done |
600 |
||
601 |
lemma (in group) iso_trans: |
|
14803 | 602 |
"[|h \<in> G \<cong> H; i \<in> H \<cong> I|] ==> (compose (carrier G) i h) \<in> G \<cong> I" |
14761 | 603 |
by (auto simp add: iso_def hom_compose bij_betw_compose) |
604 |
||
14963 | 605 |
lemma DirProd_commute_iso: |
606 |
shows "(\<lambda>(x,y). (y,x)) \<in> (G \<times>\<times> H) \<cong> (H \<times>\<times> G)" |
|
31754 | 607 |
by (auto simp add: iso_def hom_def inj_on_def bij_betw_def) |
14761 | 608 |
|
14963 | 609 |
lemma DirProd_assoc_iso: |
610 |
shows "(\<lambda>(x,y,z). (x,(y,z))) \<in> (G \<times>\<times> H \<times>\<times> I) \<cong> (G \<times>\<times> (H \<times>\<times> I))" |
|
31727 | 611 |
by (auto simp add: iso_def hom_def inj_on_def bij_betw_def) |
14761 | 612 |
|
613 |
||
61382 | 614 |
text\<open>Basis for homomorphism proofs: we assume two groups @{term G} and |
615 |
@{term H}, with a homomorphism @{term h} between them\<close> |
|
61565
352c73a689da
Qualifiers in locale expressions default to mandatory regardless of the command.
ballarin
parents:
61384
diff
changeset
|
616 |
locale group_hom = G?: group G + H?: group H for G (structure) and H (structure) + |
29237 | 617 |
fixes h |
13813 | 618 |
assumes homh: "h \<in> hom G H" |
29240 | 619 |
|
620 |
lemma (in group_hom) hom_mult [simp]: |
|
621 |
"[| x \<in> carrier G; y \<in> carrier G |] ==> h (x \<otimes>\<^bsub>G\<^esub> y) = h x \<otimes>\<^bsub>H\<^esub> h y" |
|
622 |
proof - |
|
623 |
assume "x \<in> carrier G" "y \<in> carrier G" |
|
624 |
with homh [unfolded hom_def] show ?thesis by simp |
|
625 |
qed |
|
626 |
||
627 |
lemma (in group_hom) hom_closed [simp]: |
|
628 |
"x \<in> carrier G ==> h x \<in> carrier H" |
|
629 |
proof - |
|
630 |
assume "x \<in> carrier G" |
|
31754 | 631 |
with homh [unfolded hom_def] show ?thesis by auto |
29240 | 632 |
qed |
13813 | 633 |
|
634 |
lemma (in group_hom) one_closed [simp]: |
|
635 |
"h \<one> \<in> carrier H" |
|
636 |
by simp |
|
637 |
||
638 |
lemma (in group_hom) hom_one [simp]: |
|
14693 | 639 |
"h \<one> = \<one>\<^bsub>H\<^esub>" |
13813 | 640 |
proof - |
15076
4b3d280ef06a
New prover for transitive and reflexive-transitive closure of relations.
ballarin
parents:
14963
diff
changeset
|
641 |
have "h \<one> \<otimes>\<^bsub>H\<^esub> \<one>\<^bsub>H\<^esub> = h \<one> \<otimes>\<^bsub>H\<^esub> h \<one>" |
13813 | 642 |
by (simp add: hom_mult [symmetric] del: hom_mult) |
643 |
then show ?thesis by (simp del: r_one) |
|
644 |
qed |
|
645 |
||
646 |
lemma (in group_hom) inv_closed [simp]: |
|
647 |
"x \<in> carrier G ==> h (inv x) \<in> carrier H" |
|
648 |
by simp |
|
649 |
||
650 |
lemma (in group_hom) hom_inv [simp]: |
|
14693 | 651 |
"x \<in> carrier G ==> h (inv x) = inv\<^bsub>H\<^esub> (h x)" |
13813 | 652 |
proof - |
653 |
assume x: "x \<in> carrier G" |
|
14693 | 654 |
then have "h x \<otimes>\<^bsub>H\<^esub> h (inv x) = \<one>\<^bsub>H\<^esub>" |
14963 | 655 |
by (simp add: hom_mult [symmetric] del: hom_mult) |
14693 | 656 |
also from x have "... = h x \<otimes>\<^bsub>H\<^esub> inv\<^bsub>H\<^esub> (h x)" |
14963 | 657 |
by (simp add: hom_mult [symmetric] del: hom_mult) |
14693 | 658 |
finally have "h x \<otimes>\<^bsub>H\<^esub> h (inv x) = h x \<otimes>\<^bsub>H\<^esub> inv\<^bsub>H\<^esub> (h x)" . |
27698 | 659 |
with x show ?thesis by (simp del: H.r_inv H.Units_r_inv) |
13813 | 660 |
qed |
661 |
||
57271 | 662 |
(* Contributed by Joachim Breitner *) |
663 |
lemma (in group) int_pow_is_hom: |
|
664 |
"x \<in> carrier G \<Longrightarrow> (op(^) x) \<in> hom \<lparr> carrier = UNIV, mult = op +, one = 0::int \<rparr> G " |
|
665 |
unfolding hom_def by (simp add: int_pow_mult) |
|
666 |
||
20318
0e0ea63fe768
Restructured algebra library, added ideals and quotient rings.
ballarin
parents:
19984
diff
changeset
|
667 |
|
61382 | 668 |
subsection \<open>Commutative Structures\<close> |
13936 | 669 |
|
61382 | 670 |
text \<open> |
13936 | 671 |
Naming convention: multiplicative structures that are commutative |
672 |
are called \emph{commutative}, additive structures are called |
|
673 |
\emph{Abelian}. |
|
61382 | 674 |
\<close> |
13813 | 675 |
|
14963 | 676 |
locale comm_monoid = monoid + |
677 |
assumes m_comm: "\<lbrakk>x \<in> carrier G; y \<in> carrier G\<rbrakk> \<Longrightarrow> x \<otimes> y = y \<otimes> x" |
|
13813 | 678 |
|
14963 | 679 |
lemma (in comm_monoid) m_lcomm: |
680 |
"\<lbrakk>x \<in> carrier G; y \<in> carrier G; z \<in> carrier G\<rbrakk> \<Longrightarrow> |
|
13813 | 681 |
x \<otimes> (y \<otimes> z) = y \<otimes> (x \<otimes> z)" |
682 |
proof - |
|
14693 | 683 |
assume xyz: "x \<in> carrier G" "y \<in> carrier G" "z \<in> carrier G" |
13813 | 684 |
from xyz have "x \<otimes> (y \<otimes> z) = (x \<otimes> y) \<otimes> z" by (simp add: m_assoc) |
685 |
also from xyz have "... = (y \<otimes> x) \<otimes> z" by (simp add: m_comm) |
|
686 |
also from xyz have "... = y \<otimes> (x \<otimes> z)" by (simp add: m_assoc) |
|
687 |
finally show ?thesis . |
|
688 |
qed |
|
689 |
||
14963 | 690 |
lemmas (in comm_monoid) m_ac = m_assoc m_comm m_lcomm |
13813 | 691 |
|
13936 | 692 |
lemma comm_monoidI: |
19783 | 693 |
fixes G (structure) |
13936 | 694 |
assumes m_closed: |
14693 | 695 |
"!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> x \<otimes> y \<in> carrier G" |
696 |
and one_closed: "\<one> \<in> carrier G" |
|
13936 | 697 |
and m_assoc: |
698 |
"!!x y z. [| x \<in> carrier G; y \<in> carrier G; z \<in> carrier G |] ==> |
|
14693 | 699 |
(x \<otimes> y) \<otimes> z = x \<otimes> (y \<otimes> z)" |
700 |
and l_one: "!!x. x \<in> carrier G ==> \<one> \<otimes> x = x" |
|
13936 | 701 |
and m_comm: |
14693 | 702 |
"!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> x \<otimes> y = y \<otimes> x" |
13936 | 703 |
shows "comm_monoid G" |
704 |
using l_one |
|
14963 | 705 |
by (auto intro!: comm_monoid.intro comm_monoid_axioms.intro monoid.intro |
27714
27b4d7c01f8b
Tuned (for the sake of a meaningless log entry).
ballarin
parents:
27713
diff
changeset
|
706 |
intro: assms simp: m_closed one_closed m_comm) |
13817 | 707 |
|
13936 | 708 |
lemma (in monoid) monoid_comm_monoidI: |
709 |
assumes m_comm: |
|
14693 | 710 |
"!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> x \<otimes> y = y \<otimes> x" |
13936 | 711 |
shows "comm_monoid G" |
712 |
by (rule comm_monoidI) (auto intro: m_assoc m_comm) |
|
14963 | 713 |
|
14693 | 714 |
(*lemma (in comm_monoid) r_one [simp]: |
13817 | 715 |
"x \<in> carrier G ==> x \<otimes> \<one> = x" |
716 |
proof - |
|
717 |
assume G: "x \<in> carrier G" |
|
718 |
then have "x \<otimes> \<one> = \<one> \<otimes> x" by (simp add: m_comm) |
|
719 |
also from G have "... = x" by simp |
|
720 |
finally show ?thesis . |
|
14693 | 721 |
qed*) |
14963 | 722 |
|
13936 | 723 |
lemma (in comm_monoid) nat_pow_distr: |
724 |
"[| x \<in> carrier G; y \<in> carrier G |] ==> |
|
725 |
(x \<otimes> y) (^) (n::nat) = x (^) n \<otimes> y (^) n" |
|
726 |
by (induct n) (simp, simp add: m_ac) |
|
727 |
||
728 |
locale comm_group = comm_monoid + group |
|
729 |
||
730 |
lemma (in group) group_comm_groupI: |
|
731 |
assumes m_comm: "!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> |
|
14693 | 732 |
x \<otimes> y = y \<otimes> x" |
13936 | 733 |
shows "comm_group G" |
61169 | 734 |
by standard (simp_all add: m_comm) |
13817 | 735 |
|
13936 | 736 |
lemma comm_groupI: |
19783 | 737 |
fixes G (structure) |
13936 | 738 |
assumes m_closed: |
14693 | 739 |
"!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> x \<otimes> y \<in> carrier G" |
740 |
and one_closed: "\<one> \<in> carrier G" |
|
13936 | 741 |
and m_assoc: |
742 |
"!!x y z. [| x \<in> carrier G; y \<in> carrier G; z \<in> carrier G |] ==> |
|
14693 | 743 |
(x \<otimes> y) \<otimes> z = x \<otimes> (y \<otimes> z)" |
13936 | 744 |
and m_comm: |
14693 | 745 |
"!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> x \<otimes> y = y \<otimes> x" |
746 |
and l_one: "!!x. x \<in> carrier G ==> \<one> \<otimes> x = x" |
|
14963 | 747 |
and l_inv_ex: "!!x. x \<in> carrier G ==> \<exists>y \<in> carrier G. y \<otimes> x = \<one>" |
13936 | 748 |
shows "comm_group G" |
27714
27b4d7c01f8b
Tuned (for the sake of a meaningless log entry).
ballarin
parents:
27713
diff
changeset
|
749 |
by (fast intro: group.group_comm_groupI groupI assms) |
13936 | 750 |
|
751 |
lemma (in comm_group) inv_mult: |
|
13854
91c9ab25fece
First distributed version of Group and Ring theory.
ballarin
parents:
13835
diff
changeset
|
752 |
"[| x \<in> carrier G; y \<in> carrier G |] ==> inv (x \<otimes> y) = inv x \<otimes> inv y" |
13936 | 753 |
by (simp add: m_ac inv_mult_group) |
13854
91c9ab25fece
First distributed version of Group and Ring theory.
ballarin
parents:
13835
diff
changeset
|
754 |
|
20318
0e0ea63fe768
Restructured algebra library, added ideals and quotient rings.
ballarin
parents:
19984
diff
changeset
|
755 |
|
61382 | 756 |
subsection \<open>The Lattice of Subgroups of a Group\<close> |
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
757 |
|
61382 | 758 |
text_raw \<open>\label{sec:subgroup-lattice}\<close> |
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
759 |
|
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
760 |
theorem (in group) subgroups_partial_order: |
55926 | 761 |
"partial_order \<lparr>carrier = {H. subgroup H G}, eq = op =, le = op \<subseteq>\<rparr>" |
61169 | 762 |
by standard simp_all |
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
763 |
|
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
764 |
lemma (in group) subgroup_self: |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
765 |
"subgroup (carrier G) G" |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
766 |
by (rule subgroupI) auto |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
767 |
|
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
768 |
lemma (in group) subgroup_imp_group: |
55926 | 769 |
"subgroup H G ==> group (G\<lparr>carrier := H\<rparr>)" |
26199 | 770 |
by (erule subgroup.subgroup_is_group) (rule group_axioms) |
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
771 |
|
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
772 |
lemma (in group) is_monoid [intro, simp]: |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
773 |
"monoid G" |
14963 | 774 |
by (auto intro: monoid.intro m_assoc) |
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
775 |
|
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
776 |
lemma (in group) subgroup_inv_equality: |
55926 | 777 |
"[| subgroup H G; x \<in> H |] ==> m_inv (G \<lparr>carrier := H\<rparr>) x = inv x" |
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
778 |
apply (rule_tac inv_equality [THEN sym]) |
14761 | 779 |
apply (rule group.l_inv [OF subgroup_imp_group, simplified], assumption+) |
780 |
apply (rule subsetD [OF subgroup.subset], assumption+) |
|
781 |
apply (rule subsetD [OF subgroup.subset], assumption) |
|
782 |
apply (rule_tac group.inv_closed [OF subgroup_imp_group, simplified], assumption+) |
|
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
783 |
done |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
784 |
|
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
785 |
theorem (in group) subgroups_Inter: |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
786 |
assumes subgr: "(!!H. H \<in> A ==> subgroup H G)" |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
787 |
and not_empty: "A ~= {}" |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
788 |
shows "subgroup (\<Inter>A) G" |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
789 |
proof (rule subgroupI) |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
790 |
from subgr [THEN subgroup.subset] and not_empty |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
791 |
show "\<Inter>A \<subseteq> carrier G" by blast |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
792 |
next |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
793 |
from subgr [THEN subgroup.one_closed] |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
794 |
show "\<Inter>A ~= {}" by blast |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
795 |
next |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
796 |
fix x assume "x \<in> \<Inter>A" |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
797 |
with subgr [THEN subgroup.m_inv_closed] |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
798 |
show "inv x \<in> \<Inter>A" by blast |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
799 |
next |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
800 |
fix x y assume "x \<in> \<Inter>A" "y \<in> \<Inter>A" |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
801 |
with subgr [THEN subgroup.m_closed] |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
802 |
show "x \<otimes> y \<in> \<Inter>A" by blast |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
803 |
qed |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
804 |
|
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
805 |
theorem (in group) subgroups_complete_lattice: |
55926 | 806 |
"complete_lattice \<lparr>carrier = {H. subgroup H G}, eq = op =, le = op \<subseteq>\<rparr>" |
22063
717425609192
Reverted to structure representation with records.
ballarin
parents:
21041
diff
changeset
|
807 |
(is "complete_lattice ?L") |
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
808 |
proof (rule partial_order.complete_lattice_criterion1) |
22063
717425609192
Reverted to structure representation with records.
ballarin
parents:
21041
diff
changeset
|
809 |
show "partial_order ?L" by (rule subgroups_partial_order) |
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
810 |
next |
46008
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
811 |
have "greatest ?L (carrier G) (carrier ?L)" |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
812 |
by (unfold greatest_def) (simp add: subgroup.subset subgroup_self) |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
813 |
then show "\<exists>G. greatest ?L G (carrier ?L)" .. |
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
814 |
next |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
815 |
fix A |
22063
717425609192
Reverted to structure representation with records.
ballarin
parents:
21041
diff
changeset
|
816 |
assume L: "A \<subseteq> carrier ?L" and non_empty: "A ~= {}" |
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
817 |
then have Int_subgroup: "subgroup (\<Inter>A) G" |
44890
22f665a2e91c
new fastforce replacing fastsimp - less confusing name
nipkow
parents:
44655
diff
changeset
|
818 |
by (fastforce intro: subgroups_Inter) |
46008
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
819 |
have "greatest ?L (\<Inter>A) (Lower ?L A)" (is "greatest _ ?Int _") |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
820 |
proof (rule greatest_LowerI) |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
821 |
fix H |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
822 |
assume H: "H \<in> A" |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
823 |
with L have subgroupH: "subgroup H G" by auto |
55926 | 824 |
from subgroupH have groupH: "group (G \<lparr>carrier := H\<rparr>)" (is "group ?H") |
46008
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
825 |
by (rule subgroup_imp_group) |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
826 |
from groupH have monoidH: "monoid ?H" |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
827 |
by (rule group.is_monoid) |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
828 |
from H have Int_subset: "?Int \<subseteq> H" by fastforce |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
829 |
then show "le ?L ?Int H" by simp |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
830 |
next |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
831 |
fix H |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
832 |
assume H: "H \<in> Lower ?L A" |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
833 |
with L Int_subgroup show "le ?L H ?Int" |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
834 |
by (fastforce simp: Lower_def intro: Inter_greatest) |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
835 |
next |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
836 |
show "A \<subseteq> carrier ?L" by (rule L) |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
837 |
next |
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
838 |
show "?Int \<in> carrier ?L" by simp (rule Int_subgroup) |
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
839 |
qed |
46008
c296c75f4cf4
reverted some changes for set->predicate transition, according to "hg log -u berghofe -r Isabelle2007:Isabelle2008";
wenzelm
parents:
44890
diff
changeset
|
840 |
then show "\<exists>I. greatest ?L I (Lower ?L A)" .. |
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
841 |
qed |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
842 |
|
13813 | 843 |
end |