Let F be the set of all functions from {1, 2, ..., n} to {0, 1}. Define the binary relation ~ on F as follows: f ~ g if and only if f(x) <= g(x), where 0 <= 1. Which of the following statement(s) is/are TRUE?
A. ~ is a symmetric relation
B. ~ is a partial order
C. ~ is a lattice
D. ~ is an equivalence relation
GATE 2025 · Discrete Mathematics · Relations · medium
Answer: B, C
Check A: Is ~ symmetric?: Take n=1: f = (0), g = (1). f~g since 0<=1. But g~f requires 1<=0 which is FALSE. So ~ is NOT symmetric.
Check B: Is ~ a partial order?: Reflexive: f(x)<=f(x) always. Antisymmetric: f~g and g~f => f(x)=g(x) for all x => f=g. Transitive: f~g and g~h => f(x)<=g(x)<=h(x) => f~h. All three hold.
Check C: Is (F, ~) a lattice?: For any f,g in F: join(f,g)(x) = max(f(x),g(x)) in {0,1}; meet(f,g)(x) = min(f(x),g(x)) in {0,1}. Both are in F. So every pair has LUB and GLB.
Check D: Is ~ an equivalence relation?: Symmetry fails (shown in Step 1). So ~ is NOT an equivalence relation.