Definition 1.2.1.
Let \(X\) be a non-empty set. A partition of \(X\) is a collection \(P=\{X_i\mid i \in I\}\) of nonempty subsets so that
- \(\ds X = \bigcup_{i\in I} X_i\text{,}\) and
- \(X_i\cap X_j = \emptyset\) for all \(i\ne j.\)
Section 1.2 Partitions and Equivalence Relations
In our bid to classify things by type, we introduce the notion of isomorphism to say two objects are of the same type. That means that when we look at the set of all objects (say groups), we partition that set of objects into equivalence classes so that any two objects in one class are isomorphic, but no two objects from different classes can be isomorphic.
The notions of a partition and of a set of equivalence classes are deeply intertwined. Let’s review the basics.
Given a nonempty set \(X,\) a partition of \(X\) is simply a collection of non-overlapping subsets whose union is the original set. For example, the pieces of a puzzle form a partition of the image which is their union. The set of all M&M’s in a bag can be partitioned by color. We give a formal definition.
The closely related notion is that of an equivalence relation on a nonempty set. Formally, we have
Definition 1.2.2.
Let \(X\) be a non-empty set. A relation on \(X\) is a subset \(R\subseteq X\times X\text{,}\) that is a collection of ordered pairs. Often instead of saying \((x,y)\in R\text{,}\) write \(x \sim y\) and say \(x\) is related to \(y.\)
An equivalence relation on \(X\) is a relation which satisfies three properties:
- \(x\sim x\) (i.e., \((x,x) \in R\)) for all \(x\in X\text{.}\) This is called the reflexive property of the relation.
- If \(x\sim y,\) then \(y \sim x\text{,}\) that is, whenever the ordered pair \((x,y) \in R\text{,}\) then also \((y,x) \in R.\) This is called the symmetric property of the relation.
- If \(x \sim y\) and \(y \sim z\text{,}\) then \(x\sim z\text{,}\) that is, if \((x,y), (y,z) \in R\text{,}\) then so it \((x,z).\) This is called the transitive property of the relation.
Let \(\sim\) be an equivalence relation on a set \(X.\) For each \(x\in X,\) the equivalence class containing \(x\) is given by:
\begin{equation*}
[x] = \{y \in X \mid y\sim x\}.
\end{equation*}
Notice that by the reflexive property, \(x \in [x]\text{,}\) and we did not need to fuss in the definition about whether \(y\sim x\text{,}\) or \(x\sim y\) since the relation is symmetric. And the transitive property shows that two equivalence classes are either the same or disjoint. It follows that
Proposition 1.2.3.
Let \(\sim\) be an equivalence relation on a set \(X.\) Then \(P = \{ [x] \mid x\in X\}\) forms a partition of \(X\text{.}\) In words, the set of equivalence classes forms a partition of the set.
Conversely, we have
Proposition 1.2.4.
Given a partition \(P=\{X_i\mid i\in I\}\) of a set \(X\text{,}\) the relation \(x\sim y\) if and only if \(x,y \in X_j\) for some (unique) \(j\in I\) defines an equivalence relation on \(X\) in which the equivalence classes are the elements of the original partition.
Example 1.2.5. The Integers modulo \(n\).
One of the most familiar example comes from introducing an equivalence relations on the integers, \(\Z.\) We fix a positive integer \(n\text{,}\) and define the relation by
\begin{equation*}
j\sim k \text{ iff } j\equiv k \pmod n.
\end{equation*}
Then the set of equivalences classes is called the integers modulo \(n\). There are multiple notations for this, but the set of classes is generally denoted
\begin{equation*}
\Z_n \text{ (or) } \Z/n\Z = \{[k] \mid k \in \Z\}.
\end{equation*}
As you recall from your course, \(\Z_n\) consists of \(n\) equivalence classes often denoted with representatives given by \([0], [1], \dots, [n-1].\)
Example 1.2.6. Similarity classes of matrices.
If \(F\) is a field, we say that two matrices \(A,B
\in M_n(F)\) are similar if there is an invertible matrix \(P\) so that \(B=P^{-1}AP.\) We often adopt the more general term that \(A\) and \(B\) are conjugate.
Once again it is easy to verify that similarity is an equivalence relation. If you have had an advanced linear algebra course, you would know that each similarity class \([A]\) has a distinguished representative which is the rational canonical form of \(A.\)
Now often, as in the case of \(\Z_n\text{,}\) we wish to introduce an algebraic structure on the set of equivalence classes. With \(\Z_n\) you know that the operations
\begin{equation*}
[a]+[b] = [a+b] \text{ and } [a][b]=[ab]
\end{equation*}
makes \(\Z_n\) into a commutative ring with identity.
Insight 1.2.7.
And other times, algebraic objects that we have known since grade school suddenly reveal themselves in the guise of equivalence classes. The rational numbers, \(\Q\text{,}\) is such an example. How can something we understand so intrinsically be hiding this underlying structure?
Well, if we went back to grade school we could solve the following arithmetic problem using some curious-looking rules learned long ago:
\begin{equation*}
\frac 25 + \frac37 = \frac{29}{35}.
\end{equation*}
Just what is the rule that tells you how to add \(\ds \frac{a}{b} + \frac{c}{d}?\) Yes, after a moment’s thought you could write down the rule, but where in the world did it come from and why is such a complicated-looking rule really needed?
Indeed, what could we possible mean by writing
\begin{equation*}
\frac12=\frac24=\frac5{10}, \text{ etc.}\text{?}
\end{equation*}
It is becoming very clear that this symbol \(\ds
\frac{a}{b}\) or \(a/b\) has a nontrivial meaning.
It is easy to believe writing \(a/b\) where there is a distinguished numerator and denominator that we are doing nothing more than introducing a fancy notation for an ordered pair \((a,b)\) where the first coordinate is the numerator and the second the denominator. But then we note that while \(\ds\frac12 =
\frac24,\) it is not true that \((1,2) = (2,4).\) So it is time to understand what we have been doing for years without a thought about higher-level mathematics.
The short version is that we define a set \(X\) as
\begin{equation*}
X= \Z \times \Z\setminus \{0\},
\end{equation*}
the set of ordered pairs with arbitrary first coordinate, but nonzero second coordinate. Then we define the relation \((a,b)\sim (c,d) \text{ iff } ad-bc=0.\) As this is an equivalence relation, we can talk about its equivalence classes, and we denote the equivalence class of \((a,b)\) not as \([(a,b)],\) but as \(a/b\) or \(\ds\frac{a}{b}.\)
Then we are left with the task of giving definitions for addition and multiplication which are well-defined on the equivalence classes, that is independent of the choice of representative of the class. But you know all that.
