GATE CS

Sets, relations, functions, partial orders and lattices

This topic covers sets, relations, functions, partial orders and lattices, the vocabulary used all through discrete mathematics. Typical questions ask you to count objects (relations with a given property, functions, partitions), to test a relation for its properties, or to decide whether a poset is a lattice and of what kind. The definitions and counting formulas below are stated with their conditions; read each question's own conventions first.

8 previous-year questions · 8 solved · 6 practice questions

Sets and counting with sets

A set is a collection of distinct objects. $∣ A ∣$ is the number of elements of a finite set $A$ . The power set $P (A)$ is the set of all subsets of $A$ (including $\emptyset$ and $A$ ). The symmetric difference $A \oplus B = (A ∖ B) \cup (B ∖ A)$ holds the elements in exactly one of the two sets. The Cartesian product $A \times B$ is the set of ordered pairs $(a, b)$ with $a \in A$ , $b \in B$ . Complements are taken inside a universe $U$ that contains every set in the question: $\overline{A} = U ∖ A$ .

SIZE OF THE POWER SET

∣ P (A) ∣ = 2^{∣ A ∣}

For a finite set A; each element is either in or out of a subset.

SIZE OF A CARTESIAN PRODUCT

∣ A \times B ∣ = ∣ A ∣ ∣ B ∣

Finite sets. A relation from A to B is any subset of A × B, so there are $2^{∣ A ∣∣ B ∣}$ of them.

INCLUSION-EXCLUSION FOR TWO SETS

∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣

Finite sets; this is the basis of Venn-diagram counting.

INCLUSION-EXCLUSION FOR THREE SETS

∣ A \cup B \cup C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ - ∣ A \cap B ∣ - ∣ A \cap C ∣ - ∣ B \cap C ∣ + ∣ A \cap B \cap C ∣

Finite sets; add singles, subtract pairs, add the triple.

SIZE OF THE SYMMETRIC DIFFERENCE

∣ A \oplus B ∣ = ∣ A ∣ + ∣ B ∣ - 2 ∣ A \cap B ∣

Finite sets.

Set identities to know

De Morgan: $\overline{A \cup B} = \overline{A} \cap \overline{B}$ and $\overline{A \cap B} = \overline{A} \cup \overline{B}$ .
Distributive: $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ and $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ .
$A ∖ B = A \cap \overline{B}$ .
$A \oplus B = (A \cup B) ∖ (A \cap B)$ ; $\oplus$ is associative and commutative, and $A \oplus A = \emptyset$ .
$A \subseteq B$ if and only if $A \cap B = A$ if and only if $A \cup B = B$ .

EXAM TIP

In Venn-diagram problems first count the region common to all the sets, then work outwards. At the end check that the regions 'in none', 'in exactly one', 'in exactly two' and 'in all three' add up to $∣ U ∣$ .

Countable and uncountable sets

A set is countable if it is finite or can be put in one-to-one correspondence with $N$ (countably infinite). Otherwise it is uncountable. Here $N = {0, 1, 2, \dots}$ ; starting from 1 changes nothing about countability. A subset of a countable set is countable. A countable union of countable sets is countable. A finite Cartesian product of countable sets is countable.

Which common sets are countable

Set	Countable?	Reason in one line
$N$ , $Z$	Yes	List as $0, 1, - 1, 2, - 2, \dots$
$Q$	Yes	Each rational is a pair of integers; list the pairs in a diagonal order
Finite strings over a finite alphabet	Yes	List by length, then alphabetically
Finite subsets of $N$	Yes	For each $k$ , the subsets with largest element $k$ are finitely many; a countable union of finite sets
$R$ , any interval $(a, b)$ with $a < b$	No	Cantor's diagonal argument
$P (N)$	No	Cantor's theorem: $∣ P (A) ∣ > ∣ A ∣$ for every set $A$
All functions $N \to {0, 1}$	No	Same size as $P (N)$ : a subset corresponds to its 0/1 indicator
All functions $N \to N$	No	Contains all functions $N \to {0, 1}$
All infinite binary strings	No	Same as the functions $N \to {0, 1}$

EXAM TIP

