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

\begin{document}
\psol{7}{October 24, 1997}

\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}


\bigskip

\begin{itemize}

\item $f(x)=e^x$ is an injection because $x\neq y \Rightarrow e^x \neq e^y$. 
It is not a surjection because it maps $\reals$ onto $\reals^+$. Hence, 
it is not a bijection, and so it does not have an inverse.

\item $f(x)=x^2+3$ is not a surjection because it maps $\reals$ onto
$[3,\infty)$.  It's not an injection, because $-1$ and $+1$ have the
same image. Hence, it's not a bijection and it does not have an inverse.

\item 
$f(x)=(x+1)/(x^2+2)$ is not an injection because $0$ and $2$ have the 
same image.  It's not a surjection because $+1$ doesn't have a pre-image
(equivalently the equation $x^2-x+1$ has no real solutions). Therefore
it's not a bijection and it doesn't have an inverse.

\item 
This function is a surjection, because for every $x \in \reals, x\neq 0$, there
exists a $y = 1/x$ such that $f(y) = x$.  $0$ also has a pre-image, 
namely $0$.
It's also a injection because ${1 \over x} = {1 \over y} \Rightarrow
x = y, \forall x,y \neq 0$.  Moreover, if $x \neq 0$, then it is mapped on
a non-zero real number (namely $1/x$).  Therefore $f$ is a bijection. It's
inverse is itself.
\end{itemize}


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

\problem{\bf [10 points]}

Prove that the composition of two injective functions is injective.

\bigskip

Let $f : B \rightarrow C$ and $g : A \rightarrow 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.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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$.

\bigskip

Let $A = \{ a_1, \ldots , a_{|A|} \}$ and $B = \{ b_1, \ldots , b_{|B|} \}$.
Create a function $f$ by setting $f(a_i) = b_i$ for $i \leq |B|$ and
$f(a_i)= b_{|B|}, \forall i > |B|$ (if any).  This function is obviously
a surjection.

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

\bigskip

%By part (a) there is a surjection $f$, from $B$ onto $A$.  
%Let $A = \{ a_1,\ldots, a_n \}$.
%Since $f: B \rightarrow A$ is onto, the subsets of $B$, 
%$f^{-1}(a_1),\ldots, f^{-1}(a_n)$ are non-empty (they are also disjoint
%because $f$ is a function).  Create a function $g: A \rightarrow B$, by
%selecting for each $a_i \in A$ an element of $f^{-1}(a_i)$.
%This function is an injection because the subsets 
%$f^{-1}(a_1),\ldots, f^{-1}(a_n)$ are disjoint.

Let $f:A \rightarrow B$ be the function defined by $f(a_i) = b_i$.
$f$ is an injection.

\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$.

\bigskip

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 consecutive 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 {\bf [10 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$.

\bigskip

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 are done. 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 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?

\bigskip

There are three possible outcomes for each weighting (heavier, lighter,
or equal) so there are $3^2 = 9$ possible outcomes of the experiment
There are five ways to pick the ball of different weight and two ways in 
which the weight can differ (lighter or heavier).  So there are ten different
case and only nine possible outcomes.  Therefore the problem cannot be solved
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.

\bigskip


\begin{proof}
Since each  $S_i$ is countable, it's elements can be listed in a sequence.
Let $s_{ik}$ be the $kth$ element in the listing of $S_i$. 
We list the sets in the following array

\[ \begin{array}{ccccc}
s_{11} & s_{12}  & s_{13} & s_{14} & \cdots \\
s_{21} & s_{22}  & s_{23} & s_{24} & \cdots \\
s_{31} & s_{32}  & s_{33} & s_{34} & \cdots \\
s_{41} & s_{42}  & s_{43} & s_{44} & \cdots \\
\cdots & \cdots  & \cdots & \cdots & \cdots \\
\end{array} \]

We can count the elements using the
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 \}$. 

Since we have been able to give a valid listing, $ {\displaystyle
\bigcup}^\infty_{i=1} {\cal S}_i $ is countable.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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.

\bigskip

%\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 with them must
%be uncountable. But the set of all such functions has at least this
%cardinality, so it, too, must be uncountable. 
%\end{proof}

\begin{proof}
Assume, for the purposes of contradiction, that this set is countable.
Then there is a listing of the function in the set,
 $f_1, f_2,\ldots$.  Now define $f$ such that $f(i) = (f_i(i)+5) \mod 10$.
Then $f$ is not in the list, because $f$ differs from each $f_i$
in the $i$th value.  We have established a contradiction.  We conclude that
the set is uncountable.
\end{proof}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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$.

\bigskip

Let $\phi\colon 2^\reals\to F$ be the function mapping any set 
$A\subseteq \reals$ to the function $\phi_A$ defined as follows:
\[\phi_A(x)=\left\{\begin{array}{ll}
 1 & \mbox{if $x\in A$} \\
 0 & \mbox{otherwise}
 \end{array}\right.\]
We prove that $\phi$ is a bijection, i.e., 
it is injective and surjective.
\begin{itemize}
 \item Injective: Let $A$ and $B$ be two subsets of $\reals$
  such that $A\neq B$. $A$ and $B$ cannot be both empty, so
  assume without loss of generality 
  that there exists some $x$ such that $x\in A$ but $x\not\in B$.
  We have $\phi_A(x)=1\neq 0 = \phi_B(x)$. Therefore 
  $\phi_A\neq \phi_B$ and $\phi$ is injective.
 \item Surjective: Let $f$ be a function from $\reals$
  to $\{0,1\}$. We want to show that $f=\phi_A$ for some $A$.
  Define the set $A=\{x\in \reals \mid f(x)=1\}$.
  We have $\phi_A(x) = f(x)$ for all $x\in \reals$.
  Therefore $\phi_A = f$ and $\phi$ is surjective.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%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.

\bigskip

Let $P_d$ be the set of degree $d$ polynomials with rational 
coefficients.
The function 
\[f\colon (q_0,q_1,\ldots, q_d)\mapsto q_0x^d+q_1x^{d-1}+\cdots+q_d\]
is a surjection from $(\rationals - \{0\}) \times \rationals^d$ 
to $P_d$.
Since the set $(\rationals - \{0\}) \times \rationals^d$ is countable 
(the Cartesian product of finitely many countable sets is countable),
then also the set $P_d$ 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).

\bigskip

Since each degree $d$ polynomial has at most $d$ roots we can give a 
surjection from $P_d\times\{1,\ldots, d\}$ to the set of all 
roots of degree $d$ polynomials with rational coefficients.
For example we can define $f(p(x),i) = x_i$,
where $x_1,\ldots, x_d$ are the roots of $p(x)$
(if $p(x)$ has less then $d$ roots, just repeat the last 
one many times).

\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}).


The set of algebraic numbers is the union of the sets 
of the roots of polynomials with rational coefficients
of degree $d$, for all $d$.
This is a countable union of countable sets,
and from the result in part (a) it is countable.


\ppart Prove that there is a transcendental number.

If there were no transcendental numbers, all numbers would be 
algebraic, i.e., the set of algebraic numbers equals $\reals$.
But this is not possible because the reals are not countable.

\eparts

\end{problems}

\end{document}



