\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Velleman, 5.4.6
\problem\points{10} Suppose, $f \from A \to B$, $f$~is one-to-one
  and onto, and $Y \subseteq B$. Show that the inverse image of~$Y$
  under~$f$ is equal to the image of~$Y$ under~$f^{-1}$.

Hint: Carefully read the definitions of image and inverse image in
\S~5.4 of Velleman.

% Check the solution! I wrote it up, but the problem has never been
% used on any pset. /Lars (spring 2001)
\solution{\begin{proof}
  The inverse image of~$Y$ under~$f$ is the set
  \begin{displaymath}
    X = \{a \in A \mid f(a) \in Y\}
  \end{displaymath}
  and the image of~$Y$ under~$f^{-1}$ is the set
  \begin{displaymath}
    Z  = \{a \in A \mid \exists y \in Y(f^{-1}(y) = a)\}
  \end{displaymath}
  (note that $f^{-1}$ is a function from~$B$ to~$A$).
  
  We first prove that $X \subseteq Z$. Let $x \in X$ and $y = f(x)$.
  By the definition of~$X$, $y \in Y$ and by the definition of
  $f^{-1}$, $f^{-1}(y) = x$. Thus, there exists a~$y \in Y$ such that
  $f^{-1}(y) = x$, and therefore $x \in Z$ by the above definition of~$Z$.
  
  We now prove that $Z \subseteq X$. Let $z \in Z$. By the definition
  of~$Z$ this implies that there exists an $y \in Y$ such that
  $f^{-1}(y) = z$. Thus $f(z) = y \in Y$, which implies, by the
  definition of~$X$ above, that $z \in X$.
  
  To conclude, we have proven that $X \subseteq Z$ and that $Z
  \subseteq X$, which implies that $X = Z$.
\end{proof}}

%BEGIN Kavita's problems
% Fall 1998

%**************
%   PSET 5    *
%**************
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (15 points)}  In 1997 there was a breakthrough on a
long-standing problem in computer science called The Traveling
Salesman Problem.  The idea is that there is a salesman who wants to
visit $n$ cities scattered around the country.  The problem is to
determine the order in which he should visit the cities so as to
minimize the total distance that he travels, assuming that he can go
in a straight line between any two cities.  Surprisingly, this problem
is very difficult when the number of cities $n$ is large.

The breakthrough was an algorithm that efficiently computes a
nearly-optimal solution, a route for the salesman that has length at
most 10\% greater than the shortest possible route.  The running time
of the algorithm is described in the orginal publication as ``nearly
linear'' in the number of cities.  More precisely, the algorithm
requires about $n
\ln^{400} n$ steps.

\begin{problemparts}

\problempart Prove that $n \ln^{400} n$ is $o(n^{1.1})$.  This shows that
the algorithm truly is ``nearly linear'' in an asymptotic sense.  You
may make use of L'Hopital's rule:

\[
        \text{If} \  
\lim_{n\rightarrow\infty} f(n) = \infty
        \ \text{and} \ 
\lim_{n\rightarrow\infty} g(n) = \infty,
        \ \text{then} \  
\lim_{n\rightarrow\infty} \frac{f(n)}{g(n)} =
        \lim_{n\rightarrow\infty} \frac{f'(n)}{g'(n)}.
\]

\solution{
\begin{proof}
We will first use L'Hopital's Rule to prove that the ratio of the two
running times tends to zero.

\begin{eqnarray*}
\lim_{n\rightarrow\infty} \frac{n \ln^{400} n}{n^{1.1}}
        & = & \lim_{n\rightarrow\infty} \frac{\ln^{400} n}{n^{0.1}} \\
        & = & \left( \lim_{n\rightarrow\infty} \frac{\ln n}{n^{1/4000}}
                \right)^{400} \\
        & = & \left( \lim_{n\rightarrow\infty} \frac{1/n}
                {\frac{1}{4000}n^{-3999/4000}}\right)^{400} \\
        & = & \left( \lim_{n\rightarrow\infty} \frac{4000}
                {n^{1/4000}}\right)^{400} \\
        & = & 0^{400} \\
        & = & 0
\end{eqnarray*}

The first step is simplification.  The second step uses the fact that
the limit of a product is the product of the limits.  L'Hopital's rule
is applied in the third step, and the remaining steps are
simplifications.

The definition of a limit implies that for all $c > 0$, there exists
an $n_0$ such that $n \ln^{400} n / n^{1.1} < c$ for all $n \geq
n_0$.  Rewriting this inequality as $n \ln^{400} n < c n^{1.1}$, we
establish that $n \ln^{400} n = o(n^{1.1})$ by the definition of $o$.
\end{proof}
}

\problempart Find a specific value of $n$ such that $n^{1.1}$ is actually
greater than $n \ln^{400} n$.

\solution{ We forgot to rule out small values of $n$.  Thus, for
example, $n = 1$ is an acceptable answer worth full credit.  However,
you are a SUPERIOR HUMAN BEING if you followed the intent of the
question and identified an $n$ such that the inequality holds for that
value and for all larger values.

Suppose that we choose $n = e^{50000}$, a number with more than
twenty-one thousand digits.  Then $n^{1.1}$ is equal to $e^{55000}$,
and $n \ln^{400} n$ is equal to $e^{50000} \cdot 50000^{400} =
e^{50000 + 400 \ln 50000} \approx e^{54328}$, which is a little
smaller.

Note that setting $n$ equal to $e^{40000}$--- a paltry seventeen
thousand digit number--- would not suffice.  Asymptotic notation can
be misleading!  }

\end{problemparts}

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

\problem {\bf (10 points)}  Order the functions in each set below so that
each function is either $O$ or $\Theta$ of the next function.
Indicate whether the stronger $\Theta$ relationship holds in each
case.  No proofs are required.

{\bf Example. \quad} $n^2$, $n$, $n^3 / (n + 1)$, $3n^2$
\begin{eqnarray*}
n       & = &   O(n^2) \\
n^2     & = &   \Theta(3n^2) \\
3n^2    & = &   \Theta(n^3 / (n+1))
\end{eqnarray*}

\begin{problemparts}
\problempart $\ln n, \ln \sqrt{n}, \sqrt{\ln n}, n^{1/n}$

