1. Algebra — Relations and Functions

Transitive relation

A relation $R$ on a set $A$ is termed transitive if whenever an element is related to a second, and the second to a third, then the first is necessarily related to the third. This topic covers transitivity, along with reflexivity and symmetry,.

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 Transitive Relation

Let $A$ be a non-empty set. A relation $R$ on $A$ ($R \subset A \times A$) is said to be transitive if \forall a, b, c \in A, \quad (a, b) \in R \text{ and } (b, c) \in R \implies (a, c) \in R.

📐 Geometric Interpretation

Graphically, if directed edges exist from vertex $a$ to vertex $b$ and from vertex $b$ to vertex $c$ in the digraph of the relation, transitivity requires the presence of a direct directed edge from $a$ to $c$.

⚙️ Algebraic & Structural Meaning

Transitivity enforces hierarchical, order-like, or divisibility consistency across algebraic structures, ensuring that compositional chains do not break the underlying relational property.

Conditions and hypotheses

Check each condition and what changes when it is omitted:

Hypothesis / Condition	Domain / Interval	Necessity	What Fails If Condition Dropped
Non-empty base set $A$	`Discrete or Continuous Set $A$`	Strictly Mandatory / Necessary	If $A$ is empty (empty relation), transitivity is vacuously true, but standard non-trivial problems require a non-empty domain.
Implication Chain Verification	`Ordered pairs $(a,b) \in R \text{ and } (b,c) \in R$`	Strictly Mandatory	Failing to check all possible pairs where the second coordinate of the first pair matches the first coordinate of the second pair leads to false positives.
Vacuous Truth Condition	`Absence of $(b,c)$ for a given $(a,b)$`	Logical necessity	Assuming a relation is non-transitive simply because no chain $(a,b)$ and $(b,c)$ exists; relations with no such chains are vacuously transitive.

Useful results and shortcuts

Use these identities and results when their conditions apply:

Universal Transitivity of Equality and Inequalities

$$a = b \land b = c \implies a = c \quad (\text{Transitive})$$

Rule: Standard relations like $=$, $\le$, $\ge$, $<$, $>$, divides ($|$) on $\mathbb{Z}$, and subset ($\subseteq$) on $\mathcal{P}(S)$ are universally transitive.

Application: Directly tested in UP PGT to quickly identify equivalence or partial order relations without manual pair-checking.

Congruence Modulo $n$

$$a \equiv b \pmod n \text{ and } b \equiv c \pmod n \implies a \equiv c \pmod n$$

Rule: Congruence relations are always equivalence relations, hence transitive.

Application: Frequently asked in number theory sections of UP TGT/PGT mathematics.

Perpendicularity and Parallelism

$$L_1 \parallel L_2 \land L_2 \parallel L_3 \implies L_1 \parallel L_3 \quad (\text{Transitive})$$

Rule: Parallelism of lines is transitive, whereas perpendicularity is NOT transitive ($L_1 \perp L_2$ and $L_2 \perp L_3 \implies L_1 \parallel L_3$).

Subset Inclusion Relation

$$A \subseteq B \land B \subseteq C \implies A \subseteq C$$

Rule: Inclusion is always transitive. Strict inclusion ($A \subset B$) is also transitive.

Function Composition Transitivity

$$f: A \to B, \ g: B \to C \implies \text{ relational properties transfer}$$

Rule: Relations defined via functional equations (e.g., $f(x) = f(y)$) inherit transitivity from equality in the codomain.

Application: Advanced relation problems in UP PGT.

Rapid Elimination Trick for Non-Transitivity

$$(a,b) \in R, (b,c) \in R \text{ but } (a,c) \notin R$$

Rule: To disprove transitivity, you only need to find a single counterexample triplet $(a, b, c)$ satisfying the premise but violating the conclusion.

Common errors and counterexamples

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

⚠️ COMMON ERROR #01

The Vacuous Truth Fallacy

Common Pitfall: Candidates assume a relation with very few elements cannot be transitive.

Counterexample: R = \{(1, 2)\} \text{ on } A = \{1, 2, 3}

Why it fails: There is no pair $(b, c)$ starting with $2$. Thus, the implication $(1,2) \land (2,c) \implies (1,c)$ is vacuously true. The relation IS transitive.

🛡️ Exam Defense: Check if any chain $(a,b)$ and $(b,c)$ actually exists before declaring failure.

⚠️ COMMON ERROR #02

Mistaking Perpendicularity for Transitivity

Common Pitfall: Assuming symmetric geometric relations are automatically transitive.

Counterexample: R = \{(L_1, L_2) : L_1 \perp L_2\}

Why it fails: If $L_1 \perp L_2$ and $L_2 \perp L_3$, then $L_1$ and $L_3$ are parallel, not perpendicular. Hence $(L_1, L_3) \notin R$.

🛡️ Exam Defense: Never extrapolate symmetry to transitivity in geometric orthogonality.

Comparison

Concept / Theorem	Hypotheses / Assumptions	Key Formula / Outcome	Geometric Meaning	Exam Identification Clue
Reflexivity	\forall a \in A	(a, a) \in R	Every element relates to itself	Look for identity pairs $(x,x)$
Symmetry	(a, b) \in R	\implies (b, a) \in R	Bidirectional linkage	Look for reverse pairs
Transitivity	(a,b) \in R \land (b,c) \in R	\implies (a, c) \in R	Chain closure property	Look for bridge elimination ($b$)
Equivalence Relation	Reflexive + Symmetric + Transitive	Partitions set into disjoint equivalence classes	Complete structural symmetry	Standard UP PGT scoring item

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 real numbers $\mathbb{R}$ defined by $R = \{(a, b) : a \le b^2\}$. Examine $R$ for transitivity.

