Equivalence Relation in Discrete Mathematics

We all have learned about fractions in our childhood and if we have then it is not unknown to us that every fraction has many equivalent forms. Let us take an example, 1/2, 2/4, 3/6, -1/-2, -3/-6, 15/30

The fractions given above may all look different from each other or maybe referred to by different names but actually they are all equal and the same number.

This unique idea of classifying them together that “look different but are actually the same” is the fundamental idea of equivalence relation. Distribution of a set S is either a finite or infinite collection of a nonempty and mutually disjoint subset whose union is S.

A relation R on a set A can be considered as an equivalence relation only if the relation R will be reflexive, along with being symmetric, and transitive. But what does reflexive, symmetric, and transitive mean?

Reflexive: A relation is supposed to be reflexive, if (a, a) ∈ R, for every a ∈ A.

Symmetric: A relation is supposed to be symmetric, if (a, b) ∈ R, then (b, a) ∈ R.

Transitive: A relation is supposed to be transitive if (a, b) ∈ R and (b, c) ∈ R, then (a, c) ∈ R.

Solved Examples of Equivalence Relation 

1. Let us consider that F is a relation on the set R real numbers that are defined by xFy on a condition if x-y is an integer. Prove F as an equivalence relation on R.

Reflexive property: Assume that x belongs to R, and, x – x = 0 which is an integer. Thus, xFx.

Symmetric Property: Assume that x and y belongs to R and xFy. And x – y is an integer. Therefore, y – x = – ( x – y), y – x is too an integer. Thus, yFx.

Transitive Property: Assume that x and y belongs to R, xFy, and yFz. And both x-y and y-z are integers. So, according to the transitive property, ( x – y ) + ( y – z ) = x – z is also an integer. Therefore, xFz.

Hence, R is an equivalence relation on R.

2. How do we know that the relation R is an equivalence relation in the set A = { 1, 2, 3, 4, 5 } given by the relation R = { (a, b):|a-b| is even }.

Here, R = { (a, b):|a-b| is even }. And a, b belongs to A

Reflexive Property : From the given relation,

|a – a| = | 0 |=0

And 0 is always even.

Thus, |a-a| is even

Therefore, (a, a) belongs to R

Hence R is Reflexive

Symmetric Property : From the given relation,

|a – b| = |b – a|

We know that |a – b| = |-(b – a)|= |b – a|

Hence |a – b| is even,

Then |b – a| is also even.

Therefore, if (a, b) ∈ R, then (b, a) belongs to R

Hence R is symmetric

Transitive Property : If |a-b| is even, then (a-b) is even.

In the same way, if |b-c| is even, then (b-c) is also even.

Sum of even number is also even

So, we can write it as a-b+ b-c is even

Then, a – c is also even

So,

|a – b| and |b – c| is even , then |a-c| is even.

Therefore, if (a, b) ∈ R and (b, c) ∈ R, then (a, c) also belongs to R

Hence R is transitive. 

Connection of Equivalence Relation to other relations

• An incomplete order is a reciprocal, system can be classified, and linear relation. 

• Equality is a complete order as well as an equivalence relation.

• Equality is also the only inductive, symmetric, and antisymmetric relation on a set. 

• Equal variables in algebraic expressions can be replaced for one another, a feature not accessible for equivalence-related variables. 

• Persons inside an equivalence relation's equivalence classes can replace each other, but not people within a class.

• A rigorous incomplete order is asymmetric, irreflexive, and bidirectional. 

• A complete equivalence connection is equal and linear. Such a relationship is bidirectional if and only if it is serial, that is, if for every display style, there occurs some display style text such that asim b. As a result, an equivalence relation can be defined in a variety of ways, including symmetric, transitive, and serial.

• The ternary equivalent of the normal equivalence relation is the ternary comparability relation.

• A reliance relation or a tolerance relation is a reciprocal and symmetrical relation.

• A sequence is both bidirectional and inductive.

• An equivalence relation whose domain X is also the bottom set for an algebraic form and which satisfies the extra form is known as a congruence relation. In general, congruence relations serve as homomorphism kernels, and a structure's quotient can be created using a congruence relation. Congruence relations have an alternate representation as structural components of the form on which they are established in many crucial circumstances.

• Although the opposite assertion holds exclusively in classical mathematics because it is identical to the law of excluded middle, any equivalence connection is the negative of an apartness relationship.

• Every recursive and left or right Riemann connection is also an interval estimate.

A Few key points to remember

i) Equations with similar solutions or bases are known as equivalent equations.

ii) An analogous equation is created by adding or subtracting the identical number or phrase to both sides of an equation.

iii) An analogous equation is created by multiplying or dividing both sides of an equation by the same non-zero value.

Conclusion

The primary focus lies in conceptual understanding and one who has mastered that art is sure to succeed. Practice sums after going through the concept for a better understanding of the topic. Equivalence relations can be a tricky affair if not practiced again and again.