Official PYQ · 1999Q1.2Sets, Relations and FunctionsMCQ1 mark

GATE CS 1999 Q1.2 — Sets, Relations and Functions

The number of binary relations on a set with $n$ elements is:

View worked solution

Answer: C

A binary relation $R$ on a set $A$ is defined as a subset of the Cartesian product $A \times A$ .

Let the set $A$ have $n$ elements, i.e., $|A| = n$ .

The number of elements in the Cartesian product $A \times A$ is:

|A \times A| = |A| \times |A| = n \times n = n^2

Since any relation on $A$ is a subset of $A \times A$ , the total number of possible binary relations is equal to the number of subsets of $A \times A$ (which is the power set of $A \times A$ ):

\text{Number of binary relations} = 2^{|A \times A|} = 2^{n^2}

Thus, the correct option is C.

Free practice · Your answers on this page are not saved.

Published 10 Oct 2026

Report a correction

GATE CS · 2026Sets, Relations and Functions
Let $R$ be a binary relation on the set $\{1,2, \ldots, 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$ ?
MSQ · 1 mark
GATE CS · 2025Sets, Relations and Functions
$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)$ ?
MCQ · 1 mark
GATE CS · 2025Sets, Relations and Functions
$A=\{0,1,2,3, \ldots\}$ is the set of non-negative integers. Let $F$ be the set of functions from $A$ to itself. For any two functions, $f_{1}, f_{2} \in \mathrm{~F}$ , we define $\left(f_{1} \odot f_{2}\right)(n)=f_{1}(n)+f_{2}(n)$ for every number $n$ in $A$ . Which of the following is/are CORRECT about the mathematical structure …
MCQ · 2 marks
GATE CS · 2025Sets, Relations and Functions
Let $\mathcal{F}$ be the set of all functions from $\{1, \ldots, n\}$ to $\{0,1\}$ . Define the binary relation $\leqslant$ on $\mathcal{F}$ as follows: $\forall f, g \in \mathcal{F}, f \preccurlyeq g$ if and only if $\forall x \in\{1, \ldots, n\}, f(x) \leq g(x)$ , where $0 \leq 1$ . Which of the following statement(s) is/are TRUE?
MSQ · 2 marks
GATE CS · 2024Sets, Relations and Functions
Let $A$ and $B$ be non-empty finite sets such that there exist one-to-one and onto functions $\text{(i)}$ from $A$ to $B$ and $\text{(ii)}$ from $A \times A$ to $A \cup B$ . The number of possible values of $\text{|A|}$ is ___________.
NAT · 1 mark
GATE CS · 2023Sets, Relations and Functions
Let $f: A \rightarrow 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} \text{ if } f\left(a_{1}\right)=f\left(a_{2}\right),$ where $a_{1}, a_{2} \in A$ . Let $\mathcal{E}=\{[x]: x \in A\}$ be the set of all the equivalence classes under …
MSQ · 2 marks

Browse this topic

More Sets, Relations and Functions questions

GATE CS 1999 Q1.2 — Sets, Relations and Functions

Related questions