\solution{
\begin{eqnarray*}
n^{1/n}         & = &   O(\sqrt{\ln n}) \\
\sqrt{\ln n}    & = &   O(\ln \sqrt{n}) \\
\ln \sqrt{n}    & = &   \Theta(\ln n)
\end{eqnarray*}
}

\problempart $(\sqrt{n})^{2 \ln \ln n}, n, n \ln n, \ln n^{\ln n},
\ln n!$

\solution{ The notation $\ln n^{\ln n}$ was ambiguous, and so two
solutions are acceptable.

\begin{eqnarray*}
n               & = &   O(n \ln n) \\
n \ln n & = &   \Theta(\ln n!) \\
\ln n!          & = &   O((\ln n)^{\ln n}) \\
(\ln n)^{\ln n} & = &   \Theta((\sqrt{n})^{2 \ln \ln n})
\end{eqnarray*}

Alternatively,

\begin{eqnarray*}
\ln(n^{\ln n})  & = &   O(n) \\
n               & = &   O(n \ln n) \\
n \ln n         & = &   \Theta(\ln n!) \\
\ln n!          & = &   O((\sqrt{n})^{2 \ln \ln n})
\end{eqnarray*}
}

\problempart $n!, n^n, (n/3)^n, n^{n + \ln \ln n}, e^{n \ln \ln n}$

\solution{
\begin{eqnarray*}
e^{n \ln \ln n} & = &   O((n/3)^n) \\
(n/3)^n                 & = &   O(n!) \\
n!                      & = &   O(n^n) \\
n^n                     & = &   O(n^{n + \ln \ln n})
\end{eqnarray*}

The hardest relation here was probably $(n/3)^n = O(n!)$.  The
integral method gives the following.

\begin{eqnarray*}
\ln n!  & \geq &        \int_1^n \ln u \ du \\
        & = &           n \ln n - n + 1 \\
n!      & \geq &        e^{n \ln n - n + 1} \\
        & \geq &        \left(\frac{n}{e}\right)^n
\end{eqnarray*}

The ratio $(n/3)^n$ divided by $(n/e)^n$ is equal to $(e/3)^n$, which
tends to 0 as $n$ goes to infinity.  This implies an $O$-relationship
rather than a $\Theta$-relationship.  }

\end{problemparts}

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

\problem {\bf (20 points)} Recently, Theory Pig found a small piece of
blue crayon behind the filing cabinet in Professor Lynch's office.
Theory Pig was delighted to find that with this wondrous new toy he
could draw pretty blue rectangles with a width of $w$ centimeters and
a height of $\ln w$ centimeters for any $w > 1$ that he took a fancy
to.

\centerline{
\begin{picture}(250,200)
\put(0,50){\framebox(200,100)}
\put(95,160){$w$}
\put(210,100){$\ln w$}
\end{picture}
}

Our pal proudly presented this remarkable discovery to 6.042 TA
Rodrigo Leroux.  Rodrigo was unimpressed: ``Yeah, but what if I want a
rectangle with an area of $n$ square centimeters?  Then what should be
the width $w$?''  Fidgeting nervously with his crayon, Theory Pig
replied that he believed the width should be $\Theta(n / \ln n)$
asymptotically, but that unfortunately he could not rigorously prove
this fact.  Rodrigo replied, ``If you can't play with your toys
properly, then they'll be taken away!''  And then he confiscated
Theory Pig's crayon!

Return joy to our little pal's world by supplying a proof of his
claim.

\solution{
Let $f(w) = w \ln w$.  Then a rectangle with width $w$ has area
$f(w)$.  Consequently, a rectangle with area $n$ should have width
$f^{-1}(n)$.  We can now formalize the problem as follows.

\bigskip
{\bf Claim. \quad} If $f(w) = w \ln w$, then $f^{-1}(n) = \Theta(n /
\ln n)$.
\bigskip

\begin{proof}
We must prove that there exists an $n_0$ and constants $c_1, c_2 > 0$
such that for all $n > n_0$

\[
c_1 \cdot \frac{n}{\ln n} \geq f^{-1}(n) \geq c_2 \cdot \frac{n}{\ln n}.
\]

Since $f$ is an increasing function, the above inequalities hold if
and only if

\begin{eqnarray*}
f\left(c_1 \cdot \frac{n}{\ln n}\right) \geq
        f(f^{-1}(n)) \geq
        f\left(c_2 \cdot \frac{n}{\ln n}\right).
\end{eqnarray*}

Suppose that we choose $c_1 = e$ and $c_2 = 1$.  Then the inqualities
can be rewritten as follows:

\begin{eqnarray*}
e \cdot \frac{n}{\ln n} \cdot \ln\left(
                e \cdot \frac{n}{\ln n} \right) \geq
        n \geq
        \frac{n}{\ln n} \cdot \ln\left( \frac{n}{\ln n} \right) \\ \\
n \cdot \left(e + \frac{e}{\ln n} - \frac{e \ln \ln n}{\ln n}\right) \geq
        n \geq
        n \cdot \left(1 - \frac{\ln \ln n}{\ln n}\right)
\end{eqnarray*}

In the expression on the left, the $e \ln \ln n / \ln n$ term is
$o(1)$, and so the expression in parentheses is greater than 1 for all
sufficiently large $n$.  In the expression on the right, the $\ln
\ln n / \ln n$ term is positive for all $n > e$, and so the expression is
parentheses is less than 1 for all sufficiently large $n$.  Therefore,
there exists an $n_0$ such that both inequalities hold for all $n >
n_0$ as desired.
\end{proof}
}


%**************
%   PSET 7    *
%**************

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

%  Largely stolen from Fall 97.

\problem {\bf (10 points)} For each of the functions below, determine
whether the function is injective, whether it is surjective, and
whether it is bijective.  No proofs are required.

\begin{problemparts}
\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ defined by
$f(x)=e^x$

\solution{ The function is injective because $e^x = e^y$ if and only
if $x = y$.  The function is not surjective, because $e^x$ never takes
on non-positive values.  The function is not bijective, because it is
not surjective.  }

