GATE CS 2025 Set 2 — Question 42

The set $\mathcal{F}$ represents the set of all functions mapping elements from $\{1, \dots, n\}$ to $\{0, 1\}$. This structure is isomorphic to the power set of a set with $n$ elements, denoted as $\mathcal{P}(S)$, where the relation $\preccurlyeq$ corresponds to the subset relation $\subseteq$ (bitwise less than or equal).Let's analyze the properties of the relation $\preccurlyeq$:Since the relation is reflexive, antisymmetric, and transitive, $(\mathcal{F}, \preccurlyeq)$ is a partial order. Therefore, option (B) is TRUE.Since the relation is antisymmetric, it is not symmetric (unless the set has only one element, but generally speaking for arbitrary $n$, it is not). Therefore, option (A) is FALSE.Since it is not symmetric, it cannot be an equivalence relation. Therefore, option (D) is FALSE.A partial order is a lattice if every pair of elements has a least upper bound (join) and a greatest lower bound (meet). In this case:

• Join ($f \lor g$): Define $h(x) = \max(f(x), g(x))$. This is the smallest function greater than or equal to both $f$ and $g$.
• Meet ($f \land g$): Define $k(x) = \min(f(x), g(x))$. This is the largest function smaller than or equal to both $f$ and $g$.

Since join and meet exist for all pairs, $(\mathcal{F}, \preccurlyeq)$ is a lattice. This is analogous to the power set lattice where join is union and meet is intersection. Therefore, option (C) is TRUE.