Skip to main content

Section 12.1 Read

Subsection Partitions

Definition 12.1.1. Partition.

A partition of a collection is a subdivision into non-overlapping subcollections (called partition cells) so that every element in the original collection is in one and only one cell.

Usually the most convenient way to identity partition cells is to choose one representative element in each cell to represent the entire cell. So if element \(x\) is in our collection, by definition it appears in one and only one partition cell, so we can unambiguously write \(\eqclass{x}\) to represent that entire partition cell containing \(x\text{,}\) and now \(x\) is the cell representative.

Example 12.1.2. Evens and odds.

We can partition the integers into evens and odds. Choosing \(1\) to represent the odds and \(2\) to represent the evens, we have

\begin{align*} \eqclass{1} \amp = \{ \dotsc, -3, -1, 1, 3, \dotsc \} \text{,} \\ \eqclass{2} \amp = \{ \dotsc, -4, -2, 0, 2, 4, \dotsc \} \text{.} \end{align*}

Note that a choice of representatives is not unalterable; we can make a new choice of representatives whenever we like. For example, it is also valid to write

\begin{align*} \eqclass{3} \amp = \{ \dotsc, -3, -1, 1, 3, \dotsc \} \text{,} \\ \eqclass{-4} \amp = \{ \dotsc, -4, -2, 0, 2, 4, \dotsc \} \text{.} \end{align*}

That is, because \(1\) and \(3\) are in the same cell, we have \(\eqclass{3} = \eqclass{1}\text{,}\) and similarly \(\eqclass{-4} = \eqclass{2}\text{.}\)

Example 12.1.3. Positives and negatives.

We can also partition the integers into positives, negatives, and neither:

\begin{align*} \eqclass{1} \amp = \{ 1, 2, 3, \dotsc \} \text{,} \\ \eqclass{0} \amp = \{ 0 \} \text{,} \\ \eqclass{-1} \amp = \{ -1, -2, -3, \dotsc \} \text{.} \end{align*}

Example 12.1.4. \(\Z_n\).

Technically, elements in the group \(\Z_n\) are not numbers, they are partition cells of numbers. For example, when \(n=5\) we can partition the integers into the following cells:

\begin{align*} \eqclass{0} \amp = \{ \dotsc, -5, 0, 5, 10, \dotsc \} \text{,} \\ \eqclass{1} \amp = \{ \dotsc, -4, 1, 6, 11, \dotsc \} \text{,} \\ \eqclass{2} \amp = \{ \dotsc, -3, 2, 7, 12, \dotsc \} \text{,} \\ \eqclass{3} \amp = \{ \dotsc, -2, 3, 8, 13, \dotsc \} \text{,} \\ \eqclass{4} \amp = \{ \dotsc, -1, 4, 9, 14, \dotsc \} \text{.} \end{align*}

When we write

\begin{equation*} 3 + 4 = 2 \end{equation*}

using clock arithmetic on a \(5\)-hour clock, it actually is nonsense, because in reality

\begin{equation*} 3 + 4 = 7 \text{.} \end{equation*}

What's going on is that we're not adding the numbers \(3\) and \(4\text{,}\) we're adding the entire partition cells that contain \(3\) and \(4\text{:}\)

\begin{equation*} \eqclass{3} + \eqclass{4} = \eqclass{7} = \eqclass{2} \text{,} \end{equation*}

where the last step is valid because numbers \(7\) and \(2\) appear in the same partition cell. And we would get the same result if we used different representatives:

\begin{equation*} \eqclass{13} + \eqclass{-1} = \eqclass{12} = \eqclass{2} \text{.} \end{equation*}

(This is important — clock arithmetic wouldn't work if the operation results weren't independent of choice of cell representatives.)

Example 12.1.5. Cosets.

We have already seen that left cosets of a subgroup partition a group. And the same is true for right cosets.

Subsection Equivalence

A relation is some sort of relationship between objects in a certain collection. For example, “is less than” is a relation on numbers.

Definition 12.1.6. Equivalence relation.

A relation that satisfies the following.

  • Reflexive.

    Every object is related to itself.

  • Symmetric.

    The relation can be stated in either order without changing the meaning. That is, saying “\(b\) is related to \(a\)” is the same as saying “\(a\) is related to \(b\text{.}\)”

  • Transitive.

    Chains of relations can be completed. That is, if \(a\) is related to \(b\) and \(b\) is related to \(c\text{,}\) then it must also be that \(a\) is related to \(c\text{.}\)

In the case of an equivalence relation, we usually say “is equivalent to” instead of “is related to.”

Example 12.1.8.

The partition of \(\Z\) into positives, negatives, and zero in Example 12.1.3 corresponds to the equivalence relation where \(0\) is equivalent only to itself, and two nonzero numbers are considered equivalent if they have the same sign.

Example 12.1.9.

The partition of \(\Z\) relative to \(n = 5\) in Example 12.1.4 corresponds to the equivalence relation where two integers are considered equivalent if they are both the same amount greater than a multiple of \(5\text{.}\) For example, \(22\) is equivalent to \(7\) because \(22\) is \(2\) more than \(20\) and likewise \(7\) is \(2\) more than \(5\text{.}\) (And both of these numbers is equivalent to \(2\text{.}\))

In this case, the equivalence classes are usually called residue classes modulo \(5\), the natural class representatives \(0, 1, 2, 3, 4\) are called the residues of the numbers in their respective classes, and the technical terminology for “clock arithmetic” is arithmetic modulo \(5\).

Example 12.1.10.

The partition of \(\Z\) into evens and odds in Example 12.1.2 is actually just the partition into residue classes modulo \(2\text{.}\)

Subsection Motivation

In this course we will use partitions/equivalence classes for two things:

  • to help us count complicated collections, since if we count the objects in each equivalence class we can get the total by adding all those class counts together; and

  • to create new examples of groups by trying to define a group operation between equivalence classes.

We have already seen one example of the second task: the group \(\Z_n\) is really the group of residue classes of integers modulo \(n\text{,}\) where we add classes by adding any choice of representatives for the classes.