
\problemdata     
{S01-PS4-3}           
{relations, chains and antichains}              
{}              
{S01-PS4} 		
{S01 Karger}


\renewcommand{\power}{\mathcal{P}}

\begin{problem}

 \textbf{Chains and antichains}

\noindent Let $A = \{1,2,\ldots,n\}$
and consider the partial order $(\power(A),\subseteq)$. (Remember that
$\power(A)$ is the set of all subsets of~$A$ and that $\subseteq$ is
the normal subset operator.)

\begin{problemparts}
  \ppart Prove that there exists a chain of length~$n+1$ in
  $(\power(A),\subseteq)$.
  
  \solution{Let $A_0 = \emptyset$ and $A_i = A_{i-1} \cup \{i\}$ for
    $0 < i \leq n$. Then $A_i \subset A_{i+1}$ and there are $n+1$
    different $A_i$'s.}

  
  \ppart Prove that for any integer~$k$ such that $0 < k < n$, the
  set $\{B \subseteq A : |B| = k\}$ is an antichain in
  $(\power(A),\subseteq)$.
  
  \solution{Let $A_k = \{B \subseteq A : |B| = k\}$ and consider
    $B_1,B_2 \in A_k$ such that $B_1 \neq B_2$. We prove the claim by
    contradiction, i.e., by assuming that $B_1$ and~$B_2$ are related.
    Thus, assume without loss of generality that $B_1 \subseteq B_2$.
    Since $B_1 \neq B_2$, this implies that $B_1 \subset B_2$, which
    implies that $|B_1| < |B_2|$, which contradicts the fact that
    $B_1,B_2 \in A_k$.  Thus $B_1$ and~$B_2$ are uncomparable, which
    implies that $A_k$~is an antichain.}
\end{problemparts}


\end{problem}
