Relations are where Discrete Mathematics turns from vocabulary into reasoning. Once you can test a relation for the three core properties and compute its closures, a large block of GATE questions on equivalence classes, partial orders and Hasse diagrams becomes mechanical. This post builds the topic from set operations up through relation properties, the three closures, equivalence relations, and partial orders, with a closure computed step by step.
Set operations and Cartesian products
A set is an unordered collection of distinct elements. The operations you need are union (A union B, everything in either), intersection (A intersect B, everything in both), difference (A minus B, in A but not B), complement (everything in the universe not in A), and the power set (the set of all subsets, of size 2^n for an n-element set). Two identities carry most manipulation: DeMorgan's laws for sets, (A union B)' = A' intersect B' and (A intersect B)' = A' union B', which are the exact analogues of the Boolean versions.
The Cartesian product A x B is the set of all ordered pairs (a, b) with a in A and b in B. If A has m elements and B has n, then A x B has m times n pairs. This matters because a relation is defined on top of it.
Relations: definition and the three properties
A relation R from a set A to a set B is any subset of A x B. When A equals B we call it a relation on A, and the interesting properties are defined there. For a relation R on a set A:
Reflexive: every element relates to itself, (a, a) is in R for all a in A.
Symmetric: if (a, b) is in R then (b, a) is in R.
Antisymmetric: if (a, b) and (b, a) are both in R, then a = b. This is not the opposite of symmetric; a relation can be both (only when it holds solely on the diagonal) or neither.
Transitive: if (a, b) and (b, c) are in R, then (a, c) is in R.
An n-element set has 2^(n^2) possible relations in total, because A x A has n^2 pairs and each may be in or out. Counting relations with a given property is a standard exam item, so know that the number of reflexive relations on an n-set is 2^(n^2 - n) and the number of symmetric ones is 2^(n(n+1)/2).
Closures: adding the least you must
A closure of a relation with respect to a property is the smallest relation that contains R and has that property. Three matter.
Reflexive closure: add every missing pair (a, a). Formally R union the identity relation.
Symmetric closure: add (b, a) for every (a, b) in R. Formally R union its inverse.
Transitive closure: add pairs forced by transitivity, repeatedly, until nothing new appears. This is the one that takes work, and Warshall's algorithm computes it systematically.
A worked transitive closure
Let A = {1, 2, 3, 4} and R = {(1, 2), (2, 3), (3, 4)}. R is not transitive: (1, 2) and (2, 3) demand (1, 3), which is absent. Compute the transitive closure step by step by chasing every two-step path and adding the shortcut.
(1, 2) then (2, 3) forces (1, 3).
(2, 3) then (3, 4) forces (2, 4).
(3, 4) has no outgoing pair from 4, so it forces nothing yet.
Now with (1, 3) present, (1, 3) then (3, 4) forces (1, 4).
With (2, 4) present, 4 has no outgoing pair, so nothing new.
Re-scan: no further two-step path lacks its shortcut.
The transitive closure is R union {(1, 3), (2, 4), (1, 4)}, that is {(1,2), (2,3), (3,4), (1,3), (2,4), (1,4)}. In words, the closure connects every element to every other element it can reach along a directed path, which is exactly what "reachability" means, and why transitive closure and graph reachability are the same computation.
Equivalence relations and partition
A relation that is reflexive, symmetric and transitive is an equivalence relation. Its central consequence is that it partitions the set: the elements fall into disjoint equivalence classes whose union is the whole set, where two elements share a class exactly when they are related. The canonical example is congruence modulo m on the integers, which sorts every integer into m classes by remainder. The number of distinct equivalence relations on an n-element set equals the number of ways to partition it, the Bell number, a fact GATE uses for small n.
Partial orders and Hasse diagrams
A relation that is reflexive, antisymmetric and transitive is a partial order, and the set with it is a poset. "Partial" means some pairs may be incomparable, neither element related to the other, unlike a total order where every pair is comparable. The divides relation on {1, 2, 3, 4, 6, 12} is the standard example: 2 and 3 are incomparable because neither divides the other.
A Hasse diagram draws a poset compactly by dropping everything implied. You remove the self-loops (reflexivity is assumed), remove edges implied by transitivity, and orient the rest upward so direction is shown by height rather than arrows. What remains are only the cover relations, each element joined to those immediately above it.
From the diagram you read off the vocabulary GATE tests: 1 is the least element, 12 is the greatest, and terms like maximal, minimal, least upper bound (join) and greatest lower bound (meet) are all defined by position in this picture. A poset in which every pair has a join and a meet is a lattice, the divides example here being one.
How set theory and relations are tested in GATE
Discrete Mathematics is a large, reliable scorer, with over 190 published questions under Relations and over 160 under Set Theory in the KnowledgeGate bank, inside a Discrete pool of over 1,200 published. The dependable patterns are: classify a given relation by its properties, count relations of a given type on an n-set, compute a closure or identify equivalence classes, and read a Hasse diagram for least, greatest, maximal or minimal elements or for the lattice property. A frequent trap presents a relation that is antisymmetric and asks you to call it "not symmetric", when a relation can be both on the diagonal.
The habitual mistakes are treating antisymmetric as the negation of symmetric, forgetting that transitive closure must be iterated until it stabilises, and drawing a Hasse diagram with the transitive edges still in. Each is fixed by working a handful of concrete relations by hand.
The short version
Test relations against the three properties without guessing, compute closures by chasing paths to a fixed point, and read a poset straight off its Hasse diagram. Work the topic on the Relations learn module and the foundational Set Theory learn module. For the full GATE sequence, where set theory and relations lead into functions and lattices, GATE Guidance by Sanchit Sir orders the Discrete syllabus properly, with the CS Fundamentals category collecting the rest.
