\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}

\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 3    *
%**************

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
problem {\bf (5 points)} Let $R$ be a binary relation on the set $\{ a, b, c, d, e \}$
defined as follows:

\begin{eqnarray*}
R & =  \{ & (a, a), (a, b), (a, d), (b, a), (b, b), (b, c), (b, d), \\
  & \mbox{} & (c, b), (c, c), (c, d), (d, b), (d, c), (d, d), (e, e) \quad \}
\end{eqnarray*}

Answer yes or no to each of the following questions; if you answer no,
then defend your answer.

\begin{problemparts}
\problempart Is $R$ reflexive?

\solution{
Yes.
}

\problempart Is $R$ symmetric?

\solution{
No. $R$ contains $(a, d)$, but
not $(d, a)$.
}

\problempart Is $R$ transitive?

\solution{
No. $R$ contains $(d, b)$ and $(b, a)$, but not $(d, a)$.  }

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 points)} A relation $R$ on a set $A$ is {\em weakly
transitive} if for all $a, b, c, d \in A$, the relations $aRb$, $bRc$,
and $cRd$ imply the relation $aRd$.

Prove or disprove the following statements.

\begin{problemparts}

\problempart Every symmetric, weakly transitive relation is transitive.

\solution{
The claim is false.  The diagram below shows a counterexample.

\begin{figure}[h!]
\centerline{\resizebox{!}{1.0in}{\includegraphics{figs/f98ps3-relation-cx.eps}}}
\end{figure}
}

\problempart Every reflexive, symmetric, weakly transitive relation
is an equivalence relation.

\solution{
\begin{proof}
The relation $R$ is an equivalence relation if it is reflexive,
symmetric, and transitive.  The first two properties hold by
assumption; all that remains is to show that $R$ is a transitive
relation.  Suppose that the relations $aRb$ and $bRc$ hold.  Because
$R$ is reflexive, the relation $aRa$ also holds.  Because $R$ is
weakly transtive, the relations $aRa$, $aRb$, and $bRc$ imply the
relation $aRc$.  Therefore, $R$ is transitive.
\end{proof}
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problemparts}

\problempart List all the linear extensions of the poset represented by the
Hasse diagram below.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{figs/f98ps3-partial2.eps}}}
\end{figure}

\solution{
\[
\begin{array}{ccc}
a > b > c > e > d	& \quad \quad &		a > c > b > e > d \\
a > b > c > d > e	&	&		a > c > b > d > e \\
a > b > d > c > e
\end{array}
\]
}

\problempart  After considering the above examples, Theory Pig formulated
the following claim.

\bigskip

{\bf Claim.} The number of linear extensions of a partially ordered
set with $n$ elements always divides $n!$.

\bigskip

Either prove that his claim is correct for all posets or else draw
the Hasse diagram of a counterexample and list all linear extensions.

\bigskip

\solution{
The claim is false.  The 4-element poset depicted below has 5 linear
extensions.  This is a counterexample, because 5 does not divide 4!.

\begin{figure}[htbp]
\centerline{\resizebox{!}{1.5in}{\includegraphics{figs/f98ps3-poset-cx.eps}}}
\end{figure}

\[
\begin{array}{ccc}
a > b > c > d	& \quad \quad &		a > b > d > c \\
b > a > c > d   &	&		b > a > d > c \\
b > d > a > c
\end{array}
\]
}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%END   Kavita's problems

%BEGIN Joe's problems
%END   Joe's problems

%BEGIN Ray's problems

%%%%%%%%%%%%%%%%%%  S99 ps8


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem{\bf (15 points)}

\bparts

\ppart (10 points) Let $[0,1]$ be the closed unit line segment, i.e.,
$\set{r \in \reals \mid 0 \leq r \leq 1}$.  Show that there is a bijection
from $[0,1]$ to the whole real line, i.e., to $\reals$.

