Mathematical Reasoning: Writing and Proof (PreTeXt Edition)

Subsection Directed Graphs and Properties of Relations

In Section 7.1, we used directed graphs, or digraphs, to represent relations on finite sets. Three properties of relations were introduced in Beginning Activity 1 and will be repeated in the following descriptions of how these properties can be visualized on a directed graph.

Let \(A\) be a nonempty set and let \(R\) be a relation on \(A\text{.}\)

• The relation \(R\) is reflexive on \(\boldsymbol{A}\) provided that for each \(x \in A\text{,}\) \(x \mathrel{R} x\) or, equivalently, \(\left( {x, x} \right) \in R\text{.}\) This means that if a reflexive relation is represented on a digraph, there would have to be a loop at each vertex, as is shown in the following figure.

  

• The relation \(R\) is symmetric provided that for every \(x, y \in A\text{,}\) if \(x \mathrel{R} y\text{,}\) then \(y \mathrel{R} x\) or, equivalently, for every \(x, y \in A\text{,}\) if \(\left( {x, y} \right) \in R\text{,}\) then \(\left( {y, x} \right) \in R\text{.}\) This means that if a symmetric relation is represented on a digraph, then anytime there is a directed edge from one vertex to a second vertex, there would be a directed edge from the second vertex to the first vertex, as is shown in the following figure.

  

• The relation \(R\) is transitive provided that for every \(x, y, z \in A\text{,}\) if \(x \mathrel{R} y\) and \(y \mathrel{R} z\text{,}\) then \(x \mathrel{R} z\) or, equivalently, for every \(x, y, z \in A\text{,}\) if \(\left( {x, y} \right) \in R\) and \(\left( {y, z} \right) \in R\text{,}\) then \(\left( {x, z} \right) \in R\text{.}\) So if a transitive relation is represented by a digraph, then anytime there is a directed edge from a vertex \(x\) to a vertex \(y\) and a directed edge from \(y\) to a vertex \(z\text{,}\) there would be a directed edge from \(x\) to \(z\text{.}\)

  In addition, if a transitive relation is represented by a digraph, then anytime there is a directed edge from a vertex \(x\) to a vertex \(y\) and a directed edge from \(y\) to the vertex \(x\text{,}\) there would be loops at \(x\) and \(y\text{.}\) These two situations are illustrated as follows:

  

Subsection Definition of an Equivalence Relation

In mathematics, as in real life, it is often convenient to think of two different things as being essentially the same. For example, when you go to a store to buy a cold soft drink, the cans of soft drinks in the cooler are often sorted by brand and type of soft drink. The Coca Colas are grouped together, the Pepsi Colas are grouped together, the Dr. Peppers are grouped together, and so on. When we choose a particular can of one type of soft drink, we are assuming that all the cans are essentially the same. Even though the specific cans of one type of soft drink are physically different, it makes no difference which can we choose. In doing this, we are saying that the cans of one type of soft drink are equivalent, and we are using the mathematical notion of an equivalence relation.

An equivalence relation on a set is a relation with a certain combination of properties that allow us to sort the elements of the set into certain classes. In this section, we will focus on the properties that define an equivalence relation, and in the next section, we will see how these properties allow us to sort or partition the elements of the set into certain classes.

Most of the examples we have studied so far have involved a relation on a small finite set. For these examples, it was convenient to use a directed graph to represent the relation. It is now time to look at some other type of examples, which may prove to be more interesting. In these examples, keep in mind that there is a subtle difference between the reflexive property and the other two properties. The reflexive property states that some ordered pairs actually belong to the relation \(R\text{,}\) or some elements of \(A\) are related. The reflexive property has a universal quantifier and, hence, we must prove that for all \(x \in A\text{,}\) \(x \mathrel{R} x\text{.}\) Symmetry and transitivity, on the other hand, are defined by conditional sentences. We often use a direct proof for these properties, and so we start by assuming the hypothesis and then showing that the conclusion must follow from the hypothesis.

The relation \(M\) is reflexive on \(\Z\) and is transitive, but since \(M\) is not symmetric, it is not an equivalence relation on \(\Z\text{.}\)

Subsection Congruence Modulo \(\boldsymbol{n}\)

One of the important equivalence relations we will study in detail is that of congruence modulo \(n\text{.}\) We reviewed this relation in Beginning Activity 2.

Theorem 3.36 tells us that congruence modulo \(n\) is an equivalence relation on \(\mathbb{Z}\text{.}\) Recall that by the Division Algorithm, if \(a \in \mathbb{Z}\text{,}\) then there exist unique integers \(q\) and \(r\) such that

