\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}
\input psfig

\begin{document}

\psol{4}{October 8, 1996}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\bparts
\ppart 
The set of ordered pairs
 $=\{(2,2),(2,4),(2,6),(2,8),(3,3),(3,6),(5,5),(7,7)\}$. \\
\[
M_R = 
\left| \begin{array}{ccccccc}
        1 & 0 & 1 & 0 & 1 & 0 & 1\\
        0 & 1 & 0 & 0 & 1 & 0 & 0\\
        0 & 0 & 0 & 0 & 0 & 0 & 0\\
        0 & 0 & 0 & 1 & 0 & 0 & 0\\
        0 & 0 & 0 & 0 & 0 & 0 & 0\\
        0 & 0 & 0 & 0 & 0 & 1 & 0\\
        0 & 0 & 0 & 0 & 0 & 0 & 0
       \end{array}
\right|
\]
\begin{figure}[h]
\centerline{\psfig{figure=digraph.ps,height=2in}}
\end{figure}
\ppart $R$ is not reflexive or symmetric. It is antisymmetric and transitive.
Hence, $R$ is not an equivalence relation.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\bparts
\ppart 
\begin{itemize}
\item $f(x)=e^x$ is an injection. It is not 
a surjection since $f:\reals \longrightarrow \reals^+$. Hence, 
it is not a bijection, and so it does not have an inverse.
\item $f(x)=x^2+3$ is neither an injection, nor a surjection. Hence, it is
not a bijection, and so it does not have an inverse.
\item $f(x)={{x^2+1}\over {x^2+2}}$ is not an injection, surjection, or 
bijection. Hence, it does not have an inverse.
\end{itemize}
\ppart Let $f : B \longrightarrow C$ and $g : A \longrightarrow B$, so that 
$f\circ g : A\longrightarrow C$, for sets $A, B, \mbox{and}~ C$. Let
$x~\mbox{and}~y$ be distinct elements of $A$. Since $g$ is one-to-one,
$g(x)~\mbox{and}~g(y)$ are distinct elements of $B$. 
Since $f$ is one-to-one,
$f(g(x))=f\circ g(x)~\mbox{and}~f(g(y))=f\circ g(y)$ are distinct 
elements of $C$. Hence, $f\circ g$ is one-to-one.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Let $f : B \longrightarrow C$ and $g : A \longrightarrow B$, so that 
$f\circ g : A\longrightarrow C$, for sets $A, B, \mbox{and}~ C$. Then:
\bparts
\ppart 
\begin{theorem} If $f\circ g$ is one-to-one, then $g$ is one-to-one.
\end{theorem}
\begin{proof} (By contradiction): Suppose not. Then there are distinct 	
elements $a_1, a_2\in A$ such that $g(a_1)=g(a_2)$. But this implies that
$f(g(a_1)) = f(g(a_2))~ \longrightarrow (f\circ g)(a_1) = (f\circ g)(a_2)$. 
Contradiction! $f\circ g$ is one-to-one by assumption.
\end{proof}