\solution{
Obviously, $f_1:[0,1] \to \reals$ s.t. $f(x)=x$ is an injection
between the two sets.  There are many ways to construct a surjection
$f_2:[0,1] \to \reals$.  For example, it can be a superposition
$f_2(x)=h(g(x))$ of two surjections $g:[0,1] \to [-1,1]$ and
$h:[-1,1] \to \reals$ defined as follows:
\begin{eqnarray*}
g:[0,1]\rightarrow[-1,1]
&&
g(x)=2x-1
\\
h:[-1,1]\rightarrow\reals
&&
h(x)=\left\{\begin{array}{llr}
        1/x-1   & x>0   & \mbox{map $(0,1]$ to $[0,\infty)$}\\
        0       & x=0   &\\
        1/x+1   & x<0   & \mbox{map $[-1,0)$ to $(-\infty,0]$}
        \end{array}
       \right.
\end{eqnarray*}

If there is a surjection from $[0,1]$ to $\reals$ then, by an
elementary fact listed in Lemma 2.3 in Handout 38, there exists an
injection from $\reals$ to $[0,1]$.  Therefore, by the
Schroeder-Bernstein theorem (Tutorial 8, and section 5 in Handout 38),
there exists a {\em bijection} between $[0,1]$ and $\reals$.


{\bf Alternative Solution:}

Some students constructed a direct bijection between $[0,1]$ and
$\reals$ by superimposing two bijections: $f_1:[0,1] \to (0,1)$ and
$f_2:(0,1) \to \reals$:
\begin{eqnarray*}
f_1(x) & = &
  \left\{
  \begin{array}{ll}
     1/(n+2) & \mbox{if $x= 1/n$ for some $n\in\naturals, n>0$,}\\
     1/2   & \mbox{if $x=0$,}\\
      x            & \mbox{otherwise.}
   \end{array}
  \right.\\
f_2(x) & = & \tan \left(\pi x-\frac{\pi}{2}\right)
\end{eqnarray*}
}

\ppart (5 points) Conclude that there is a bijection between the unit line
segment and the whole plane, i.e., between $[0,1]$ and $\reals \times
\reals$. \hint See Handout 38: Notes on Cardinality.

\solution{
By Theorem 7.2 in Handout 38, there is a bijection between $\reals$
and $\reals^2=\reals\times\reals$.  By Part (a), there is a bijection
between $[0,1]$ and $\reals$.  Hence, by transitivity of bijective
relation between sets, there is a bijection between $[0,1]$ and
$\reals^2$.
}

\eparts  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%Fall 99
%%%%%%%%%%%%%%%

% problem set 4, problem 1
% equivalence classes
\begin{problems}

\problem \textbf{Equivalence Relations}
Let $(a,b) \sim (c,d)$ if $a+d = b+c$. We claim that $\sim$ is an
equivalence relation.

\begin{problemparts}

\problempart Partition the set $\{0,1,2\} \times \{0,1,2\}$ 
into the distinct equivalence classes under $\sim$.

\solution{
We can rewrite $(a,b) \sim (c,d)$ if $a+d = b+c$ as $(a,b) \sim (c,d)$ 
if $a-b = c -d$. This shows that with any equivalence class 
${\cal C}$ we can associate a {\em difference} $d$ such that 
$(a,b) \in {\cal C} \Rightarrow a - b = d$. This gives us an easy way to 
list the equivalence classes of $\{0,1,2\} \times \{0,1,2\}$.
\begin{itemize}
\item $d = -2$ :  $\{(0,2)\}$.
\item $d= -1$ : $\{(0,1),(1,2)\}$.
\item $d= 0$ : $\{(0,0),(1,1),(2,2)\}$.
\item $d= 1$ : $\{(1,0),(2,1)\}$.
\item $d= 2$ : $\{(2,0)\}$.
\end{itemize}
}

\problempart  Prove that $\sim$ is an equivalence 
relation on $\integers \times \integers$.

\solution{
\begin{itemize}
\item {\em Reflexivity} $(a,b) \sim (a,b)$ since $a + b = b + a$.
\item {\em Symmetry} $(a,b) \sim (c,d) \Rightarrow (c,d) \sim (a,b)$ 
since $a + d = b + c \Rightarrow c + b = d + a$.
\item {\em Transitivity} Assume $(a,b) \sim (c,d)$, i.e. $ a + d = b + c$. 
And, $(c,d) \sim (e,f)$, i.e. $c + f = d + e$. Adding we get 
$a + d + c + f = b + c + d + e$ or $a + f = b + e$, 
i.e. $(a,b) \sim (e,f)$. 
Hence $(a,b) \sim (c,d) \wedge (c,d) \sim (e,f) \Rightarrow (a,b) \sim (e,f)$.
\end{itemize}
Since $\sim$ is reflexive, symmetric and transitive it is an equivalence relation.
}

\problempart How many distinct equivalence classes under $\sim$ 
are there on the set $\{0,1,\ldots, n\} \times \{0,1,\ldots, n\}$. 
You do not need to prove your answer.

\solution{
$2n+1$ since the difference can be any value in $\{-n,\ldots, n\}$.}
\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%problem set 4, problem 2
%posets

\problem \textbf{Posets}

Let $R$ be the lexicographic ordering of strings of symbols
from a totally ordered alphabet as defined in Rosen p. 417.

\begin{problemparts}

\problempart Prove that $R$ is a total order.

\solution{We first show that $R$ is a partial order.
Reflexivity is clear from the definition. To show antisymmetry,
suppose that $a_1\ldots a_m<b_1\ldots b_n$, and let $t=\min(m,n)$. This
means that either $a_1\ldots a_t = b_1\ldots b_t$ and $m<n$, so that
$b_1\ldots b_n \not <a_1\ldots a_m$, or else $a_1\ldots a_t<b_1\ldots b_t$,
so that $b_1\ldots b_t \not < a_1\ldots a_t$ and hence again 
$b_1\ldots b_n\not < a_1\ldots a_m$. Finally for transitivity, suppose that
$a_1\ldots a_m<b_1\ldots b_n<c_1\ldots c_p$
. Let $t=\min(m,n)$, $r=\min(n,p)$,
$s=\min(m,p)$, and $l=\min(m,n,p)$. Now if 
$a_1\ldots a_l<b_1\ldots b_l<c_1\ldots c_l$
then clearly $a_1\ldots a_m<c_1\ldots c_p$. Otherwise, without loss
of generality we may assume that $a_1\ldots a_l=b_1\ldots b_l$. If $l=t$
then $m<n$ and $m\le p$. Furthermore, either $b_1\ldots b_r<c_1\ldots c_r$
or $b_1\ldots b_r=c_1\ldots c_r$ and $n<p$. In the former case, if 
$r>l$, then since $p>m$ we have $a_1\ldots a_m<c_1\ldots c_p$, whereas if 
$r=l$ then $a_1\ldots a_l<c_1\ldots c_l$. In the latter case, 
$a_1\ldots a_s=c_1\ldots c_s$ and $m<p$, so again 
$a_1\ldots a_m<c_1\ldots c_p$. If $l<t$, then we must have 
$b_1\ldots b_l<c_1\ldots c_l$, whence $a_1\ldots a_l<c_1\ldots c_l$.
Finally, the fact that $R$ is a total order follows trivially from the 
definition of a lexicographic order and noticing
that the strings of symbols are taken from a totally ordered alphabet.
}

\problempart Prove that neither $R$ nor $R^{-1}$ is a well-ordering.

\solution{
Consider the alphabet $\{a,b\}$ with $a\preceq b$. Then $R$ is not
a well ordering since $\{b,ab,aab,aaab,aaaab,\ldots\}$ has no least element.
Moreover, $R^{-1}$ is not a well-ordering since $\{a,aa,aaa,aaaa,\ldots\}$
has no least element. 
%Consider the alphabet 
%$\{\ldots,a_{-2},a_{-1},a_0,a_1,a_2,\ldots\}$, 
%with the ordering 
%$\ldots\preceq a_{-1}\preceq a_0\preceq a_1\preceq\ldots$. 
%Then $R$ is not a well-ordering, since the set of strings, 
%$\{a_{-1},a_{-2},a_{-3},\ldots\}$ does not have a least element.
%Moreover, the set of strings $\{a_0,a_1,a_2,\ldots\}$ 
%does not have a least element under the ordering $R^{-1}$, and
%therefore $R^{-1}$ is not a well-ordering either.
}

\end{problemparts}

%END   Tina's problems

\end{problems}

\end{document}


