Equivalence Relations

students, in this lesson you will learn how a special kind of relation can group objects that “belong together” in a mathematically precise way ✨. Equivalence relations are one of the most useful ideas in discrete mathematics because they help us organize information, compare objects, and build categories from raw data.

What is an equivalence relation?

In discrete mathematics, a relation connects elements of a set. An equivalence relation is a relation that behaves like the idea of “being essentially the same” in some respect.

A relation $R$ on a set $A$ is an equivalence relation if it satisfies all three properties:

Reflexive: for every $a \in A$, $aRa$.
Symmetric: for all $a,b \in A$, if $aRb$, then $bRa$.
Transitive: for all $a,b,c \in A$, if $aRb$ and $bRc$, then $aRc$.

These three properties are the whole story. If a relation has all three, it is an equivalence relation.

Think of it as a “same category” rule. If students and another student both get the same grade range, or two numbers leave the same remainder when divided by $3$, those items can be treated as equivalent in the context of that relation. 📚

Why these three properties matter

Each property has a clear job.

Reflexive

Reflexive means every element is related to itself. That makes sense for equivalence because every object should be considered equivalent to itself. For example, any number has the same remainder as itself when divided by $3$.

Symmetric

Symmetry means the relation works both ways. If $a$ is equivalent to $b$, then $b$ must be equivalent to $a$. This matches the idea of “same type” or “same group.” If two objects are equivalent, the order should not matter.

Transitive

Transitivity means equivalence passes through a chain. If $a$ is equivalent to $b$, and $b$ is equivalent to $c$, then $a$ must be equivalent to $c$. Without transitivity, a relation would not reliably group objects together.

These three properties together make equivalence relations powerful enough to create partitions of a set, which means splitting the set into non-overlapping groups. Each item belongs to exactly one group.

Example 1: Congruence modulo $n$

One of the most famous equivalence relations is congruence modulo $n$.

For integers, we say $a \equiv b \pmod{n}$ if $n$ divides $a-b$.

This means $a$ and $b$ leave the same remainder when divided by $n$.

Let’s use $n=3$.

$7 \equiv 1 \pmod{3}$ because $7-1=6$, and $3$ divides $6$.
$10 \equiv 4 \pmod{3}$ because $10-4=6$, and $3$ divides $6$.
So $7 \equiv 10 \pmod{3}$, since both have remainder $1$.

Why is this an equivalence relation?

Reflexive: $a-a=0$, and $n$ divides $0$.
Symmetric: if $n$ divides $a-b$, then it also divides $-(a-b)=b-a$.
Transitive: if $n$ divides $a-b$ and $n$ divides $b-c$, then $n$ divides $(a-b)+(b-c)=a-c$.

So congruence modulo $n$ is an equivalence relation. This is very important in number theory and computer science because it organizes integers into remainder classes. 🔢

Example 2: Same birthday month

Suppose the set $A$ is a group of students, and we define a relation $R$ by

$$aRb \text{ if and only if } a \text{ and } b \text{ were born in the same month.}$$

Is this an equivalence relation?

Reflexive: every student was born in the same month as themselves.
Symmetric: if student $a$ was born in the same month as student $b$, then student $b$ was born in the same month as student $a$.
Transitive: if $a$ and $b$ share a birth month, and $b$ and $c$ share a birth month, then $a$ and $c$ share that month too.

So yes, this is an equivalence relation.

The equivalence classes would be the groups of students born in each month, such as January, February, and so on. This shows how equivalence relations naturally sort a set into categories.

Equivalence classes and partitions

Once you have an equivalence relation, you can talk about equivalence classes.

If $a \in A$, the equivalence class of $a$ is the set of all elements in $A$ related to $a$:

$$[a] = \{x \in A : xRa\}$$

This set contains everything equivalent to $a$.

For congruence modulo $3$, the equivalence classes of integers are:

$$[0] = \{\ldots,-6,-3,0,3,6,\ldots\}$$

$$[1] = \{\ldots,-5,-2,1,4,7,\ldots\}$$

$$[2] = \{\ldots,-4,-1,2,5,8,\ldots\}$$

