GATE CS 2025 Set 2 Q32 — Sets, Relations and Functions

To determine which statements are true, let us analyze the properties of the relation $\preccurlyeq$ defined on the set of functions $\mathcal{F} = \{f \mid f: \{1, \ldots, n\} \to \{0, 1\}\}$.

1. Checking for Partial Order (Option B)

A relation is a partial order if it is reflexive, antisymmetric, and transitive:

• Reflexivity: For any $f \in \mathcal{F}$, since $f(x) \leq f(x)$ for all $x \in \{1, \ldots, n\}$, we have $f \preccurlyeq f$.
• Antisymmetry: If $f \preccurlyeq g$ and $g \preccurlyeq f$, then for all $x \in \{1, \ldots, n\}$, $f(x) \leq g(x)$ and $g(x) \leq f(x)$. This implies $f(x) = g(x)$ for all $x$, so $f = g$.
• Transitivity: If $f \preccurlyeq g$ and $g \preccurlyeq h$, then for all $x \in \{1, \ldots, n\}$, $f(x) \leq g(x)$ and $g(x) \leq h(x)$. This implies $f(x) \leq h(x)$ for all $x$, so $f \preccurlyeq h$.

Since $\preccurlyeq$ is reflexive, antisymmetric, and transitive, $(\mathcal{F}, \preccurlyeq)$ is a partial order. Thus, Option B is TRUE.

2. Checking for Symmetry and Equivalence (Options A and D)

Consider $n \geq 1$. Let $f(x) = 0$ and $g(x) = 1$ for all $x$. Here, $f \preccurlyeq g$ because $0 \leq 1$, but $g \not\preccurlyeq f$ because $1 \not\leq 0$.

• Since $f \preccurlyeq g \not\implies g \preccurlyeq f$, the relation is not symmetric. Thus, Option A is FALSE.
• Since it is not symmetric, it is not an equivalence relation. Thus, Option D is FALSE.

3. Checking for Lattice (Option C)

A partially ordered set is a lattice if every pair of elements $f, g \in \mathcal{F}$ has a unique supremum (least upper bound, LUB) and infimum (greatest lower bound, GLB) in $\mathcal{F}$.

For any $f, g \in \mathcal{F}$, define the pointwise operations:

• Join (LUB): $(f \lor g)(x) = \max(f(x), g(x))$
• Meet (GLB): $(f \land g)(x) = \min(f(x), g(x))$

Since the codomain of the functions is $\{0, 1\}$, the maximum and minimum of any two values in $\{0, 1\}$ also belong to $\{0, 1\}$. Thus, both $(f \lor g)$ and $(f \land g)$ are valid functions in $\mathcal{F}$.

Since every pair of functions has a unique supremum and infimum in $\mathcal{F}$, $(\mathcal{F}, \preccurlyeq)$ is a lattice. Thus, Option C is TRUE.