This article adapts material from the main article: Lagrange's theorem
This page is part of the Groupprops Guided tour for beginners (Jump to beginning of tour)
PREVIOUS: Index of a subgroup |UP: Introduction three (beginners) | NEXT: Generating set of a group
WHAT YOU NEED TO DO:
- Read and understand the statement of Lagrange's theorem
- Make sure the proof is clear to you. Fill in any missing details.
- 1 Statement
- 2 Facts used
- 3 Proof
- 4 Related facts
- 5 Infinite versions
- 6 Analogues
In a finite group, the order of any subgroup divides the order of the group. In fact, the ratio of the orders is the index of the subgroup, which is the same as the number of left cosets, and as the number of right cosets, of the subgroup.
Statement with symbols
- Left cosets partition a group: So the group is a disjoint union of left cosets of the subgroup
- Left cosets are in bijection via left multiplication: All the left cosets have the same size.
Given: A finite group , a subgroup
Proof: From fact (1), we know that we can write as a disjoint union of left cosets of . Let be the number of left cosets of and be the left cosets of . Then, we can write:
(the symbol stands for disjoint union).
Taking cardinalities both sides:
By fact (2) for each left coset of , so:
WHAT'S MORE: Further information on applications, converses, infinite versions and measure-theoretic versions of Lagrange's theorem. Some of these will be touched upon in the Mind's Eye Test and Interdisciplinary problems.
- Index is multiplicative: This states that if are subgroups then . Lagrange's theorem is a special case with the trivial subgroup.
Lagrange's theorem is extremely useful in providing information about the size and structure of subgroups given information about the size of the whole group. Here are some obvious corollaries of Lagrange's theorem:
- Subgroup of size more than half is whole group: This turns out to be useful when trying to prove that a certain subgroup is the whole group. It is also used to design probabilistic tests of primality.
- Prime order implies no proper nontrivial subgroup
- Order of element divides order of group: In a finite group, the order of any element, i.e., the smallest positive integer for which its power is the identity element, is a divisor of the order of the group.
Normal subgroups and surjective homomorphisms
Combining Lagrange's theorem with the first isomorphism theorem, we see that given any surjective homomorphism of finite groups and , the order of must divide the order of . That's because, if is the kernel of the homomorphism, the first isomorphism theorem identifies with the quotient group , whose order equals the index . See:
- Order of quotient group divides order of group
- Order of extension group is product of order of normal subgroup and quotient group
In fact, more is true: the surjective homomorphism from to has the property that the inverse images of all elements of have equal size. Further information: Variety of groups is congruence-uniform
Transitive group actions
Hence, the order of divides the order of .
Further information: Group having subgroups of every order dividing the group order
While there's no direct formulation of a converse to Lagrange's theorem, one plausible converse might be: given any finite group , and any positive divisor of the order of , there exists a subgroup of of order . This is, however false. The smallest counterexample is the alternating group on four elements, which has order 12 and has no subgroup of order 6 (see its subgroup structure). However, partial versions of the converse are true:
- For a cyclic group, there is a unique subgroup of every order dividing the order of the group.
- A group of prime power order, and more generally, a finite nilpotent group, and even more generally a finite supersolvable group, has subgroups of every possible order dividing the order of the group. For full proof, refer: Prime power order implies subgroups of all orders dividing the group order, Finite supersolvable implies subgroups of all orders dividing the group order
- Sylow's theorem: In any finite group, there exist Sylow subgroups. A Sylow subgroup is a group of prime power order, whose order and index are relatively prime.
- Hall's theorem: A finite group is a finite solvable group if and only if it has Hall subgroups of all permissible orders. A Hall subgroup is a subgroup whose order and index are relatively prime.
- Every finite solvable group is a subgroup of a finite group having subgroups of all orders dividing the group order
Choice of coset representatives
Lagrange's theorem proves that the order of a group equals the product of the order of the subgroup and the number of left cosets. There is, however, no natural bijection between the group and the Cartesian product of the subgroup and the left coset space. In other words, for a subgroup , there is no natural bijection:
We can obtain a bijection if we choose a set of coset representatives, i.e., we make a choice of one element in each left coset. Such a choice gives a specific bijection between the subgroup and each of its left cosets. Essentially, the coset representative is used as a reference point. To describe an element of , we describe its coset, and the ratio between that element and its coset representative, and this yields the bijection.
However, there is in general no natural choice of coset representatives, and being able to choose coset representatives requires the axiom of choice. The Vitali construction of a non-measurable set, as well as the Banach-Tarski paradox, use precisely this ability.
Further information: Cardinal multiplication#Lagrange's theorem
While Lagrange's theorem is typically stated for a finite group, the reasoning used in its proof also works for infinite groups. Thus, if is any group, is a subgroup, then, in the sense of cardinals:
The theory of multiplication of infinite cardinals allows us to determine the cardinality of knowing the cardinality of and ; however, it does not permit us to always compute successfully the cardinality of using the other two, or to compute the index using the other two quantities.
Groups with measures
Lagrange's theorem has analogues in groups equipped with measures (in fact, the analogues make sense in groups equipped with finitely additive functions, such as amenable discrete groups). Here, we replace the order of the group and subgroup by their measures, while the index remains the index. Thus, if is a group with a left-invariant measure and is a measurable subgroup of , of finite index in , then:
Further information: Lagrange's theorem for measures
Weaker algebraic structures
The analogue of Lagrange's theorem fails to hold for structures like magmas, semigroups, and monoids. There are two problems: the left cosets of any submonoid are not necessarily pairwise disjoint, and the left cosets may not have equal size. For a cancellative monoid, the left cosets do always have equal size, but they still may not be pairwise disjoint.
This page is part of the Groupprops Guided tour for beginners (Jump to beginning of tour). If you found anything difficult or unclear, make a note of it; it is likely to be resolved by the end of the tour.
PREVIOUS: Index of a subgroup | UP: Introduction three (beginners) | NEXT: Generating set of a group