Countable union and finite product keep countability. The power set of an infinite set, and the set of all functions from an infinite set to a set with at least two elements, are uncountable. $R ∖ Q$ is uncountable, since removing a countable set from an uncountable one leaves an uncountable set.

Relations and their properties

A relation $R$ on a set $A$ is a subset of $A \times A$ . Write $a R b$ for $(a, b) \in R$ . For $∣ A ∣ = n$ the relation has an $n \times n$ 0/1 matrix $M$ with $M_{ab} = 1$ exactly when $a R b$ . The identity relation is $Δ = {(a, a) : a \in A}$ . The inverse is $R^{- 1} = {(b, a) : (a, b) \in R}$ .

Properties of a relation R on A

Property	Definition	In the matrix
Reflexive	$\forall a (a R a)$	All diagonal entries are 1
Irreflexive	$\forall a \neg (a R a)$	All diagonal entries are 0
Symmetric	$a R b \to b R a$	$M = M^{T}$
Antisymmetric	$(a R b \land b R a) \to a = b$	No pair $a \neq = b$ with $M_{ab} = M_{ba} = 1$
Asymmetric	$a R b \to \neg (b R a)$	Diagonal 0 and no symmetric pair of 1s (irreflexive and antisymmetric)
Transitive	$(a R b \land b R c) \to a R c$	Whenever $M_{ab} = M_{b c} = 1$ then $M_{a c} = 1$

EXAM TIP

Symmetric and antisymmetric are not opposites. The empty relation and the identity relation are both. A relation that is not symmetric need not be antisymmetric. The empty relation is symmetric, antisymmetric, asymmetric, irreflexive and transitive, and is reflexive only when $A = \emptyset$ .

ALL RELATIONS ON AN N-ELEMENT SET

2^{n^{2}}

Each of the $n^{2}$ ordered pairs is in or out.

REFLEXIVE RELATIONS

2^{n (n - 1)}

The n diagonal pairs are forced; the other $n (n - 1)$ are free. Irreflexive relations have the same count.

NEITHER REFLEXIVE NOR IRREFLEXIVE

2^{n^{2}} - 2 \cdot 2^{n (n - 1)}

For $n \geq 1$ , where no relation is both reflexive and irreflexive: subtract the reflexive and the irreflexive relations from all relations.

SYMMETRIC RELATIONS

2^{n (n + 1) /2}

Choose freely for each of the $n$ diagonal pairs and each of the $(2 n)$ unordered pairs ${a, b}$ with $a \neq = b$ .

ANTISYMMETRIC RELATIONS

2^{n} \cdot 3^{n (n - 1) /2}

Diagonal pairs are free ( $2^{n}$ ); each unordered pair ${a, b}$ with $a \neq = b$ has 3 choices: none, $(a, b)$ only, $(b, a)$ only.

ASYMMETRIC RELATIONS

3^{n (n - 1) /2}

Diagonal pairs are excluded; each unordered pair has the same 3 choices. Reflexive and antisymmetric relations have the same count (diagonal forced in instead of out).

REFLEXIVE AND SYMMETRIC RELATIONS

2^{n (n - 1) /2}

Diagonal forced to 1; each unordered pair with $a \neq = b$ is in or out. Irreflexive and symmetric relations have the same count.

RELATIONS BOTH SYMMETRIC AND ANTISYMMETRIC

2^{n}

Such a relation is a subset of the identity relation, so only the diagonal pairs are free.

EXAM TIP

There is no simple closed form for the number of transitive relations on $n$ elements; for $n = 1, 2, 3$ the counts are $2, 13, 171$ , and small cases are done by listing. The other counts above all come from one idea: separate the $n$ diagonal pairs from the $(2 n)$ unordered off-diagonal pairs, and count the choices for each.

WORKED EXAMPLE

How many antisymmetric relations are there on a set with 4 elements?

Solution

Diagonal pairs: 4, each free, giving $2^{4} = 16$ choices.
Unordered pairs ${a, b}$ with $a \neq = b$ : $(2 4) = 6$ , each with 3 choices (none, one direction, other direction), giving $3^{6} = 729$ .
Total: $16 \times 729 = 11664$ .

Answer: 11664

Equivalence relations, closures and composition

