The GATE Grind

GATE 2025 CS (CS2) – Question 42

Engineering Mathematics · Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices · 2 marks · Multiple select

Let $\mathcal{F}$ be the set of all functions from $\{1,\dots,n\}$ to $\{0,1\}$. Define the binary relation $\preccurlyeq$ on $\mathcal{F}$ as follows:

$\forall f, g \in \mathcal{F},\ f \preccurlyeq g$ if and only if $\forall x \in \{1,\dots,n\},\ f(x) \le g(x)$, where $0 \le 1$.

Which of the following statement(s) is/are TRUE?

  1. $\preccurlyeq$ is a symmetric relation
  2. $(\mathcal{F}, \preccurlyeq)$ is a partial order
  3. $(\mathcal{F}, \preccurlyeq)$ is a lattice
  4. $\preccurlyeq$ is an equivalence relation

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $(\mathcal{F}, \preccurlyeq)$ is a partial order; (C) $(\mathcal{F}, \preccurlyeq)$ is a lattice

Explanation

$\mathcal F$ is the set of all functions $\{1,\dots,n\}\to\{0,1\}$, i.e. all binary vectors of length $n$. $f\preccurlyeq g$ means $f(x)\le g(x)$ for every $x$.

Answer: B, C.

More Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions

All Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions →