Equivalence Relations

Section 7.2 Equivalence Relations

Beginning Activity Beginning Activity 1: Properties of Relations
A4 US

In previous mathematics courses, we have worked with the equality relation. For example, let

R

be the relation on

Z

defined as follows: For all

a, b \in Z,

a R b

if and only if

a = b .

We know this equality relation on

Z

has the following properties:

For each $a \in Z,$ $a = a$ and so $a R a .$
For all $a, b \in Z,$ if $a = b,$ then $b = a .$ That is, if $a R b,$ then $b R a .$
For all $a, b, c \in Z,$ if $a = b$ and $b = c,$ then $a = c .$ That is, if $a R b$ and $b R c,$ then $a R c .$

🔗

In mathematics, when something satisfies certain properties, we often ask if other things satisfy the same properties. Before investigating this, we will give names to these properties.

🔗

Definition.

Let $A$ be a nonempty set and let $R$ be a relation on $A .$

The relation $R$ is reflexive on $A$ provided that for each $x \in A,$ $x R x$ or, equivalently, $(x, x) \in R .$
The relation $R$ is symmetric provided that for every $x, y \in A,$ if $x R y,$ then $y R x$ or, equivalently, for every $x, y \in A,$ if $(x, y) \in R,$ then $(y, x) \in R .$
The relation $R$ is transitive provided that for every $x, y, z \in A,$ if $x R y$ and $y R z,$ then $x R z$ or, equivalently, for every $x, y, z \in A,$ if $(x, y) \in R$ and $(y, z) \in R,$ then $(x, z) \in R .$

🔗

Before exploring examples, for each of these properties, it is a good idea to understand what it means to say that a relation does not satisfy the property. So let

A

be a nonempty set and let

R

be a relation on

A .

🔗

1.

Carefully explain what it means to say that the relation $R$ is not reflexive on the set $A .$

🔗

2.

Carefully explain what it means to say that the relation $R$ is not symmetric.

🔗

3.

Carefully explain what it means to say that the relation $R$ is not transitive.

🔗

To illustrate these properties, we let

A = {1, 2, 3, 4}

and define the relations

R

and

T

A

as follows:

\begin{aligned} R & = {(1, 1), (2, 2), (3, 3), (4, 4), (1, 3), (3, 2)} \\ T & = {(1, 1), (1, 4), (2, 4), (4, 1), (4, 2)} \end{aligned}

🔗

4.

Draw a directed graph for the relation $R .$ Then explain why the relation $R$ is reflexive on $A,$ is not symmetric, and is not transitive.

🔗

5.

Draw a directed graph for the relation $T .$ Is the relation $T$ reflexive on $A ?$ Is the relation $T$ symmetric? Is the relation $T$ transitive? Explain.

🔗

Beginning Activity Beginning Activity 2: Review of Congruence Modulo $n$
A4 US

🔗

1.

Let $a, b \in Z$ and let $n \in N .$ On Definition of Section 3.1, we defined what it means to say that $a$ is congruent to $b$ modulo $n .$ Write this definition and state two different conditions that are equivalent to the definition.

🔗

2.

Explain why congruence modulo $n$ is a relation on $Z .$

🔗

3.

Carefully review Theorem 3.36 and the proofs given on Theorem 3.36 of Section 3.5. In terms of the properties of relations introduced in Beginning Activity 1, what does this theorem say about the relation of congruence modulo $n$ on the integers?

🔗

4.

Write a complete statement of Theorem 3.37 and Corollary 3.38.

🔗

5.

Write a proof of the symmetric property for congruence modulo $n .$ That is, prove the following:

Let $a, b \in Z$ and let $n \in N .$ If $a \equiv b (\mod n),$ then $b \equiv a (\mod n) .$

🔗

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 .

The relation $R$ is reflexive on $A$ provided that for each $x \in A,$ $x R x$ or, equivalently, $(x, x) \in R .$ 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,$ if $x R y,$ then $y R x$ or, equivalently, for every $x, y \in A,$ if $(x, y) \in R,$ then $(y, x) \in R .$ 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,$ if $x R y$ and $y R z,$ then $x R z$ or, equivalently, for every $x, y, z \in A,$ if $(x, y) \in R$ and $(y, z) \in R,$ then $(x, z) \in R .$ 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,$ there would be a directed edge from $x$ to $z .$

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,$ there would be loops at $x$ and $y .$ These two situations are illustrated as follows:

