1. Algebra — Relations and Functions

Equivalence class

An equivalence class is a subset of a set partitioned by an equivalence relation, grouping elements that are mutually related under the given property. This topic covers equivalence classes and their disjoint partitions.

For: UP PGT Mathematics UP TGT Mathematics DSSSB PGT / TGT KVS / NVS PGT LT Grade

📖 Topic progress

○ Mark as complete

Definition and statement

Fundamental Partition Theorem of Equivalence Relations

Let $R$ be an equivalence relation on a non-empty set $A$. For any $a \in A$, the equivalence class containing $a$, denoted by $[a]$ or $\bar{a}$, is defined as $[a] = \{x \in A : (x, a) \in R\}$. Then: (1) $a \in [a]$ for all $a \in A$, (2) $[a] = [b] \iff (a, b) \in R$, and (3) For any two equivalence classes $[a]$ and $[b]$, either $[a] = [b]$ or $[a] \cap [b] = \emptyset.

📐 Geometric Interpretation

Geometrically, an equivalence relation partitions the entire space $A$ into a collection of mutually disjoint, non-empty subsets whose union equals $A$. Each equivalence class acts as a distinct geometric fiber or leaf of the partition.

⚙️ Algebraic & Structural Meaning

Algebraically, it establishes the fundamental correspondence between equivalence relations on a set and partitions of that set, forming the cornerstone for constructing quotient structures such as quotient groups and residue rings.

Conditions and hypotheses

Check each condition and what changes when it is omitted:

Hypothesis / Condition	Domain / Interval	Necessity	What Fails If Condition Dropped
Reflexivity on $A$	`Domain set $A$`	Strictly Mandatory / Necessary	If reflexivity fails, no element is guaranteed to belong to its own equivalence class, destroying the covering property of the partition.
Symmetry on $A$	`Domain set $A$`	Strictly Mandatory	If symmetry fails, mutual relatedness is lost, meaning $x \in [y]$ does not imply $y \in [x]$, violating the equality condition of classes.
Transitivity on $A$	`Domain set $A$`	Essential for partition disjointness	If transitivity fails, intersecting equivalence classes may not be identical, ruining the mutually disjoint partition structure.

Useful results and shortcuts

Use these identities and results when their conditions apply:

Counting Equivalence Classes under Congruence Modulo $n$

$$|A / R| = n \text{ for } R = \{(x,y) \in \mathbb{Z} \times \mathbb{Z} : x \equiv y \pmod n\}$$

Rule: The number of distinct equivalence classes for congruence modulo $n$ on integers is exactly $n$, represented by $[0], [1], [2], \dots, [n-1].

Size of Equivalence Classes for Finite Uniform Relations

$$|[a]| = \frac{|A|}{\text{Number of disjoint classes}} \text{ (when all classes are equal in size)}$$

Rule: In symmetric finite structures, if each class has equal cardinality, total elements divided by class size yields the partition count.

Application: Frequently asked in DSSSB PGT Mathematics partitioning problems.

Cartesian Product Equivalence Class Rule

$$[(a,b)]_{R_1 \times R_2} = [a]_{R_1} \times [b]_{R_2}$$

Rule: The equivalence class of an ordered pair under a product relation is the Cartesian product of the individual equivalence classes.

Matrix Rank / Kernel Equivalence

$$x \sim y \iff f(x) = f(y)$$

Rule: Any equivalence relation is induced by a mapping; the equivalence classes are precisely the level sets (fibers) $f^{-1}(\{y\})$ of the function.

Application: Crucial conceptual shortcut for theoretical assertions in UP PGT.

Divisibility Equivalence on Integers

$$[a] = \{x \in \mathbb{Z} : x - a = k \cdot n\}$$

Rule: Instantly identify that elements within the same class differ by a multiple of the relation modulus.

Application: Appears in LT Grade and UP TGT number theory sections.

Rapid Elimination via Reflexivity Test

$$(x, x) \notin R \implies R \text{ is not an equivalence relation}$$

Rule: Always check $(x,x) \in R$ first. If any element fails, immediately eliminate options claiming it forms equivalence classes.

Common errors and counterexamples

These examples show how a conclusion can fail when a condition is missing:

⚠️ COMMON ERROR #01

Assuming Intersection of Classes is Non-Empty

Common Pitfall: Candidates assume that if two equivalence classes share a single element, they can be partially overlapping.

Counterexample: $[a] \cap [b] \neq \emptyset \implies [a] = [b]$