An equivalence relation is reflexive, symmetric and transitive. The equivalence class of $a$ is $[a] = {x : x R a}$ . The classes are non-empty, pairwise disjoint and their union is $A$ , so they form a partition of $A$ . Conversely every partition defines an equivalence relation ( $a R b$ when $a$ and $b$ lie in the same block). Equivalence relations on $A$ and partitions of $A$ correspond one to one, and the equivalence relations with exactly $k$ classes correspond to the partitions into $k$ blocks.

EQUIVALENCE RELATIONS ON N ELEMENTS

B_{n} = k = 1 \sum n S (n, k), B_{0}, B_{1}, B_{2}, B_{3}, B_{4}, B_{5} = 1, 1, 2, 5, 15, 52

$B_{n}$ (Bell number) counts partitions of an n-element set; $S (n, k)$ (Stirling number of the second kind) counts partitions into exactly $k$ non-empty blocks.

RECURRENCES FOR BELL AND STIRLING NUMBERS

B_{n + 1} = k = 0 \sum n (k n) B_{k}, S (n, k) = k S (n - 1, k) + S (n - 1, k - 1)

With $S (n, 1) = S (n, n) = 1$ for $n \geq 1$ , and $S (n, n - 1) = (2 n)$ .

PARTITIONS INTO TWO BLOCKS

S (n, 2) = 2^{n - 1} - 1

For $n \geq 2$ : the number of equivalence relations on n elements with exactly two classes.

The reflexive, symmetric and transitive closures of $R$ are the smallest relations containing $R$ with that property. For relations $R$ from $A$ to $B$ and $S$ from $B$ to $C$ , this page writes composition in the same order as functions: $S \circ R = {(a, c) : \exists b (a R b \land b S c)}$ , so $R$ is applied first, just as $g \circ f$ applies $f$ first. Some texts write the same relation as $R \circ S$ ; always read the definition in the question. Powers do not depend on the convention: $R^{1} = R$ and $R^{k + 1} = R^{k} \circ R$ .

Closures and composition

Operation	Formula	Matrix view
Reflexive closure	$R \cup Δ$	Set the diagonal to 1
Symmetric closure	$R \cup R^{- 1}$	$M \lor M^{T}$
Transitive closure $R^{+}$	$R \cup R^{2} \cup \dots \cup R^{n}$ for $∣ A ∣ = n$	Warshall's algorithm, or the union of Boolean powers of $M$
Reflexive-transitive closure	$R^{+} \cup Δ$	Transitive closure with diagonal set to 1
Composition $S \circ R$ ( $R$ first)	${(a, c) : \exists b (a R b \land b S c)}$	Boolean product $M_{R} ⊙ M_{S}$ (AND for multiply, OR for add), in that order

Warshall's algorithm for the transitive closure

Start with the matrix $W = M$ .
For each element $k = 1, \dots, n$ in turn, and for every pair $(i, j)$ : set $W_{ij} = W_{ij} \lor (W_{ik} \land W_{k j})$ .
After the last $k$ , $W$ is the matrix of the transitive closure.

More facts

$(S \circ R)^{- 1} = R^{- 1} \circ S^{- 1}$ , and composition of relations is associative.
The intersection of two equivalence relations on $A$ is an equivalence relation.
The union of two equivalence relations need not be one: on ${1, 2, 3}$ , the relation joining 1 and 2 and the relation joining 2 and 3 have a union containing $(1, 2)$ and $(2, 3)$ but not $(1, 3)$ .

WORKED EXAMPLE

Find the transitive closure of $R = {(1, 2), (2, 3), (3, 1)}$ on $A = {1, 2, 3}$ .

Solution

$R^{2}$ : from $(1, 2), (2, 3)$ get $(1, 3)$ ; from $(2, 3), (3, 1)$ get $(2, 1)$ ; from $(3, 1), (1, 2)$ get $(3, 2)$ . So $R^{2} = {(1, 3), (2, 1), (3, 2)}$ .
$R^{3} = R^{2} \circ R$ : $1 R 2$ and $2 R^{2} 1$ give $(1, 1)$ ; $2 R 3$ and $3 R^{2} 2$ give $(2, 2)$ ; $3 R 1$ and $1 R^{2} 3$ give $(3, 3)$ . So $R^{3} = Δ$ .
$R^{+} = R \cup R^{2} \cup R^{3}$ contains all 9 ordered pairs.

