Consider the following relation on subsets of the set ܵ\(S\) of integers…
2014
Consider the following relation on subsets of the set ܵ\(S\) of integers between 1 and 2014. For two distinct subsets \(U\) ܷand ܸ\(V\) of ܵ\(S\) we say ܷ\(U < V\) if the minimum element in the symmetric difference of the two sets is in ܷ\(U\).
Consider the following two statements: ܵ
\(S1\): There is a subset of ܵ\(S\) that is larger than every other subset. ܵ
\(S2\): There is a subset of ܵ\(S\) that is smaller than every other subset.
Which one of the following is CORRECT?
- A.
Both
\(S1\)and ܵ\(S2\)are true - B.
\(S1\)is true and ܵ\(S2\)is false - C.
\(S2\)is true and ܵ\(S1\)is false - D.
Neither ܵ
\(S1\)nor ܵ\(S2\)is true
Attempted by 289 students.
Show answer & explanation
Correct answer: A
Key idea: compare subsets by the smallest element where they differ. At that element, the subset that contains it is declared smaller.
Show there is a smallest subset:
Take the full set S (all integers 1 through 2014). For any other subset V distinct from S, the smallest element in which they differ is an element that belongs to S but not to V. By the ordering rule that element being in S makes S smaller than V. Hence S is smaller than every other subset.
Show there is a largest subset:
Take the empty set ∅. For any other subset V distinct from ∅, the smallest element in which they differ is an element that belongs to V (and not to ∅). By the ordering rule that element being in V makes V smaller than ∅, so every other subset is smaller than ∅. Hence ∅ is larger than every other subset.
Conclusion: Both existence claims are true. The full set S is a smallest element and the empty set is a largest element under the given order.
A video solution is available for this question — log in and enroll to watch it.