\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}^+$
defined by $f(x)=e^x$.  (Here $\mathbb{R}^+$ denotes the set of
positive real numbers.)

\solution{The function is injective as before, but is now also surjective
because for every $y \in \mathbb{R}^+$, there exists an $x$ (namely $x
= \ln y$) such that $y = e^x$.  Therefore, the function is bijective.}

\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ defined
by $(x+1)/(x^2+1)$

\solution{ The function is not injective, because $f(0) = f(1) = 1$.
The function is not surjective, because the function never takes on
large positive or negative values.  The function is not bijective
because it is neither injective nor surjective.}

\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ defined
by

\begin{eqnarray*}
f(x) & = & \left\{
\begin{array}{cl}
1/x & \text{for $x \neq 0$} \\
0 & \text{for $x = 0$.}
\end{array}
\right.
\end{eqnarray*}

\solution{ The function is injective, because $f(x) = f(y)$ if and
only if $x = y$.  The function is surjective, because for all $y \in
\mathbb{R}$, there exists an $x$ (namely $x = 1 / y$ or $x = 0$) such
that $f(x) = y$.  Therefore, the function is also bijective.}

\end{problemparts}


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

\problem {\bf (10 points)} Suppose that $f$ is a function of the form
$f: A \mapsto B$, and $g$ is a function of the form $g: B \mapsto C$.
The composed function $g \circ f$ has domain $A$, range $C$, and is
defined by $(g \circ f)(a) = g(f(a))$.

\begin{problemparts}

\problempart Prove that if the composition $g \circ f$ is a bijection,
then $f$ is an injection and $g$ is a surjection.

\solution{
\begin{proof}
Suppose that $g \circ f$ is a bijection.

Assume for the purpose of contradiction that $f$ is not an injection.
Then there exist elements $a_1, a_2 \in A$, such that $f(a_1) =
f(a_2)$.  This implies that $g(f(a_1)) = g(f(a_2))$.  Therefore, $g
\circ f$ is not an injection and thus not a bijection.  This is a
contradiction; therefore, $f$ must be an injection.

Now assume for the purpose of contradiction that $g$ is not a
surjection.  Then there exists an element $c \in C$ such that for all
$b \in B$, $g(b) \neq c$.  Therefore, for all $a \in A$, $g(f(a)) \neq
c$.  This implies that $g \circ f$ is not a surjection and thus not a
bijection.  This is again a contradiction; therefore, $g$ must be a
surjection.
\end{proof}
}

\problempart If $f$ is an injection and $g$ is a surjection, then is
$g \circ f$ necessarily a bijection?

\solution{
No.  For example, consider the following setup.

\begin{eqnarray*}
A & = & \{ 1 \} \\
B & = & \{ 1, 2 \} \\
C & = & \{ 1, 2 \} \\
\\
f(x) & = & x \\
g(x) & = & x
\end{eqnarray*}

In this case, $f$ is injective, $g$ is surjective, but $g \circ f$ is
not bijective.  }

\end{problemparts}

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

%END   Kavita's problems

%BEGIN Joe's problems
\problem %source: spring00 ps6
\textbf{Injections, Surjections, and Bijections}
%[[[Source:  first two parts are standard, second two are from
%Velleman, p. 231, Ex. 6]]]

Let $f$ be a function from $A$ to $B$, and $g$ a function from $B$ to
$C$.  The composition $g \circ f$ is defined by:
$g \circ f (x) = g(f(x))$.

%[[[Check that my notation is consistent with what's been used in the
%class, in Rosen, etc.]]]

Determine whether each of the following statements is true or false.
If it's true, prove it.  If it's false, give a counterexample.

\begin{problemparts}

\vspace{-\baselineskip}
\problempart
If $f$ and $g$ are both injective then $g \circ f$ is injective.

\vspace{-\baselineskip}
\problempart
If $f$ and $g$ are both surjective then $g \circ f$ is surjective.

\vspace{-\baselineskip}
\problempart
If $f$ is surjective and $g \circ f$ is injective then $g$ is injective.

\vspace{-\baselineskip}
\problempart
If $g$ is injective and $g \circ f$ is surjective then $f$ is surjective.

\end{problemparts}

%END   Joe's problems

%BEGIN Ray's problems

%%%%%%%%  S99 ps5

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (10 points)} Use the integral method to find a $\Theta$
bound on the following sum.

\[
\sum_{i=1}^n i \ln i
\]

\solution{
We can bound the sum with two integrals.

\[
\int_1^n i \ln i \ di \ \leq \ 
        \sum_{i=1}^n i \ln i \ \leq \  
        \int_1^n (i+1) \ln(i+1) \ di
\]

Integration by parts gives the indefinite integral

\begin{eqnarray*}
\int i \ln i \ di
        & = &   \frac{1}{2} i^2 \ln i - \frac{1}{4} i^2 + C
\end{eqnarray*}

Substituting the appropriate integration ranges gives the bound
$\Theta(n^2 \ln n)$.}


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

\problem {\bf (20 points)} In analyzing algorithms, one often must
determine the asymptotic behavior of nasty functions like those
shown below.

\[
\begin{array}{ccc}
\iffalse \hspace{2cm} & n^{10} - n^{9} &\hspace{2cm} \fi
n! & (\ln n)^{300} & 2 n^{\ln \ln n}  \\
\iffalse  & \sum_{i=0}^n \sqrt{i}\fi
n^n & n (\ln n)^{4} & n^{1.01}/2 \\
7 n^2 + 3 & \sqrt{n}^{\sqrt{n}} & 4^n \\
\iffalse  & \frac{(2n)!}{n! \ n!}\fi
(n/e)^n & (7n^3 - 17n^2)/(n + 128) & (\ln n)^{\ln n}
\end{array}
\]

Arrange these functions in a list so that each is $\Theta$ or $O$ of
the next function in the list.  For each pair of consecutive functions
in your list, indicate whether the stonger $\Theta$ relationship holds
or only the weaker $O$ relationship.  No proofs are required.

