Nah ini dia! Lemma Burnside alias Teorema Burnside alias Lemma Cauchy-Frobenius alias Teorema untuk Menghitung Orbit adalah teorema yang sangat-sangat berguna untuk menghitung orbit yang berhubungan dengan suatu grup aksi. Sebelum membahasa lemma ini, kita terlebih dahulu harus mengenal istilah Fixer.
Diketahui $X$ adalah himpunan objek yang berhingga.
Diketahui $G$ adalah himpunan aksi yang berhingga.
Diketahui $(G, \star)$ adalah grup aksi kiri terhadap himpunan objek $X$.
Untuk suatu aksi $g \in G$, fixer dari $g$, dinotasikan $F(g)$, adalah himpunan bagian dari himpunan $X$ yang didefinisikan sebagai berikut.
$F(g) = \{ x \in X ~:~ \phi(g, x) = x \}.$
Sebelum membaca tulisan ini, ada baiknya untuk membaca tulisan terkait grup aksi berikut.
$X$ adalah himpunan objek yang berhingga.
$G$ adalah himpunan aksi yang berhingga.
$(G, \star)$ adalah grup aksi kiri terhadap himpunan objek $X$.
Akan berlaku persamaan berikut.
$\displaystyle |X/G| = \frac{1}{|G|} \sum_{g \in G}{|F(g)|}$
Step 1
Oke! Kita jabarkan dulu persamaan di atas dengan syarat keanggotaan himpunan $F(g)$.
$\displaystyle |X/G| = \frac{1}{|G|} \sum_{g \in G}{|F(g)|} = \frac{1}{|G|} \sum_{g \in G}{| \{ x \in X ~:~ \phi(g, x) = x \} |}$
Step 2
Nah! Sekarang kita akan buat supaya persamaan di atas menjadi lebih mudah untuk dibayangkan. Ingat! Himpunan aksi $G$ adalah himpunan yang berhingga. Oleh sebab itu, kita asumsikan saja bahwa himpunan $G$ memuat sebanyak $m$ aksi, yaitu:
$G = \{ g_1, g_2, g_3, ..., g_m\}$.
Step 3
Berdasarkan hasil pada Step 2, maka persamaan pada Step 1 dapat kita jabarkan menjadi seperti ini ya.
$\displaystyle |X/G| = \frac{1}{|G|} \sum_{g \in G}{|F(g)|} = \frac{1}{|G|} \Bigg( \Big| \{ x \in X ~:~ \phi(g_1, x) = x \} \Big| + ... + \Big| \{ x \in X ~:~ \phi(g_m, x) = x \} \Big| \Bigg) $
Step 4
Naah! Supaya membayangkannya menjadi tambah lebih mudah lagi, sekarang kita akan mengamati bentuk $\Big| \{ x \in X ~:~ \phi(g_1, x) = x \} \Big| $. Perhatikan ya bahwa kita ini sedang mengamati kasus untuk aksi $g_1$.
Nah, ingat! Himpunan objek $X$ juga adalah himpunan yang berhingga. Oleh sebab itu, kita asumsikan saja bahwa himpunan $X$ memuat sebanyak $n$ objek, yaitu:
$X = \{ x_1, x_2, x_3, ..., x_n\}$.
Dengan demikian, kita bisa menjabarkan bentuk $\Big| \{ x \in X ~:~ \phi(g_1, x) = x \} \Big| $ menjadi seperti berikut.
$\displaystyle \Big| \{ x \in X ~:~ \phi(g_1, x) = x \} \Big| = \Big| \{ x_1 ~:~ \phi(g_1, x_1) = x_1 \} \Big| + \Big| \{ x_2 ~:~ \phi(g_1, x_2) = x_2 \} \Big| + ... + \Big| \{ x_n ~:~ \phi(g_1, x_n) = x_n \} \Big|$
Step 5
Naaah! Sekarang kita akan mengandaikan lagi nih!
Misalkan dari objek-objek $x_1$, $x_2$, $x_3$, hingga $x_n$ yang termuat di dalam himpunan $X$, hanya objek $x_2$ dan $x_4$ yang memenuhi persamaan $\phi(g_1, x_2) = x_2$ dan $\phi(g_1, x_4) = x_4$. Dengan kata lain, akan berlaku:
Akibatnya, untuk objek-objek $x_1$, $x_3$, $x_5$, $x_6$, hingga $x_n$ akan berlaku:
Akibatnya lagi, persamaan di bawah ini akan berlaku benar.
$\displaystyle \{ x_1 ~:~ \phi(g_1, x_1) = x_1 \} = \{ x_3 ~:~ \phi(g_1, x_3) = x_3 \} = \{ x_5 ~:~ \phi(g_1, x_5) = x_5 \} = \{ x_6 ~:~ \phi(g_1, x_6) = x_6 \} = ... = \{ x_n ~:~ \phi(g_1, x_n) = x_n \} = \{ \}$.
Akibatnya lagiii, persamaan di bawah ini akan berlaku benar.
$\displaystyle \Big| \{ x_1 ~:~ \phi(g_1, x_1) = x_1 \} \Big| = \Big|\{ x_3 ~:~ \phi(g_1, x_3) = x_3 \} \Big| = \Big|\{ x_5 ~:~ \phi(g_1, x_5) = x_5 \} \Big| = \Big|\{ x_6 ~:~ \phi(g_1, x_6) = x_6 \}\Big| = ... = \Big|\{ x_n ~:~ \phi(g_1, x_n) = x_n \}\Big| = \Big|\{ \}\Big| = 0$.
Dengan demikian, kita akan memperoleh hasil sebagai berikut.
$\begin{split} \Big| \{ x \in X ~:~ \phi(g_1, x) = x \} \Big| &= \Big| \{ x_1 ~:~ \phi(g_1, x_1) = x_1 \} \Big| + \Big| \{ x_2 ~:~ \phi(g_1, x_2) = x_2 \} \Big| + ... + \Big| \{ x_n ~:~ \phi(g_1, x_n) = x_n \} \Big| \\ &= \Big| \{\} \Big| + \Big| \{x_2\} \Big| + \Big| \{\} \Big| + \Big| \{x_4\} \Big| + \Big| \{\} \Big| + \Big| \{\} \Big| + ... + \Big| \{\} \Big| \\ &= 0 +1 + 0+1 +0+0+...+0 \\ &= 2\end{split}$
Step 6
Ingat lho ya! Penjabaran yang dilengkapi pengandaian pada Step 5 di atas itu hanya ilustrasi! Sekadar memberi gambaran saja.
Hal yang ingin ditekankan dari Step 5 di atas adalah cara perhitungan. Lebih tepatnya, apakah sesungguhnya yang dihitung.
Perhatikan! Awalnya kita menghitung $\displaystyle \sum_{g \in G}{\Big| \{ x \in X ~:~ \phi(g, x) = x \} \Big|}$. Akan tetapi, pada akhirnya kita melakukan perhitungan akan banyaknya $|\{ x_i \}|$.
Naaaah! Oleh sebab itu, kenapa simbol jumlahan $\displaystyle \sum_{g \in G}$ itu tidak kita ganti dengan simbol $\displaystyle \sum_{x \in X}$ saja? Karena ya itu. Ujung-ujungnya, kita melakukan perhitungan akan banyaknya $|\{ x_i \}|$ kan?
Step 7
Berdasarkan insight yang diperoleh dari Step 6, kita akan coba menjabarkan ulang bentuk $\displaystyle \sum_{g \in G}{|F(g)|}$.
$\begin{split} \displaystyle \sum_{g \in G}{|F(g)|} &= \Big| \{ x \in X ~:~ \phi(g_1, x) = x \} \Big| + ... + \Big| \{ x \in X ~:~ \phi(g_m, x) = x \} \Big| \\ &= \Big| \{ x_1 ~:~ \phi(g_1, x_1) = x_1 \} \Big| + ... + \Big| \{ x_n ~:~ \phi(g_1, x_n) = x_n \} \Big| + ... + \Big| \{ x_1 ~:~ \phi(g_m, x_1) = x_1 \} \Big| + ... + \Big| \{ x_n ~:~ \phi(g_m, x_n) = x_n \} \Big| \\ &= \Big| \{ x_1 ~:~ \phi(g_1, x_1) = x_1 \} \Big| + ... + \Big| \{ x_1 ~:~ \phi(g_m, x_1) = x_1 \} \Big| + ... + \Big| \{ x_n ~:~ \phi(g_1, x_n) = x_n \} \Big| + ... + \Big| \{ x_n ~:~ \phi(g_m, x_n) = x_n \} \Big| \\ &= \Big| \{ g \in G ~:~ \phi(g, x_1) = x_1 \} \Big| + ... + \Big| \{ g \in G ~:~ \phi(g, x_n) = x_n \} \Big| \\ &= \displaystyle \sum_{x \in X}{ | S(x) | } \end{split}$
dengan $S(x) = \{ g \in G ~:~ \phi(g, x) = x \}$ adalah stabilizer suatu objek $x$ terhadap grup aksi kiri $(G, \star)$. Stabilizer ini sudah pernah dibahas pada Pengantar Grup Aksi, Orbit, dan Stabilizer.
Step 8
Berdasarkan Teorema Orbit-Stabilizer pada Grup Aksi yang Berhingga, kita akan memiliki persamaan sebagai berikut.
$\displaystyle |S(x)| = \frac{|G|}{|O(x)|}$
Step 9
Berdasarkan persamaan di Step 8, maka hasil persamaan pada Step 7 akan menjadi sebagai berikut.
$\displaystyle \sum_{g \in G}{|F(g)|} ~=~ \sum_{x \in X}{ | S(x) | } ~=~ \sum_{x \in X}{ \frac{|G|}{|O(x)|} }$
Supaya tidak terlalu membingungkan, karena pada Step 2 kita mengasumsikan bahwa $G = \{ g_1, g_2, g_3, ..., g_m\}$, maka jelas bahwa $|G| = m$ untuk suatu bilangan asli $m$. Dengan demikian, kita akan punya persamaan berikut.
$\displaystyle \sum_{x \in X}{ \frac{|G|}{|O(x)|} } ~=~ \sum_{x \in X}{ \frac{m}{|O(x)|} }$
Nah, karena bilangan asli $m$ tidak "terikat" dengan iterator $x \in X$, maka sesuai sifat jumlahan $\sum$, akan diperoleh persamaan sebagai berikut.
$\displaystyle \sum_{x \in X}{ \frac{m}{|O(x)|} } ~=~ m \cdot \sum_{x \in X}{ \frac{1}{|O(x)|} } ~=~ |G| \cdot \sum_{x \in X}{ \frac{1}{|O(x)|} }$
pada persamaan di atas, kita ganti lagi notasi $m$ dengan $|G|$ karena nanti kita akan berkutat dengan notasi $|G|$.
Oke! Jadi, pada akhir Step 9 ini, kita punya persamaan berikut.
$\displaystyle \sum_{g \in G}{|F(g)|} = |G| \cdot \sum_{x \in X}{ \frac{1}{|O(x)|} }$
Step 10
Karena kita ingin membuktikan kebenaran persamaan:
$\displaystyle |X/G| = \frac{1}{|G|} \sum_{g \in G}{|F(g)|}$
maka persamaan $\displaystyle \sum_{g \in G}{|F(g)|} = |G| \cdot \sum_{x \in X}{ \frac{1}{|O(x)|} }$ yang kita peroleh dari Step 9 akan kita kalikan dengan $\displaystyle \frac{1}{|G|}$. Apakah hasilnya akan sama dengan $|X/G|$? Let's find out!
$\displaystyle \frac{1}{|G|} \cdot \sum_{g \in G}{|F(g)|} ~=~ \frac{1}{|G|} \cdot |G| \cdot \sum_{x \in X}{ \frac{1}{|O(x)|} } = \sum_{x \in X}{ \frac{1}{|O(x)|} }$
Berdasarkan Pengantar Grup Aksi, Orbit, dan Stabilizer, definisi dari $|O(x)|$ adalah sebagai berikut.
$X/G = \{ O(x_1),~ O(x_2),~ O(x_3),~ ...,~ O(x_n)\} = \{ O(x) ~|~ x \in X \}$
Dengan demikian, jika $\displaystyle \sum_{x \in X}{ \frac{1}{|O(x)|} }$ dijabarkan, akan diperoleh hasil sebagai berikut.
$\displaystyle \sum_{x \in X}{ \frac{1}{|O(x)|} } = \frac{1}{|O(x_1)|} + \frac{1}{|O(x_2)|} + \frac{1}{|O(x_3)|} + ... + \frac{1}{|O(x_n)|}$
Step 11
Ingat! Orbit $O(x)$ adalah kelas ekuivalensi pada himpunan objek $X$! Dengan kata lain, orbit akan mempartisi himpunan objek $X$.
Supaya tidak bingung, kita buat ilustrasi sedikit. Misalkan $X = \{ x_1, x_2, ..., x_{8} \}$ dengan $O(x_1) = \{ x_1, x_3, x_4, x_8 \}$, $O(x_2) = \{ x_2, x_6 \}$, $O(x_5) = \{ x_5\}$, dan $O(x_7) = \{ x_7 \}$. Berdasarkan ilustrasi ini, akan berlaku persamaan $O(x_1) = O(x_3) = O(x_4) = O(x_8)$ dan dengan demikian akan berlaku persamaan berikut.
$\displaystyle \frac{1}{|O(x_1)|} + \frac{1}{|O(x_3)|} + \frac{1}{|O(x_4)|} + \frac{1}{|O(x_8)|} = \frac{1}{|O(x_1)|} + \frac{1}{|O(x_1)|} + \frac{1}{|O(x_1)|} + \frac{1}{|O(x_1)|} = 4 \cdot \frac{1}{|O(x_1)|} = 4 \cdot \frac{1}{4} = 1.$
Masih dengan ilustrasi yang sama, karena berlaku persamaan $O(x_2) = O(x_6)$ dan dengan demikian akan berlaku persamaan berikut.
$\displaystyle \frac{1}{|O(x_2)|} + \frac{1}{|O(x_6)|} = \frac{1}{|O(x_2)|} + \frac{1}{|O(x_2)|} = 2 \cdot \frac{1}{|O(x_2)|} = 2 \cdot \frac{1}{2} = 1.$
Masih dengan ilustrasi yang sama, untuk orbit yang hanya memuat satu objek, hasilnya juga serupa.
$\displaystyle \frac{1}{|O(x_5)|} = 1 \cdot \frac{1}{|O(x_5)|} = 1 \cdot \frac{1}{1} = 1.$
Berdasarkan ilustrasi ini, ayo kita elaborasi dengan penjabaran yang kita dapatkan di akhir Step 10!
Step 12
Ayo kita kelompokkan suku-suku pada jumlahan:
$\displaystyle \frac{1}{|O(x_1)|} + \frac{1}{|O(x_2)|} + \frac{1}{|O(x_3)|} + ... + \frac{1}{|O(x_n)|}$
sesuai dengan orbit-orbitnya. Misalkan, hasilnya akan menjadi seperti ini.
$\displaystyle \Bigg\{ \frac{1}{|O(x_1)|} + \frac{1}{|O(x_3)|} + ... + \frac{1}{|O(x_{i_1})|} \Bigg\} + ... + \Bigg\{ \frac{1}{|O(x_2)|} + \frac{1}{|O(x_6)|} \Bigg\} + ... + \Bigg\{ \frac{1}{|O(x_n)|} \Bigg\}$
Pada jumlahan di atas, objek-objek $x_1$, $x_3$, hingga $x_{i_1}$ itu berada dalam satu orbit yang sama. Objek $x_2$ dan $x_6$ termuat di dalam orbit yang sama. Objek $x_n$ termuat di dalam orbit yang hanya memuat satu objek.
Nah, perhatikan! Apapun wujud eksak dari himpunan objek $X$, grup aksi (kiri) $(G, \star)$, dan juga orbit-orbitnya, kita akan selalu mendapatkan jumlahan dalam bentuk seperti ini, sesuai dengan orbit-orbitnya.
$\displaystyle \Bigg\{ ... \Bigg\} + ... + \Bigg\{ ... \Bigg\} + ... + \Bigg\{ ... \Bigg\}$
Nah! Berdasarkan ilustrasi pada Step 11, akan berlaku persamaan:
$\displaystyle \Bigg\{ ... \Bigg\} = 1$
dan dengan demikian, akan menghasilkan persamaan berikut.
$\displaystyle \Bigg\{ ... \Bigg\} + ... + \Bigg\{ ... \Bigg\} + ... + \Bigg\{ ... \Bigg\} = 1 + 1 + ... + 1$
Nah ini! Perhatikan baik-baik! Jumlah suku $1$ yang terlibat dalam jumlahan di atas adalah sama dengan jumlah semua orbit. Dengan kata lain, akan berlaku persamaan berikut.
$\displaystyle \Bigg\{ ... \Bigg\} + ... + \Bigg\{ ... \Bigg\} + ... + \Bigg\{ ... \Bigg\} = 1 + 1 + ... + 1 = \sum_{i = 1}^{|X/G|}{ 1 } = |X/G|$
Final Step
Oke! Kita akan rangkai semua yang sudah kita ketahui. Khususnya, pada Step 10 hingga Step 12.
$\displaystyle \frac{1}{|G|} \cdot \sum_{g \in G}{|F(g)|} ~=~ \sum_{x \in X}{ \frac{1}{|O(x)|} } = \Bigg\{ ... \Bigg\} + ... + \Bigg\{ ... \Bigg\} = 1 + 1 + ... + 1 = \sum_{i = 1}^{|X/G|}{ 1 } = |X/G|$
Jadi, terbukti bahwa persamaan $\displaystyle |X/G| = \frac{1}{|G|} \sum_{g \in G}{|F(g)|}$ berlaku benar.
$\blacksquare$