🔗

Progress Check 7.11. Properties of Relations.

Let $A = {a, b, c, d}$ and let $R$ be the following relation on $A :$

R = {(a, a), (b, b), (a, c), (c, a), (b, d), (d, b)} .

Draw a directed graph for the relation $R$ and then determine if the relation $R$ is reflexive on $A,$ if the relation $R$ is symmetric, and if the relation $R$ is transitive.

Solution.

The relation $R :$

Is not reflexive since $(c, c) \notin R$ and $(d, d) \notin R .$
Is symmetric.
Is not transitive. For example, $(c, a) \in R,$ $(a, c) \in R,$ but $(c, c) \notin R .$

🔗

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.

🔗

Definition.

Let $A$ be a nonempty set. A relation $\sim$ on the set $A$ is an equivalence relation provided that $\sim$ is reflexive, symmetric, and transitive. For $a, b \in A,$ if $\sim$ is an equivalence relation on $A$ and $a \sim b,$ we say that $a$ is equivalent to $b$ .

🔗

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,

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,

x R x .

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.

🔗

Example 7.12. A Relation that Is Not an Equivalence Relation.

Let $M$ be the relation on $Z$ defined as follows:

For $a, b \in Z,$ $a M b$ if and only if $a$ is a multiple of $b .$

So $a M b$ if and only if there exists a $k \in Z$ such that $a = b k .$

The relation $M$ is reflexive on $Z$ since for each $x \in Z,$ $x = x \cdot 1$ and, hence, $x M x .$
Notice that $4 M 2,$ but $2 ⧸ M 4 .$ So there exist integers $x$ and $y$ such that $x M y$ but $y ⧸ M x .$ Hence, the relation $M$ is not symmetric.
Now assume that $x M y$ and $y M z .$ Then there exist integers $p$ and $q$ such that

$x = y p and y = z q .$

Using the second equation to make a substitution in the first equation, we see that $x = z (p q) .$ Since $p q \in Z,$ we have shown that $x$ is a multiple of $z$ and hence $x M z .$ Therefore, $M$ is a transitive relation.

🔗

The relation

M

is reflexive on

Z

and is transitive, but since

M

is not symmetric, it is not an equivalence relation on

Z .

🔗

Progress Check 7.13. A Relation that Is an Equivalence Relation.

Define the relation $\sim$ on $Q$ as follows: For all $a, b \in Q,$ $a \sim b$ if and only if $a - b \in Z .$ For example:

$\frac{3}{4} \sim \frac{7}{4}$ since $\frac{3}{4} - \frac{7}{4} = - 1$ and $- 1 \in Z .$
$\frac{3}{4} ≁ \frac{1}{2}$ since $\frac{3}{4} - \frac{1}{2} = \frac{1}{4}$ and $\frac{1}{4} \notin Z .$

To prove that $\sim$ is reflexive on $Q,$ we note that for all $a \in Q,$ $a - a = 0 .$ Since $0 \in Z,$ we conclude that $a \sim a .$ Now prove that the relation $\sim$ is symmetric and transitive, and hence, that $\sim$ is an equivalence relation on $Q .$

Solution.

Proof that the relation $\sim$ is symmetric: Let $a, b \in Q$ and assume that $a \sim b .$ This means that $a - b \in Z .$ Therefore, $- (a - b) \in Z$ and this means that $b - a \in Z,$ and hence, $b \sim a .$

Proof that the relation $\sim$ is transitive: Let $a, b, c \in Q$ and assume that $a \sim b$ and $b \sim c .$ This means that $a - b \in Z$ and that $b - c \in Z .$ Therefore, $((a - b) + (b - c)) \in Z$ and this means that $a - c \in Z,$ and hence, $a \sim c .$

🔗

Subsection Congruence Modulo $n$

🔗

One of the important equivalence relations we will study in detail is that of congruence modulo

n .

We reviewed this relation in Beginning Activity 2.

🔗

Theorem 3.36 tells us that congruence modulo

n

is an equivalence relation on

Z .

Recall that by the Division Algorithm, if

a \in Z,

then there exist unique integers

q

and

r

such that

