Difference between revisions of "Orbit-stabilizer theorem"

(short page)
 
m (Link to group action article)
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>
  

Revision as of 18:48, 9 September 2008

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 \stab(i)$ (Error compiling LaTeX. Unknown error_msg). 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