\solution{
\begin{eqnarray*}
(\ln n)^{300}           & = & O\left(n (\ln n)^{4}\right) \\
n (\ln n)^{4}           & = & O\left(\frac{1}{2} n^{1.01}\right) \\
\frac{1}{2} n^{1.01}    & = & O\left(7 n^2 + 3\right) \\
7 n^2 + 3               & = & \Theta\left(\frac{7n^3 - 17n^2}
                                        {n + 128}\right) \\
\frac{8n^3 - 17n^2}
        {n + 128}       & = & O\left((\ln n)^{\ln n}\right) \\
(\ln n)^{\ln n}         & = & \Theta\left(2 n^{\ln \ln n}\right) \\
2 n^{\ln \ln n}         & = & O\left(\sqrt{n}^{\sqrt{n}}\right) \\
\sqrt{n}^{\sqrt{n}}     & = & O\left(4^n\right) \\
4^n                     & = & O\left(\left(\frac{n}{e}\right)^n\right) \\
\left(\frac{n}{e}\right)^n
                        & = & O\left(n!\right) \\
n!                      & = & O\left(n^n\right)
\end{eqnarray*}
}




%%%%%%%%%%%%%%%%%%%%%% S99 ps7


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

\problem {\bf (10 points)} Let $A$, $B$, and $C$ be finite sets.  Let
$f$ be a function mapping $A$ to $B$, $g$ be a function mapping $B$ to
$C$, and $h$ be a function mapping $C$ to $A$.  No proofs are required
for this problem.

\begin{problemparts}

\problempart Suppose that $h(g(f(a))) = a$ for all $a$ in $A$.  Which
functions must be injective and which must be surjective?

\solution{The function $f$ must be injective, and the function $h$
must be surjective.}

\problempart Suppose also that $|A| = |C|$.  Now which functions must
be injective and which must be surjective?

\solution{The functions $f$ and $h$ must be injective, and the
functions $g$ and $h$ must be surjective.}

\problempart Suppose also that $f$ is invertible.  Now which functions
must be injective and which must be surjective?

\solution{All of the functions must be both injective and surjective.}

\end{problemparts}

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

\problem {\bf (15 points)} Recall that in the game Lights Out there is
an $m \times n$ grid of squares, each of which is lit or unlit.
Pressing a square switches the light on that square and on all squares
that share an edge with the one pressed.  The solution to this
(solitary) game is a subset of squares s.t. if initially all lights on
the grid are lit then pressing all squares in this subset will turn
all the lights on the grid off.

Note that pressing a sequence of squares has the same effect as
pressing the same squares in any other order.  Also, note that
pressing a square twice has the same effect as not pressing it at all.
Therefore, if a configuration of lights can be reached at all, then it
can be reached by pressing some set of squares in an arbitrary order.

In this problem we want you to think about the function $f_{m,n}$ that
maps each subset of the squares in an $m \times n$ grid to the subset
of lights that are switched if those squares are pressed.  For
example, let's look at the value of function $f_{2,3}$ on argument
$A$, a particular subset of squares in the $2\times{3}$ grid:
\[
A=
\begin{array}{|c|c|c|}
\hline
x&\hspace{1ex}&\hspace{1ex}\\ \hline
&x&\\ \hline
\end{array}
\]
Then $B=f_{2,3}(A)$ is the following subset of lights:
\[
B=f_{2,3}(A)=
\begin{array}{|c|c|c|}
\hline
x&\hspace{1ex}&\hspace{1ex}\\ \hline
&x&x\\ \hline
\end{array}
\]

Include a brief explanation with your answers to the following
questions:

\begin{problemparts}
\problempart First, consider the function $f_{3,3}$.  Recall that for
a $3 \times 3$ grid, every configuration of lights can be reached from
the initial state where all lights are on.  Is this function
injective?  Is it surjective?

\solution{The function is surjective, since every configuration of
lights can be achieved by pressing some set of squares.  The domain
has size $2^9$, since every square is either pressed or not pressed.
The range also has size $2^9$, since every square is lit or unlit.
Therefore, the function is also injective.}

\problempart Is the function $f_{2,3}$ injective?  Is it surjective?

\solution{Pressing the set of squares indicated below has the same
effect as pressing no squares at all.  Consequently, the function is
not injective.  Since the domain and range again have the same size
(now $2^6$), the function can not be surjective.

\[
\begin{array}{|c|c|c|}
\hline
x&\hspace{1ex}&x\\ \hline
x& &x\\ \hline
\end{array}
\]
}

\problempart A solution to the $5 \times 5$ version of Lights Out is
shown below; if the marked squares are pressed, then all lights are
switched.

\[
\begin{array}{|c|c|c|c|c|}
\hline
x& &x&x& \\ \hline
 &x&x&x& \\ \hline
x&x&x& & \\ \hline
x&x& &x&x\\ \hline
 & & &x&x\\ \hline
\end{array}
\]

Is the function $f_{5,5}$ injective?  Is it surjective?

\solution{Three more solutions can be obtained by rotation.
Therefore, the function is not injective.  Since the domain and range
are the same size (now $2^{25}$), the function is not surjective
either.}

\end{problemparts}


%%%%%%%%%%%%%%%%%%  S99 ps8


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem{\bf (15 points)}

\bparts

\ppart (10 points) Let $[0,1]$ be the closed unit line segment, i.e.,
$\set{r \in \reals \mid 0 \leq r \leq 1}$.  Show that there is a bijection
from $[0,1]$ to the whole real line, i.e., to $\reals$.