Why it fails: Equivalence classes are either identical or completely disjoint; partial overlap violates the definition of a partition.

🛡️ Exam Defense: Never select options showing partial overlapping intervals or sets for equivalence classes.

⚠️ COMMON ERROR #02

Confusing the Representative Element with the Class Itself

Common Pitfall: Treating the notation $[a]$ as just the single element $a$ rather than the set of all elements related to $a$.

Counterexample: $[0] \neq 0 \text{ in } \mathbb{Z}_4 \text{; rather } [0] = \{..., -8, -4, 0, 4, 8, ...\}$

Why it fails: Leads to incorrect set-theoretic operations and cardinality calculations.

🛡️ Exam Defense: Always expand $[a]$ as a set builder notation \{x : (x,a) \in R\} during tricky problems.

Comparison

Concept / Theorem	Hypotheses / Assumptions	Key Formula / Outcome	Geometric Meaning	Exam Identification Clue
Equivalence Relation	Reflexive, Symmetric, Transitive	$R \subset A \times A$	Partitioning into fibers	Keywords: 'mod n', 'congruence', 'same remainder'
Equivalence Class	$a \in A, R$ is equivalence	$[a] = \{x : (x,a) \in R\}$	Disjoint constituent block	Asked as 'Find [2] in Z_5'
Quotient Set	Partition of set $A$ by $R$	$A/R = \{[a] : a \in A\}$	Space of all disjoint blocks	Exams ask for cardinality of $A/R$
Partial Order Relation	Reflexive, Antisymmetric, Transitive	Poset $(A, \le)$	Hasse diagram / hierarchy	Keywords: 'divides', 'subset inclusion'

Solved examples

Each problem includes a full solution and a shorter method:

CANONICAL PROBLEM 01 Dual-Method Breakdown

Let $R$ be the equivalence relation defined on the set of integers $\mathbb{Z}$ by $a \, R \, b \iff 3 \text{ divides } (a - b)$. Find the equivalence class $[1].$

(A) $\{3k : k \in \mathbb{Z}\}$(B) $\{3k + 1 : k \in \mathbb{Z}\}$(C) $\{3k + 2 : k \in \mathbb{Z}\}$(D) $\mathbb{Z}$

📚 Method A: Formal Textbook Derivation

By definition, $[1] = \{x \in \mathbb{Z} : (x, 1) \in R\} = \{x \in \mathbb{Z} : 3 \text{ divides } (x - 1)\}$. Thus, $x - 1 = 3k$ for $k \in \mathbb{Z}$, which implies $x = 3k + 1$.

⚡ Method B: 25-Second Exam Shortcut

For congruence modulo $n$, $[r]$ is simply the set of integers of the form $nk + r$. Here $n=3, r=1$, giving $3k+1$.

💡 Tip: Identify the modulus immediately from the divisibility condition.

CANONICAL PROBLEM 02 Dual-Method Breakdown

Let $A = \{1, 2, 3, 4, 5, 6\}$. If $R = \{(x, y) \in A \times A : x \equiv y \pmod 2\}$, then the equivalence class [2] is:

(A) $\{2, 4, 6\}$(B) $\{1, 3, 5\}$(C) $\{1, 2, 3, 4, 5, 6\}$(D) $\{2\}$

📚 Method A: Formal Textbook Derivation

Check elements $y \in A$ such that $y - 2$ is divisible by 2. These are numbers having the same parity as 2 (even numbers). Thus $[2] = \{2, 4, 6\}$.

⚡ Method B: 25-Second Exam Shortcut

Congruence modulo 2 splits the set into even and odd numbers. Since 2 is even, [2] contains all even elements in $A$.

💡 Tip: Check if the set is finite; list elements if cardinality is small.

Practice questions

Choose an answer to check it and see the solution:

MCQ 1: If $R$ is an equivalence relation on a set $A$, then for any $a, b \in A$, $[a] = [b]$ if and only if:

A $(a, b) \in R$

B $(a, b) \notin R$

C $[a] \cap [b] \neq \emptyset$

D $a = b$

Derivation & Analysis:

By definition of equivalence classes, $[a] = [b] \iff a \in [b] \iff (a, b) \in R$.

MCQ 2: The number of distinct equivalence classes of congruence modulo 5 on $\mathbb{Z}$ is:

A 4

B 5

C Infinitely many

D 1

Derivation & Analysis:

