Discrete Mathematics: An Active Approach to Mathematical Reasoning

In Section 8.2 we studied three properties of a relation, the reflexive, symmetric, and transitive properties. These three properties are important for generalizing the idea of equality in mathematics. We may want to relate objects based on certain criteria; objects that share that criteria are “equivalent.” For example, you may recall from geometry, the idea of congruent triangles. Two triangles are congruent if they have the same angles. In geometry, we may not care at all about the lengths of the sides, just the angles. In this case, we relate triangles with the same angles and treat them as the same triangle.

In Example 8.2.8 we proved that the relation given by \((m, n)\in R \Leftrightarrow 3\mid (m-n)\) is an equivalence relation since we proved it is reflexive, symmetric, and transitive.

In fact, the proof can easily be adapted to show \((m, n)\in R \Leftrightarrow d\mid (m-n)\) is an equivalence relation for \(d\neq 0, d\in \mathbb{Z}\text{.}\) The details are left as an exercise, Exercise 8.3.9

This relation is an important enough that it has its own definition.

Given a specific \(a\in A\text{,}\) we find the equivalence class of \(a\) by finding all the elements that are related to \(a\text{.}\) Keep in mind the equivalence class is a set, denoted \([a]\text{.}\)

We can notice a few things from this last example. We can see that some of our equivalence classes are the same. In particular, \([0]=[3]\) and \([2]=[-1]\text{.}\) In fact, there are only three distinct equivalence classes, \([0], [1], [2]\text{,}\) any other equivalence class will equal one of these.

A few other things to notice, distinct equivalence classes are disjoint--they have no elements in common. Also, \([a]\) contains \(a\text{.}\) We may also recognize that the equivalence classes \([0], [1], [2]\) partition the integers.

Once again, the distinct equivalence classes are disjoint--they have no elements in common. Furthermore, the equivalence classes \([\emptyset], [\{1\}], [\{1, 2\}], [\{1, 2, 3\}]\) partition the power set by size of the subset.

There is an important connection between equivalence classes and partitions, as we see in the next two theorems.

Conversely, as we saw in Activity 8.3.3, if we have a partition \(\{A_1, A_2, \ldots, A_n\ldots\}\) of \(A\) and define the relation \((a, b)\in R \Leftrightarrow a\) and \(b\) are in the same subset \(A_i\text{,}\) then \(R\) is an equivalence relation. We call this the equivalence relation induced by the partition.

We leave the details of the proof of Theorem 8.3.7 as an exercise.

The proof of Theorem 8.3.6 follows directly from the next two Lemmas.

Lemma 8.3.8 really says that if two elements are related in an equivalence relation, they must have the same equivalence class. You can check this with the above examples. Note, we needed the symmetric and transitive properties to prove this lemma.

Lemma 8.3.9 really says that any two equivalence classes are either disjoint or exactly the same.

Theorem 8.3.6 follows since, by the reflexive property, \(x R x, \forall x\in A\) means every element is in an equivalence class. Thus, the union of the equivalence classes is all of \(A\text{.}\) By Lemma 8.3.9 distinct equivalence classes are disjoint. Thus, we have a partition of \(A\text{.}\)