MathematicsRelations and FunctionsJEE

Relations and Functions · Part 2 of 20

Reflexive, Symmetric and Transitive Relations

Draw A × A as an n × n grid and three properties become visible: reflexive (the whole diagonal), symmetric (mirror pairs) and transitive (every chain has its shortcut). The grid also counts them.

Builds on: Part 1 · Relations: Definition, Domain and Range.

Reflexive, Symmetric and Transitive Relations

Video coming soon

The picture

Diagonal and two mirror triangles

A × A has n² cells: the diagonal holds the n pairs (a, a), and the other n² − n cells form two triangles of $\frac{n ^{2} - n}{2}$ each, mirror images across the diagonal.

4 by 4 grid with the diagonal and triangles tinted. — n = 4: 4 diagonal cells, 6 + 6 off it.

Grid with diagonal dots and mirrored pairs. — Choose in one triangle; the mirror cell follows.

Counting

Reflexive and symmetric

Reflexive: diagonal forced, $n^{2} - n$ cells free, so $2^{n^{2} - n}$ relations. Symmetric: diagonal and one triangle free, $2^{(n^{2} + n) /2}$ . Both: only one triangle free, $2^{(n^{2} - n) /2}$ . For n = 3: 64 symmetric, 8 reflexive and symmetric, so 56 symmetric but not reflexive.

Transitive

Every chain needs its shortcut

(a, b) and (b, c) in R force (a, c) into R. R = {(1, 2), (2, 3)} fails: (1, 3) is missing. Chains can come back: (1, 2), (2, 1) force (1, 1) and (2, 2).

3 by 3 grid showing a broken chain. — The missing shortcut is marked.

Table of six relations. — R, S, T for each relation.

Classify

Six relations on N

x + y even and x + 2y divisible by 3 are equivalence relations; xy even and HCF{x, y} = 1 are symmetric only; max{x, y} = x and y | x are reflexive and transitive.

Summary

Key formulas

reflexive: 2^{n^{2} - n}

Reflexive relation

symmetric: 2^{(n^{2} + n) /2}

Symmetric relation

reflexive and symmetric: 2^{(n^{2} - n) /2}

Symmetric relation

Worked examples

From the video

1. 4096 reflexive relations on A. Find n(A).

2^(n² − n) = 2¹², so n² − n = 12 and n = 4.

2. n(A) = 3. Relations that are symmetric but not reflexive?

64 − 8 = 56.

3. A = {1, …, 130}, a R b iff ab = 100a + b. Find n(R) and the fewest pairs to add for symmetry.

n(R) = 7; 6 pairs, because (101, 101) is its own mirror (some keys print 7).

4. R = {(a, b) : a ≤ b²} on R. Reflexive? Symmetric? Transitive?

None: (0.5, 0.5) ∉ R; (1, 4) ∈ R but (4, 1) ∉ R; (3, 2), (2, 1.5) ∈ R but (3, 1.5) ∉ R.

JEE-style question

Your turn

A = {1, 2, 3}. The number of relations on A that are both reflexive and symmetric is:

(a)8

(b)56

(c)64

(d)512

Show the answer and the traps

The diagonal is forced, and one triangle of 3 cells is free: 2³ = 8. Option (a).

56 counts the symmetric relations that are not reflexive.

64 counts reflexive ones alone, or symmetric ones alone. 512 = 2⁹ counts every relation.

Watch out

Common mistakes

Assuming transitivity because no counter-example comes to mindTest the chain through every pair, including chains that return.

Adding a mirror pair for every pair of RA pair (a, a) is its own mirror and needs nothing.

Calling a relation reflexive when one (a, a) is missingEvery element of A needs its diagonal pair.

Practice

Try these

1. How many reflexive relations are there on a set of 3 elements?

2^(9 − 3) = 64.

2. R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 3)} on {1, 2, 3}. Which properties hold?

Reflexive only: not symmetric ((1, 2) without (2, 1)), not transitive ((1, 3) missing).

3. On the lines in a plane, L₁ R L₂ iff L₁ ⊥ L₂. Classify R.

Symmetric only: no line is perpendicular to itself, and L₁ ⊥ L₂, L₂ ⊥ L₃ give L₁ ∥ L₃.

4. How many symmetric relations are there on a set of 4 elements?

2^((16 + 4)/2) = 2¹⁰ = 1024.