\solution{
Obviously, $f_1:[0,1] \to \reals$ s.t. $f(x)=x$ is an injection
between the two sets.  There are many ways to construct a surjection
$f_2:[0,1] \to \reals$.  For example, it can be a superposition
$f_2(x)=h(g(x))$ of two surjections $g:[0,1] \to [-1,1]$ and
$h:[-1,1] \to \reals$ defined as follows:
\begin{eqnarray*}
g:[0,1]\rightarrow[-1,1]
&&
g(x)=2x-1
\\
h:[-1,1]\rightarrow\reals
&&
h(x)=\left\{\begin{array}{llr}
        1/x-1   & x>0   & \mbox{map $(0,1]$ to $[0,\infty)$}\\
        0       & x=0   &\\
        1/x+1   & x<0   & \mbox{map $[-1,0)$ to $(-\infty,0]$}
        \end{array}
       \right.
\end{eqnarray*}

If there is a surjection from $[0,1]$ to $\reals$ then, by an
elementary fact listed in Lemma 2.3 in Handout 38, there exists an
injection from $\reals$ to $[0,1]$.  Therefore, by the
Schroeder-Bernstein theorem (Tutorial 8, and section 5 in Handout 38),
there exists a {\em bijection} between $[0,1]$ and $\reals$.


{\bf Alternative Solution:}

Some students constructed a direct bijection between $[0,1]$ and
$\reals$ by superimposing two bijections: $f_1:[0,1] \to (0,1)$ and
$f_2:(0,1) \to \reals$:
\begin{eqnarray*}
f_1(x) & = &
  \left\{
  \begin{array}{ll}
     1/(n+2) & \mbox{if $x= 1/n$ for some $n\in\naturals, n>0$,}\\
     1/2   & \mbox{if $x=0$,}\\
      x            & \mbox{otherwise.}
   \end{array}
  \right.\\
f_2(x) & = & \tan \left(\pi x-\frac{\pi}{2}\right)
\end{eqnarray*}
}

\ppart (5 points) Conclude that there is a bijection between the unit line
segment and the whole plane, i.e., between $[0,1]$ and $\reals \times
\reals$. \hint See Handout 38: Notes on Cardinality.

\solution{
By Theorem 7.2 in Handout 38, there is a bijection between $\reals$
and $\reals^2=\reals\times\reals$.  By Part (a), there is a bijection
between $[0,1]$ and $\reals$.  Hence, by transitivity of bijective
relation between sets, there is a bijection between $[0,1]$ and
$\reals^2$.
}

\eparts  

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

%%%%%%%%%%%%%%%%%%%%% S99 ps8

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

\problem {\bf (10 Points)}

In this problem, we will have to be careful about the technical
distinction between the \emph{range} and the \emph{codomain} of a
function.

If $D$ and $C$ are sets, the notation $f:D \to C$ indicates that $f$ is a
total function with \emph{domain} $D$ and \emph{codomain} $C$.  This means
that for every element, $d$, of the domain, $D$, there is a unique
element, denoted $f(d)$, in the codomain, $C$, that is determined by $f$.
The \emph{range of $f$} is the set of values actually taken by $f$, namely
\[
\mbox{range}(f) :: = \set{d \mid \exists c \in C :\ d = f(c)}.
\]
It follows that the range of a function is in general just a \emph{subset}
of its codomain, and equals the codomain precisely when the function is a
surjection.

Now let $\{0,1\}^n$ be the set of all bit strings of length $n$.

\bparts

\ppart

How many functions are there with domain $\{0,1\}^m$ and codomain
$\{0,1\}^n$?


\solution{There are $2^m$ elements in the domain.  There are $2^n$
elements in the codomain.  For every element in the domain, we thus have
$2^n$ choices for what we can map it to.  Therefore, by the product rule,
there are $(2^n)^{2^m}$ possible functions with domain $\{0,1\}^m$ and
codomain $\{0,1\}^n$.}

\ppart


How many functions with domain and codomain $\{0,1\}^n$ are {\em not
bijections}?

\solution{There are $2^n$ elements in both the domain and codomain.  Hence
there are a total of $(2^n)^{2^n}$ functions.  When the domain and
codomain coincide as in this case, the bijections are precisely the same
as permutations of the domain.  We know that there are $(2^n)!$ of these
permutations.  Hence the remaining are not bijections.  The total number
of functions with domain and codomain $\{0,1\}^n$ that are not bijections
is therefore $(2^n)^{2^n} - (2^n)!$.}

\ppart

A value $x$ is called a {\em fixed point} of a function $f$ if $f(x) = x$.
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em no} fixed
points?

\solution{We have $2^n$ elements in the domain, and each of them can
possibly be mapped to $2^n - 1$ elements in the codomain---to any element
but itself.  Therefore, there are $(2^n-1)^{2^n}$ such functions with no
fixed points.}

\ppart 
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em at least one} 
fixed point?

\solution{There are $(2^n)^{2^n}$ functions, and $(2^n-1)^{2^n}$ have no
fixed points.  Therefore, the remaining $(2^n)^{2^n} - (2^n-1)^{2^n}$ have
at least one fixed point.}

\ppart
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em exactly one} 
fixed point?

\solution{Let's fix a particular point for our fixed point.  Now let's
consider where the remaining $2^n - 1$ points can be mapped.  Each one can
be mapped to any spot but itself---thus it can be mapped to exactly $2^n
- 1$ possible spots.  So there are $(2^n - 1)^{2^n - 1}$ functions with
exactly this particular fixed point and no other.  Now there are $2^n$
possible choices for the particular fixed point, so the total number of
functions with exactly one fixed point is $2^n(2^n - 1)^{2^n - 1}$.}

\eparts



%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset5 problem5 spring98
\problem 
Justify your answers to the following:
\bparts
\ppart Is $2^n = O(4^n)$? 

\solution{
Yes, $2^n=O(4^n)$. To show this, we need to find an $n_0$ and a $c$ that
satisfy the definition of $O$, specifically,
$\forall n>n_0, 2^n<c \cdot 4^n$.
Choose $n_0=0$ and $c=1$. Then we have
$\forall n>0, 2^n<4^n$, which is certainly true.
}

\ppart Is $2^{2n} = O(2^n)$? 

\solution{
$2^{2n}$ is not $O(2^n)$.
To prove that $2^{2n}=O(2^n)$, we
have to find an $n_0$ and $c$ for which
$\forall n>n_0, 2^{2n}<c \cdot 2^n$.
Let's divide both sides by $2^n$, which we can do since $2^n$ is
always positive, and never equal to $0$. Then we have 
$\forall n>n_0, 2^n<c$.
Since $2^n$ is unbounded as $n \rightarrow \infty$, there's
no $n_0$ for which $2^n$ will be less than a constant.
}

\ppart Is $2^{n+1} = O(2^n)$?

\solution{
Yes, $2^{n+1}=O(2^n)$, with (for example) $c=2$, and $n_0=0$.
}

\ppart Is $\log_{10} x = \Theta (\log_2 x)$?