a = n q + r and 0 \leq r < n .

🔗

Theorem 3.37 and Corollary 3.38 then tell us that

a \equiv r (\mod n) .

That is,

a

is congruent modulo

n

to its remainder

r

when it is divided by

n .

When we use the term “remainder” in this context, we always mean the remainder

r

with

0 \leq r < n

that is guaranteed by the Division Algorithm. We can use this idea to prove the following theorem.

🔗

Theorem 7.14.

Let $n \in N$ and let $a, b \in Z .$ Then $a \equiv b (\mod n)$ if and only if $a$ and $b$ have the same remainder when divided by $n .$

🔗

Proof.

Let $n \in N$ and let $a, b \in Z .$ We will first prove that if $a$ and $b$ have the same remainder when divided by $n,$ then $a \equiv b (\mod n) .$ So assume that $a$ and $b$ have the same remainder when divided by $n,$ and let $r$ be this common remainder. Then, by Theorem 3.37,

a \equiv r (\mod n) and b \equiv r (\mod n) .

Since congruence modulo $n$ is an equivalence relation, it is a symmetric relation. Hence, since $b \equiv r (\mod n),$ we can conclude that $r \equiv b (\mod n) .$ Combining this with the fact that $a \equiv r (\mod n),$ we now have

a \equiv r (\mod n) and r \equiv b (\mod n) .

We can now use the transitive property to conclude that $a \equiv b (\mod n) .$ This proves that if $a$ and $b$ have the same remainder when divided by $n,$ then $a \equiv b (\mod n) .$

We will now prove that if $a \equiv b (\mod n),$ then $a$ and $b$ have the same remainder when divided by $n .$ Assume that $a \equiv b (\mod n),$ and let $r$ be the least nonnegative remainder when $b$ is divided by $n .$ Then $0 \leq r < n$ and, by Theorem 3.37,

b \equiv r (\mod n) .

Now, using the facts that $a \equiv b (\mod n)$ and $b \equiv r (\mod n),$ we can use the transitive property to conclude that

a \equiv r (\mod n) .

This means that there exists an integer $q$ such that $a - r = n q$ or that

a = n q + r .

Since we already know that $0 \leq r < n,$ the last equation tells us that $r$ is the least nonnegative remainder when $a$ is divided by $n .$ Hence we have proven that if $a \equiv b (\mod n),$ then $a$ and $b$ have the same remainder when divided by $n .$

🔗

Subsection Examples of Other Equivalence Relations

The relation $\sim$ on $Q$ from Progress Check 7.13 is an equivalence relation.
Let $A$ be a nonempty set. The equality relation on $A$ is an equivalence relation. This relation is also called the identity relation on $A$ and is denoted by $I_{A},$ where

$I_{A} = {(x, x) ∣ x \in A} .$
Define the relation $\sim$ on $R$ as follows:
For $a, b \in R,$ $a \sim b$ if and only if there exists an integer $k$ such that $a - b = 2 k π .$

We will prove that the relation $\sim$ is an equivalence relation on $R .$ The relation $\sim$ is reflexive on $R$ since for each $a \in R,$ $a - a = 0 = 2 \cdot 0 \cdot π .$

Now, let $a, b \in R$ and assume that $a \sim b .$ We will prove that $b \sim a .$ Since $a \sim b,$ there exists an integer $k$ such that

$a - b = 2 k π .$

By multiplying both sides of this equation by $- 1,$ we obtain

$\begin{aligned} (- 1) (a - b) & = (- 1) (2 k π) \\ b = a & = 2 (- k) π . \end{aligned}$

Since $- k \in Z,$ the last equation proves that $b \sim a .$ Hence, we have proven that if $a \sim b,$ then $b \sim a$ and, therefore, the relation $\sim$ is symmetric.

To prove transitivity, let $a, b, c \in R$ and assume that $a \sim b$ and $b \sim c .$ We will prove that $a \sim c .$ Now, there exist integers $k$ and $n$ such that

$a - b = 2 k π and b - c = 2 n π .$

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

$\begin{aligned} (a - b) + (b - c) & = 2 k π + 2 n π \\ a - c & = 2 (k + n) π \end{aligned}$

