\documentstyle[12pt,twoside,amssymb]{article}
\input{macros-course}


\let\union\cup
\let\Union\bigcup
\let\Intersect\bigcap
\let\Leq\sqsubseteq
\def\lte{\Leq_A}
\newcommand{\tuple}[1]{\langle{#1}\rangle}
\newcommand{\seq}[1]{\mbox{seq}(#1)}
\newcommand{\width}[1]{\mbox{width}(#1)}
\def\twotenths{\mbox{twotenths}}

\newcommand{\provable}{\vdash}
\begin{document}

\pset{4}{March 7, 1996}{March 15, 1996}

{\bf Reading for this assignment:}   Rosen course text, \S 1.6, 1.7, 4.2, 7.1

{\bf Reading for recitation and next week's lectures:} \S 6.3, 6.4, 7.1--5, 7.8

\bigskip

\begin{problems}

\problem

As on Quiz 1, let $A$ be the set of nonempty subsets of $\{1,2,\dots,n\}$
for some integer $n>1$.  For $a\in A$, let $\max(a)$ be the maximum
element in~$a$.  Define a partial order, $\lte$, on $A$ by the rule that
\[
a \lte a' \mbox{ iff }\quad \max(a) < \max(a') \mbox{ or } [\max(a) =
\max(a') \mbox{ and } a \subseteq a'].
\]
You learned from the quiz (we hope :-)\ ) that the parallel-time of $(A
\lte)$, which equals the length of the longest chain, is $n(n+1)/2$.  Now
Dilworth's Theorem implies that there is an antichain of size at least
$\lceil 2(2^n-1)/n(n+1)\rceil$.

In fact there are much larger antichains when $n$ is large enough.  What
is the least $n>1$ such that there is an antichain of size strictly bigger
than guaranteed by Dilworth's Theorem?  Write down the elements of such an
antichain.

\problem

Rosen, Problem 4.2.34, p. 249.

\problem

In class we have shown that for any set $A$, if there is an injection from
$A$ to a proper subset of $A$, then there is also an injection from
$\nats$ to $A$.  Prove the converse: if there is an injection from $\nats$
to $A$, then there is an injection from $A$ to a proper subset of $A$.

\problem
Prove that the set $[0,1)$ (the half-open unit interval of the real
line) has the same cardinality as the set $[0,1)\times[0,1)$ (the
half-open unit square of the Euclidian plane).

Hint: Use the fact that every real number $r\in[0,1)$ has a {\em unique}
decimal representation $0.d_1d_2d_3\cdots$ which does not end in all
$9$'s.

\problem %
Let $A$ be a set. Define the set $\seq{A}$ to be the set of all
finite tuples of one or more elements in $A$.  Namely,
\[\seq{A} = \Union_{n>0}{\underbrace{A\times\cdots\times A}_n}.
\]
We say a set $S$ is {\em countable} iff there is an injection from $S$
to $\nats$.  Prove that $\seq{\nats}$ is countable.

Hint: Define the {\em norm} of any tuple $\tuple{n_1,\dots,n_k} \in
\seq{\nats}$ to be $\max{\{k, n_1, \dots, n_k\}}$.  Observe that for any
$k>0$, there are only finitely many tuples with norm $k$.

\problem

Define a {\em checkered} set of reals numbers to be one which is a finite
union of disjoint, finite, closed intervals.  Let ``$\twotenths$'' be the
operation which maps a checkered set to the checkered set obtained by
removing all but the first and last tenth of each closed interval.  For
example,
\begin{eqnarray*}
\twotenths([0,1]) & =  & [0,1/10] \union [9/10,1],\\
\twotenths([0,1/10] \union [9/10,1]) & =  & [0,1/100] \union [9/100,1/10] \union
[9/10,91/100] \union [99/100,1].
\end{eqnarray*}
Continuing in this way, we define
\begin{eqnarray*}
{\frak C}_0 & = & [0,1],\\
{\frak C}_{n+1} & = & \twotenths({\frak C}_n),\\
{\frak C} &=& \Intersect_{n\geq 0}{\frak C}_n.
\end{eqnarray*}

\bparts

\ppart Prove that for any $\epsilon >0$, there is a checkered set of
intervals of total length $< \epsilon$ which contains ${\frak C}$.

\ppart Prove that ${\frak C}$ is not countable.  (Hint: Consider the
infinite decimal expansion of elements in ${\frak C}$.)

\eparts

\problem
\bparts

\ppart
% Rosen, Problem 7.1.11, p. 436. % has a solution in the book!
The {\em intersection graph} of a collection of sets $A_1,A_2,...,A_n$
is the graph that has a vertex for each of these sets and has an edge
connecting the vertices representing two sets if these two sets have a
nonempty intersection. Construct the intersection graph for the
following collection of sets.
\begin{eqnarray*}
A_1 & = & \{0,1\}\\
A_2 & = & \{1,2\}\\
A_3 & = & \{2,3,8\}\\
A_4 & = & \{3,4,5\}\\
A_5 & = & \{1,2,4,9\}
\end{eqnarray*}

\ppart Show that a graph is {\em simple} (cf. Rosen, \S 7.1 ,Def. 1) iff it
is graph isomorphic (cf. Rosen, \S 7.3, Def. 1) to an intersection graph.

\eparts

   \iffalse

   \problem[Optional, for extra credit.]
   Let $(A,\Leq_A)$ be a finite poset.
   Define a {\em chain cover} to be a collection of chains in
   $(A,\Leq_A)$, such that every element in $A$ belongs to at least one
   chain in the collection.  Let
   \[
   \width{A} = \max{\{n \alt A \mbox{ has an antichain of size }n\}}.
   \]
   Prove that there is a chain cover of $A$ with $\width{A}$ chains.

   Hint: Induction on the size of $A$.  There are two cases
   to consider:
   \begin{description}
   \item[Case 1.]
   There is an antichain, $T$, of size $\width{A}$ which contains two elements
   $a,b\in A$ such that $a$ is strictly bigger than some element of $T$,
   and $b$ is strictly smaller than some element of $T$.
   \item[Case 2.]
   Not case 1.  In other words, the only antichains of size $\width{A}$ are: i)
   the set of maximal elements of $A$, or ii) the set of minimal elements
   of $A$, or iii) both i) and ii).
   \end{description}
   \fi


\end{problems}
\end{document}


