Sets, Relations, Functions and Order Structures PYQs for GATE CS

Solve 8+ Sets, Relations, Functions and Order Structures previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Discrete Structures

Chapter Roadmap

Discrete Structures

1. Function Properties, Composition & Cardinality

Mapping elements, counting functions, and analyzing composed operations.

2. Relation Properties & Equivalence Conditions

Reflexivity, symmetry, transitivity, and the precise rules of equivalence.

3. Equivalence Relations & Quotient Mappings

Partitioning sets into equivalence classes and mapping them cleanly.

4. Partial Orders, Linear Extensions & Lattices

Hierarchies, Hasse diagrams, and finding bounds in ordered sets.

Functions as Precise Machines

A function $f : A \to B$ is a specific type of relation that assigns exactly one element of $B$ to each element of $A$ .

The Three Key Sets

Domain ( $A$ ): The set of all valid inputs. Every element here must be mapped.
Codomain ( $B$ ): The set of all possible outputs. It defines the boundaries of the function.
Range (or Image): The set of actual outputs produced. It is always a subset of the codomain ( $Range \subseteq B$ ).

Mathematical Condition:
If

(x, y_{1}) \in f

and

(x, y_{2}) \in f

, then

y_{1} = y_{2}

.
(An input cannot have multiple outputs).

Sets, Relations, Functions and Order Structures: Solved Questions with Step-by-Step Explanations (8 Problems)

Question 1 · Engineering Mathematics · 2026_Set2 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

Correct Answer:

["A","B","C"]

Step-by-Step Solution

Key idea: This is a relation properties question, recognizable by the condition that the product of two elements is a perfect square.

Step 1: Check Reflexivity. For any $x \in {1, \dots, 10}$ , $x \cdot x = x^{2}$ , which is a perfect square. Thus, $(x, x) \in R$ . Reflexive is TRUE.

Step 2: Check Symmetry. If $(x, y) \in R$ , then $x \cdot y = k^{2}$ . Since multiplication is commutative, $y \cdot x = k^{2}$ , so $(y, x) \in R$ . Symmetric is TRUE.

Step 3: Check Transitivity. Suppose $(x, y) \in R$ and $(y, z) \in R$ . Then $x \cdot y = a^{2}$ and $y \cdot z = b^{2}$ for some integers $a, b$ . We need to check if $x \cdot z$ is a perfect square. Notice that $(x \cdot y) (y \cdot z) = a^{2} b^{2} ⟹ x \cdot z \cdot y^{2} = (ab)^{2} ⟹ x \cdot z = (ab / y)^{2}$ . For $x \cdot z$ to be an integer square, $y$ must divide $ab$ . Let the prime factorization of $y$ have $p^{e}$ . Since $y ∣ a^{2}$ , $e \leq 2 α$ (where $p^{α} ∣∣ a$ ). Similarly, $e \leq 2 β$ (where $p^{β} ∣∣ b$ ). We need $e \leq α + β$ . This is always true because if $e > α + β$ , then $2 e > 2 α + 2 β$ , which contradicts $e \leq 2 α$ and $e \leq 2 β$ . Thus, $y$ always divides $ab$ , making $ab / y$ an integer. Therefore, $x \cdot z$ is always a perfect square. Transitive is TRUE.

Step 4: Check Antisymmetry. $(1, 4) \in R$ since $1 \cdot 4 = 2^{2}$ , and $(4, 1) \in R$ , but $1 \neq = 4$ . Thus, it is NOT antisymmetric.

Answer: Options A, B, and C.

Question 2 · Engineering Mathematics · 2025_Set2 MSQ

Let

F

be the set of all functions from

{1, \dots, n}

{0, 1}

. Define the binary relation

⪯

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

Correct Answer:

["B","C"]

Step-by-Step Solution

Key idea: This is a poset and lattice identification question on a function space, recognizable by the pointwise ordering of functions.

