\documentclass{article}
\usepackage{amsmath,amsthm,amssymb,fancyhdr,epic,eepic,multicol,graphicx}

\renewcommand{\baselinestretch}{1.1}

\theoremstyle{plain}
\newtheorem{claim}{Claim}
\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem*{answer}{Answer}
\newtheorem{definition}{Definition}

\newcommand{\bp}{\begin{problem}}
\newcommand{\ep}{\end{problem}}
\newcommand{\ba}{\begin{answer}}
\newcommand{\ea}{\end{answer}}
\newcommand{\ds}{\displaystyle}
\newcommand{\ben}{\renewcommand{\theenumi}{\alph{enumi}}\renewcommand{\labelenumi}{(\theenumi)}\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}

\fancyhead[L]{\Large \textbf{Math 157 Fall 2013}}
\fancyhead[R]{\large \textbf{Homework 6 - Selected answers}}



\begin{document}
\pagestyle{fancy}
\fancyfoot[R,L,C]{}

\bp Read Chapter 1, through section 1.8.  (pages 48-61).
\ben
\item In Section 1.5, do exercises 2,3,4,8,9,10, and 11.
\ba Exercise 2.  Let $f(x)=1+x$ and $g(x)=1-x$.  Then 
\begin{gather*}
f(2)+g(2)=3+-1=2\\
f(2)-g(2)=3--1=4\\
f(2)g(2)=(3)(-1)=-3\\
\frac{f(2)}{g(2)}=\frac{3}{-1}=-3\\
g(f(2))=g(3)=1-3=-2\\
f(g(2))=f(-1)=-1+1=0\\
f(a)+g(-a)=1+a+(1--a)=2+2a\\
f(t)g(-t)=(1+t)(1+t).
\end{gather*}
\ea
\ba Exercise 9.  Let $$f(x)=\sum_{k=0}^n c_kx^k=c_0+c_1x+c_2x^2+\cdots +c_kx^k.$$
\ben
\item If $n\geq 1$ and $f(0)=0$, the $f(x)=xg(x)$ where $g$ is a
  polynomial of degree $n-1$.  To see this, note that for any
  polynomial, $f(0)=c_0$.  So, if $f(0)=0$, then $c_0=0$.  So, 
\begin{align*}
f(x)&=
  \sum_{k=1}^n c_kx^k=c_1x+c_2x^2+\cdots +c_kx^k\\
&=x
  \left(c_1+c_2x+\cdots c_{k}x^{k-1}\right)\\
&x g(x)
\end{align*}
where $$g(x)=\left(c_1+c_2x+\cdots
  c_{k}x^{k-1}\right)=\sum_{k=0}^n c_{k+1}x^k.$$
\item For each real number $a$, the function $p$ defined by
  $p(x)=f(x+a)$ is a polynomial of degree $n$.  To see this, simply
  substitute $x+a$ for $x$ in $f(x)$, expand the expressions
  $(x+a)^k$, and collect the powers of $x$.  More explicitly, 
\begin{align*}
p(x)&=f(x+a)&\\
&=c_0+c_1(x+a)+c_2(x+a)^2+\cdots+c_n(x+a)^n\\
&=c_0+(c_1x+c_1a)+(c_2x^2+2c_2ax+c_2a^2)+(c_3x^3+3c_3ax^2+3c_3a^2x+c_3a^3)\\
&\hspace{2cm}
+\cdots+(c_nx^n+nc_nax^{n-1}+\cdots+nc_na^{n-1}x+ c_n a^n)\\
&=(c_0+c_1a+c_2a^2+c_3a^3+\cdots+c_na^n) + (c_1+2c_2a+3c_3a^2+\cdots+nc_na^{n-1})x+\\
&\hspace{2cm}+(c_2+3c_3a+\cdots )x^2+\cdots +c_nx^n
\end{align*}
which is a polynomial of degree $n$ also.
\item 
If $n\geq 1$ and $f(a)=0$, then there exists a polynomial $h$ of
  degree $n-1$ with $f(x)=(x-a)h(x)$.   To see this, let
  $p(x)=f(x+a)$.  Note that
  $f(x)=p(x-a)$.   Since $f(a)=0$, we
  have $p(0)=0$ and since $p$ is a polynomial of degree $n$, part (a)
  implies that $p$ factors as $$p(x)=xq(x)$$ for some
  polynomial $q(x)$ of degree $n-1$.  Therefore $f(x)=p(x-a)=(x-a)q(x-a)$.  Since $q(x)$ is a
  polynomial of degree $n-1$, so is $h(x):=q(x-a)$.  Thus, we have found a polynomial
  $h$ of degree $n-1$ so that  
