What are common examiner traps in Sets, Relations and Functions?

Off-by-one counting error: assuming the set \0, 1, , n\ has n elements instead of n + 1, leading to computing 210 = 1024 instead of 211 = 2048. Off-by-one error when counting elements in a range starting at 0 (e.g., forgetting that |\0, 1, , 2014\| = 2015, an odd number). Assuming an involution must be the identity map globally (f(x) = x for all x) rather than permitting 2-cycles / pairwise swaps. Failing to recognize that f f = I implies f is its own two-sided inverse, directly guaranteeing that f is onto. Confusing domain and codomain powers when computing function count (|A||B| vs |B||A|). Selecting only 'bijection exists' and missing 'surjection exists' or 'injection exists' in an MSQ format. Miscalculating matrix cardinality as |A| n2 instead of |A|n2. Confusing |B||A| with |A||B| when computing total functions. Forgetting to enforce non-emptiness (|A| 1), which might incorrectly allow |A| = 0. Missing extreme overlap cases in set unions (disjoint vs subset) leading to missing valid integer solutions for |A|.

Sets, Relations and Functions

5 Qs · 2014–2024 · 7 marks · 0.3 marks/paperStandard yield

Take topic test

In this topic, GATE tests the foundational properties of finite sets, combinatorial counting of structured objects (such as matrices and function spaces), and the existence of mapp… Guide

Type

GATE CSE 2024 Set 1Q32NAT1 markMediumLet $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 ________
GATE CSE 2021 Set 2Q11MSQ1 markEasyConsider the following sets, where $n \ge 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?
GATE CSE 2015 Set 2Q18NAT1 markEasyThe cardinality of the power set of $\{ 0, 1, 2, \dots, 10 \}$ is _______.
GATE CSE 2014 Set 1Q50NAT2 marksEasyLet $S$ denote the set of all functions $f: \{0,1\}^4 \to \{0,1\}$ . Denote by $N$ the number of functions from $S$ to the set $\{0,1\}$ . The value of $\log_2 \log_2 N$ is _______.
GATE CSE 2014 Set 3Q49MCQ2 marksMediumConsider the set of all functions $f\colon \{0, 1, \dots, 2014\} \to \{0, 1, \dots, 2014\}$ such that $f(f(i)) = i$ , for all $0 \le i \le 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…

Topic guide

What does GATE test in Sets, Relations and Functions?

In this topic, GATE tests the foundational properties of finite sets, combinatorial counting of structured objects (such as matrices and function spaces), and the existence of mappings (injections, surjections, and bijections). The focus is on comparing cardinalities of constructed sets and understanding how equal or unequal cardinalities govern the existence of specific mapping types.

Core concepts

Set cardinality
Power set definition and cardinality
Inclusive integer range counting
Involutions (functions satisfying f(f(x)) = x)
Bijection, Injection, and Surjection properties of invertible functions
Fixed points of finite set permutations (f(x) = x)
Parity and counting arguments on finite set cardinalities
Set Cardinality and Combinatorics
Matrix configurations over finite alphabets
Function spaces and total functions (BA)
Injective, Surjective, and Bijective mappings between finite sets
Function cardinality and function spaces (BA)
Bijection (one-to-one and onto) and equinumerosity
Cartesian product cardinality
Principle of Inclusion-Exclusion bounds on union of sets
Logarithmic scaling of large combinatorial powers

Recurring question patterns

Power Set Cardinality Computation
rare · NAT · 1 marks · 2015
Given an explicitly defined finite set or integer range (often starting from 0 to test inclusive counting), compute the total number of subsets (the cardinality of the power set) using $2^{|S|}$ .
Properties of Involutions and Finite Set Mappings
rare · MCQ · 2 marks · 2014
Given a function $f: S \to S$ satisfying an algebraic relation like $f(f(x)) = x$ on a finite set $S$ , evaluate statements concerning injectivity, surjectivity, identity mapping, and the existence of fixed points.
Cardinality Comparison and Existence of Mappings
rare · MSQ · 1 marks · 2021
Two abstract sets $S_1$ and $S_2$ are defined via combinatorial constructions (e.g., matrices over finite alphabets, set of total functions). Candidates compute $|S_1|$ and $|S_2|$ to evaluate assertions regarding injective, surjective, or bijective mappings between them.
Higher-Order Function Space Cardinality
occasional · NAT · 2 marks · 2014
Determining the size of a set of functions and subsequent meta-functions between such sets, usually requiring logarithmic compression to evaluate the final integer answer.
Cardinality Constraints from Bijections
occasional · NAT · 1 marks · 2024
Given bijective mappings between compound sets derived from finite sets (such as $A \times A$ and $A \cup B$ ), setting up bounds via the Principle of Inclusion-Exclusion to find the number of valid integer cardinalities.

