Math 2.0

Group theory and generalizations Proof

Proof of the order of the symmetric group

Builds on Symmetric groupPermutationOrder of a groupNumber of permutations

Proof

  1. Let nn be a positive integer and let X={1,2,…,n}X = \{1, 2, \dots, n\}, a set with nn elements.
  2. By the definition of the symmetric group, Sn=Sym⁡(X)S_n = \operatorname{Sym}(X) is the set of all bijections from XX to XX.
  3. These bijections are exactly the permutations of XX.
  4. By the number of permutations, XX has exactly n!n! permutations.
  5. The order of SnS_n is the number of its elements. By steps 2 to 4, it is n!n!.

Idea

The group SnS_n is just the set of permutations of nn symbols with composition. So its order is the number of such permutations, which is n!n! by a counting argument. The image of 11 has nn choices, the image of 22 then has n−1n - 1 choices, and so on.

Reading path

To understand this page from the ground up, read these 50 pages in order. The foundations come first. The path takes the proofs Proof that a composition of injections is injective, Proof that a function is bijective iff it has a two-sided inverse, Proof of the complement principle, Proof of the number of injections, Proof that a composition of surjections is surjective, Proof of the rule of sum, Proof of the number of permutations by counting injections, Proof of the bijection principle.

  1. Cardinality of a finite set definition
  2. Element definition
  3. Factorial definition
  4. Falling factorial definition
  5. Group concept
  6. Permutation definition
  7. Proposition concept
  8. Set definition
  9. Order of a group definition
  10. Symmetric group definition
  11. Conjunction definition
  12. Implication definition
  13. Predicate definition
  14. Empty set object
  15. Ordered pair definition
  16. Intersection definition
  17. Existential quantifier definition
  18. Universal quantifier definition
  19. Cartesian product definition
  20. Disjoint sets definition
  21. Subset definition
  22. Uniqueness quantifier definition
  23. Binary relation definition
  24. Function definition
  25. Codomain definition
  26. Function composition definition
  27. Identity function definition
  28. Injective function definition
  29. Restriction of a function definition
  30. Surjective function definition
  31. Left inverse definition
  32. Right inverse definition
  33. Proof that a composition of injections is injective proof
  34. Proof that a composition of surjections is surjective proof
  35. Bijective function definition
  36. Composition of injections is injective statement
  37. Composition of surjections is surjective statement
  38. Proof of the rule of sum proof
  39. Proof that a function is bijective iff it has a two-sided inverse proof
  40. Rule of sum statement
  41. Bijective iff it has a two-sided inverse statement
  42. Proof of the complement principle proof
  43. Proof of the bijection principle proof
  44. Complement principle statement
  45. Bijection principle statement
  46. Proof of the number of injections proof
  47. Number of injections statement
  48. Proof of the number of permutations by counting injections proof
  49. Number of permutations statement
  50. Proof of the order of the symmetric group proof

Where this leads

3 pages build on this one.

Further reading

  1. Web https://en.wikipedia.org/wiki/Permutation, Properties
About this page
Tag9RMV75ESTN
URIm2://9RMV75ESTN
Kindproof
WritingW0 stub
MSC20B30
ProvesOrder of the symmetric group
UsesSymmetric group, Permutation, Order of a group, Number of permutations
Changed4 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.