\solution{
Yes.
The change of base formula tells us that
$\log_an={{\log_cn} \over {\log_c a}}$.
Therefore, we know that $\log_{10} n = {{\log_2n} \over {\log_2 10}}$.
For all $n>0$, $\log_{10} n$ is within a constant factor, namely ${1 \over {\log_2 10}}$, of $\log_2 n$.
}
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset5 problem6 spring98
\problem 
Find a $\Theta$ bound for $\sum_{k=1}^n k^6$.

\solution{
Let $\sum_{k=1}^n k^6 = S_n$.

There are $n$ terms in $S_n$ and each term is at most $n^6$, so 
$S_n \leq n \cdot n^6 = n^7 = O(n^7)$. So $S_n=O(n^7)$.

On the other hand, at least $(n-1)/2$ of the terms are as large as $[(n-1)/2]^6$, 
so 
\begin{eqnarray*}
S_n &\geq & ((n-1)/2) \cdot [(n-1)/2]^6\\
    & = & [(n-1)/2]^7 \\
    & \geq & (n/3)^7
\end{eqnarray*}
for $n>3$,  so $n^7 \leq 3^7 \cdot S_n$. In other words, $n^7 = O(S_n)$. Since we've shown $S_n=O(n^7)$ and $n^7 = O(S_n)$, we know that  $S_n = \Theta(n^7)$.


We can also do this problem using the Integral Method:

\begin{eqnarray*}
\int_0^n x^6 \ dx \leq \sum_{k=1}^n k^6 \leq \int_0^n (x+1)^6 \ dx \\
\frac{n^7}{7} \leq \sum_{k=1}^n k^6 \leq \frac{(n+1)^7}{7} - \frac{1}{7}
\end{eqnarray*}

From which we see that  $\sum_{k=1}^n k^6 = \Theta(n^7)$
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset5 problem7 spring98
\problem 

Prove or give a counterexample: If $f(n) = \Theta(n)$, then $\sum_{i=1}^n f(i)
= \Theta(n^2)$.

\solution{
If $f(n) = \Theta(n)$, we know that $\exists c_1, c_2, k >0$, such that
$\forall n>k, c_1n\leq f(n)\leq c_2n$.  Let's assume that $n > 2k$.  (Note
that we can make assumptions of this type since we're free to choose the
lower bound on $n$ needed in the definition of the $\Theta$ bound that
we're proving.  That is, we're going to prove that $a_1n^2 \leq
\sum_{i=1}^n f(i) \leq a_2 n^2$ for all $n>n_0$, and we can make the $n_0$
as large as we'd like.)

Let's look at $\sum_{i=k+1}^n c_1 i$.  Since $n > 2k$, at least ${n \over 2}$ terms in the sum must be bigger than $c_1 {n \over 2}$, which we can state mathematically as follows:

\begin{eqnarray*}
({n \over 2})^2 \cdot c_1 & \leq & \sum_{i=k+1}^n c_1 i \\
& \leq &  \sum_{i=k+1}^n f(i)\\  %from the fact that f(i)=\Theta(n) 
& \leq &  \sum_{i=k+1}^n c_2 i \\
& \leq &  \sum_{i=k+1}^n c_2 n \\
& \leq & c_2 n^2.
\end{eqnarray*}

So, $${c_1 \over 4} n^2 \leq \sum_{i=k+1}^n f(i) \leq c_2n^2$$
Now we need to manipulate this to get the summation to start at
$1$, rather than $k+1$. (Note that the definition of $\Theta$ will only
let us assume that $c_1n \leq f(i) \leq c_2n$ for $i>k$, so we need
to find some other method of dealing with the sum from $1$ to $k$).

Let $s=\sum_{i=1}^{k}f(i)$. Then, by adding $s$ to each part of
the inequality above, we get
$${c_1 \over 4}n^2 + s \leq \sum_{i=1}^n f(i) \leq c_2n^2 + s$$

Now, assume that $n \geq \sqrt{\abs {s}}$, so we can write
$c_2n^2+s \leq (c_2+1)n^2$ 

Assume $n \geq \sqrt{ 8\abs {s}/c_1}$, so ${\displaystyle {c_1 \over 8}n^2 \leq {c_1 \over 4}n^2 +s}$

So, letting $n_0 = max(2k, \sqrt{\abs s}, \sqrt{8 \abs{s} / c_1})$, we now
know that for all $n>n_0$,
\[{c_1 \over 8}n^2 \leq {c_1 \over 4}n^2 + s \leq \sum_{i=1}^n f(i) \leq
c_2n^2+s \leq (c_2+1)n^2,\]
which satisfies the definition of $\Theta(n^2)$, with
$a_1={c_1 \over 8}, a_2=c_2+1$. \qed
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset6 problem5 spring98 injections, bijections, surjections see ps7 fall97
\problem

For each of the following functions, $f: \reals \rightarrow \reals$, determine whether it is an injection,
surjection, or bijection, and give the inverse if it exists.  (The inverse
of a function is defined in Rosen page 64).

\bparts

\ppart
$f(x) = sin(x)$

\solution{
{\bf Solution:}
$f(x) = sin(x)$ is not an injection because it maps
$0$ and $\pi$ to $0$.  It is not a surjection because
it maps $\reals$ onto $[-1,1]$.  Therefore it is not a 
bijection and does not have an inverse. 
}

\ppart
$f(x) = {{x+2}\over{x^2 + 4}}$

\solution{
{\bf Solution:}
$f(x) = {{x+2}\over{x^2 + 4}}$ is not an injection because
it maps $0$ and $2$ to ${1}\over{2}$.  It is not a surjection
because $1$ has no pre-image.  $x^2 + 4 = x+2$ has no
real solutions.  Therefore it is not a bijection and
does not have an inverse.
}

\ppart
$f(x) = \begin{cases}
        {ln x} & \text{if $x > 0$},\\
        0 & \text{if $x=0$}, \\
        {e^x} & \text{if $x < 0$}
        \end{cases}$

\solution{
{\bf Solution:}
This function is not an injection because $ln {{1}\over{2}}$ and
$e^{{1}\over{2}}$ both map to ${1}\over{2}$.  It is a
surjection because for any $x \in \reals$, a pre-image of 
$x$ is $e^x$ for $x \neq 0$, and $0$ for $x=0$.  
}

\ppart
$f(x) = x^3 + 2$

\solution{
{\bf Solution:}
$f(x) = x^3 + 2$ is an injection because $x \neq y \rightarrow
x^3 \neq y^3 \rightarrow x^3 + 2 \neq y^3 + 2$.  The function is
a surjection because for every $x \in \reals$  $\exists y = (x-2)^{{1}\over{3}}$.  Therefore $f$ is a bijection.  It's inverse is 
$(x-2)^{{1}\over{3}}$.
}
\eparts

%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%  Fall 2000   Problem Set 6    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%


\problem {\bf (10 points)} The expression $\binom{n}{k}$ is read ``$n$
choose $k$'' and represents the quantity
\[\frac{n!}{k! \ (n-k)!}.\]
This expression comes up frequently in probability and combinatorics
and will be used extensively later in this course.  Suppose that $n$
is even.  Prove that

\begin{eqnarray*}
\binom{n}{n/2}
    & = &   \Theta(2^n / \sqrt{n}).
\end{eqnarray*}

Use the following form of Stirling's formula:

\begin{eqnarray*}
n!  & \sim &    \sqrt{2 \pi n} \left(\frac{n}{e}\right)^n
\end{eqnarray*}

\solution{
\textbf{Solution:}\\
Though substituting in Stirling's formula initially gives a
complicated expression, most of the square roots and the exponentials
cancel.

\begin{eqnarray*}
\binom{n}{\alpha n}
    & = &   \frac{n!}{(\alpha n)! \ ((1-\alpha) n)!} \\
    & \sim &    \frac{\sqrt{2 \pi n} \left(\frac{n}{e}\right)^n}
    {\sqrt{2 \pi \alpha n} \left(\frac{\alpha n}{e}\right)^{\alpha n}
    \cdot
    \sqrt{2 \pi (1-\alpha) n} \left(\frac{(1-\alpha) n}{e}\right)^{(1-\alpha) n}} \\
    & = &   \frac{1}{\sqrt{2 \pi n \alpha (1 - \alpha)}} \cdot
        \frac{1}{\alpha^{\alpha n} \cdot (1-\alpha)^{(1-\alpha)n}}
\end{eqnarray*}

Letting $\alpha = 1/2$,
\begin{eqnarray*}
\binom{n}{\alpha n}
    & \sim &    \frac{1}{\sqrt{2 \pi n \alpha (1 - \alpha)}} \cdot
        \frac{1}{\alpha^{\alpha n} \cdot (1-\alpha)^{(1-\alpha)n}} \\
    & = &   \frac{1}{\sqrt{2 \pi n \alpha (1 - \alpha)}} \cdot
        2^n \\
    & = &   \Theta\left(\frac{2^n}{\sqrt{n}}\right).
\end{eqnarray*}
}
      
%%%%%%%%%%%%%%  Fall 2000   Problem Set 6    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem \textbf{Asymptotic notation}
% problem 1, problem set 7, fall 1999

For each pair of functions $(f(n), g(n))$ in the table below, indicate
whether the statement at the top of the column is true (e.g., whether
$f(n) = O(g(n))$).  Assume $k\geq 1$, $\epsilon > 0$, and $c > 1$ are
constants. Your answer should be in the form of a table with ``yes''
or ``no'' in each box.

\vspace*{-0.5\baselineskip}

\begin{equation*}
  \begin{array}{|cc|*{3}{c|}}
    \hline
    f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n)) & f(n) =
    \Theta(g(n)) \\\hline\hline
    \log^k n & n^\epsilon &&&\\\hline
    n^k & c^n &&&\\\hline
    \sqrt{n} & n^{\sin n} &&&\\\hline
    2^n & 2^{n/2} &&&\\\hline
    \log(n!) & \log(n^n) &&&\\\hline
  \end{array}
