Editing Cayley's theorem (section)

{{short description|Representation of groups by permutations}}
{{For|the number of labeled trees in graph theory|Cayley's formula}}

In the mathematical discipline of [[group theory]], '''Cayley's theorem''', named in honour of [[Arthur Cayley]], states that every [[group (mathematics)|group]] {{mvar|G}} is [[group isomorphism|isomorphic]] to a [[subgroup]] of a [[symmetric group]].<ref>{{harvtxt|Jacobson|2009|p=38}}</ref> 
More specifically, {{mvar|G}} is isomorphic to a subgroup of the symmetric group <math>\operatorname{Sym}(G)</math> whose elements are the [[permutation]]s of the underlying set of {{mvar|G}}.
Explicitly,
* for each <math>g \in G</math>, the left-multiplication-by-{{mvar|g}} map <math>\ell_g \colon G \to G</math> sending each element {{mvar|x}} to {{math|''gx''}} is a [[permutation]] of {{mvar|G}}, and
* the map <math>G \to \operatorname{Sym}(G)</math> sending each element {{mvar|g}} to <math>\ell_g</math> is an [[injective]] [[homomorphism]], so it defines an isomorphism from {{mvar|G}} onto a subgroup of <math>\operatorname{Sym}(G)</math>.
The homomorphism <math>G \to \operatorname{Sym}(G)</math> can also be understood as arising from the left translation [[Group action (mathematics)|action]] of {{mvar|G}} on the underlying set {{mvar|G}}.<ref>{{harvtxt|Jacobson|2009|p=72, ex. 1}}</ref>

When {{mvar|G}} is finite, <math>\operatorname{Sym}(G)</math> is finite too.  The proof of Cayley's theorem in this case shows that if {{mvar|G}} is a finite group of order {{mvar|n}}, then {{mvar|G}} is isomorphic to a subgroup of the standard symmetric group <math>S_n</math>.  But {{mvar|G}} might also be isomorphic to a subgroup of a smaller symmetric group, <math>S_m</math> for some <math>m<n</math>; for instance, the order 6 group <math>G=S_3</math> is not only isomorphic to a subgroup of <math>S_6</math>, but also (trivially) isomorphic to a subgroup of <math>S_3</math>.<ref name="Cameron2008">{{cite book|author=Peter J. Cameron|title=Introduction to Algebra, Second Edition|url=https://archive.org/details/introductiontoal00came_088|url-access=limited|year=2008|publisher=Oxford University Press|isbn=978-0-19-852793-0|page=[https://archive.org/details/introductiontoal00came_088/page/n144 134]}}</ref>  The problem of finding the minimal-order symmetric group into which a given group {{mvar|G}} embeds is rather difficult.<ref>{{Cite journal | doi = 10.2307/2373739| jstor = 2373739| title = Minimal Permutation Representations of Finite Groups| journal = American Journal of Mathematics| volume = 93| issue = 4| pages = 857–866| year = 1971| last1 = Johnson | first1 = D. L.}}</ref><ref>{{Cite journal | doi = 10.1023/A:1023860730624| year = 2003| last1 = Grechkoseeva | first1 = M. A.| journal = Siberian Mathematical Journal|title=On Minimal Permutation Representations of Classical Simple Groups| volume = 44| issue = 3| pages = 443–462| s2cid = 126892470}}</ref>

[[Jonathan Lazare Alperin|Alperin]] and Bell note that "in general the fact that finite groups are imbedded in symmetric groups has not influenced the methods used to study finite groups".<ref name="AlperinBell1995">{{cite book|author1=J. L. Alperin|author2=Rowen B. Bell|title=Groups and representations|url=https://archive.org/details/groupsrepresenta00alpe_213|url-access=limited|year=1995|publisher=Springer|isbn=978-0-387-94525-5|page=[https://archive.org/details/groupsrepresenta00alpe_213/page/n39 29]}}</ref>

When {{mvar|G}} is infinite, <math>\operatorname{Sym}(G)</math> is infinite, but Cayley's theorem still applies.