Answer: $R^{+} = A \times A$ (all 9 pairs).

EXAM TIP

For the smallest equivalence relation containing $R$ , take the reflexive and symmetric closures (in either order) and the transitive closure last: the transitive closure of a reflexive, symmetric relation stays reflexive and symmetric. Taking the symmetric closure after the transitive one can lose transitivity: ${(1, 2)}$ is transitive, but its symmetric closure ${(1, 2), (2, 1)}$ is not, since it lacks $(1, 1)$ .

Functions and counting functions

A function $f : A \to B$ assigns to every $a \in A$ exactly one $f (a) \in B$ ; $A$ is the domain, $B$ the codomain and $f (A) = {f (a) : a \in A}$ the range. It is injective (one-to-one) if $f (a_{1}) = f (a_{2})$ implies $a_{1} = a_{2}$ ; surjective (onto) if every $b \in B$ equals $f (a)$ for some $a$ ; bijective if both. The composition $g \circ f$ means apply $f$ first: $(g \circ f) (a) = g (f (a))$ . A function has an inverse function exactly when it is a bijection.

Facts about composition

If $g \circ f$ is injective then $f$ is injective (nothing is said about $g$ ).
If $g \circ f$ is surjective then $g$ is surjective (nothing is said about $f$ ).
So if $g \circ f$ is a bijection, $f$ is injective and $g$ is surjective.
The composition of injective functions is injective; of surjective functions is surjective; of bijections is a bijection.
$(g \circ f)^{- 1} = f^{- 1} \circ g^{- 1}$ for bijections $f, g$ .
A function between finite sets of the same size is injective if and only if it is surjective.

ALL FUNCTIONS FROM A TO B

∣ B ∣^{∣ A ∣}

Each element of $A$ independently picks an image.

INJECTIVE FUNCTIONS

\frac{n !}{( n - m )!} = n (n - 1) \dots (n - m + 1)

$m = ∣ A ∣$ , $n = ∣ B ∣$ , $m \leq n$ ; when $m > n$ there are none (the product form gives 0).

BIJECTIONS BETWEEN SETS OF EQUAL SIZE

n!

$∣ A ∣ = ∣ B ∣ = n$ ; this is also the number of permutations of an n-set.

SURJECTIVE FUNCTIONS (INCLUSION-EXCLUSION)

k = 0 \sum n (- 1)^{k} (k n) (n - k)^{m} = n! S (m, n)

$m = ∣ A ∣$ , $n = ∣ B ∣$ ; zero when $m < n$ .

PARTIAL FUNCTIONS FROM A TO B

(n + 1)^{m}

$m = ∣ A ∣$ , $n = ∣ B ∣$ ; each element of $A$ maps to one of the $n$ elements or is left undefined.

WORKED EXAMPLE

How many surjective functions are there from a 5-element set onto a 3-element set?

Solution

Here $m = 5$ , $n = 3$ .
Count all functions: $3^{5} = 243$ .
Subtract functions missing at least one of the 3 targets: $(1 3) 2^{5} = 96$ .
Add back functions missing two targets (counted twice): $(2 3) 1^{5} = 3$ .
Functions missing all three targets: none, since $0^{5} = 0$ .
Total: $243 - 96 + 3 = 150$ .

Answer: 150

EXAM TIP

The definition of the domain and codomain matters: the same rule can be onto for one codomain and not onto for another. Also check whether a question counts functions from $A$ to $B$ or from $B$ to $A$ ; the formulas for injective and surjective counts use $m = ∣ A ∣$ (domain) and $n = ∣ B ∣$ (codomain).

Partial orders and Hasse diagrams

A partial order is a relation that is reflexive, antisymmetric and transitive; the pair $(A, ⪯)$ is a poset. Elements $a, b$ are comparable if $a ⪯ b$ or $b ⪯ a$ . The poset is a total order (chain) if any two elements are comparable. Element $b$ covers $a$ if $a ≺ b$ and no element $c$ has $a ≺ c ≺ b$ . A Hasse diagram draws one vertex per element and an edge from $a$ up to $b$ exactly when $b$ covers $a$ , leaving out the loops and all edges implied by transitivity. On this page a Hasse diagram is given by its list of covers.

