Let be a nonempty set and let . Let be the fixed set of . Let be the elements which are moved by some element of .
Define . Prove that is a normal subgroup of .
The identity permutation moves zero objects, and so . Now suppose . Now , and , so that is closed under identity, inversion, and multiplication, and hence is a subgroup.
Next we prove some lemmas.
Lemma 1: For all and , . Proof: Let . Then , hence . Thus , and so . Let . Then for some . So , hence , and thus .
Lemma 2: If is defined as above, then for all , . Proof: If , then for some . Thus . Now , so that . If , then . Thus , so that . Hence .
Lemma 3: If is defined as above, then for all , . Proof: We have .
Now to the main result.
Let and . Then by Lemma 3. Since is finite and is a bijection, is also finite. Hence . Thus is normal.