\end{equation*}

\solution{
\textbf{Solution:}\\
  \newcommand\y{\text{yes}}
  \newcommand\n{\text{no}}
%
  \begin{equation*}
    \begin{array}{|cc|*{3}{c|}}
      \hline
      f(n) & g(n) & f(n) = O(g(n)) & g(n) = O(f(n)) & f(n) =
      \Theta(g(n)) \\\hline\hline
      \log^k n & n^\epsilon & \y & \n & \n \\\hline
      n^k & c^n & \y & \n & \n \\\hline
      \sqrt{n} & n^{\sin n} & \n & \n & \n\\\hline
      2^n & 2^{n/2} & \n & \y & \n \\\hline
      \log(n!) & \log(n^n) & \y & \y & \y \\\hline
    \end{array}
  \end{equation*}
  
  Following are some hints on deriving the table above:\\
  (a) See notes on $O$-notation. (to appear)\\
  (b) Polynomial growth versus exponential growth. (See Theorem 3.6,
  Lecture 9, Fall97.)\\
  (c) When $n$ is a multiple of $\pi$, $n^{\sin n}=1$, so no
  constant times 1 will bound $\sqrt n$ as $n$ ranges over
  multiples of $\pi$. When $n$ is of the form $2k'\pi + \pi/2$,
  for some integer $k'$, then $n^{\sin n}=n$ and $\frac{n}{\sqrt n} =
  \sqrt n$ grows without bound as $k'$ increases.\\
  (d) $\frac{2^n}{2^{n/2}}=2^{n/2}$ grows without bound as $n$
  grows -- it is not bounded by a constant.\\
  (e) See Rosen \S 1.8 Ex. 61,62\\
  }
                         
