Relations look simple until reflexive, symmetric, antisymmetric, transitive, equivalence, and partial-order questions arrive together. Every one of those is a finite check on a finite list of ordered pairs: scan the diagonal, scan the reversed pairs, scan the two-step chains, and the classification falls out. Divisibility on {1, 2, 3, 6} settles into a partial order that way, and remainders modulo 3 settle into three equivalence classes.
What a relation is: Cartesian products, domain and range
A binary relation from A to B is any subset of A × B. Let A = {a, b, c} and B = {0, 1}. Then
A × B = {(a, 0), (a, 1), (b, 0), (b, 1), (c, 0), (c, 1)}.
Six independent choices give 2^6 = 64 relations. For an n-element set, A × A has n^2 pairs, giving 2^(n^2) relations. Review Set Theory and Relations: Closures, Equivalence and Partial Orders for the foundations.
For R = {(a, 0), (a, 1), (c, 1)}, domain = {a, c}, codomain = B = {0, 1}, and range = {0, 1}; b need not appear. A relation may give an input zero, one, or several partners. Direction matters: (a, 0) and (0, a) differ, and the second is not in A × B.
Relation representations and operations: matrix, digraph, inverse, complement, composition
For A = {1, 2, 3}, let R = {(1, 1), (1, 2), (2, 3), (3, 3)}. In row and column order 1, 2, 3, its Boolean matrix is:
1 | 2 | 3 | |
|---|---|---|---|
1 | 1 | 1 | 0 |
2 | 0 | 0 | 1 |
3 | 0 | 0 | 1 |
Its digraph has loops at 1 and 3, plus arrows 1 → 2 and 2 → 3. A relation on one set is exactly a directed graph on that set, so the path and reachability vocabulary of Graph Theory: Euler and Hamiltonian Paths, Coloring and Connectivity applies to it unchanged.
Reverse every pair: R^(-1) = {(1, 1), (2, 1), (3, 2), (3, 3)}. In A × A, R^c = {(1, 3), (2, 1), (2, 2), (3, 1), (3, 2)}. Composition includes (x, z) when some y gives xRy and yRz. Two-step paths give
R ∘ R = {(1, 1), (1, 2), (1, 3), (2, 3), (3, 3)}.
Relation properties: use a mechanical checklist
Property | Test |
|---|---|
Reflexive | Every (x, x) is present. |
Irreflexive | No (x, x) is present. |
Symmetric | xRy implies yRx. |
Antisymmetric | xRy and yRx together force x = y. |
Asymmetric | xRy forbids yRx, so loops are forbidden. |
Transitive | xRy and yRz imply xRz. |
Apply the checklist to divisibility on A = {1, 2, 3, 6}:
D = {(1, 1), (1, 2), (1, 3), (1, 6), (2, 2), (2, 6), (3, 3), (3, 6), (6, 6)}.
Its four loops prove reflexivity. If positive x divides y and y divides x, then x = y, proving antisymmetry. Since divisibility chains compose, D is transitive. It is not symmetric because (2, 6) occurs but (6, 2) does not. Loops rule out irreflexivity and asymmetry. Therefore, D is a partial order, not an equivalence relation.
For S = {(1, 2), (2, 3)}, the reflexive closure adds {(1, 1), (2, 2), (3, 3)}, the symmetric closure adds {(2, 1), (3, 2)}, and the transitive closure adds {(1, 3)}. These are separate minimal additions.
Equivalence relations create disjoint classes
An equivalence relation is reflexive, symmetric, and transitive. On A = {0, 1, 2, 3, 4, 5}, define xEy when x and y leave the same remainder on division by 3. Then
E = {(0, 0), (0, 3), (3, 0), (3, 3), (1, 1), (1, 4), (4, 1), (4, 4), (2, 2), (2, 5), (5, 2), (5, 5)}.
Every number shares its own remainder, proving reflexivity. Sharing a remainder works in both directions, proving symmetry. If x shares y's remainder and y shares z's, then x shares z's, proving transitivity.
The classes are [0] = {0, 3}, [1] = {1, 4}, and [2] = {2, 5}; [3] = [0], [4] = [1], and [5] = [2]. They are non-empty, pairwise disjoint, and unite to A, so they form a partition. Conversely, {{0, 3}, {1, 4}, {2, 5}} defines E by relating elements in the same block. Thus A/E = {[0], [1], [2]}.
Partial orders, Hasse diagrams, bounds and lattices
A partial order is reflexive, antisymmetric, and transitive. A total order also compares every distinct pair. Divisibility on {1, 2, 3, 6} is not total because neither 2 divides 3 nor 3 divides 2.
For its Hasse diagram, remove the four loops and transitive edge 1 to 6. The covers are 1 to 2, 1 to 3, 2 to 6, and 3 to 6. Element 1 is least and uniquely minimal; 6 is greatest and uniquely maximal.
For {2, 3}, lower bounds = {1}, so meet(2, 3) = 1; upper bounds = {6}, so join(2, 3) = 6. Every pair has a meet and join, making this poset a lattice. Larger posets, and the bounded, complemented and distributive lattice types, are worked out on the divisors of 30 in Lattices and Hasse Diagrams for GATE: LUB, GLB and the Lattice Test.
Common relation mistakes and their corrections
Mistaken move | Concrete counterexample | Correction |
|---|---|---|
Antisymmetric means not symmetric. | Equality on {1, 2}, that is {(1, 1), (2, 2)}, is both. | Test each definition separately. |
A pair whose reverse is missing proves antisymmetry. | {(1, 2), (2, 3), (3, 2)} has (1, 2) unreversed, yet (2, 3) and (3, 2) break antisymmetry. | Antisymmetry fails only on a two-way pair of distinct elements, so check all of them. |
Transitive means every pair needs a reverse. | {(1, 2), (2, 3), (1, 3)} is transitive and contains no reversed pair. | Check every relevant two-step chain, not the reversals. |
Inverse and composition are interchangeable. | For R above, R^(-1) holds (2, 1) and R ∘ R does not; R ∘ R holds (1, 3) and R^(-1) does not. | Reverse pairs for the inverse, follow length-two paths for the composition. |
Transitive closure adds all missing pair types. | For S = {(1, 2), (2, 3)}, it adds only (1, 3). | Do not add reversed or diagonal pairs unless they are asked for. |
A Hasse diagram shows the full relation. | D's four loops and its 1-to-6 edge are all absent from the diagram. | Remove loops and implied edges; place larger elements higher. |
How GATE-style and interview questions test relations
Identify the operation first: test properties, count relations, find a closure, derive classes, or read a Hasse diagram. The syllabus wording and paper rules for a given cycle are in the official GATE information brochure published by that year's organising institute.
For |A| = 3, A × A has nine pairs:
All relations: 2^9 = 512.
Reflexive relations: the three loops are forced, so 2^(9 - 3) = 64.
Symmetric relations: choose three loops and three unordered off-diagonal pairs, so 2^(3 + C(3, 2)) = 64.
Antisymmetric relations: choose the three loops freely. Each unordered off-diagonal pair permits neither direction or exactly one direction, so 2^3 × 3^C(3, 2) = 8 × 27 = 216.
Asymmetric relations: loops are forbidden, leaving 3^C(3, 2) = 27.
No independent-choice formula counts transitive relations, so those sets are counted case by case. More than 190 questions on relations sit in the KnowledgeGate question bank, and GATE Guidance by Sanchit Sir teaches the Discrete Mathematics sequence they belong to in order. Interviewers usually want the reasoning rather than a count: divisibility is antisymmetric because x dividing y and y dividing x force x = y for positive integers, and it is not symmetric because 2 divides 6 while 6 does not divide 2.
Relations in discrete mathematics: the short version and next step
Use this six-step checklist:
Write the underlying set and universe.
List or mark all diagonal pairs.
Test reverse pairs.
Test every relevant two-step chain.
Decide whether the relation is an equivalence or a partial order.
Draw classes or a Hasse diagram only after classification.
Modulo 3 gave three equivalence classes; divisibility on {1, 2, 3, 6} gave a four-element lattice. For the rest of the Discrete Mathematics sequence, and timed practice on these property checks, start from GATE CS Exam Preparation Courses and Test Series.
Next, recreate R's matrix, prove D's properties, redraw its Hasse diagram without 1-to-6, and recompute 216 without notes.