Theorem 3.37 and Corollary 3.38 then tell us that \(a \equiv r \pmod n\text{.}\) That is, \(a\) is congruent modulo \(n\) to its remainder \(r\) when it is divided by \(n\text{.}\) When we use the term “remainder” in this context, we always mean the remainder \(r\) with \(0 \leq r \lt n\) that is guaranteed by the Division Algorithm. We can use this idea to prove the following theorem.

Subsection Examples of Other Equivalence Relations

1. The relation \(\sim\) on \(\Q\) from Progress Check 7.13 is an equivalence relation.

2. Let \(A\) be a nonempty set. The equality relation on \(\boldsymbol{A}\) is an equivalence relation. This relation is also called the identity relation on \(\boldsymbol{A}\) and is denoted by \(I_A\text{,}\) where

   \begin{equation*} I_A = \left\{ {\left( {x, x} \right) \mid x \in A} \right\}\!\text{.} \end{equation*}

3. Define the relation \(\sim\) on \(\mathbb{R}\) as follows:

   For \(a, b \in \mathbb{R}\text{,}\) \(a \sim b\) if and only if there exists an integer \(k\) such that \(a - b = 2k\pi\text{.}\)

   We will prove that the relation \(\sim\) is an equivalence relation on \(\mathbb{R}\text{.}\) The relation \(\sim\) is reflexive on \(\mathbb{R}\) since for each \(a \in \mathbb{R}\text{,}\) \(a - a = 0 = 2 \cdot 0 \cdot \pi\text{.}\)

   Now, let \(a, b \in \mathbb{R}\) and assume that \(a \sim b\text{.}\) We will prove that \(b \sim a\text{.}\) Since \(a \sim b\text{,}\) there exists an integer \(k\) such that

   \begin{equation*} a - b = 2k\pi\text{.} \end{equation*}

   By multiplying both sides of this equation by \(-1\text{,}\) we obtain

   \begin{align*} ( { - 1} )( {a - b} ) \amp = ( { - 1} )( {2k\pi } )\\ b = a \amp = 2( { - k} )\pi\text{.} \end{align*}

   Since \(- k \in \mathbb{Z}\text{,}\) the last equation proves that \(b \sim a\text{.}\) Hence, we have proven that if \(a \sim b\text{,}\) then \(b \sim a\) and, therefore, the relation \(\sim\) is symmetric.

   To prove transitivity, let \(a, b, c \in \mathbb{R}\) and assume that \(a \sim b\) and \(b \sim c\text{.}\) We will prove that \(a \sim c\text{.}\) Now, there exist integers \(k\) and \(n\) such that

   \begin{equation*} a - b = 2k\pi \text{ and } b - c = 2n\pi\text{.} \end{equation*}

   By adding the corresponding sides of these two equations, we see that

   \begin{align*} ( {a - b} ) + ( {b - c} ) \amp = 2k\pi + 2n\pi\\ a - c \amp = 2( {k + n} )\pi \end{align*}

   By the closure properties of the integers, \(k + n \in \mathbb{Z}\text{.}\) So this proves that \(a \sim c\) and, hence the relation \(\sim\) is transitive.

   We have now proven that \(\sim\) is an equivalence relation on \(\mathbb{R}\text{.}\) This equivalence relation is important in trigonometry. If \(a \sim b\text{,}\) then there exists an integer \(k\) such that \(a - b = 2k\pi\) and, hence, \(a = b + k( {2\pi } )\text{.}\) Since the sine and cosine functions are periodic with a period of \(2\pi\text{,}\) we see that

   \begin{align*} \sin a \amp = \sin( {b + k( {2\pi } )} ) = \sin b,\text{ and }\\ \cos a \amp = \cos( {b + k( {2\pi } )} ) = \cos b\text{.} \end{align*}

   Therefore, when \(a \sim b\text{,}\) each of the trigonometric functions have the same value at \(a\) and \(b\text{.}\)

4. For an example from Euclidean geometry, we define a relation \(P\) on the set \(\mathcal{L}\) of all lines in the plane as follows:

   For \(l_1 , l_2 \in \mathcal{L}\text{,}\) \(l_1 \mathrel{P}l_2\) if and only if \(l_1\) is parallel to \(l_2\) or \(l_1 = l_2\text{.}\)

   We added the second condition to the definition of \(P\) to ensure that \(P\) is reflexive on \(\mathcal{L}\text{.}\) Theorems from Euclidean geometry tell us that if \(l_1\) is parallel to \(l_2\text{,}\) then \(l_2\) is parallel to \(l_1\text{,}\) and if \(l_1\) is parallel to \(l_2\) and \(l_2\) is parallel to \(l_3\text{,}\) then \(l_1\) is parallel to \(l_3\text{.}\) (Drawing pictures will help visualize these properties.) This tells us that the relation \(P\) is reflexive, symmetric, and transitive and, hence, an equivalence relation on \(\mathcal{L}\text{.}\)