$$f(x)=(x-a)h(x)$$
\item It follows that if $f$ is a polynomial of degree $n$, then
  $f(x)=0$ for at most $n$ distinct real numbers.  I'll walk through a
  slow argument of this fact.


If $n\geq 2$, and $f(x)=0$ for two distinct values of $x$, say $x=a$ and $x=b$,
  then there exists a polynomial $g$ of degree $n-2$ so that
  $f(x)=(x-a)(x-b)g(x)$.  To see this, use the previous part to write
  $f(x)=(x-a)h(x)$ for a polynomial $h$ of degree $n-1$.  Then, since
  $f(b)=0$, we have $(b-a)h(b)=0$.  Since $b-a\neq 0$ if $a$ and $b$
  are distinct, we must have $h(b)=0$.  Then, the previous part says
  that there exists a polynomial $g$ of degree $n-2$ so that
  $h(x)=(x-b)g(x)$.  Then, $$f(x)=(x-a)(x-b)g(x).$$  

Continuing, one
  sees that if $f(x)=0$ for $k$ distinct values of $x$, say $x=a_1,
  \ldots, a_k$, then there exists a polynomial $g$ of degree $n-k$ so that
  $$f(x)=(x-a_1)\cdots(x-a_k)g(x).$$
  Note that if the degree of $f$ is $n$, then $f(x)=0$ for at most $n$
  distinct values of $x$.  To see this, note that if $f(x)=0$ for $n>0$
  distinct values of $x$, call them $a_1, \ldots, a_n$, then
  $$f(x)=(x-a_1)(x-a_2)\cdots (x-a_n)g(x)$$ for some 
  polynomial $g$ of degree zero.  Since $g$ is a degree zero
  polynomial, $g(x)=c$ for some constant $c$ and $c\neq 0$ since
  degree of $f$ is $n>0$.  So the polynomial $f$ has the form 
  $$f(x)=c(x-a_1)(x-a_2)\cdots
  (x-a_n)$$ for some constants $a_1, \ldots, a_n$  and some nonzero
  constant $c$.
  Then, for any number $a_{n+1}$ distinct from $a_1,
  \ldots, a_n$, we have $(a_{n+1}-a_i)\neq 0$, so the righthand side
  $c(x-a_1)(x-a_2)\cdots (x-a_n)$ is not zero at $x=a_{n+1}$.  That
  is, $f(x)$ cannot be zero for any number $a_{n+1}$ distinct from
  $a_1, \ldots, a_n$.

  Another way to summarize this is to say that if $f$ is a polynomial
  of degree less than or equal to $n$ and
  $f(x)=0$ for $n+1$ distinct values of $x$, then
  $f(x)=0$ for all $x$.

\item Now suppose that $g$ is a polynomial of $m\geq n$, where
  $n$ is the degree of the polynomial $f$.  If $f(x)=g(x)$ for $m+1$
  distinct values of $x$, then $f=g$.  To see this, note that the
  function $h$ defined by $h(x)=f(x)-g(x)$ is a polynomial of degree
  $\leq m$.  If $f(x)=g(x)$ for $m+1$
  distinct values of $x$, then $h(x)=0$ for more than $m+1$ distinct
  numbers, hence $h(x)=0$.
\een
\ea
\item In Section 1.7, do exercises 1,2,3, and 6.
\een
\ep


\section*{Functions}

\begin{definition}
  We say that a set of ordered pairs $f \subseteq X\times Y$ is a
  \emph{function from $X$ to $Y$} if and only if for all $x \in X$
  there exists one and only one $y\in Y$ so that $(x,y)\in f.$ We
  usually write $f:X\rightarrow Y$ if $f \subseteq X\times Y$ is
  a function and we write $y=f(x)$ if $(x,y)\in f.$ The set $X$
  is called \emph{the domain of $f$} and the set $Y$ is called
  \emph{the codomain of $f.$}
\end{definition}

It is common to think of a function $f:X\rightarrow Y$
a ``rule'' that associates $x\in X$ to $y\in Y$ whenever
$y=f(x)$ and to refer to the set of ordered pairs $f \subseteq X\times Y$ as
the \emph{graph} of the function.  By this convention the ``rule'' is
referred to as the function $f$ 
and the set $graph(f)=\{(x,y)\in X \times Y
: f(x)=y\}$ is the \emph{graph of $f$}.


