High yield ●●●

🔗 Sets, Relations & Functions

Why it matters: A steady 2 to 3 marks: count relations with a property, decide whether a relation is an equivalence or partial order, read a Hasse diagram or lattice, and classify functions.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 7 done.

Formulas

Inclusion–exclusion
|A∪B∪C| = Σ|A| − Σ|A∩B| + |A∩B∩C|
Power set / product
|P(A)| = 2^|A|; |A × B| = |A|·|B|
Relations on an n-set
all 2^(n²), reflexive 2^(n²−n), symmetric 2^(n(n+1)/2)
Antisymmetric / asymmetric
2ⁿ·3^(n(n−1)/2) / 3^(n(n−1)/2)
Equivalence relations
Bell(n): 1, 2, 5, 15, 52, 203, …
Functions m → n
all nᵐ; injective n!/(n−m)!; onto n!·S(m,n)
Transitive closure
R⁺ = R ∪ R² ∪ … ∪ Rⁿ
Divisor lattice
D_n is Boolean iff n is squarefree; |D_n| = Π(eᵢ + 1)

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Count relations or functions with a given property
Use the formulas for reflexive/symmetric/antisymmetric; for onto functions use inclusion–exclusion or S(m,n).
★★★
Is this relation an equivalence / partial order?
Test the three properties in turn; one counter-example kills it.
★★★
Hasse diagram, lattice, lub/glb
Read covers, find minimal/maximal, check each pair has a unique lub and glb.
★★★
Number of equivalence classes / size of a relation
Sum of squares of class sizes; or count classes of mod k.
★★★
Injective/surjective/composition statements
Test with small counter-examples; use g∘f results.

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

20 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

20 questions · 0 correct of 0 attempted · marks 0 / 32

Year:
GATE 2025 CS1 · Q17MCQ1 mark
g(·) is a function from A to B, f(·) is a function from B to C, and their composition defined as f(g(·)) is a mapping from A to C. If f(·) and f(g(·)) are onto (surjective) functions, which ONE of the following is TRUE about the function g(·)?
GATE 2025 CS2 · Q42MSQ2 marks
Let F be the set of all functions from {1, …, n} to {0, 1}. Define the binary relation ≼ on F as follows: ∀f, g ∈ F, f ≼ g if and only if ∀x ∈ {1, …, n}, f(x) ≤ g(x), where 0 ≤ 1. Which of the following statement(s) is/are TRUE?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS1 · Q32NAT1 mark
Let A and B be non-empty finite sets such that there exist one-to-one and onto functions (i) from A to B and (ii) from A × A to A ∪ B. The number of possible values of |A| is ______.
GATE 2024 CS2 · Q34NAT1 mark
Let P be the partial order defined on the set {1, 2, 3, 4} as follows: P = {(x, x) | x ∈ {1, 2, 3, 4}} ∪ {(1, 2), (3, 2), (3, 4)}. The number of total orders on {1, 2, 3, 4} that contain P is ______.
GATE 2023 · Q49MSQ2 marks
Let f : A → B be an onto (or surjective) function, where A and B are nonempty sets. Define an equivalence relation ∼ on the set A as a₁ ∼ a₂ if f(a₁) = f(a₂), where a₁, a₂ ∈ A. Let E = {[x] : x ∈ A} be the set of all the equivalence classes under ∼. Define a new mapping F : E → B as F([x]) = f(x), for all the equivalence classes [x] in E. Which of the following statements is/are TRUE?

One or more options may be correct. Select all that apply, then submit.

GATE 2021 Set 2 · Q11MSQ1 mark
Consider the following sets, where n ≥ 2: S₁: Set of all n × n matrices with entries from the set {a, b, c}. S₂: Set of all functions from the set {0, 1, 2, …, n² − 1} to the set {0, 1, 2}. Which of the following choice(s) is/are correct?

One or more options may be correct. Select all that apply, then submit.

GATE 2021 Set 1 · Q43MSQ2 marks
A relation R is said to be circular if aRb and bRc together imply cRa. Which of the following options is/are correct?

One or more options may be correct. Select all that apply, then submit.