(A) Transitive(B) Not transitive(C) Symmetric but not transitive(D) Equivalence relation

📚 Method A: Formal Textbook Derivation

Step 1: Test with real numbers. Let $a = 2, b = -3, c = -1$. Step 2: Check $(2, -3)$: $2 \le (-3)^2 = 9$ (True). Step 3: Check $(-3, -1)$: $-3 \le (-1)^2 = 1$ (True). Step 4: Check $(2, -1)$: $2 \le (-1)^2 = 1$ (False). Step 5: Since $(2,-3)\in R$ and $(-3,-1)\in R$ but $(2,-1)\notin R$, $R$ is not transitive.

⚡ Method B: 25-Second Exam Shortcut

Use small integer counterexamples involving negative numbers or fractions.

💡 Tip: Inequalities involving squares or absolute values often fail transitivity.

CANONICAL PROBLEM 02 Dual-Method Breakdown

Let $R$ be the relation defined on the set $N$ of natural numbers by $xRy \iff x$ divides $y$. Then $R$ is:

(A) Reflexive and symmetric only(B) Transitive and symmetric only(C) Equivalence relation(D) Reflexive and transitive, but not symmetric

📚 Method A: Formal Textbook Derivation

Step 1: Reflexivity: $x$ divides $x$ ($\true$). Step 2: Symmetry: $2$ divides $4$, but $4$ does not divide $2$ (Not symmetric). Step 3: Transitivity: If $x$ divides $y$ and $y$ divides $z$, then $x$ divides $z$ ($\true$).

⚡ Method B: 25-Second Exam Shortcut

Divisibility relation on $\mathbb{N}$ is a classic partial order (reflexive, antisymmetric, transitive).

💡 Tip: Memorize standard order relations on $\mathbb{N}$ or $\mathbb{R}$ for instant answers.

Practice questions

Choose an answer to check it and see the solution:

MCQ 1: Which of the following relations on $\mathbb{R}$ is transitive? $R = \{(a, b) : a \ge b\}$

A $a \ge b$ and $b \ge c \implies a \ge c$

B $a \ge b$ and $b \ge c \implies a \le c$

C $a \ge b$ and $b \ge c \implies a = c$

D Not transitive

Derivation & Analysis:

Standard inequality $\ge$ is transitive over real numbers.

MCQ 2: Let $A = \{1, 2, 3\}$. The relation $R = \{(1, 2), (2, 3), (1, 3)\}$ on $A$ is:

A Reflexive

B Symmetric

C Transitive

D Equivalence

Derivation & Analysis:

Here $(1,2)$ and $(2,3)$ give $(1,3)$ which is in $R$. Thus it is transitive.

MCQ 3: The relation $R$ on the set of all lines in a plane defined by $L_1 R L_2 \iff L_1 \perp L_2$ is:

A Reflexive

B Symmetric

C Transitive

D None of these

Derivation & Analysis:

Perpendicularity is symmetric and irreflexive, but not transitive.

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

A Reflexive only

B Symmetric only

C Transitive only

D An equivalence relation

Derivation & Analysis:

Intersection of any family of equivalence relations is always an equivalence relation.

MCQ 5: The empty relation $\phi$ on a non-empty set $A$ is:

A Reflexive

B Symmetric and transitive

C Symmetric only

D Not transitive

Derivation & Analysis:

The empty relation satisfies symmetry and transitivity vacuously.

MCQ 6: Let $R = \{(a, b) : a - b \text{ is an integer}\}$ on $\mathbb{R}$. $R$ is:

A Transitive only

B Reflexive and symmetric only

C Equivalence relation

D None of these

Derivation & Analysis:

Difference of integers is reflexive, symmetric, and transitive.

MCQ 7: The universal relation on a non-empty set $A$ is:

A Always transitive

B Never transitive

C Transitive only if $|A| = 1$

D Symmetric only

Derivation & Analysis:

The universal relation $A \times A$ contains all ordered pairs, hence trivially transitive.

MCQ 8: Let $R = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)\}$ on $A = \{1, 2, 3\}$. $R$ is:

A Not transitive

B Equivalence relation

C Transitive but not symmetric

D Reflexive only

Derivation & Analysis:

Checking all chain combinations reveals all conditions for an equivalence relation are satisfied.

MCQ 9: If a relation $R$ is both symmetric and transitive, then it:

A Is always reflexive

B Is an equivalence relation

C May not be reflexive

D Is empty

Derivation & Analysis:

Symmetry and transitivity do not automatically guarantee reflexivity unless the domain condition is met.

Q10

MCQ 10: In a set of 5 elements, the maximum number of ordered pairs in a transitive relation can be:

A 25

B 20

C 15

D 10

Derivation & Analysis:

The universal relation contains $5^2 = 25$ pairs, which is transitive.

Common questions

Yes. For a set with one element, all required implications are trivially or vacuously satisfied, making the relation transitive.

Forgetting the vacuous truth condition. If $(a, b) \in R$ exists but there is no $c$ such that $(b, c) \in R$, the condition is automatically satisfied without failure.

Immediately test small integer values, fractions, or negative numbers to find a counterexample where $(a,b) \in R$ and $(b,c) \in R$, but $(a,c) \notin R$.

← Previous Topic

Symmetric relation

Next Topic →

Principle of mathematical induction