1. Algebra — Relations and Functions

Equivalence relation

An equivalence relation on a non-empty set is a binary relation that satisfies reflexivity, symmetry, and transitivity, partitioning the set into disjoint equivalence classes. This topic covers equivalence relations.

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

📖 Topic progress

○ Mark as complete

Definition and statement

Definition of Equivalence Relation and Partition Theorem

Let $A$ be a non-empty set. A relation $R \subseteq A \times A$ is called an equivalence relation if and only if: (i) Reflexive: $(a, a) \in R$ $\forall a \in A$. (ii) Symmetric: $(a, b) \in R \implies (b, a) \in R$ $\forall a, b \in A$. (iii) Transitive: $((a, b) \in R \land (b, c) \in R) \implies (a, c) \in R$ $\forall a, b, c \in A$. Furthermore, every equivalence relation on $A$ induces a unique partition of $A$ into mutually disjoint equivalence classes whose union is $A$.

📐 Geometric Interpretation

Geometrically, an equivalence relation can be visualized as dividing a geometric space or grid into equivalence classes (like parallel lines or congruent geometric figures) where elements within the same partition cell are 'connected' or 'equivalent' under the given rule.

⚙️ Algebraic & Structural Meaning

Algebraically, equivalence relations provide the fundamental mechanism for constructing quotient structures, such as quotient groups ($G/H$), quotient rings, and modular integer rings ($\mathbb{Z}_n$), making them indispensable across abstract algebra.

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 set $A$	`Entire set $A$`	Strictly Mandatory	If even a single element $a \in A$ fails to relate to itself ($(a, a) \notin R$), the relation instantly fails to be an equivalence relation.
Symmetry across elements	`Ordered pairs in $A \times A$`	Strictly Mandatory	If $(a, b) \in R$ but $(b, a) \notin R$ for any pair, symmetry fails and the relation cannot be an equivalence relation.
Transitivity chain	`Triplets in $A \times A \times A$`	Strictly Mandatory	If $(a, b) \in R$ and $(b, c) \in R$ without $(a, c) \in R$, transitivity breaks, invalidating the equivalence property.

Useful results and shortcuts

Use these identities and results when their conditions apply:

Congruence Modulo $n$ Equivalence Classes

$$a \equiv b \pmod n \iff n \mid (a - b)$$

Rule: Congruence modulo $n$ on $\mathbb{Z}$ always partitions $\mathbb{Z}$ into exactly $n$ distinct equivalence classes: $[0], [1], [2], \dots, [n-1].

Application: Directly tested in UP PGT to find the number of equivalence classes or specific remainder sets.

Matrix Equality & Equivalence

$$R = \{(A, B) \in \mathcal{M}_n(\mathbb{R}) \mid B = P^{-1}AP \text{ for invertible } P\}$$

Rule: Similarity of matrices is an equivalence relation. Reflexive ($P=I$), Symmetric ($P^{-1}$), Transitive (product of invertible matrices).

Application: Frequently asked in KVS PGT and DSSSB PGT regarding algebraic structures on matrices.

Equality of Functions / Fibers

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

Rule: For any function $f: A \to B$, the relation defined by $f(x) = f(y)$ is always an equivalence relation. The equivalence classes are precisely the fibers $f^{-1}(\{b\})$.

Subgroup Cosets in Group Theory

$$a \sim b \iff a^{-1}b \in H$$

Rule: Left (or right) cosets of a subgroup $H$ in a group $G$ form equivalence classes that partition $G$ into equal-sized sets.

Application: High-frequency concept in UP PGT Higher Mathematics section.

Universal and Identity Relations

$$R_{\text{id}} = \{(a, a) \mid a \in A\}, \quad R_{\text{univ}} = A \times A$$

Rule: The identity relation $R_{\text{id}}$ is reflexive, antisymmetric, and transitive. The universal relation $R_{\text{univ}}$ is reflexive, symmetric, and transitive (hence an equivalence relation if $|A| \ge 1$).

Rapid Elimination via Counterexample to Symmetry/Transitivity

$$a \le b \implies \text{Reflexive, Transitive, NOT Symmetric}$$

Rule: Inequality relations like $\le$ or $\subset$ are partial orders (antisymmetric), never symmetric (unless set has 1 element), hence instantly eliminated as equivalence relations.

Common errors and counterexamples

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

⚠️ COMMON ERROR #01

Confusing Partial Order with Equivalence Relation

Common Pitfall: Candidates assume relations like 'less than or equal to' ($\le$) or 'subset of' ($\subseteq$) are equivalence relations because they are reflexive and transitive.

Counterexample: $a \le b$ on $\mathbb{R}$

Why it fails: While reflexive and transitive, it is antisymmetric ($a \le b$ and $b \le a \implies a = b$), not symmetric. Thus, it is a partial order, not an equivalence relation.