Special elements of a poset (A, ⪯) and a subset S

Term	Meaning
Maximal element	$m$ with no $x \in A$ such that $m ≺ x$ (there can be several)
Minimal element	$m$ with no $x \in A$ such that $x ≺ m$ (there can be several)
Greatest element	An element $g$ with $x ⪯ g$ for all $x \in A$ (at most one; it is the only maximal element)
Least element	An element $l$ with $l ⪯ x$ for all $x \in A$ (at most one; it is the only minimal element)
Upper bound of S	An element $u \in A$ with $s ⪯ u$ for all $s \in S$
Lower bound of S	An element $l \in A$ with $l ⪯ s$ for all $s \in S$
Least upper bound (join) of S	The least element of the set of upper bounds, if it exists
Greatest lower bound (meet) of S	The greatest element of the set of lower bounds, if it exists

EXAM TIP

A finite non-empty poset always has at least one maximal and one minimal element, and it has a greatest element exactly when it has only one maximal element. In an infinite poset a unique maximal element need not be greatest: in $N$ with its usual order plus one extra element $m$ comparable to nothing else, $m$ is the only maximal element but is not greatest.

SUBSETS OF AN N-SET ORDERED BY INCLUSION

Hasse diagram edges = n 2^{n - 1}

Poset $(P (A), \subseteq)$ with $∣ A ∣ = n$ : $S$ is covered by $S \cup {x}$ for each $x \in / S$ .

DIVISIBILITY ON THE DIVISORS OF N

N = p_{1}^{a_{1}} \dots p_{k}^{a_{k}} \Rightarrow number of divisors = i = 1 \prod k (a_{i} + 1)

Poset of positive divisors under 'divides' ( $p_{i}$ distinct primes); join is lcm and meet is gcd.

HASSE DIAGRAM EDGES FOR THE DIVISORS OF N

i = 1 \sum k a_{i} j \neq = i \prod (a_{j} + 1)

$N = p_{1}^{a_{1}} \dots p_{k}^{a_{k}}$ ; $d$ is covered by $d p_{i}$ whenever $d p_{i}$ divides $N$ . For $N = 12 = 2^{2} \cdot 3$ : $2 \cdot 2 + 1 \cdot 3 = 7$ .

Chains and antichains

A chain is a subset in which any two elements are comparable; an antichain is a subset in which no two distinct elements are comparable.
In a finite poset, the largest size of an antichain equals the smallest number of chains that together cover the poset.
In a finite poset, the largest number of elements in a chain equals the smallest number of antichains that together cover the poset.
In $(P (A), \subseteq)$ with $∣ A ∣ = n$ , the largest antichain has $(⌊ n /2 ⌋ n)$ elements (all subsets of size $⌊ n /2 ⌋$ ).

Every finite poset has a linear extension (a total order that keeps all the given comparisons), found by repeatedly removing a minimal element. This is topological sorting. Partial orders have no simple counting formula: the number of partial orders on a labelled set of 1, 2, 3, 4 elements is 1, 3, 19, 219. The number of total orders on an n-element set is $n!$ .

Lattices and Boolean algebras

A lattice is a poset in which every pair of elements $a, b$ has a join $a \lor b$ (least upper bound) and a meet $a \land b$ (greatest lower bound). Every finite non-empty lattice has a greatest element $1$ and a least element $0$ , so it is bounded. In a bounded lattice, $b$ is a complement of $a$ if $a \lor b = 1$ and $a \land b = 0$ . The lattice is complemented if every element has at least one complement. It is distributive if $a \land (b \lor c) = (a \land b) \lor (a \land c)$ for all $a, b, c$ (the dual identity then holds too). A sublattice is a subset closed under the lattice's own join and meet.

Quick tests for common lattices

Lattice	Join / meet	Distributive?	Complemented?
Chain with $\geq 1$ element	max / min	Yes	Only if it has at most 2 elements
$(P (A), \subseteq)$	$\cup$ / $\cap$	Yes	Yes (complement is set complement); a Boolean algebra
Positive divisors of $N$ under divisibility	lcm / gcd	Yes	Exactly when $N$ is square-free (no repeated prime); then a Boolean algebra
Diamond $M_{3}$	Read from the covers below	No	Yes (each atom has two complements)
Pentagon $N_{5}$	Read from the covers below	No	Yes ( $c$ has two complements, $a$ and $b$ )

