Sets, Relations, Functions and Order Structures Practice Questions for GATE CS

Solve 133+ Sets, Relations, Functions and Order Structures practice 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 (10 Problems)

Question 1 · Engineering Mathematics MCQ

Let $g : A \to B$ and $f : B \to C$ be functions such that their composition $f \circ g : A \to C$ is injective. Which of the following properties MUST hold for the individual functions?

A.
$f$ must be injective
B.
$g$ must be injective
C.
$f$ must be surjective
D.
$g$ must be surjective

Correct Answer:

Step-by-Step Solution

Key idea: This is a composition properties question, recognizable by the given injectivity of a composite function $f \circ g$ .

Step 1: Recall the definition of injectivity for $f \circ g$ . If $(f \circ g) (x_{1}) = (f \circ g) (x_{2})$ , then $x_{1} = x_{2}$ .

Step 2: This means $f (g (x_{1})) = f (g (x_{2})) ⟹ x_{1} = x_{2}$ . For this to hold, $g$ must map distinct $x_{1}, x_{2}$ to distinct values $g (x_{1}), g (x_{2})$ . Thus, $g$ must be injective.

Step 3: Does $f$ need to be injective? No. $f$ only needs to be injective on the range of $g$ . It can map other elements of $B$ to the same values.

Step 4: Does $g$ need to be surjective? No. $g$ can leave some elements of $B$ unmapped, as long as the elements it does map are distinct.

Answer: Option B.

Question 2 · Engineering Mathematics MCQ

Let $g : A \to B$ and $f : B \to C$ be functions. If the composition $f \circ g$ is surjective (onto), which of the following MUST be true?

A.
$g$ must be surjective
B.
$f$ must be surjective
C.
$g$ must be injective
D.
$f$ must be injective

Correct Answer:

Step-by-Step Solution

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

Step 1: Recall the definition of surjectivity for $f \circ g$ . The range of $f \circ g$ must equal the codomain $C$ .

Step 2: The outputs of $f \circ g$ are produced by applying $f$ to the outputs of $g$ . For $f \circ g$ to cover all of $C$ , the function $f$ must be able to map the elements it receives from $g$ to all of $C$ .

Step 3: This implies that $f$ itself must be surjective. If $f$ were not surjective, there would be some element in $C$ that $f$ cannot reach, meaning $f \circ g$ could not reach it either.

Step 4: Does $g$ need to be surjective? No. $g$ only needs to provide enough elements for $f$ to cover $C$ . $g$ can leave some elements of $B$ unmapped.

Answer: Option B.

Question 3 · Engineering Mathematics MCQ

If there exists a bijective function $f : A \to B$ between two finite sets $A$ and $B$ , which of the following must be true?

A.
$∣ A ∣ > ∣ B ∣$
B.
$∣ A ∣ < ∣ B ∣$
C.
$∣ A ∣ = ∣ B ∣$
D.
$|A|

eq |B|$

Correct Answer:

Step-by-Step Solution

Key idea: This is a fundamental property of bijective functions between finite sets, recognisable by the keyword "bijective" and finite sets.

Step 1: Recall the definition of a bijective function. A function is bijective if it is both injective (one-to-one) and surjective (onto).

Step 2: For finite sets, an injective function requires that the domain is no larger than the codomain, so $∣ A ∣ \leq ∣ B ∣$ .

Step 3: A surjective function requires that the domain is at least as large as the codomain, so $∣ A ∣ \geq ∣ B ∣$ .

Step 4: For a function to be both injective and surjective (bijective), we must simultaneously satisfy $∣ A ∣ \leq ∣ B ∣$ and $∣ A ∣ \geq ∣ B ∣$ .

Step 5: The only way both conditions can be true is if $∣ A ∣ = ∣ B ∣$ .

Answer: $∣ A ∣ = ∣ B ∣$

Question 4 · Engineering Mathematics MCQ

Let $A$ and $B$ be finite sets with $∣ A ∣ = m$ and $∣ B ∣ = n$ , where $m \leq n$ . According to the standard counting formulas, what is the number of injective (one-to-one) functions from $A$ to $B$ ?

