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

The relation is reflexive, antisymmetric and transitive, so it is a partial order, but it is not symmetric or an equivalence. Pointwise max and min give the join and meet, so it is a lattice (the Boolean lattice $2^n$).