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

\begin{document}

\pset{7}{October 14, 1997}{October 21}

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

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1
%show bijection, inj etc
\problem
%sec 1.6, problems 11 and 15
 {\bf [10 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.

({\em Note: The inverse of a function is defined in Rosen page 64.})

\begin{itemize}
\item $f(x)=e^x$
\item $f(x)=x^2+3$
\item $f(x)=(x+1)/(x^2+2)$
\item $f(x) = \begin{cases}
              {1 \over x} & \text{if $x \neq 0$},\\
              0 & \text{if $x=0$}
              \end{cases}
$
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2
%some simple theorems with inj,bij

\problem{\bf [10 points]}

Prove that the composition of two injective functions is injective.

({\em Note:  The composition of two functions is defined in Rosen, page 66.})

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
\problem{\bf [10 points]}

Let $A$ and $B$ be finite sets.

\bparts

\ppart
Prove that if $|A| \geq |B|$, then there exists a surjection from
$A$ to $B$.

\ppart
Prove that if $|A| \leq |B|$, then there exists an injection from
$A$ to $B$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
\problem{\bf [20 points]} 
%Mojdeh (part a), The Theory of numbers by Niven..., page 208

\bparts
\ppart{\bf [10 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 [10 points]} Consider a set 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 5
\problem {\bf [10 points]}

Suppose that you have a scale on which you can compare any two groups of 
balls and produce three outcomes (lighter, heavier,  or equal).
You are given five balls. All but one have the same weight. 
You are supposed to find which ball differs and how (lighter or heavier).
Can you do this with two weighings?


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 6
\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{\bf [10 points]}

%Determine whether each of the following sets is countable or
%uncountable. 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.
%\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
\problem{\bf [10 points]}
%sec 1.8, problem 30

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{\bf [20 points]}
%\bparts

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

%\ppart
%Jelly beans of 8 different colors are in 6 jars.  There are 20
%jelly beans of each color.  Use the pigeonhole principle to prove
%that there is some jar that contains at least two beans each from two
%different colors of jelly beans.
%\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 8
\problem{\bf [10 points]}

Let $F$ be the set of all functions $f: \reals \rightarrow
\{0,1\}$.  Show that there is a bijection from $2^{\reals}$ to $F$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 9
\problem {\bf [10 points]}

A real number is {\em algebraic} if it is the root of a
polynomial with rational number coefficients.  Algebraic numbers form
an important part in the study of (what else) modern algebra.  A
number that is not algebraic is called {\em transcendental}.

\bparts

\ppart Prove that for any particular $d$, the set of degree $d$
polynomials with rational coefficients is countable.

\ppart Prove that the set of all roots of degree $d$ polynomials with
rational coefficients is countable (you may use the fact that a degree
$d$ polynomial has at most $d$ roots).

\ppart Prove that the set of algebraic numbers (which is just the
union of the sets in the previous part) is countable ({\em Hint:
use the result of problem 6}).

\ppart Prove that there is a transcendental number.

\eparts

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

\end{problems}

\end{document}
% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
% LocalWords:  Posets poset countability ie



