# Left cosets of a subgroup partition a monoid

## Contents

## Statement

Suppose is a monoid and is a subgroup of , i.e., is a subset of with the same identity element and forming a group under the induced binary operation. Then, the following equivalent conditions hold:

- The left cosets of , namely , form a partition of . In other words, is a disjoint union of all the left cosets of in .
- The relation is an equivalence relation on .
- For every , there is
*exactly*one left coset of containing . - For , either or is empty.

## Equivalence of statements

These statements are equivalent because of the following general fact about sets and equivalence relations. If is a set, and is an equivalence relation on , then we can partition as a disjoint union of *equivalence classes* under . Two elements and are defined to be in the same equivalence class under if .

Conversely, if is partitioned as a disjoint union of subsets, then the relation of being in the same subset is an equivalence relation on .

Hence, there is a correspondence between *equivalence relations* on a set and *partitions of the set* into subsets. This statement about left cosets thus states that the left cosets partition the group, which is *also* the same as saying that the relation of one element being in the left coset of another, is an equivalence relation.

Here, we give the proof both in form (2) and form (4). The two proofs are essentially the same, but they are worked out in somewhat different language, and explain how to think both in terms of *equivalence relations* and in terms of *partitions*.

## Related facts

- Left cosets partition a group: The typical formulation, where the whole monoid is also a group.
- left cosets are in bijection via left multiplication versus Left cosets of a subgroup are not in bijection via left multiplication in a monoid: In a group, the left cosets of a subgroup are in bijection via left multiplication. But this fails to hold for monoids in general.
- Lagrange's theorem, which states that the order of any subgroup divides the order of the group. This combines the fact that left cosets partition the group and the fact that they are in bijection via left multiplication.
- Left cosets of a cyclic subgroup partition an alternative loop

## Proof in form (2)

**Given**: A monoid , a subgroup

**To prove**: The relation such that , is an equivalence relation on .

Note that in the proof, we will freely use the existence of inverses of elements in as well as associativity in . Further, it is important for the proofs that the identity element of is the same as that of .

### Reflexivity

**To prove**: For any , .

**Proof**: Clearly (since is a subgroup with the *same* identity element). Hence, for any , , so : is in its own left coset.

### Symmetry

**To prove**: For any such that , we have .

**Proof**: If , for some , then . Since and is a subgroup, . Thus, if is in the left coset of , then is in the left coset of . In symbols, .

### Transitivity

**To prove**: If are such that , and , then

**Proof**: If , and , for , and . Since is a subgroup, , so is in the left coset of .

## Proof in form (4)

**Given**: A monoid , a subgroup , two elements

**To prove**: The left cosets and are either equal or disjoint (they have empty intersection)

**Proof**: We'll assume that and are *not* disjoint, and prove that they are equal.

For this, suppose . Then, there exist such that . Thus, and .

Now, for any element , we have , and similarly, for every element , we have . Thus, and , so .

## Other proofs

### Orbits under a group action

One easy way of seeing that the left cosets partition a monoid is by viewing the left cosets as orbits of the monoid under the action of the subgroup by right multiplication.