Transitive Relation MCQs: 12 Solved Questions on Definition, Count, Properties and Closure

Transitivity is a chain-completion rule. One missing shortcut pair can invalidate a large relation, while an empty relation is transitive without containing a pair.

Transitive relations are tested through definitions, counterexamples, finite relations and closure. A decisive chain or counterexample shows why each answer follows. The wider GATE CS Exam Preparation Courses & Test Series route connects this topic to the rest of the syllabus.

Transitive relation definition and a worked counting reference

A relation R on A is transitive when, for every a,b,c in A, (a,b) in R and (b,c) in R imply (a,c) in R. Every two-step chain needs its direct shortcut. If no pairs form such a chain, there is no violation.

For A={1,2,3} and R={(1,2),(2,3),(1,3)}, the chain 1R2, 2R3 has its required shortcut 1R3, so the relation is transitive. Remove (1,3), and the chain fails. Test diagonal pairs through the same rule.

For A={1,2}, four possible ordered pairs produce 2^(2^2)=2^4=16 relations. Failure requires both (1,2) and (2,1) with at least one required loop missing. The failures are {(1,2),(2,1)}, that set plus (1,1), and that set plus (2,2). Thus 16-3=13 relations are transitive.

To audit, choose each middle element b. Match every incoming a->b with every outgoing b->c, then require a->c. One missing shortcut settles the result.

Definition and direct relation-audit MCQs 1-3

Question 1

What is a transitive relation?

• A. A relation where if a is related to b and b is related to c, then a is related to c

• B. A relation where if a is related to b and b is related to c, then a is not related to c

• C. A relation where every element is related to itself

• D. A relation where every element is related to every other element

Answer: A. A states (a,b),(b,c) in R => (a,c) in R. C is reflexivity, D is universal, and B denies the shortcut.

Question 2

Which of these relations is transitive?

• A. R = {(1, 2), (2, 3), (1, 3)}

• B. R = {(1, 2), (2, 3), (3, 1)}

• C. R = {(1, 2), (2, 1), (3, 2)}

• D. R = {(1, 2), (2, 1), (3, 3)}

Answer: A. A includes the shortcut (1,3) for 1->2->3. B lacks it; C and D contain 1->2->1 but omit (1,1).

Question 3

Set A = {a, b, c} A relation R is defined on A as R = {(a, a), (a, b), (a, c), (b, b), (b, c), (c, c)} Choose the correct option about R.

• A. R is reflexive, symmetric, transitive

• B. R is reflexive, not symmetric, not transitive

• C. R is irreflexive, not symmetric, transitive

• D. R is reflexive, not symmetric, transitive

Answer: D. The diagonal pairs make R reflexive, while (a,b) without (b,a) disproves symmetry. The chain (a,b),(b,c) has (a,c); loop-based chains reproduce existing pairs, so R is transitive.

Counterexample MCQs 4-6: OR conditions, common divisors and approximation

Question 4

A binary relation $R$ on $\mathbb{N} \times \mathbb{N}$ is defined as follows: $(a, b) R(c, d)$ if $a \leq c$ or $b \leq d$. Consider the following propositions: P: $R$ is reflexive Q: $R$ is transitive Which one of the following statements is TRUE?

• A. Both P and Q are true.

• B. P is true and Q is false.

• C. P is false and Q is true.

• D. Both P and Q are false.

Answer: B. Reflexivity follows from a<=a. Now (4,5)R(5,1) via 4<=5 and (5,1)R(2,3) via 1<=3, but the endpoint link fails because 4<=2 and 5<=3 are false. The two links used different sides of the OR.

Question 5

Let 𝑅 be the relation on the set of positive integers such that 𝑎𝑅𝑏 if and only if 𝑎 and 𝑏 are distinct and have a common divisor other than 1. Which one of the following statements about 𝑅 is true?

• A. 𝑅 is symmetric and reflexive but not transitive

• B. 𝑅 is reflexive but not symmetric and not transitive

• C. 𝑅 is transitive but not reflexive and not symmetric

• D. 𝑅 is symmetric but not reflexive and not transitive

Answer: D. Distinctness makes every aRa false, while common divisors are unchanged on reversal, so R is not reflexive but is symmetric. Also, 6R30 via 6 and 30R25 via 5, yet gcd(6,25)=1, so transitivity fails.

Question 6

Let ε = 0.0005 and let Re be the relation Re = { (x, y) ∈ R² : |x − y| < ε } Re could be interpreted as the relation "approximately equal". Re is: (A) Reflexive (B) Symmetric (C) Transitive Choose the correct answer from the options given below.

• A. (A) and (B) only true

• B. (B) and (C) only true

• C. (A) and (C) only true

• D. (A), (B) and (C) true

Answer: A. The identities |x-x|=0<0.0005 and |x-y|=|y-x| prove reflexivity and symmetry. For x=0, y=0.0004, z=0.0008, both adjacent gaps are 0.0004, but the endpoint gap is 0.0008. Transitivity fails.

Divisibility, disjointness and vacuous truth MCQs 7-9

