Set theory and relations are the grammar of discrete mathematics: almost every later topic, from functions and lattices to graph theory, is written in this language. GATE rewards a clean grasp of set identities, the reflexive-symmetric-transitive tests, closures, equivalence classes, and partial orders, and it punishes vague memorisation with distractor-heavy options. Each question below carries the GATE year it appeared in. Attempt it before reading the explanation, then follow the link under it for the full working. If a definition feels shaky, the theory sits in the Discrete Mathematics learn module.
Set operations and identities
Q1. In a class of 200 students, 125 took Programming, 85 took Data Structures, 65 took Computer Organization, 50 took Programming and Data Structures, 35 took Data Structures and Computer Organization, 30 took Programming and Computer Organization, and 15 took all three. How many took none of the three? (GATE 2004)
(a) 15
(b) 20
(c) 25
(d) 35
Answer: (c) 25. Inclusion-exclusion gives the union as 125 + 85 + 65 minus 50 + 35 + 30 plus 15, which is 275 - 115 + 15 = 175. The students taking none are 200 - 175 = 25. Add the singles, subtract the pairs, add back the triple: getting the alternating signs right is the whole exam here (see the full worked solution).
Q2. For sets A and B, the set (A - B) union (B - A) union (A intersection B) equals (GATE 1996)
(a) A union B
(b) A complement union B complement
(c) A intersection B
(d) A complement intersection B complement
Answer: (a) A union B. The three pieces are the only-in-A part, the only-in-B part, and the shared part. They are disjoint and together cover exactly everything in A or in B, so their union is A union B. A quick Venn sketch settles this class of identity in seconds (see the full working).
Q3. If P, Q, R are subsets of the universal set U, the value of (P intersection Q intersection R) union (P complement intersection Q intersection R) union Q complement union R complement is (GATE 2008)
(a) Q complement union R complement
(b) P union Q complement union R complement
(c) P complement union Q complement union R complement
(d) U
Answer: (d) U. Merge the first two terms: (P union P complement) intersection Q intersection R is just Q intersection R. What remains is (Q intersection R) union (Q intersection R) complement, because by DeMorgan Q complement union R complement is the complement of Q intersection R. A set unioned with its own complement is the universe U (see the step-by-step solution).
Relations: property tests and counting
Q4. For a set A of n elements, how many binary relations can be defined on A? (GATE 1999)
(a) n squared
(b) 2 to the power n
(c) 2 to the power n squared
(d) None of the above
Answer: (c) 2 to the power n squared. A binary relation on A is any subset of A cross A, and A cross A has n times n = n squared ordered pairs. The number of subsets of a set with n squared elements is 2 to the power n squared. Every counting question about relations starts from this A cross A base (see the detailed solution).
Q5. For the relation R = {(x, y), (x, z), (z, x), (z, y)} on the set {x, y, z}, which is TRUE? (GATE 2009)
(a) R is symmetric but not antisymmetric
(b) R is not symmetric but antisymmetric
(c) R is both symmetric and antisymmetric
(d) R is neither symmetric nor antisymmetric
Answer: (d) neither. Symmetry fails because (x, y) is present but (y, x) is not. Antisymmetry also fails because both (x, z) and (z, x) are present with x not equal to z, which is exactly the pattern antisymmetry forbids. A relation can lack both properties at once, and mixing up "not symmetric" with "antisymmetric" is the classic slip (see the full worked solution).
Q6. The empty relation S = the empty set on the set A = {1, 2, 3} is (GATE 2002)
(a) neither reflexive nor symmetric
(b) symmetric and reflexive
(c) transitive and reflexive
(d) transitive and symmetric
Answer: (d) transitive and symmetric. The empty relation has no pairs, so symmetry and transitivity hold vacuously, there is no counterexample to break them. But reflexivity fails, because it demands (1,1), (2,2) and (3,3), none of which are present. Vacuous truth is a favourite discrete-maths trap (see the full working).
Closures and equivalence relations
Q7. For S = {(x, y) : y = x + 1 and x, y in {0, 1, 2, ...}}, the reflexive transitive closure of S is (GATE 2004)
(a) {(x, y) : y greater than x}
(b) {(x, y) : y greater than or equal to x}
(c) {(x, y) : y less than x}
(d) {(x, y) : y less than or equal to x}
Answer: (b) {(x, y) : y greater than or equal to x}. S holds only the successor pairs (x, x+1). Transitivity chains these into (x, x+n) for every positive n, giving all pairs with y greater than x. Adding reflexivity supplies the case n = 0, so the closure is every pair with y greater than or equal to x. Closure means adding the minimum pairs to gain the named property (see the step-by-step solution).
Q8. A relation R on the integers is defined by x R y if x + y is even. Which is true? (GATE 2000)
(a) R is not an equivalence relation
(b) R is an equivalence relation with 1 equivalence class
(c) R is an equivalence relation with 2 equivalence classes
(d) R is an equivalence relation with 3 equivalence classes
Answer: (c) an equivalence relation with 2 classes. A sum is even exactly when both numbers share parity, so R is reflexive, symmetric and transitive, an equivalence relation. It partitions the integers into two classes, the evens and the odds. Every equivalence relation corresponds to a partition, and here parity is the partition (see the detailed solution).
Q9. The number of equivalence relations on the set {1, 2, 3, 4} is (GATE 1997)
(a) 15
(b) 16
(c) 24
(d) 4
Answer: (a) 15. Equivalence relations on a set are in one-to-one correspondence with its partitions, so the count is the Bell number. For a 4-element set the Bell number is 15. Do not count orderings or subsets; count the ways to partition (see the full worked solution).
Q10. For a set S of n elements, the numbers of ordered pairs in the largest and the smallest equivalence relations on S are (GATE 2007)
(a) n and n
(b) n squared and n
(c) n squared and 0
(d) n and 1
Answer: (b) n squared and n. The largest equivalence relation is the universal relation S cross S, with n squared pairs, corresponding to the single-block partition. The smallest is the identity relation, one pair (a, a) per element, so n pairs, corresponding to all singletons. Reflexivity forbids the empty relation, which rules out option (c) (see the full working).
Partial orders, covers and Hasse diagram edges
Q11. For X = {2, 3, 6, 12, 24} with the partial order x less than or equal to y when x divides y, the number of edges in the Hasse diagram is (GATE 1996)
(a) 3
(b) 4
(c) 9
(d) None of the above
Answer: (b) 4. A Hasse diagram draws only cover relations, dropping edges implied by transitivity. The covers here are 2 divides 6, 3 divides 6, 6 divides 12, and 12 divides 24, four edges in all. Pairs like 2 divides 12 are omitted because 6 sits between them. Reduce to covers before counting, never draw the full order (see the step-by-step solution).
Q12. A partial order P on the natural numbers is defined by (0, 0) in P, and (a, b) in P if and only if a mod 10 is at most b mod 10 and (a div 10, b div 10) in P. Which pairs lie in P: (i) (101, 22), (ii) (22, 101), (iii) (145, 265), (iv) (0, 153)? (GATE 2007)
(a) (i) and (iii)
(b) (ii) and (iv)
(c) (i) and (iv)
(d) (iii) and (iv)
Answer: (d) (iii) and (iv). The rule compares numbers digit by digit from the units up, requiring each digit of the first to be at most the matching digit of the second. For (145, 265): 5 at most 5, 4 at most 6, 1 at most 2, all hold. For (0, 153): 0 is at most every digit. Pair (i) fails at the hundreds digit and (ii) fails at the units, so only (iii) and (iv) qualify (see the detailed solution).
Set theory and relations: the question shapes GATE reuses
GATE returns to five recognisable shapes in this topic. Counting problems on sets fall to inclusion-exclusion, where the marks are lost on the alternating signs rather than on the idea. Identity problems built from complements and DeMorgan collapse fast once you merge terms until a set meets its own complement. Property questions on a small relation are settled by hunting one counterexample per property, and the trap is assuming that a failure of symmetry buys you antisymmetry. Counting questions on relations start from the A cross A base, and counting equivalence relations means counting partitions, never subsets or orderings. Partial orders reward reducing the order to its cover pairs before anything is drawn or counted. The picture underneath all five is that an equivalence relation is a partition and a partial order is a divisibility-style hierarchy, so redrawing a relation as one of those two usually cracks the question. Set algebra is the same structure you meet as a Boolean algebra, so the Boolean algebra and K-map MCQs drill the identical laws on logic variables. If a definition needs rebuilding rather than revising, Set theory and relations explained works through closures, equivalence classes and posets from first principles.
Work each question a second time a week later, and confirm your reasoning against the Discrete Mathematics learn module. GATE aspirants get the full discrete maths sequence inside GATE Guidance by Sanchit Sir, and you can place the subject in the wider syllabus on the GATE CS Exam page. Solve, review the ones you missed, and the marks get locked in on the second pass.
