-
Notifications
You must be signed in to change notification settings - Fork 110
/
action.v
2734 lines (2156 loc) · 98.8 KB
/
action.v
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
(* (c) Copyright 2006-2016 Microsoft Corporation and Inria. *)
(* Distributed under the terms of CeCILL-B. *)
From mathcomp Require Import ssreflect ssrbool ssrfun eqtype ssrnat div seq.
From mathcomp Require Import fintype bigop finset fingroup morphism perm.
From mathcomp Require Import automorphism quotient.
(******************************************************************************)
(* Group action: orbits, stabilisers, transitivity. *)
(* is_action D to == the function to : T -> aT -> T defines an action *)
(* of D : {set aT} on T. *)
(* action D T == structure for a function defining an action of D. *)
(* act_dom to == the domain D of to : action D rT. *)
(* {action: aT &-> T} == structure for a total action. *)
(* := action [set: aT] T *)
(* TotalAction to1 toM == the constructor for total actions; to1 and toM *)
(* are the proofs of the action identities for 1 and *)
(* a * b, respectively. *)
(* is_groupAction R to == to is a group action on range R: for all a in D, *)
(* the permutation induced by to a is in Aut R. Thus *)
(* the action of D must be trivial outside R. *)
(* groupAction D R == the structure for group actions of D on R. This *)
(* is a telescope on action D rT. *)
(* gact_range to == the range R of to : groupAction D R. *)
(* GroupAction toAut == constructs a groupAction for action to from *)
(* toAut : actm to @* D \subset Aut R (actm to is *)
(* the morphism to {perm rT} associated to 'to'). *)
(* orbit to A x == the orbit of x under the action of A via to. *)
(* orbit_transversal to A S == a transversal of the partition orbit to A @: S *)
(* of S, provided A acts on S via to. *)
(* amove to A x y == the set of a in A whose action sends x to y. *)
(* 'C_A[x | to] == the stabiliser of x : rT in A :&: D. *)
(* 'C_A(S | to) == the pointwise stabiliser of S : {set rT} in D :&: A. *)
(* 'N_A(S | to) == the global stabiliser of S : {set rT} in D :&: A. *)
(* 'Fix_(S | to)[a] == the set of fixpoints of a in S. *)
(* 'Fix_(S | to)(A) == the set of fixpoints of A in S. *)
(* In the first three _A can be omitted and defaults to the domain D of to; *)
(* in the last two S can be omitted and defaults to [set: T], so 'Fix_to[a] *)
(* is the set of all fixpoints of a. *)
(* The domain restriction ensures that stabilisers have a canonical group *)
(* structure, but note that 'Fix sets are generally not groups. Indeed, we *)
(* provide alternative definitions when to is a group action on R: *)
(* 'C_(G | to)(A) == the centraliser in R :&: G of the group action of *)
(* D :&: A via to *)
(* 'C_(G | to)[a] == the centraliser in R :&: G of a \in D, via to. *)
(* These sets are groups when G is; G can be omitted: 'C(|to)(A) is the *)
(* centraliser in R of the action of D :&: A via to. *)
(* [acts A, on S | to] == A \subset D acts on the set S via to. *)
(* {acts A, on S | to} == A acts on the set S (Prop statement). *)
(* {acts A, on group G | to} == [acts A, on S | to] /\ G \subset R, i.e., *)
(* A \subset D acts on G \subset R, via *)
(* to : groupAction D R. *)
(* [transitive A, on S | to] == A acts transitively on S. *)
(* [faithful A, on S | to] == A acts faithfully on S. *)
(* acts_irreducibly to A G == A acts irreducibly via the groupAction to *)
(* on the nontrivial group G, i.e., A does *)
(* not act on any nontrivial subgroup of G. *)
(* Important caveat: the definitions of orbit, amove, 'Fix_(S | to)(A), *)
(* transitive and faithful assume that A is a subset of the domain D. As most *)
(* of the permutation actions we consider are total this is usually harmless. *)
(* (Note that the theory of partial actions is only partially developed.) *)
(* In all of the above, to is expected to be the actual action structure, *)
(* not merely the function. There is a special scope %act for actions, and *)
(* constructions and notations for many classical actions: *)
(* 'P == natural action of a permutation group via aperm. *)
(* 'J == internal group action (conjugation) via conjg (_ ^ _). *)
(* 'R == regular group action (right translation) via mulg (_ * _). *)
(* (However, to limit ambiguity, _ * _ is NOT a canonical action.) *)
(* to^* == the action induced by to on {set rT} via to^* (== setact to). *)
(* 'Js == the internal action on subsets via _ :^ _, equivalent to 'J^*. *)
(* 'Rs == the regular action on subsets via rcoset, equivalent to 'R^*. *)
(* 'JG == the conjugation action on {group rT} via (_ :^ _)%G. *)
(* to / H == the action induced by to on coset_of H via qact to H, and *)
(* restricted to (qact_dom to H) == 'N(rcosets H 'N(H) | to^* ). *)
(* 'Q == the action induced to cosets by conjugation; the domain is *)
(* qact_dom 'J H, which is provably equal to 'N(H). *)
(* to %% A == the action of coset_of A via modact to A, with domain D / A *)
(* and support restricted to 'C(D :&: A | to). *)
(* to \ sAD == the action of A via ract to sAD == to, if sAD : A \subset D. *)
(* [Aut G] == the permutation action restricted to Aut G, via autact G. *)
(* <[nRA]> == the action of A on R via actby nRA == to in A and on R, and *)
(* the trivial action elsewhere; here nRA : [acts A, on R | to] *)
(* or nRA : {acts A, on group R | to}. *)
(* to^? == the action induced by to on sT : @subType rT P, via subact to *)
(* with domain subact_dom P to == 'N([set x | P x] | to). *)
(* <<phi>> == the action of phi : D >-> {perm rT}, via mact phi. *)
(* to \o f == the composite action (with domain f @*^-1 D) of the action to *)
(* with f : {morphism G >-> aT}, via comp_act to f. Here f must *)
(* be the actual morphism object (e.g., coset_morphism H), not *)
(* the underlying function (e.g., coset H). *)
(* The explicit application of an action to is usually written (to%act x a), *)
(* but %act can be omitted if to is an abstract action or a set action to0^*. *)
(* Note that this form will simplify and expose the acting function. *)
(* There is a %gact scope for group actions; the notations above are *)
(* recognised in %gact when they denote canonical group actions. *)
(* Actions can be used to define morphisms: *)
(* actperm to == the morphism D >-> {perm rT} induced by to. *)
(* actm to a == if a \in D the function on D induced by the action to, else *)
(* the identity function. If to is a group action with range R *)
(* then actm to a is canonically a morphism on R. *)
(* We also define here the restriction operation on permutations (the domain *)
(* of this operations is a stabiliser), and local automorphism groups: *)
(* restr_perm S p == if p acts on S, the permutation with support in S that *)
(* coincides with p on S; else the identity. Note that *)
(* restr_perm is a permutation group morphism that maps *)
(* Aut G to Aut S when S is a subgroup of G. *)
(* Aut_in A G == the local permutation group 'N_A(G | 'P) / 'C_A(G | 'P) *)
(* Usually A is an automorphism group, and then Aut_in A G *)
(* is isomorphic to a subgroup of Aut G, specifically *)
(* restr_perm @* A. *)
(* Finally, gproduct.v will provide a semi-direct group construction that *)
(* maps an external group action to an internal one; the theory of morphisms *)
(* between such products makes use of the following definition: *)
(* morph_act to to' f fA <=> the action of to' on the images of f and fA is *)
(* the image of the action of to, i.e., for all x and a we *)
(* have f (to x a) = to' (f x) (fA a). Note that there is *)
(* no mention of the domains of to and to'; if needed, this *)
(* predicate should be restricted via the {in ...} notation *)
(* and domain conditions should be added. *)
(******************************************************************************)
Set Implicit Arguments.
Unset Strict Implicit.
Unset Printing Implicit Defensive.
Import GroupScope.
Section ActionDef.
Variables (aT : finGroupType) (D : {set aT}) (rT : Type).
Implicit Types a b : aT.
Implicit Type x : rT.
Definition act_morph to x := forall a b, to x (a * b) = to (to x a) b.
Definition is_action to :=
left_injective to /\ forall x, {in D &, act_morph to x}.
Record action := Action {act :> rT -> aT -> rT; _ : is_action act}.
Definition clone_action to :=
let: Action _ toP := to return {type of Action for to} -> action in
fun k => k toP.
End ActionDef.
(* Need to close the Section here to avoid re-declaring all Argument Scopes *)
Delimit Scope action_scope with act.
Bind Scope action_scope with action.
Arguments act_morph {aT rT%type} to x%g.
Arguments is_action {aT} D%g {rT} to.
Arguments act {aT D%g rT%type} to%act x%g a%g : rename.
Arguments clone_action [aT D%g rT%type to%act] _.
Notation "{ 'action' aT &-> T }" := (action [set: aT] T)
(at level 0, format "{ 'action' aT &-> T }") : type_scope.
Notation "[ 'action' 'of' to ]" := (clone_action (@Action _ _ _ to))
(at level 0, format "[ 'action' 'of' to ]") : form_scope.
Definition act_dom aT D rT of @action aT D rT := D.
Section TotalAction.
Variables (aT : finGroupType) (rT : Type) (to : rT -> aT -> rT).
Hypotheses (to1 : to^~ 1 =1 id) (toM : forall x, act_morph to x).
Lemma is_total_action : is_action setT to.
Proof.
split=> [a | x a b _ _] /=; last by rewrite toM.
by apply: can_inj (to^~ a^-1) _ => x; rewrite -toM ?mulgV.
Qed.
Definition TotalAction := Action is_total_action.
End TotalAction.
Section ActionDefs.
Variables (aT aT' : finGroupType) (D : {set aT}) (D' : {set aT'}).
Definition morph_act rT rT' (to : action D rT) (to' : action D' rT') f fA :=
forall x a, f (to x a) = to' (f x) (fA a).
Variable rT : finType. (* Most definitions require a finType structure on rT *)
Implicit Type to : action D rT.
Implicit Type A : {set aT}.
Implicit Type S : {set rT}.
Definition actm to a := if a \in D then to^~ a else id.
Definition setact to S a := [set to x a | x in S].
Definition orbit to A x := to x @: A.
Definition amove to A x y := [set a in A | to x a == y].
Definition afix to A := [set x | A \subset [set a | to x a == x]].
Definition astab S to := D :&: [set a | S \subset [set x | to x a == x]].
Definition astabs S to := D :&: [set a | S \subset to^~ a @^-1: S].
Definition acts_on A S to := {in A, forall a x, (to x a \in S) = (x \in S)}.
Definition atrans A S to := S \in orbit to A @: S.
Definition faithful A S to := A :&: astab S to \subset [1].
End ActionDefs.
Arguments setact {aT D%g rT} to%act S%g a%g.
Arguments orbit {aT D%g rT} to%act A%g x%g.
Arguments amove {aT D%g rT} to%act A%g x%g y%g.
Arguments afix {aT D%g rT} to%act A%g.
Arguments astab {aT D%g rT} S%g to%act.
Arguments astabs {aT D%g rT} S%g to%act.
Arguments acts_on {aT D%g rT} A%g S%g to%act.
Arguments atrans {aT D%g rT} A%g S%g to%act.
Arguments faithful {aT D%g rT} A%g S%g to%act.
Notation "to ^*" := (setact to) (at level 2, format "to ^*") : fun_scope.
Prenex Implicits orbit amove.
Notation "''Fix_' to ( A )" := (afix to A)
(at level 8, to at level 2, format "''Fix_' to ( A )") : group_scope.
(* camlp4 grammar factoring *)
Notation "''Fix_' ( to ) ( A )" := 'Fix_to(A)
(at level 8, only parsing) : group_scope.
Notation "''Fix_' ( S | to ) ( A )" := (S :&: 'Fix_to(A))
(at level 8, format "''Fix_' ( S | to ) ( A )") : group_scope.
Notation "''Fix_' to [ a ]" := ('Fix_to([set a]))
(at level 8, to at level 2, format "''Fix_' to [ a ]") : group_scope.
Notation "''Fix_' ( S | to ) [ a ]" := (S :&: 'Fix_to[a])
(at level 8, format "''Fix_' ( S | to ) [ a ]") : group_scope.
Notation "''C' ( S | to )" := (astab S to)
(at level 8, format "''C' ( S | to )") : group_scope.
Notation "''C_' A ( S | to )" := (A :&: 'C(S | to))
(at level 8, A at level 2, format "''C_' A ( S | to )") : group_scope.
Notation "''C_' ( A ) ( S | to )" := 'C_A(S | to)
(at level 8, only parsing) : group_scope.
Notation "''C' [ x | to ]" := ('C([set x] | to))
(at level 8, format "''C' [ x | to ]") : group_scope.
Notation "''C_' A [ x | to ]" := (A :&: 'C[x | to])
(at level 8, A at level 2, format "''C_' A [ x | to ]") : group_scope.
Notation "''C_' ( A ) [ x | to ]" := 'C_A[x | to]
(at level 8, only parsing) : group_scope.
Notation "''N' ( S | to )" := (astabs S to)
(at level 8, format "''N' ( S | to )") : group_scope.
Notation "''N_' A ( S | to )" := (A :&: 'N(S | to))
(at level 8, A at level 2, format "''N_' A ( S | to )") : group_scope.
Notation "[ 'acts' A , 'on' S | to ]" := (A \subset pred_of_set 'N(S | to))
(at level 0, format "[ 'acts' A , 'on' S | to ]") : form_scope.
Notation "{ 'acts' A , 'on' S | to }" := (acts_on A S to)
(at level 0, format "{ 'acts' A , 'on' S | to }") : form_scope.
Notation "[ 'transitive' A , 'on' S | to ]" := (atrans A S to)
(at level 0, format "[ 'transitive' A , 'on' S | to ]") : form_scope.
Notation "[ 'faithful' A , 'on' S | to ]" := (faithful A S to)
(at level 0, format "[ 'faithful' A , 'on' S | to ]") : form_scope.
Section RawAction.
(* Lemmas that do not require the group structure on the action domain. *)
(* Some lemmas like actMin would be actually be valid for arbitrary rT, *)
(* e.g., for actions on a function type, but would be difficult to use *)
(* as a view due to the confusion between parameters and assumptions. *)
Variables (aT : finGroupType) (D : {set aT}) (rT : finType) (to : action D rT).
Implicit Types (a : aT) (x y : rT) (A B : {set aT}) (S T : {set rT}).
Lemma act_inj : left_injective to. Proof. by case: to => ? []. Qed.
Arguments act_inj : clear implicits.
Lemma actMin x : {in D &, act_morph to x}.
Proof. by case: to => ? []. Qed.
Lemma actmEfun a : a \in D -> actm to a = to^~ a.
Proof. by rewrite /actm => ->. Qed.
Lemma actmE a : a \in D -> actm to a =1 to^~ a.
Proof. by move=> Da; rewrite actmEfun. Qed.
Lemma setactE S a : to^* S a = [set to x a | x in S].
Proof. by []. Qed.
Lemma mem_setact S a x : x \in S -> to x a \in to^* S a.
Proof. exact: mem_imset. Qed.
Lemma card_setact S a : #|to^* S a| = #|S|.
Proof. by apply: card_imset; apply: act_inj. Qed.
Lemma setact_is_action : is_action D to^*.
Proof.
split=> [a R S eqRS | a b Da Db S]; last first.
by rewrite /setact /= -imset_comp; apply: eq_imset => x; apply: actMin.
apply/setP=> x; apply/idP/idP=> /(mem_setact a).
by rewrite eqRS => /imsetP[y Sy /act_inj->].
by rewrite -eqRS => /imsetP[y Sy /act_inj->].
Qed.
Canonical set_action := Action setact_is_action.
Lemma orbitE A x : orbit to A x = to x @: A. Proof. by []. Qed.
Lemma orbitP A x y :
reflect (exists2 a, a \in A & to x a = y) (y \in orbit to A x).
Proof. by apply: (iffP imsetP) => [] [a]; exists a. Qed.
Lemma mem_orbit A x a : a \in A -> to x a \in orbit to A x.
Proof. exact: mem_imset. Qed.
Lemma afixP A x : reflect (forall a, a \in A -> to x a = x) (x \in 'Fix_to(A)).
Proof.
rewrite inE; apply: (iffP subsetP) => [xfix a /xfix | xfix a Aa].
by rewrite inE => /eqP.
by rewrite inE xfix.
Qed.
Lemma afixS A B : A \subset B -> 'Fix_to(B) \subset 'Fix_to(A).
Proof. by move=> sAB; apply/subsetP=> u; rewrite !inE; apply: subset_trans. Qed.
Lemma afixU A B : 'Fix_to(A :|: B) = 'Fix_to(A) :&: 'Fix_to(B).
Proof. by apply/setP=> x; rewrite !inE subUset. Qed.
Lemma afix1P a x : reflect (to x a = x) (x \in 'Fix_to[a]).
Proof. by rewrite inE sub1set inE; apply: eqP. Qed.
Lemma astabIdom S : 'C_D(S | to) = 'C(S | to).
Proof. by rewrite setIA setIid. Qed.
Lemma astab_dom S : {subset 'C(S | to) <= D}.
Proof. by move=> a /setIP[]. Qed.
Lemma astab_act S a x : a \in 'C(S | to) -> x \in S -> to x a = x.
Proof.
rewrite 2!inE => /andP[_ cSa] Sx; apply/eqP.
by have:= subsetP cSa x Sx; rewrite inE.
Qed.
Lemma astabS S1 S2 : S1 \subset S2 -> 'C(S2 | to) \subset 'C(S1 | to).
Proof.
move=> sS12; apply/subsetP=> x; rewrite !inE => /andP[->].
exact: subset_trans.
Qed.
Lemma astabsIdom S : 'N_D(S | to) = 'N(S | to).
Proof. by rewrite setIA setIid. Qed.
Lemma astabs_dom S : {subset 'N(S | to) <= D}.
Proof. by move=> a /setIdP[]. Qed.
Lemma astabs_act S a x : a \in 'N(S | to) -> (to x a \in S) = (x \in S).
Proof.
rewrite 2!inE subEproper properEcard => /andP[_].
rewrite (card_preimset _ (act_inj _)) ltnn andbF orbF => /eqP{2}->.
by rewrite inE.
Qed.
Lemma astab_sub S : 'C(S | to) \subset 'N(S | to).
Proof.
apply/subsetP=> a cSa; rewrite !inE (astab_dom cSa).
by apply/subsetP=> x Sx; rewrite inE (astab_act cSa).
Qed.
Lemma astabsC S : 'N(~: S | to) = 'N(S | to).
Proof.
apply/setP=> a; apply/idP/idP=> nSa; rewrite !inE (astabs_dom nSa).
by rewrite -setCS -preimsetC; apply/subsetP=> x; rewrite inE astabs_act.
by rewrite preimsetC setCS; apply/subsetP=> x; rewrite inE astabs_act.
Qed.
Lemma astabsI S T : 'N(S | to) :&: 'N(T | to) \subset 'N(S :&: T | to).
Proof.
apply/subsetP=> a; rewrite !inE -!andbA preimsetI => /and4P[-> nSa _ nTa] /=.
by rewrite setISS.
Qed.
Lemma astabs_setact S a : a \in 'N(S | to) -> to^* S a = S.
Proof.
move=> nSa; apply/eqP; rewrite eqEcard card_setact leqnn andbT.
by apply/subsetP=> _ /imsetP[x Sx ->]; rewrite astabs_act.
Qed.
Lemma astab1_set S : 'C[S | set_action] = 'N(S | to).
Proof.
apply/setP=> a; apply/idP/idP=> nSa.
case/setIdP: nSa => Da; rewrite !inE Da sub1set inE => /eqP defS.
by apply/subsetP=> x Sx; rewrite inE -defS mem_setact.
by rewrite !inE (astabs_dom nSa) sub1set inE /= astabs_setact.
Qed.
Lemma astabs_set1 x : 'N([set x] | to) = 'C[x | to].
Proof.
apply/eqP; rewrite eqEsubset astab_sub andbC setIS //.
by apply/subsetP=> a; rewrite ?(inE,sub1set).
Qed.
Lemma acts_dom A S : [acts A, on S | to] -> A \subset D.
Proof. by move=> nSA; rewrite (subset_trans nSA) ?subsetIl. Qed.
Lemma acts_act A S : [acts A, on S | to] -> {acts A, on S | to}.
Proof. by move=> nAS a Aa x; rewrite astabs_act ?(subsetP nAS). Qed.
Lemma astabCin A S :
A \subset D -> (A \subset 'C(S | to)) = (S \subset 'Fix_to(A)).
Proof.
move=> sAD; apply/subsetP/subsetP=> [sAC x xS | sSF a aA].
by apply/afixP=> a aA; apply: astab_act (sAC _ aA) xS.
rewrite !inE (subsetP sAD _ aA); apply/subsetP=> x xS.
by move/afixP/(_ _ aA): (sSF _ xS); rewrite inE => ->.
Qed.
Section ActsSetop.
Variables (A : {set aT}) (S T : {set rT}).
Hypotheses (AactS : [acts A, on S | to]) (AactT : [acts A, on T | to]).
Lemma astabU : 'C(S :|: T | to) = 'C(S | to) :&: 'C(T | to).
Proof. by apply/setP=> a; rewrite !inE subUset; case: (a \in D). Qed.
Lemma astabsU : 'N(S | to) :&: 'N(T | to) \subset 'N(S :|: T | to).
Proof.
by rewrite -(astabsC S) -(astabsC T) -(astabsC (S :|: T)) setCU astabsI.
Qed.
Lemma astabsD : 'N(S | to) :&: 'N(T | to) \subset 'N(S :\: T| to).
Proof. by rewrite setDE -(astabsC T) astabsI. Qed.
Lemma actsI : [acts A, on S :&: T | to].
Proof. by apply: subset_trans (astabsI S T); rewrite subsetI AactS. Qed.
Lemma actsU : [acts A, on S :|: T | to].
Proof. by apply: subset_trans astabsU; rewrite subsetI AactS. Qed.
Lemma actsD : [acts A, on S :\: T | to].
Proof. by apply: subset_trans astabsD; rewrite subsetI AactS. Qed.
End ActsSetop.
Lemma acts_in_orbit A S x y :
[acts A, on S | to] -> y \in orbit to A x -> x \in S -> y \in S.
Proof.
by move=> nSA/imsetP[a Aa ->{y}] Sx; rewrite (astabs_act _ (subsetP nSA a Aa)).
Qed.
Lemma subset_faithful A B S :
B \subset A -> [faithful A, on S | to] -> [faithful B, on S | to].
Proof. by move=> sAB; apply: subset_trans; apply: setSI. Qed.
Section Reindex.
Variables (vT : Type) (idx : vT) (op : Monoid.com_law idx) (S : {set rT}).
Lemma reindex_astabs a F : a \in 'N(S | to) ->
\big[op/idx]_(i in S) F i = \big[op/idx]_(i in S) F (to i a).
Proof.
move=> nSa; rewrite (reindex_inj (act_inj a)); apply: eq_bigl => x.
exact: astabs_act.
Qed.
Lemma reindex_acts A a F : [acts A, on S | to] -> a \in A ->
\big[op/idx]_(i in S) F i = \big[op/idx]_(i in S) F (to i a).
Proof. by move=> nSA /(subsetP nSA); apply: reindex_astabs. Qed.
End Reindex.
End RawAction.
Arguments act_inj {aT D rT} to a [x1 x2] : rename.
Notation "to ^*" := (set_action to) : action_scope.
Arguments orbitP {aT D rT to A x y}.
Arguments afixP {aT D rT to A x}.
Arguments afix1P {aT D rT to a x}.
Arguments reindex_astabs [aT D rT] to [vT idx op S] a [F].
Arguments reindex_acts [aT D rT] to [vT idx op S A a F].
Section PartialAction.
(* Lemmas that require a (partial) group domain. *)
Variables (aT : finGroupType) (D : {group aT}) (rT : finType).
Variable to : action D rT.
Implicit Types a : aT.
Implicit Types x y : rT.
Implicit Types A B : {set aT}.
Implicit Types G H : {group aT}.
Implicit Types S : {set rT}.
Lemma act1 x : to x 1 = x.
Proof. by apply: (act_inj to 1); rewrite -actMin ?mulg1. Qed.
Lemma actKin : {in D, right_loop invg to}.
Proof. by move=> a Da /= x; rewrite -actMin ?groupV // mulgV act1. Qed.
Lemma actKVin : {in D, rev_right_loop invg to}.
Proof. by move=> a Da /= x; rewrite -{2}(invgK a) actKin ?groupV. Qed.
Lemma setactVin S a : a \in D -> to^* S a^-1 = to^~ a @^-1: S.
Proof.
by move=> Da; apply: can2_imset_pre; [apply: actKVin | apply: actKin].
Qed.
Lemma actXin x a i : a \in D -> to x (a ^+ i) = iter i (to^~ a) x.
Proof.
move=> Da; elim: i => /= [|i <-]; first by rewrite act1.
by rewrite expgSr actMin ?groupX.
Qed.
Lemma afix1 : 'Fix_to(1) = setT.
Proof. by apply/setP=> x; rewrite !inE sub1set inE act1 eqxx. Qed.
Lemma afixD1 G : 'Fix_to(G^#) = 'Fix_to(G).
Proof. by rewrite -{2}(setD1K (group1 G)) afixU afix1 setTI. Qed.
Lemma orbit_refl G x : x \in orbit to G x.
Proof. by rewrite -{1}[x]act1 mem_orbit. Qed.
Local Notation orbit_rel A := (fun x y => x \in orbit to A y).
Lemma contra_orbit G x y : x \notin orbit to G y -> x != y.
Proof. by apply: contraNneq => ->; apply: orbit_refl. Qed.
Lemma orbit_in_sym G : G \subset D -> symmetric (orbit_rel G).
Proof.
move=> sGD; apply: symmetric_from_pre => x y /imsetP[a Ga].
by move/(canLR (actKin (subsetP sGD a Ga))) <-; rewrite mem_orbit ?groupV.
Qed.
Lemma orbit_in_trans G : G \subset D -> transitive (orbit_rel G).
Proof.
move=> sGD _ _ z /imsetP[a Ga ->] /imsetP[b Gb ->].
by rewrite -actMin ?mem_orbit ?groupM // (subsetP sGD).
Qed.
Lemma orbit_in_eqP G x y :
G \subset D -> reflect (orbit to G x = orbit to G y) (x \in orbit to G y).
Proof.
move=> sGD; apply: (iffP idP) => [yGx|<-]; last exact: orbit_refl.
by apply/setP=> z; apply/idP/idP=> /orbit_in_trans-> //; rewrite orbit_in_sym.
Qed.
Lemma orbit_in_transl G x y z :
G \subset D -> y \in orbit to G x ->
(y \in orbit to G z) = (x \in orbit to G z).
Proof.
by move=> sGD Gxy; rewrite !(orbit_in_sym sGD _ z) (orbit_in_eqP y x sGD Gxy).
Qed.
Lemma orbit_act_in x a G :
G \subset D -> a \in G -> orbit to G (to x a) = orbit to G x.
Proof. by move=> sGD /mem_orbit/orbit_in_eqP->. Qed.
Lemma orbit_actr_in x a G y :
G \subset D -> a \in G -> (to y a \in orbit to G x) = (y \in orbit to G x).
Proof. by move=> sGD /mem_orbit/orbit_in_transl->. Qed.
Lemma orbit_inv_in A x y :
A \subset D -> (y \in orbit to A^-1 x) = (x \in orbit to A y).
Proof.
move/subsetP=> sAD; apply/imsetP/imsetP=> [] [a Aa ->].
by exists a^-1; rewrite -?mem_invg ?actKin // -groupV sAD -?mem_invg.
by exists a^-1; rewrite ?memV_invg ?actKin // sAD.
Qed.
Lemma orbit_lcoset_in A a x :
A \subset D -> a \in D ->
orbit to (a *: A) x = orbit to A (to x a).
Proof.
move/subsetP=> sAD Da; apply/setP=> y; apply/imsetP/imsetP=> [] [b Ab ->{y}].
by exists (a^-1 * b); rewrite -?actMin ?mulKVg // ?sAD -?mem_lcoset.
by exists (a * b); rewrite ?mem_mulg ?set11 ?actMin // sAD.
Qed.
Lemma orbit_rcoset_in A a x y :
A \subset D -> a \in D ->
(to y a \in orbit to (A :* a) x) = (y \in orbit to A x).
Proof.
move=> sAD Da; rewrite -orbit_inv_in ?mul_subG ?sub1set // invMg.
by rewrite invg_set1 orbit_lcoset_in ?inv_subG ?groupV ?actKin ?orbit_inv_in.
Qed.
Lemma orbit_conjsg_in A a x y :
A \subset D -> a \in D ->
(to y a \in orbit to (A :^ a) (to x a)) = (y \in orbit to A x).
Proof.
move=> sAD Da; rewrite conjsgE.
by rewrite orbit_lcoset_in ?groupV ?mul_subG ?sub1set ?actKin ?orbit_rcoset_in.
Qed.
Lemma orbit1P G x : reflect (orbit to G x = [set x]) (x \in 'Fix_to(G)).
Proof.
apply: (iffP afixP) => [xfix | xfix a Ga].
apply/eqP; rewrite eq_sym eqEsubset sub1set -{1}[x]act1 mem_imset //=.
by apply/subsetP=> y; case/imsetP=> a Ga ->; rewrite inE xfix.
by apply/set1P; rewrite -xfix mem_imset.
Qed.
Lemma card_orbit1 G x : #|orbit to G x| = 1%N -> orbit to G x = [set x].
Proof.
move=> orb1; apply/eqP; rewrite eq_sym eqEcard {}orb1 cards1.
by rewrite sub1set orbit_refl.
Qed.
Lemma orbit_partition G S :
[acts G, on S | to] -> partition (orbit to G @: S) S.
Proof.
move=> actsGS; have sGD := acts_dom actsGS.
have eqiG: {in S & &, equivalence_rel [rel x y | y \in orbit to G x]}.
by move=> x y z * /=; rewrite orbit_refl; split=> // /orbit_in_eqP->.
congr (partition _ _): (equivalence_partitionP eqiG).
apply: eq_in_imset => x Sx; apply/setP=> y.
by rewrite inE /= andb_idl // => /acts_in_orbit->.
Qed.
Definition orbit_transversal A S := transversal (orbit to A @: S) S.
Lemma orbit_transversalP G S (P := orbit to G @: S)
(X := orbit_transversal G S) :
[acts G, on S | to] ->
[/\ is_transversal X P S, X \subset S,
{in X &, forall x y, (y \in orbit to G x) = (x == y)}
& forall x, x \in S -> exists2 a, a \in G & to x a \in X].
Proof.
move/orbit_partition; rewrite -/P => partP.
have [/eqP defS tiP _] := and3P partP.
have trXP: is_transversal X P S := transversalP partP.
have sXS: X \subset S := transversal_sub trXP.
split=> // [x y Xx Xy /= | x Sx].
have Sx := subsetP sXS x Xx.
rewrite -(inj_in_eq (pblock_inj trXP)) // eq_pblock ?defS //.
by rewrite (def_pblock tiP (mem_imset _ Sx)) ?orbit_refl.
have /imsetP[y Xy defxG]: orbit to G x \in pblock P @: X.
by rewrite (pblock_transversal trXP) ?mem_imset.
suffices /orbitP[a Ga def_y]: y \in orbit to G x by exists a; rewrite ?def_y.
by rewrite defxG mem_pblock defS (subsetP sXS).
Qed.
Lemma group_set_astab S : group_set 'C(S | to).
Proof.
apply/group_setP; split=> [|a b cSa cSb].
by rewrite !inE group1; apply/subsetP=> x _; rewrite inE act1.
rewrite !inE groupM ?(@astab_dom _ _ _ to S) //; apply/subsetP=> x Sx.
by rewrite inE actMin ?(@astab_dom _ _ _ to S) ?(astab_act _ Sx).
Qed.
Canonical astab_group S := group (group_set_astab S).
Lemma afix_gen_in A : A \subset D -> 'Fix_to(<<A>>) = 'Fix_to(A).
Proof.
move=> sAD; apply/eqP; rewrite eqEsubset afixS ?sub_gen //=.
by rewrite -astabCin gen_subG ?astabCin.
Qed.
Lemma afix_cycle_in a : a \in D -> 'Fix_to(<[a]>) = 'Fix_to[a].
Proof. by move=> Da; rewrite afix_gen_in ?sub1set. Qed.
Lemma afixYin A B :
A \subset D -> B \subset D -> 'Fix_to(A <*> B) = 'Fix_to(A) :&: 'Fix_to(B).
Proof. by move=> sAD sBD; rewrite afix_gen_in ?afixU // subUset sAD. Qed.
Lemma afixMin G H :
G \subset D -> H \subset D -> 'Fix_to(G * H) = 'Fix_to(G) :&: 'Fix_to(H).
Proof.
by move=> sGD sHD; rewrite -afix_gen_in ?mul_subG // genM_join afixYin.
Qed.
Lemma sub_astab1_in A x :
A \subset D -> (A \subset 'C[x | to]) = (x \in 'Fix_to(A)).
Proof. by move=> sAD; rewrite astabCin ?sub1set. Qed.
Lemma group_set_astabs S : group_set 'N(S | to).
Proof.
apply/group_setP; split=> [|a b cSa cSb].
by rewrite !inE group1; apply/subsetP=> x Sx; rewrite inE act1.
rewrite !inE groupM ?(@astabs_dom _ _ _ to S) //; apply/subsetP=> x Sx.
by rewrite inE actMin ?(@astabs_dom _ _ _ to S) ?astabs_act.
Qed.
Canonical astabs_group S := group (group_set_astabs S).
Lemma astab_norm S : 'N(S | to) \subset 'N('C(S | to)).
Proof.
apply/subsetP=> a nSa; rewrite inE sub_conjg; apply/subsetP=> b cSb.
have [Da Db] := (astabs_dom nSa, astab_dom cSb).
rewrite mem_conjgV !inE groupJ //; apply/subsetP=> x Sx.
rewrite inE !actMin ?groupM ?groupV //.
by rewrite (astab_act cSb) ?actKVin ?astabs_act ?groupV.
Qed.
Lemma astab_normal S : 'C(S | to) <| 'N(S | to).
Proof. by rewrite /normal astab_sub astab_norm. Qed.
Lemma acts_sub_orbit G S x :
[acts G, on S | to] -> (orbit to G x \subset S) = (x \in S).
Proof.
move/acts_act=> GactS.
apply/subsetP/idP=> [| Sx y]; first by apply; apply: orbit_refl.
by case/orbitP=> a Ga <-{y}; rewrite GactS.
Qed.
Lemma acts_orbit G x : G \subset D -> [acts G, on orbit to G x | to].
Proof.
move/subsetP=> sGD; apply/subsetP=> a Ga; rewrite !inE sGD //.
apply/subsetP=> _ /imsetP[b Gb ->].
by rewrite inE -actMin ?sGD // mem_imset ?groupM.
Qed.
Lemma acts_subnorm_fix A : [acts 'N_D(A), on 'Fix_to(D :&: A) | to].
Proof.
apply/subsetP=> a nAa; have [Da _] := setIP nAa; rewrite !inE Da.
apply/subsetP=> x Cx; rewrite inE; apply/afixP=> b DAb.
have [Db _]:= setIP DAb; rewrite -actMin // conjgCV actMin ?groupJ ?groupV //.
by rewrite /= (afixP Cx) // memJ_norm // groupV (subsetP (normsGI _ _) _ nAa).
Qed.
Lemma atrans_orbit G x : [transitive G, on orbit to G x | to].
Proof. by apply: mem_imset; apply: orbit_refl. Qed.
Section OrbitStabilizer.
Variables (G : {group aT}) (x : rT).
Hypothesis sGD : G \subset D.
Let ssGD := subsetP sGD.
Lemma amove_act a : a \in G -> amove to G x (to x a) = 'C_G[x | to] :* a.
Proof.
move=> Ga; apply/setP=> b; have Da := ssGD Ga.
rewrite mem_rcoset !(inE, sub1set) !groupMr ?groupV //.
by case Gb: (b \in G); rewrite //= actMin ?groupV ?ssGD ?(canF_eq (actKVin Da)).
Qed.
Lemma amove_orbit : amove to G x @: orbit to G x = rcosets 'C_G[x | to] G.
Proof.
apply/setP => Ha; apply/imsetP/rcosetsP=> [[y] | [a Ga ->]].
by case/imsetP=> b Gb -> ->{Ha y}; exists b => //; rewrite amove_act.
by rewrite -amove_act //; exists (to x a); first apply: mem_orbit.
Qed.
Lemma amoveK :
{in orbit to G x, cancel (amove to G x) (fun Ca => to x (repr Ca))}.
Proof.
move=> _ /orbitP[a Ga <-]; rewrite amove_act //= -[G :&: _]/(gval _).
case: repr_rcosetP => b; rewrite !(inE, sub1set)=> /and3P[Gb _ xbx].
by rewrite actMin ?ssGD ?(eqP xbx).
Qed.
Lemma orbit_stabilizer :
orbit to G x = [set to x (repr Ca) | Ca in rcosets 'C_G[x | to] G].
Proof.
rewrite -amove_orbit -imset_comp /=; apply/setP=> z.
by apply/idP/imsetP=> [xGz | [y xGy ->]]; first exists z; rewrite /= ?amoveK.
Qed.
Lemma act_reprK :
{in rcosets 'C_G[x | to] G, cancel (to x \o repr) (amove to G x)}.
Proof.
move=> _ /rcosetsP[a Ga ->] /=; rewrite amove_act ?rcoset_repr //.
rewrite -[G :&: _]/(gval _); case: repr_rcosetP => b /setIP[Gb _].
exact: groupM.
Qed.
End OrbitStabilizer.
Lemma card_orbit_in G x : G \subset D -> #|orbit to G x| = #|G : 'C_G[x | to]|.
Proof.
move=> sGD; rewrite orbit_stabilizer 1?card_in_imset //.
exact: can_in_inj (act_reprK _).
Qed.
Lemma card_orbit_in_stab G x :
G \subset D -> (#|orbit to G x| * #|'C_G[x | to]|)%N = #|G|.
Proof. by move=> sGD; rewrite mulnC card_orbit_in ?Lagrange ?subsetIl. Qed.
Lemma acts_sum_card_orbit G S :
[acts G, on S | to] -> \sum_(T in orbit to G @: S) #|T| = #|S|.
Proof. by move/orbit_partition/card_partition. Qed.
Lemma astab_setact_in S a : a \in D -> 'C(to^* S a | to) = 'C(S | to) :^ a.
Proof.
move=> Da; apply/setP=> b; rewrite mem_conjg !inE -mem_conjg conjGid //.
apply: andb_id2l => Db; rewrite sub_imset_pre; apply: eq_subset_r => x.
by rewrite !inE !actMin ?groupM ?groupV // invgK (canF_eq (actKVin Da)).
Qed.
Lemma astab1_act_in x a : a \in D -> 'C[to x a | to] = 'C[x | to] :^ a.
Proof. by move=> Da; rewrite -astab_setact_in // /setact imset_set1. Qed.
Theorem Frobenius_Cauchy G S : [acts G, on S | to] ->
\sum_(a in G) #|'Fix_(S | to)[a]| = (#|orbit to G @: S| * #|G|)%N.
Proof.
move=> GactS; have sGD := acts_dom GactS.
transitivity (\sum_(a in G) \sum_(x in 'Fix_(S | to)[a]) 1%N).
by apply: eq_bigr => a _; rewrite -sum1_card.
rewrite (exchange_big_dep (mem S)) /= => [|a x _]; last by case/setIP.
rewrite (set_partition_big _ (orbit_partition GactS)) -sum_nat_const /=.
apply: eq_bigr => _ /imsetP[x Sx ->].
rewrite -(card_orbit_in_stab x sGD) -sum_nat_const.
apply: eq_bigr => y; rewrite orbit_in_sym // => /imsetP[a Ga defx].
rewrite defx astab1_act_in ?(subsetP sGD) //.
rewrite -{2}(conjGid Ga) -conjIg cardJg -sum1_card setIA (setIidPl sGD).
by apply: eq_bigl => b; rewrite !(sub1set, inE) -(acts_act GactS Ga) -defx Sx.
Qed.
Lemma atrans_dvd_index_in G S :
G \subset D -> [transitive G, on S | to] -> #|S| %| #|G : 'C_G(S | to)|.
Proof.
move=> sGD /imsetP[x Sx {1}->]; rewrite card_orbit_in //.
by rewrite indexgS // setIS // astabS // sub1set.
Qed.
Lemma atrans_dvd_in G S :
G \subset D -> [transitive G, on S | to] -> #|S| %| #|G|.
Proof.
move=> sGD transG; apply: dvdn_trans (atrans_dvd_index_in sGD transG) _.
exact: dvdn_indexg.
Qed.
Lemma atransPin G S :
G \subset D -> [transitive G, on S | to] ->
forall x, x \in S -> orbit to G x = S.
Proof. by move=> sGD /imsetP[y _ ->] x; apply/orbit_in_eqP. Qed.
Lemma atransP2in G S :
G \subset D -> [transitive G, on S | to] ->
{in S &, forall x y, exists2 a, a \in G & y = to x a}.
Proof. by move=> sGD transG x y /(atransPin sGD transG) <- /imsetP. Qed.
Lemma atrans_acts_in G S :
G \subset D -> [transitive G, on S | to] -> [acts G, on S | to].
Proof.
move=> sGD transG; apply/subsetP=> a Ga; rewrite !inE (subsetP sGD) //.
by apply/subsetP=> x /(atransPin sGD transG) <-; rewrite inE mem_imset.
Qed.
Lemma subgroup_transitivePin G H S x :
x \in S -> H \subset G -> G \subset D -> [transitive G, on S | to] ->
reflect ('C_G[x | to] * H = G) [transitive H, on S | to].
Proof.
move=> Sx sHG sGD trG; have sHD := subset_trans sHG sGD.
apply: (iffP idP) => [trH | defG].
rewrite group_modr //; apply/setIidPl/subsetP=> a Ga.
have Sxa: to x a \in S by rewrite (acts_act (atrans_acts_in sGD trG)).
have [b Hb xab]:= atransP2in sHD trH Sxa Sx.
have Da := subsetP sGD a Ga; have Db := subsetP sHD b Hb.
rewrite -(mulgK b a) mem_mulg ?groupV // !inE groupM //= sub1set inE.
by rewrite actMin -?xab.
apply/imsetP; exists x => //; apply/setP=> y; rewrite -(atransPin sGD trG Sx).
apply/imsetP/imsetP=> [] [a]; last by exists a; first apply: (subsetP sHG).
rewrite -defG => /imset2P[c b /setIP[_ cxc] Hb ->] ->.
exists b; rewrite ?actMin ?(astab_dom cxc) ?(subsetP sHD) //.
by rewrite (astab_act cxc) ?inE.
Qed.
End PartialAction.
Arguments orbit_transversal {aT D%g rT} to%act A%g S%g.
Arguments orbit_in_eqP {aT D rT to G x y}.
Arguments orbit1P {aT D rT to G x}.
Arguments contra_orbit [aT D rT] to G [x y].
Notation "''C' ( S | to )" := (astab_group to S) : Group_scope.
Notation "''C_' A ( S | to )" := (setI_group A 'C(S | to)) : Group_scope.
Notation "''C_' ( A ) ( S | to )" := (setI_group A 'C(S | to))
(only parsing) : Group_scope.
Notation "''C' [ x | to ]" := (astab_group to [set x%g]) : Group_scope.
Notation "''C_' A [ x | to ]" := (setI_group A 'C[x | to]) : Group_scope.
Notation "''C_' ( A ) [ x | to ]" := (setI_group A 'C[x | to])
(only parsing) : Group_scope.
Notation "''N' ( S | to )" := (astabs_group to S) : Group_scope.
Notation "''N_' A ( S | to )" := (setI_group A 'N(S | to)) : Group_scope.
Section TotalActions.
(* These lemmas are only established for total actions (domain = [set: rT]) *)
Variable (aT : finGroupType) (rT : finType).
Variable to : {action aT &-> rT}.
Implicit Types (a b : aT) (x y z : rT) (A B : {set aT}) (G H : {group aT}).
Implicit Type S : {set rT}.
Lemma actM x a b : to x (a * b) = to (to x a) b.
Proof. by rewrite actMin ?inE. Qed.
Lemma actK : right_loop invg to.
Proof. by move=> a; apply: actKin; rewrite inE. Qed.
Lemma actKV : rev_right_loop invg to.
Proof. by move=> a; apply: actKVin; rewrite inE. Qed.
Lemma actX x a n : to x (a ^+ n) = iter n (to^~ a) x.
Proof. by elim: n => [|n /= <-]; rewrite ?act1 // -actM expgSr. Qed.
Lemma actCJ a b x : to (to x a) b = to (to x b) (a ^ b).
Proof. by rewrite !actM actK. Qed.
Lemma actCJV a b x : to (to x a) b = to (to x (b ^ a^-1)) a.
Proof. by rewrite (actCJ _ a) conjgKV. Qed.
Lemma orbit_sym G x y : (x \in orbit to G y) = (y \in orbit to G x).
Proof. exact/orbit_in_sym/subsetT. Qed.
Lemma orbit_trans G x y z :
x \in orbit to G y -> y \in orbit to G z -> x \in orbit to G z.
Proof. exact/orbit_in_trans/subsetT. Qed.
Lemma orbit_eqP G x y :
reflect (orbit to G x = orbit to G y) (x \in orbit to G y).
Proof. exact/orbit_in_eqP/subsetT. Qed.
Lemma orbit_transl G x y z :
y \in orbit to G x -> (y \in orbit to G z) = (x \in orbit to G z).
Proof. exact/orbit_in_transl/subsetT. Qed.
Lemma orbit_act G a x: a \in G -> orbit to G (to x a) = orbit to G x.
Proof. exact/orbit_act_in/subsetT. Qed.
Lemma orbit_actr G a x y :
a \in G -> (to y a \in orbit to G x) = (y \in orbit to G x).
Proof. by move/mem_orbit/orbit_transl; apply. Qed.
Lemma orbit_eq_mem G x y :
(orbit to G x == orbit to G y) = (x \in orbit to G y).
Proof. exact: sameP eqP (orbit_eqP G x y). Qed.
Lemma orbit_inv A x y : (y \in orbit to A^-1 x) = (x \in orbit to A y).
Proof. by rewrite orbit_inv_in ?subsetT. Qed.
Lemma orbit_lcoset A a x : orbit to (a *: A) x = orbit to A (to x a).
Proof. by rewrite orbit_lcoset_in ?subsetT ?inE. Qed.
Lemma orbit_rcoset A a x y :
(to y a \in orbit to (A :* a) x) = (y \in orbit to A x).
Proof. by rewrite orbit_rcoset_in ?subsetT ?inE. Qed.
Lemma orbit_conjsg A a x y :
(to y a \in orbit to (A :^ a) (to x a)) = (y \in orbit to A x).
Proof. by rewrite orbit_conjsg_in ?subsetT ?inE. Qed.
Lemma astabP S a : reflect (forall x, x \in S -> to x a = x) (a \in 'C(S | to)).
Proof.
apply: (iffP idP) => [cSa x|cSa]; first exact: astab_act.
by rewrite !inE; apply/subsetP=> x Sx; rewrite inE cSa.
Qed.
Lemma astab1P x a : reflect (to x a = x) (a \in 'C[x | to]).
Proof. by rewrite !inE sub1set inE; apply: eqP. Qed.
Lemma sub_astab1 A x : (A \subset 'C[x | to]) = (x \in 'Fix_to(A)).
Proof. by rewrite sub_astab1_in ?subsetT. Qed.
Lemma astabC A S : (A \subset 'C(S | to)) = (S \subset 'Fix_to(A)).
Proof. by rewrite astabCin ?subsetT. Qed.
Lemma afix_cycle a : 'Fix_to(<[a]>) = 'Fix_to[a].
Proof. by rewrite afix_cycle_in ?inE. Qed.
Lemma afix_gen A : 'Fix_to(<<A>>) = 'Fix_to(A).
Proof. by rewrite afix_gen_in ?subsetT. Qed.
Lemma afixM G H : 'Fix_to(G * H) = 'Fix_to(G) :&: 'Fix_to(H).
Proof. by rewrite afixMin ?subsetT. Qed.
Lemma astabsP S a :
reflect (forall x, (to x a \in S) = (x \in S)) (a \in 'N(S | to)).
Proof.
apply: (iffP idP) => [nSa x|nSa]; first exact: astabs_act.
by rewrite !inE; apply/subsetP=> x; rewrite inE nSa.
Qed.
Lemma card_orbit G x : #|orbit to G x| = #|G : 'C_G[x | to]|.
Proof. by rewrite card_orbit_in ?subsetT. Qed.
Lemma dvdn_orbit G x : #|orbit to G x| %| #|G|.
Proof. by rewrite card_orbit dvdn_indexg. Qed.
Lemma card_orbit_stab G x : (#|orbit to G x| * #|'C_G[x | to]|)%N = #|G|.
Proof. by rewrite mulnC card_orbit Lagrange ?subsetIl. Qed.
Lemma actsP A S : reflect {acts A, on S | to} [acts A, on S | to].
Proof.
apply: (iffP idP) => [nSA x|nSA]; first exact: acts_act.
by apply/subsetP=> a Aa; rewrite !inE; apply/subsetP=> x; rewrite inE nSA.