Orbit-stabilizer theorem

Revision as of 12:41, 18 August 2016 by Devenware (talk | contribs)

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 left. 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