🛡️ Exam Defense: Check symmetry first: if $a \le b$ does not imply $b \le a$, immediately reject equivalence.

⚠️ COMMON ERROR #02

Assuming Transitivity Holds for Inequality / Divisibility Exceptions

Common Pitfall: Assuming 'is perpendicular to' or 'is brother of' satisfies transitivity.

Counterexample: $L_1 \perp L_2$ and $L_2 \perp L_3 \implies L_1 \parallel L_3$

Why it fails: Perpendicularity is symmetric and irreflexive, but completely fails transitivity because two perpendicular lines to the same line are parallel, not perpendicular.

🛡️ Exam Defense: Never assume geometric relations are transitive without testing perpendicular/parallel rules.

Comparison

Concept / Theorem	Hypotheses / Assumptions	Key Formula / Outcome	Geometric Meaning	Exam Identification Clue
Equivalence Relation	Reflexive, Symmetric, Transitive	Partition into disjoint equivalence classes	Mutually exclusive partition cells	Keywords: 'Congruence', 'Parallel', 'Equivalence class'
Partial Order Relation	Reflexive, Antisymmetric, Transitive	Hasse diagram, Poset structure	Hierarchical tree or poset ranking	Keywords: 'Divides', 'Subset', 'Less than equal to'
Equivalence Class $[a]$	Defined via equivalence relation $R$	$[a] = \{x \in A \mid (x, a) \in R\}$	Entire orbit or fiber under relation	Find elements related to a given element
Quotient Set $A/R$	Collection of all equivalence classes	$A/R = \{[a] \mid a \in A\}$	Partitioned quotient space	Count number of distinct remainders or cosets

Solved examples

Each problem includes a full solution and a shorter method:

CANONICAL PROBLEM 01 Dual-Method Breakdown

Let $R$ be a relation on the set of integers $\mathbb{Z}$ defined by $a \, R \, b \iff$ $a - b$ is divisible by $5$. Which of the following is true?

(A) $R$ is an equivalence relation(B) $R$ is reflexive and symmetric, but not transitive(C) $R$ is an equivalence relation with 3 equivalence classes(D) $R$ is a partial order relation

📚 Method A: Formal Textbook Derivation

Step 1: Reflexivity: $a - a = 0 = 5(0)$, divisible by 5. Step 2: Symmetry: If $a - b = 5k$, then $b - a = 5(-k)$. Step 3: Transitivity: If $a - b = 5k$ and $b - c = 5m$, then $a - c = 5(k+m)$. Thus $R$ is an equivalence relation.

⚡ Method B: 25-Second Exam Shortcut

Recognize congruence modulo $n$ ($n=5$) instantly as the canonical equivalence relation on $\mathbb{Z}$ with exactly 5 equivalence classes.

💡 Tip: Whenever divisibility by $n$ ($5 \mid a-b$) appears, it is always an equivalence relation with $n$ equivalence classes.

CANONICAL PROBLEM 02 Dual-Method Breakdown

Let $A = \{1, 2, 3\}$. The number of equivalence relations on $A$ containing $(1, 2)$ and $(2, 1)$ is:

(A) $1$(B) $2$(C) $3$(D) $5$

📚 Method A: Formal Textbook Derivation

Step 1: Reflexive pairs $(1,1), (2,2), (3,3)$ must be included. Step 2: Given $(1,2)$ and $(2,1)$, symmetry is satisfied. Step 3: For transitivity, we test partitions of 3 elements (Bell numbers). The partitions of $\{1,2,3\}$ are 5 total. Partitions compatible with $\{1,2\}$ being together are $\{\{1,2\}, \{3\}\}$ (gives equivalence relation with 2 classes) and the universal relation $\{\{1,2,3\}\}$. Exactly 2 relations satisfy this.

⚡ Method B: 25-Second Exam Shortcut

Use Bell number formula for total equivalence relations on $n$ elements ($B_3 = 5$). Filter those containing $\{1,2\}$, yielding 2 relations.

💡 Tip: Memorize Bell numbers: $B_1=1, B_2=2, B_3=5, B_4=15$ for counting equivalence relations on finite sets.

Practice questions

Choose an answer to check it and see the solution:

MCQ 1: Let $R$ be a relation on $\mathbb{R}$ defined by $x \, R \, y \iff x \le y$. Then $R$ is:

A Equivalence relation

B Reflexive and transitive, but not symmetric

C Symmetric and transitive, but not reflexive

D An equivalence relation if $x, y \ge 0$

Derivation & Analysis:

$x \le x$ (Reflexive). $x \le y$ and $y \le z \implies x \le z$ (Transitive). However, $x \le y$ does not imply $y \le x$ (Not symmetric). Thus it is a partial order.

