Difference between revisions of "Orbit-stabilizer theorem"

m (Link to group action article)
Line 4: Line 4:
 
<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 right.  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 \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
+
''Proof.''  Without loss of generality, let <math>G</math> operate on <math>S</math> from the right.  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>

Revision as of 16:53, 12 September 2015

The orbit-stabilizer theorem is a combinatorial result in group theory.

Let $G$ be a group acting on a set $S$. For any $i \in S$, let $\text{stab}(i)$ denote the stabilizer of $i$, and let $\text{orb}(i)$ denote the orbit of $i$. The orbit-stabilizer theorem states that \[\lvert G \rvert = \lvert \text{orb}(i) \rvert \cdot \lvert \text{stab}(i) \rvert .\]

Proof. Without loss of generality, let $G$ operate on $S$ from the right. We note that if $\alpha, \beta$ are elements of $G$ such that $\alpha(i) = \beta(i)$, then $\alpha^{-1} \beta \in \text{stab}(i)$. Hence for any $x \in \text{orb}(i)$, the set of elements $\alpha$ of $G$ for which $\alpha(i)= x$ constitute a unique left coset modulo $\text{stab}(i)$. Thus \[\lvert \text{orb}(i) \rvert = \lvert G/\text{stab}(i) \rvert.\] The result then follows from Lagrange's Theorem. $\blacksquare$

See also

Invalid username
Login to AoPS