Power Set Width

The maximum possible value of $|X|$ is $6$ . To see this, first notice that $X =$ the set of subsets with two elements satisfies the condition of the problem, with $|X|=\binom{4}{2}=6$ . To see that this is maximal, note that the set of subsets of $\{1,2,3,4\}$ can be covered by six chains : $\begin{aligned} \emptyset, \{1\},{\color{#D61F06}{\{1,2\}}},\{1,2,3\},\{1,2,3,4\} \\ \{2\},{\color{#D61F06}{\{2,3\}}},\{2,3,4\} \\ \{3\},{\color{#D61F06}{\{3,4\}}},\{1,3,4\} \\ \{4\},{\color{#D61F06}{\{1,4\}}},\{1,2,4\} \\ {\color{#D61F06}{\{1,3\}}} \\ {\color{#D61F06}{\{2,4\}}} \end{aligned}$ where each element in each chain is contained in the next one. Note that any set $X$ of subsets with the property in the problem must have at most one element in each chain, because no element of $X$ can contain another element of $X$ . (The elements of $X$ are colored in red above.)

Sets with the property in the problem are called antichains . So every antichain has size at most $6$ . This shows that $X$ is maximal.

It is not hard to guess the answer for $\{1,2,\ldots,n\}$ ; it is $\binom{n}{\lfloor n/2 \rfloor},$ and the set of subsets of size $\lfloor n/2 \rfloor$ is a maximal antichain. When $n$ is odd, note that it is not unique: for instance, when $n = 5$ , the set of two-element subsets and the set of three-element subsets are both maximal antichains of size $10$ .

Showing that this answer is correct is not easy: the result is known as Sperner's theorem.

For more on this topic, see Dilworth's theorem .