\begin{definition}
Suppose that $f:X\rightarrow Y$ is a function.  
\ben
\item For any subset $A \subseteq X$, we define the set
  $f(A)\subseteq Y$
  by $$f(A)=\{y\in Y : \exists x \in A \text{ with }f(x)=y\}.$$
\item We call $f(X)\subseteq Y$ the \emph{range of $f$.}
\item For any subset $B \subseteq Y$, we define the set
  $f^{-1}(B)\subseteq X$
  by $$f^{-1}(B)=\{x\in X : f(x)\in B\}.$$
\een
\end{definition}



\bp Suppose that $f:X\rightarrow Y$ is a function.  
\ben 
\item For any $A\subseteq X$ and $B\subseteq X$, compare $f(A\cup
  B)$ and $f(A)\cup f(B).$
\ba 
\begin{claim}For any $A,B\subseteq X$, we have $f(A\cup
  B)=f(A)\cup f(B).$
\end{claim}
\begin{proof}Let $A,B\subseteq X$.
To prove that $f(A\cup
  B)\subseteq f(A)\cup f(B)$ let $y\in f(A\cup B)$.  This means there
  exists an element $x\in A\cup B$ with $f(x)=y$.  If $x\in A$, we have
  $y=f(x)\in f(A)\Rightarrow y\in f(A)\cup f(B)$.  If $x\in B$, we
  have $y=f(x)\in f(B)\Rightarrow y\in f(A)\cup f(B)$.

To prove that $f(A)\cup f(B)\subseteq f(A\cup
  B)$, let $y\in f(A)\cup f(B)$.  If $y\in f(A)$, there exists an element
  $x\in A$ with $f(x)=y$.  Since $x\in A$, we have $x\in A\cup B$, so
  $y=f(x)\in f(A\cup B)$.  If $y\in f(B)$, there exists an element
  $x\in B$ with $f(x)=y$.  Since $x\in B$, we have $x\in A\cup B$, so
  $y=f(x)\in f(A\cup B)$.
\end{proof}
\ea
\item For  any $A\subseteq X$ and $B\subseteq X$, compare $f(A\cap B)$ and
  $f(A)\cap f(B).$