Covers of the diamond and the pentagon

Lattice	Elements	Covers ( $x ≺ y$ means $y$ covers $x$ )
Diamond $M_{3}$	$0, a, b, c, 1$	$0 ≺ a$ , $0 ≺ b$ , $0 ≺ c$ , $a ≺ 1$ , $b ≺ 1$ , $c ≺ 1$
Pentagon $N_{5}$	$0, a, b, c, 1$	$0 ≺ a$ , $a ≺ b$ , $b ≺ 1$ , $0 ≺ c$ , $c ≺ 1$

Facts and tests

A lattice is distributive if and only if it has no sublattice isomorphic to the diamond $M_{3}$ or the pentagon $N_{5}$ .
A lattice is modular if $a ⪯ c$ implies $a \lor (b \land c) = (a \lor b) \land c$ . It is modular if and only if it has no sublattice isomorphic to $N_{5}$ . Every distributive lattice is modular; $M_{3}$ is modular but not distributive.
In a bounded distributive lattice an element has at most one complement.
A Boolean algebra is a complemented distributive lattice. A finite Boolean algebra has $2^{k}$ elements and is isomorphic to the power set of a $k$ -element set.
A finite poset is a lattice when every pair has a join and a meet. Shortcut: a finite poset with a least element in which every pair has a join is a lattice; dually, a finite poset with a greatest element in which every pair has a meet is a lattice.
Lattice laws: idempotent $a \lor a = a$ ; commutative; associative; absorption $a \lor (a \land b) = a$ and $a \land (a \lor b) = a$ .

WORKED EXAMPLE

Consider the divisors of $30$ under divisibility, and the divisors of $12$ under divisibility. Decide for each whether it is a Boolean algebra.

Solution

Divisors of 30: $30 = 2 \cdot 3 \cdot 5$ is square-free, with $2^{3} = 8$ divisors; it is a distributive lattice (lcm and gcd) and every divisor $d$ has complement $30/ d$ , since $g cd (d, 30/ d) = 1$ and $lcm (d, 30/ d) = 30$ .
So the divisors of 30 form a Boolean algebra, isomorphic to $P ({2, 3, 5})$ .
Divisors of 12: $12 = 2^{2} \cdot 3$ is not square-free; the divisors are $1, 2, 3, 4, 6, 12$ .
Take the element $2$ : we need $y$ with $lcm (2, y) = 12$ and $g cd (2, y) = 1$ . Then $y$ must be odd, so $lcm (2, y)$ has only one factor of 2, which cannot be $12$ .
So $2$ has no complement; the lattice is distributive but not complemented, hence not a Boolean algebra.

Answer: Divisors of 30: Boolean algebra. Divisors of 12: distributive but not complemented, so not a Boolean algebra.

PREVIOUS-YEAR QUESTIONS

8 questions from the CS papers

Try each question first, then open the answer. We placed each question under a topic ourselves; the exam paper does not label topics.

See these papers in full: GATE CSE 2026 Set 2 · GATE CSE 2025 Set 1 · GATE CSE 2025 Set 2 · GATE CSE 2024 Set 1 · GATE CSE 2024 Set 2 · GATE CSE 2023 · GATE CSE 2020 · GATE CSE 2018

GATE 2026 CS2 Q.26

GATE 2026 · CS2Q.26 · 1 mark · MSQ

Let $R$ be a binary relation on the set ${1, 2, \dots, 10}$ , where $(x, y) \in R$ if the product of $x$ and $y$ is square of an integer. Which of the following properties is/are satisfied by $R$ ?

(A)
Reflexive
(B)
Symmetric
(C)
Transitive
(D)
Antisymmetric

Answer and solution

GATE 2026 CS2 Q.26: answer and solution

See the question in the paper

Tap to open full size

GATE 2026 CS2 Q.26: answer and solution

GATE 2025 CS1 Q.17

