\documentstyle[11pt,twoside,xypic]{article}
\input{macros-course}

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}
\newcommand{\provable}{\vdash}
\begin{document}

\psol{3}{March 1, 1996}

\bigskip
\begin{problems}

\problem Rosen, 6.1.28 on page 366
\bparts
\ppart
$R \bigcup S$ is reflexive.  

Since $R$ is reflexive, 
 $(a,a) \in R$ for all $a\in R$.  Thus, $(a,a) \in R \bigcup S$ for all $a \in R$.
So, $R \bigcup S$ is reflexive.  

\ppart
$R \bigcap S$ is reflexive.  

Since $R,S$ are reflexive, 
 $(a,a) \in R$ and $(a,a) \in S$ for all $a\in R$.
Therefore, $(a,a) \in R \bigcap S$.  So, 
$R \bigcap S$ is reflexive. 

\ppart
$R\oplus S$ is irreflexive.

$(a,a)$ is both in $R$ and $S$, so $(a,a) \not\in R\oplus S$.
Thus, $R\oplus S$ is irreflexive.

\ppart
$R- S$ is irreflexive.

$(a,a)$ is  both in $R$ and $S$, so $(a,a) \not\in R - S$.
Thus, $R\oplus S$ is irreflexive.

\ppart
$S \circ R$ is reflexive.

$(a,a) \in R$ and $(a,a) \in S$, so $(a,a) \in S \circ R$.
Thus, $S \circ R$ is reflexive.

\eparts

\problem Rosen, 6.5.26 on page 401

\bparts
\ppart
This is a partition.  Every number is either even or odd.

\ppart
Almost a partition.  However, 0 is neither a positive or negative number,
so 0 is not in either set.  Thus, this is not a partition.

\ppart
This is a partition.  Every number is congruent to either 0,1, or 2 (mod 3).

\ppart
This is a partition.  If the absolute value of a number is
less than or equal to 100, it's in the second set. 
Otherwise, it will be in either the first or third set.

\ppart
Not a partition.  For example, 2 is not divisible by 3, and 2 is an even integer.
Therefore, 2 is in two different sets.

These sets do cover all the integers.  For an element, $x$, {\em not} to be in
the first set, $x\equiv 0 \mod{3}$.  For $x$ {\em not} to be in
the second set, $x\equiv 1 \mod{2}$.  By the Chinese Remainder Theorem,
this corresponds to the set $x \equiv 3 \mod{6}$, which is the third set.
\eparts

\problem Rosen, 6.6.20 on page 417
\bparts
\ppart
Maximal elements -- $l$,$m$.
\ppart
Minimal elements -- $a$,$b$,$c$.
\ppart
No.  There is no greatest element.
\ppart
No. There is no least element.
\ppart
Upperbounds for $\{a,b,c\}$ are $k$,$l$,$m$.
\ppart
The least upperbound for $\{a,b,c\}$ is $k$.
\ppart
There are no lower bounds for $\{f,g,h\}$.
\ppart
There is no greatest lowerbound.
\eparts

