GATE 2025 CS (CS2) – Question 42
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?
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$.
- **Reflexive:** $f(x)\le f(x)$. Yes.
- **Antisymmetric:** $f\preccurlyeq g$ and $g\preccurlyeq f$ give $f(x)=g(x)$ everywhere. Yes.
- **Transitive:** yes. So $\preccurlyeq$ is a **partial order** (B).
- **Symmetric?** No: $0\preccurlyeq1$ but not $1\preccurlyeq0$. So (A) and (D) are false (it is not an equivalence relation).
- **Lattice?** Yes: the join is the pointwise max ($f\vee g$) and the meet is the pointwise min, and both are in $\mathcal F$. This is the Boolean lattice $2^n$ (C).
Answer: B, C.
More Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions
- GATE 2024 CS (CS1) Q32
- GATE 2024 CS (CS2) Q34
- GATE 2023 CS Q49
- GATE 2021 CS (CS1) Q53
- GATE 2020 CS Q27
- GATE 2019 CS Q31
All Discrete Mathematics: Sets, Relations, Functions, Partial Orders and Lattices questions →