GATE 2021 Set 2 · Q50NAT2 marks
Let S be a set consisting of 10 elements. The number of tuples of the form (A, B) such that A and B are subsets of S, and A ⊆ B is ______.
GATE 2020 · Q17NAT1 mark
Let R be the set of all binary relations on the set {1, 2, 3}. Suppose a relation is chosen from R at random. The probability that the chosen relation is reflexive (round off to 3 decimal places) is ______.
GATE 2019 Set 2 · Q34MCQ2 marks
Consider the following sets: S1. Set of all recursively enumerable languages over the alphabet {0, 1}. S2. Set of all syntactically valid C programs. S3. Set of all languages over the alphabet {0, 1}. S4. Set of all non-regular languages over the alphabet {0, 1}. Which of the above sets are uncountable?
GATE 2018 · Q27MCQ2 marks
Let N be the set of natural numbers. Consider the following sets. P: Set of Rational numbers (positive and negative). Q: Set of functions from {0, 1} to N. R: Set of functions from N to {0, 1}. S: Set of finite subsets of N. Which of the sets above are countable?
GATE 2017 Set 2 · Q21NAT1 mark
Consider the set X = {a, b, c, d, e} under the partial ordering R = {(a,a), (a,b), (a,c), (a,d), (a,e), (b,b), (b,c), (b,e), (c,c), (c,e), (d,d), (d,e), (e,e)}. The Hasse diagram of the partial order (X, R) is a chain a < b < c < e on one side and a < d < e on the other. The minimum number of ordered pairs that need to be added to R to make (X, R) a lattice is ______.
GATE 2016 Set 2 · Q26MCQ2 marks
A binary relation R on N × N is defined as follows: (a, b) R (c, d) if a ≤ c or b ≤ d. Consider the following propositions: P: R is reflexive. Q: R is transitive. Which one of the following statements is TRUE?
GATE 2016 Set 1 · Q28NAT2 marks
A function f : N⁺ → N⁺, defined on the set of positive integers N⁺, satisfies the following properties: f(n) = f(n/2) if n is even; f(n) = f(n + 5) if n is odd. Let R = {i | ∃j : f(j) = i} be the set of distinct values that f takes. The maximum possible size of R is ______.
GATE 2014 Set 3 · Q2MCQ1 mark
Let X and Y be finite sets and f : X → Y be a function. Which one of the following statements is TRUE?
GATE 2014 Set 3 · Q16MCQ1 mark
Let Σ be a finite non-empty alphabet and let 2Σ* be the power set of Σ*. Which one of the following is TRUE?
GATE 2014 Set 3 · Q49MCQ2 marks
Consider the set of all functions f : {0, 1, …, 2014} → {0, 1, …, 2014} such that f(f(i)) = i, for all 0 ≤ i ≤ 2014. Consider the following statements. P. For each such function it must be the case that for every i, f(i) = i. Q. For each such function it must be the case that for some i, f(i) = i. R. Each such function must be onto. Which one of the following is CORRECT?
GATE 2014 Set 1 · Q50NAT2 marks
Let S denote the set of all functions f : {0, 1}⁴ → {0, 1}. Denote by N the number of functions from S to the set {0, 1}. The value of log₂ log₂ N is ______.
GATE 2014 Set 2 · Q50MCQ2 marks
Consider the following relation on subsets of the set S of integers between 1 and 2014. For two distinct subsets U and V of S we say U < V if the minimum element in the symmetric difference of the two sets is in U. Consider the following two statements: S1: There is a subset of S that is larger than every other subset. S2: There is a subset of S that is smaller than every other subset. Which one of the following is CORRECT?
GATE 2012 Code A · Q37MCQ2 marks
How many onto (or surjective) functions are there from an n-element (n ≥ 2) set to a 2-element set?

Common traps

Antisymmetric ≠ not symmetric. The identity relation is both; a relation with (1,2),(2,1),(1,3) is neither antisymmetric nor symmetric.
A relation with no pairs is symmetric, antisymmetric and transitive (vacuously), but not reflexive.
A relation that is symmetric and transitive but misses some (a,a) fails reflexivity: an element with no partner has no (a,a).
Maximal ≠ greatest: a poset can have several maximal elements and no greatest.
Onto functions are counted with inclusion–exclusion, not with nᵐ − n!.