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

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

\begin{document}

\pset{4}{September 26, 1995}{Start of Class, October 3}

{\bf Reading:} Sections 1.6, 4.2, 6.2, 6.3 and 6.5 of {\it
Discrete Mathematics and its Applications} by Kenneth H. Rosen.

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\bparts
\ppart 
The following is a matrix that depicts the binary relation ``reachable
by a non-stop flight'' on the set of cities $i, 1 \leq i \leq 5$. In
other words entry $(i,j)$ is $1$ iff there is a non-stop flight from
$i$ to $j$.
\[ \left( \begin{array}{ccccc}
1 & 1 & 0 & 0 & 0\\
0 & 1 & 1 & 0 & 0\\
1 & 1 & 1 & 0 & 1\\
1 & 1 & 1 & 1 & 1\\
0 & 0 & 0 & 1 & 1
	\end{array} \right) \] 

Compute the matrix that represents the relation ``reachable by at most two
intermediate connections.''

\ppart Prove or give a counterexample to the following statement : ``Let $R$ be a relation. Then $R^2 = R$ iff $R$ is transitive and reflexive.''
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\bparts
\ppart State for each of the following functions 
($f:\reals \rightarrow \reals$)	 whether it is a injection, 
surjection or a bijection. Also, give the inverse if it exists.
\begin{itemize}
\item sin$(x)$
\item $x^{1994}$
\item $x^{1995}$
\item $x/(x^2+5)$
\end{itemize}
\ppart Let $f(x) = x + 1, g(x) = 2x$ and $h(x) = x^2$ be three functions
from $\reals$ to $\reals$. Compute $f\circ g, g\circ h$ and $f\circ g\circ h$. 
\ppart Prove that the composition of two surjective functions is surjective.
\eparts
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Show that for all odd natural numbers $m$ there exists an $n \geq 1$ such
that $m | 2^n - 1$. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
There are $n$ players playing a chess championship in one big hall.
Each chess game is between two players and ends in either a draw or
win/loss.  Furthermore, each player plays any other player at most once.
At some point, during the championship the lights in
the hall go out. Prove that, at this point, there exist two players,
among the $n$, who have completed the same number of chess games.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
\bparts
\ppart Show that any subset of a countable set is countable.
\ppart 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.
\ppart Is $\reals - \rationals$ countable?  Prove your answer.
\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\bparts
\ppart Use an diagonalization argument to prove that ${\cal P}(\naturals)$ 
is not countable.
\ppart Show that $|\reals^+|=|\reals|$ by exhibiting an explicit bijection.
$\reals^+$ denotes the positive reals.
\eparts
\end{problems} 
\end{document}


