Relations are where Discrete Mathematics turns from vocabulary into reasoning. Once you can test a relation for the four defining properties and compute its closures, a large block of GATE questions on equivalence classes, partial orders and Hasse diagrams becomes mechanical. The trouble is that the properties look interchangeable on paper: antisymmetric is not the negation of symmetric, and a transitive closure is rarely finished after one pass.
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: De Morgan'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. Cardinality, countability and the subset hierarchy are built on these same operations, and they are worked out in the Set Theory learn module.
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 four 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, and the KnowledgeGate question bank carries over 190 practice questions on Relations and over 160 on Set Theory, inside a Discrete pool of over 1,200. 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 shows a relation that is antisymmetric and invites you to conclude it cannot be symmetric, when a relation that holds only on the diagonal is both.
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 concrete relations by hand, which is what the solved set on Symmetric, Antisymmetric and Asymmetric Relation MCQs drills, one property test at a time.
The short version
Test relations against the four 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. 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.