A.
$n^{m}$
B.
$m^{n}$
C.
$\frac{n !}{( n - m )!}$
D.
$m!$

Correct Answer:

Step-by-Step Solution

Key idea: This is a counting functions question, recognizable by the request for the number of injective functions between two finite sets.

Step 1: Identify the sizes of the domain and codomain. Let $∣ A ∣ = m$ and $∣ B ∣ = n$ .

Step 2: For an injective function, each of the $m$ elements in $A$ must map to a distinct element in $B$ .

Step 3: The first element in $A$ has $n$ choices in $B$ . The second has $n - 1$ choices, the third has $n - 2$ , and so on, until the $m$ -th element has $n - m + 1$ choices.

Step 4: Multiply these choices: $n \times (n - 1) \times \dots \times (n - m + 1)$ , which is exactly the permutation formula $\frac{n !}{( n - m )!}$ .

Answer: Option C.

Question 5 · Engineering Mathematics MCQ

Let $\sim$ be an equivalence relation on a set $A$ . A function $g : A / \sim \to B$ is defined by the rule $g ([x]) = f (x)$ for some function $f : A \to B$ . For $g$ to be a well-defined function, which of the following conditions must hold for all $x, y \in A$ ?

A.
$f (x) = f (y) ⟹ x \sim y$
B.
$x \sim y ⟹ f (x) = f (y)$
C.
$x \sim y ⟺ f (x) = f (y)$
D.
$f (x) \neq = f (y) ⟹ x \neq \sim y$

Correct Answer:

Step-by-Step Solution

Key idea: This is a well-definedness question on quotient sets, recognizable by the definition of a function $g$ on equivalence classes using a representative $x$ .

Step 1: Recall what it means for $g ([x]) = f (x)$ to be well-defined. The output of $g$ must depend only on the equivalence class $[x]$ , not on the specific representative $x$ chosen from that class.

Step 2: Translate this into a mathematical condition. If we pick two different representatives $x$ and $y$ from the same class, they must produce the same output.

Step 3: Two representatives $x$ and $y$ belong to the same class if and only if $x \sim y$ . Therefore, the condition is: if $x \sim y$ , then $g ([x])$ must equal $g ([y])$ , which means $f (x) = f (y)$ .

Step 4: Match this with the options. The condition $x \sim y ⟹ f (x) = f (y)$ perfectly captures this requirement.

Answer: Option B.

Question 6 · Engineering Mathematics MCQ

Let $\sim$ be an equivalence relation on a set $A$ . A function $g : A / \sim\to B$ is defined by the rule $g ([x]) = f (x)$ for some function $f : A \to B$ . For $g$ to be a well-defined function, which of the following conditions must hold for all $x, y \in A$ ?

A.
$f (x) = f (y) ⟹ x \sim y$
B.
$x \sim y ⟹ f (x) = f (y)$
C.
$x \sim y ⟺ f (x) = f (y)$
D.
$f (x) \neq = f (y) ⟹ x \neq \sim y$

Correct Answer:

Step-by-Step Solution

Key idea: This is a well-definedness question on quotient sets, recognizable by the definition of a function $g$ on equivalence classes using a representative $x$ .

Step 2: Translate this into a mathematical condition. If we pick two different representatives $x$ and $y$ from the same class, they must produce the same output.

Step 4: Match this with the options. The condition $x \sim y ⟹ f (x) = f (y)$ perfectly captures this requirement.

Answer: Option B.

Question 7 · Engineering Mathematics MCQ

What is the total number of possible binary relations that can be defined on a set $A$ containing exactly 3 elements?

A.
9
B.
27
C.
512
D.
1024

Correct Answer:

Step-by-Step Solution

Key idea: The total number of binary relations on a set of size $n$ is determined by the number of subsets of the Cartesian product $A \times A$ .

Step 1: Identify the size of the set, $n = 3$ .

Step 2: Calculate the total number of possible ordered pairs in $A \times A$ , which is $n^{2} = 3^{2} = 9$ .