Each integer belongs to exactly one of these classes.

This leads to a major fact: equivalence relations and partitions are closely connected.

An equivalence relation divides a set into equivalence classes.
A partition divides a set into disjoint nonempty subsets.

Every equivalence relation gives a partition, and every partition defines an equivalence relation.

That connection is one reason equivalence relations are central in discrete mathematics: they turn a messy set into organized groups. 🧩

How to check whether a relation is an equivalence relation

When students is given a relation, a good strategy is to test the three properties one by one.

Step 1: Check reflexive

Ask: for every element $a$ in the set, is $aRa$ true?

If even one element fails this test, the relation is not an equivalence relation.

Step 2: Check symmetric

Ask: whenever $aRb$ is true, does $bRa$ also hold?

If you find one example where the reverse fails, the relation is not symmetric.

Step 3: Check transitive

Ask: whenever $aRb$ and $bRc$ are both true, must $aRc$ also be true?

This is often the hardest property to prove or disprove.

Example: “Has the same absolute value” on integers

Define $aRb$ if $|a|=|b|$.

Reflexive: $|a|=|a|$.
Symmetric: if $|a|=|b|$, then $|b|=|a|$.
Transitive: if $|a|=|b|$ and $|b|=|c|$, then $|a|=|c|$.

So this is an equivalence relation.

Its equivalence classes are pairs like $\{3,-3\}$, except for $0$, which forms the class $\{0\}$. This is a nice example because it shows how a relation can group numbers that look different but are equivalent under a chosen rule.

Equivalence relations inside the bigger picture of sets, functions, and relations

Equivalence relations sit right in the middle of the topic “Sets, Functions, and Relations.”

A set gives the collection of objects.
A relation tells how objects are connected.
An equivalence relation is a relation with special structure.

Functions also connect to equivalence relations. A function can create an equivalence relation by grouping inputs that produce the same output. If $f:A\to B$, then define

$$aRb \text{ if and only if } f(a)=f(b)$$

This is an equivalence relation on $A$.

Why? Because:

$f(a)=f(a)$, so it is reflexive.
If $f(a)=f(b)$, then $f(b)=f(a)$, so it is symmetric.
If $f(a)=f(b)$ and $f(b)=f(c)$, then $f(a)=f(c)$, so it is transitive.

This is very useful in mathematics because it lets us study objects by their output behavior. For example, different algebraic expressions can be equivalent if they always give the same value after simplification.

Common mistakes to avoid

A relation is not automatically an equivalence relation just because it looks familiar.

Here are some common errors:

Thinking symmetry alone is enough. It is not.
Forgetting to test every element for reflexivity.
Assuming transitivity from intuition instead of proof.
Confusing equivalence with equality. Equality is an equivalence relation, but not every equivalence relation is equality.

A relation can be useful even if it is not equality, because it may identify things that are equivalent for a specific purpose.

Conclusion

Equivalence relations are a foundational idea in discrete mathematics because they let us classify objects in a consistent way. A relation is an equivalence relation exactly when it is reflexive, symmetric, and transitive. These three properties create equivalence classes, and equivalence classes form partitions of a set.

students, when you understand equivalence relations, you also understand a major bridge between sets and relations, and you see how functions can produce meaningful groupings of data. This idea appears in modular arithmetic, sorting categories, simplifying expressions, and many other areas of mathematics and computer science. ✅

Study Notes

An equivalence relation is a relation that is reflexive, symmetric, and transitive.
Reflexive means $aRa$ for every element $a$.
Symmetric means if $aRb$, then $bRa$.
Transitive means if $aRb$ and $bRc$, then $aRc$.
Equivalence classes are defined by $[a]=\{x\in A:xRa\}$.
Equivalence relations divide a set into disjoint equivalence classes.
Every equivalence relation gives a partition of the set, and every partition gives an equivalence relation.
Congruence modulo $n$, same birth month, and same absolute value are examples of equivalence relations.
A function can define an equivalence relation by $aRb$ if and only if $f(a)=f(b)$.
Equivalence relations are important because they help organize objects into groups based on a chosen rule.