\problemdata     
{relations-4}           
{partial orders, chains, antichains}              
{}              
{S00, S02} 		
{Radhika, S02}        	



\begin{problem} 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 relation.

\begin{problemparts}
  \problempart 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.}

  
  \problempart 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.}

  \problempart Draw a DAG for the relation $(\power(A),\subseteq)$ if
  $A = \{1,2,3\}$ and indicate which are the chains and
  antichains. Give an example of a topological sort of this relation.

  \solution{See Figure~\ref{figure1}. $\{\}, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}$ is a topological sort of this relation.

\begin{figure}[ht]
\begin{center}
\unitlength=0.5pt
\input{../figures/ps3-1.pic}
\end{center}
\caption{DAG for Problem 4c.}
\label{figure1}
\end{figure}
Note that not all chains and antichains are labelled.  A chain is any group that is connected in some manner with arrows.  Antichains are groups of elements where no two members are connected.}  


%   \problempart Prove that, if $A$ is finite then every non-empty
%   subset of $P(S)$ has a \textit{minimal element} (as defined in Rosen
%   ?, or include definition).

%   \solution{FIX, let $T$ be a non-empty subset of $\power(A)$, then we
%   can order the elements of $T$ by cardinality. Size of a set is a
%   natural number which and any of the sets with the smallest size will
%   be the set with then can order the elements }

\end{problemparts}
\end{problem}