Step 3: A binary relation is any subset of these 9 pairs. The number of subsets of a set with 9 elements is $2^{9}$ .

Step 4: Calculate $2^{9} = 512$ .

Answer: 512.

Question 8 · Engineering Mathematics MCQ

What is the minimum number of ordered pairs that must be added to the relation $R = {(1, 2), (2, 1)}$ on the set $A = {1, 2}$ to make it an equivalence relation?

A.
1
B.
2
C.
3
D.
4

Correct Answer:

Step-by-Step Solution

Key idea: An equivalence relation must be reflexive, symmetric, and transitive. We check which of these properties are missing and add the minimum required pairs.

Step 1: Check Reflexivity. For $A = {1, 2}$ , we need $(1, 1)$ and $(2, 2)$ . Neither is in $R$ . We must add both. (2 pairs added).

Step 2: Check Symmetry. $R$ contains $(1, 2)$ and $(2, 1)$ . It is already symmetric. (0 pairs added).

Step 3: Check Transitivity. We have $(1, 2)$ and $(2, 1)$ , which requires $(1, 1)$ and $(2, 2)$ to be present. We already added these in Step 1 to satisfy reflexivity. No additional pairs are needed.

Step 4: Total minimum pairs to add = 2.

Answer: 2.

Question 9 · Engineering Mathematics MCQ

Let $(L, ⪯)$ be a lattice. Which of the following situations is impossible?

A.
Two elements have multiple upper bounds
B.
Two elements have two distinct least upper bounds
C.
Two elements are incomparable
D.
An element is both maximal and minimal

Correct Answer:

Step-by-Step Solution

Key idea: A lattice requires every pair of elements to have a unique least upper bound (join) and a unique greatest lower bound (meet).

Step 1: By definition, a lattice is a poset where every pair ${x, y}$ has a supremum (least upper bound) and an infimum (greatest lower bound).

Step 2: "Multiple upper bounds" is possible. For example, in the subset lattice, ${1}$ and ${2}$ have upper bounds ${1, 2}, {1, 2, 3}$ , etc.

Step 3: "Two distinct least upper bounds" is impossible. If $u_{1}$ and $u_{2}$ are both least upper bounds, then $u_{1} ⪯ u_{2}$ and $u_{2} ⪯ u_{1}$ , so $u_{1} = u_{2}$ by antisymmetry.

Step 4: "Incomparable elements" is possible. In the subset lattice, ${1}$ and ${2}$ are incomparable.

Step 5: "Both maximal and minimal" is possible in a singleton lattice ${a}$ , where $a$ is the only element.

Answer: Two elements have two distinct least upper bounds

Question 10 · Engineering Mathematics MCQ

Let $A = {1, 2, 3}$ . How many partial orders on $A$ contain exactly 4 ordered pairs?

A.
3
B.
4
C.
6
D.
9

Correct Answer:

Step-by-Step Solution

Key idea: A partial order must be reflexive, so the diagonal pairs are always included. The remaining pairs must be chosen such that antisymmetry and transitivity hold.

Step 1: The set $A$ has 3 elements. Any partial order on $A$ must be reflexive, so it must contain the 3 diagonal pairs: $(1, 1), (2, 2), (3, 3)$ .

Step 2: We need exactly 4 ordered pairs in total. This means we must choose exactly $4 - 3 = 1$ off-diagonal pair.

Step 3: There are $3^{2} - 3 = 6$ possible off-diagonal pairs: $(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)$ .

Step 4: If we add any single off-diagonal pair, say $(1, 2)$ , the relation is ${(1, 1), (2, 2), (3, 3), (1, 2)}$ .

Step 5: This relation is trivially antisymmetric (since the reverse pair is not present) and transitive (since there are no chains of length 2).

Step 6: Thus, every choice of 1 off-diagonal pair yields a valid partial order. There are 6 such choices.

Answer: 6

Try a question

Login to view the complete practice 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 Practice Questions 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 (10 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

Step-by-Step Solution

Step-by-Step Solution

More practice questions in this unit