]> matita.cs.unibo.it Git - helm.git/blob - helm/software/matita/library/algebra/groups.ma
- oCic2NCic and nCic2OCic moved to ng_library
[helm.git] / helm / software / matita / library / algebra / groups.ma
1 (**************************************************************************)
2 (*       ___                                                              *)
3 (*      ||M||                                                             *)
4 (*      ||A||       A project by Andrea Asperti                           *)
5 (*      ||T||                                                             *)
6 (*      ||I||       Developers:                                           *)
7 (*      ||T||         The HELM team.                                      *)
8 (*      ||A||         http://helm.cs.unibo.it                             *)
9 (*      \   /                                                             *)
10 (*       \ /        This file is distributed under the terms of the       *)
11 (*        v         GNU General Public License Version 2                  *)
12 (*                                                                        *)
13 (**************************************************************************)
14
15 include "algebra/monoids.ma".
16 include "nat/le_arith.ma".
17 include "datatypes/bool.ma".
18 include "nat/compare.ma".
19
20 record PreGroup : Type ≝
21  { pre_monoid:> PreMonoid;
22    inv: pre_monoid -> pre_monoid
23  }.
24
25 interpretation "Group inverse" 'invert x = (inv ? x).
26
27 record isGroup (G:PreGroup) : Prop ≝
28  { is_monoid           :> IsMonoid G;
29    inv_is_left_inverse :  is_left_inverse G (inv G);
30    inv_is_right_inverse:  is_right_inverse G (inv G)
31  }.
32
33 record Group : Type ≝
34  { pre_group:> PreGroup;
35    is_group:> isGroup pre_group
36  }.
37
38 definition Monoid_of_Group: Group → Monoid ≝
39  λG. mk_Monoid ? (is_group G).
40
41 coercion Monoid_of_Group nocomposites.
42
43 definition left_cancellable ≝
44  λT:Type. λop: T -> T -> T.
45   ∀x. injective ? ? (op x).
46   
47 definition right_cancellable ≝
48  λT:Type. λop: T -> T -> T.
49   ∀x. injective ? ? (λz.op z x).
50   
51 theorem eq_op_x_y_op_x_z_to_eq:
52  ∀G:Group. left_cancellable G (op G).
53 intros;
54 unfold left_cancellable;
55 unfold injective;
56 intros (x y z);
57 rewrite < (e_is_left_unit ? G);
58 rewrite < (e_is_left_unit ? G z);
59 rewrite < (inv_is_left_inverse ? G x);
60 rewrite > (op_is_associative ? G);
61 rewrite > (op_is_associative ? G);
62 apply eq_f;
63 assumption.
64 qed.
65
66 theorem eq_op_x_y_op_z_y_to_eq:
67  ∀G:Group. right_cancellable G (op G).
68 intros;
69 unfold right_cancellable;
70 unfold injective;
71 intros (x y z);
72 rewrite < (e_is_right_unit ? G);
73 rewrite < (e_is_right_unit ? G z);
74 rewrite < (inv_is_right_inverse ? G x);
75 rewrite < (op_is_associative ? G);
76 rewrite < (op_is_associative ? G);
77 rewrite > H;
78 reflexivity.
79 qed.
80
81 theorem eq_inv_inv_x_x: ∀G:Group. ∀x:G. x \sup -1 \sup -1 = x.
82 intros;
83 apply (eq_op_x_y_op_z_y_to_eq ? (x \sup -1));
84 rewrite > (inv_is_right_inverse ? G);
85 rewrite > (inv_is_left_inverse ? G);
86 reflexivity.
87 qed.
88
89 theorem eq_opxy_e_to_eq_x_invy:
90  ∀G:Group. ∀x,y:G. x·y=ⅇ → x=y \sup -1.
91 intros;
92 apply (eq_op_x_y_op_z_y_to_eq ? y);
93 rewrite > (inv_is_left_inverse ? G);
94 assumption.
95 qed.
96
97 theorem eq_opxy_e_to_eq_invx_y:
98  ∀G:Group. ∀x,y:G. x·y=ⅇ → x \sup -1=y.
99 intros;
100 apply (eq_op_x_y_op_x_z_to_eq ? x);
101 rewrite > (inv_is_right_inverse ? G);
102 symmetry;
103 assumption.
104 qed.
105
106 theorem eq_opxy_z_to_eq_x_opzinvy:
107  ∀G:Group. ∀x,y,z:G. x·y=z → x = z·y \sup -1.
108 intros;
109 apply (eq_op_x_y_op_z_y_to_eq ? y);
110 rewrite > (op_is_associative ? G);
111 rewrite > (inv_is_left_inverse ? G);
112 rewrite > (e_is_right_unit ? G);
113 assumption.
114 qed.
115
116 theorem eq_opxy_z_to_eq_y_opinvxz:
117  ∀G:Group. ∀x,y,z:G. x·y=z → y = x \sup -1·z.
118 intros;
119 apply (eq_op_x_y_op_x_z_to_eq ? x);
120 rewrite < (op_is_associative ? G);
121 rewrite > (inv_is_right_inverse ? G);
122 rewrite > (e_is_left_unit ? G);
123 assumption.
124 qed.
125
126 theorem eq_inv_op_x_y_op_inv_y_inv_x:
127  ∀G:Group. ∀x,y:G. (x·y) \sup -1 = y \sup -1 · x \sup -1.
128 intros;
129 apply (eq_op_x_y_op_z_y_to_eq ? (x·y));
130 rewrite > (inv_is_left_inverse ? G);
131 rewrite < (op_is_associative ? G);
132 rewrite > (op_is_associative ? G (y \sup -1));
133 rewrite > (inv_is_left_inverse ? G);
134 rewrite > (e_is_right_unit ? G);
135 rewrite > (inv_is_left_inverse ? G);
136 reflexivity.
137 qed.
138
139 (* Morphisms *)
140
141 record morphism (G,G':Group) : Type ≝
142  { image:1> G → G';
143    f_morph: ∀x,y:G.image(x·y) = image x · image y
144  }.
145  
146 theorem morphism_to_eq_f_1_1:
147  ∀G,G'.∀f:morphism G G'.f ⅇ  = ⅇ.
148 intros;
149 apply (eq_op_x_y_op_z_y_to_eq ? (f ⅇ));
150 rewrite > (e_is_left_unit ? G');
151 rewrite < f_morph;
152 rewrite > (e_is_left_unit ? G);
153 reflexivity.
154 qed.
155  
156 theorem eq_image_inv_inv_image:
157  ∀G,G'.∀f:morphism G G'.
158   ∀x.f (x \sup -1) = (f x) \sup -1.
159 intros;
160 apply (eq_op_x_y_op_z_y_to_eq ? (f x));
161 rewrite > (inv_is_left_inverse ? G');
162 rewrite < f_morph;
163 rewrite > (inv_is_left_inverse ? G);
164 apply (morphism_to_eq_f_1_1 ? ? f).
165 qed.
166
167 record monomorphism (G,G':Group) : Type ≝
168  { morphism:> morphism G G';
169    injective: injective ? ? (image ? ? morphism)
170  }.
171
172 (* Subgroups *)
173
174 record subgroup (G:Group) : Type ≝
175  { group:> Group;
176    embed:> monomorphism group G
177  }.
178
179 notation "hvbox(x \sub H)" with precedence 79
180 for @{ 'subgroupimage $H $x }.
181
182 interpretation "Subgroup image" 'subgroupimage H x =
183  (image ?? (morphism_OF_subgroup ? H) x).
184
185 definition member_of_subgroup ≝
186  λG.λH:subgroup G.λx:G.∃y.x=y \sub H.
187
188 notation "hvbox(x break \in H)" with precedence 79
189 for @{ 'member_of $x $H }.
190
191 notation "hvbox(x break \notin H)" with precedence 79
192 for @{ 'not_member_of $x $H }.
193
194 interpretation "Member of subgroup" 'member_of x H =
195  (member_of_subgroup ? H x).
196  
197 interpretation "Not member of subgroup" 'not_member_of x H =
198  (Not (member_of_subgroup ? H x)).
199
200 (* Left cosets *)
201
202 record left_coset (G:Group) : Type ≝
203  { element: G;
204    subgrp: subgroup G
205  }.
206
207 (* Here I would prefer 'magma_op, but this breaks something in the next definition *)
208 interpretation "Left_coset" 'times x C =
209  (mk_left_coset ? x C).
210
211 definition member_of_left_coset ≝
212  λG:Group.λC:left_coset G.λx:G.
213   ∃y.x=(element ? C)·y \sub (subgrp ? C).
214
215 interpretation "Member of left_coset" 'member_of x C =
216  (member_of_left_coset ? C x).
217
218 definition left_coset_eq ≝
219  λG.λC,C':left_coset G.
220   ∀x.((element ? C)·x \sub (subgrp ? C)) ∈ C'.
221   
222 interpretation "Left cosets equality" 'eq t C C' = (left_coset_eq t C C').
223
224 definition left_coset_disjoint ≝
225  λG.λC,C':left_coset G.
226   ∀x.¬(((element ? C)·x \sub (subgrp ? C)) ∈ C'). 
227
228 notation "hvbox(a break \par b)"
229  non associative with precedence 45
230 for @{ 'disjoint $a $b }.
231
232 interpretation "Left cosets disjoint" 'disjoint C C' =
233  (left_coset_disjoint ? C C').
234
235 (* The following should be a one-shot alias! *)
236 alias symbol "member_of" (instance 0) = "Member of subgroup".
237 theorem member_of_subgroup_op_inv_x_y_to_left_coset_eq:
238  ∀G.∀x,y.∀H:subgroup G. (x \sup -1 ·y) ∈ H → x*H = y*H.
239 intros;
240 simplify;
241 intro;
242 unfold member_of_subgroup in H1;
243 elim H1;
244 clear H1;
245 exists;
246 [ apply (a\sup-1 · x1)
247 | rewrite > f_morph;
248   rewrite > eq_image_inv_inv_image; 
249   rewrite < H2;
250   rewrite > eq_inv_op_x_y_op_inv_y_inv_x;
251   rewrite > eq_inv_inv_x_x;
252   rewrite < (op_is_associative ? G);
253   rewrite < (op_is_associative ? G);
254   rewrite > (inv_is_right_inverse ? G);
255   rewrite > (e_is_left_unit ? G);
256   reflexivity
257 ].
258 qed.
259
260 theorem Not_member_of_subgroup_to_left_coset_disjoint:
261  ∀G.∀x,y.∀H:subgroup G.(x \sup -1 ·y) ∉ H → x*H ∥ y*H.
262 intros;
263 simplify;
264 unfold Not;
265 intros (x');
266 apply H1;
267 unfold member_of_subgroup;
268 elim H2;
269 apply (ex_intro ? ? (x'·a \sup -1));
270 rewrite > f_morph; 
271 apply (eq_op_x_y_op_z_y_to_eq ? (a \sub H));
272 rewrite > (op_is_associative ? G);
273 rewrite < H3;
274 rewrite > (op_is_associative ? G);
275 rewrite < f_morph;
276 rewrite > (inv_is_left_inverse ? H);
277 rewrite < (op_is_associative ? G);
278 rewrite > (inv_is_left_inverse ? G);
279 rewrite > (e_is_left_unit ? G);
280 rewrite < (f_morph ? ? H);
281 rewrite > (e_is_right_unit ? H);
282 reflexivity.
283 qed.
284
285 (*CSC: here the coercion Type_of_Group cannot be omitted. Why? *)
286 theorem in_x_mk_left_coset_x_H:
287  ∀G.∀x:Type_OF_Group G.∀H:subgroup G.x ∈ (x*H).
288 intros;
289 simplify;
290 apply (ex_intro ? ? ⅇ);
291 rewrite > morphism_to_eq_f_1_1;
292 rewrite > (e_is_right_unit ? G);
293 reflexivity.
294 qed.
295
296 (* Normal Subgroups *)
297
298 record normal_subgroup (G:Group) : Type ≝
299  { ns_subgroup:> subgroup G;
300    normal:> ∀x:G.∀y:ns_subgroup.(x·y \sub ns_subgroup·x \sup -1) ∈ ns_subgroup
301  }.
302
303 (*CSC: I have not defined yet right cosets 
304 theorem foo:
305  ∀G.∀H:normal_subgroup G.∀x.x*H=H*x.
306 *)
307 (*
308 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:
309  ∀G.∀H:normal_subgroup G.∀x,y,a,b.
310   a ∈ (x*H) → b ∈ (y*H) → (a·b) ∈ ((x·y)*H).
311 intros;
312 simplify;
313 qed.
314 *)