GATE 2025 CS2 Q.42: solution and answer

Official answer: B, CSource: Official answer key, GATE 2025 CS2 (IIT Roorkee)

1. Each $f\in \mathcal{F}$ is a bit vector $(f(1),\dots ,f(n))$, and $f\preccurlyeq g$ means $f(x)\le g(x)$ in every position. This is the componentwise order on $\{0,1{\}}^n$.

2. Reflexive: $f(x)\le f(x)$ for all $x$, so $f\preccurlyeq f$.

3. Antisymmetric: if $f\preccurlyeq g$ and $g\preccurlyeq f$, then $f(x)\le g(x)$ and $g(x)\le f(x)$ for every $x$. So $f(x)=g(x)$ for every $x$, and $f=g$.

4. Transitive: if $f\preccurlyeq g$ and $g\preccurlyeq h$, then $f(x)\le g(x)\le h(x)$ for all $x$, so $f\preccurlyeq h$. The relation is reflexive, antisymmetric and transitive, so $(\mathcal{F},\preccurlyeq )$ is a partial order. (B) is true.

5. Lattice: for any $f,g$ define $(f\vee g)(x)=\max (f(x),g(x))$ and $(f\wedge g)(x)=\min (f(x),g(x))$. Both take values in $\{0,1\}$, so both lie in $\mathcal{F}$. The first is an upper bound of $f$ and $g$, and any upper bound $h$ has $h(x)\ge \max (f(x),g(x))$ at each $x$, so it is the least upper bound. Dually, the second is the greatest lower bound. Every pair has a join and a meet, so $(\mathcal{F},\preccurlyeq )$ is a lattice (the Boolean lattice $2^n$). (C) is true.

6. Symmetric fails: take $f\equiv 0$ and $g\equiv 1$. Then $f\preccurlyeq g$, but $g/\preccurlyeq f$ because $1\nleqq 0$. So (A) is false.

7. An equivalence relation must be symmetric, and this one is not, so (D) is false. The true statements are (B) and (C).