Project ForgeLet F be the set of all functions from {1,...,n} to {0,1}. Define the binary relation ⪯ on F as follows: ∀f,g ∈ F, f⪯g if and only if ∀x∈{1,...,n}, f(x)≤g(x). Which of the following statement(s) is/are TRUE?
- A⪯ is a symmetric relation
- (F,⪯) is a partial order
- (F,⪯) is a lattice
- D⪯ is an equivalence relation
Explanation
⪯ is reflexive, antisymmetric (f⪯g and g⪯f forces f=g pointwise), and transitive — a genuine partial order (B true), specifically the standard product/Boolean-lattice order on {0,1}ⁿ. It's NOT symmetric (the all-zero function ⪯ the all-one function, but not vice versa — A false, and consequently D, which needs symmetry, is also false). It IS a lattice (C true): pointwise min and max of any two functions always stay in F and serve as the meet and join.
Source: GATE CS 2025 (Session 2 / CS2) (2025)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.