Question

Let $A$ be a set with $n$ elements. Let $C$ be a collection of distinct subsets of $A$ such that for any two subsets $S_1$ and $S_2$ in $C$, either $S_1\subset S_2$ or $S_2\subset S_1$. What is the maximum cardinality of $C$ ?

• A. $n$
• B. $n+1$
• C. $2^{n-1}+1$
• D. $n!$

Answer 1

The correct option is B $n+1$

The way $C$ is defined in the question, it contains only comparable subsets of $A$.
i.e. the set $C$ is the set of all comparable subsets of the set $A$. Such a set is called a chain.
Consider an example with set $A=\{1,2\}$
Subsets are $\varphi ,\left\{1\right\},\left\{2\right\}$ and $\{1,2\}$
Maximum cardinality of collection of distinct subsets is $\{\varphi ,\{1\left\}\text{and}\right\{1,2\left\}\right\}\text{i.e.}3$
So with $n$ elements maximum cardinality is $n+1$.