GATE 2025 · CS1Q.17 · 1 mark · MCQ

$g (\cdot)$ is a function from $A$ to $B$ , $f (\cdot)$ is a function from $B$ to $C$ , and their composition defined as $f (g (\cdot))$ is a mapping from $A$ to $C$ .

If $f (\cdot)$ and $f (g (\cdot))$ are onto (surjective) functions, which ONE of the following is TRUE about the function $g (\cdot)$ ?

(A)
$g (\cdot)$ must be an onto (surjective) function.
(B)
$g (\cdot)$ must be a one-to-one (injective) function.
(C)
$g (\cdot)$ must be a bijective function, that is, both one-to-one and onto.
(D)
$g (\cdot)$ is not required to be a one-to-one or onto function.

Answer and solution

GATE 2025 CS1 Q.17: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS1 Q.17: answer and solution

GATE 2025 CS2 Q.42

GATE 2025 · CS2Q.42 · 2 marks · MSQ

Let $F$ be the set of all functions from ${1, \dots, n}$ to ${0, 1}$ . Define the binary relation $≼$ on $F$ as follows:

$\forall f, g \in F, f ≼ g$ if and only if $\forall x \in {1, \dots, n}, f (x) \leq g (x)$ , where $0 \leq 1$ .

Which of the following statement(s) is/are TRUE?

(A)
$≼$ is a symmetric relation
(B)
$(F, ≼)$ is a partial order
(C)
$(F, ≼)$ is a lattice
(D)
$≼$ is an equivalence relation

Answer and solution

GATE 2025 CS2 Q.42: answer and solution

See the question in the paper

Tap to open full size

GATE 2025 CS2 Q.42: answer and solution

GATE 2024 CS1 Q.32

GATE 2024 · CS1Q.32 · 1 mark · NAT

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 \times A$ to $A \cup B$ . The number of possible values of $∣ A ∣$ is ______

Answer and solution

GATE 2024 CS1 Q.32: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS1 Q.32: answer and solution

GATE 2024 CS2 Q.34

GATE 2024 · CS2Q.34 · 1 mark · NAT

Let $P$ be the partial order defined on the set ${1, 2, 3, 4}$ as follows

P = {(x, x) ∣ x \in {1, 2, 3, 4}} \cup {(1, 2), (3, 2), (3, 4)}

The number of total orders on ${1, 2, 3, 4}$ that contain $P$ is __________

Answer and solution

GATE 2024 CS2 Q.34: answer and solution

See the question in the paper

Tap to open full size

GATE 2024 CS2 Q.34: answer and solution

GATE 2023 CS Q.49

GATE 2023 · CSQ.49 · 2 marks · MSQ

Let $f : A \to B$ be an onto (or surjective) function, where $A$ and $B$ are nonempty sets. Define an equivalence relation $\sim$ on the set $A$ as

a_{1} \sim a_{2} if f (a_{1}) = f (a_{2}),

where $a_{1}, a_{2} \in A$ . Let $E = {[x] : x \in A}$ be the set of all the equivalence classes under $\sim$ . Define a new mapping $F : E \to B$ as

F ([x]) = f (x), for all the equivalence classes [x] in E .

Which of the following statements is/are TRUE?

(A)
$F$ is NOT well-defined.
(B)
$F$ is an onto (or surjective) function.
(C)
$F$ is a one-to-one (or injective) function.
(D)
$F$ is a bijective function.

Answer and solution

GATE 2023 CS Q.49: answer and solution

See the question in the paper

Tap to open full size

GATE 2023 CS Q.49: answer and solution

GATE 2020 CS Q.17

GATE 2020 · CSQ.17 · 1 mark · NAT

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 ______.

Answer and solution

GATE 2020 CS Q.17: answer and solution

See the question in the paper

Tap to open full size

GATE 2020 CS Q.17: answer and solution

GATE 2018 CS Q.27

GATE 2018 · CSQ.27 · 2 marks · MCQ

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?

(A)
$Q$ and $S$ only
(B)
$P$ and $S$ only
(C)
$P$ and $R$ only
(D)
$P$ , $Q$ and $S$ only

Answer and solution

GATE 2018 CS Q.27: answer and solution

See the question in the paper

Tap to open full size

