Difference between revisions of "Orbit-stabilizer theorem"

(short page)
 
(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 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 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 12:26, 9 April 2019

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