%%%%%%%%%%%%%%  Fall 2000  Problem Set 6   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
 \problem \textbf{Asymptotic notation} \\
  You don't need to give proofs for this problem.

  \begin{problemparts}
    \problempart Find functions $f_1$, $f_2$, $g_1$, and $g_2$, such
    that
    \begin{align*}
      f_1(n) &= \Theta(f_2(n)),\\
      g_1(n) &= \Theta(g_2(n)),\\      
      \neg [f_1(g_1(n)) &= \Theta(f_2(g_2(n)))].\\
    \end{align*}

    \solution{$f_1(n) = f_2(n) = 2^n$, $g_1(n) = n$, $g_2(n) = 2n$.}
    

    \problempart Find functions $f$ and $g$ such that
    \begin{gather*}
      f(n) = O(g(n)), \text{ but } \neg [g(n) = O(f(n))];\\
      f(g(n)) = \Theta(g(f(n))).
    \end{gather*}

    \solution{$f(n) = n^2$, $g(n) = n^3$.}

      
    \problempart Find functions $f$ and $g$ such that
    \begin{alignat*}{3}
      f(n) &= O(g(n)), &\text{ but } &&\neg [g(n) &= O(f(n))];\\
      f(g(n)) &= O(g(f(n))),  &\text{ but } &&\neg [g(f(n)) &=
      O(f(g(n)))].\\
    \end{alignat*}

    \solution{$f(n) = n^2$, $g(n) = 2^n$.}
    
    
    \problempart Find functions $f$ and $g$ such that
    \begin{alignat*}{3}
      f(n) &= O(g(n)), &\text{ but } &&\neg [g(n) &= O(f(n))];\\
      g(f(n)) &= O(f(g(n))), &\text{ but } &&\neg [f(g(n)) &= O(g(f(n)))].\\
    \end{alignat*}
    
    \solution{$f(n) = 2^n$, $g(n) = 2^{2 n}$. Then $f(g(n)) = 2^{2^{2
          n}}$, while $g(f(n)) = 2^{2^{n+1}}$.}

  \end{problemparts}  
%%%%%%%%%%%%%%  Fall 2000  PS7   %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem For each of the functions below, determine
whether the function is injective, whether it is surjective, and
whether it is bijective.  No proofs are required.

\begin{problemparts}
\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ defined by
$f(x)=e^x$

\solution{ The function is injective because $e^x = e^y$ if and only
if $x = y$.  The function is not surjective, because $e^x$ never takes
on non-positive values.  The function is not bijective, because it is
not surjective.  }

\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}^+$
defined by $f(x)=e^x$.  (Here $\mathbb{R}^+$ denotes the set of
positive real numbers.)

\solution{The function is injective as before, but is now also surjective
because for every $y \in \mathbb{R}^+$, there exists an $x$ (namely $x
= \ln y$) such that $y = e^x$.  Therefore, the function is bijective.}

\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ defined
by $(x+1)/(x^2+1)$

\solution{ The function is not injective, because $f(0) = f(1) = 1$.
The function is not surjective, because the function never takes on
large positive or negative values.  The function is not bijective
because it is neither injective nor surjective.}

\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ defined
by

\begin{eqnarray*}
f(x) & = & \left\{
\begin{array}{cl}
1/x & \text{for $x \neq 0$} \\
0 & \text{for $x = 0$.}
\end{array}
\right.
\end{eqnarray*}

\solution{ The function is injective, because $f(x) = f(y)$ if and
only if $x = y$.  The function is surjective, because for all $y \in
\mathbb{R}$, there exists an $x$ (namely $x = 1 / y$ or $x = 0$) such
that $f(x) = y$.  Therefore, the function is also bijective.}

\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
% Fall 99
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset 2, #1

\problem For each of the functions below, determine whether the function
is injective, whether it is surjective, and whether it is bijective.  No
proofs are required.

\begin{problemparts}
\problempart The function $f : \reals \to \reals$ defined by
$f(x)=x^2$.

\solution{$f(r) = f(-r)$ so not injective.  $f(r) \geq 0$ so not
surjective.}

\problempart The function $f : \reals^+ \to \reals^+$
defined by $f(x)=x^2$.  (Here $\reals^+$ denotes the set of
positive real numbers.)

\solution{A bijection, because every positive real has a unique positive
square root.}

\problempart The function $f : \reals \to \reals$ defined by
$f(x)=x^3$.

\solution{$f$ is an increasing function, namely $x<y$ implies $f(x) <f(y)$
so it is an injection.  It also takes on all real values, that is, it is a
surjection too.  So it is a bijection.}

\problempart The function $f : \reals \to \reals$ defined by
$f(x)=xe^x$.

\solution{$f'(x) = e^x + x e^x = e^x(1 + x)$, so $f$ has a minimum at $x
=1$ which implies it is neither an injection nor a surjection.}

\problempart The function $f : \reals \times \reals \to \reals$ defined
by $f(x,y) = xy$.

\solution{Not an injection since $f(0,y)=f(0,z)$ for all $y,z$.  It is a
surjection, since $r = f(1, r)$ for all $r$.}

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset 2, #2

\problem Prove that there is a bijection between $\integers$ and
$\naturals$.

\solution{Let $f(0) = 0, f(1) = 2, f(2) = 4, f(3) = 6, \dots$ and
$f(-1) = 1, f(-2) = 3, f(-3) = 5, \dots$.  That is, 
\[f(k) ::= \left\{\begin{array}{ll}
             2k & \mbox{ if } k \geq 0,\\
             -2k - 1 & \mbox{ if } k < 0.
                    \end{array}
           \right.
\]
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% pset 2, #3
\problem Let $f: B \to C$ and $g: A \to B$ so $f \circ g : A
\to C$.  Given that $f \circ g$ is one-to-one, prove or give a
counterexample:

\begin{problemparts}

\problempart $g$ is an injection.

\solution{It is.
\begin{proof}
Assume for the purpose of contradiction that $g$ is not an one-to-one.
Then there exist elements $a_1, a_2 \in A$, such that $g(a_1) = g(a_2)$.
This implies that $f(g(a_1)) = f(g(a_2))$.  Therefore, $f \circ g$ is not
one-to-one, a contradiction.
\end{proof}}

\problempart $f$ is an injection.

\solution{It need not be.  For example, let $A::=\set{1,2}, C::=
B::=\set{1,2,3}, C ::= A$, and define $g(n) ::= n$, $f(1)::=1$, $f(2) = f(3)
::= 2$.}

\end{problemparts}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% pset 3, #5

\problem  \textbf{Defining Bijections}  %F97 H19-Pset7

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

\solution{
Let $\phi\colon P(\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}
}
%%%%%%%%%%%%%%%%%%%%%%%%%%%5
%END   Tina's problems


\end{problems}

\end{document}