GATE 2018 CS Q.27: answer and solution

PRACTICE

6 questions to test yourself

PRACTICE 12 marks · NAT

How many asymmetric relations are there on a set with exactly 4 elements? (A relation $R$ on $A$ is asymmetric if $(a, b) \in R$ implies $(b, a) \in / R$ for all $a, b \in A$ , including $a = b$ .)

Answer and solution

Answer: $729$

Asymmetric forces the diagonal pairs out, so no diagonal pair is in $R$ .
There are $(2 4) = 6$ unordered pairs ${a, b}$ with $a \neq = b$ .
Each has 3 choices: neither, $(a, b)$ only, or $(b, a)$ only.
Total $= 3^{6} = 729$ .

PRACTICE 22 marks · MCQ

Let $L$ be the set of positive divisors of $60$ ordered by divisibility. Which statement is true?

(A)
$L$ is a lattice, is distributive, and is complemented
(B)
$L$ is a lattice, is distributive, but is not complemented
(C)
$L$ is a lattice but is not distributive
(D)
$L$ is not a lattice

Answer and solution

Answer: (B)

Any two divisors have an lcm (join) and a gcd (meet) among the divisors, so $L$ is a lattice, and it is distributive because gcd and lcm distribute over each other.
$60 = 2^{2} \cdot 3 \cdot 5$ is not square-free, so $L$ is not complemented.
Direct check: for $2$ we need $y$ with $g cd (2, y) = 1$ and $lcm (2, y) = 60$ ; the second needs $4 ∣ y$ , which contradicts the first.
So the answer is B.

PRACTICE 32 marks · NAT

How many surjective functions are there from a set with 4 elements onto a set with 3 elements?

Answer and solution

Answer: $36$

Use inclusion-exclusion with $m = 4$ , $n = 3$ : $3^{4} - (1 3) 2^{4} + (2 3) 1^{4} - (3 3) 0^{4}$ .
$= 81 - 48 + 3 - 0 = 36$ .
Check: $3! S (4, 3) = 6 \times 6 = 36$ .

PRACTICE 41 mark · NAT

How many equivalence relations on the set ${1, 2, 3, 4}$ have exactly two equivalence classes?

Answer and solution

Answer: $7$

Equivalence relations with exactly two classes correspond to partitions into two non-empty blocks.
The count is $S (4, 2) = 2^{4 - 1} - 1 = 7$ .
Check by block sizes: one block of size 1 and one of size 3 gives 4 partitions; two blocks of size 2 gives $\frac{1}{2} (2 4) = 3$ ; total $4 + 3 = 7$ .

PRACTICE 51 mark · MCQ

Consider the poset of all subsets of ${a, b, c}$ ordered by inclusion. How many edges does its Hasse diagram have?

(A)
9
(B)
12
(C)
16
(D)
27

Answer and solution

Answer: (B)

An edge joins $S$ to $S \cup {x}$ for $x \in / S$ (a cover).
Total edges $= n 2^{n - 1} = 3 \times 4 = 12$ .
Check by levels: sizes 0 to 1 give 3 edges, 1 to 2 give 6 edges, 2 to 3 give 3 edges, total 12.

PRACTICE 61 mark · MSQ

Let $R$ be the relation on the set of integers $Z$ defined by $a R b$ if and only if $∣ a - b ∣ \leq 1$ . Which of the following properties does $R$ have?

(A)
Reflexive
(B)
Symmetric
(C)
Antisymmetric
(D)
Transitive

Answer and solution

Answer: (A), (B)

$∣ a - a ∣ = 0 \leq 1$ , so $R$ is reflexive.
$∣ a - b ∣ = ∣ b - a ∣$ , so $R$ is symmetric.
$1 R 2$ and $2 R 1$ but $1 \neq = 2$ , so not antisymmetric.
$1 R 2$ and $2 R 3$ but $∣1 - 3∣ = 2 > 1$ , so not transitive.
Correct options: A and B.

OFFICIAL GATE 2027 SYLLABUS WORDING

Copied from the GATE 2027 syllabus; see all 2027 syllabi.

GATE CS

Sets, relations, functions, partial orders and lattices

Preparing in Kolkata? IAE Academy's course for GATE CSE.