Modulo $n$ arithmetic yields exactly $n$ distinct residue classes: $[0], [1], [2], [3], [4]$. Thus for $n=5$, there are 5 classes.

MCQ 3: Let $R$ be an equivalence relation on set $A$. Which of the following is always false?

A $[a] = [b]$ for some $a \neq b$

B $[a] \cap [b] = \emptyset$ for $[a] \neq [b]$

C $\bigcup_{a \in A} [a] = A$

D $[a] = \emptyset$ for some $a \in A$

Derivation & Analysis:

Since $a \in [a]$ by reflexivity, no equivalence class can be empty ($[a]$ always contains at least $a$ itself).

MCQ 4: In $\mathbb{Z}$ under the relation $a \, R \, b \iff a - b$ is even, the equivalence class $[0]$ is:

A Set of all odd integers

B Set of all even integers

C $\{0\}$

D $\mathbb{Z}$

Derivation & Analysis:

$[0] = \{x \in \mathbb{Z} : x - 0 = 2k\} = \{2k : k \in \mathbb{Z}\}$, which is the set of all even integers.

MCQ 5: Let $A = \{1, 2, 3\}$. The equivalence relation $R = \{(1,1), (2,2), (3,3), (1,2), (2,1)\}$ partitions $A$ into equivalence classes:

A $\{1\}, \{2\}, \{3\}$

B $\{1, 2\}, \{3\}$

C $\{1, 2, 3\}$

D $\{1, 3\}, \{2\}$

Derivation & Analysis:

Here $[1] = \{1, 2\}$, $[2] = \{1, 2\}$, and $[3] = \{3\}$. The distinct classes are $\{1, 2\}$ and $\{3\}$.

MCQ 6: If $R_1$ and $R_2$ are equivalence relations on a set $A$, then $R_1 \cap R_2$ is:

A Always an equivalence relation

B Never an equivalence relation

C C) Only symmetric

D Only transitive

Derivation & Analysis:

The intersection of any family of equivalence relations is always reflexive, symmetric, and transitive, hence an equivalence relation.

MCQ 7: The equivalence class $[3]$ in $\mathbb{Z}$ under $a \equiv b \pmod 4$ is given by:

A $\{4k : k \in \mathbb{Z}\}$

B $\{4k + 3 : k \in \mathbb{Z}\}$

C $\{3k : k \in \mathbb{Z}\}$

D $\{4k + 1 : k \in \mathbb{Z}\}$

Derivation & Analysis:

By formula, $[r] = \{4k + r : k \in \mathbb{Z}\}$. For $r = 3$, $[3] = \{4k + 3 : k \in \mathbb{Z}\}$.

MCQ 8: If a relation $R$ on set $A$ is symmetric and transitive, but NOT reflexive, then:

A It forms equivalence classes

B It may form equivalence classes on a subset

C It can never form a partition of $A$

D It is an equivalence relation

Derivation & Analysis:

All three properties (reflexive, symmetric, transitive) are strictly required to define equivalence classes that partition the entire set $A$.

MCQ 9: Let $f: \mathbb{R} \to \mathbb{R}$ be defined by $f(x) = x^2$. The equivalence relation defined by $x \sim y \iff f(x) = f(y)$ produces equivalence classes of the form:

A $\{x, -x\}$

B $\{x\}$

C $\{x, x^2\}$

D $\mathbb{R}$

Derivation & Analysis:

$x^2 = y^2 \iff y = \pm x$. Thus each equivalence class consists of two elements $\{x, -x\}$, except for $[0] = \{0\}$.

Q10

MCQ 10: What is the maximum possible number of equivalence classes on a set of cardinality $n$?

A $n$

B $2^n$

C $n!$

D Bell number $B_n$

Derivation & Analysis:

A partition can have at most $n$ equivalence classes (when each element forms a singleton class, corresponding to the identity relation).

Common questions

No. By the fundamental properties of equivalence relations, any two equivalence classes are either identical or completely disjoint. If they share even a single element, the transitivity and symmetry properties force the two classes to be exactly the same set.

Candidates often confuse the equivalence class $[a]$ with the single element $a$, or they fail to check reflexivity across the entire domain set, leading to false assumptions about partitions.

Master modular arithmetic shortcuts and immediately test reflexivity $(x,x) \in R$. For finite sets, quickly inspect matrix or roster representations to isolate disjoint blocks without full manual expansion.

← Previous Topic

Composite of functions

Next Topic →

Equivalence relation