Abstract Algebra: Theory and Applications, Remixed!

Example 1.21.

Let \(p\text{,}\) \(q\text{,}\) \(r\text{,}\) and \(s\) be integers, where \(q\) and \(s\) are nonzero. Define \(p/q \sim r/s\) if \(ps = qr\text{.}\) Clearly \(\sim\) is reflexive and symmetric. To show that it is also transitive, suppose that \(p/q \sim r/s\) and \(r/s \sim t/u\text{,}\) with \(q\text{,}\) \(s\text{,}\) and \(u\) all nonzero. Then \(ps = qr\) and \(ru = st\text{.}\) Therefore,

Since \(s \neq 0\text{,}\) \(pu = qt\text{.}\) Consequently, \(p/q \sim t/u\text{.}\)

Example 1.22.

Suppose that \(f\) and \(g\) are differentiable functions on \({\mathbb R}\text{.}\) We can define an equivalence relation on such functions by letting \(f(x) \sim g(x)\) if \(f'(x) = g'(x)\text{.}\) It is clear that \(\sim\) is both reflexive and symmetric. To demonstrate transitivity, suppose that \(f(x) \sim g(x)\) and \(g(x) \sim h(x)\text{.}\) From calculus we know that \(f(x) - g(x) = c_1\) and \(g(x)- h(x) = c_2\text{,}\) where \(c_1\) and \(c_2\) are both constants. Hence,

and \(f'(x) - h'(x) = 0\text{.}\) Therefore, \(f(x) \sim h(x)\text{.}\)

Example 1.23.

For \((x_1, y_1 )\) and \((x_2, y_2)\) in \({\mathbb R}^2\text{,}\) define \((x_1, y_1 ) \sim (x_2, y_2)\) if \(x_1^2 + y_1^2 = x_2^2 + y_2^2\text{.}\) Then \(\sim\) is an equivalence relation on \({\mathbb R}^2\text{.}\)

Example 1.24.

Let \(A\) and \(B\) be \(2 \times 2\) matrices with entries in the real numbers. We can define an equivalence relation on the set of \(2 \times 2\) matrices, by saying \(A \sim B\) if there exists an invertible matrix \(P\) such that \(PAP^{-1} = B\text{.}\) For example, if

then \(A \sim B\) since \(PAP^{-1} = B\) for

Let \(I\) be the \(2 \times 2\) identity matrix; that is,

Then \(IAI^{-1} = IAI = A\text{;}\) therefore, the relation is reflexive. To show symmetry, suppose that \(A \sim B\text{.}\) Then there exists an invertible matrix \(P\) such that \(PAP^{-1} = B\text{.}\) So

Finally, suppose that \(A \sim B\) and \(B \sim C\text{.}\) Then there exist invertible matrices \(P\) and \(Q\) such that \(PAP^{-1} = B\) and \(QBQ^{-1} = C\text{.}\) Since

the relation is transitive. Two matrices that are equivalent in this manner are said to be similar.

Example 1.27.

In the equivalence relation in Example 1.21, two pairs of integers, \((p,q)\) and \((r,s)\text{,}\) are in the same equivalence class when they reduce to the same fraction in its lowest terms.

Example 1.28.

In the equivalence relation in Example 1.22, two functions \(f(x)\) and \(g(x)\) are in the same partition when they differ by a constant.

Example 1.29.

We defined an equivalence class on \({\mathbb R}^2\) by \((x_1, y_1 ) \sim (x_2, y_2)\) if \(x_1^2 + y_1^2 = x_2^2 + y_2^2\text{.}\) Two pairs of real numbers are in the same partition when they lie on the same circle about the origin.

Example 1.30.

Let \(r\) and \(s\) be two integers and suppose that \(n \in {\mathbb N}\text{.}\) We say that \(r\) is congruent to \(s\) modulo \(n\text{,}\) or \(r\) is congruent to \(s\) mod \(n\text{,}\) if \(r - s\) is evenly divisible by \(n\text{;}\) that is, \(r - s = nk\) for some \(k \in {\mathbb Z}\text{.}\) In this case we write \(r \equiv s \pmod{n}\text{.}\) For example, \(41 \equiv 17 \pmod{ 8}\) since \(41 - 17=24\) is divisible by \(8\text{.}\) We claim that congruence modulo \(n\) forms an equivalence relation of \({\mathbb Z}\text{.}\) Certainly any integer \(r\) is equivalent to itself since \(r - r = 0\) is divisible by \(n\text{.}\) We will now show that the relation is symmetric. If \(r \equiv s \pmod{ n}\text{,}\) then \(r - s = -(s -r)\) is divisible by \(n\text{.}\) So \(s - r\) is divisible by \(n\) and \(s \equiv r \pmod{ n}\text{.}\) Now suppose that \(r \equiv s \pmod{ n}\) and \(s \equiv t \pmod{ n}\text{.}\) Then there exist integers \(k\) and \(l\) such that \(r -s = kn\) and \(s - t = ln\text{.}\) To show transitivity, it is necessary to prove that \(r - t\) is divisible by \(n\text{.}\) However,

and so \(r - t\) is divisible by \(n\text{.}\)

If we consider the equivalence relation established by the integers modulo \(3\text{,}\) then

Notice that \([0] \cup [1] \cup [2] = {\mathbb Z}\) and also that the sets are disjoint. The sets \([0]\text{,}\) \([1]\text{,}\) and \([2]\) form a partition of the integers.

The integers modulo \(n\) are a very important example in the study of abstract algebra and will become quite useful in our investigation of various algebraic structures such as groups and rings. In our discussion of the integers modulo \(n\) we have actually assumed a result known as the division algorithm, which will be stated and proved in Section 6.1.