Let \(\mathcal{F}\) be the set of all functions from \(\{1, \ldots, 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, \ldots, n\},\ f(x) \le g(x),\) where \(0 \le 1\).
Which of the following statement(s) is/are TRUE?
Answer
(B), (C)
Explanation
Each \(f \in \mathcal{F}\) is an \(n\)-bit vector, and \(f \preccurlyeq g\) compares the vectors position by position.
- Reflexive: \(f(x) \le f(x)\). Antisymmetric: \(f \preccurlyeq g\) and \(g \preccurlyeq f\) force \(f(x) = g(x)\) for every \(x\). Transitive, because \(\le\) is. So it is a partial order (B).
- Any two functions have a greatest lower bound, the pointwise minimum, and a least upper bound, the pointwise maximum, so it is a lattice (C): the Boolean lattice of subsets of \(\{1, \ldots, n\}\).
- It is not symmetric: the all-0 function is \(\preccurlyeq\) the all-1 function, but not the other way round. So A is false, and D is false because an equivalence relation must be symmetric.
Answer: B, C