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. 

 

How clear is this post?