Formulas GATE uses

Power Set Cardinality

|\mathcal{P}(S)| = 2^{|S|}

Used to find the number of all possible subsets of a finite set $S$ .

Inclusive Integer Range Cardinality

|\{a, a+1, \dots, b\}| = b - a + 1

Used to find the number of elements in a contiguous set of integers from $a$ to $b$ inclusive.

Cycle Decomposition of Involutions

2k + m = |S|

Used to relate the number of 2-cycles ( $k$ ) and fixed points / 1-cycles ( $m$ ) to the total cardinality of the set $|S|$ .

Invertibility Condition for Involutions

f(f(x)) = x \implies f = f^{-1} \implies f \text{ is bijective (injective and surjective)}

Used to prove that any self-inverse mapping on a set is both one-to-one and onto.

Number of Matrices Over a Finite Set

|S| = |A|^{n \times m}

Determining the number of $n \times m$ matrices where each entry is chosen independently from an alphabet/set $A$ .

Total Number of Functions

|B^A| = |B|^{|A|}

Computing the number of total functions from domain set $A$ to codomain set $B$ .

Existence of Mappings between Finite Sets

|A| = |B| \implies \text{Bijection exists} \implies (\text{Injection exists} \land \text{Surjection exists})

Evaluating the validity of assertions about injective, surjective, and bijective mappings between finite sets of identical cardinality.

Number of Functions Between Sets

|B^A| = |B|^{|A|}

Used to compute total number of functions from domain set $A$ to codomain set $B$ .

Bijection Cardinality Equivalence

f: X \to Y \text{ is bijective} \implies |X| = |Y|

Used to equate cardinalities of sets connected by a one-to-one and onto function.

Cartesian Product Cardinality

|A \times B| = |A| \times |B|

Used when computing domain or codomain size of product sets.

Inclusion-Exclusion Cardinality Bounds

|A| \le |A \cup B| = |A| + |B| - |A \cap B| \le |A| + |B|

Used to establish bounds on the union of two finite sets.

Examiner traps in Sets, Relations and Functions

Off-by-one counting error: assuming the set \0, 1, , n\ has n elements instead of n + 1, leading to computing 210 = 1024 instead of 211 = 2048.
Off-by-one error when counting elements in a range starting at 0 (e.g., forgetting that |\0, 1, , 2014\| = 2015, an odd number).
Assuming an involution must be the identity map globally (f(x) = x for all x) rather than permitting 2-cycles / pairwise swaps.
Failing to recognize that f f = I implies f is its own two-sided inverse, directly guaranteeing that f is onto.
Confusing domain and codomain powers when computing function count (|A||B| vs |B||A|).
Selecting only 'bijection exists' and missing 'surjection exists' or 'injection exists' in an MSQ format.
Miscalculating matrix cardinality as |A| n2 instead of |A|n2.
Confusing |B||A| with |A||B| when computing total functions.
Forgetting to enforce non-emptiness (|A| 1), which might incorrectly allow |A| = 0.
Missing extreme overlap cases in set unions (disjoint vs subset) leading to missing valid integer solutions for |A|.

How questions are asked

Direct NAT power set size calculation
Multi-statement verification on function properties
Identify valid mapping properties (injection/surjection/bijection) between two constructed sets
Evaluate nested log of total function count
Determine the count of possible set cardinalities satisfying bijective conditions

Paper trends

Appears as a 1-mark NAT testing quick evaluation of power set size with minimal computational complexity.
2015
In 2014, emphasis was placed on combining functional identities ( $f(f(x)) = x$ ) with discrete parity arguments based on set cardinality ( $|S| = 2015$ ) to determine surjectivity and fixed-point presence.
2014
With the introduction of MSQ question types in 2021, set theory questions test multiple logical consequences of cardinality equality (e.g., bijection implies both injection and surjection) across individual options.
2021
Both questions appear as NAT items testing cardinality principles rather than abstract proofs, shifting from direct nested function counting to inequality-bounded algebraic reasoning on set cardinalities.
2024, 2014

Difficulty notes

Easy: Direct evaluation of power set size $2^{|S|}$ for a contiguous range of integers. Medium: Base set defined with predicates/conditions (e.g., divisibility or prime criteria) before power set evaluation. Hard: Nested power sets (e.g., $|\mathcal{P}(\mathcal{P}(S))|$ ) or subsets with specific size/parity constraints.