\documentclass[12pt]{article}
\textwidth = 6.5 in
\textheight = 9 in
\oddsidemargin = 0.0 in
\evensidemargin = 0.0 in
\topmargin = 0.2 in
\headheight = 0.0 in
\headsep = 0.0 in
\parskip = 0.2in
\parindent = 0.0in

\usepackage{amsmath,amssymb,enumerate}
%\def\rmdefault{bch} % Use Charter for main text font.

% =========================================================
\begin{document}

\begin{center}
{\LARGE
\textbf{CS 173: Discrete Structures, Fall 2009}
\\
\textbf{Homework 5}
\\[1ex]}

This homework contains 5 problems worth a total of 50 regular points.
It is due on Friday, October 9 at noon.   Put your homework in
the appropriate dropbox in the Siebel basement.

\end{center}

\begin{enumerate}
%----------------------------------------------------------------------
\item 
\textbf{Functions [8 points]} 

For each of the following functions, give the following information:
what is its co-domain?  what is its image?  is the function onto?
is the function one-to-one?

\begin{enumerate}
\item $f: \mathbb{C} \rightarrow \mathbb{R}$ such that $f(x + yi) = x+y$
\item $g: \mathbb{R} \rightarrow \mathbb{R}$ such that $f(x) = x^3 + 7$
\item $h: \mathbb{Z}^2 \rightarrow \mathbb{Z}$ such that $h(x,y) = 2^x3^y$
\item $k: [0,1] \rightarrow \mathbb{R}^2$ such that 
$k(x) = x(3,4) + (1-x)(1,2)$.  (The product of a number $a$ and a 2D point
$(x,y)$ is $(ax,ay)$ i.e. multiply both coordinates by $a$.)
\end{enumerate}

If you can't immediately see the answer for (d), pick some convenient
input values and compute their output values.  Try plotting the output
values in 2D.



%----------------------------------------------------------------------
\item 
\textbf{Nested quantifiers [8 points]} 

State whether the following propositions are true or false, and briefly (but
clearly!) explain why.

\begin{enumerate}
\item $\forall x \in \mathbb{R}, \ \exists y \in \mathbb{R},
y^3 \le x$

\item $\exists x \in \mathbb{N}, \ \forall y \in \mathbb{N},
xy = x$

\item $\forall x \in \mathbb{R}, \ \exists y \in \mathbb{Q}, 
|x-y| \le 0.01$

\item $\exists y \in \mathbb{Q}, \ \forall x \in \mathbb{R}, 
|x-y| \le 0.01$


\end{enumerate}

%----------------------------------------------------------------------
\item 
\textbf{Proving a set relation [10 points]} 


\begin{enumerate}

\item Prove the following set inclusion by choosing an
element from the smaller set and showing that it's in the
larger set.   

\begin{quote}
For any sets $A$, $B$, and $C$, $(A \cup B)\cap C \subseteq A \cup (B \cap C)$.
\end{quote}

\item Show that the set inclusion doesn't hold in the other direction,
by giving specific sets $A$, $B$, and $C$ for which it fails.

\end{enumerate}

Hint: drawing yourself a Venn diagram may help you understand
what's happening.

\newpage

%----------------------------------------------------------------------
\item 
\textbf{Proofs with concrete functions [10 points]} 

Prove the following claims.   Do this directly from
the definitions of one-to-one and onto, plus high-school algebra.
{\bf Do not use calculus or theorems about increasing functions.}

\begin{enumerate}
\item Consider $g:\mathbb{R} \rightarrow \mathbb{R}$ such that
$g(x) = 2^{x + 1}$.   Show that $g$ is one-to-one.

\item Consider $f:\mathbb{Z}^2 \rightarrow \mathbb{Z}$ such that
$f(x,y) = xy + 27$.   Show that $f$ is onto.


\end{enumerate}

%----------------------------------------------------------------------
\item 
\textbf{A curious bijection [14 points]} 

Mathematicians define two sets to be the same size if you can produce
a bijection from one to the other.  You might imagine that the set of
pairs of natural numbers is larger than the natural numbers.  However, it
turns out that they are the same size.   

Let's define a function $f$ from $\mathbb{N}^2$ to $\mathbb{N}$ as follows:

$$ f(x,y) = \left\{
   \begin{array}{ll}
       x + y^2 & \text{ if } y \ge x \\
       (x +1)^2 - (y+1) & \text{ otherwise} 
   \end{array}
\right. $$


Pretty mysterious, eh?  I claim that $f$ is actually a bijection and,
thus, it has an inverse which is a function mapping $\mathbb{N}$ onto
all of $\mathbb{N}^2$.

\begin{enumerate}
\item (3 points) Draw a picture of what the function does for pairs $(x,y)$ such
that $x+y \le 4$.  That is, draw a 2D table.  At the 2D position 
corresponding to $(x,y)$, write the value of the function $f$
for input $(x,y)$.   That is, at location $(1,2)$ in your picture,
write the value $5$.

\item What is the range of possible output values for an input pair
$(x,k)$ where $x \le k$?  That is, write formulas (depending only
on $k$) for the largest and smallest output values.

\item What is the range of possible output values for an input pair
$(k,y)$ where $y < k$?

\item What is the preimage of the output value 17?

\item If the larger of the two input coordinates is $k$, how many different
input values are possible?  How does this compare to the number of
different output values?

\item (3 points) Suppose that we have pairs $(x,y)$ and $(p,q)$ such that
$\max(x,y) \not = \max(p,q)$.  
Explain why $f(x,y)$ cannot be equal to $f(p,q)$.

\end{enumerate}

This problem should give you a strong intuition for why $f$ is both
one-to-one and onto.    To firm this up into a formal proof, we'd need
to explain why $f$ is one-to-one within each of the ranges of input
values carved out in parts (b) and (c).
I won't make you do this because it's a bit messy.


\end{enumerate}

\end{document}
