]> matita.cs.unibo.it Git - helm.git/blob - matita/library/algebra/groups.ma
970a5e38892ae9a3b2c46c9ce92b81f7520fb2b2
[helm.git] / 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 set "baseuri" "cic:/matita/algebra/groups/".
16
17 include "algebra/monoids.ma".
18 include "nat/le_arith.ma".
19 include "datatypes/bool.ma".
20 include "nat/compare.ma".
21
22 record PreGroup : Type ≝
23  { premonoid:> PreMonoid;
24    inv: premonoid -> premonoid
25  }.
26
27 record isGroup (G:PreGroup) : Prop ≝
28  { is_monoid: isMonoid G;
29    inv_is_left_inverse: is_left_inverse (mk_Monoid ? is_monoid) (inv G);
30    inv_is_right_inverse: is_right_inverse (mk_Monoid ? is_monoid) (inv G)
31  }.
32  
33 record Group : Type ≝
34  { pregroup:> PreGroup;
35    group_properties:> isGroup pregroup
36  }.
37
38 (*notation < "G"
39 for @{ 'monoid $G }.
40
41 interpretation "Monoid coercion" 'monoid G =
42  (cic:/matita/algebra/groups/monoid.con G).*)
43
44 notation < "G"
45 for @{ 'type_of_group $G }.
46
47 interpretation "Type_of_group coercion" 'type_of_group G =
48  (cic:/matita/algebra/groups/Type_of_Group.con G).
49
50 notation < "G"
51 for @{ 'magma_of_group $G }.
52
53 interpretation "magma_of_group coercion" 'magma_of_group G =
54  (cic:/matita/algebra/groups/Magma_of_Group.con G).
55
56 notation "hvbox(x \sup (-1))" with precedence 89
57 for @{ 'ginv $x }.
58
59 interpretation "Group inverse" 'ginv x =
60  (cic:/matita/algebra/groups/inv.con _ x).
61
62 definition left_cancellable ≝
63  λT:Type. λop: T -> T -> T.
64   ∀x. injective ? ? (op x).
65   
66 definition right_cancellable ≝
67  λT:Type. λop: T -> T -> T.
68   ∀x. injective ? ? (λz.op z x).
69   
70 theorem eq_op_x_y_op_x_z_to_eq:
71  ∀G:Group. left_cancellable G (op G).
72 intros;
73 unfold left_cancellable;
74 unfold injective;
75 intros (x y z);
76 rewrite < (e_is_left_unit ? (is_monoid ? G));
77 rewrite < (e_is_left_unit ? (is_monoid ? G) z);
78 rewrite < (inv_is_left_inverse ? G x);
79 rewrite > (associative ? (is_semi_group ? (is_monoid ? G)));
80 rewrite > (associative ? (is_semi_group ? (is_monoid ? G)));
81 apply eq_f;
82 assumption.
83 qed.
84
85
86 theorem eq_op_x_y_op_z_y_to_eq:
87  ∀G:Group. right_cancellable G (op G).
88 intros;
89 unfold right_cancellable;
90 unfold injective;
91 simplify;fold simplify (op G); 
92 intros (x y z);
93 rewrite < (e_is_right_unit ? (is_monoid ? G));
94 rewrite < (e_is_right_unit ? (is_monoid ? G) z);
95 rewrite < (inv_is_right_inverse ? G x);
96 rewrite < (associative ? (is_semi_group ? (is_monoid ? G)));
97 rewrite < (associative ? (is_semi_group ? (is_monoid ? G)));
98 rewrite > H;
99 reflexivity.
100 qed.
101
102 theorem inv_inv: ∀G:Group. ∀x:G. x \sup -1 \sup -1 = x.
103 intros;
104 apply (eq_op_x_y_op_z_y_to_eq ? (x \sup -1));
105 rewrite > (inv_is_right_inverse ? G);
106 rewrite > (inv_is_left_inverse ? G);
107 reflexivity.
108 qed.
109
110 theorem eq_opxy_e_to_eq_x_invy:
111  ∀G:Group. ∀x,y:G. x·y=1 → x=y \sup -1.
112 intros;
113 apply (eq_op_x_y_op_z_y_to_eq ? y);
114 rewrite > (inv_is_left_inverse ? G);
115 assumption.
116 qed.
117
118 theorem eq_opxy_e_to_eq_invx_y:
119  ∀G:Group. ∀x,y:G. x·y=1 → x \sup -1=y.
120 intros;
121 apply (eq_op_x_y_op_x_z_to_eq ? x);
122 rewrite > (inv_is_right_inverse ? G);
123 symmetry;
124 assumption.
125 qed.
126
127 theorem eq_opxy_z_to_eq_x_opzinvy:
128  ∀G:Group. ∀x,y,z:G. x·y=z → x = z·y \sup -1.
129 intros;
130 apply (eq_op_x_y_op_z_y_to_eq ? y);
131 rewrite > (associative ? (is_semi_group ? (is_monoid ? G)));
132 rewrite > (inv_is_left_inverse ? G);
133 rewrite > (e_is_right_unit ? (is_monoid ? G));
134 assumption.
135 qed.
136
137 theorem eq_opxy_z_to_eq_y_opinvxz:
138  ∀G:Group. ∀x,y,z:G. x·y=z → y = x \sup -1·z.
139 intros;
140 apply (eq_op_x_y_op_x_z_to_eq ? x);
141 rewrite < (associative ? (is_semi_group ? (is_monoid ? G)));
142 rewrite > (inv_is_right_inverse ? G);
143 rewrite > (e_is_left_unit ? (is_monoid ? G));
144 assumption.
145 qed.
146
147 (* Morphisms *)
148
149 record morphism (G,G':Group) : Type ≝
150  { image: G → G';
151    f_morph: ∀x,y:G.image(x·y) = image x · image y
152  }.
153  
154 notation "hvbox(f˜ x)" with precedence 79
155 for @{ 'morimage $f $x }.
156
157 interpretation "Morphism image" 'morimage f x =
158  (cic:/matita/algebra/groups/image.con _ _ f x).
159  
160 theorem morphism_to_eq_f_1_1:
161  ∀G,G'.∀f:morphism G G'.f˜1 = 1.
162 intros;
163 apply (eq_op_x_y_op_z_y_to_eq G' (f˜1));
164 rewrite > (e_is_left_unit ? (is_monoid ? G') ?);
165 rewrite < (f_morph ? ? f);
166 rewrite > (e_is_left_unit ? (is_monoid ? G));
167 reflexivity.
168 qed.
169  
170 theorem eq_image_inv_inv_image:
171  ∀G,G'.∀f:morphism G G'.
172   ∀x.f˜(x \sup -1) = (f˜x) \sup -1.
173 intros;
174 apply (eq_op_x_y_op_z_y_to_eq G' (f˜x));
175 rewrite > (inv_is_left_inverse ? G');
176 rewrite < (f_morph ? ? f);
177 rewrite > (inv_is_left_inverse ? G);
178 apply (morphism_to_eq_f_1_1 ? ? f).
179 qed.
180
181 record monomorphism (G,G':Group) : Type ≝
182  { morphism: morphism G G';
183    injective: injective ? ? (image ? ? morphism)
184  }.
185
186 (* Subgroups *)
187
188 record subgroup (G:Group) : Type ≝
189  { group: Group;
190    embed: monomorphism group G
191  }.
192  
193 notation "hvbox(x \sub H)" with precedence 79
194 for @{ 'subgroupimage $H $x }.
195
196 interpretation "Subgroup image" 'subgroupimage H x =
197  (cic:/matita/algebra/groups/image.con _ _
198    (cic:/matita/algebra/groups/morphism.con _ _
199      (cic:/matita/algebra/groups/embed.con _ H))
200    x).
201
202 definition belongs_to_subgroup ≝
203  λG.λH:subgroup G.λx:G.∃y.x=y \sub H.
204
205 notation "hvbox(x ∈ H)" with precedence 79
206 for @{ 'belongs_to $x $H }.
207
208 interpretation "Belongs to subgroup" 'belongs_to x H =
209  (cic:/matita/algebra/groups/belongs_to_subgroup.con _ H x).
210
211 (* Left cosets *)
212
213 record left_coset (G:Group) : Type ≝
214  { element: G;
215    subgrp: subgroup G
216  }.
217
218 (* Here I would prefer 'magma_op, but this breaks something in the next definition *)
219 interpretation "Left_coset" 'times x C =
220  (cic:/matita/algebra/groups/left_coset.ind#xpointer(1/1/1) _ x C).
221
222 definition belongs_to_left_coset ≝
223  λG:Group.λC:left_coset G.λx:G.
224   ∃y.x=(element ? C)·y \sub (subgrp ? C).
225
226 interpretation "Belongs to left_coset" 'belongs_to x C =
227  (cic:/matita/algebra/groups/belongs_to_left_coset.con _ C x).
228
229 definition left_coset_eq ≝
230  λG.λC,C':left_coset G.
231   ∀x.((element ? C)·x \sub (subgrp ? C)) ∈ C'.
232   
233 interpretation "Left cosets equality" 'eq C C' =
234  (cic:/matita/algebra/groups/left_coset_eq.con _ C C').
235
236 definition left_coset_disjoint ≝
237  λG.λC,C':left_coset G.
238   ∀x.¬(((element ? C)·x \sub (subgrp ? C)) ∈ C'). 
239
240 notation "hvbox(a break ∥ b)"
241  non associative with precedence 45
242 for @{ 'disjoint $a $b }.
243
244 interpretation "Left cosets disjoint" 'disjoint C C' =
245  (cic:/matita/algebra/groups/left_coset_disjoint.con _ C C').
246
247 (*
248 (* The following should be a one-shot alias! *)
249 alias symbol "belongs_to" (instance 0) = "Belongs to subgroup".
250 theorem foo:
251  ∀G.∀x,y:(Type_of_Group G).∀H:subgroup G.
252   (x \sup -1 ·y) ∈ H → (mk_left_coset ? x H) = (mk_left_coset ? y H).
253 intros;
254 unfold left_coset_eq;
255 simplify in ⊢ (? → ? ? ? (? ? ? (? ? ? (? ? ? (? ? %)) ?)));
256 simplify in ⊢ (? → ? ? ? (? ? % ?));
257 simplify in ⊢ (? % → ?);
258 intros;
259 unfold belongs_to_left_coset;
260 simplify in ⊢ (? ? (λy:?.? ? ? (? ? ? (? ? ? (? ? ? (? ? %)) ?))));
261 simplify in ⊢ (? ? (λy:? %.?));
262 simplify in ⊢ (? ? (λy:?.? ? ? (? ? % ?)));
263 unfold belongs_to_subgroup in H1;
264 elim H1;
265 clear H1;
266 exists;
267 [
268
269 ].
270 qed.
271 *)
272
273 (*theorem foo:
274  \forall G:Group. \forall x1,x2:G. \forall H:subgroup G.
275   x1*x2^-1 \nin H \to x1*H does_not_overlap x2*H
276
277 theorem foo:
278  \forall x:G. \forall H:subgroup G. x \in x*H
279
280 definition disjoinct
281  (T: Type) (n:nat) (S: \forall x:nat. x < n -> {S:Type * (S -> T)})
282 :=
283  \forall i,j:nat. i < n \to j < n \to ...
284
285
286 check
287  (λG.λH,H':left_coset G.λx:Type_of_Group (group ? (subgrp ? H)). (embed ? (subgrp ? H) x)).
288
289 definition left_coset_eq ≝
290  λG.λH,H':left_coset G.
291   ∀x:group ? (subgrp ? H).
292    ex (group ? (subgroup ? H')) (λy.
293     (element ? H)·(embed ? (subgrp ? H) x) =
294     (element ? H')·(embed ? (subgrp ? H') y)).
295  
296 (*record left_coset (G:Group) : Type ≝
297  { subgroup: Group;
298    subgroup_is_subgroup: subgroup ≤ G;
299    element: G
300  }.
301
302 definition left_coset_eq ≝
303  λG.λH,H':left_coset G.
304   ∀x:subgroup ? H.
305    ex (subgroup ? H') (λy.
306     (element ? H)·(embed ? ? (subgroup_is_subgroup ? H) ˜ x) =
307     (element ? H')·(embed ? ? (subgroup_is_subgroup ? H') ˜ y)).
308 *)
309 *)