Step 1: Analyze the relation $⪯$ . $f ⪯ g$ iff $f (x) \leq g (x)$ for all $x \in {1, \dots, n}$ .

Step 2: Check if it's a partial order (Option B).

Reflexive: $f (x) \leq f (x)$ is true for all $x$ .
Antisymmetric: $f ⪯ g$ and $g ⪯ f ⟹ f (x) = g (x)$ for all $x ⟹ f = g$ .
Transitive: $f ⪯ g$ and $g ⪯ h ⟹ f (x) \leq h (x) ⟹ f ⪯ h$ .

Thus, $(F, ⪯)$ is a partial order. Option B is true.

Step 3: Check if it's a lattice (Option C). For any $f, g \in F$ , we can define the pointwise maximum $(f \lor g) (x) = max (f (x), g (x))$ and pointwise minimum $(f \land g) (x) = min (f (x), g (x))$ . Since the codomain is ${0, 1}$ , these are well-defined functions in $F$ and satisfy the properties of join and meet. Thus, it is a lattice. Option C is true.

Step 4: Check symmetry (Option A) and equivalence (Option D). $f ⪯ g$ does not imply $g ⪯ f$ (e.g., $f (x) = 0, g (x) = 1$ ). So it's not symmetric, hence not an equivalence relation. Options A and D are false.

Answer: Options B and C.

Question 3 · Engineering Mathematics · 2025_Set1 MCQ

g (.)

is a function from

A

B

f (.)

is a function from

B

C

, and their composition defined as

f (g (.))

is a mapping from

A

C

.

If

f (.)

and

f (g (.))

are onto (surjective) functions, which ONE of the following is TRUE about the function

g (.)

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

Correct Answer:

Step-by-Step Solution

Key idea: This is a function composition property question, recognizable by the given surjectivity of $f$ and $f \circ g$ .

Step 1: Analyze the given conditions. We know $f : B \to C$ is onto, and $f \circ g : A \to C$ is onto.

Step 2: Test if $g$ must be onto. Consider $A = {1}$ , $B = {1, 2}$ , $C = {1}$ . Let $g (1) = 1$ and $f (1) = f (2) = 1$ . Here, $f$ is onto and $f (g (1)) = 1$ is onto, but $g$ is not onto (2 is not in the range of $g$ ). Thus, $g$ is not required to be onto.

Step 3: Test if $g$ must be one-to-one. Consider $A = {1, 2}$ , $B = {1}$ , $C = {1}$ . Let $g (1) = g (2) = 1$ and $f (1) = 1$ . Here, $f$ is onto and $f \circ g$ is onto, but $g$ is not one-to-one.

Step 4: Since $g$ is neither required to be onto nor one-to-one, Option D is the only necessarily true statement.

Answer: Option D.

Question 4 · Engineering Mathematics · 2024_Set2 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 __________

Correct Answer:

Step-by-Step Solution

Key idea: This is a counting linear extensions question, recognizable by the request for the number of total orders containing a given partial order.

Step 1: Identify the cover relations (dependencies) from $P$ . The non-reflexive pairs are $(1, 2)$ , $(3, 2)$ , and $(3, 4)$ . This means in any valid total order, 1 must appear before 2, 3 must appear before 2, and 3 must appear before 4.

Step 2: A valid total order (linear extension) is a permutation of ${1, 2, 3, 4}$ that respects these dependencies.

Step 3: The minimal elements (those with no prerequisites) are 1 and 3. So the sequence must start with either 1 or 3.

Case 1: The sequence starts with 1. The remaining elements are ${2, 3, 4}$ . Since 3 must precede both 2 and 4, 3 must be the next element. The remaining elements ${2, 4}$ have no dependencies between them, so they can be arranged in $2! = 2$ ways: $(1, 3, 2, 4)$ and $(1, 3, 4, 2)$ .