By the closure properties of the integers, $k + n \in Z .$ 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 $R .$ This equivalence relation is important in trigonometry. If $a \sim b,$ then there exists an integer $k$ such that $a - b = 2 k π$ and, hence, $a = b + k (2 π) .$ Since the sine and cosine functions are periodic with a period of $2 π,$ we see that

$\begin{aligned} \sin a & = \sin (b + k (2 π)) = \sin b, and \\ \cos a & = \cos (b + k (2 π)) = \cos b . \end{aligned}$

Therefore, when $a \sim b,$ each of the trigonometric functions have the same value at $a$ and $b .$
For an example from Euclidean geometry, we define a relation $P$ on the set $L$ of all lines in the plane as follows:
For $l_{1}, l_{2} \in L,$ $l_{1} P l_{2}$ if and only if $l_{1}$ is parallel to $l_{2}$ or $l_{1} = l_{2} .$
We added the second condition to the definition of $P$ to ensure that $P$ is reflexive on $L .$ Theorems from Euclidean geometry tell us that if $l_{1}$ is parallel to $l_{2},$ then $l_{2}$ is parallel to $l_{1},$ and if $l_{1}$ is parallel to $l_{2}$ and $l_{2}$ is parallel to $l_{3},$ then $l_{1}$ is parallel to $l_{3} .$ (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 $L .$

🔗

Progress Check 7.15. Another Equivalence Relation.

Let $U$ be a finite, nonempty set and let $P (U)$ be the power set of $U .$ Recall that $P (U)$ consists of all subsets of $U .$ (See Definition.) Define the relation $\approx$ on $P (U)$ as follows:

For $A, B \in P (U),$ $A \approx B$ if and only if $card (A) = card (B) .$

For the definition of the cardinality of a finite set, see Definition. This relation states that two subsets of

U

are equivalent provided that they have the same number of elements. Prove that

\approx

is an equivalence relation on the power set

P (U) .

Solution.

The relation $\approx$ is reflexive on $P (U)$ since for all $A \in P (U),$ $card (A) = card (A) .$

The relation $\approx$ is symmetric since for all $A, B \in P (U),$ if $card (A) = card (B),$ then using the fact that equality on $Z$ is symmetric, we conclude that $card (B) = card (A) .$ That is, if $A$ has the same number of elements as $B,$ then $B$ has the same number of elements as $A .$

The relation $\approx$ is transitive since for all $A, B, C \in P (U),$ if $card (A) = card (B)$ and $card (B) = card (C),$ then using the fact that equality on $Z$ is transitive, we conclude that $card (A) = card (C) .$ That is, if $A$ and $B$ have the same number of elements and $B$ and $C$ have the same number of elements, then $A$ and $C$ have the same number of elements.

Therefore, the relation $\approx$ is an equivalence relation on $P (U) .$

🔗

Exercises Exercises

🔗

1.

Let $A = {a, b}$ and let $R = {(a, b)} .$ Is $R$ an equivalence relation on $A ?$ If not, is $R$ reflexive, symmetric, or transitive? Justify all conclusions.

Answer.

The relation $R$ is not reflexive on $A$ and is not symmetric. However, it is transitive since the conditional statement “For all $x, y, z \in A,$ if $x R y$ and $y R z,$ then $x R z$ ” is a true conditional statement since the hypothesis will always be false.

🔗

2.

Let $A = {a, b, c} .$ For each of the following, draw a directed graph that represents a relation with the specified properties.

🔗

(a)

A relation on $A$ that is symmetric but not transitive

🔗

(b)

A relation on $A$ that is transitive but not symmetric

🔗

(c)

A relation on $A$ that is symmetric and transitive but not reflexive on $A$

🔗

(d)

A relation on $A$ that is not reflexive on $A,$ is not symmetric, and is not transitive

🔗

(e)

A relation on $A,$ other than the identity relation, that is an equivalence relation on $A$

🔗

3.

Let $A = {1, 2, 3, 4, 5} .$ The identity relation on $A$ is

I_{A} = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)} .

Determine an equivalence relation on $A$ that is different from $I_{A}$ or explain why this is not possible.

Answer.

There are many possible equivalence relations on this set. Perhaps one of the easier ways to determine one is to first decide what elements will be equivalent. For example, suppose we say that we want 1 and 2 to be equivalent (and of course, all elements will be equivalent to themselves). So if we use the symbol $\sim$ for the equivalence relation, then we need $1 \sim 2$ and $2 \sim 1 .$ Using set notation, we can write this equivalence relation as

