### The Orbit/Stabiliser Theorem

The Orbit/Stabiliser Theorem is a simple theorem in group theory. Thanks to Tim Gowers for the proof I outline here - I find it much more intuitive than the proof that was presented in lectures, and it involves equivalence relations (which I think are wonderful things).

Theorem: \(\vert {g(x), g \in G} \vert \times \vert {g \in G: g(x) = x} \vert = \vert G \vert\).

Proof: We fix an element \(x \in G\), and define two equivalence relations: \(g \sim h\) iff \(g(x) = h(x)\), and \(g \cdot h\) if \(h^{-1} g \in \text{Stab}_G(x)\), where \(\text{Stab}_G(k) = {g \in G: g(k) = k}\).

Now, these are the same relation (we will check that they are indeed equivalence relations - don’t worry!). This is because \(g \sim h \iff g(x) = h(x) \iff h^{-1}g(x) = x \iff h^{-1}g \in \text{Stab}_G(x) \iff g \cdot h\).

And \(\sim\) is an equivalence relation, almost trivially: it is reflexive since \(g \sim g \iff g(x) = g(x)\) is obviously true; it is symmetric, since \(g \sim h \iff g(x) = h(x) \iff h(x) = g(x) \iff h \sim g\); it is transitive similarly.

Now, it is clear that the number of equivalence classes of \(\sim\) is just the size of the orbit \({g(x), g \in G }\), because for each equivalence class there is one member of the orbit (with \([g]\) representing \(g(x)\)), and for each member of the orbit there is one equivalence class (with \(g(x)\) being represented solely by \([g]\)).

It is also clear that the size of the stabiliser \(\text{Stab}_G(x)\) is just the size of an equivalence class \([g]\) of \(\cdot\), since for each member \(s\) of the stabiliser, we have that \(g \cdot (g s)\) so \(\vert [g] \vert \geq \vert \text{Stab}_G(x) \vert"\), while for each for each member \(h\) of \([g]\) we have that \(h^{-1}g \in \text{Stab}_G(x)\) by definition of \(\cdot\) - but all these \(h^{-1}g\) are different (because otherwise we could cancel a \(g\)) so \(\vert [g] \vert \leq \vert \text{Stab}_G(x) \vert\).

And the equivalence classes of \(\sim \ = \cdot\) partition the set \(G\), so (size of equivalence class) times (number of equivalence classes) is just \( \vert G \vert\) - but this is exactly what we required.