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

%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\pset{4}{September 24, 1996}{Start of Class, Tuesday, October 1}

{\bf Reading:} Sections 1.6, 1.7 (pages 76-78), 4.2, 6.2, and 6.3
of {\it Discrete Mathematics and its Applications} by Kenneth H.
Rosen.

\bigskip

\begin{problems}

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

{\bf [14 points]}

Let $R$ be the relation $\{(a,b)|a~ \mbox{is prime, and}~ a|b\}$ on the 
set $A=\{2,3,4,5,6,7,8\}$. 
\bparts
\ppart {\bf [7 points]} List the ordered pairs, write the matrix, 
and draw the directed graph
representing $R$.
\ppart {\bf [7 points]} Determine whether $R$ is reflexive, symmetric,
antisymmetric, and transitive. Is $R$ an equivalence relation?
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
%sec 1.6, problems 11 and 15
 {\bf [10 points]}
\bparts
\ppart {\bf [6 points]} Determine whether each of the following functions, 
$f : \reals \rightarrow \reals$, is an injection, surjection or a bijection.
Also, give the inverse if it exists.
\begin{itemize}
\item $f(x)=e^x$
\item $f(x)=x^2+3$
\item $f(x)=(x^2+1)/(x^2+2)$
\end{itemize}
\ppart {\bf [4 points]} Prove that the composition of two injective 
functions is injective.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
%Mojdeh(parts a and c)
%sec 1.6, problem 36 (part b)
{\bf [15 points]}
\bparts
\ppart {\bf [5 points]} If $f \circ g$ is one-to-one, 
does it follow that $f$ and $g$ are
also one-to-one? Justify your answer.
\ppart {\bf [5 points]} Suppose that $f$ is an invertible function 
from $Y$ to $Z$ and $g$
is an invertible function from $X$ to $Y$. Show that the inverse of the
composition $f \circ g$ is given by $(f \circ g)^{-1} = g^{-1} \circ
f^{-1}$. (Problem 36, Sec. 1.6 of Rosen)
\ppart {\bf [5 points]} Let $f_1, f_2, ..., f_n$ be functions 
from $\naturals$ to 
$\naturals$, where $f_i(x) = \sqrt[i]{x}$.

Compute $f_1 \circ f_2 \circ ... \circ f_n$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
 {\bf [15 points]}
Determine whether each of the following sets is countable or
uncoutable. Prove your answers. 
\bparts
\ppart {\bf [5 points]} The set of irrational but real numbers.
\ppart {\bf [5 points]} The set of numbers of the form: $a+b\sqrt{2}$, where 
$a$ and $b$ are rational.
\ppart {\bf [5 points]} The set of real numbers in $(0,1)$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
%fall 95, PS4, problem 4-5.b

{\bf [10 points]} Let ${\cal S}_i, 1 \leq i \leq \infty$ be a 
family of countable sets.
Prove that ${\displaystyle \bigcup}^\infty_{i=1} {\cal S}_i$ is countable.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
%Mojdeh (part a), The Theory of numbers by Niven..., page 208

{\bf [21 points]}
\bparts
\ppart {\bf [7 points]}
Show that any subset of $101$ numbers from [1,200] contains two
numbers $x$ and $y$ such that $x|y$.
\ppart{\bf [7 points]} If $\cal P$ is any set of $n+1$ integers selected from 
$1, 2, 3, \ldots, 2n$, prove that there are two relatively prime
integers in $\cal P$.
\ppart {\bf [7 points]} Consider a sequence of $k$ integers: 
$a_1, a_2, \ldots, a_k$. Show that there is some subset of these 
terms whose sum is divisible by
$k$.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
%sec 1.8, problem 30
{\bf [15 points]}

Use a diagonalization argument to show that the set of functions from
the positive integers to the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ is
uncountable. (Problem 30, Sec. 1.7 of Rosen)

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

\end{problems} 
\end{document}