Case 2: The sequence starts with 3. The remaining elements are ${1, 2, 4}$ . The only remaining dependency is $1 ≺ 2$ . The number of valid permutations of 3 elements with one specific order constraint is $3! /2 = 3$ . These are: $(3, 1, 2, 4)$ , $(3, 1, 4, 2)$ , and $(3, 4, 1, 2)$ .

Step 4: Total linear extensions = 2 (from Case 1) + 3 (from Case 2) = 5.

Answer: 5.

Question 5 · Engineering Mathematics · 2024_Set1 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 __________

Correct Answer:

Step-by-Step Solution

Key idea: This is a cardinality and bijection constraint question, recognizable by the existence of bijections between Cartesian products and set unions.

Step 1: Let $∣ A ∣ = a$ and $∣ B ∣ = b$ . Since there is a bijection from $A$ to $B$ , we must have $∣ A ∣ = ∣ B ∣$ , so $b = a$ .

Step 2: Since there is a bijection from $A \times A$ to $A \cup B$ , their cardinalities must be equal. Thus, $∣ A \times A ∣ = ∣ A \cup B ∣$ .

Step 3: We know $∣ A \times A ∣ = a^{2}$ . The size of the union is $∣ A \cup B ∣ = ∣ A ∣ + ∣ B ∣ - ∣ A \cap B ∣ = 2 a - k$ , where $k = ∣ A \cap B ∣$ .

Step 4: Since $A \cap B$ is a subset of $A$ , the intersection size $k$ must satisfy $0 \leq k \leq a$ .

Step 5: Equating the cardinalities gives $a^{2} = 2 a - k$ , which means $k = 2 a - a^{2}$ .

Step 6: Apply the bounds on $k$ :

$0 \leq 2 a - a^{2} \leq a$

From $2 a - a^{2} \geq 0$ , we get $a (2 - a) \geq 0$ . Since $a \geq 1$ (non-empty), $a \leq 2$ .

From $2 a - a^{2} \leq a$ , we get $a - a^{2} \leq 0 ⟹ a (1 - a) \leq 0$ . Since $a \geq 1$ , this is always true.

Step 7: The possible integer values for $a$ are 1 and 2.

If $a = 1$ , $k = 1$ (sets are identical).
If $a = 2$ , $k = 0$ (sets are disjoint).

Both are valid. The number of possible values for $∣ A ∣$ is 2.

Answer: 2.

Question 6 · Engineering Mathematics · 2023 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

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

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.

Correct Answer:

["B","C","D"]

Step-by-Step Solution

Key idea: This is a quotient mapping question, recognizable by the definition of an equivalence relation based on a function's output and the induced mapping on equivalence classes.

Step 1: Check if $F$ is well-defined. Suppose $[x] = [y]$ . By the definition of the equivalence relation, this means $x \sim y$ , which implies $f (x) = f (y)$ . Therefore, $F ([x]) = f (x) = f (y) = F ([y])$ . The output does not depend on the choice of representative, so $F$ is well-defined. Option A is FALSE.

Step 2: Check if $F$ is onto. We are given that $f : A \to B$ is onto. For any $b \in B$ , there exists some $a \in A$ such that $f (a) = b$ . Then $F ([a]) = f (a) = b$ . Thus, $F$ is onto. Option B is TRUE.

Step 3: Check if $F$ is one-to-one. Suppose $F ([x]) = F ([y])$ . This means $f (x) = f (y)$ . By the definition of the equivalence relation, $f (x) = f (y)$ implies $x \sim y$ , which means $[x] = [y]$ . Thus, $F$ is one-to-one. Option C is TRUE.

Step 4: Since $F$ is both one-to-one and onto, it is bijective. Option D is TRUE.

Answer: Options B, C, and D.

Question 7 · Engineering Mathematics · 2021_Set2 MSQ

Consider the following sets, where

n \geq 2

S_{1}

: Set of all

n \times n

matrices with entries from the set

{a, b, c}

S_{2}

: Set of all functions from the set

{0, 1, 2, \dots, n^{2} - 1}

