author | paulson <lp15@cam.ac.uk> |
Wed, 03 Apr 2019 14:55:30 +0100 | |
changeset 70040 | 6a9e2a82ea15 |
parent 70039 | 733e256ecdf3 |
child 70044 | da5857dbcbb9 |
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. |
|
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
5 |
With additional contributions from Martin Baillon and Paulo Emílio de Vilhena. |
13813 | 6 |
*) |
7 |
||
28823 | 8 |
theory Group |
68188
2af1f142f855
move FuncSet back to HOL-Library (amending 493b818e8e10)
immler
parents:
68072
diff
changeset
|
9 |
imports Complete_Lattice "HOL-Library.FuncSet" |
28823 | 10 |
begin |
13813 | 11 |
|
70040
6a9e2a82ea15
Products and sums of a family of groups
paulson <lp15@cam.ac.uk>
parents:
70039
diff
changeset
|
12 |
(*MOVE*) |
6a9e2a82ea15
Products and sums of a family of groups
paulson <lp15@cam.ac.uk>
parents:
70039
diff
changeset
|
13 |
lemma image_paired_Times: |
6a9e2a82ea15
Products and sums of a family of groups
paulson <lp15@cam.ac.uk>
parents:
70039
diff
changeset
|
14 |
"(\<lambda>(x,y). (f x,g y)) ` (A \<times> B) = (f ` A) \<times> (g ` B)" |
6a9e2a82ea15
Products and sums of a family of groups
paulson <lp15@cam.ac.uk>
parents:
70039
diff
changeset
|
15 |
by auto |
6a9e2a82ea15
Products and sums of a family of groups
paulson <lp15@cam.ac.uk>
parents:
70039
diff
changeset
|
16 |
|
61382 | 17 |
section \<open>Monoids and Groups\<close> |
13936 | 18 |
|
61382 | 19 |
subsection \<open>Definitions\<close> |
20318
0e0ea63fe768
Restructured algebra library, added ideals and quotient rings.
ballarin
parents:
19984
diff
changeset
|
20 |
|
61382 | 21 |
text \<open> |
58622 | 22 |
Definitions follow @{cite "Jacobson:1985"}. |
61382 | 23 |
\<close> |
13813 | 24 |
|
14963 | 25 |
record 'a monoid = "'a partial_object" + |
26 |
mult :: "['a, 'a] \<Rightarrow> 'a" (infixl "\<otimes>\<index>" 70) |
|
27 |
one :: 'a ("\<one>\<index>") |
|
13817 | 28 |
|
35847 | 29 |
definition |
14852 | 30 |
m_inv :: "('a, 'b) monoid_scheme => 'a => 'a" ("inv\<index> _" [81] 80) |
67091 | 31 |
where "inv\<^bsub>G\<^esub> x = (THE y. y \<in> carrier G \<and> x \<otimes>\<^bsub>G\<^esub> y = \<one>\<^bsub>G\<^esub> \<and> y \<otimes>\<^bsub>G\<^esub> x = \<one>\<^bsub>G\<^esub>)" |
13936 | 32 |
|
35847 | 33 |
definition |
14651 | 34 |
Units :: "_ => 'a set" |
67443
3abf6a722518
standardized towards new-style formal comments: isabelle update_comments;
wenzelm
parents:
67399
diff
changeset
|
35 |
\<comment> \<open>The set of invertible elements\<close> |
67091 | 36 |
where "Units G = {y. y \<in> carrier G \<and> (\<exists>x \<in> carrier G. x \<otimes>\<^bsub>G\<^esub> y = \<one>\<^bsub>G\<^esub> \<and> y \<otimes>\<^bsub>G\<^esub> x = \<one>\<^bsub>G\<^esub>)}" |
13936 | 37 |
|
19783 | 38 |
locale monoid = |
39 |
fixes G (structure) |
|
13813 | 40 |
assumes m_closed [intro, simp]: |
14963 | 41 |
"\<lbrakk>x \<in> carrier G; y \<in> carrier G\<rbrakk> \<Longrightarrow> x \<otimes> y \<in> carrier G" |
42 |
and m_assoc: |
|
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
43 |
"\<lbrakk>x \<in> carrier G; y \<in> carrier G; z \<in> carrier G\<rbrakk> |
14963 | 44 |
\<Longrightarrow> (x \<otimes> y) \<otimes> z = x \<otimes> (y \<otimes> z)" |
45 |
and one_closed [intro, simp]: "\<one> \<in> carrier G" |
|
46 |
and l_one [simp]: "x \<in> carrier G \<Longrightarrow> \<one> \<otimes> x = x" |
|
47 |
and r_one [simp]: "x \<in> carrier G \<Longrightarrow> x \<otimes> \<one> = x" |
|
13817 | 48 |
|
13936 | 49 |
lemma monoidI: |
19783 | 50 |
fixes G (structure) |
13936 | 51 |
assumes m_closed: |
14693 | 52 |
"!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> x \<otimes> y \<in> carrier G" |
53 |
and one_closed: "\<one> \<in> carrier G" |
|
13936 | 54 |
and m_assoc: |
55 |
"!!x y z. [| x \<in> carrier G; y \<in> carrier G; z \<in> carrier G |] ==> |
|
14693 | 56 |
(x \<otimes> y) \<otimes> z = x \<otimes> (y \<otimes> z)" |
57 |
and l_one: "!!x. x \<in> carrier G ==> \<one> \<otimes> x = x" |
|
58 |
and r_one: "!!x. x \<in> carrier G ==> x \<otimes> \<one> = x" |
|
13936 | 59 |
shows "monoid G" |
27714
27b4d7c01f8b
Tuned (for the sake of a meaningless log entry).
ballarin
parents:
27713
diff
changeset
|
60 |
by (fast intro!: monoid.intro intro: assms) |
13936 | 61 |
|
62 |
lemma (in monoid) Units_closed [dest]: |
|
63 |
"x \<in> Units G ==> x \<in> carrier G" |
|
64 |
by (unfold Units_def) fast |
|
65 |
||
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
66 |
lemma (in monoid) one_unique: |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
67 |
assumes "u \<in> carrier G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
68 |
and "\<And>x. x \<in> carrier G \<Longrightarrow> u \<otimes> x = x" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
69 |
shows "u = \<one>" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
70 |
using assms(2)[OF one_closed] r_one[OF assms(1)] by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
71 |
|
13936 | 72 |
lemma (in monoid) inv_unique: |
14693 | 73 |
assumes eq: "y \<otimes> x = \<one>" "x \<otimes> y' = \<one>" |
74 |
and G: "x \<in> carrier G" "y \<in> carrier G" "y' \<in> carrier G" |
|
13936 | 75 |
shows "y = y'" |
76 |
proof - |
|
77 |
from G eq have "y = y \<otimes> (x \<otimes> y')" by simp |
|
78 |
also from G have "... = (y \<otimes> x) \<otimes> y'" by (simp add: m_assoc) |
|
79 |
also from G eq have "... = y'" by simp |
|
80 |
finally show ?thesis . |
|
81 |
qed |
|
82 |
||
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
83 |
lemma (in monoid) Units_m_closed [simp, intro]: |
27698 | 84 |
assumes x: "x \<in> Units G" and y: "y \<in> Units G" |
85 |
shows "x \<otimes> y \<in> Units G" |
|
86 |
proof - |
|
87 |
from x obtain x' where x: "x \<in> carrier G" "x' \<in> carrier G" and xinv: "x \<otimes> x' = \<one>" "x' \<otimes> x = \<one>" |
|
88 |
unfolding Units_def by fast |
|
89 |
from y obtain y' where y: "y \<in> carrier G" "y' \<in> carrier G" and yinv: "y \<otimes> y' = \<one>" "y' \<otimes> y = \<one>" |
|
90 |
unfolding Units_def by fast |
|
91 |
from x y xinv yinv have "y' \<otimes> (x' \<otimes> x) \<otimes> y = \<one>" by simp |
|
92 |
moreover from x y xinv yinv have "x \<otimes> (y \<otimes> y') \<otimes> x' = \<one>" by simp |
|
93 |
moreover note x y |
|
94 |
ultimately show ?thesis unfolding Units_def |
|
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
95 |
by simp (metis m_assoc m_closed) |
27698 | 96 |
qed |
97 |
||
13940 | 98 |
lemma (in monoid) Units_one_closed [intro, simp]: |
99 |
"\<one> \<in> Units G" |
|
100 |
by (unfold Units_def) auto |
|
101 |
||
13936 | 102 |
lemma (in monoid) Units_inv_closed [intro, simp]: |
103 |
"x \<in> Units G ==> inv x \<in> carrier G" |
|
68662 | 104 |
apply (simp add: Units_def m_inv_def) |
105 |
by (metis (mono_tags, lifting) inv_unique the_equality) |
|
13936 | 106 |
|
19981 | 107 |
lemma (in monoid) Units_l_inv_ex: |
108 |
"x \<in> Units G ==> \<exists>y \<in> carrier G. y \<otimes> x = \<one>" |
|
109 |
by (unfold Units_def) auto |
|
110 |
||
111 |
lemma (in monoid) Units_r_inv_ex: |
|
112 |
"x \<in> Units G ==> \<exists>y \<in> carrier G. x \<otimes> y = \<one>" |
|
113 |
by (unfold Units_def) auto |
|
114 |
||
27698 | 115 |
lemma (in monoid) Units_l_inv [simp]: |
13936 | 116 |
"x \<in> Units G ==> inv x \<otimes> x = \<one>" |
68662 | 117 |
apply (unfold Units_def m_inv_def, simp) |
118 |
by (metis (mono_tags, lifting) inv_unique the_equality) |
|
13936 | 119 |
|
27698 | 120 |
lemma (in monoid) Units_r_inv [simp]: |
13936 | 121 |
"x \<in> Units G ==> x \<otimes> inv x = \<one>" |
68458 | 122 |
by (metis (full_types) Units_closed Units_inv_closed Units_l_inv Units_r_inv_ex inv_unique) |
13936 | 123 |
|
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
124 |
lemma (in monoid) inv_one [simp]: |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
125 |
"inv \<one> = \<one>" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
126 |
by (metis Units_one_closed Units_r_inv l_one monoid.Units_inv_closed monoid_axioms) |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
127 |
|
13936 | 128 |
lemma (in monoid) Units_inv_Units [intro, simp]: |
129 |
"x \<in> Units G ==> inv x \<in> Units G" |
|
130 |
proof - |
|
131 |
assume x: "x \<in> Units G" |
|
132 |
show "inv x \<in> Units G" |
|
133 |
by (auto simp add: Units_def |
|
134 |
intro: Units_l_inv Units_r_inv x Units_closed [OF x]) |
|
135 |
qed |
|
136 |
||
137 |
lemma (in monoid) Units_l_cancel [simp]: |
|
138 |
"[| x \<in> Units G; y \<in> carrier G; z \<in> carrier G |] ==> |
|
139 |
(x \<otimes> y = x \<otimes> z) = (y = z)" |
|
140 |
proof |
|
141 |
assume eq: "x \<otimes> y = x \<otimes> z" |
|
14693 | 142 |
and G: "x \<in> Units G" "y \<in> carrier G" "z \<in> carrier G" |
13936 | 143 |
then have "(inv x \<otimes> x) \<otimes> y = (inv x \<otimes> x) \<otimes> z" |
27698 | 144 |
by (simp add: m_assoc Units_closed del: Units_l_inv) |
44472 | 145 |
with G show "y = z" by simp |
13936 | 146 |
next |
147 |
assume eq: "y = z" |
|
14693 | 148 |
and G: "x \<in> Units G" "y \<in> carrier G" "z \<in> carrier G" |
13936 | 149 |
then show "x \<otimes> y = x \<otimes> z" by simp |
150 |
qed |
|
151 |
||
152 |
lemma (in monoid) Units_inv_inv [simp]: |
|
153 |
"x \<in> Units G ==> inv (inv x) = x" |
|
154 |
proof - |
|
155 |
assume x: "x \<in> Units G" |
|
27698 | 156 |
then have "inv x \<otimes> inv (inv x) = inv x \<otimes> x" by simp |
157 |
with x show ?thesis by (simp add: Units_closed del: Units_l_inv Units_r_inv) |
|
13936 | 158 |
qed |
159 |
||
160 |
lemma (in monoid) inv_inj_on_Units: |
|
161 |
"inj_on (m_inv G) (Units G)" |
|
162 |
proof (rule inj_onI) |
|
163 |
fix x y |
|
14693 | 164 |
assume G: "x \<in> Units G" "y \<in> Units G" and eq: "inv x = inv y" |
13936 | 165 |
then have "inv (inv x) = inv (inv y)" by simp |
166 |
with G show "x = y" by simp |
|
167 |
qed |
|
168 |
||
13940 | 169 |
lemma (in monoid) Units_inv_comm: |
170 |
assumes inv: "x \<otimes> y = \<one>" |
|
14693 | 171 |
and G: "x \<in> Units G" "y \<in> Units G" |
13940 | 172 |
shows "y \<otimes> x = \<one>" |
173 |
proof - |
|
174 |
from G have "x \<otimes> y \<otimes> x = x \<otimes> \<one>" by (auto simp add: inv Units_closed) |
|
175 |
with G show ?thesis by (simp del: r_one add: m_assoc Units_closed) |
|
176 |
qed |
|
177 |
||
61628 | 178 |
lemma (in monoid) carrier_not_empty: "carrier G \<noteq> {}" |
179 |
by auto |
|
180 |
||
27698 | 181 |
(* Jacobson defines submonoid here. *) |
182 |
(* Jacobson defines the order of a monoid here. *) |
|
183 |
||
184 |
||
61382 | 185 |
subsection \<open>Groups\<close> |
27698 | 186 |
|
61382 | 187 |
text \<open> |
13936 | 188 |
A group is a monoid all of whose elements are invertible. |
61382 | 189 |
\<close> |
13936 | 190 |
|
191 |
locale group = monoid + |
|
192 |
assumes Units: "carrier G <= Units G" |
|
193 |
||
70039
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
194 |
lemma (in group) is_group [iff]: "group G" by (rule group_axioms) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
195 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
196 |
lemma (in group) is_monoid [iff]: "monoid G" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
197 |
by (rule monoid_axioms) |
14761 | 198 |
|
13936 | 199 |
theorem groupI: |
19783 | 200 |
fixes G (structure) |
13936 | 201 |
assumes m_closed [simp]: |
14693 | 202 |
"!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> x \<otimes> y \<in> carrier G" |
203 |
and one_closed [simp]: "\<one> \<in> carrier G" |
|
13936 | 204 |
and m_assoc: |
205 |
"!!x y z. [| x \<in> carrier G; y \<in> carrier G; z \<in> carrier G |] ==> |
|
14693 | 206 |
(x \<otimes> y) \<otimes> z = x \<otimes> (y \<otimes> z)" |
207 |
and l_one [simp]: "!!x. x \<in> carrier G ==> \<one> \<otimes> x = x" |
|
14963 | 208 |
and l_inv_ex: "!!x. x \<in> carrier G ==> \<exists>y \<in> carrier G. y \<otimes> x = \<one>" |
13936 | 209 |
shows "group G" |
210 |
proof - |
|
211 |
have l_cancel [simp]: |
|
212 |
"!!x y z. [| x \<in> carrier G; y \<in> carrier G; z \<in> carrier G |] ==> |
|
14693 | 213 |
(x \<otimes> y = x \<otimes> z) = (y = z)" |
13936 | 214 |
proof |
215 |
fix x y z |
|
14693 | 216 |
assume eq: "x \<otimes> y = x \<otimes> z" |
217 |
and G: "x \<in> carrier G" "y \<in> carrier G" "z \<in> carrier G" |
|
13936 | 218 |
with l_inv_ex obtain x_inv where xG: "x_inv \<in> carrier G" |
14693 | 219 |
and l_inv: "x_inv \<otimes> x = \<one>" by fast |
220 |
from G eq xG have "(x_inv \<otimes> x) \<otimes> y = (x_inv \<otimes> x) \<otimes> z" |
|
13936 | 221 |
by (simp add: m_assoc) |
222 |
with G show "y = z" by (simp add: l_inv) |
|
223 |
next |
|
224 |
fix x y z |
|
225 |
assume eq: "y = z" |
|
14693 | 226 |
and G: "x \<in> carrier G" "y \<in> carrier G" "z \<in> carrier G" |
227 |
then show "x \<otimes> y = x \<otimes> z" by simp |
|
13936 | 228 |
qed |
229 |
have r_one: |
|
14693 | 230 |
"!!x. x \<in> carrier G ==> x \<otimes> \<one> = x" |
13936 | 231 |
proof - |
232 |
fix x |
|
233 |
assume x: "x \<in> carrier G" |
|
234 |
with l_inv_ex obtain x_inv where xG: "x_inv \<in> carrier G" |
|
14693 | 235 |
and l_inv: "x_inv \<otimes> x = \<one>" by fast |
236 |
from x xG have "x_inv \<otimes> (x \<otimes> \<one>) = x_inv \<otimes> x" |
|
13936 | 237 |
by (simp add: m_assoc [symmetric] l_inv) |
14693 | 238 |
with x xG show "x \<otimes> \<one> = x" by simp |
13936 | 239 |
qed |
240 |
have inv_ex: |
|
67091 | 241 |
"\<And>x. x \<in> carrier G \<Longrightarrow> \<exists>y \<in> carrier G. y \<otimes> x = \<one> \<and> x \<otimes> y = \<one>" |
13936 | 242 |
proof - |
243 |
fix x |
|
244 |
assume x: "x \<in> carrier G" |
|
245 |
with l_inv_ex obtain y where y: "y \<in> carrier G" |
|
14693 | 246 |
and l_inv: "y \<otimes> x = \<one>" by fast |
247 |
from x y have "y \<otimes> (x \<otimes> y) = y \<otimes> \<one>" |
|
13936 | 248 |
by (simp add: m_assoc [symmetric] l_inv r_one) |
14693 | 249 |
with x y have r_inv: "x \<otimes> y = \<one>" |
13936 | 250 |
by simp |
67091 | 251 |
from x y show "\<exists>y \<in> carrier G. y \<otimes> x = \<one> \<and> x \<otimes> y = \<one>" |
13936 | 252 |
by (fast intro: l_inv r_inv) |
253 |
qed |
|
67091 | 254 |
then have carrier_subset_Units: "carrier G \<subseteq> Units G" |
13936 | 255 |
by (unfold Units_def) fast |
61169 | 256 |
show ?thesis |
257 |
by standard (auto simp: r_one m_assoc carrier_subset_Units) |
|
13936 | 258 |
qed |
259 |
||
27698 | 260 |
lemma (in monoid) group_l_invI: |
13936 | 261 |
assumes l_inv_ex: |
14963 | 262 |
"!!x. x \<in> carrier G ==> \<exists>y \<in> carrier G. y \<otimes> x = \<one>" |
13936 | 263 |
shows "group G" |
264 |
by (rule groupI) (auto intro: m_assoc l_inv_ex) |
|
265 |
||
266 |
lemma (in group) Units_eq [simp]: |
|
267 |
"Units G = carrier G" |
|
268 |
proof |
|
67091 | 269 |
show "Units G \<subseteq> carrier G" by fast |
13936 | 270 |
next |
67091 | 271 |
show "carrier G \<subseteq> Units G" by (rule Units) |
13936 | 272 |
qed |
273 |
||
274 |
lemma (in group) inv_closed [intro, simp]: |
|
275 |
"x \<in> carrier G ==> inv x \<in> carrier G" |
|
276 |
using Units_inv_closed by simp |
|
277 |
||
19981 | 278 |
lemma (in group) l_inv_ex [simp]: |
279 |
"x \<in> carrier G ==> \<exists>y \<in> carrier G. y \<otimes> x = \<one>" |
|
280 |
using Units_l_inv_ex by simp |
|
281 |
||
282 |
lemma (in group) r_inv_ex [simp]: |
|
283 |
"x \<in> carrier G ==> \<exists>y \<in> carrier G. x \<otimes> y = \<one>" |
|
284 |
using Units_r_inv_ex by simp |
|
285 |
||
14963 | 286 |
lemma (in group) l_inv [simp]: |
13936 | 287 |
"x \<in> carrier G ==> inv x \<otimes> x = \<one>" |
68399
0b71d08528f0
resolution of name clashes in Algebra
paulson <lp15@cam.ac.uk>
parents:
68188
diff
changeset
|
288 |
by simp |
13813 | 289 |
|
20318
0e0ea63fe768
Restructured algebra library, added ideals and quotient rings.
ballarin
parents:
19984
diff
changeset
|
290 |
|
61382 | 291 |
subsection \<open>Cancellation Laws and Basic Properties\<close> |
13813 | 292 |
|
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
293 |
lemma (in group) inv_eq_1_iff [simp]: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
294 |
assumes "x \<in> carrier G" shows "inv\<^bsub>G\<^esub> x = \<one>\<^bsub>G\<^esub> \<longleftrightarrow> x = \<one>\<^bsub>G\<^esub>" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
295 |
proof - |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
296 |
have "x = \<one>" if "inv x = \<one>" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
297 |
proof - |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
298 |
have "inv x \<otimes> x = \<one>" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
299 |
using assms l_inv by blast |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
300 |
then show "x = \<one>" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
301 |
using that assms by simp |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
302 |
qed |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
303 |
then show ?thesis |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
304 |
by auto |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
305 |
qed |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
306 |
|
14963 | 307 |
lemma (in group) r_inv [simp]: |
13813 | 308 |
"x \<in> carrier G ==> x \<otimes> inv x = \<one>" |
68399
0b71d08528f0
resolution of name clashes in Algebra
paulson <lp15@cam.ac.uk>
parents:
68188
diff
changeset
|
309 |
by simp |
13813 | 310 |
|
68399
0b71d08528f0
resolution of name clashes in Algebra
paulson <lp15@cam.ac.uk>
parents:
68188
diff
changeset
|
311 |
lemma (in group) right_cancel [simp]: |
13813 | 312 |
"[| x \<in> carrier G; y \<in> carrier G; z \<in> carrier G |] ==> |
313 |
(y \<otimes> x = z \<otimes> x) = (y = z)" |
|
68399
0b71d08528f0
resolution of name clashes in Algebra
paulson <lp15@cam.ac.uk>
parents:
68188
diff
changeset
|
314 |
by (metis inv_closed m_assoc r_inv r_one) |
13813 | 315 |
|
316 |
lemma (in group) inv_inv [simp]: |
|
317 |
"x \<in> carrier G ==> inv (inv x) = x" |
|
13936 | 318 |
using Units_inv_inv by simp |
319 |
||
320 |
lemma (in group) inv_inj: |
|
321 |
"inj_on (m_inv G) (carrier G)" |
|
322 |
using inv_inj_on_Units by simp |
|
13813 | 323 |
|
13854
91c9ab25fece
First distributed version of Group and Ring theory.
ballarin
parents:
13835
diff
changeset
|
324 |
lemma (in group) inv_mult_group: |
13813 | 325 |
"[| x \<in> carrier G; y \<in> carrier G |] ==> inv (x \<otimes> y) = inv y \<otimes> inv x" |
326 |
proof - |
|
14693 | 327 |
assume G: "x \<in> carrier G" "y \<in> carrier G" |
13813 | 328 |
then have "inv (x \<otimes> y) \<otimes> (x \<otimes> y) = (inv y \<otimes> inv x) \<otimes> (x \<otimes> y)" |
44472 | 329 |
by (simp add: m_assoc) (simp add: m_assoc [symmetric]) |
27698 | 330 |
with G show ?thesis by (simp del: l_inv Units_l_inv) |
13813 | 331 |
qed |
332 |
||
13940 | 333 |
lemma (in group) inv_comm: |
334 |
"[| x \<otimes> y = \<one>; x \<in> carrier G; y \<in> carrier G |] ==> y \<otimes> x = \<one>" |
|
14693 | 335 |
by (rule Units_inv_comm) auto |
13940 | 336 |
|
13944 | 337 |
lemma (in group) inv_equality: |
13943 | 338 |
"[|y \<otimes> x = \<one>; x \<in> carrier G; y \<in> carrier G|] ==> inv x = y" |
68399
0b71d08528f0
resolution of name clashes in Algebra
paulson <lp15@cam.ac.uk>
parents:
68188
diff
changeset
|
339 |
using inv_unique r_inv by blast |
13943 | 340 |
|
57271 | 341 |
lemma (in group) inv_solve_left: |
342 |
"\<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" |
|
343 |
by (metis inv_equality l_inv_ex l_one m_assoc r_inv) |
|
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
344 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
345 |
lemma (in group) inv_solve_left': |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
346 |
"\<lbrakk> a \<in> carrier G; b \<in> carrier G; c \<in> carrier G \<rbrakk> \<Longrightarrow> inv b \<otimes> c = a \<longleftrightarrow> c = b \<otimes> a" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
347 |
by (metis inv_equality l_inv_ex l_one m_assoc r_inv) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
348 |
|
57271 | 349 |
lemma (in group) inv_solve_right: |
350 |
"\<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" |
|
351 |
by (metis inv_equality l_inv_ex l_one m_assoc r_inv) |
|
352 |
||
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
353 |
lemma (in group) inv_solve_right': |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
354 |
"\<lbrakk>a \<in> carrier G; b \<in> carrier G; c \<in> carrier G\<rbrakk> \<Longrightarrow> b \<otimes> inv c = a \<longleftrightarrow> b = a \<otimes> c" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
355 |
by (auto simp: m_assoc) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
356 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
357 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
358 |
subsection \<open>Power\<close> |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
359 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
360 |
consts |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
361 |
pow :: "[('a, 'm) monoid_scheme, 'a, 'b::semiring_1] => 'a" (infixr "[^]\<index>" 75) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
362 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
363 |
overloading nat_pow == "pow :: [_, 'a, nat] => 'a" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
364 |
begin |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
365 |
definition "nat_pow G a n = rec_nat \<one>\<^bsub>G\<^esub> (%u b. b \<otimes>\<^bsub>G\<^esub> a) n" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
366 |
end |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
367 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
368 |
lemma (in monoid) nat_pow_closed [intro, simp]: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
369 |
"x \<in> carrier G ==> x [^] (n::nat) \<in> carrier G" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
370 |
by (induct n) (simp_all add: nat_pow_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
371 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
372 |
lemma (in monoid) nat_pow_0 [simp]: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
373 |
"x [^] (0::nat) = \<one>" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
374 |
by (simp add: nat_pow_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
375 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
376 |
lemma (in monoid) nat_pow_Suc [simp]: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
377 |
"x [^] (Suc n) = x [^] n \<otimes> x" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
378 |
by (simp add: nat_pow_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
379 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
380 |
lemma (in monoid) nat_pow_one [simp]: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
381 |
"\<one> [^] (n::nat) = \<one>" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
382 |
by (induct n) simp_all |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
383 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
384 |
lemma (in monoid) nat_pow_mult: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
385 |
"x \<in> carrier G ==> x [^] (n::nat) \<otimes> x [^] m = x [^] (n + m)" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
386 |
by (induct m) (simp_all add: m_assoc [THEN sym]) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
387 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
388 |
lemma (in monoid) nat_pow_comm: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
389 |
"x \<in> carrier G \<Longrightarrow> (x [^] (n::nat)) \<otimes> (x [^] (m :: nat)) = (x [^] m) \<otimes> (x [^] n)" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
390 |
using nat_pow_mult[of x n m] nat_pow_mult[of x m n] by (simp add: add.commute) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
391 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
392 |
lemma (in monoid) nat_pow_Suc2: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
393 |
"x \<in> carrier G \<Longrightarrow> x [^] (Suc n) = x \<otimes> (x [^] n)" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
394 |
using nat_pow_mult[of x 1 n] Suc_eq_plus1[of n] |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
395 |
by (metis One_nat_def Suc_eq_plus1_left l_one nat.rec(1) nat_pow_Suc nat_pow_def) |
13936 | 396 |
|
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
397 |
lemma (in monoid) nat_pow_pow: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
398 |
"x \<in> carrier G ==> (x [^] n) [^] m = x [^] (n * m::nat)" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
399 |
by (induct m) (simp, simp add: nat_pow_mult add.commute) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
400 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
401 |
lemma (in monoid) nat_pow_consistent: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
402 |
"x [^] (n :: nat) = x [^]\<^bsub>(G \<lparr> carrier := H \<rparr>)\<^esub> n" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
403 |
unfolding nat_pow_def by simp |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
404 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
405 |
lemma nat_pow_0 [simp]: "x [^]\<^bsub>G\<^esub> (0::nat) = \<one>\<^bsub>G\<^esub>" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
406 |
by (simp add: nat_pow_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
407 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
408 |
lemma nat_pow_Suc [simp]: "x [^]\<^bsub>G\<^esub> (Suc n) = (x [^]\<^bsub>G\<^esub> n)\<otimes>\<^bsub>G\<^esub> x" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
409 |
by (simp add: nat_pow_def) |
13936 | 410 |
|
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
411 |
lemma (in group) nat_pow_inv: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
412 |
assumes "x \<in> carrier G" shows "(inv x) [^] (i :: nat) = inv (x [^] i)" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
413 |
proof (induction i) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
414 |
case 0 thus ?case by simp |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
415 |
next |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
416 |
case (Suc i) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
417 |
have "(inv x) [^] Suc i = ((inv x) [^] i) \<otimes> inv x" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
418 |
by simp |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
419 |
also have " ... = (inv (x [^] i)) \<otimes> inv x" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
420 |
by (simp add: Suc.IH Suc.prems) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
421 |
also have " ... = inv (x \<otimes> (x [^] i))" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
422 |
by (simp add: assms inv_mult_group) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
423 |
also have " ... = inv (x [^] (Suc i))" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
424 |
using assms nat_pow_Suc2 by auto |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
425 |
finally show ?case . |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
426 |
qed |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
427 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
428 |
overloading int_pow == "pow :: [_, 'a, int] => 'a" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
429 |
begin |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
430 |
definition "int_pow G a z = |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
431 |
(let p = rec_nat \<one>\<^bsub>G\<^esub> (%u b. b \<otimes>\<^bsub>G\<^esub> a) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
432 |
in if z < 0 then inv\<^bsub>G\<^esub> (p (nat (-z))) else p (nat z))" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
433 |
end |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
434 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
435 |
lemma int_pow_int: "x [^]\<^bsub>G\<^esub> (int n) = x [^]\<^bsub>G\<^esub> n" |
70019
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
436 |
by(simp add: int_pow_def nat_pow_def) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
437 |
|
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
438 |
lemma pow_nat: |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
439 |
assumes "i\<ge>0" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
440 |
shows "x [^]\<^bsub>G\<^esub> nat i = x [^]\<^bsub>G\<^esub> i" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
441 |
proof (cases i rule: int_cases) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
442 |
case (nonneg n) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
443 |
then show ?thesis |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
444 |
by (simp add: int_pow_int) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
445 |
next |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
446 |
case (neg n) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
447 |
then show ?thesis |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
448 |
using assms by linarith |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
449 |
qed |
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
450 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
451 |
lemma int_pow_0 [simp]: "x [^]\<^bsub>G\<^esub> (0::int) = \<one>\<^bsub>G\<^esub>" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
452 |
by (simp add: int_pow_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
453 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
454 |
lemma int_pow_def2: "a [^]\<^bsub>G\<^esub> z = |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
455 |
(if z < 0 then inv\<^bsub>G\<^esub> (a [^]\<^bsub>G\<^esub> (nat (-z))) else a [^]\<^bsub>G\<^esub> (nat z))" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
456 |
by (simp add: int_pow_def nat_pow_def) |
13936 | 457 |
|
458 |
lemma (in group) int_pow_one [simp]: |
|
67341
df79ef3b3a41
Renamed (^) to [^] in preparation of the move from "op X" to (X)
nipkow
parents:
67091
diff
changeset
|
459 |
"\<one> [^] (z::int) = \<one>" |
13936 | 460 |
by (simp add: int_pow_def2) |
461 |
||
57271 | 462 |
lemma (in group) int_pow_closed [intro, simp]: |
67341
df79ef3b3a41
Renamed (^) to [^] in preparation of the move from "op X" to (X)
nipkow
parents:
67091
diff
changeset
|
463 |
"x \<in> carrier G ==> x [^] (i::int) \<in> carrier G" |
57271 | 464 |
by (simp add: int_pow_def2) |
465 |
||
466 |
lemma (in group) int_pow_1 [simp]: |
|
67341
df79ef3b3a41
Renamed (^) to [^] in preparation of the move from "op X" to (X)
nipkow
parents:
67091
diff
changeset
|
467 |
"x \<in> carrier G \<Longrightarrow> x [^] (1::int) = x" |
57271 | 468 |
by (simp add: int_pow_def2) |
469 |
||
470 |
lemma (in group) int_pow_neg: |
|
67341
df79ef3b3a41
Renamed (^) to [^] in preparation of the move from "op X" to (X)
nipkow
parents:
67091
diff
changeset
|
471 |
"x \<in> carrier G \<Longrightarrow> x [^] (-i::int) = inv (x [^] i)" |
57271 | 472 |
by (simp add: int_pow_def2) |
473 |
||
70019
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
474 |
lemma (in group) int_pow_neg_int: "x \<in> carrier G \<Longrightarrow> x [^] -(int n) = inv (x [^] n)" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
475 |
by (simp add: int_pow_neg int_pow_int) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
476 |
|
57271 | 477 |
lemma (in group) int_pow_mult: |
68662 | 478 |
assumes "x \<in> carrier G" shows "x [^] (i + j::int) = x [^] i \<otimes> x [^] j" |
57271 | 479 |
proof - |
480 |
have [simp]: "-i - j = -j - i" by simp |
|
481 |
show ?thesis |
|
70027
94494b92d8d0
some new group theory results: integer group, trivial group, etc.
paulson <lp15@cam.ac.uk>
parents:
70019
diff
changeset
|
482 |
by (auto simp: assms int_pow_def2 inv_solve_left inv_solve_right nat_add_distrib [symmetric] nat_pow_mult) |
57271 | 483 |
qed |
484 |
||
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
485 |
lemma (in group) int_pow_inv: |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
486 |
"x \<in> carrier G \<Longrightarrow> (inv x) [^] (i :: int) = inv (x [^] i)" |
70027
94494b92d8d0
some new group theory results: integer group, trivial group, etc.
paulson <lp15@cam.ac.uk>
parents:
70019
diff
changeset
|
487 |
by (metis int_pow_def2 nat_pow_inv) |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
488 |
|
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
489 |
lemma (in group) int_pow_pow: |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
490 |
assumes "x \<in> carrier G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
491 |
shows "(x [^] (n :: int)) [^] (m :: int) = x [^] (n * m :: int)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
492 |
proof (cases) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
493 |
assume n_ge: "n \<ge> 0" thus ?thesis |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
494 |
proof (cases) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
495 |
assume m_ge: "m \<ge> 0" thus ?thesis |
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
496 |
using n_ge nat_pow_pow[OF assms, of "nat n" "nat m"] int_pow_def2 [where G=G] |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
497 |
by (simp add: mult_less_0_iff nat_mult_distrib) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
498 |
next |
68605 | 499 |
assume m_lt: "\<not> m \<ge> 0" |
500 |
with n_ge show ?thesis |
|
501 |
apply (simp add: int_pow_def2 mult_less_0_iff) |
|
502 |
by (metis assms mult_minus_right n_ge nat_mult_distrib nat_pow_pow) |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
503 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
504 |
next |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
505 |
assume n_lt: "\<not> n \<ge> 0" thus ?thesis |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
506 |
proof (cases) |
68605 | 507 |
assume m_ge: "m \<ge> 0" |
508 |
have "inv x [^] (nat m * nat (- n)) = inv x [^] nat (- (m * n))" |
|
509 |
by (metis (full_types) m_ge mult_minus_right nat_mult_distrib) |
|
510 |
with m_ge n_lt show ?thesis |
|
511 |
by (simp add: int_pow_def2 mult_less_0_iff assms mult.commute nat_pow_inv nat_pow_pow) |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
512 |
next |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
513 |
assume m_lt: "\<not> m \<ge> 0" thus ?thesis |
68605 | 514 |
using n_lt by (auto simp: int_pow_def2 mult_less_0_iff assms nat_mult_distrib_neg nat_pow_inv nat_pow_pow) |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
515 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
516 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
517 |
|
61628 | 518 |
lemma (in group) int_pow_diff: |
67341
df79ef3b3a41
Renamed (^) to [^] in preparation of the move from "op X" to (X)
nipkow
parents:
67091
diff
changeset
|
519 |
"x \<in> carrier G \<Longrightarrow> x [^] (n - m :: int) = x [^] n \<otimes> inv (x [^] m)" |
68662 | 520 |
by(simp only: diff_conv_add_uminus int_pow_mult int_pow_neg) |
61628 | 521 |
|
522 |
lemma (in group) inj_on_multc: "c \<in> carrier G \<Longrightarrow> inj_on (\<lambda>x. x \<otimes> c) (carrier G)" |
|
68662 | 523 |
by(simp add: inj_on_def) |
61628 | 524 |
|
525 |
lemma (in group) inj_on_cmult: "c \<in> carrier G \<Longrightarrow> inj_on (\<lambda>x. c \<otimes> x) (carrier G)" |
|
68662 | 526 |
by(simp add: inj_on_def) |
61628 | 527 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
528 |
|
70019
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
529 |
lemma (in monoid) group_commutes_pow: |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
530 |
fixes n::nat |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
531 |
shows "\<lbrakk>x \<otimes> y = y \<otimes> x; x \<in> carrier G; y \<in> carrier G\<rbrakk> \<Longrightarrow> x [^] n \<otimes> y = y \<otimes> x [^] n" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
532 |
apply (induction n, auto) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
533 |
by (metis m_assoc nat_pow_closed) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
534 |
|
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
535 |
lemma (in monoid) pow_mult_distrib: |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
536 |
assumes eq: "x \<otimes> y = y \<otimes> x" and xy: "x \<in> carrier G" "y \<in> carrier G" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
537 |
shows "(x \<otimes> y) [^] (n::nat) = x [^] n \<otimes> y [^] n" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
538 |
proof (induct n) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
539 |
case (Suc n) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
540 |
have "x \<otimes> (y [^] n \<otimes> y) = y [^] n \<otimes> x \<otimes> y" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
541 |
by (simp add: eq group_commutes_pow m_assoc xy) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
542 |
then show ?case |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
543 |
using assms Suc.hyps m_assoc by auto |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
544 |
qed auto |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
545 |
|
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
546 |
lemma (in group) int_pow_mult_distrib: |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
547 |
assumes eq: "x \<otimes> y = y \<otimes> x" and xy: "x \<in> carrier G" "y \<in> carrier G" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
548 |
shows "(x \<otimes> y) [^] (i::int) = x [^] i \<otimes> y [^] i" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
549 |
proof (cases i rule: int_cases) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
550 |
case (nonneg n) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
551 |
then show ?thesis |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
552 |
by (metis eq int_pow_int pow_mult_distrib xy) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
553 |
next |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
554 |
case (neg n) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
555 |
then show ?thesis |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
556 |
unfolding neg |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
557 |
apply (simp add: xy int_pow_neg_int del: of_nat_Suc) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
558 |
by (metis eq inv_mult_group local.nat_pow_Suc nat_pow_closed pow_mult_distrib xy) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
559 |
qed |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
560 |
|
70030
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
561 |
lemma (in group) pow_eq_div2: |
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
562 |
fixes m n :: nat |
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
563 |
assumes x_car: "x \<in> carrier G" |
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
564 |
assumes pow_eq: "x [^] m = x [^] n" |
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
565 |
shows "x [^] (m - n) = \<one>" |
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
566 |
proof (cases "m < n") |
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
567 |
case False |
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
568 |
have "\<one> \<otimes> x [^] m = x [^] m" by (simp add: x_car) |
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
569 |
also have "\<dots> = x [^] (m - n) \<otimes> x [^] n" |
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
570 |
using False by (simp add: nat_pow_mult x_car) |
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
571 |
also have "\<dots> = x [^] (m - n) \<otimes> x [^] m" |
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
572 |
by (simp add: pow_eq) |
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
573 |
finally show ?thesis |
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
574 |
by (metis nat_pow_closed one_closed right_cancel x_car) |
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
575 |
qed simp |
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
576 |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
577 |
subsection \<open>Submonoids\<close> |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
578 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
579 |
locale submonoid = \<^marker>\<open>contributor \<open>Martin Baillon\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
580 |
fixes H and G (structure) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
581 |
assumes subset: "H \<subseteq> carrier G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
582 |
and m_closed [intro, simp]: "\<lbrakk>x \<in> H; y \<in> H\<rbrakk> \<Longrightarrow> x \<otimes> y \<in> H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
583 |
and one_closed [simp]: "\<one> \<in> H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
584 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
585 |
lemma (in submonoid) is_submonoid: \<^marker>\<open>contributor \<open>Martin Baillon\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
586 |
"submonoid H G" by (rule submonoid_axioms) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
587 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
588 |
lemma (in submonoid) mem_carrier [simp]: \<^marker>\<open>contributor \<open>Martin Baillon\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
589 |
"x \<in> H \<Longrightarrow> x \<in> carrier G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
590 |
using subset by blast |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
591 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
592 |
lemma (in submonoid) submonoid_is_monoid [intro]: \<^marker>\<open>contributor \<open>Martin Baillon\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
593 |
assumes "monoid G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
594 |
shows "monoid (G\<lparr>carrier := H\<rparr>)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
595 |
proof - |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
596 |
interpret monoid G by fact |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
597 |
show ?thesis |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
598 |
by (simp add: monoid_def m_assoc) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
599 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
600 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
601 |
lemma submonoid_nonempty: \<^marker>\<open>contributor \<open>Martin Baillon\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
602 |
"~ submonoid {} G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
603 |
by (blast dest: submonoid.one_closed) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
604 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
605 |
lemma (in submonoid) finite_monoid_imp_card_positive: \<^marker>\<open>contributor \<open>Martin Baillon\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
606 |
"finite (carrier G) ==> 0 < card H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
607 |
proof (rule classical) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
608 |
assume "finite (carrier G)" and a: "~ 0 < card H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
609 |
then have "finite H" by (blast intro: finite_subset [OF subset]) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
610 |
with is_submonoid a have "submonoid {} G" by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
611 |
with submonoid_nonempty show ?thesis by contradiction |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
612 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
613 |
|
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
614 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
615 |
lemma (in monoid) monoid_incl_imp_submonoid : \<^marker>\<open>contributor \<open>Martin Baillon\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
616 |
assumes "H \<subseteq> carrier G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
617 |
and "monoid (G\<lparr>carrier := H\<rparr>)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
618 |
shows "submonoid H G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
619 |
proof (intro submonoid.intro[OF assms(1)]) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
620 |
have ab_eq : "\<And> a b. a \<in> H \<Longrightarrow> b \<in> H \<Longrightarrow> a \<otimes>\<^bsub>G\<lparr>carrier := H\<rparr>\<^esub> b = a \<otimes> b" using assms by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
621 |
have "\<And>a b. a \<in> H \<Longrightarrow> b \<in> H \<Longrightarrow> a \<otimes> b \<in> carrier (G\<lparr>carrier := H\<rparr>) " |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
622 |
using assms ab_eq unfolding group_def using monoid.m_closed by fastforce |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
623 |
thus "\<And>a b. a \<in> H \<Longrightarrow> b \<in> H \<Longrightarrow> a \<otimes> b \<in> H" by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
624 |
show "\<one> \<in> H " using monoid.one_closed[OF assms(2)] assms by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
625 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
626 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
627 |
lemma (in monoid) inv_unique': \<^marker>\<open>contributor \<open>Martin Baillon\<close>\<close> |
68517 | 628 |
assumes "x \<in> carrier G" "y \<in> carrier G" |
629 |
shows "\<lbrakk> x \<otimes> y = \<one>; y \<otimes> x = \<one> \<rbrakk> \<Longrightarrow> y = inv x" |
|
630 |
proof - |
|
631 |
assume "x \<otimes> y = \<one>" and l_inv: "y \<otimes> x = \<one>" |
|
632 |
hence unit: "x \<in> Units G" |
|
633 |
using assms unfolding Units_def by auto |
|
634 |
show "y = inv x" |
|
635 |
using inv_unique[OF l_inv Units_r_inv[OF unit] assms Units_inv_closed[OF unit]] . |
|
636 |
qed |
|
637 |
||
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
638 |
lemma (in monoid) m_inv_monoid_consistent: \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68517 | 639 |
assumes "x \<in> Units (G \<lparr> carrier := H \<rparr>)" and "submonoid H G" |
640 |
shows "inv\<^bsub>(G \<lparr> carrier := H \<rparr>)\<^esub> x = inv x" |
|
641 |
proof - |
|
642 |
have monoid: "monoid (G \<lparr> carrier := H \<rparr>)" |
|
643 |
using submonoid.submonoid_is_monoid[OF assms(2) monoid_axioms] . |
|
644 |
obtain y where y: "y \<in> H" "x \<otimes> y = \<one>" "y \<otimes> x = \<one>" |
|
645 |
using assms(1) unfolding Units_def by auto |
|
646 |
have x: "x \<in> H" and in_carrier: "x \<in> carrier G" "y \<in> carrier G" |
|
647 |
using y(1) submonoid.subset[OF assms(2)] assms(1) unfolding Units_def by auto |
|
648 |
show ?thesis |
|
649 |
using monoid.inv_unique'[OF monoid, of x y] x y |
|
650 |
using inv_unique'[OF in_carrier y(2-3)] by auto |
|
651 |
qed |
|
652 |
||
61382 | 653 |
subsection \<open>Subgroups\<close> |
13813 | 654 |
|
19783 | 655 |
locale subgroup = |
656 |
fixes H and G (structure) |
|
14963 | 657 |
assumes subset: "H \<subseteq> carrier G" |
658 |
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
|
659 |
and one_closed [simp]: "\<one> \<in> H" |
14963 | 660 |
and m_inv_closed [intro,simp]: "x \<in> H \<Longrightarrow> inv x \<in> H" |
13813 | 661 |
|
20318
0e0ea63fe768
Restructured algebra library, added ideals and quotient rings.
ballarin
parents:
19984
diff
changeset
|
662 |
lemma (in subgroup) is_subgroup: |
26199 | 663 |
"subgroup H G" by (rule subgroup_axioms) |
20318
0e0ea63fe768
Restructured algebra library, added ideals and quotient rings.
ballarin
parents:
19984
diff
changeset
|
664 |
|
13813 | 665 |
declare (in subgroup) group.intro [intro] |
13949
0ce528cd6f19
HOL-Algebra complete for release Isabelle2003 (modulo section headers).
ballarin
parents:
13944
diff
changeset
|
666 |
|
14963 | 667 |
lemma (in subgroup) mem_carrier [simp]: |
668 |
"x \<in> H \<Longrightarrow> x \<in> carrier G" |
|
669 |
using subset by blast |
|
13813 | 670 |
|
14963 | 671 |
lemma (in subgroup) subgroup_is_group [intro]: |
27611 | 672 |
assumes "group G" |
673 |
shows "group (G\<lparr>carrier := H\<rparr>)" |
|
674 |
proof - |
|
29237 | 675 |
interpret group G by fact |
68458 | 676 |
have "Group.monoid (G\<lparr>carrier := H\<rparr>)" |
677 |
by (simp add: monoid_axioms submonoid.intro submonoid.submonoid_is_monoid subset) |
|
678 |
then show ?thesis |
|
679 |
by (rule monoid.group_l_invI) (auto intro: l_inv mem_carrier) |
|
27611 | 680 |
qed |
13813 | 681 |
|
68555
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
682 |
lemma subgroup_is_submonoid: |
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
683 |
assumes "subgroup H G" shows "submonoid H G" |
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
684 |
using assms by (auto intro: submonoid.intro simp add: subgroup_def) |
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
685 |
|
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
686 |
lemma (in group) subgroup_Units: |
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
687 |
assumes "subgroup H G" shows "H \<subseteq> Units (G \<lparr> carrier := H \<rparr>)" |
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
688 |
using group.Units[OF subgroup.subgroup_is_group[OF assms group_axioms]] by simp |
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
689 |
|
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
690 |
lemma (in group) m_inv_consistent [simp]: |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
691 |
assumes "subgroup H G" "x \<in> H" |
68555
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
692 |
shows "inv\<^bsub>(G \<lparr> carrier := H \<rparr>)\<^esub> x = inv x" |
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
693 |
using assms m_inv_monoid_consistent[OF _ subgroup_is_submonoid] subgroup_Units[of H] by auto |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
694 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
695 |
lemma (in group) int_pow_consistent: \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
696 |
assumes "subgroup H G" "x \<in> H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
697 |
shows "x [^] (n :: int) = x [^]\<^bsub>(G \<lparr> carrier := H \<rparr>)\<^esub> n" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
698 |
proof (cases) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
699 |
assume ge: "n \<ge> 0" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
700 |
hence "x [^] n = x [^] (nat n)" |
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
701 |
using int_pow_def2 [of G] by auto |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
702 |
also have " ... = x [^]\<^bsub>(G \<lparr> carrier := H \<rparr>)\<^esub> (nat n)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
703 |
using nat_pow_consistent by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
704 |
also have " ... = x [^]\<^bsub>(G \<lparr> carrier := H \<rparr>)\<^esub> n" |
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
705 |
by (metis ge int_nat_eq int_pow_int) |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
706 |
finally show ?thesis . |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
707 |
next |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
708 |
assume "\<not> n \<ge> 0" hence lt: "n < 0" by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
709 |
hence "x [^] n = inv (x [^] (nat (- n)))" |
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
710 |
using int_pow_def2 [of G] by auto |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
711 |
also have " ... = (inv x) [^] (nat (- n))" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
712 |
by (metis assms nat_pow_inv subgroup.mem_carrier) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
713 |
also have " ... = (inv\<^bsub>(G \<lparr> carrier := H \<rparr>)\<^esub> x) [^]\<^bsub>(G \<lparr> carrier := H \<rparr>)\<^esub> (nat (- n))" |
68555
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
714 |
using m_inv_consistent[OF assms] nat_pow_consistent by auto |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
715 |
also have " ... = inv\<^bsub>(G \<lparr> carrier := H \<rparr>)\<^esub> (x [^]\<^bsub>(G \<lparr> carrier := H \<rparr>)\<^esub> (nat (- n)))" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
716 |
using group.nat_pow_inv[OF subgroup.subgroup_is_group[OF assms(1) is_group]] assms(2) by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
717 |
also have " ... = x [^]\<^bsub>(G \<lparr> carrier := H \<rparr>)\<^esub> n" |
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
718 |
by (simp add: int_pow_def2 lt) |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
719 |
finally show ?thesis . |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
720 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
721 |
|
61382 | 722 |
text \<open> |
69597 | 723 |
Since \<^term>\<open>H\<close> is nonempty, it contains some element \<^term>\<open>x\<close>. Since |
63167 | 724 |
it is closed under inverse, it contains \<open>inv x\<close>. Since |
725 |
it is closed under product, it contains \<open>x \<otimes> inv x = \<one>\<close>. |
|
61382 | 726 |
\<close> |
13813 | 727 |
|
728 |
lemma (in group) one_in_subset: |
|
729 |
"[| 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 |] |
|
730 |
==> \<one> \<in> H" |
|
44472 | 731 |
by force |
13813 | 732 |
|
61382 | 733 |
text \<open>A characterization of subgroups: closed, non-empty subset.\<close> |
13813 | 734 |
|
735 |
lemma (in group) subgroupI: |
|
736 |
assumes subset: "H \<subseteq> carrier G" and non_empty: "H \<noteq> {}" |
|
14963 | 737 |
and inv: "!!a. a \<in> H \<Longrightarrow> inv a \<in> H" |
738 |
and mult: "!!a b. \<lbrakk>a \<in> H; b \<in> H\<rbrakk> \<Longrightarrow> a \<otimes> b \<in> H" |
|
13813 | 739 |
shows "subgroup H G" |
27714
27b4d7c01f8b
Tuned (for the sake of a meaningless log entry).
ballarin
parents:
27713
diff
changeset
|
740 |
proof (simp add: subgroup_def assms) |
27b4d7c01f8b
Tuned (for the sake of a meaningless log entry).
ballarin
parents:
27713
diff
changeset
|
741 |
show "\<one> \<in> H" by (rule one_in_subset) (auto simp only: assms) |
13813 | 742 |
qed |
743 |
||
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
744 |
lemma (in group) subgroupE: |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
745 |
assumes "subgroup H G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
746 |
shows "H \<subseteq> carrier G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
747 |
and "H \<noteq> {}" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
748 |
and "\<And>a. a \<in> H \<Longrightarrow> inv a \<in> H" |
68517 | 749 |
and "\<And>a b. \<lbrakk> a \<in> H; b \<in> H \<rbrakk> \<Longrightarrow> a \<otimes> b \<in> H" |
750 |
using assms unfolding subgroup_def[of H G] by auto |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
751 |
|
13936 | 752 |
declare monoid.one_closed [iff] group.inv_closed [simp] |
753 |
monoid.l_one [simp] monoid.r_one [simp] group.inv_inv [simp] |
|
13813 | 754 |
|
755 |
lemma subgroup_nonempty: |
|
67091 | 756 |
"\<not> subgroup {} G" |
13813 | 757 |
by (blast dest: subgroup.one_closed) |
758 |
||
68517 | 759 |
lemma (in subgroup) finite_imp_card_positive: "finite (carrier G) \<Longrightarrow> 0 < card H" |
760 |
using subset one_closed card_gt_0_iff finite_subset by blast |
|
13813 | 761 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
762 |
lemma (in subgroup) subgroup_is_submonoid : \<^marker>\<open>contributor \<open>Martin Baillon\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
763 |
"submonoid H G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
764 |
by (simp add: submonoid.intro subset) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
765 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
766 |
lemma (in group) submonoid_subgroupI : \<^marker>\<open>contributor \<open>Martin Baillon\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
767 |
assumes "submonoid H G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
768 |
and "\<And>a. a \<in> H \<Longrightarrow> inv a \<in> H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
769 |
shows "subgroup H G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
770 |
by (metis assms subgroup_def submonoid_def) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
771 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
772 |
lemma (in group) group_incl_imp_subgroup: \<^marker>\<open>contributor \<open>Martin Baillon\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
773 |
assumes "H \<subseteq> carrier G" |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
774 |
and "group (G\<lparr>carrier := H\<rparr>)" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
775 |
shows "subgroup H G" |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
776 |
proof (intro submonoid_subgroupI[OF monoid_incl_imp_submonoid[OF assms(1)]]) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
777 |
show "monoid (G\<lparr>carrier := H\<rparr>)" using group_def assms by blast |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
778 |
have ab_eq : "\<And> a b. a \<in> H \<Longrightarrow> b \<in> H \<Longrightarrow> a \<otimes>\<^bsub>G\<lparr>carrier := H\<rparr>\<^esub> b = a \<otimes> b" using assms by simp |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
779 |
fix a assume aH : "a \<in> H" |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
780 |
have " inv\<^bsub>G\<lparr>carrier := H\<rparr>\<^esub> a \<in> carrier G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
781 |
using assms aH group.inv_closed[OF assms(2)] by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
782 |
moreover have "\<one>\<^bsub>G\<lparr>carrier := H\<rparr>\<^esub> = \<one>" using assms monoid.one_closed ab_eq one_def by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
783 |
hence "a \<otimes>\<^bsub>G\<lparr>carrier := H\<rparr>\<^esub> inv\<^bsub>G\<lparr>carrier := H\<rparr>\<^esub> a= \<one>" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
784 |
using assms ab_eq aH group.r_inv[OF assms(2)] by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
785 |
hence "a \<otimes> inv\<^bsub>G\<lparr>carrier := H\<rparr>\<^esub> a= \<one>" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
786 |
using aH assms group.inv_closed[OF assms(2)] ab_eq by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
787 |
ultimately have "inv\<^bsub>G\<lparr>carrier := H\<rparr>\<^esub> a = inv a" |
68605 | 788 |
by (metis aH assms(1) contra_subsetD group.inv_inv is_group local.inv_equality) |
789 |
moreover have "inv\<^bsub>G\<lparr>carrier := H\<rparr>\<^esub> a \<in> H" |
|
790 |
using aH group.inv_closed[OF assms(2)] by auto |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
791 |
ultimately show "inv a \<in> H" by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
792 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
793 |
|
13936 | 794 |
|
61382 | 795 |
subsection \<open>Direct Products\<close> |
13813 | 796 |
|
35848
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
797 |
definition |
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
798 |
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
|
799 |
"G \<times>\<times> H = |
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
800 |
\<lparr>carrier = carrier G \<times> carrier H, |
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
801 |
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
|
802 |
one = (\<one>\<^bsub>G\<^esub>, \<one>\<^bsub>H\<^esub>)\<rparr>" |
13813 | 803 |
|
14963 | 804 |
lemma DirProd_monoid: |
27611 | 805 |
assumes "monoid G" and "monoid H" |
14963 | 806 |
shows "monoid (G \<times>\<times> H)" |
807 |
proof - |
|
30729
461ee3e49ad3
interpretation/interpret: prefixes are mandatory by default;
wenzelm
parents:
29240
diff
changeset
|
808 |
interpret G: monoid G by fact |
461ee3e49ad3
interpretation/interpret: prefixes are mandatory by default;
wenzelm
parents:
29240
diff
changeset
|
809 |
interpret H: monoid H by fact |
27714
27b4d7c01f8b
Tuned (for the sake of a meaningless log entry).
ballarin
parents:
27713
diff
changeset
|
810 |
from assms |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
811 |
show ?thesis by (unfold monoid_def DirProd_def, auto) |
14963 | 812 |
qed |
13813 | 813 |
|
814 |
||
61382 | 815 |
text\<open>Does not use the previous result because it's easier just to use auto.\<close> |
14963 | 816 |
lemma DirProd_group: |
27611 | 817 |
assumes "group G" and "group H" |
14963 | 818 |
shows "group (G \<times>\<times> H)" |
27611 | 819 |
proof - |
30729
461ee3e49ad3
interpretation/interpret: prefixes are mandatory by default;
wenzelm
parents:
29240
diff
changeset
|
820 |
interpret G: group G by fact |
461ee3e49ad3
interpretation/interpret: prefixes are mandatory by default;
wenzelm
parents:
29240
diff
changeset
|
821 |
interpret H: group H by fact |
27611 | 822 |
show ?thesis by (rule groupI) |
14963 | 823 |
(auto intro: G.m_assoc H.m_assoc G.l_inv H.l_inv |
824 |
simp add: DirProd_def) |
|
27611 | 825 |
qed |
13813 | 826 |
|
68662 | 827 |
lemma carrier_DirProd [simp]: "carrier (G \<times>\<times> H) = carrier G \<times> carrier H" |
14963 | 828 |
by (simp add: DirProd_def) |
13944 | 829 |
|
68662 | 830 |
lemma one_DirProd [simp]: "\<one>\<^bsub>G \<times>\<times> H\<^esub> = (\<one>\<^bsub>G\<^esub>, \<one>\<^bsub>H\<^esub>)" |
14963 | 831 |
by (simp add: DirProd_def) |
13944 | 832 |
|
68662 | 833 |
lemma mult_DirProd [simp]: "(g, h) \<otimes>\<^bsub>(G \<times>\<times> H)\<^esub> (g', h') = (g \<otimes>\<^bsub>G\<^esub> g', h \<otimes>\<^bsub>H\<^esub> h')" |
14963 | 834 |
by (simp add: DirProd_def) |
13944 | 835 |
|
70039
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
836 |
lemma mult_DirProd': "x \<otimes>\<^bsub>(G \<times>\<times> H)\<^esub> y = (fst x \<otimes>\<^bsub>G\<^esub> fst y, snd x \<otimes>\<^bsub>H\<^esub> snd y)" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
837 |
by (subst mult_DirProd [symmetric]) simp |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
838 |
|
68662 | 839 |
lemma DirProd_assoc: "(G \<times>\<times> H \<times>\<times> I) = (G \<times>\<times> (H \<times>\<times> I))" |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
840 |
by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
841 |
|
14963 | 842 |
lemma inv_DirProd [simp]: |
27611 | 843 |
assumes "group G" and "group H" |
13944 | 844 |
assumes g: "g \<in> carrier G" |
845 |
and h: "h \<in> carrier H" |
|
14963 | 846 |
shows "m_inv (G \<times>\<times> H) (g, h) = (inv\<^bsub>G\<^esub> g, inv\<^bsub>H\<^esub> h)" |
27611 | 847 |
proof - |
30729
461ee3e49ad3
interpretation/interpret: prefixes are mandatory by default;
wenzelm
parents:
29240
diff
changeset
|
848 |
interpret G: group G by fact |
461ee3e49ad3
interpretation/interpret: prefixes are mandatory by default;
wenzelm
parents:
29240
diff
changeset
|
849 |
interpret H: group H by fact |
461ee3e49ad3
interpretation/interpret: prefixes are mandatory by default;
wenzelm
parents:
29240
diff
changeset
|
850 |
interpret Prod: group "G \<times>\<times> H" |
27714
27b4d7c01f8b
Tuned (for the sake of a meaningless log entry).
ballarin
parents:
27713
diff
changeset
|
851 |
by (auto intro: DirProd_group group.intro group.axioms assms) |
14963 | 852 |
show ?thesis by (simp add: Prod.inv_equality g h) |
853 |
qed |
|
27698 | 854 |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
855 |
lemma DirProd_subgroups : |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
856 |
assumes "group G" |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
857 |
and "subgroup H G" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
858 |
and "group K" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
859 |
and "subgroup I K" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
860 |
shows "subgroup (H \<times> I) (G \<times>\<times> K)" |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
861 |
proof (intro group.group_incl_imp_subgroup[OF DirProd_group[OF assms(1)assms(3)]]) |
68687 | 862 |
have "H \<subseteq> carrier G" "I \<subseteq> carrier K" using subgroup.subset assms by blast+ |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
863 |
thus "(H \<times> I) \<subseteq> carrier (G \<times>\<times> K)" unfolding DirProd_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
864 |
have "Group.group ((G\<lparr>carrier := H\<rparr>) \<times>\<times> (K\<lparr>carrier := I\<rparr>))" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
865 |
using DirProd_group[OF subgroup.subgroup_is_group[OF assms(2)assms(1)] |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
866 |
subgroup.subgroup_is_group[OF assms(4)assms(3)]]. |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
867 |
moreover have "((G\<lparr>carrier := H\<rparr>) \<times>\<times> (K\<lparr>carrier := I\<rparr>)) = ((G \<times>\<times> K)\<lparr>carrier := H \<times> I\<rparr>)" |
68687 | 868 |
unfolding DirProd_def using assms by simp |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
869 |
ultimately show "Group.group ((G \<times>\<times> K)\<lparr>carrier := H \<times> I\<rparr>)" by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
870 |
qed |
14963 | 871 |
|
70039
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
872 |
subsection \<open>Homomorphisms (mono and epi) and Isomorphisms\<close> |
13813 | 873 |
|
35847 | 874 |
definition |
875 |
hom :: "_ => _ => ('a => 'b) set" where |
|
35848
5443079512ea
slightly more uniform definitions -- eliminated old-style meta-equality;
wenzelm
parents:
35847
diff
changeset
|
876 |
"hom G H = |
67091 | 877 |
{h. h \<in> carrier G \<rightarrow> carrier H \<and> |
14693 | 878 |
(\<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 | 879 |
|
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
880 |
lemma homI: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
881 |
"\<lbrakk>\<And>x. x \<in> carrier G \<Longrightarrow> h x \<in> carrier H; |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
882 |
\<And>x y. \<lbrakk>x \<in> carrier G; y \<in> carrier G\<rbrakk> \<Longrightarrow> h (x \<otimes>\<^bsub>G\<^esub> y) = h x \<otimes>\<^bsub>H\<^esub> h y\<rbrakk> \<Longrightarrow> h \<in> hom G H" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
883 |
by (auto simp: hom_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
884 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
885 |
lemma hom_carrier: "h \<in> hom G H \<Longrightarrow> h ` carrier G \<subseteq> carrier H" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
886 |
by (auto simp: hom_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
887 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
888 |
lemma hom_in_carrier: "\<lbrakk>h \<in> hom G H; x \<in> carrier G\<rbrakk> \<Longrightarrow> h x \<in> carrier H" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
889 |
by (auto simp: hom_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
890 |
|
69700
7a92cbec7030
new material about summations and powers, along with some tweaks
paulson <lp15@cam.ac.uk>
parents:
69597
diff
changeset
|
891 |
lemma hom_compose: |
69122
1b5178abaf97
updates to Algebra from Baillon and de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68687
diff
changeset
|
892 |
"\<lbrakk> f \<in> hom G H; g \<in> hom H I \<rbrakk> \<Longrightarrow> g \<circ> f \<in> hom G I" |
1b5178abaf97
updates to Algebra from Baillon and de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68687
diff
changeset
|
893 |
unfolding hom_def by (auto simp add: Pi_iff) |
1b5178abaf97
updates to Algebra from Baillon and de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68687
diff
changeset
|
894 |
|
1b5178abaf97
updates to Algebra from Baillon and de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68687
diff
changeset
|
895 |
lemma (in group) hom_restrict: |
1b5178abaf97
updates to Algebra from Baillon and de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68687
diff
changeset
|
896 |
assumes "h \<in> hom G H" and "\<And>g. g \<in> carrier G \<Longrightarrow> h g = t g" shows "t \<in> hom G H" |
1b5178abaf97
updates to Algebra from Baillon and de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68687
diff
changeset
|
897 |
using assms unfolding hom_def by (auto simp add: Pi_iff) |
1b5178abaf97
updates to Algebra from Baillon and de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68687
diff
changeset
|
898 |
|
14761 | 899 |
lemma (in group) hom_compose: |
31754 | 900 |
"[|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
|
901 |
by (fastforce simp add: hom_def compose_def) |
13943 | 902 |
|
70027
94494b92d8d0
some new group theory results: integer group, trivial group, etc.
paulson <lp15@cam.ac.uk>
parents:
70019
diff
changeset
|
903 |
lemma (in group) restrict_hom_iff [simp]: |
94494b92d8d0
some new group theory results: integer group, trivial group, etc.
paulson <lp15@cam.ac.uk>
parents:
70019
diff
changeset
|
904 |
"(\<lambda>x. if x \<in> carrier G then f x else g x) \<in> hom G H \<longleftrightarrow> f \<in> hom G H" |
94494b92d8d0
some new group theory results: integer group, trivial group, etc.
paulson <lp15@cam.ac.uk>
parents:
70019
diff
changeset
|
905 |
by (simp add: hom_def Pi_iff) |
94494b92d8d0
some new group theory results: integer group, trivial group, etc.
paulson <lp15@cam.ac.uk>
parents:
70019
diff
changeset
|
906 |
|
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
907 |
definition iso :: "_ => _ => ('a => 'b) set" |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
908 |
where "iso G H = {h. h \<in> hom G H \<and> bij_betw h (carrier G) (carrier H)}" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
909 |
|
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
910 |
definition is_iso :: "_ \<Rightarrow> _ \<Rightarrow> bool" (infixr "\<cong>" 60) |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
911 |
where "G \<cong> H = (iso G H \<noteq> {})" |
14761 | 912 |
|
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
913 |
definition mon where "mon G H = {f \<in> hom G H. inj_on f (carrier G)}" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
914 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
915 |
definition epi where "epi G H = {f \<in> hom G H. f ` (carrier G) = carrier H}" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
916 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
917 |
lemma isoI: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
918 |
"\<lbrakk>h \<in> hom G H; bij_betw h (carrier G) (carrier H)\<rbrakk> \<Longrightarrow> h \<in> iso G H" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
919 |
by (auto simp: iso_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
920 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
921 |
lemma epi_iff_subset: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
922 |
"f \<in> epi G G' \<longleftrightarrow> f \<in> hom G G' \<and> carrier G' \<subseteq> f ` carrier G" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
923 |
by (auto simp: epi_def hom_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
924 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
925 |
lemma iso_iff_mon_epi: "f \<in> iso G H \<longleftrightarrow> f \<in> mon G H \<and> f \<in> epi G H" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
926 |
by (auto simp: iso_def mon_def epi_def bij_betw_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
927 |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
928 |
lemma iso_set_refl: "(\<lambda>x. x) \<in> iso G G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
929 |
by (simp add: iso_def hom_def inj_on_def bij_betw_def Pi_def) |
14761 | 930 |
|
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
931 |
lemma id_iso: "id \<in> iso G G" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
932 |
by (simp add: iso_def hom_def inj_on_def bij_betw_def Pi_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
933 |
|
70019
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
934 |
corollary iso_refl [simp]: "G \<cong> G" |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
935 |
using iso_set_refl unfolding is_iso_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
936 |
|
70039
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
937 |
lemma iso_iff: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
938 |
"h \<in> iso G H \<longleftrightarrow> h \<in> hom G H \<and> h ` (carrier G) = carrier H \<and> inj_on h (carrier G)" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
939 |
by (auto simp: iso_def hom_def bij_betw_def) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
940 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
941 |
lemma iso_imp_homomorphism: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
942 |
"h \<in> iso G H \<Longrightarrow> h \<in> hom G H" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
943 |
by (simp add: iso_iff) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
944 |
|
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
945 |
lemma trivial_hom: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
946 |
"group H \<Longrightarrow> (\<lambda>x. one H) \<in> hom G H" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
947 |
by (auto simp: hom_def Group.group_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
948 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
949 |
lemma (in group) hom_eq: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
950 |
assumes "f \<in> hom G H" "\<And>x. x \<in> carrier G \<Longrightarrow> f' x = f x" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
951 |
shows "f' \<in> hom G H" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
952 |
using assms by (auto simp: hom_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
953 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
954 |
lemma (in group) iso_eq: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
955 |
assumes "f \<in> iso G H" "\<And>x. x \<in> carrier G \<Longrightarrow> f' x = f x" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
956 |
shows "f' \<in> iso G H" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
957 |
using assms by (fastforce simp: iso_def inj_on_def bij_betw_def hom_eq image_iff) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
958 |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
959 |
lemma (in group) iso_set_sym: |
68458 | 960 |
assumes "h \<in> iso G H" |
961 |
shows "inv_into (carrier G) h \<in> iso H G" |
|
962 |
proof - |
|
963 |
have h: "h \<in> hom G H" "bij_betw h (carrier G) (carrier H)" |
|
964 |
using assms by (auto simp add: iso_def bij_betw_inv_into) |
|
965 |
then have HG: "bij_betw (inv_into (carrier G) h) (carrier H) (carrier G)" |
|
966 |
by (simp add: bij_betw_inv_into) |
|
967 |
have "inv_into (carrier G) h \<in> hom H G" |
|
968 |
unfolding hom_def |
|
969 |
proof safe |
|
970 |
show *: "\<And>x. x \<in> carrier H \<Longrightarrow> inv_into (carrier G) h x \<in> carrier G" |
|
971 |
by (meson HG bij_betwE) |
|
972 |
show "inv_into (carrier G) h (x \<otimes>\<^bsub>H\<^esub> y) = inv_into (carrier G) h x \<otimes> inv_into (carrier G) h y" |
|
973 |
if "x \<in> carrier H" "y \<in> carrier H" for x y |
|
974 |
proof (rule inv_into_f_eq) |
|
975 |
show "inj_on h (carrier G)" |
|
976 |
using bij_betw_def h(2) by blast |
|
977 |
show "inv_into (carrier G) h x \<otimes> inv_into (carrier G) h y \<in> carrier G" |
|
978 |
by (simp add: * that) |
|
979 |
show "h (inv_into (carrier G) h x \<otimes> inv_into (carrier G) h y) = x \<otimes>\<^bsub>H\<^esub> y" |
|
980 |
using h bij_betw_inv_into_right [of h] unfolding hom_def by (simp add: "*" that) |
|
981 |
qed |
|
982 |
qed |
|
983 |
then show ?thesis |
|
984 |
by (simp add: Group.iso_def bij_betw_inv_into h) |
|
985 |
qed |
|
14761 | 986 |
|
68458 | 987 |
corollary (in group) iso_sym: "G \<cong> H \<Longrightarrow> H \<cong> G" |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
988 |
using iso_set_sym unfolding is_iso_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
989 |
|
70019
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
990 |
lemma iso_set_trans: |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
991 |
"\<lbrakk>h \<in> Group.iso G H; i \<in> Group.iso H I\<rbrakk> \<Longrightarrow> i \<circ> h \<in> Group.iso G I" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
992 |
by (force simp: iso_def hom_compose intro: bij_betw_trans) |
14761 | 993 |
|
70019
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
994 |
corollary iso_trans [trans]: "\<lbrakk>G \<cong> H ; H \<cong> I\<rbrakk> \<Longrightarrow> G \<cong> I" |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
995 |
using iso_set_trans unfolding is_iso_def by blast |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
996 |
|
69122
1b5178abaf97
updates to Algebra from Baillon and de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68687
diff
changeset
|
997 |
lemma iso_same_card: "G \<cong> H \<Longrightarrow> card (carrier G) = card (carrier H)" |
1b5178abaf97
updates to Algebra from Baillon and de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68687
diff
changeset
|
998 |
using bij_betw_same_card unfolding is_iso_def iso_def by auto |
1b5178abaf97
updates to Algebra from Baillon and de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68687
diff
changeset
|
999 |
|
70039
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1000 |
lemma iso_finite: "G \<cong> H \<Longrightarrow> finite(carrier G) \<longleftrightarrow> finite(carrier H)" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1001 |
by (auto simp: is_iso_def iso_def bij_betw_finite) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1002 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1003 |
lemma mon_compose: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1004 |
"\<lbrakk>f \<in> mon G H; g \<in> mon H K\<rbrakk> \<Longrightarrow> (g \<circ> f) \<in> mon G K" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1005 |
by (auto simp: mon_def intro: hom_compose comp_inj_on inj_on_subset [OF _ hom_carrier]) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1006 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1007 |
lemma mon_compose_rev: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1008 |
"\<lbrakk>f \<in> hom G H; g \<in> hom H K; (g \<circ> f) \<in> mon G K\<rbrakk> \<Longrightarrow> f \<in> mon G H" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1009 |
using inj_on_imageI2 by (auto simp: mon_def) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1010 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1011 |
lemma epi_compose: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1012 |
"\<lbrakk>f \<in> epi G H; g \<in> epi H K\<rbrakk> \<Longrightarrow> (g \<circ> f) \<in> epi G K" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1013 |
using hom_compose by (force simp: epi_def hom_compose simp flip: image_image) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1014 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1015 |
lemma epi_compose_rev: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1016 |
"\<lbrakk>f \<in> hom G H; g \<in> hom H K; (g \<circ> f) \<in> epi G K\<rbrakk> \<Longrightarrow> g \<in> epi H K" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1017 |
by (fastforce simp: epi_def hom_def Pi_iff image_def set_eq_iff) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1018 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1019 |
lemma iso_compose_rev: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1020 |
"\<lbrakk>f \<in> hom G H; g \<in> hom H K; (g \<circ> f) \<in> iso G K\<rbrakk> \<Longrightarrow> f \<in> mon G H \<and> g \<in> epi H K" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1021 |
unfolding iso_iff_mon_epi using mon_compose_rev epi_compose_rev by blast |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1022 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1023 |
lemma epi_iso_compose_rev: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1024 |
assumes "f \<in> epi G H" "g \<in> hom H K" "(g \<circ> f) \<in> iso G K" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1025 |
shows "f \<in> iso G H \<and> g \<in> iso H K" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1026 |
proof |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1027 |
show "f \<in> iso G H" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1028 |
by (metis (no_types, lifting) assms epi_def iso_compose_rev iso_iff_mon_epi mem_Collect_eq) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1029 |
then have "f \<in> hom G H \<and> bij_betw f (carrier G) (carrier H)" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1030 |
using Group.iso_def \<open>f \<in> Group.iso G H\<close> by blast |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1031 |
then have "bij_betw g (carrier H) (carrier K)" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1032 |
using Group.iso_def assms(3) bij_betw_comp_iff by blast |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1033 |
then show "g \<in> iso H K" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1034 |
using Group.iso_def assms(2) by blast |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1035 |
qed |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1036 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1037 |
lemma mon_left_invertible: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1038 |
"\<lbrakk>f \<in> hom G H; \<And>x. x \<in> carrier G \<Longrightarrow> g(f x) = x\<rbrakk> \<Longrightarrow> f \<in> mon G H" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1039 |
by (simp add: mon_def inj_on_def) metis |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1040 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1041 |
lemma epi_right_invertible: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1042 |
"\<lbrakk>g \<in> hom H G; f \<in> carrier G \<rightarrow> carrier H; \<And>x. x \<in> carrier G \<Longrightarrow> g(f x) = x\<rbrakk> \<Longrightarrow> g \<in> epi H G" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1043 |
by (force simp: Pi_iff epi_iff_subset image_subset_iff_funcset subset_iff) |
69122
1b5178abaf97
updates to Algebra from Baillon and de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68687
diff
changeset
|
1044 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
1045 |
lemma (in monoid) hom_imp_img_monoid: \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1046 |
assumes "h \<in> hom G H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1047 |
shows "monoid (H \<lparr> carrier := h ` (carrier G), one := h \<one>\<^bsub>G\<^esub> \<rparr>)" (is "monoid ?h_img") |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1048 |
proof (rule monoidI) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1049 |
show "\<one>\<^bsub>?h_img\<^esub> \<in> carrier ?h_img" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1050 |
by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1051 |
next |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1052 |
fix x y z assume "x \<in> carrier ?h_img" "y \<in> carrier ?h_img" "z \<in> carrier ?h_img" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1053 |
then obtain g1 g2 g3 |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1054 |
where g1: "g1 \<in> carrier G" "x = h g1" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1055 |
and g2: "g2 \<in> carrier G" "y = h g2" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1056 |
and g3: "g3 \<in> carrier G" "z = h g3" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1057 |
using image_iff[where ?f = h and ?A = "carrier G"] by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1058 |
have aux_lemma: |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1059 |
"\<And>a b. \<lbrakk> a \<in> carrier G; b \<in> carrier G \<rbrakk> \<Longrightarrow> h a \<otimes>\<^bsub>(?h_img)\<^esub> h b = h (a \<otimes> b)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1060 |
using assms unfolding hom_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1061 |
|
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1062 |
show "x \<otimes>\<^bsub>(?h_img)\<^esub> \<one>\<^bsub>(?h_img)\<^esub> = x" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1063 |
using aux_lemma[OF g1(1) one_closed] g1(2) r_one[OF g1(1)] by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1064 |
|
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1065 |
show "\<one>\<^bsub>(?h_img)\<^esub> \<otimes>\<^bsub>(?h_img)\<^esub> x = x" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1066 |
using aux_lemma[OF one_closed g1(1)] g1(2) l_one[OF g1(1)] by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1067 |
|
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1068 |
have "x \<otimes>\<^bsub>(?h_img)\<^esub> y = h (g1 \<otimes> g2)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1069 |
using aux_lemma g1 g2 by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1070 |
thus "x \<otimes>\<^bsub>(?h_img)\<^esub> y \<in> carrier ?h_img" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1071 |
using g1(1) g2(1) by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1072 |
|
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1073 |
have "(x \<otimes>\<^bsub>(?h_img)\<^esub> y) \<otimes>\<^bsub>(?h_img)\<^esub> z = h ((g1 \<otimes> g2) \<otimes> g3)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1074 |
using aux_lemma g1 g2 g3 by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1075 |
also have " ... = h (g1 \<otimes> (g2 \<otimes> g3))" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1076 |
using m_assoc[OF g1(1) g2(1) g3(1)] by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1077 |
also have " ... = x \<otimes>\<^bsub>(?h_img)\<^esub> (y \<otimes>\<^bsub>(?h_img)\<^esub> z)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1078 |
using aux_lemma g1 g2 g3 by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1079 |
finally show "(x \<otimes>\<^bsub>(?h_img)\<^esub> y) \<otimes>\<^bsub>(?h_img)\<^esub> z = x \<otimes>\<^bsub>(?h_img)\<^esub> (y \<otimes>\<^bsub>(?h_img)\<^esub> z)" . |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1080 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1081 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
1082 |
lemma (in group) hom_imp_img_group: \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1083 |
assumes "h \<in> hom G H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1084 |
shows "group (H \<lparr> carrier := h ` (carrier G), one := h \<one>\<^bsub>G\<^esub> \<rparr>)" (is "group ?h_img") |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1085 |
proof - |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1086 |
interpret monoid ?h_img |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1087 |
using hom_imp_img_monoid[OF assms] . |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1088 |
|
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1089 |
show ?thesis |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1090 |
proof (unfold_locales) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1091 |
show "carrier ?h_img \<subseteq> Units ?h_img" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1092 |
proof (auto simp add: Units_def) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1093 |
have aux_lemma: |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1094 |
"\<And>g1 g2. \<lbrakk> g1 \<in> carrier G; g2 \<in> carrier G \<rbrakk> \<Longrightarrow> h g1 \<otimes>\<^bsub>H\<^esub> h g2 = h (g1 \<otimes> g2)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1095 |
using assms unfolding hom_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1096 |
|
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1097 |
fix g1 assume g1: "g1 \<in> carrier G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1098 |
thus "\<exists>g2 \<in> carrier G. (h g2) \<otimes>\<^bsub>H\<^esub> (h g1) = h \<one> \<and> (h g1) \<otimes>\<^bsub>H\<^esub> (h g2) = h \<one>" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1099 |
using aux_lemma[OF g1 inv_closed[OF g1]] |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1100 |
aux_lemma[OF inv_closed[OF g1] g1] |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1101 |
inv_closed by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1102 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1103 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1104 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1105 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
1106 |
lemma (in group) iso_imp_group: \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1107 |
assumes "G \<cong> H" and "monoid H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1108 |
shows "group H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1109 |
proof - |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1110 |
obtain \<phi> where phi: "\<phi> \<in> iso G H" "inv_into (carrier G) \<phi> \<in> iso H G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1111 |
using iso_set_sym assms unfolding is_iso_def by blast |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1112 |
define \<psi> where psi_def: "\<psi> = inv_into (carrier G) \<phi>" |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1113 |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1114 |
have surj: "\<phi> ` (carrier G) = (carrier H)" "\<psi> ` (carrier H) = (carrier G)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1115 |
and inj: "inj_on \<phi> (carrier G)" "inj_on \<psi> (carrier H)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1116 |
and phi_hom: "\<And>g1 g2. \<lbrakk> g1 \<in> carrier G; g2 \<in> carrier G \<rbrakk> \<Longrightarrow> \<phi> (g1 \<otimes> g2) = (\<phi> g1) \<otimes>\<^bsub>H\<^esub> (\<phi> g2)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1117 |
and psi_hom: "\<And>h1 h2. \<lbrakk> h1 \<in> carrier H; h2 \<in> carrier H \<rbrakk> \<Longrightarrow> \<psi> (h1 \<otimes>\<^bsub>H\<^esub> h2) = (\<psi> h1) \<otimes> (\<psi> h2)" |
68662 | 1118 |
using phi psi_def unfolding iso_def bij_betw_def hom_def by auto |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1119 |
|
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1120 |
have phi_one: "\<phi> \<one> = \<one>\<^bsub>H\<^esub>" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1121 |
proof - |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1122 |
have "(\<phi> \<one>) \<otimes>\<^bsub>H\<^esub> \<one>\<^bsub>H\<^esub> = (\<phi> \<one>) \<otimes>\<^bsub>H\<^esub> (\<phi> \<one>)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1123 |
by (metis assms(2) image_eqI monoid.r_one one_closed phi_hom r_one surj(1)) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1124 |
thus ?thesis |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1125 |
by (metis (no_types, hide_lams) Units_eq Units_one_closed assms(2) f_inv_into_f imageI |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1126 |
monoid.l_one monoid.one_closed phi_hom psi_def r_one surj) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1127 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1128 |
|
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1129 |
have "carrier H \<subseteq> Units H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1130 |
proof |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1131 |
fix h assume h: "h \<in> carrier H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1132 |
let ?inv_h = "\<phi> (inv (\<psi> h))" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1133 |
have "h \<otimes>\<^bsub>H\<^esub> ?inv_h = \<phi> (\<psi> h) \<otimes>\<^bsub>H\<^esub> ?inv_h" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1134 |
by (simp add: f_inv_into_f h psi_def surj(1)) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1135 |
also have " ... = \<phi> ((\<psi> h) \<otimes> inv (\<psi> h))" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1136 |
by (metis h imageI inv_closed phi_hom surj(2)) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1137 |
also have " ... = \<phi> \<one>" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1138 |
by (simp add: h inv_into_into psi_def surj(1)) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1139 |
finally have 1: "h \<otimes>\<^bsub>H\<^esub> ?inv_h = \<one>\<^bsub>H\<^esub>" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1140 |
using phi_one by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1141 |
|
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1142 |
have "?inv_h \<otimes>\<^bsub>H\<^esub> h = ?inv_h \<otimes>\<^bsub>H\<^esub> \<phi> (\<psi> h)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1143 |
by (simp add: f_inv_into_f h psi_def surj(1)) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1144 |
also have " ... = \<phi> (inv (\<psi> h) \<otimes> (\<psi> h))" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1145 |
by (metis h imageI inv_closed phi_hom surj(2)) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1146 |
also have " ... = \<phi> \<one>" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1147 |
by (simp add: h inv_into_into psi_def surj(1)) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1148 |
finally have 2: "?inv_h \<otimes>\<^bsub>H\<^esub> h = \<one>\<^bsub>H\<^esub>" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1149 |
using phi_one by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1150 |
|
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1151 |
thus "h \<in> Units H" unfolding Units_def using 1 2 h surj by fastforce |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1152 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1153 |
thus ?thesis unfolding group_def group_axioms_def using assms(2) by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1154 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1155 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
1156 |
corollary (in group) iso_imp_img_group: \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1157 |
assumes "h \<in> iso G H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1158 |
shows "group (H \<lparr> one := h \<one> \<rparr>)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1159 |
proof - |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1160 |
let ?h_img = "H \<lparr> carrier := h ` (carrier G), one := h \<one> \<rparr>" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1161 |
have "h \<in> iso G ?h_img" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1162 |
using assms unfolding iso_def hom_def bij_betw_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1163 |
hence "G \<cong> ?h_img" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1164 |
unfolding is_iso_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1165 |
hence "group ?h_img" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1166 |
using iso_imp_group[of ?h_img] hom_imp_img_monoid[of h H] assms unfolding iso_def by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1167 |
moreover have "carrier H = carrier ?h_img" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1168 |
using assms unfolding iso_def bij_betw_def by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1169 |
hence "H \<lparr> one := h \<one> \<rparr> = ?h_img" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1170 |
by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1171 |
ultimately show ?thesis by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1172 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1173 |
|
70039
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1174 |
subsubsection \<open>HOL Light's concept of an isomorphism pair\<close> |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1175 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1176 |
definition group_isomorphisms |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1177 |
where |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1178 |
"group_isomorphisms G H f g \<equiv> |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1179 |
f \<in> hom G H \<and> g \<in> hom H G \<and> |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1180 |
(\<forall>x \<in> carrier G. g(f x) = x) \<and> |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1181 |
(\<forall>y \<in> carrier H. f(g y) = y)" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1182 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1183 |
lemma group_isomorphisms_sym: "group_isomorphisms G H f g \<Longrightarrow> group_isomorphisms H G g f" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1184 |
by (auto simp: group_isomorphisms_def) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1185 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1186 |
lemma group_isomorphisms_imp_iso: "group_isomorphisms G H f g \<Longrightarrow> f \<in> iso G H" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1187 |
by (auto simp: iso_def inj_on_def image_def group_isomorphisms_def hom_def bij_betw_def Pi_iff, metis+) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1188 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1189 |
lemma (in group) iso_iff_group_isomorphisms: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1190 |
"f \<in> iso G H \<longleftrightarrow> (\<exists>g. group_isomorphisms G H f g)" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1191 |
proof safe |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1192 |
show "\<exists>g. group_isomorphisms G H f g" if "f \<in> Group.iso G H" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1193 |
unfolding group_isomorphisms_def |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1194 |
proof (intro exI conjI) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1195 |
let ?g = "inv_into (carrier G) f" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1196 |
show "\<forall>x\<in>carrier G. ?g (f x) = x" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1197 |
by (metis (no_types, lifting) Group.iso_def bij_betw_inv_into_left mem_Collect_eq that) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1198 |
show "\<forall>y\<in>carrier H. f (?g y) = y" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1199 |
by (metis (no_types, lifting) Group.iso_def bij_betw_inv_into_right mem_Collect_eq that) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1200 |
qed (use Group.iso_def iso_set_sym that in \<open>blast+\<close>) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1201 |
next |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1202 |
fix g |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1203 |
assume "group_isomorphisms G H f g" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1204 |
then show "f \<in> Group.iso G H" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1205 |
by (auto simp: iso_def group_isomorphisms_def hom_in_carrier intro: bij_betw_byWitness) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1206 |
qed |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1207 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1208 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1209 |
subsubsection \<open>Involving direct products\<close> |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1210 |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1211 |
lemma DirProd_commute_iso_set: |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1212 |
shows "(\<lambda>(x,y). (y,x)) \<in> iso (G \<times>\<times> H) (H \<times>\<times> G)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1213 |
by (auto simp add: iso_def hom_def inj_on_def bij_betw_def) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1214 |
|
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1215 |
corollary DirProd_commute_iso : |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1216 |
"(G \<times>\<times> H) \<cong> (H \<times>\<times> G)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1217 |
using DirProd_commute_iso_set unfolding is_iso_def by blast |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1218 |
|
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1219 |
lemma DirProd_assoc_iso_set: |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1220 |
shows "(\<lambda>(x,y,z). (x,(y,z))) \<in> iso (G \<times>\<times> H \<times>\<times> I) (G \<times>\<times> (H \<times>\<times> I))" |
31754 | 1221 |
by (auto simp add: iso_def hom_def inj_on_def bij_betw_def) |
14761 | 1222 |
|
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1223 |
lemma (in group) DirProd_iso_set_trans: |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1224 |
assumes "g \<in> iso G G2" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1225 |
and "h \<in> iso H I" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1226 |
shows "(\<lambda>(x,y). (g x, h y)) \<in> iso (G \<times>\<times> H) (G2 \<times>\<times> I)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1227 |
proof- |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1228 |
have "(\<lambda>(x,y). (g x, h y)) \<in> hom (G \<times>\<times> H) (G2 \<times>\<times> I)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1229 |
using assms unfolding iso_def hom_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1230 |
moreover have " inj_on (\<lambda>(x,y). (g x, h y)) (carrier (G \<times>\<times> H))" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1231 |
using assms unfolding iso_def DirProd_def bij_betw_def inj_on_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1232 |
moreover have "(\<lambda>(x, y). (g x, h y)) ` carrier (G \<times>\<times> H) = carrier (G2 \<times>\<times> I)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1233 |
using assms unfolding iso_def bij_betw_def image_def DirProd_def by fastforce |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1234 |
ultimately show "(\<lambda>(x,y). (g x, h y)) \<in> iso (G \<times>\<times> H) (G2 \<times>\<times> I)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1235 |
unfolding iso_def bij_betw_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1236 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1237 |
|
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1238 |
corollary (in group) DirProd_iso_trans : |
68662 | 1239 |
assumes "G \<cong> G2" and "H \<cong> I" |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1240 |
shows "G \<times>\<times> H \<cong> G2 \<times>\<times> I" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1241 |
using DirProd_iso_set_trans assms unfolding is_iso_def by blast |
14761 | 1242 |
|
70039
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1243 |
lemma hom_pairwise: "f \<in> hom G (DirProd H K) \<longleftrightarrow> (fst \<circ> f) \<in> hom G H \<and> (snd \<circ> f) \<in> hom G K" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1244 |
apply (auto simp: hom_def mult_DirProd' dest: Pi_mem) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1245 |
apply (metis Product_Type.mem_Times_iff comp_eq_dest_lhs funcset_mem) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1246 |
by (metis mult_DirProd prod.collapse) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1247 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1248 |
lemma hom_paired: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1249 |
"(\<lambda>x. (f x,g x)) \<in> hom G (DirProd H K) \<longleftrightarrow> f \<in> hom G H \<and> g \<in> hom G K" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1250 |
by (simp add: hom_pairwise o_def) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1251 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1252 |
lemma hom_paired2: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1253 |
assumes "group G" "group H" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1254 |
shows "(\<lambda>(x,y). (f x,g y)) \<in> hom (DirProd G H) (DirProd G' H') \<longleftrightarrow> f \<in> hom G G' \<and> g \<in> hom H H'" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1255 |
using assms |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1256 |
by (fastforce simp: hom_def Pi_def dest!: group.is_monoid) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1257 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1258 |
lemma iso_paired2: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1259 |
assumes "group G" "group H" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1260 |
shows "(\<lambda>(x,y). (f x,g y)) \<in> iso (DirProd G H) (DirProd G' H') \<longleftrightarrow> f \<in> iso G G' \<and> g \<in> iso H H'" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1261 |
using assms |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1262 |
by (fastforce simp add: iso_def inj_on_def bij_betw_def hom_paired2 image_paired_Times |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1263 |
times_eq_iff group_def monoid.carrier_not_empty) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1264 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1265 |
lemma hom_of_fst: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1266 |
assumes "group H" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1267 |
shows "(f \<circ> fst) \<in> hom (DirProd G H) K \<longleftrightarrow> f \<in> hom G K" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1268 |
proof - |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1269 |
interpret group H |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1270 |
by (rule assms) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1271 |
show ?thesis |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1272 |
using one_closed by (auto simp: hom_def Pi_def) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1273 |
qed |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1274 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1275 |
lemma hom_of_snd: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1276 |
assumes "group G" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1277 |
shows "(f \<circ> snd) \<in> hom (DirProd G H) K \<longleftrightarrow> f \<in> hom H K" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1278 |
proof - |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1279 |
interpret group G |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1280 |
by (rule assms) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1281 |
show ?thesis |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1282 |
using one_closed by (auto simp: hom_def Pi_def) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1283 |
qed |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1284 |
|
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1285 |
|
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
1286 |
subsection\<open>The locale for a homomorphism between two groups\<close> |
14761 | 1287 |
|
69597 | 1288 |
text\<open>Basis for homomorphism proofs: we assume two groups \<^term>\<open>G\<close> and |
1289 |
\<^term>\<open>H\<close>, with a homomorphism \<^term>\<open>h\<close> between them\<close> |
|
61565
352c73a689da
Qualifiers in locale expressions default to mandatory regardless of the command.
ballarin
parents:
61384
diff
changeset
|
1290 |
locale group_hom = G?: group G + H?: group H for G (structure) and H (structure) + |
29237 | 1291 |
fixes h |
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
1292 |
assumes homh [simp]: "h \<in> hom G H" |
29240 | 1293 |
|
70019
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1294 |
declare group_hom.homh [simp] |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1295 |
|
29240 | 1296 |
lemma (in group_hom) hom_mult [simp]: |
1297 |
"[| x \<in> carrier G; y \<in> carrier G |] ==> h (x \<otimes>\<^bsub>G\<^esub> y) = h x \<otimes>\<^bsub>H\<^esub> h y" |
|
1298 |
proof - |
|
1299 |
assume "x \<in> carrier G" "y \<in> carrier G" |
|
1300 |
with homh [unfolded hom_def] show ?thesis by simp |
|
1301 |
qed |
|
1302 |
||
1303 |
lemma (in group_hom) hom_closed [simp]: |
|
1304 |
"x \<in> carrier G ==> h x \<in> carrier H" |
|
1305 |
proof - |
|
1306 |
assume "x \<in> carrier G" |
|
31754 | 1307 |
with homh [unfolded hom_def] show ?thesis by auto |
29240 | 1308 |
qed |
13813 | 1309 |
|
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
1310 |
lemma (in group_hom) one_closed: "h \<one> \<in> carrier H" |
13813 | 1311 |
by simp |
1312 |
||
68662 | 1313 |
lemma (in group_hom) hom_one [simp]: "h \<one> = \<one>\<^bsub>H\<^esub>" |
13813 | 1314 |
proof - |
15076
4b3d280ef06a
New prover for transitive and reflexive-transitive closure of relations.
ballarin
parents:
14963
diff
changeset
|
1315 |
have "h \<one> \<otimes>\<^bsub>H\<^esub> \<one>\<^bsub>H\<^esub> = h \<one> \<otimes>\<^bsub>H\<^esub> h \<one>" |
13813 | 1316 |
by (simp add: hom_mult [symmetric] del: hom_mult) |
70039
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1317 |
then show ?thesis |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1318 |
by (metis H.Units_eq H.Units_l_cancel H.one_closed local.one_closed) |
13813 | 1319 |
qed |
1320 |
||
69749
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
1321 |
lemma hom_one: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
1322 |
assumes "h \<in> hom G H" "group G" "group H" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
1323 |
shows "h (one G) = one H" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
1324 |
apply (rule group_hom.hom_one) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
1325 |
by (simp add: assms group_hom_axioms_def group_hom_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
1326 |
|
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
1327 |
lemma hom_mult: |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
1328 |
"\<lbrakk>h \<in> hom G H; x \<in> carrier G; y \<in> carrier G\<rbrakk> \<Longrightarrow> h (x \<otimes>\<^bsub>G\<^esub> y) = h x \<otimes>\<^bsub>H\<^esub> h y" |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
1329 |
by (auto simp: hom_def) |
10e48c47a549
some new results in group theory
paulson <lp15@cam.ac.uk>
parents:
69700
diff
changeset
|
1330 |
|
13813 | 1331 |
lemma (in group_hom) inv_closed [simp]: |
1332 |
"x \<in> carrier G ==> h (inv x) \<in> carrier H" |
|
1333 |
by simp |
|
1334 |
||
1335 |
lemma (in group_hom) hom_inv [simp]: |
|
68662 | 1336 |
assumes "x \<in> carrier G" shows "h (inv x) = inv\<^bsub>H\<^esub> (h x)" |
13813 | 1337 |
proof - |
68662 | 1338 |
have "h x \<otimes>\<^bsub>H\<^esub> h (inv x) = h x \<otimes>\<^bsub>H\<^esub> inv\<^bsub>H\<^esub> (h x)" |
1339 |
using assms by (simp flip: hom_mult) |
|
1340 |
with assms show ?thesis by (simp del: H.r_inv H.Units_r_inv) |
|
13813 | 1341 |
qed |
1342 |
||
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
1343 |
lemma (in group) int_pow_is_hom: \<^marker>\<open>contributor \<open>Joachim Breitner\<close>\<close> |
67399 | 1344 |
"x \<in> carrier G \<Longrightarrow> (([^]) x) \<in> hom \<lparr> carrier = UNIV, mult = (+), one = 0::int \<rparr> G " |
57271 | 1345 |
unfolding hom_def by (simp add: int_pow_mult) |
1346 |
||
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
1347 |
lemma (in group_hom) img_is_subgroup: "subgroup (h ` (carrier G)) H" \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1348 |
apply (rule subgroupI) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1349 |
apply (auto simp add: image_subsetI) |
68687 | 1350 |
apply (metis G.inv_closed hom_inv image_iff) |
68605 | 1351 |
by (metis G.monoid_axioms hom_mult image_eqI monoid.m_closed) |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1352 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
1353 |
lemma (in group_hom) subgroup_img_is_subgroup: \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1354 |
assumes "subgroup I G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1355 |
shows "subgroup (h ` I) H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1356 |
proof - |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1357 |
have "h \<in> hom (G \<lparr> carrier := I \<rparr>) H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1358 |
using G.subgroupE[OF assms] subgroup.mem_carrier[OF assms] homh |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1359 |
unfolding hom_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1360 |
hence "group_hom (G \<lparr> carrier := I \<rparr>) H h" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1361 |
using subgroup.subgroup_is_group[OF assms G.is_group] is_group |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1362 |
unfolding group_hom_def group_hom_axioms_def by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1363 |
thus ?thesis |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1364 |
using group_hom.img_is_subgroup[of "G \<lparr> carrier := I \<rparr>" H h] by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1365 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1366 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
1367 |
lemma (in group_hom) induced_group_hom: \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1368 |
assumes "subgroup I G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1369 |
shows "group_hom (G \<lparr> carrier := I \<rparr>) (H \<lparr> carrier := h ` I \<rparr>) h" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1370 |
proof - |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1371 |
have "h \<in> hom (G \<lparr> carrier := I \<rparr>) (H \<lparr> carrier := h ` I \<rparr>)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1372 |
using homh subgroup.mem_carrier[OF assms] unfolding hom_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1373 |
thus ?thesis |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1374 |
unfolding group_hom_def group_hom_axioms_def |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1375 |
using subgroup.subgroup_is_group[OF assms G.is_group] |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1376 |
subgroup.subgroup_is_group[OF subgroup_img_is_subgroup[OF assms] is_group] by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1377 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1378 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
1379 |
lemma (in group) canonical_inj_is_hom: \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1380 |
assumes "subgroup H G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1381 |
shows "group_hom (G \<lparr> carrier := H \<rparr>) G id" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1382 |
unfolding group_hom_def group_hom_axioms_def hom_def |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1383 |
using subgroup.subgroup_is_group[OF assms is_group] |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1384 |
is_group subgroup.subset[OF assms] by auto |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1385 |
|
70019
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1386 |
lemma (in group_hom) hom_nat_pow: \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1387 |
"x \<in> carrier G \<Longrightarrow> h (x [^] (n :: nat)) = (h x) [^]\<^bsub>H\<^esub> n" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1388 |
by (induction n) auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1389 |
|
70019
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1390 |
lemma (in group_hom) hom_int_pow: \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1391 |
"x \<in> carrier G \<Longrightarrow> h (x [^] (n :: int)) = (h x) [^]\<^bsub>H\<^esub> n" |
70019
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1392 |
using hom_nat_pow by (simp add: int_pow_def2) |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1393 |
|
70019
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1394 |
lemma hom_nat_pow: |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1395 |
"\<lbrakk>h \<in> hom G H; x \<in> carrier G; group G; group H\<rbrakk> \<Longrightarrow> h (x [^]\<^bsub>G\<^esub> (n :: nat)) = (h x) [^]\<^bsub>H\<^esub> n" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1396 |
by (simp add: group_hom.hom_nat_pow group_hom_axioms_def group_hom_def) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1397 |
|
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1398 |
lemma hom_int_pow: |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1399 |
"\<lbrakk>h \<in> hom G H; x \<in> carrier G; group G; group H\<rbrakk> \<Longrightarrow> h (x [^]\<^bsub>G\<^esub> (n :: int)) = (h x) [^]\<^bsub>H\<^esub> n" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1400 |
by (simp add: group_hom.hom_int_pow group_hom_axioms.intro group_hom_def) |
20318
0e0ea63fe768
Restructured algebra library, added ideals and quotient rings.
ballarin
parents:
19984
diff
changeset
|
1401 |
|
61382 | 1402 |
subsection \<open>Commutative Structures\<close> |
13936 | 1403 |
|
61382 | 1404 |
text \<open> |
13936 | 1405 |
Naming convention: multiplicative structures that are commutative |
1406 |
are called \emph{commutative}, additive structures are called |
|
1407 |
\emph{Abelian}. |
|
61382 | 1408 |
\<close> |
13813 | 1409 |
|
14963 | 1410 |
locale comm_monoid = monoid + |
1411 |
assumes m_comm: "\<lbrakk>x \<in> carrier G; y \<in> carrier G\<rbrakk> \<Longrightarrow> x \<otimes> y = y \<otimes> x" |
|
13813 | 1412 |
|
14963 | 1413 |
lemma (in comm_monoid) m_lcomm: |
1414 |
"\<lbrakk>x \<in> carrier G; y \<in> carrier G; z \<in> carrier G\<rbrakk> \<Longrightarrow> |
|
13813 | 1415 |
x \<otimes> (y \<otimes> z) = y \<otimes> (x \<otimes> z)" |
1416 |
proof - |
|
14693 | 1417 |
assume xyz: "x \<in> carrier G" "y \<in> carrier G" "z \<in> carrier G" |
13813 | 1418 |
from xyz have "x \<otimes> (y \<otimes> z) = (x \<otimes> y) \<otimes> z" by (simp add: m_assoc) |
1419 |
also from xyz have "... = (y \<otimes> x) \<otimes> z" by (simp add: m_comm) |
|
1420 |
also from xyz have "... = y \<otimes> (x \<otimes> z)" by (simp add: m_assoc) |
|
1421 |
finally show ?thesis . |
|
1422 |
qed |
|
1423 |
||
14963 | 1424 |
lemmas (in comm_monoid) m_ac = m_assoc m_comm m_lcomm |
13813 | 1425 |
|
13936 | 1426 |
lemma comm_monoidI: |
19783 | 1427 |
fixes G (structure) |
13936 | 1428 |
assumes m_closed: |
14693 | 1429 |
"!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> x \<otimes> y \<in> carrier G" |
1430 |
and one_closed: "\<one> \<in> carrier G" |
|
13936 | 1431 |
and m_assoc: |
1432 |
"!!x y z. [| x \<in> carrier G; y \<in> carrier G; z \<in> carrier G |] ==> |
|
14693 | 1433 |
(x \<otimes> y) \<otimes> z = x \<otimes> (y \<otimes> z)" |
1434 |
and l_one: "!!x. x \<in> carrier G ==> \<one> \<otimes> x = x" |
|
13936 | 1435 |
and m_comm: |
14693 | 1436 |
"!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> x \<otimes> y = y \<otimes> x" |
13936 | 1437 |
shows "comm_monoid G" |
1438 |
using l_one |
|
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1439 |
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
|
1440 |
intro: assms simp: m_closed one_closed m_comm) |
13817 | 1441 |
|
13936 | 1442 |
lemma (in monoid) monoid_comm_monoidI: |
1443 |
assumes m_comm: |
|
14693 | 1444 |
"!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> x \<otimes> y = y \<otimes> x" |
13936 | 1445 |
shows "comm_monoid G" |
1446 |
by (rule comm_monoidI) (auto intro: m_assoc m_comm) |
|
14963 | 1447 |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1448 |
lemma (in comm_monoid) submonoid_is_comm_monoid : |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1449 |
assumes "submonoid H G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1450 |
shows "comm_monoid (G\<lparr>carrier := H\<rparr>)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1451 |
proof (intro monoid.monoid_comm_monoidI) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1452 |
show "monoid (G\<lparr>carrier := H\<rparr>)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1453 |
using submonoid.submonoid_is_monoid assms comm_monoid_axioms comm_monoid_def by blast |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1454 |
show "\<And>x y. x \<in> carrier (G\<lparr>carrier := H\<rparr>) \<Longrightarrow> y \<in> carrier (G\<lparr>carrier := H\<rparr>) |
68687 | 1455 |
\<Longrightarrow> x \<otimes>\<^bsub>G\<lparr>carrier := H\<rparr>\<^esub> y = y \<otimes>\<^bsub>G\<lparr>carrier := H\<rparr>\<^esub> x" |
1456 |
by simp (meson assms m_comm submonoid.mem_carrier) |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1457 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1458 |
|
13936 | 1459 |
locale comm_group = comm_monoid + group |
1460 |
||
1461 |
lemma (in group) group_comm_groupI: |
|
68662 | 1462 |
assumes m_comm: "!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> x \<otimes> y = y \<otimes> x" |
13936 | 1463 |
shows "comm_group G" |
61169 | 1464 |
by standard (simp_all add: m_comm) |
13817 | 1465 |
|
13936 | 1466 |
lemma comm_groupI: |
19783 | 1467 |
fixes G (structure) |
13936 | 1468 |
assumes m_closed: |
14693 | 1469 |
"!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> x \<otimes> y \<in> carrier G" |
1470 |
and one_closed: "\<one> \<in> carrier G" |
|
13936 | 1471 |
and m_assoc: |
1472 |
"!!x y z. [| x \<in> carrier G; y \<in> carrier G; z \<in> carrier G |] ==> |
|
14693 | 1473 |
(x \<otimes> y) \<otimes> z = x \<otimes> (y \<otimes> z)" |
13936 | 1474 |
and m_comm: |
14693 | 1475 |
"!!x y. [| x \<in> carrier G; y \<in> carrier G |] ==> x \<otimes> y = y \<otimes> x" |
1476 |
and l_one: "!!x. x \<in> carrier G ==> \<one> \<otimes> x = x" |
|
14963 | 1477 |
and l_inv_ex: "!!x. x \<in> carrier G ==> \<exists>y \<in> carrier G. y \<otimes> x = \<one>" |
13936 | 1478 |
shows "comm_group G" |
27714
27b4d7c01f8b
Tuned (for the sake of a meaningless log entry).
ballarin
parents:
27713
diff
changeset
|
1479 |
by (fast intro: group.group_comm_groupI groupI assms) |
13936 | 1480 |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1481 |
lemma comm_groupE: |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1482 |
fixes G (structure) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1483 |
assumes "comm_group G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1484 |
shows "\<And>x y. \<lbrakk> x \<in> carrier G; y \<in> carrier G \<rbrakk> \<Longrightarrow> x \<otimes> y \<in> carrier G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1485 |
and "\<one> \<in> carrier G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1486 |
and "\<And>x y z. \<lbrakk> x \<in> carrier G; y \<in> carrier G; z \<in> carrier G \<rbrakk> \<Longrightarrow> (x \<otimes> y) \<otimes> z = x \<otimes> (y \<otimes> z)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1487 |
and "\<And>x y. \<lbrakk> x \<in> carrier G; y \<in> carrier G \<rbrakk> \<Longrightarrow> x \<otimes> y = y \<otimes> x" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1488 |
and "\<And>x. x \<in> carrier G \<Longrightarrow> \<one> \<otimes> x = x" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1489 |
and "\<And>x. x \<in> carrier G \<Longrightarrow> \<exists>y \<in> carrier G. y \<otimes> x = \<one>" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1490 |
apply (simp_all add: group.axioms assms comm_group.axioms comm_monoid.m_comm comm_monoid.m_ac(1)) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1491 |
by (simp_all add: Group.group.axioms(1) assms comm_group.axioms(2) monoid.m_closed group.r_inv_ex) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1492 |
|
13936 | 1493 |
lemma (in comm_group) inv_mult: |
13854
91c9ab25fece
First distributed version of Group and Ring theory.
ballarin
parents:
13835
diff
changeset
|
1494 |
"[| x \<in> carrier G; y \<in> carrier G |] ==> inv (x \<otimes> y) = inv x \<otimes> inv y" |
13936 | 1495 |
by (simp add: m_ac inv_mult_group) |
13854
91c9ab25fece
First distributed version of Group and Ring theory.
ballarin
parents:
13835
diff
changeset
|
1496 |
|
70019
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1497 |
lemma (in comm_monoid) nat_pow_distrib: |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1498 |
fixes n::nat |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1499 |
assumes "x \<in> carrier G" "y \<in> carrier G" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1500 |
shows "(x \<otimes> y) [^] n = x [^] n \<otimes> y [^] n" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1501 |
by (simp add: assms pow_mult_distrib m_comm) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1502 |
|
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1503 |
lemma (in comm_group) int_pow_distrib: |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1504 |
assumes "x \<in> carrier G" "y \<in> carrier G" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1505 |
shows "(x \<otimes> y) [^] (i::int) = x [^] i \<otimes> y [^] i" |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1506 |
by (simp add: assms int_pow_mult_distrib m_comm) |
095dce9892e8
A few results in Algebra, and bits for Analysis
paulson <lp15@cam.ac.uk>
parents:
69895
diff
changeset
|
1507 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
1508 |
lemma (in comm_monoid) hom_imp_img_comm_monoid: \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1509 |
assumes "h \<in> hom G H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1510 |
shows "comm_monoid (H \<lparr> carrier := h ` (carrier G), one := h \<one>\<^bsub>G\<^esub> \<rparr>)" (is "comm_monoid ?h_img") |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1511 |
proof (rule monoid.monoid_comm_monoidI) |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1512 |
show "monoid ?h_img" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1513 |
using hom_imp_img_monoid[OF assms] . |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1514 |
next |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1515 |
fix x y assume "x \<in> carrier ?h_img" "y \<in> carrier ?h_img" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1516 |
then obtain g1 g2 |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1517 |
where g1: "g1 \<in> carrier G" "x = h g1" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1518 |
and g2: "g2 \<in> carrier G" "y = h g2" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1519 |
by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1520 |
have "x \<otimes>\<^bsub>(?h_img)\<^esub> y = h (g1 \<otimes> g2)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1521 |
using g1 g2 assms unfolding hom_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1522 |
also have " ... = h (g2 \<otimes> g1)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1523 |
using m_comm[OF g1(1) g2(1)] by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1524 |
also have " ... = y \<otimes>\<^bsub>(?h_img)\<^esub> x" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1525 |
using g1 g2 assms unfolding hom_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1526 |
finally show "x \<otimes>\<^bsub>(?h_img)\<^esub> y = y \<otimes>\<^bsub>(?h_img)\<^esub> x" . |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1527 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1528 |
|
70039
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1529 |
lemma (in comm_group) hom_group_mult: |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1530 |
assumes "f \<in> hom H G" "g \<in> hom H G" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1531 |
shows "(\<lambda>x. f x \<otimes>\<^bsub>G\<^esub> g x) \<in> hom H G" |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1532 |
using assms by (auto simp: hom_def Pi_def m_ac) |
733e256ecdf3
new group theory material, mostly ported from HOL Light
paulson <lp15@cam.ac.uk>
parents:
70030
diff
changeset
|
1533 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
1534 |
lemma (in comm_group) hom_imp_img_comm_group: \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68517 | 1535 |
assumes "h \<in> hom G H" |
1536 |
shows "comm_group (H \<lparr> carrier := h ` (carrier G), one := h \<one>\<^bsub>G\<^esub> \<rparr>)" |
|
1537 |
unfolding comm_group_def |
|
1538 |
using hom_imp_img_group[OF assms] hom_imp_img_comm_monoid[OF assms] by simp |
|
1539 |
||
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
1540 |
lemma (in comm_group) iso_imp_img_comm_group: \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1541 |
assumes "h \<in> iso G H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1542 |
shows "comm_group (H \<lparr> one := h \<one>\<^bsub>G\<^esub> \<rparr>)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1543 |
proof - |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1544 |
let ?h_img = "H \<lparr> carrier := h ` (carrier G), one := h \<one> \<rparr>" |
68517 | 1545 |
have "comm_group ?h_img" |
1546 |
using hom_imp_img_comm_group[of h H] assms unfolding iso_def by auto |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1547 |
moreover have "carrier H = carrier ?h_img" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1548 |
using assms unfolding iso_def bij_betw_def by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1549 |
hence "H \<lparr> one := h \<one> \<rparr> = ?h_img" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1550 |
by simp |
68517 | 1551 |
ultimately show ?thesis by simp |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1552 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1553 |
|
69895
6b03a8cf092d
more formal contributors (with the help of the history);
wenzelm
parents:
69749
diff
changeset
|
1554 |
lemma (in comm_group) iso_imp_comm_group: \<^marker>\<open>contributor \<open>Paulo Emílio de Vilhena\<close>\<close> |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1555 |
assumes "G \<cong> H" "monoid H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1556 |
shows "comm_group H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1557 |
proof - |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1558 |
obtain h where h: "h \<in> iso G H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1559 |
using assms(1) unfolding is_iso_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1560 |
hence comm_gr: "comm_group (H \<lparr> one := h \<one> \<rparr>)" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1561 |
using iso_imp_img_comm_group[of h H] by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1562 |
hence "\<And>x. x \<in> carrier H \<Longrightarrow> h \<one> \<otimes>\<^bsub>H\<^esub> x = x" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1563 |
using monoid.l_one[of "H \<lparr> one := h \<one> \<rparr>"] unfolding comm_group_def comm_monoid_def by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1564 |
moreover have "h \<one> \<in> carrier H" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1565 |
using h one_closed unfolding iso_def hom_def by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1566 |
ultimately have "h \<one> = \<one>\<^bsub>H\<^esub>" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1567 |
using monoid.one_unique[OF assms(2), of "h \<one>"] by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1568 |
hence "H = H \<lparr> one := h \<one> \<rparr>" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1569 |
by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1570 |
thus ?thesis |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1571 |
using comm_gr by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1572 |
qed |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1573 |
|
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1574 |
(*A subgroup of a subgroup is a subgroup of the group*) |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1575 |
lemma (in group) incl_subgroup: |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1576 |
assumes "subgroup J G" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1577 |
and "subgroup I (G\<lparr>carrier:=J\<rparr>)" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1578 |
shows "subgroup I G" unfolding subgroup_def |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1579 |
proof |
68452
c027dfbfad30
more on infinite products. Also subgroup_imp_subset -> subgroup.subset
paulson <lp15@cam.ac.uk>
parents:
68445
diff
changeset
|
1580 |
have H1: "I \<subseteq> carrier (G\<lparr>carrier:=J\<rparr>)" using assms(2) subgroup.subset by blast |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1581 |
also have H2: "...\<subseteq>J" by simp |
68452
c027dfbfad30
more on infinite products. Also subgroup_imp_subset -> subgroup.subset
paulson <lp15@cam.ac.uk>
parents:
68445
diff
changeset
|
1582 |
also have "...\<subseteq>(carrier G)" by (simp add: assms(1) subgroup.subset) |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1583 |
finally have H: "I \<subseteq> carrier G" by simp |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1584 |
have "(\<And>x y. \<lbrakk>x \<in> I ; y \<in> I\<rbrakk> \<Longrightarrow> x \<otimes> y \<in> I)" using assms(2) by (auto simp add: subgroup_def) |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1585 |
thus "I \<subseteq> carrier G \<and> (\<forall>x y. x \<in> I \<longrightarrow> y \<in> I \<longrightarrow> x \<otimes> y \<in> I)" using H by blast |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1586 |
have K: "\<one> \<in> I" using assms(2) by (auto simp add: subgroup_def) |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1587 |
have "(\<And>x. x \<in> I \<Longrightarrow> inv x \<in> I)" using assms subgroup.m_inv_closed H |
68555
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
1588 |
by (metis H1 H2 m_inv_consistent subsetCE) |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1589 |
thus "\<one> \<in> I \<and> (\<forall>x. x \<in> I \<longrightarrow> inv x \<in> I)" using K by blast |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1590 |
qed |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1591 |
|
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1592 |
(*A subgroup included in another subgroup is a subgroup of the subgroup*) |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1593 |
lemma (in group) subgroup_incl: |
68555
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
1594 |
assumes "subgroup I G" and "subgroup J G" and "I \<subseteq> J" |
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
1595 |
shows "subgroup I (G \<lparr> carrier := J \<rparr>)" |
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
1596 |
using group.group_incl_imp_subgroup[of "G \<lparr> carrier := J \<rparr>" I] |
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
1597 |
assms(1-2)[THEN subgroup.subgroup_is_group[OF _ group_axioms]] assms(3) by auto |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1598 |
|
20318
0e0ea63fe768
Restructured algebra library, added ideals and quotient rings.
ballarin
parents:
19984
diff
changeset
|
1599 |
|
61382 | 1600 |
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
|
1601 |
|
61382 | 1602 |
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
|
1603 |
|
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1604 |
theorem (in group) subgroups_partial_order: |
67399 | 1605 |
"partial_order \<lparr>carrier = {H. subgroup H G}, eq = (=), le = (\<subseteq>)\<rparr>" |
61169 | 1606 |
by standard simp_all |
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1607 |
|
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1608 |
lemma (in group) subgroup_self: |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1609 |
"subgroup (carrier G) G" |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1610 |
by (rule subgroupI) auto |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1611 |
|
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1612 |
lemma (in group) subgroup_imp_group: |
55926 | 1613 |
"subgroup H G ==> group (G\<lparr>carrier := H\<rparr>)" |
26199 | 1614 |
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
|
1615 |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1616 |
lemma (in group) subgroup_mult_equality: |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1617 |
"\<lbrakk> subgroup H G; h1 \<in> H; h2 \<in> H \<rbrakk> \<Longrightarrow> h1 \<otimes>\<^bsub>G \<lparr> carrier := H \<rparr>\<^esub> h2 = h1 \<otimes> h2" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1618 |
unfolding subgroup_def by simp |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1619 |
|
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1620 |
theorem (in group) subgroups_Inter: |
67091 | 1621 |
assumes subgr: "(\<And>H. H \<in> A \<Longrightarrow> subgroup H G)" |
1622 |
and not_empty: "A \<noteq> {}" |
|
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1623 |
shows "subgroup (\<Inter>A) G" |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1624 |
proof (rule subgroupI) |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1625 |
from subgr [THEN subgroup.subset] and not_empty |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1626 |
show "\<Inter>A \<subseteq> carrier G" by blast |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1627 |
next |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1628 |
from subgr [THEN subgroup.one_closed] |
67091 | 1629 |
show "\<Inter>A \<noteq> {}" by blast |
14751
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1630 |
next |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1631 |
fix x assume "x \<in> \<Inter>A" |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1632 |
with subgr [THEN subgroup.m_inv_closed] |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1633 |
show "inv x \<in> \<Inter>A" by blast |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1634 |
next |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1635 |
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
|
1636 |
with subgr [THEN subgroup.m_closed] |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1637 |
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
|
1638 |
qed |
0d7850e27fed
Change of theory hierarchy: Group is now based in Lattice.
ballarin
parents:
14706
diff
changeset
|
1639 |
|
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1640 |
lemma (in group) subgroups_Inter_pair : |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1641 |
assumes "subgroup I G" |
68443
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1642 |
and "subgroup J G" |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1643 |
shows "subgroup (I\<inter>J) G" using subgroups_Inter[ where ?A = "{I,J}"] assms by auto |
43055b016688
New material from Martin Baillon and Paulo Emílio de Vilhena
paulson <lp15@cam.ac.uk>
parents:
68399
diff
changeset
|
1644 |
|
66579 | 1645 |
theorem (in group) subgroups_complete_lattice: |
67399 | 1646 |
"complete_lattice \<lparr>carrier = {H. subgroup H G}, eq = (=), le = (\<subseteq>)\<rparr>" |
66579 | 1647 |
(is "complete_lattice ?L") |
1648 |
proof (rule partial_order.complete_lattice_criterion1) |
|
1649 |
show "partial_order ?L" by (rule subgroups_partial_order) |
|
1650 |
next |
|
1651 |
have "greatest ?L (carrier G) (carrier ?L)" |
|
1652 |
by (unfold greatest_def) (simp add: subgroup.subset subgroup_self) |
|
1653 |
then show "\<exists>G. greatest ?L G (carrier ?L)" .. |
|
1654 |
next |
|
1655 |
fix A |
|
67091 | 1656 |
assume L: "A \<subseteq> carrier ?L" and non_empty: "A \<noteq> {}" |
66579 | 1657 |
then have Int_subgroup: "subgroup (\<Inter>A) G" |
1658 |
by (fastforce intro: subgroups_Inter) |
|
1659 |
have "greatest ?L (\<Inter>A) (Lower ?L A)" (is "greatest _ ?Int _") |
|
1660 |
proof (rule greatest_LowerI) |
|
1661 |
fix H |
|
1662 |
assume H: "H \<in> A" |
|
1663 |
with L have subgroupH: "subgroup H G" by auto |
|
1664 |
from subgroupH have groupH: "group (G \<lparr>carrier := H\<rparr>)" (is "group ?H") |
|
1665 |
by (rule subgroup_imp_group) |
|
1666 |
from groupH have monoidH: "monoid ?H" |
|
1667 |
by (rule group.is_monoid) |
|
1668 |
from H have Int_subset: "?Int \<subseteq> H" by fastforce |
|
1669 |
then show "le ?L ?Int H" by simp |
|
1670 |
next |
|
1671 |
fix H |
|
1672 |
assume H: "H \<in> Lower ?L A" |
|
1673 |
with L Int_subgroup show "le ?L H ?Int" |
|
1674 |
by (fastforce simp: Lower_def intro: Inter_greatest) |
|
1675 |
next |
|
1676 |
show "A \<subseteq> carrier ?L" by (rule L) |
|
1677 |
next |
|
1678 |
show "?Int \<in> carrier ?L" by simp (rule Int_subgroup) |
|
1679 |
qed |
|
1680 |
then show "\<exists>I. greatest ?L I (Lower ?L A)" .. |
|
1681 |
qed |
|
1682 |
||
70030
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
1683 |
subsection\<open>The units in any monoid give rise to a group\<close> |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1684 |
|
70030
042ae6ca2c40
The order of a group now follows the HOL Light definition, which is more general
paulson <lp15@cam.ac.uk>
parents:
70027
diff
changeset
|
1685 |
text \<open>Thanks to Jeremy Avigad. The file Residues.thy provides some infrastructure to use |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1686 |
facts about the unit group within the ring locale. |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1687 |
\<close> |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1688 |
|
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1689 |
definition units_of :: "('a, 'b) monoid_scheme \<Rightarrow> 'a monoid" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1690 |
where "units_of G = |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1691 |
\<lparr>carrier = Units G, Group.monoid.mult = Group.monoid.mult G, one = one G\<rparr>" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1692 |
|
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1693 |
lemma (in monoid) units_group: "group (units_of G)" |
68458 | 1694 |
proof - |
1695 |
have "\<And>x y z. \<lbrakk>x \<in> Units G; y \<in> Units G; z \<in> Units G\<rbrakk> \<Longrightarrow> x \<otimes> y \<otimes> z = x \<otimes> (y \<otimes> z)" |
|
1696 |
by (simp add: Units_closed m_assoc) |
|
1697 |
moreover have "\<And>x. x \<in> Units G \<Longrightarrow> \<exists>y\<in>Units G. y \<otimes> x = \<one>" |
|
1698 |
using Units_l_inv by blast |
|
1699 |
ultimately show ?thesis |
|
1700 |
unfolding units_of_def |
|
1701 |
by (force intro!: groupI) |
|
1702 |
qed |
|
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1703 |
|
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1704 |
lemma (in comm_monoid) units_comm_group: "comm_group (units_of G)" |
68458 | 1705 |
proof - |
1706 |
have "\<And>x y. \<lbrakk>x \<in> carrier (units_of G); y \<in> carrier (units_of G)\<rbrakk> |
|
1707 |
\<Longrightarrow> x \<otimes>\<^bsub>units_of G\<^esub> y = y \<otimes>\<^bsub>units_of G\<^esub> x" |
|
1708 |
by (simp add: Units_closed m_comm units_of_def) |
|
1709 |
then show ?thesis |
|
1710 |
by (rule group.group_comm_groupI [OF units_group]) auto |
|
1711 |
qed |
|
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1712 |
|
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1713 |
lemma units_of_carrier: "carrier (units_of G) = Units G" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1714 |
by (auto simp: units_of_def) |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1715 |
|
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1716 |
lemma units_of_mult: "mult (units_of G) = mult G" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1717 |
by (auto simp: units_of_def) |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1718 |
|
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1719 |
lemma units_of_one: "one (units_of G) = one G" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1720 |
by (auto simp: units_of_def) |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1721 |
|
68555
22d51874f37d
a few more lemmas from Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68551
diff
changeset
|
1722 |
lemma (in monoid) units_of_inv: |
68458 | 1723 |
assumes "x \<in> Units G" |
1724 |
shows "m_inv (units_of G) x = m_inv G x" |
|
1725 |
by (simp add: assms group.inv_equality units_group units_of_carrier units_of_mult units_of_one) |
|
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1726 |
|
68551
b680e74eb6f2
More on Algebra by Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68517
diff
changeset
|
1727 |
lemma units_of_units [simp] : "Units (units_of G) = Units G" |
b680e74eb6f2
More on Algebra by Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68517
diff
changeset
|
1728 |
unfolding units_of_def Units_def by force |
b680e74eb6f2
More on Algebra by Paulo and Martin
paulson <lp15@cam.ac.uk>
parents:
68517
diff
changeset
|
1729 |
|
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1730 |
lemma (in group) surj_const_mult: "a \<in> carrier G \<Longrightarrow> (\<lambda>x. a \<otimes> x) ` carrier G = carrier G" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1731 |
apply (auto simp add: image_def) |
68458 | 1732 |
by (metis inv_closed inv_solve_left m_closed) |
68445
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1733 |
|
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1734 |
lemma (in group) l_cancel_one [simp]: "x \<in> carrier G \<Longrightarrow> a \<in> carrier G \<Longrightarrow> x \<otimes> a = x \<longleftrightarrow> a = one G" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1735 |
by (metis Units_eq Units_l_cancel monoid.r_one monoid_axioms one_closed) |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1736 |
|
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1737 |
lemma (in group) r_cancel_one [simp]: "x \<in> carrier G \<Longrightarrow> a \<in> carrier G \<Longrightarrow> a \<otimes> x = x \<longleftrightarrow> a = one G" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1738 |
by (metis monoid.l_one monoid_axioms one_closed right_cancel) |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1739 |
|
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1740 |
lemma (in group) l_cancel_one' [simp]: "x \<in> carrier G \<Longrightarrow> a \<in> carrier G \<Longrightarrow> x = x \<otimes> a \<longleftrightarrow> a = one G" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1741 |
using l_cancel_one by fastforce |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1742 |
|
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1743 |
lemma (in group) r_cancel_one' [simp]: "x \<in> carrier G \<Longrightarrow> a \<in> carrier G \<Longrightarrow> x = a \<otimes> x \<longleftrightarrow> a = one G" |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1744 |
using r_cancel_one by fastforce |
c183a6a69f2d
reorganisation of Algebra: new material from Baillon and Vilhena, removal of duplicate names, elimination of "More_" theories
paulson <lp15@cam.ac.uk>
parents:
68443
diff
changeset
|
1745 |
|
70027
94494b92d8d0
some new group theory results: integer group, trivial group, etc.
paulson <lp15@cam.ac.uk>
parents:
70019
diff
changeset
|
1746 |
declare pow_nat [simp] (*causes looping if added above, especially with int_pow_def2*) |
94494b92d8d0
some new group theory results: integer group, trivial group, etc.
paulson <lp15@cam.ac.uk>
parents:
70019
diff
changeset
|
1747 |
|
13813 | 1748 |
end |