Equivalence Relation

Definition

Let $R$ be a relation on a set $A$ . Then $R$ is called an equivalence relation if it satisfies all three properties:

1. Reflexive

For every $a \in A$ , $aRa$ .

2. Symmetric

For all $a, b \in A$ , if $aRb$ , then $bRa$ .

3. Transitive

For all $a, b, c \in A$ , if $aRb$ and $bRc$ , then $aRc$ .

If a relation satisfies these three conditions, it partitions the set into disjoint equivalence classes.

Example: On the set of integers $\mathbb{Z}$ , define $a \sim b$ if $a-b$ is divisible by 5. This is an equivalence relation.

Main Content

1. Properties of an Equivalence Relation

Reflexive property

Every element must be related to itself. This means the relation includes all diagonal pairs $(a,a)$ . For example, equality on any set is reflexive because every element equals itself.

Symmetric and transitive properties

If one element is related to a second, then the second must also be related to the first; and if the first is related to the second and the second to the third, then the first must be related to the third. These conditions ensure consistency in grouping elements.

To verify whether a relation is an equivalence relation, all three properties must be checked carefully. Missing even one property means the relation is not an equivalence relation.

Example:
Let $A = \{1,2,3\}$ and define $R = \{(1,1),(2,2),(3,3),(1,2),(2,1)\}$ .

Reflexive: yes, because $(1,1),(2,2),(3,3)$ are present.
Symmetric: yes, because $(1,2)$ and $(2,1)$ both appear.
Transitive: no, because $(1,2)$ and $(2,1)$ imply $(1,1)$ , which is present, but if additional links were missing in larger sets, transitivity could fail. So this relation may still need full checking; in this small case it happens to satisfy the listed pairs, but in general transitivity must be tested thoroughly.

A common non-example is the relation “less than” on integers:

It is not reflexive because $a < a$ is false.
It is not symmetric because if $a < b$ , then $b < a$ is false.
It is transitive, but that alone is not enough.

2. Equivalence Classes and Partition of a Set

Equivalence class

For an element $a \in A$ , its equivalence class is the set of all elements related to $a$ . It is written as $[a]$ and defined as $[a] = \{x \in A \mid xRa\}.$ All elements in the same equivalence class are considered equivalent under the relation.

Partition of the set

An equivalence relation divides the set into mutually disjoint subsets called equivalence classes. Every element belongs to exactly one class. This is called a partition.

Important facts about equivalence classes:

If $aRb$ , then $[a] = [b]$ .
If $a$ is not related to $b$ , then $[a]$ and $[b]$ are disjoint.
The union of all equivalence classes is the entire set.

Example: Modulo 3 on integers
Define $a \sim b$ if $a-b$ is divisible by 3.

Then the equivalence classes are:

$[0] = \{\dots,-6,-3,0,3,6,\dots\}$
$[1] = \{\dots,-5,-2,1,4,7,\dots\}$
$[2] = \{\dots,-4,-1,2,5,8,\dots\}$

These classes form a partition of $\mathbb{Z}$ .

A simple visual grouping:

Integers
   |
   +-- Class [0]: ..., -6, -3, 0, 3, 6, ...
   +-- Class [1]: ..., -5, -2, 1, 4, 7, ...
   +-- Class [2]: ..., -4, -1, 2, 5, 8, ...

This structure is very useful because it reduces a large set into manageable groups.

3. Common Examples and Real-World Use

Equality relation

The simplest example is equality ( $=$ ) on any set. It is reflexive, symmetric, and transitive, so it is an equivalence relation. Each equivalence class contains exactly one element.

Congruence modulo $n$

For integers, $a \equiv b \pmod n$ if $n$ divides $a-b$ . This is a classic equivalence relation used in number theory and cryptography. It creates $n$ classes of integers.

Same shape / same object type

In geometry, figures may be considered equivalent if they are congruent or similar, depending on the rule chosen. In computer science, two strings may be equivalent if they have the same length or same hash value under a given comparison rule.

More examples:

On the set of all people, “has the same birth month as” is an equivalence relation.
On the set of all polygons, “has the same number of sides as” is an equivalence relation.
On the set of all rational numbers written as fractions, $\frac{a}{b} \sim \frac{c}{d}$ if $ad = bc$ . This identifies different fractions representing the same rational number, such as $\frac{1}{2}$ and $\frac{2}{4}$ .

Why these examples matter:

They show that equivalence relations are not only abstract ideas.
They are practical tools for classification.
They help in building mathematical structures from simpler relations.

Working / Process

1. Identify the set and the relation

First, clearly state the set $A$ and define the relation $R$ on it. A relation must be well-defined before checking its properties. For example, if the set is integers and the relation is “has the same remainder when divided by 4,” write it precisely as $a \sim b \iff 4 \mid (a-b)$ .

2. Verify the three properties

Check reflexivity: prove $aRa$ for every $a \in A$ .
Check symmetry: assume $aRb$ and prove $bRa$ .
Check transitivity: assume $aRb$ and $bRc$ and prove $aRc$ .
Each property usually requires a direct proof, algebraic manipulation, or logical reasoning depending on how the relation is defined.

3. Determine equivalence classes and partition

Once the relation is confirmed as an equivalence relation, find the equivalence class of a typical element. Then list all distinct classes and show that they do not overlap. This gives the partition of the set.
Example: Under modulo 2 on integers, the two classes are even and odd integers.

Advantages / Applications

Simplifies complex sets by grouping similar elements

Instead of studying every element separately, equivalence relations allow us to work with groups of equivalent elements.

Used in modular arithmetic and number theory

Congruence relations are foundational for computations involving divisibility, remainders, cryptography, and arithmetic structure.

Important in quotient structures and classifications

Equivalence relations are used to construct quotient sets, rational numbers from integer pairs, and many algebraic structures. They also appear in automata theory, geometry, and database equivalence grouping.

Summary

An equivalence relation is a relation that is reflexive, symmetric, and transitive.
It divides a set into disjoint equivalence classes.
Common examples include equality and congruence modulo $n$ .
It is widely used for classification, simplification, and building quotient structures.