Sets, Relations, Functions and Order Structures Short Notes for GATE CS

Sets, Relations, Functions and Order Structures short notes for GATE CS: 4 study cards covering concepts, formulas, shortcuts and exam traps, plus solved practice questions.

Function Properties & Cardinality Cheat Sheet

Cheat Sheet

Core Definitions

Injective: $f (x) = f (y) ⟹ x = y$
Surjective: $Range = Codomain$
Bijective: Injective + Surjective (Inverse exists)

Counting

Domain $m$ , Codomain $n$

Total: $n^{m}$
Injective: $n! / (n - m)!$
Bijective: $m!$ (if $m = n$ )

Composition

$f : A \to B$ , $g : B \to C$

$g \circ f$ inj $⟹ f$ inj
$g \circ f$ surj $⟹ g$ surj
$g \circ f$ bij $⟹ f$ inj, $g$ surj

Function Space

$∣ B^{A} ∣ = ∣ B ∣^{∣ A ∣}$

Quotient Mappings Cheat Sheet

Core Definitions

Equivalence Class: $[a] = {x \in A ∣ x \sim a}$
Quotient Set: $A / \sim = {[a] ∣ a \in A}$
Partition: Disjoint, non-empty blocks covering $A$ (1-to-1 with equivalence relations).

Well-Definedness

$x \sim y ⟹ g ([x]) = g ([y])$

The Induced Bijection

Given surjective $f : A \to B$ and $x \sim y ⟺ f (x) = f (y)$ .
The map $F ([x]) = f (x)$ is a bijection from $A / \sim$ to $B$ .

Final Checklist: Relation Properties

1. Property Identification

Reflexive: All $(x, x)$ present.
Symmetric: $(x, y) ⟹ (y, x)$ .
Transitive: $(x, y) \land (y, z) ⟹ (x, z)$ .
Antisymmetric: $(x, y) \land (y, x) ⟹ x = y$ .
Asymmetric: $(x, y) ⟹ (y, x) \in / R$ (Implies Irreflexive).

2. The Golden Shortcuts

Reflexive + Circular = Equivalence Relation.
Vacuous Truth: If no pairs satisfy the premise, the property is TRUE.

3. Counting Formulas (for $∣ A ∣ = n$ )

Total: $2^{n^{2}}$
Reflexive: $2^{n^{2} - n}$
Symmetric: $2^{n + \frac{n ( n - 1 )}{2}}$
Reflexive + Symmetric: $2^{\frac{n ( n - 1 )}{2}}$
Antisymmetric: $3^{\frac{n ( n - 1 )}{2}} \times 2^{n}$
Asymmetric: $3^{\frac{n ( n - 1 )}{2}}$

4. Equivalence Conditions

Must be R + S + T.
Creates a unique Partition of the set.

Final Checklist: Posets and Lattices

1. Posets & Hasse Diagrams

Partial Order: Reflexive, Antisymmetric, Transitive.
Hasse Diagram: Drop self-loops, drop transitive edges, draw upwards.

2. Extremal Elements & Bounds

Greatest: Above everything (Unique). Maximal: Nothing above it (Can be multiple).
Supremum: Least upper bound. Infimum: Greatest lower bound.

3. Linear Extensions

Count valid topological sorts. Pick minimal elements step-by-step.

4. Lattices & Distributivity

Lattice: Every pair has a unique Join ( $\lor$ ) and Meet ( $\land$ ).
Distributive: Fails if it contains $N_{5}$ (Pentagon) or $M_{3}$ (Diamond).
Boolean Algebra: Bounded + Complemented + Distributive.

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