MCQ 2: The total number of equivalence relations on the set $A = \{1, 2, 3\}$ is:

A 3

B 5

C 15

D 52

Derivation & Analysis:

The number of equivalence relations on a finite set of $n$ elements equals the Bell number $B_n$. For $n=3$, $B_3 = 5$ (corresponding to the 5 partitions of a 3-element set).

MCQ 3: Let $R$ be the relation on set $A = \{1, 2, 3, 4\}$ given by $R = \{(1,1), (2,2), (3,3), (4,4), (1,2), (2,1), (2,3), (3,2), (1,3), (3,1)\}$. $R$ is:

A Reflexive and symmetric only

B Equivalence relation

C Transitive only

D Reflexive and transitive only

Derivation & Analysis:

All elements have $(a,a) \in R$ (Reflexive). For every $(a,b) \in R$, $(b,a) \in R$ (Symmetric). All transitivity conditions are satisfied (the set partitions into $\{1, 2, 3\}$ and $\{4\}$). Thus $R$ is an equivalence relation.

MCQ 4: 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 An equivalence relation only if $R_1 = R_2$

D Symmetric only

Derivation & Analysis:

The intersection of any family of equivalence relations is always an equivalence relation. Reflexivity, symmetry, and transitivity are all preserved under set intersection.

MCQ 5: Let $f: X \to Y$ be a function. Define relation $R$ on $X$ by $x_1 \, R \, x_2 \iff f(x_1) = f(x_2)$. $R$ is:

A An equivalence relation

B Only symmetric

C Only transitive

D A partial order

Derivation & Analysis:

$f(x)=f(x)$ (Reflexive). If $f(x_1)=f(x_2)$ then $f(x_2)=f(x_1)$ (Symmetric). If $f(x_1)=f(x_2)$ and $f(x_2)=f(x_3)$ then $f(x_1)=f(x_3)$ (Transitive). Hence it is an equivalence relation.

MCQ 6: Which of the following relations on $\mathbb{Z}$ is NOT an equivalence relation?

A $a \, R \, b \iff a + b$ is even

B $a \, R \, b \iff a - b$ is a multiple of 3

C $a \, R \, b \iff a \ge b$

D $a \, R \, b \iff a = b$

Derivation & Analysis:

The relation $a \ge b$ is reflexive and transitive, but NOT symmetric (e.g., $3 \ge 2$ but not $2 \ge 3$). Thus it fails to be an equivalence relation.

MCQ 7: The equivalence class $[0]$ for the relation $a \equiv b \pmod 4$ on $\mathbb{Z}$ is:

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

B $\{4k \mid k \in \mathbb{Z}\}$

C $\{4k+1 \mid k \in \mathbb{Z}\}$

D $\mathbb{Z}$

Derivation & Analysis:

The equivalence class $[0]$ consists of all integers $x$ such that $x \equiv 0 \pmod 4$, meaning $4 \mid (x - 0)$, which gives the set of all multiples of 4: $\{... -8, -4, 0, 4, 8, ...\}$.

MCQ 8: Let $R$ be a relation on the set of all lines in a plane defined by $L_1 \, R \, L_2 \iff L_1$ is parallel to $L_2$. $R$ is:

A Reflexive only

B Equivalence relation

C Partial order

D Symmetric and transitive, but not reflexive

Derivation & Analysis:

Every line is parallel to itself ($L_1 \parallel L_1$). If $L_1 \parallel L_2$, then $L_2 \parallel L_1$. If $L_1 \parallel L_2$ and $L_2 \parallel L_3$, then $L_1 \parallel L_3$. Thus parallelism is an equivalence relation.

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

A $R$ is an equivalence relation

B $R$ cannot be reflexive anywhere on $A$

C $R$ might be reflexive on a subset of $A$

D $R$ is always empty

Derivation & Analysis:

A common logical trap: symmetry and transitivity alone do not guarantee reflexivity, but $R$ may be reflexive on a subset of $A$ without being reflexive on the entire set $A$.

Q10

MCQ 10: The number of equivalence classes determined by the equivalence relation $a \equiv b \pmod n$ on $\mathbb{Z}$ is:

A $n-1$

B $n$

C Infinite

D $2n$

Derivation & Analysis:

The distinct equivalence classes are $[0], [1], [2], \dots, [n-1]$, totaling exactly $n$ equivalence classes partitioning $\mathbb{Z}$.

Common questions

Generally no. The union of two equivalence relations $R_1 \cup R_2$ fails to be transitive in general, unless one relation is contained within the other.

Equivalence classes are either identical or completely disjoint. Their union covers the entire underlying set $A$, forming a precise partition.

Look for chaining properties like modular arithmetic or equality. If $(a,b) \in R$ and $(b,c) \in R$ algebraically leads to $(a,c) \in R$ via substitution or addition, transitivity holds.