Difference between revisions of "Orbit-stabilizer theorem"
(short page) |
Hashtagmath (talk | contribs) (→See also) |
||
| (3 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
The '''orbit-stabilizer theorem''' is a [[combinatorics |combinatorial]] result in [[group theory]]. | The '''orbit-stabilizer theorem''' is a [[combinatorics |combinatorial]] result in [[group theory]]. | ||
| − | Let <math>G</math> be a [[group]] acting on a [[set]] <math>S</math>. For any <math>i \in S</math>, let <math>\text{stab}(i)</math> denote the [[stabilizer]] of <math>i</math>, and let <math>\text{orb}(i)</math> denote the [[orbit]] of <math>i</math>. The orbit-stabilizer theorem states that | + | Let <math>G</math> be a [[group]] [[group action|acting]] on a [[set]] <math>S</math>. For any <math>i \in S</math>, let <math>\text{stab}(i)</math> denote the [[stabilizer]] of <math>i</math>, and let <math>\text{orb}(i)</math> denote the [[orbit]] of <math>i</math>. The orbit-stabilizer theorem states that |
<cmath> \lvert G \rvert = \lvert \text{orb}(i) \rvert \cdot \lvert \text{stab}(i) \rvert . </cmath> | <cmath> \lvert G \rvert = \lvert \text{orb}(i) \rvert \cdot \lvert \text{stab}(i) \rvert . </cmath> | ||
| − | ''Proof.'' Without loss of generality, let <math>G</math> operate on <math>S</math> from the | + | ''Proof.'' Without loss of generality, let <math>G</math> operate on <math>S</math> from the left. We note that if <math>\alpha, \beta</math> are elements of <math>G</math> such that <math>\alpha(i) = \beta(i)</math>, then <math>\alpha^{-1} \beta \in \text{stab}(i)</math>. Hence for any <math>x \in \text{orb}(i)</math>, the set of elements <math>\alpha</math> of <math>G</math> for which <math>\alpha(i)= x</math> constitute a unique [[coset |left coset]] modulo <math>\text{stab}(i)</math>. Thus |
<cmath> \lvert \text{orb}(i) \rvert = \lvert G/\text{stab}(i) \rvert. </cmath> | <cmath> \lvert \text{orb}(i) \rvert = \lvert G/\text{stab}(i) \rvert. </cmath> | ||
The result then follows from [[Lagrange's Theorem]]. <math>\blacksquare</math> | The result then follows from [[Lagrange's Theorem]]. <math>\blacksquare</math> | ||
| Line 15: | Line 15: | ||
[[Category:Group theory]] | [[Category:Group theory]] | ||
| + | [[Category: Theorems]] | ||
Latest revision as of 11:26, 9 April 2019
The orbit-stabilizer theorem is a combinatorial result in group theory.
Let 
be a group acting on a set 
. For any 
, let 
denote the stabilizer of 
, and let 
denote the orbit of . The orbit-stabilizer theorem states that
![\[\lvert G \rvert = \lvert \text{orb}(i) \rvert \cdot \lvert \text{stab}(i) \rvert .\]](http://latex.artofproblemsolving.com/4/f/d/4fd05faa02a0317f2d3ff70c1b49a4c2b97f22ff.png)
Proof. Without loss of generality, let operate on from the left. We note that if 
are elements of such that 
, then 
. Hence for any 
, the set of elements 
of for which 
constitute a unique left coset modulo . Thus
![\[\lvert \text{orb}(i) \rvert = \lvert G/\text{stab}(i) \rvert.\]](http://latex.artofproblemsolving.com/2/b/d/2bdf56fb75cf03827521db5982b2acb72f3f7fca.png)
The result then follows from Lagrange's Theorem. 
