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