Question 7

R is a relation defined over the set of integers Z as follows "aRb iff a is a factor of b". Then R is

• A. Reflexive, Symmetric but not Transitive

• B. Symmetric, Transitive but not Reflexive

• C. Reflexive, Transitive but not Symmetric

• D. Reflexive, Symmetric and Transitive

Answer: C. Every integer divides itself. From a|b and b|c, write b=ak, c=bm, hence c=a(km) and a|c. Symmetry fails because 2|4, but 4 does not divide 2.

Question 8

Let R be a non-empty relation on a collection of sets defined by A R B if and only if A ∩ B = ϕ. Then, (pick the true statement)

• A. R is reflexive and transitive

• B. R is symmetric and not transitive

• C. R is an equivalence relation

• D. R is not reflexive and not symmetric

Answer: B. Disjointness is symmetric because A intersection B equals B intersection A. For A={1}, B={2}, C={1}, the adjacent sets are disjoint but A intersection C={1}, disproving transitivity. Disjointness plays two different roles: Symmetric, Antisymmetric and Asymmetric Relation MCQs: 11 Solved Questions uses it to distinguish symmetry, antisymmetry and asymmetry; Q8 uses it to isolate the missing endpoint shortcut in a two-step chain.

Question 9

The binary relation S = ϕ (empty set) on set A = {1, 2, 3} is:

• A. Neither reflexive nor symmetric

• B. Symmetric and reflexive

• C. Transitive and reflexive

• D. Transitive and symmetric

Answer: D. Missing loops make S non-reflexive. Symmetry and transitivity hold vacuously because no pair can violate reversal and no two-pair chain can demand a shortcut. Empty does not mean property-free.

Finite relation MCQ 10: prove transitivity without checking 64 triples

Question 10

The binary relation R= { (1, 1), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4) } on the set A(1, 2, 3, 4) is

• A. Reflexive, symmetric and transitive

• B. Neither reflexive, nor irreflexive but transitive

• C. Irreflexive, symmetric and transitive

• D. Irreflexive and anti-symmetric

Answer: B. Loops on 1, 2 and 3 are present but (4,4) is absent, so R is neither reflexive nor irreflexive. The successor sets are 1->{1}, 2->{1,2,3,4}, 3->{1,2,3,4}, 4->{}. Chains through 1 reproduce an endpoint, chains through 2 or 3 start in complete rows, and none continues through 4, so R is transitive.

Transitive-closure MCQs 11-12: repeated reachability and Warshall's rule

Question 11

Consider the binary relation: S = {(x, y) | y = x+1 and x, y ∈ {0, 1, 2, ...}} The reflexive transitive closure of S is

• A. {(x, y) | y > x and x, y ∈ {0, 1, 2, ... }}

• B. {(x, y) | y ≥ x and x, y ∈ {0, 1, 2, ... }}

• C. {(x, y) | y < x and x, y ∈ {0, 1, 2, ... }}

• D. {(x, y) | y ≤ x and x, y ∈ {0, 1, 2, ... }}

Answer: B. Repeated steps give x->x+k for k>=1; for example, 2->3->4->5 adds (2,5). Reflexive closure adds the zero-step pair (x,x), giving exactly y>=x.

Question 12

Find the zero-one matrix of the transitive closure of the relation given by the matrix $A$ : $A =\begin{bmatrix} 1 & 0& 1\\ 0 & 1 & 0\\ 1& 1& 0 \end{bmatrix}$

• A. $\begin{bmatrix} 1 & 1& 1\\ 0 & 1 & 0\\ 1& 1& 1 \end{bmatrix}$

• B. $\begin{bmatrix} 1 & 0& 1\\ 0 & 1 & 0\\ 1& 1& 0 \end{bmatrix}$

• C. $\begin{bmatrix} 1 & 0& 1\\ 0 & 1 & 0\\ 1& 0& 1 \end{bmatrix}$

• D. $\begin{bmatrix} 1 & 1& 1\\ 0 & 1 & 0\\ 1& 0& 1 \end{bmatrix}$

Answer: A. Read rows as sources and columns as destinations. The paths 3->1->3 and 1->3->2 force (3,3) and (1,2). Since node 2 has only its loop, the closure rows are [1,1,1], [0,1,0], [1,1,1]. Warshall update sets w[i,j] to true when w[i,k] and w[k,j] are true. At k=1 it adds (3,3) through 3->1->3, and at k=3 it adds (1,2) through 1->3->2.

Transitive relation answer map, traps and the next practice step

Answers: 1-A; 2-A; 3-D; 4-B; 5-D; 6-A; 7-C; 8-B; 9-D; 10-B; 11-B; 12-A.

Reproduce: 16-3=13 on {1,2}; failed endpoint (4,5)->(5,1)->(2,3); Q10 successor sets; Q12 additions (3,3), (1,2).

Next, solve Set Theory and Relations MCQs: 12 Solved. Use GATE Guidance by Sanchit Sir for Relations lessons and the GATE Test Series for timed mixed practice. Make every answer earn its shortcut or counterexample.