We know that a relation is called an Equivalence Relation when it is reflexive, symmetric AND transitive on some set A. Let’s look at some examples.

Example One: Let \(a,b \in \mathbb{R}.\) Suppose we have that a is related to b (i.e. a ~ b) if \(a - b \in \mathbb{Z}.\) We want to show that our relation ~ is an equivalence relation.

First, let’s unpack what the question requires us to prove: It wants us to show that the relation ~ on set A is an equivalence relation. Hence, we need to show that ~ is reflexive, symmetric and transitive.

The relation ~ (in this case) is defined as follows: IF any two real numbers, a and b, are related THEN we know that a – b is some integer.

It’s important to note that the order in which a relation is important! Always write your equations as they’ve been given in the question to avoid confusion and mistakes

Ok, let’s prove this.

Show reflexive property:

Since \(a - a = 0 \in \mathbb{Z}\) holds for all \(a \in \mathbb{R},\) then we can contently conclude that ~ is reflexive. For instance, \(a = \pi \text { then } \pi - \pi = 0\)

Show symmetry property:

Let \(a,b \in \mathbb{R}\) such that a ~ b.

To show that ~ is symmetric, we need to show that b ~ a. We know that this means \(b - a \in \mathbb{Z}\) since that is how our relation is defined in the question.

Since we have a ~ b, then by the definition of our relation (as stated in the question), we know a – b is some integer value. Let’s label it w.

So we have \(a - b = w\) For instance, \(a = 300.5 \text { and } b = 0.5. \text { Then } w = 300 \in \mathbb{Z}\)

But \(- (a - b) = - w\) which is also an integer. So \(b - a\) is also an integer (i.e. b ~ a). This is what we wanted to prove!

So ~ is symmetric.

Show transitive property:

Let \(a,b,c \in \mathbb{R}\) such that a ~ b and b ~ c.

We need to show that ~ is transitive. To show a ~ c, we need to show that a – c is an integer.

We know that a ~ b, so \(a - b = x \in \mathbb{Z}\) and b ~ c means \(b - c = y \in \mathbb{Z}\)

We know we can add integers, so when we add \(x + y = (a-b) + (b-c) = a + (-b + b) - c = a + 0 -c = a - c\)

This is what we wanted because \(a - c\) implies a ~ c! Hence we can happily conclude that ~ is transitive!

Since ~ is reflexive, symmetric and transitive on A, then ~ is an equivalence relation on A!

Note: Plugging in values is usually useful when you’re trying to find counter-examples to disprove a statement.

Example Two: Let \(n \in \mathbb{N}.\) Show that the relation \(\equiv (mod n)\) on the set Z is reflexive, symmetric and transitive.

The first question we ask ourselves is, what are we required to prove? We must show that the relation \(\equiv\) on set Z  is an equivalence relation.

The relation (in this case) is defined as follows: IF any two natural numbers, a and b, are related THEN we know that n| (a – b). We write, IF \(a \equiv b (mod n)\) THEN \(n|(a - b).\) In this case, the integer n is some fixed value – although unknown. In other words, we can think n =10 for the entire question, and only values of  a and b can change.

Note n|(a – b) means ” n divides (a – b),” so we can find some integer k such that “nk = a – b.”

Show reflexive property:

Take integer a. Since a – a = 0, and for any integer n|0 holds true since n|0 = 0 \(\in \mathbb{Z}.\) Hence, \(a \equiv a (mod n)\) so the relation is reflexive.

Show symmetry property:

Let a and b be integers. Suppose \(a\equiv b(mod n)\)

We need to show \(b\equiv a (mod n).\) Hence we need to show that n|(b-a), i.e. we need to find proof that there exists at least one integer such that n|(b-a) holds.

Since \(a\equiv b(mod n)\) means n|(b-a), then there exists some integer k such that nk = a – b.

By multiplying all the integers by -1, we get -nk = b – a.

In other words, there exists some integer (namely -k, or -10) such that n|(b-a). So we showed that the relation is symmetric and we can write \(b \equiv a (mod n)\)

Show transitive property:

Let a, b and c be integers. Suppose \(a\equiv b(mod n) \text{ and }  b\equiv c(mod n)\)

We need to show that \(a \equiv c (mod n).\) In other words, there exists some integer such that n| (a-c).

Since \(a\equiv b(mod n) \text{ and }  b\equiv c(mod n),\) then we have n|(b − a) and n|(c − b). So we can find integers r and t for which b-a = nr and c-b = nt.

Adding these two equations, we obtain (c-b)+(b-a) = c + (-b + b) -a = c + 0 -a = c – a on the left side and the right side gives us nr + nt = n(r+t)

So we have c-a = n(r+t). We know r+t is the sum of two integers, so \(r+t \in \mathbb{Z}\). So we conclude n| (c-a), meaning \(a\equiv c(mod n)\) is transitive.

This completes the proof that ≡ is an equivalence relation.