to the set

{0, 1, 2}

Which of the following choice(s) is/are correct?

A.
There does not exist a bijection from $S_{1}$ to $S_{2}$ .
B.
There exists a surjection from $S_{1}$ to $S_{2}$ .
C.
There exists a bijection from $S_{1}$ to $S_{2}$ .
D.
There does not exist an injection from $S_{1}$ to $S_{2}$ .

Correct Answer:

["B","C"]

Step-by-Step Solution

Key idea: This is a cardinality comparison question, recognizable by the need to compare the sizes of two differently described sets.

Step 1: Calculate the cardinality of $S_{1}$ . An $n \times n$ matrix has $n^{2}$ entries. Each entry can be independently chosen from the set ${a, b, c}$ , which has 3 elements. Thus, $∣ S_{1} ∣ = 3^{n^{2}}$ .

Step 2: Calculate the cardinality of $S_{2}$ . The set of all functions from a domain of size $k$ to a codomain of size $m$ is $m^{k}$ . Here, the domain is ${0, 1, \dots, n^{2} - 1}$ , which has size $n^{2}$ . The codomain is ${0, 1, 2}$ , which has size 3. Thus, $∣ S_{2} ∣ = 3^{n^{2}}$ .

Step 3: Compare the cardinalities. Since $∣ S_{1} ∣ = ∣ S_{2} ∣ = 3^{n^{2}}$ and both are finite sets, there exists a bijection between them.

Step 4: Evaluate the options. Since a bijection exists, Option C is true. A bijection is also a surjection, so Option B is true. Options A and D are false because they claim a bijection or injection does not exist.

Answer: Options B and C.

Question 8 · Engineering Mathematics · 2021_Set1 MSQ

A relation

R

is said to be circular if

a R b

and

b R c

together imply

c R a

.
Which of the following options is/are correct?

A.
If a relation S is reflexive and symmetric, then S is an equivalence relation.
B.
If a relation S is circular and symmetric, then S is an equivalence relation.
C.
If a relation S is reflexive and circular, then S is an equivalence relation.
D.
If a relation S is transitive and circular, then S is an equivalence relation.

Correct Answer:

["C"]

Step-by-Step Solution

Key idea: This is a relation property equivalence question, recognizable by the definition of a circular relation and the conditions for an equivalence relation.

Step 1: Recall the definition of an equivalence relation: it must be reflexive, symmetric, and transitive.

Step 2: Analyze Option A. Reflexive and symmetric do not guarantee transitive (e.g., a path of length 2 in a graph without the closing edge). False.

Step 3: Analyze Option B. Circular and symmetric. Circular means $a R b \land b R c ⟹ c R a$ . With symmetry, $c R a ⟹ a R c$ , so it is transitive. However, it lacks reflexivity (e.g., the empty relation on a non-empty set is circular and symmetric but not reflexive). False.

Step 4: Analyze Option C. Reflexive and circular.

Symmetry: $a R b$ . Since reflexive, $b R b$ . By circularity, $a R b \land b R b ⟹ b R a$ . So symmetric.
Transitivity: $a R b \land b R c$ . By circularity, $c R a$ . By symmetry, $a R c$ . So transitive.

Since it is reflexive, symmetric, and transitive, it is an equivalence relation. True.

Step 5: Analyze Option D. Transitive and circular. Lacks reflexivity (e.g., the empty relation). False.

Answer: Option C.

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Sets, Relations, Functions and Order Structures PYQs for GATE CS

Chapter Roadmap: Discrete Structures

Chapter Roadmap

1. Function Properties, Composition & Cardinality

2. Relation Properties & Equivalence Conditions

3. Equivalence Relations & Quotient Mappings

4. Partial Orders, Linear Extensions & Lattices

Functions as Precise Machines

Functions as Precise Machines

The Three Key Sets

Sets, Relations, Functions and Order Structures: Solved Questions with Step-by-Step Explanations (8 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit