Coset representatives and the axiom of choice
This is a survey article related to:left transversal of a subgroup
View other survey articles about left transversal of a subgroup
PREREQUISITES: group, subgroup, left coset of a subgroup, left cosets partition a group, left cosets are in bijection via left multiplication
Consider a group and a subgroup . Then, the left cosets of are all of the same size (because left cosets are in bijection via left multiplication) and they partition the group). Thus, is a union of copies of .
This gives Lagrange's theorem:
where is the cardinality of .
However, there is no natural choice of bijection of the form:
Such a bijection can be obtained if we pick a left transversal of in : in other words, we make a choice of one element from every coset of in . We first examine how a choice of left transversal yields a bijection.
- 1 A left transversal and a coordinatization of the group
- 2 Paradoxical consequences of being able to choose coset representatives
A left transversal and a coordinatization of the group
How a left transversal gives a bijection with the product
Suppose is a left transversal of in . In other words, contains exactly one element from each left coset of in . For any , let denote the representative of the left coset .
Then, the map is given by:
In other words, the map sends an element of to the extent by which it differs from its representative, and its coset. The map the other way around is:
Here is one way of thinking of this. Each coset is a translate of the subgroup, but as a translate, it has no natural origin or reference point with respect to which other elements of the coset can be measured. A choice of representative for each coset gives precisely such a reference point. With this reference point, the left coset can be naturally identified with the subgroup itself. If we choose a representative for each coset, we thus identify with the Cartesian product.
Why a left transversal needs the axiom of choice
The axiom of choice is a general result stating that, given an arbitrary family of disjoint nonempty sets, we can find a set such that intersects each in exactly one element.
To pick a left transversal, we need to do exactly that. We are given an arbitrary collection of disjoint nonempty sets, namely the cosets of a subgroup. We need to pick a left transversal, which is a set that intersects each left coset in exactly one element.
Situations where it does not need the axiom of choice
In many situations, choosing a left transversal does not require the full strength of the axiom of choice:
- When the group is finite, or more generally, when the subgroup has finite index, we only need to make finitely many choices. Making finitely many choices does not require the axiom of choice, and can be done within the framework of axiomatic set theory without choice (Zermelo-Fraenkel set theory).
- In some cases, there is a natural choice of coset representatives. For instance, for the trivial subgroup, there is only one choice of coset representatives. Similarly, for some infinite groups, there is a choice of coset representatives that can be described using a group-theoretic condition.
- When the subgroup has countable index, then choosing a left transversal requires countably many choices. This requires the axiom of countable choice, which is weaker than the full strength of choice. Also, the axiom of countable choice does not lead to any of the paradoxical consequences of the axiom of choice.
Paradoxical consequences of being able to choose coset representatives
The ability to choose coset representatives can have a number of consequences that appear paradoxical. In most of these setups, the group is an uncountable group and the subgroup is countable. The coset representatives are chosen in such a way that they all lie within a compact subset of Euclidean space. This uncountable collection of elements in a compact subset has a very weird arrangement and this arrangement can be used to prove various results.