\ppart No, if $f\circ g$ is one-to-one, then $f$ is not necessarily 
one-to-one. Consider the following counterexample.\\
Let $A=\{\Box,\Diamond,\clubsuit\},~~B=\{a,b,c,d\}~~,\mbox{and}~~
C=\{1,2,3\}$. Now suppose 
$g(\Box)=a,~~g(\Diamond)=b,~~\mbox{and}~~g(\clubsuit)=c$. Also, define
$f(a)=1,~~f(b)=2,~~f(c)=f(d)=3$. Then $f\circ g$ is
clearly one-to-one, since 
$f\circ g(\Box)=1,~~f\circ g(\Diamond)=2,~~\mbox{and}~~f\circ g(\clubsuit)=3$,
but $f$ is not one-to-one.
\ppart This follows immediately from the definition. We want to show that 
$((f\circ g)\circ (g^{-1}\circ {f^{-1}})(z)=z,~ \forall z\in \integers$ and 
that $((g^{-1}\circ f^{-1})\circ (f\circ g))(x)=x,~ \forall x\in X$. 
For the first we have:
\begin{eqnarray*}
((f\circ g)\circ (g^{-1}\circ {f^{-1}}))(z)&=&
                                       (f\circ g)((g^{-1}\circ f^{-1})(z)) \\
                                     &=&(f\circ g)(g^{-1}(f^{-1}(z)))\\
                                     &=&f(g(g^{-1}(f^{-1}(z))))\\
                                     &=&f(f^{-1}(z))\\
                                     &=&z
\end{eqnarray*}
The second equality is done in a similar manner.

\ppart $\sqrt[1]{\sqrt[2]{{\ldots}{\sqrt[n-1]{{\sqrt[n]{x}}}}}}=\sqrt[n!]{x}$
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\begin{proof}
We have a listing of each of the sets $S_i$. Let $s_{ik}$ be the $kth$
element in the listing of $S_i$. We combine them, using the idea of
dove-tailed interleaving shown in class, to get the listing for their
union. The resulting list is $\{ s_{11}, s_{12}, s_{21}, s_{13},
s_{22}, s_{31}, \ldots \}$. It is easy to see $s_{ik}$ will occur
before position $(i+k)^2$ in our listing. Of course, we also drop
repeat elements from our listing but that does not affect anything.
Since we have been able to give a valid listing, $ {\displaystyle
\bigcup}^\infty_{i=1} {\cal S}_i $ is countable.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\bparts
\ppart Uncountable. 
\begin{proof} (By contradiction): Suppose that the set of irrational 
but real numbers is countable. We know the set of real numbers, $\reals$ is
the union of the two sets of rational and irrational numbers. We also
know that the set of rational numbers, $\rationals$ is countable.
Hence, it must be that $\reals$ is countable, since the union of
two countable sets is countable. Contradiction! So, the set of
irrational but real numbers is uncountable.
\end{proof}
\ppart Countable. We showed in class that the set of rational 
numbers, $\rationals$ is countable. Similarly, we can show the
set of numbers of the form $b\sqrt{2}$, $b$ rational, is countable 
by establishing a one-to-one correspondence between $\rationals$ and
the set of numbers of the form $b\sqrt{2}$: $\forall~ r\in \rationals$, 
correspond $r$ to $r\sqrt{2}$.
%\[ 
%\begin{array}{c}
%\\\\
%\sqrt{2} \\ 
%2\sqrt{2} \\ 
%3\sqrt{2} \\ 
%\vdots
%\end{array}
%\left| \begin{array}{cccc}
%        1 & 2 & 3 & \ldots \\ 
%        \_\_\_\_\_\_\_\_\_\_ & \_\_\_\_\_\_\_\_\_\_ & \_\_\_\_\_\_\_\_\_\_ & \_\_\_\_\_\_\_\_\_\_ \\
%        \sqrt{2} & \sqrt{2}/2 & \sqrt{2}/3 & \ldots \\ 
%        2\sqrt{2} & \sqrt{2} & 2\sqrt{2}/3 & \ldots \\ 
%
%        3\sqrt{2} & 3\sqrt{2}/2 & \sqrt{2} & \ldots \\ 
%        \vdots & \vdots & \vdots & \vdots 
%       \end{array}
%\right .
%\]
%By dovetailing throught, and dropping duplicates of numbers, we get the 
%set $\{\sqrt{2},\sqrt{2}/2,2\sqrt{2},3\sqrt{2},\sqrt{2}/3,\ldots\}$, which
%is countable since we established a one-to-one correspondence with 
%$\integers^+$. 
Now, we show the set of numbers
of the form $a+b\sqrt{2}$ is also countable. List the rational numbers
vertically, and the numbers of the form
$b\sqrt{2}$ horizontally to get a listing of all numbers of the
form $a+b\sqrt{2}$ as follows:
\[ 
\begin{array}{c}
\\\\
1 \\ 
1/2 \\ 
2/1 \\ 
3/1 \\
\vdots
\end{array}
\left| \begin{array}{ccccc}
        \sqrt{2} & \sqrt{2}/2 & 2\sqrt{2} & 3\sqrt{2} & \ldots \\ 
        \_\_\_\_\_\_\_\_\_\_\_ & \_\_\_\_\_\_\_\_\_\_\_ & \_\_\_\_\_\_\_\_\_\_\_ & \_\_\_\_\_\_\_\_\_\_\_ & \_\_\_\_\_\_\_\_\_\_\_ \\
        1+\sqrt{2} & 1+{\sqrt{2}/2} & 1+2\sqrt{2} & 1+3\sqrt{2} & \ldots \\ 
        {1/2}+\sqrt{2} & {1+\sqrt{2}}/2 & {1/2}+2\sqrt{2} & {1/2}+3\sqrt{2} & \ldots \\ 
        2+\sqrt{2} & 2+{\sqrt{2}/2} & 2+2\sqrt{2} & 2+3\sqrt{2} & \ldots \\ 
        3+\sqrt{2} & 3+{\sqrt{2}/2} & 3+2\sqrt{2} & 3+3\sqrt{2} & \ldots \\ 
        \vdots & \vdots & \vdots & \vdots & \vdots 
       \end{array}
\right .
\]
The resulting set, obtained by dovetailing through, is 
$\{1+\sqrt{2},{1/2}+\sqrt{2},1+{\sqrt{2}/2},\ldots\}$, which is 
clearly countable.
\ppart Uncountable. (See section $1.7$, example 12, pages $77-78$.)
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\bparts
\ppart For solution, see section $4.2$, example 8, page $246$ (just 
replace $n$ by $100$).
\ppart The set $\cal P$ must contain one of the $n$ pairs of consecutive
integers: $1,2$ or $3,4$ or $5,6$ or $\ldots$ or $2n-1,2n$, which are
clearly relatively prime. Let the set of $n+1$ integers represent the
$n+1$ pigeons, and $n$ pairs of consective integers that are
relatively prime, represent the holes. Then by pigeonhole principle,
there must exist at least one pair of consecutive integers among $n+1$
integers in $\cal P$.
\ppart First look at the $k$ sums 
$a_1, a_1+a_2, a_1+a_2+a_3, a_1+a_2+\ldots +a_k$. If one of these is
divisible by $k$, we need not look any further. If not, each of these
has a nonzero remainder when divided by $k$. Since the only possible
nonzero remainders are $1,2,3,\ldots,k-1$, by pigeonhole principle two
of these sums must have the same remainder $r$ when divided by $k$.
The difference of two such integers is: $(qk + r) - (pk +r) = (q - p)k$, 
for integers $p, q$,  which is divisible by $k$. In that case, if
$a_1+a_2+\ldots+a_n~\mbox{and}~a_1+a_2+\ldots+a_m$ are the sums in the
question and $n>m$, then $a_{m+1}+a_{m+2}+\ldots+a_n$ is the required
sum that is divisible by $k$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 

\begin{proof} (By constructing an injection from $[0,1)$ to the 
function space):\\
We proved in problem 5, part
(c), that the set of real numbers in $(0,1)$ is uncountable. Let us 
associate to each real number in this range (including $0$ but not
$1$) a function from the set of positive integers to the set
$\{0,1,2,3,4,5,6,7,8,9\}$ as follows: If $x$ is a real number whose
decimal representation is $0.d_1d_2\ldots$ (with ambiguity resolved by
forbidding the decimal to end with an infinite string of $9'$s), then
we associate to $x$ the function whose rule is given by $f(n)=d_n$, 
$n\in \integers^+$.
Clearly this is a one-to-one function from the set of real numbers in
$(0,1)$, and a subset of the set of all functions 
from the set of positive integers to the set
$\{0,1,2,3,4,5,6,7,8,9\}$. Two different real numbers must have
different decimal representations, so the corresponding functions are
different. (A few functions are left out, because of forbidding
representations such as $0.239999\ldots$). Since the set $(0,1)$ is
uncountable, the subset of functions we have associated wiht them must
be uncountable. But the set of all such functions has at least this
cardinality, so it, too, must be uncountable. 
\end{proof}

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

\end{problems}

\begin{center}
\large \bf Some common mistakes in your solutions
\end{center}

{\bf Problem 1(b)} Some missed the fact that $R$ is transitive.\

{\bf Problem 2:} Many thought that if a function is injective, then it
must have an inverse. Hence, they concluded that $\ln{x}$ is the
inverse of $e^x$.

{\bf Problem 3(a):} Many students were confused about this 
definitional problem. Some tried to prove both $f$ and $g$ were
injective, and some tried to show neither were injective. 

{\bf Problem 5:} Some did not
provide a way to list the union of sets, they just said that the union 
of countable sets is countable but did not consider that the problem
is about the union of {\em countably~many} countable sets.

{\bf Problem 6(c):} Some made their own assumptions about the numbers 
in the sequence ({\em e.g.}, they are consective integers, they are all
distinct, etc). Some presented very lengthy and confusing solutions.

\end{document}





