1 (**************************************************************************)
4 (* ||A|| A project by Andrea Asperti *)
6 (* ||I|| Developers: *)
7 (* ||T|| The HELM team. *)
8 (* ||A|| http://helm.cs.unibo.it *)
10 (* \ / This file is distributed under the terms of the *)
11 (* v GNU General Public License Version 2 *)
13 (**************************************************************************)
15 include "algebra/monoids.ma".
16 include "nat/le_arith.ma".
17 include "datatypes/bool.ma".
18 include "nat/compare.ma".
20 record PreGroup : Type ≝
21 { premonoid:> PreMonoid;
22 inv: premonoid -> premonoid
25 record isGroup (G:PreGroup) : Prop ≝
26 { is_monoid:> isMonoid G;
27 inv_is_left_inverse: is_left_inverse (mk_Monoid ? is_monoid) (inv G);
28 inv_is_right_inverse: is_right_inverse (mk_Monoid ? is_monoid) (inv G)
32 { pregroup:> PreGroup;
33 group_properties:> isGroup pregroup
36 notation "hvbox(x \sup (-1))" with precedence 89
39 interpretation "Group inverse" 'ginv x =
40 (cic:/matita/algebra/groups/inv.con _ x).
42 definition left_cancellable ≝
43 λT:Type. λop: T -> T -> T.
44 ∀x. injective ? ? (op x).
46 definition right_cancellable ≝
47 λT:Type. λop: T -> T -> T.
48 ∀x. injective ? ? (λz.op z x).
50 theorem eq_op_x_y_op_x_z_to_eq:
51 ∀G:Group. left_cancellable G (op G).
53 unfold left_cancellable;
56 rewrite < (e_is_left_unit ? G);
57 rewrite < (e_is_left_unit ? G z);
58 rewrite < (inv_is_left_inverse ? G x);
59 rewrite > (op_associative ? G);
60 rewrite > (op_associative ? G);
66 theorem eq_op_x_y_op_z_y_to_eq:
67 ∀G:Group. right_cancellable G (op G).
69 unfold right_cancellable;
71 simplify;fold simplify (op G);
73 rewrite < (e_is_right_unit ? G);
74 rewrite < (e_is_right_unit ? G z);
75 rewrite < (inv_is_right_inverse ? G x);
76 rewrite < (op_associative ? G);
77 rewrite < (op_associative ? G);
82 theorem eq_inv_inv_x_x: ∀G:Group. ∀x:G. x \sup -1 \sup -1 = x.
84 apply (eq_op_x_y_op_z_y_to_eq ? (x \sup -1));
85 rewrite > (inv_is_right_inverse ? G);
86 rewrite > (inv_is_left_inverse ? G);
90 theorem eq_opxy_e_to_eq_x_invy:
91 ∀G:Group. ∀x,y:G. x·y=1 → x=y \sup -1.
93 apply (eq_op_x_y_op_z_y_to_eq ? y);
94 rewrite > (inv_is_left_inverse ? G);
98 theorem eq_opxy_e_to_eq_invx_y:
99 ∀G:Group. ∀x,y:G. x·y=1 → x \sup -1=y.
101 apply (eq_op_x_y_op_x_z_to_eq ? x);
102 rewrite > (inv_is_right_inverse ? G);
107 theorem eq_opxy_z_to_eq_x_opzinvy:
108 ∀G:Group. ∀x,y,z:G. x·y=z → x = z·y \sup -1.
110 apply (eq_op_x_y_op_z_y_to_eq ? y);
111 rewrite > (op_associative ? G);
112 rewrite > (inv_is_left_inverse ? G);
113 rewrite > (e_is_right_unit ? G);
117 theorem eq_opxy_z_to_eq_y_opinvxz:
118 ∀G:Group. ∀x,y,z:G. x·y=z → y = x \sup -1·z.
120 apply (eq_op_x_y_op_x_z_to_eq ? x);
121 rewrite < (op_associative ? G);
122 rewrite > (inv_is_right_inverse ? G);
123 rewrite > (e_is_left_unit ? G);
127 theorem eq_inv_op_x_y_op_inv_y_inv_x:
128 ∀G:Group. ∀x,y:G. (x·y) \sup -1 = y \sup -1 · x \sup -1.
130 apply (eq_op_x_y_op_z_y_to_eq ? (x·y));
131 rewrite > (inv_is_left_inverse ? G);
132 rewrite < (op_associative ? G);
133 rewrite > (op_associative ? G (y \sup -1));
134 rewrite > (inv_is_left_inverse ? G);
135 rewrite > (e_is_right_unit ? G);
136 rewrite > (inv_is_left_inverse ? G);
142 record morphism (G,G':Group) : Type ≝
144 f_morph: ∀x,y:G.image(x·y) = image x · image y
147 notation "hvbox(f\tilde x)" with precedence 79
148 for @{ 'morimage $f $x }.
150 interpretation "Morphism image" 'morimage f x =
151 (cic:/matita/algebra/groups/image.con _ _ f x).
153 theorem morphism_to_eq_f_1_1:
154 ∀G,G'.∀f:morphism G G'.f˜1 = 1.
156 apply (eq_op_x_y_op_z_y_to_eq ? (f˜1));
157 rewrite > (e_is_left_unit ? G');
159 rewrite > (e_is_left_unit ? G);
163 theorem eq_image_inv_inv_image:
164 ∀G,G'.∀f:morphism G G'.
165 ∀x.f˜(x \sup -1) = (f˜x) \sup -1.
167 apply (eq_op_x_y_op_z_y_to_eq ? (f˜x));
168 rewrite > (inv_is_left_inverse ? G');
170 rewrite > (inv_is_left_inverse ? G);
171 apply (morphism_to_eq_f_1_1 ? ? f).
174 record monomorphism (G,G':Group) : Type ≝
175 { morphism:> morphism G G';
176 injective: injective ? ? (image ? ? morphism)
181 record subgroup (G:Group) : Type ≝
183 embed:> monomorphism group G
186 notation "hvbox(x \sub H)" with precedence 79
187 for @{ 'subgroupimage $H $x }.
189 interpretation "Subgroup image" 'subgroupimage H x =
190 (cic:/matita/algebra/groups/image.con _ _
191 (cic:/matita/algebra/groups/morphism_OF_subgroup.con _ H) x).
193 definition member_of_subgroup ≝
194 λG.λH:subgroup G.λx:G.∃y.x=y \sub H.
196 notation "hvbox(x break \in H)" with precedence 79
197 for @{ 'member_of $x $H }.
199 notation "hvbox(x break \notin H)" with precedence 79
200 for @{ 'not_member_of $x $H }.
202 interpretation "Member of subgroup" 'member_of x H =
203 (cic:/matita/algebra/groups/member_of_subgroup.con _ H x).
205 interpretation "Not member of subgroup" 'not_member_of x H =
206 (cic:/matita/logic/connectives/Not.con
207 (cic:/matita/algebra/groups/member_of_subgroup.con _ H x)).
211 record left_coset (G:Group) : Type ≝
216 (* Here I would prefer 'magma_op, but this breaks something in the next definition *)
217 interpretation "Left_coset" 'times x C =
218 (cic:/matita/algebra/groups/left_coset.ind#xpointer(1/1/1) _ x C).
220 definition member_of_left_coset ≝
221 λG:Group.λC:left_coset G.λx:G.
222 ∃y.x=(element ? C)·y \sub (subgrp ? C).
224 interpretation "Member of left_coset" 'member_of x C =
225 (cic:/matita/algebra/groups/member_of_left_coset.con _ C x).
227 definition left_coset_eq ≝
228 λG.λC,C':left_coset G.
229 ∀x.((element ? C)·x \sub (subgrp ? C)) ∈ C'.
231 interpretation "Left cosets equality" 'eq C C' =
232 (cic:/matita/algebra/groups/left_coset_eq.con _ C C').
234 definition left_coset_disjoint ≝
235 λG.λC,C':left_coset G.
236 ∀x.¬(((element ? C)·x \sub (subgrp ? C)) ∈ C').
238 notation "hvbox(a break \par b)"
239 non associative with precedence 45
240 for @{ 'disjoint $a $b }.
242 interpretation "Left cosets disjoint" 'disjoint C C' =
243 (cic:/matita/algebra/groups/left_coset_disjoint.con _ C C').
245 (* The following should be a one-shot alias! *)
246 alias symbol "member_of" (instance 0) = "Member of subgroup".
247 theorem member_of_subgroup_op_inv_x_y_to_left_coset_eq:
248 ∀G.∀x,y.∀H:subgroup G. (x \sup -1 ·y) ∈ H → x*H = y*H.
252 unfold member_of_subgroup in H1;
256 [ apply (a\sup-1 · x1)
258 rewrite > eq_image_inv_inv_image;
260 rewrite > eq_inv_op_x_y_op_inv_y_inv_x;
261 rewrite > eq_inv_inv_x_x;
262 rewrite < (op_associative ? G);
263 rewrite < (op_associative ? G);
264 rewrite > (inv_is_right_inverse ? G);
265 rewrite > (e_is_left_unit ? G);
270 theorem Not_member_of_subgroup_to_left_coset_disjoint:
271 ∀G.∀x,y.∀H:subgroup G.(x \sup -1 ·y) ∉ H → x*H ∥ y*H.
277 unfold member_of_subgroup;
279 apply (ex_intro ? ? (x'·a \sup -1));
281 apply (eq_op_x_y_op_z_y_to_eq ? (a \sub H));
282 rewrite > (op_associative ? G);
284 rewrite > (op_associative ? G);
286 rewrite > (inv_is_left_inverse ? H);
287 rewrite < (op_associative ? G);
288 rewrite > (inv_is_left_inverse ? G);
289 rewrite > (e_is_left_unit ? G);
290 rewrite < (f_morph ? ? H);
291 rewrite > (e_is_right_unit ? H);
295 (*CSC: here the coercion Type_of_Group cannot be omitted. Why? *)
296 theorem in_x_mk_left_coset_x_H:
297 ∀G.∀x:Type_OF_Group G.∀H:subgroup G.x ∈ (x*H).
300 apply (ex_intro ? ? 1);
301 rewrite > morphism_to_eq_f_1_1;
302 rewrite > (e_is_right_unit ? G);
306 (* Normal Subgroups *)
308 record normal_subgroup (G:Group) : Type ≝
309 { ns_subgroup:> subgroup G;
310 normal:> ∀x:G.∀y:ns_subgroup.(x·y \sub ns_subgroup·x \sup -1) ∈ ns_subgroup
313 (*CSC: I have not defined yet right cosets
315 ∀G.∀H:normal_subgroup G.∀x.x*H=H*x.
318 theorem member_of_left_coset_mk_left_coset_x_H_a_to_member_of_left_coset_mk_left_coset_y_H_b_to_member_of_left_coset_mk_left_coset_op_x_y_H_op_a_b:
319 ∀G.∀H:normal_subgroup G.∀x,y,a,b.
320 a ∈ (x*H) → b ∈ (y*H) → (a·b) ∈ ((x·y)*H).