What are equivalence relations?

A relation is said to be an equivalence relation if it is:

• Symmetric

• Reflexive

• Transitive

It would be useful to provide some revision of these concepts first.

Symmetric

Formally, we can define a symmetric relation as:

In other words, whenever a relation $(a,b)$ exists in a relation, then its mirror $(b,a)$ also exists.

Examples

A pretty common example is the siblings' relationship. Whenever $(a,b)$exists, i.e. $a$ is a sibling of $b$, inevitably, it's converse $(b,a)$is true as well. Let's check some other (less obvious) examples. We will assume all relations in the form of $(a,b)$:

• $a$ and $b$ hold the same (country's) passport.

• $a$ and $b$ are co-workers.

• $a$ and $b$ are two points connected by a line.

And similarly, some counter-examples:

• $a$ is a parent of $b$.

• A book is translated from the language $a$ into the language $b$. There is no guarantee of it happening otherwise as well.

Reflexive

A reflexive relation is pretty simple:

In other words, the self-relation should be defined for each set member.

Examples

While equality $a=a$ is a pretty obvious example, we have some examples, too, like:

• Division: A set having non-zero elements is reflexive, as every (non-zero) number can divide by itself.

• $\{ (0,0), (1,1), (2,2) \}$for the set $\{0,1,2 \}$.

Transitive

Similarly, transitive relation means that if $(a,b)$ and $(b,c)$ exist, then $(a,c)$ should exist as well.

Examples

Again, a number of examples like siblings, coworkers, and classmates are examples of transitive relations. Some more examples:

• If we define a line as a relationship between two points $a$ and $b$, then a transitive relationship holds for sets of triangles.

• Similarly, relational operators $(<,>,\ne,=)$are transitive. For example, if $a<b$ and $b<c$, then inevitably $a<c$.

Detailed example

After this preamble, let's return to the equivalence relations definition. We can now establish any relation as an equivalence relation if we test it for the above three attributes. Let's start with an example (taken from Rosen's Discrete Mathematics):

Symmetry

To check the symmetry of a relation, we need to iterate through the set members and make sure there exists a $(b,a)$ for every $(a,b)$.

As we quickly realize, a $(a,a)$relation doesn't need to be checked for the corresponding converse so we can skip them too. So we check $(1,3)$ and $(2,3)$ and find them to have corresponding $(b,a)$ relations as well. It is symmetric.

Wait a minute! Won't it be better to formulate this algorithm so we can apply it to a number of sets?

That was a sidenote and can be skipped. Now, we check for the reflexivity.

Reflexivity

We can quickly see that it contains all the $(a,a)$ relations from $(0,0)$ to $(3,3)$so it is reflexive. But why not try formulating its algo too.

Finally, we can check the transitive property too.

Transitivity

Is the above relation transitive? Apparently, yes, but it is not. $(1,3)$ and $(3,2)$ must lead to $(1,2)$ as well, but we cannot find it.

So, in the end, the relation we checked turns out to be not an equivalence set. We can check some other examples, too.

Set partitioning

But why do we use equivalence sets? It should be an automatic and valid question. Equivalence sets have a number of applications.

For example, equivalence relations on a set $S$, in other words equivalence classes on that set form a non-overlapping partition of $S$.

Note: Even the converse is true; If we partition a set into non-overlapping subsets, there would be some equivalence relations representing (or getting represented by) that partition.