\ba
\begin{claim}
For any $A,B\subseteq X$, we have $f(A\cap B)\subseteq f(A)\cap f(B).$
\end{claim}
\begin{proof}Let $A,B\subseteq X$ and let $y\in f(A\cap B)$.  This means there exists an element $x\in A\cap
B$ with $f(x)=y$.  Since $x\in A$, $y=f(x)\in f(A)$.  Since $x\in B$,
$y=f(x)\in f(B)$.  Together, $y\in f(A)$ and $y\in f(B)$ imply $y\in
f(A)\cap f(B)$.
\end{proof}
It may be the case that
$$f(A)\cap f(B)\nsubseteq f(A\cap B).$$
Consider an example:
Let $X=\{1,2,3\}$, $Y=\{a,b,c\}$ and $f:\{1,2,3\}\to
\{a,b,c\}$ be defined by $$f(1)=a, \quad f(2)=a,\quad f(3)=b.$$
For $A=\{1\}$ and $B=\{2\}$, we have $$f(A\cap
B)=f(\emptyset)=\emptyset \text{ and }f(A)\cap f(B)=f(\{1\}\cap
f(\{2\})=\{a\}\cap \{a\}=\{a\}.$$
\begin{claim}
If $f$ is injective, then for any $A,B\subseteq X$, $f(A\cap B=f(A)\cap f(B).$
\end{claim}
\begin{proof}Let $A,B\subseteq X$.
We already know that $f(A\cap B)\subseteq f(A)\cap f(B).$  To finish,
we need to show that if $f$ is injective then
$f(A)\cap f(B)\subseteq f(A\cap B)$.

So, assume $f$ is injective and let $y\in f(A)\cap
f(B)$.  Since $y\in f(A)$ there exists an element $x\in A$ with $f(x)=y$.  Since
$y\in f(B)$ there exists an element $z\in B$ with $f(z)=y$.  Since $f$
is injective and $f(x)=f(z)$, we have $x=z$.  Therefore $x\in A$ and
$x=z\in B$, so $x\in A\cap
B$.  Therefore, $y=f(x)\in f(A\cap B)$.
\end{proof}
\ea
\item For  any $C\subseteq Y$ and $D\subseteq Y$, compare $f^{-1}(C\cup
D)$ and $f^{-1}(C)\cup f^{-1}(D).$
\item For  any $C\subseteq Y$ and $D\subseteq Y$, compare $f^{-1}(C\cap
D)$ and $f^{-1}(C)\cap f^{-1}(D).$
\ba
\begin{claim}For  any $C,D\subseteq Y$, we have 
$f^{-1}(C\cap
D)=f^{-1}(C)\cap f^{-1}(D).$
\end{claim}
\begin{proof}
Let $C,D\subseteq Y$.  
To prove that $f^{-1}(C\cap D)\subseteq f^{-1}(C)\cap f^{-1}(D)$, 
let $x\in f^{-1}(C\cap D)$.  This means $f(x)\in C\cap D$.  So
$f(x)\in C$ and $f(x)\in D$.  Since $f(x)\in C$, we have $x\in
f^{-1}(C)$.  Since $f(x)\in D$, we have $x\in f^{-1}(D)$.  Together $x\in
f^{-1}(C)$ and $x\in
f^{-1}(D)$ imply that $x\in
f^{-1}(C)\cap f^{-1}(D).$

To prove that $f^{-1}(C)\cap f^{-1}(D)\subseteq f^{-1}(C\cap D)$, let $x\in f^{-1}(C)\cap f^{-1}(D)$.  This means $x\in f^{-1}(C)$ and $x\in
f^{-1}(D)$.  Since $x\in f^{-1}(C)$, we have $f(x)\in C$.  Since $x\in
f^{-1}(D)$ we have $f(x)\in D$.  Therefore, $f(x)\in C\cap D$.
Therefore $x\in f^{-1}(C\cap D)$.
\end{proof}
\ea
\item For  any $A\subseteq X$, compare $f(X\setminus A)$ and
  $Y\setminus f(A).$
\ba
First, we give an example to show that it may be the case that
$$f(X\setminus A)\nsubseteq Y\setminus f(A) \text{ and }Y
  \setminus f(A) \nsubseteq f(X \setminus A).$$
Let $X=\{1,2,3\}$, $Y=\{a,b,c\}$ and $f:\{1,2,3\}\to
\{a,b,c\}$ be defined by $$f(1)=a, \quad f(2)=a,\quad f(3)=b.$$
Let $A=\{1\}$.  We have $$f(X\setminus A)=f(\{2,3\})=\{a,b\}\text{ and }Y\setminus
f(A)=Y\setminus \{a\}=\{b,c\}.$$
\begin{claim}
If $f:X\to Y$ is injective, then for any $A\subseteq X$ we have
  $f(X\setminus A)\subseteq  Y \setminus f(A)$.
\end{claim}
\begin{proof}
Assume $f:X\to Y$ is injective  and $A\subseteq X$. 
Let $y\in f(X\setminus A).$  This
means there exists $x\in X\setminus A$ with $f(x)=y$.  Since $f$ is
injective, $x$ is the only element of $X$ with $f(x)=y$.  Since
$x\notin A$, 
there is no element $z\in A$ with $f(z)=y$.  
Thus, $y\notin f(A)$.  This says $y\in Y\setminus
f(A),$ as needed to prove that $f(X\setminus A)\subseteq Y\setminus
f(A)$.
\end{proof}
\begin{claim}If $f:X \to Y$ is surjective then for any $A\subseteq X$ we have
  $Y\setminus f(A)\subseteq f(X \setminus A)$.
\end{claim}
\begin{proof}
Assume $f:X\to Y$ is surjective and $A\subseteq X$.
Let $y\in Y\setminus f(A).$  Because
$f$ is onto, there exists $x\in X$ with $f(x)=y$.  Note that
$x\notin A$ for otherwise $f(x)=y\in f(A)$.  Therefore $x\in
X\setminus A$.  Since $f(x)=y$, we have $y\in f(X\setminus A)$, as
needed to prove that $Y\setminus f(A)\subseteq f(X \setminus A)$.
\end{proof}
\ea
\item For  any $C\subseteq Y$, compare $f^{-1}(Y\setminus C)$ and
  $X\setminus f^{-1}(C).$
\item For  any $A\subseteq X$, compare $f^{-1}(f(A))$ and $A$.
\ba 
\begin{claim}For any $A\subseteq X$, we have $A\subseteq
  f^{-1}(f(A)).$\end{claim}
\begin{proof}
Let $x\in A$.  Then $f(x)\in f(A)$.  Since $f(x)\in f(A)$, the element
$x\in f^{-1}(f(A))$.
\end{proof}
Note that $f^{-1}(f(A))$ and $A$ need not be equal.  For example, 
let $X=\{1,2,3,4\}$ and $Y=\{a,b,c,d\}$ and define 
\begin{align*}
f:X&\to Y\\
1&\mapsto a\\
2&\mapsto b\\
3&\mapsto b\\
4&\mapsto c
\end{align*}
Let $A=\{1,2\}$.  Then $$f^{-1}(f(A))=f^{-1}(\{a,b\})=\{1,2,3\}\neq
A.$$
\begin{claim}If $f$ is injective, then for any $A\subseteq X$, we have $A=
  f^{-1}(f(A)).$\end{claim}
\begin{proof}We only need to show that if $f$ is injective, then
  $f^{-1}(f(A))\subseteq A$.  So assume $f$ is injective and let $x\in
  f^{-1}(f(A))$.  This means that $f(x)\in f(A)$.  Therefore, there
  exists an element $z\in A$ with $f(z)=f(x)$.  Since $f$ is
  injective, $z=x$ and we see that $x\in A$.
\end{proof}
\ea
\item For  any $C\subseteq Y$, compare $f(f^{-1}(C))$ and $C$.
\een

Here ``compare'' means decide whether $\subseteq$, $\supseteq$, $=$,
or none apply.
\ep


\begin{definition}
Suppose that $f:X\rightarrow Y$ is a function.  
\ben
\item We say that $f$ is \emph{injective} or \emph{one to one} if and
  only if
$$\forall x\in X \forall z\in X \, (f(x)=f(z)\Rightarrow x=z).$$
\item We say that $f$ is \emph{surjective} or \emph{onto} if and
  only if
$$\forall y\in Y \exists x\in X \, (f(x)=y).$$
\item We say that $f$ is \emph{bijective} 
if $f$ is both injective and surjective.
\een
We may call an injective function an \emph{injection}, a surjective function
a \emph{surjection}, and a bijective function a \emph{bijection}.
\end{definition}


\bp Which apply: injective, surjective, or bijective?
\ben
\item Define $f:\N\rightarrow \N$ by $f(n)=2n$ for every $n\in \N.$
\ba The function $f$ is injective but not surjective.  To see that $f$
is injective, suppose $f(n)=f(k)$.  This means $2n=2k$, which implies
$n=k$.  To see that $f$ is not surjective, note that $1\notin f(\N)$
since $1\neq 2n$ for any $n\in \N$.
\ea
\item Define $g:\N\setminus \{0,1\} \rightarrow \N$ by $g(n)=n-1$ for
  every $n\in \N.$
\ba Here, $g$ is bijective.  To see that $g$ is injective, assume
$g(n)=g(k)$.  This means $n-1=k-1$ which implies $n=k$.  To see that
$g$ is surjective, let $y\in \N$, then $n=y+1\in \N\setminus \{0,1\}$
and $g(n)=g(y+1)=y+1-1=y$.
\ea
\item Let $X=\{\text{functions }\phi:\N\rightarrow \N\}$.  Define a
  function $G:X\rightarrow \N$ by $G(\phi)=\phi(3)$ for all $\phi\in
  X.$
\ba This function $G$ is surjective but not injective.  To see that it
is surjective, let $y\in \N$.  Then for the constant function $\phi:\N
\to \N$ defined by $\phi(n)=y$, we have $G(\phi)=\phi(3)=y$.

To see that $G$ is not surjective consider 
the constant function the constant function $\phi:\N
\to \N$ defined by $\phi(n)=6$ and the function $f:\N \to \N$ defined
by $f(n)=2n$.  Here, $$\phi\neq f \text{ and }G(\phi)=\phi(3)=6\text{
  and }G(f)=f(3)=6.$$
\ea
\item Let $X=\{\text{functions }\phi:\N\rightarrow \{0,1\}\}$ and let
  $Y=\{\text{subsets of }\N\}.$  Define a
  function $H:X\rightarrow Y$ by $H(f)=f^{-1}(\{1\}).$
\ba The function $H$ is bijective.  To see that $H$ is injective,
assume that $H(f)=H(g)$ for functions $f,g:\N\to \{0,1\}$.   The
assumption that $H(f)=H(g)$ means that $f^{-1}(\{1\})=g^{-1}(\{1\})$.
So, for all $n\in f^{-1}(\{1\})$, we have $f(n)=1=g(n)$.  If $n\notin
f^{-1}(\{1\})$, we must have $f(n)=0$ and $g(n)=0$.  Therefore, for
all $n\in \N$, $f(n)=g(n)$.  That is, $f=g$.

To see that $H$ is surjective, let $Y\subset \N$.  Define a function
$f:\N \to \N$ by $f(n)=1$ if $n\in Y$ and $f(n)=0$ if $n\notin Y$.
Then $H(f)=f^{-1}(\{1\})=Y$.
\ea

\een
\ep


\end{document}