The notion that group theory captures the idea of "symmetry" derives from the notion of the symmetric group, and the very important theorem due to Cayley that every group is a subgroup of a symmetric group.
Definition
Let $~$X$~$ be a Set. A bijection $~$f: X \to X$~$ is a permutation of $~$X$~$. Write $~$\mathrm{Sym}(X)$~$ for the set of permutations of the set $~$X$~$ (so its elements are functions).
Then $~$\mathrm{Sym}(X)$~$ is a group under the operation of composition of functions; it is the symmetric group on $~$X$~$. (It is also written $~$\mathrm{Aut}(X)$~$, for the automorphism group.)
We write $~$S_n$~$ for $~$\mathrm{Sym}(\{ 1,2, \dots, n\})$~$, the symmetric group on $~$n$~$ elements.
Elements of $~$S_n$~$
We can represent a permutation of $~$\{1,2,\dots, n\}$~$ in two different ways, each of which is useful in different situations.
Double-row notation
Let $~$\sigma \in S_n$~$, so $~$\sigma$~$ is a function $~$\{1,2,\dots,n\} \to \{1,2,\dots,n\}$~$. Then we write $$~$\begin{pmatrix}1 & 2 & \dots & n \\ \sigma(1) & \sigma(2) & \dots & \sigma(n) \\ \end{pmatrix}$~$$ for $~$\sigma$~$. This has the advantage that it is immediately clear where every element goes, but the disadvantage that it is quite hard to see the properties of an element when it is written in double-row notation (for example, "$~$\sigma$~$ cycles round five elements" is hard to spot at a glance), and it is not very compact.
Cycle notation
Cycle notation is a different notation, which has the advantage that it is easy to determine an element's order and to get a general sense of what the element does. Every element of $~$S_n$~$ can be expressed in (disjoint) cycle notation in an essentially unique way.
Product of transpositions
It is a useful fact that every permutation in a (finite) symmetric group may be expressed as a product of transpositions.
Examples
- The group $~$S_1$~$ is the group of permutations of a one-point set. It contains the identity only, so $~$S_1$~$ is the trivial group.
- The group $~$S_2$~$ is isomorphic to the Cyclic group of order $~$2$~$. It contains the identity map and the map which interchanges $~$1$~$ and $~$2$~$.
Those are the only two abelian symmetric groups. Indeed, in cycle notation, $~$(123)$~$ and $~$(12)$~$ do not commute in $~$S_n$~$ for $~$n \geq 3$~$, because $~$(123)(12) = (13)$~$ while $~$(12)(123) = (23)$~$.
- The group $~$S_3$~$ contains the following six elements: the identity, $~$(12), (23), (13), (123), (132)$~$. It is isomorphic to the Dihedral group $~$D_6$~$ on three vertices. ([group_s3_isomorphic_to_d6 Proof.])
Why we care about the symmetric groups
A very important (and rather basic) result is Cayley's Theorem, which states the link between group theory and symmetry.
%%%knows-requisite(Conjugacy class):
Conjugacy classes of $~$S_n$~$
It is a useful fact that the conjugacy class of an element in $~$S_n$~$ is precisely the set of elements which share its cycle type. (Proof.) We can therefore list the conjugacy classes of $~$S_5$~$ and their sizes. %%%
Relationship to the Alternating group
The Alternating group $~$A_n$~$ is defined as the collection of elements of $~$S_n$~$ which can be made by an even number of transpositions. This does form a group (proof).
%%%knows-requisite(Normal subgroup): In fact $~$A_n$~$ is a Normal subgroup of $~$S_n$~$, obtained by taking the quotient by the sign homomorphism. %%%
Comments
Patrick Stevens
Request for comment: is the definition of "cycle" something that should be on its own page? They're not about the symmetric group per se, but I've only heard of cycles being used in the context of symmetric groups.
Eric Bruylant
For core/definition pages I think we want to have super modular content (easier browsing, lets people pick just the parts they want to learn, reduces page scope creep), so putting it on its own page is good. It's a child of this page, which seems like the appropriate relationship.
Patrick Stevens
I took the plunge and put it on its own page.