Cayley's theorem
ProvedFamousTheorems.cayleyCayley's theorem.
If a group acts faithfully on a set , then is isomorphic to its image in the symmetric group of :
Taking with the left regular action — which is always faithful — gives the familiar form: every group embeds in the symmetric group on its own underlying set, so every finite group of order is a subgroup of . Abstract groups are therefore no more general than permutation groups, which is what made the abstract definition acceptable in the 19th century when groups were understood concretely as permutations.
The faithfulness hypothesis is exactly what makes the map injective: the kernel of is the set of elements acting trivially, so it is trivial precisely when the action is faithful.
Cayley stated it in 1854, though the proof there is incomplete; Jordan gave a full treatment. The embedding is rarely efficient — is vastly larger than a group of order — and finding minimal faithful permutation representations is a separate and hard problem.
Formalization note. MulAction.toPermHom G H : G →* Equiv.Perm H is the action homomorphism and
FaithfulSMul is faithfulness. The isomorphism is data, so it is wrapped in Nonempty. The result
is Mathlib's Equiv.Perm.subgroupOfMulAction.
import Mathlib
namespace FamousTheorems
open MeasureTheory ProbabilityTheory Filter Set
open scoped Topology ENNReal NNReal
theorem cayley (G H : Type*) [Group G] [MulAction G H] [FaithfulSMul G H] :
Nonempty (G ≃* (MulAction.toPermHom G H).range) := by sorry
end FamousTheorems