GATE CS 2014 Set 2 Q50 — Sets, Relations and Functions

To determine the truth of statements $S1$ and $S2$, let us analyze the given relation on the power set $\mathcal{P}(S)$ of the finite set $S = \{1, 2, \dots, 2014\}$.

For any two distinct subsets $U, V \subseteq S$, their symmetric difference $U \Delta V = (U \setminus V) \cup (V \setminus U)$ is non-empty. Since $S$ is finite, $U \Delta V$ has a unique minimum element $m = \min(U \Delta V)$. Since $m$ must belong to exactly one of the two sets:

• If $m \in U$, then $U < V$.
• If $m \in V$, then $V < U$.

This means the relation $<$ is a total order (strictly speaking, a strict total order) on the finite set $\mathcal{P}(S)$. Any finite totally ordered set must have a unique minimum (smallest) element and a unique maximum (largest) element.

We can explicitly identify these elements:

• Smallest element: The set $S$. For any $V \neq S$, the minimum element of $S \Delta V = S \setminus V$ is always in $S$, so $S < V$ for all $V \neq S$. Thus, $S2$ is true.
• Largest element: The empty set $\emptyset$. For any $V \neq \emptyset$, the minimum element of $\emptyset \Delta V = V$ is always in $V$, so $V < \emptyset$ for all $V \neq \emptyset$. Thus, $S1$ is true.

Therefore, both statements $S1$ and $S2$ are true.