\problem (Refer to Handout 7.)
Define the binary relation $=_{\provable}$ on arithmetic expressions (ae's)
by the rule:
\[
e =_{\provable} f \quad \mbox{iff} \quad \provable (e = f).
\]
Show that $=_{\provable}$ is an equivalence relation on ae's.

\begin{proof}
To show $=_{\provable}$ is an equivalence relation on ae's, we must show
it is reflexive, symmetric, and transitive.

\begin{itemize}
\item {\bf Reflexive} $\provable e=e$ by the reflexivity rule.  Therefore,
$e =_{\provable} e$.

\item {\bf Symmetric} If $e =_{\provable} f$, then there is a proof that
$e=f$.  Adding the equation $f = e$ at the end of this proof is also a
proof, since the last line now follows by the symmetry rule.  So we have a
proof that $f=e$.  Hence, $f =_{\provable} e$.

\item {\bf Transitive} If $e =_{\provable} f$ and $f =_{\provable} g$,
then there is proof that $e=f$ and a proof that $f=g$.  If put these two
proofs together (i.e.  concatenate the first proof to the front the second
proof) followed by the equation $e = g$, we get a proof in which the last
line follows by transitivity.  So we have a proof of $e=g$.  Hence, $e
=_{\provable} g$.
\end{itemize}

Therefore, $=_{\provable}$ is an equivalence relation.
\end{proof}
\problem (A construction of the rational numbers.)

Let $P$ be the set of all pairs of integers, where the second integer of the
pair is nonzero, i.e. $P = \integers \times (\integers - \{0\})$.  We define
a relation $\sim$ on $P$ as follows:
\[
(a,b) \sim (c,d) \quad \mbox{ iff } \quad ad = bc.
\]

\bparts
\ppart Prove that $\sim$ is an equivalence relation.

We need to show $\sim$ is reflexive, symmetric, and transitive.
\begin{itemize}
\item {\bf Reflexive}  $(a,b) \sim (a,b)$, since  $ab = ba$.
\item {\bf Symmetric} If $(a,b)\sim (c,d)$, then $ad=bc$.  But then
$cb=da$, so $(c,d) \sim (a,b)$.
\item {\bf Transitive} If $(a,b)\sim (c,d)$ and $(c,d) \sim (e,f)$, then
$ad=bc$ and $cf=de$.  So $(ad)f = (bc)f = b(cf) = b(de)$.  Since $d \neq
0$, we cancel $d$ and conclude $af = be$.  Thus, $(a,b)\sim (e,f)$.
\end{itemize}
Therefore, $\sim$ is an equivalence relation.


\ppart Explain why a relation defined on all pairs in $\integers \times
\integers$ by the same rule as $\sim$ would not be an equivalence relation.

We now have $(1,3)\sim (0,0)$ and $(0,0) \sim (1,2)$.  If $\sim$ were a
equivalence relation, then by transitivity, $(1,3)\sim (1,2)$, which is
false because $2 = 1 \cdot 2 \neq 3 = 3 \cdot 3$.

\ppart Give a simple description of the equivalence class of $(0,1)$.

$(a,b) \sim (0,1)$ iff $a \cdot 1 = b \cdot 0$ iff $a=0$.  Thus, the
equivalence class is $\{ (0,b) | b \in \integers - \{0\}\}$.


\ppart Define the {\em rational sum}, $+$, of two pairs in $P$ by the rule
\[
(a,b) + (c,d) ::= (ad+bc,bd)
\]
Show that for pairs $r,s,t \in P$, if $r \sim s$ then $r+t \sim s+t$.  This
says that ``$\sim$ is a congruence with respect to the rational sum
operation on $P$.''

Let $r = (r_1, r_2)$, $s=(s_1,s_2)$ and $t=(t_1,t_2)$.  If $r\sim s$, then
$r_1s_2=r_2s_1$. So, $r+t = (r_1t_2 +r_2t_1, r_2t_2)$ and 
$s+t = (s_1t_2 +s_2t_1, s_2t_2)$.  Note that
\begin{eqnarray*}
(r_1t_2 +r_2t_1)(s_2t_2) &=& r_1t_2s_2t_2 + r_2t_1s_2t_2 \\
&=& (r_1s_2)t_2 t_2 + (r_2 s_2) t_1t_2 \\
&=& (r_2s_1)t_2 t_2 + (r_2 s_2) t_1t_2 \; \; \mbox{ since $r\sim s$.} \\
&=& (r_2t_2) (s_1 t_2 + s_2 t_1) 
\end{eqnarray*}
Therefore, $r+t \sim s+t$.

\ppart Define the {\em rational product}, $\times$ of two pairs in $P$ by
the rule
\[
(a,b) \times (c,d) ::= (ac,bd)
\]
Prove that $\sim$ is a congruence with respect to the rational product.

Define $r,s,t$ as above.  We want to show that if $r\sim s$, then
$r\times t \sim s\times t$.  Since $r \sim s$, we have $r_1s_2=r_2s_1$.
Now, $r\times t = (r_1t_1, r_2 t_2)$ and $s\times t = (s_1t_1, s_2 t_2)$.
Now,
\[
(r_1t_1)(s_2t_2) = (r_1s_2)(t_1t_2)= (r_2s_1)(t_1t_2)=(s_1t_1)(r_2t_2).
\]
So, $r\times t \sim s\times t$.


\ppart Define the binary relation of {\em rational inequality}, $\preceq$, on
$P$ by
\[
(a,b) \preceq (c,d) \quad \mbox{iff} \quad abd^{2} \leq cdb^{2}.
\]
Prove that $r \preceq s$ and $s \sim t$ implies that $r \preceq t$.

%%FIX THIS TO AVOID DIVISION--we're CONSTRUCTING the rationals, so we don't
%%want to assume they exist already!

Define $r,s,t$ as above. $r\sim t$ implies $r_1t_2=r_2t_1$.
Since
$r \preceq s$, 
\begin{eqnarray*}
& r_1 r_2 s_2^2 \leq s_1s_2 r_2^2 \\
\Longrightarrow & r_1 r_2 s_2^2 t_2^2 \leq s_1 s_2 r_2^2 t_2^2
\; \;  \mbox{ since $r_2^2 >0$}\\
\Longrightarrow & (r_1 t_2) r_2 s_2^2 t_2 \leq s_1 s_2 r_2^2 t_2^2 \\
\Longrightarrow & (r_2 t_1) r_2 s_2^2 t_2 \leq s_1 s_2 r_2^2 t_2^2 \\
\Longrightarrow & t_1 r_2^2 s_2^2 t_2 \leq s_1 s_2 r_2^2 t_2^2 \\
\Longrightarrow & t_1 t_2 s_2^2 \leq s_1s_2 t_2^2 \; \;\mbox{ since $r_2^2 >0$}
\end{eqnarray*}
Therefore, $r \preceq t$.

\ppart Prove that if $(0,1) \preceq r$ and $s \preceq t$, then $r \times s
\preceq r \times t$, for all $r,s,t \in P$.

Define $r,s,t$ as above.
$(0,1) \preceq r$ implies $0 \leq r_1r_2$.
Since $s \preceq t$, we have $s_1s_2 t_2^2 \leq t_1t_2 s_2^2$.
Thus,
\[
(r_1r_2)(r_2^2)s_1s_2 t_2^2 \leq (r_1r_2)(r_2^2)t_1t_2 s_2^2
\Longrightarrow (r_1s_1)(r_2s_2)(t_2r_2)^2 \leq (r_1t_1)(r_2t_2)(r_2s_2)^2
\]
Therefore, $r \times s\preceq r \times t$.

\ppart Let $[p]_{\sim}$ be the equivalence class of $p \in P$ under $\sim$.
Define $[p]_\sim \leq_{\sim} [q]_\sim$ iff $p \preceq q$.  Prove that
$\leq_\sim$ is a partial order on the $\sim$ equivalence classes.

In part (f), we showed
that $r \preceq s$ and $s \sim t$ implies that $r \preceq t$.
Using an identical argument, we can show
that $r \preceq t$ and $r \sim s$ implies that $s \preceq t$.
Therefore, $\preceq$ is preserved for related
elements.  In other words, the binary relation, $\leq_{\sim}$ is well-defined.
With equivalence classes, if $r \sim r'$, then $[r]_\sim = [r']_\sim$.
For $\leq_\sim$ to be well-defined, it cannot depend upon the representation
of the equivalence class (i.e. it can't matter whether we use $[r]_\sim$
or $[r']_\sim$).  By part (f), it follows
that if $r\sim r'$ and $[r]
\sim \leq_\sim [t]_\sim$, then 
$[r']_\sim \leq_\sim [t]_\sim$.  
Similarly, we can show if $t\sim t'$ and $[r]
\sim \leq_\sim [t]_\sim$, then 
$[r]_\sim \leq_\sim [t']_\sim$.  Thus, $\leq_\sim$ does not depend
upon our choice of $r$ (or $t$) for the representation.  Hence, it is
well-defined.

%%THE POINT OF THIS REMARK IS NOT SUFFICIENTLY CLEAR.  NEED TO EXPLAIN
%%EXPLICITLY that the form of def of \leq_{\sim} appears to depend on $p$
%%rather than only [p]_{\sim}.  The remark above shows that in fact
%%\leq_{\sim} depends only on [p].

To show a partial order, we need to show reflexive, antisymmetric, and
transitive.

\begin{itemize}
\item {\bf Reflexive} Observe that $r \preceq r$. ($r_1r_2^3\leq r_1r_2^3$)
Thus, $[r]_\sim \leq_{\sim} [r]_\sim $ and $\leq_{\sim}$ is reflexive.
\item {\bf Antisymmetric} If $[r]_\sim \leq_{\sim} [s]_\sim$ and
$[s]_\sim \leq_{\sim} [r]_\sim$, then
$r\preceq s$ and $s\preceq r$.  Therefore,
\begin{eqnarray*}
&r_1r_2s_2^2 \leq s_1s_2r_2^2 \mbox{ and } s_1s_2r_2^2 \leq r_1r_2s_2^2 \\
\Longrightarrow & r_1r_2s_2^2 = s_1s_2r_2^2 \\
\Longrightarrow & r_1s_2 = s_1r_2 \\
\Longrightarrow & r\sim s
\end{eqnarray*}
Therefore, $[r]_\sim = [s]_\sim$ and $\leq_{\sim}$ is anti-symmetric.
\item {\bf Transitive}
If 
$[r]_\sim \leq_{\sim} [s]_\sim$ and $[s]_\sim \leq_{\sim} [t]_\sim$,
then $r\preceq s$ and $s\preceq t$.
Therefore, 
\begin{eqnarray*}
& r_1r_2s_2^2 \leq s_1s_2r_2^2 \mbox{ and }
s_1s_2t_2^2 \leq t_1t_2s_2^2 \\
\Longrightarrow 
& r_1r_2s_2^2 t_2^2\leq s_1s_2r_2^2 t_2^2\mbox{ and }
s_1s_2t_2^2 r_2^2\leq t_1t_2s_2^2 r_2^2\\
\Longrightarrow & r_1r_2s_2^2 t_2^2\leq t_1t_2s_2^2 r_2^2\\
\Longrightarrow & r_1r_2t_2^2\leq t_1t_2 r_2^2 \mbox{ since $s_2^2>0$}\\
\end{eqnarray*}
Therefore, $r \preceq t$, and $[r]_\sim \leq_{\sim} [s]_\sim$.
Thus, $\leq_{\sim}$ is transitive.
\end{itemize}
Thus, we have shown $\leq_{\sim}$ is a partial order.
\eparts


\end{problems}
\end{document}





