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 set "baseuri" "cic:/matita/algebra/groups/".
17 include "algebra/monoids.ma".
18 include "nat/le_arith.ma".
19 include "datatypes/bool.ma".
20 include "nat/compare.ma".
22 record PreGroup : Type ≝
23 { premonoid:> PreMonoid;
24 opp: premonoid -> premonoid
27 record isGroup (G:PreGroup) : Prop ≝
28 { is_monoid: isMonoid G;
29 opp_is_left_inverse: is_left_inverse (mk_Monoid ? is_monoid) (opp G);
30 opp_is_right_inverse: is_right_inverse (mk_Monoid ? is_monoid) (opp G)
34 { pregroup:> PreGroup;
35 group_properties:> isGroup pregroup
41 interpretation "Monoid coercion" 'monoid G =
42 (cic:/matita/algebra/groups/monoid.con G).*)
45 for @{ 'type_of_group $G }.
47 interpretation "Type_of_group coercion" 'type_of_group G =
48 (cic:/matita/algebra/groups/Type_of_Group.con G).
51 for @{ 'magma_of_group $G }.
53 interpretation "magma_of_group coercion" 'magma_of_group G =
54 (cic:/matita/algebra/groups/Magma_of_Group.con G).
56 notation "hvbox(x \sup (-1))" with precedence 89
59 interpretation "Group inverse" 'gopp x =
60 (cic:/matita/algebra/groups/opp.con _ x).
62 definition left_cancellable ≝
63 λT:Type. λop: T -> T -> T.
64 ∀x. injective ? ? (op x).
66 definition right_cancellable ≝
67 λT:Type. λop: T -> T -> T.
68 ∀x. injective ? ? (λz.op z x).
70 theorem eq_op_x_y_op_x_z_to_eq:
71 ∀G:Group. left_cancellable G (op G).
73 unfold left_cancellable;
76 rewrite < (e_is_left_unit ? (is_monoid ? (group_properties G)));
77 rewrite < (e_is_left_unit ? (is_monoid ? (group_properties G)) z);
78 rewrite < (opp_is_left_inverse ? (group_properties G) x);
79 rewrite > (associative ? (is_semi_group ? (is_monoid ? (group_properties G))));
80 rewrite > (associative ? (is_semi_group ? (is_monoid ? (group_properties G))));
86 theorem eq_op_x_y_op_z_y_to_eq:
87 ∀G:Group. right_cancellable G (op G).
89 unfold right_cancellable;
91 simplify;fold simplify (op G);
93 rewrite < (e_is_right_unit ? (is_monoid ? (group_properties G)));
94 rewrite < (e_is_right_unit ? (is_monoid ? (group_properties G)) z);
95 rewrite < (opp_is_right_inverse ? (group_properties G) x);
96 rewrite < (associative ? (is_semi_group ? (is_monoid ? (group_properties G))));
97 rewrite < (associative ? (is_semi_group ? (is_monoid ? (group_properties G))));
103 record finite_enumerable (T:Type) : Type ≝
107 index_of_sur: ∀x.index_of x ≤ order;
108 index_of_repr: ∀n. n≤order → index_of (repr n) = n;
109 repr_index_of: ∀x. repr (index_of x) = x
112 notation "hvbox(C \sub i)" with precedence 89
113 for @{ 'repr $C $i }.
115 (* CSC: multiple interpretations in the same file are not considered in the
117 interpretation "Finite_enumerable representation" 'repr C i =
118 (cic:/matita/algebra/groups/repr.con C _ i).*)
120 notation < "hvbox(|C|)" with precedence 89
123 interpretation "Finite_enumerable order" 'card C =
124 (cic:/matita/algebra/groups/order.con C _).
126 record finite_enumerable_SemiGroup : Type ≝
127 { semigroup:> SemiGroup;
128 is_finite_enumerable:> finite_enumerable semigroup
132 for @{ 'semigroup_of_finite_enumerable_semigroup $S }.
134 interpretation "Semigroup_of_finite_enumerable_semigroup"
135 'semigroup_of_finite_enumerable_semigroup S
137 (cic:/matita/algebra/groups/semigroup.con S).
140 for @{ 'magma_of_finite_enumerable_semigroup $S }.
142 interpretation "Magma_of_finite_enumerable_semigroup"
143 'magma_of_finite_enumerable_semigroup S
145 (cic:/matita/algebra/groups/Magma_of_finite_enumerable_SemiGroup.con S).
148 for @{ 'type_of_finite_enumerable_semigroup $S }.
150 interpretation "Type_of_finite_enumerable_semigroup"
151 'type_of_finite_enumerable_semigroup S
153 (cic:/matita/algebra/groups/Type_of_finite_enumerable_SemiGroup.con S).
155 interpretation "Finite_enumerable representation" 'repr S i =
156 (cic:/matita/algebra/groups/repr.con S
157 (cic:/matita/algebra/groups/is_finite_enumerable.con S) i).
159 notation "hvbox(ι e)" with precedence 60
160 for @{ 'index_of_finite_enumerable_semigroup $e }.
162 interpretation "Index_of_finite_enumerable representation"
163 'index_of_finite_enumerable_semigroup e
165 (cic:/matita/algebra/groups/index_of.con _
166 (cic:/matita/algebra/groups/is_finite_enumerable.con _) e).
169 (* several definitions/theorems to be moved somewhere else *)
171 definition ltb ≝ λn,m. leb n m ∧ notb (eqb n m).
173 theorem not_eq_to_le_to_lt: ∀n,m. n≠m → n≤m → n<m.
175 elim (le_to_or_lt_eq ? ? H1);
181 theorem ltb_to_Prop :
196 | apply (not_eq_to_le_to_lt ? ? H H1)
200 | apply le_to_not_lt;
201 generalize in match (not_le_to_lt ? ? H1);
209 theorem ltb_elim: ∀n,m:nat. ∀P:bool → Prop.
210 (n < m → (P true)) → (n ≮ m → (P false)) →
214 (match (ltb n m) with
216 | false ⇒ n ≮ m] → (P (ltb n m))).
217 apply Hcut.apply ltb_to_Prop.
223 theorem Not_lt_n_n: ∀n. n ≮ n.
228 apply (not_le_Sn_n ? H).
231 theorem eq_pred_to_eq:
232 ∀n,m. O < n → O < m → pred n = pred m → n = m.
234 generalize in match (eq_f ? ? S ? ? H2);
236 rewrite < S_pred in H3;
237 rewrite < S_pred in H3;
241 theorem le_pred_to_le:
242 ∀n,m. O < m → pred n ≤ pred m → n ≤ m.
247 rewrite > (S_pred m);
255 theorem le_to_le_pred:
256 ∀n,m. n ≤ m → pred n ≤ pred m.
262 generalize in match H1;
265 [ elim (not_le_Sn_O ? H1)
273 theorem lt_n_m_to_not_lt_m_Sn: ∀n,m. n < m → m ≮ S n.
279 generalize in match (le_S_S ? ? H);
281 generalize in match (transitive_le ? ? ? H2 H1);
283 apply (not_le_Sn_n ? H3).
286 theorem lt_S_S: ∀n,m. n < m → S n < S m.
289 apply (le_S_S ? ? H).
292 theorem lt_O_S: ∀n. O < S n.
299 theorem le_n_m_to_lt_m_Sn_to_eq_n_m: ∀n,m. n ≤ m → m < S n → n=m.
302 generalize in match (le_S_S_to_le ? ? H1);
304 apply cic:/matita/nat/orders/antisym_le.con;
310 (∀x,y.x≤n → y≤n → f x = f y → x=y) →
311 (∀m. m ≤ n → f m ≤ n) →
312 ∀x. x≤n → ∃y.f y = x ∧ y ≤ n.
315 [ apply (ex_intro ? ? O);
317 [ rewrite < (le_n_O_to_eq ? H2);
318 rewrite < (le_n_O_to_eq ? (H1 O ?));
327 let fSn1 ≝ f (S n1) in
329 match ltb fSn1 fx with
333 cut (∀x,y. x ≤ n1 → y ≤ n1 → f' x = f' y → x=y);
334 [ cut (∀x. x ≤ n1 → f' x ≤ n1);
335 [ apply (nat_compare_elim (f (S n1)) x);
337 elim (H f' ? ? (pred x));
344 apply (ex_intro ? ? a);
346 [ generalize in match (eq_f ? ? S ? ? H6);
349 rewrite < S_pred in H5;
350 [ generalize in match H4;
354 apply (ltb_elim (f (S n1)) (f a));
359 | apply (ltn_to_ltO ? ? H4)
363 generalize in match (not_lt_to_le ? ? H4);
366 generalize in match (le_n_m_to_lt_m_Sn_to_eq_n_m ? ? H6 H5);
368 generalize in match (H1 ? ? ? ? H4);
370 generalize in match (le_n_m_to_lt_m_Sn_to_eq_n_m ? ? H6 H5);
372 generalize in match (H1 ? ? ? ? H9);
375 elim (not_le_Sn_n ? H7)
385 | apply (ltn_to_ltO ? ? H4)
392 | apply le_S_S_to_le;
395 | apply (ltn_to_ltO ? ? H4)
399 apply (ex_intro ? ? (S n1));
412 apply (ex_intro ? ? a);
414 [ generalize in match H4;
418 apply (ltb_elim (f (S n1)) (f a));
421 generalize in match (lt_S_S ? ? H5);
423 rewrite < S_pred in H6;
424 [ elim (lt_n_m_to_not_lt_m_Sn ? ? H4 H6)
425 | apply (ltn_to_ltO ? ? H4)
436 | rewrite > (pred_Sn n1);
438 generalize in match (H2 (S n1));
440 generalize in match (lt_to_le_to_lt ? ? ? H4 (H5 (le_n ?)));
450 apply (ltb_elim (f (S n1)) (f x1));
453 [ generalize in match (H2 x1);
455 change in match n1 with (pred (S n1));
460 | generalize in match (H2 (S n1) (le_n ?));
462 generalize in match (not_lt_to_le ? ? H4);
464 generalize in match (transitive_le ? ? ? H7 H6);
466 cut (f x1 ≠ f (S n1));
467 [ generalize in match (not_eq_to_le_to_lt ? ? Hcut1 H7);
470 generalize in match (transitive_le ? ? ? H9 H6);
476 generalize in match (H1 ? ? ? ? H9);
479 apply (not_le_Sn_n ? H5)
490 apply (ltb_elim (f (S n1)) (f x1));
492 apply (ltb_elim (f (S n1)) (f y));
496 [ apply (H1 ? ? ? ? Hcut);
499 | apply eq_pred_to_eq;
500 [ apply (ltn_to_ltO ? ? H7)
501 | apply (ltn_to_ltO ? ? H6)
505 | (* pred (f x1) = f y absurd since y ≠ S n1 and thus f y ≠ f (S n1)
506 so that f y < f (S n1) < f x1; hence pred (f x1) = f y is absurd *)
508 [ generalize in match (lt_to_not_eq ? ? Hcut);
510 cut (f y ≠ f (S n1));
511 [ cut (f y < f (S n1));
512 [ rewrite < H8 in Hcut2;
515 generalize in match (le_S_S ? ? Hcut2);
517 generalize in match (transitive_le ? ? ? H10 H7);
519 rewrite < (S_pred (f x1)) in H11;
520 [ elim (not_le_Sn_n ? H11)
521 | fold simplify ((f (S n1)) < (f x1)) in H7;
522 apply (ltn_to_ltO ? ? H7)
524 | apply not_eq_to_le_to_lt;
526 | apply not_lt_to_le;
533 apply (H1 ? ? ? ? H10);
543 | (* f x1 = pred (f y) absurd since it implies S (f x1) = f y and
544 f x1 ≤ f (S n1) < f y = S (f x1) so that f x1 = f (S n1); by
545 injectivity x1 = S n1 that is absurd since x1 ≤ n1 *)
546 generalize in match (eq_f ? ? S ? ? H8);
548 rewrite < S_pred in H9;
549 [ rewrite < H9 in H6;
550 generalize in match (not_lt_to_le ? ? H7);
553 generalize in match (le_S_S ? ? H10);
555 generalize in match (antisym_le ? ? H11 H6);
557 generalize in match (inj_S ? ? H12);
559 generalize in match (H1 ? ? ? ? H13);
562 elim (not_le_Sn_n ? H4)
567 | apply (ltn_to_ltO ? ? H6)
569 | apply (H1 ? ? ? ? H8);
577 theorem finite_enumerable_SemiGroup_to_left_cancellable_to_right_cancellable_to_isMonoid:
578 ∀G:finite_enumerable_SemiGroup.
579 left_cancellable ? (op G) →
580 right_cancellable ? (op G) →
581 ∃e:G. isMonoid (mk_PreMonoid G e).
583 letin f ≝ (λn.ι(G \sub O · G \sub n));
584 cut (∀n.n ≤ order ? (is_finite_enumerable G) → ∃m.f m = n);
585 [ letin EX ≝ (Hcut O ?);
592 letin HH ≝ (eq_f ? ? (repr ? (is_finite_enumerable G)) ? ? H2);
594 rewrite > (repr_index_of ? (is_finite_enumerable G)) in HH;
595 apply (ex_intro ? ? (G \sub a));
596 letin GOGO ≝ (refl_eq ? (repr ? (is_finite_enumerable G) O));
598 rewrite < HH in GOGO;
599 rewrite < HH in GOGO:(? ? % ?);
600 rewrite > (associative ? G) in GOGO;
601 letin GaGa ≝ (H ? ? ? GOGO);
606 apply (semigroup_properties G)
607 | unfold is_left_unit; intro;
608 letin GaxGax ≝ (refl_eq ? (G \sub a ·x));
610 rewrite < GaGa in GaxGax:(? ? % ?);
611 rewrite > (associative ? (semigroup_properties G)) in GaxGax;
612 apply (H ? ? ? GaxGax)
613 | unfold is_right_unit; intro;
614 letin GaxGax ≝ (refl_eq ? (x·G \sub a));
616 rewrite < GaGa in GaxGax:(? ? % ?);
617 rewrite < (associative ? (semigroup_properties G)) in GaxGax;
618 apply (H1 ? ? ? GaxGax)
622 elim (pigeonhole (order ? G) f ? ? ? H2);
623 [ apply (ex_intro ? ? a);
627 change in H5 with (ι(G \sub O · G \sub x) = ι(G \sub O · G \sub y));
628 cut (G \sub (ι(G \sub O · G \sub x)) = G \sub (ι(G \sub O · G \sub y)));
629 [ rewrite > (repr_index_of ? ? (G \sub O · G \sub x)) in Hcut;
630 rewrite > (repr_index_of ? ? (G \sub O · G \sub y)) in Hcut;
631 generalize in match (H ? ? ? Hcut);
633 generalize in match (eq_f ? ? (index_of ? G) ? ? H6);
635 rewrite > index_of_repr in H7;
636 rewrite > index_of_repr in H7;