{(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (1, 2), (2, 1)} .

🔗

4.

Let $R = {(x, y) \in R \times R ∣ | x | + | y | = 4} .$ Then $R$ is a relation on $R .$ Is $R$ an equivalence relation on $R ?$ If not, is $R$ reflexive, symmetric, or transitive? Justify all conclusions.

Answer.

The relation $R$ is not reflexive on $A .$ For example, $(4, 4) \notin R .$ The relation $R$ is symmetric. If $(a, b) \in R,$ then $| a | + | b | = 4 .$ Therefore, $| b | + | a | = 4,$ and hence, $(b, a) \in R .$ The relation $R$ is not transitive. For example, $(4, 0) \in R,$ $(0, 4) \in R,$ and $(4, 4) \notin R .$ The relation $R$ is not an equivalence relation.

🔗

5.

A relation $R$ is defined on $Z$ as follows: For all $a, b \in Z,$ $a R b$ if and only if $| a - b | \leq 3 .$ Is $R$ an equivalence relation on $R ?$ If not, is $R$ reflexive, symmetric, or transitive? Justify all conclusions.

🔗

6.

Let $f : R \to R$ be defined by $f (x) = x^{2} - 4$ for each $x \in R .$ Define a relation $\sim$ on $R$ as follows:

For a, b \in R, a \sim b if and only if f (a) = f (b) .

🔗

(a)

Is the relation $\sim$ an equivalence relation on $R ?$ Justify your conclusion.

Answer.

The relation $\sim$ is an equivalence relation. For $a \in R,$ $a \sim a$ since $f (a) = f (a) .$ So, $\sim$ is reflexive. For $a, b \in R,$ if $a \sim b,$ then $f (a) = f (b) .$ So, $f (b) = f (a) .$ Hence, $b \sim a$ and $\sim$ is symmetric. For $a, b, c \in R,$ if $a \sim b$ and $b \sim c,$ then $f (a) = f (b)$ and $f (b) = f (c) .$ So, $f (a) = f (c) .$ Hence, $a \sim c$ and $\sim$ is transitive.

🔗

(b)

Determine all real numbers in the set $C = {x \in R ∣ x \sim 5} .$

Answer.

$C = {- 5, 5}$

🔗

7.

Repeat Exercise 6 using the function $f : R \to R$ that is defined by $f (x) = x^{2} - 3 x - 7$ for each $x \in R .$

🔗

8.

Complete the following.

🔗

(a)

Repeat Task 6.a using the function $f : R \to R$ that is defined by $f (x) = \sin x$ for each $x \in R .$

🔗

(b)

Determine all real numbers in the set $C = {x \in R ∣ x \sim π} .$

🔗

9.

Define the relation $\sim$ on $Q$ as follows: For $a, b \in Q,$ $a \sim b$ if and only if $a - b \in Z .$ In Progress Check 7.13, we showed that the relation $\sim$ is an equivalence relation on $Q .$

🔗

(a)

List four different elements of the set $C = {x \in Q ∣ x \sim \frac{5}{7}} .$

🔗

(b)

Use set builder notation (without using the symbol $\sim$ ) to specify the set $C .$

🔗

(c)

Use the roster method to specify the set $C .$

🔗

10.

Let $\sim$ and $\approx$ be relations on $Z$ defined as follows:

For $a, b \in Z,$ $a \sim b$ if and only if 2 divides $a + b .$
For $a, b \in Z,$ $a \approx b$ if and only if 3 divides $a + b .$

🔗

(a)

Is $\sim$ an equivalence relation on $Z ?$ If not, is this relation reflexive, symmetric, or transitive?

Answer.

The relation $\sim$ is an equivalence relation on $Z .$ It is reflexive since for each integer $a,$ $a + a = 2 a$ and hence, $2$ divides $a + a .$ Now let $a, b \in Z$ and assume that 2 divides $a + b .$ Since $a + b = b + a,$ 2 divides $b + a$ and hence, $\sim$ is symmetric. Finally, let $a, b, c \in Z$ and assume that $a \sim b$ and $b \sim c .$ Since 2 divides $a + b,$ $a$ and $b$ must both be odd or both be even. In the case that $a$ and $b$ are both odd, then $b \sim c$ implies that $c$ must be odd. Hence, $a + c$ is even and $a \sim c .$ A similar proof shows that if $a$ and $b$ are both even, then $a \sim c .$ Therefore, $\sim$ is transitive.

🔗

(b)

Is $\approx$ an equivalence relation on $Z ?$ If not, is this relation reflexive, symmetric, or transitive?

🔗

11.

Let $U$ be a finite, nonempty set and let $P (U)$ be the power set of $U .$ That is, $P (U)$ is the set of all subsets of $U .$ Define the relation $\sim$ on $P (U)$ as follows: For $A, B \in P (U),$ $A \sim B$ if and only if $A \cap B = \emptyset .$ That is, the ordered pair $(A, B)$ is in the relation $\sim$ if and only if $A$ and $B$ are disjoint. Is the relation $\sim$ an equivalence relation on $P (U) ?$ If not, is it reflexive, symmetric, or transitive? Justify all conclusions.

🔗

12.

Let $U$ be a nonempty set and let $P (U)$ be the power set of $U .$ That is, $P (U)$ is the set of all subsets of $U .$ For $A$ and $B$ in $P (U),$ define $A \sim B$ to mean that there exists a bijection $f : A \to B .$ Prove that $\sim$ is an equivalence relation on $P (U) .$

Use results from Section 6.4 and Section 6.5.

🔗

13.

Let $\sim$ and $\approx$ be relations on $Z$ defined as follows:

For $a, b \in Z,$ $a \sim b$ if and only if $2 a + 3 b \equiv 0 (\mod 5) .$
For $a, b \in Z,$ $a \approx b$ if and only if $a + 3 b \equiv 0 (\mod 5) .$

🔗

(a)

Is $\sim$ an equivalence relation on $Z ?$ If not, is this relation reflexive, symmetric, or transitive?

🔗

(b)

Is $\approx$ an equivalence relation on $Z ?$ If not, is this relation reflexive, symmetric, or transitive?

🔗

14.

Let $\sim$ and $\approx$ be relations on $R$ defined as follows:

For $x, y \in R,$ $x \sim y$ if and only if $x y \geq 0 .$
For $x, y \in R,$ $x \approx y$ if and only if $x y \leq 0 .$

🔗

(a)

Is $\sim$ an equivalence relation on $R ?$ If not, is this relation reflexive, symmetric, or transitive?

🔗

(b)

Is $\approx$ an equivalence relation on $R ?$ If not, is this relation reflexive, symmetric, or transitive?

🔗

15.

Define the relation $\approx$ on $R \times R$ as follows: For $(a, b), (c, d) \in R \times R,$ $(a, b) \approx (c, d)$ if and only if $a^{2} + b^{2} = c^{2} + d^{2} .$

🔗

(a)

Prove that $\approx$ is an equivalence relation on $R \times R .$

🔗

(b)

List four different elements of the set

C = {(x, y) \in R \times R ∣ (x, y) \approx (4, 3)} .

🔗

(c)

Give a geometric description of the set $C .$

Answer.

The set $C$ is a circle of radius 5 with center at the origin.

🔗

16. Evaluation of Proofs.

See the instructions for Exercise 19 from Section 3.1.

🔗

(a)

Proposition: Let $R$ be a relation on a set $A .$ If $R$ is symmetric and transitive, then $R$ is reflexive.
Proof: Let $x, y \in A .$ If $x R y,$ then $y R x$ since $R$ is symmetric. Now, $x R y$ and $y R x,$ and since $R$ is transitive, we can conclude that $x R x .$ Therefore, $R$ is reflexive.

🔗

(b)

Proposition

Let $\sim$ be a relation on $Z$ where for all $a, b \in Z,$ $a \sim b$ if and only if $(a + 2 b) \equiv 0 (\mod 3) .$ The relation $\sim$ is an equivalence relation on $Z .$

Proof

Assume $a \sim a .$ Then $(a + 2 a) \equiv 0 (\mod 3)$ since

$(3 a) \equiv 0 (\mod 3) .$ Therefore, $\sim$ is reflexive on $Z .$ In addition, if $a \sim b,$ then $(a + 2 b) \equiv 0 (\mod 3),$ and if we multiply both sides of this congruence by 2, we get

\begin{aligned} 2 (a + 2 b) & \equiv 2 \cdot 0 (\mod 3) \\ (2 a + 4 b) & \equiv 0 (\mod 3) \\ (2 a + b) & \equiv 0 (\mod 3) \\ (b + 2 a) & \equiv 0 (\mod 3) . \end{aligned}

This means that $b \sim a$ and hence, $\sim$ is symmetric.

We now assume that $(a + 2 b) \equiv 0 (\mod 3)$ and $(b + 2 c) \equiv 0 (\mod 3) .$ By adding the corresponding sides of these two congruences, we obtain

\begin{aligned} (a + 2 b) + (b + 2 c) & \equiv 0 + 0 (\mod 3) \\ (a + 3 b + 2 c) & \equiv 0 (\mod 3) \\ (a + 2 c) & \equiv 0 (\mod 3) . \end{aligned}

Hence, the relation $\sim$ is transitive and we have proved that $\sim$ is an equivalence relation on $Z .$

🔗

Activity 43. Other Types of Relations.

In this section, we focused on the properties of a relation that are part of the definition of an equivalence relation. However, there are other properties of relations that are of importance. We will study two of these properties in this activity.

A relation $R$ on a set $A$ is a circular relation provided that for all $x,$ $y,$ and $z$ in $A,$ if $x R y$ and $y R z,$ then $z R x .$

🔗

(a)

Carefully explain what it means to say that a relation $R$ on a set $A$ is not circular.

🔗

(b)

Let $A = {1, 2, 3} .$ Draw a directed graph of a relation on $A$ that is circular and draw a directed graph of a relation on $A$ that is not circular.

🔗

(c)

Let $A = {1, 2, 3} .$ Draw a directed graph of a relation on $A$ that is circular and not transitive and draw a directed graph of a relation on $A$ that is transitive and not circular.

🔗

(d)

Prove the following proposition:

A relation $R$ on a set $A$ is an equivalence relation if and only if it is reflexive and circular.

🔗

(e)

A relation $R$ on a set $A$ is an antisymmetric relation provided that for all $x, y \in A,$ if $x R y$ and $y R x,$ then $x = y .$

Carefully explain what it means to say that a relation on a set $A$ is not antisymmetric.

🔗

(f)

Let $A = {1, 2, 3} .$ Draw a directed graph of a relation on $A$ that is antisymmetric and draw a directed graph of a relation on $A$ that is not antisymmetric.

🔗

(g)

Are the following propositions true or false? Justify all conclusions.

🔗

(i)

If a relation $R$ on a set $A$ is both symmetric and antisymmetric, then $R$ is transitive.

🔗

(ii)

If a relation $R$ on a set $A$ is both symmetric and antisymmetric, then $R$ is reflexive.

Section 7.2 Equivalence Relations

Beginning Activity Beginning Activity 1: Properties of Relations A4US

Definition.

1.

2.

3.

4.

5.

Beginning Activity Beginning Activity 2: Review of Congruence Modulo n A4US

1.

2.

3.

4.

5.

Subsection Directed Graphs and Properties of Relations

Progress Check 7.11. Properties of Relations.

Subsection Definition of an Equivalence Relation

Definition.

Example 7.12. A Relation that Is Not an Equivalence Relation.

Progress Check 7.13. A Relation that Is an Equivalence Relation.

Subsection Congruence Modulo n

Theorem 7.14.

Proof.

Subsection Examples of Other Equivalence Relations

Progress Check 7.15. Another Equivalence Relation.

Exercises Exercises

1.

2.

(a)

(b)

(c)

(d)

(e)

3.

4.

5.

6.

(a)

(b)

7.

8.

(a)

(b)

9.

(a)

(b)

(c)

10.

(a)

(b)

11.

12.

13.

(a)

(b)

14.

(a)

(b)

15.

(a)

(b)

(c)

16. Evaluation of Proofs.

(a)

(b)

Activity 43. Other Types of Relations.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(i)

(ii)

Beginning Activity Beginning Activity 1: Properties of Relations
A4 US

Beginning Activity Beginning Activity 2: Review of Congruence Modulo $n$
A4 US

Subsection Congruence Modulo $n$