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

\renewcommand{\baselinestretch}{1.1}

\theoremstyle{plain}
\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}}

\newcommand{\id}{\operatorname{id}}


\fancyhead[L]{\Large \textbf{Math 157 Fall 2013}}
\fancyhead[R]{\large \textbf{Homework 7}}



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

\section*{Step functions}

\bp Read sections 1.8-1.14 (pages 60-70) in Apostol and do the following exercises:
\ben
\item Exercises 1, 3 in 1.11 on page 63.
\item Exercises 1, 2, 5, 11, 13-17 in section 1.15 on pages 70-72.
\een
\ep


\section*{More on abstract functions}

\begin{definition}Suppose that $f:X\to Y$ and $g:Y\to Z$ are
  functions.  We define the composition $g\circ f$ to be the
  function $$g\circ f:X \to Z$$ given by $(g\circ f)(x)=g(f(x))$.
\end{definition}

\begin{definition}For any set $X$, define the function $\id_X:X\to X$
  by $\id_X(x)=x$ for all $x\in X$.  
\end{definition}

\bp Prove that $\circ$ is associative.  That is, if $f:X\to Y$,
$g:Y\to Z$, and $h:Z\to W$ are functions, then $$(h\circ g)\circ
f=h\circ (g\circ f).$$
\ba We check:  for $x\in X$, we have 
$$(h\circ g)\circ f (x) = (h\circ g) (f(x))=h(g(f(x)))
\text{ and }h\circ (g\circ f) (x) = h ( g\circ f )(x) = h( g(f(x))).$$
\ea
\ep

\bp Prove that for any function $f:X\to Y$, we have $$f\circ \id_X=f
\text{ and }\id_Y\circ f =f.$$
\ba To see that $f$ and $f\circ \id_X$ are the same functions, we
check that they assign the same values to every element in the
domain.  For any $x\in X$, we have, $$f\circ \id_X (x) = f(\id_X(x))=f(x).$$
Similarly, we check that $f$ and $\id_Y \circ f$ assign the same values to every element in the
domain.  For any $x\in X$, we have 
$$\id_Y\circ f (x) = \id_Y (f(x))=f(x).$$
\ea
\ep

\begin{definition}Let $f:X\to Y$ be a function.  We say that a
  function $g:Y\to
  X$ is a \emph{left inverse} of $f$ if $g\circ f=\id_X$. We say that a
  function $g:Y\to
  X$ is a \emph{right inverse} of $f$ if $f\circ g=\id_Y$.  We say
  that a function $g:Y\to
  X$ is \emph{an inverse} of $f$ if $g$ is both a left and a right
  inverse of $f$.
\end{definition}

\bp Prove that $f:X\to Y$ has a left inverse if and only if $f$ is injective. 
\ba 
To prove that if $f:X\to Y$ has a left inverse, it must be injective 
suppose that $g:Y\to X$ satisfies $gf=\id:X\to X$ and let $x,x'\in X$
satisfy $f(x)=f(x')$.  Apply $g$ to get $g(f(x))=g(f(x'))$.  Since
$gf=\id:X\to X$, we have $x=x'$ as needed.

Conversely, if $f$ is injective, choose a fixed element $x_0\in X$ and
define a $g:Y\to X$ by
$$g(y)=\begin{cases} x & \text{ if }g(x)=y\\
  x_0 & \text{ if $y$ is not in $f(X)$}
\end{cases}
$$
The function $g$ is well defined because $f$ is injective.  By
construction, we have $gf=\id_A$.
\ea
\ep

\bp Prove that $f:X\to Y$ has a right inverse if and only if $f$ is surjective.
\ba
To see that if $f$ has a right inverse, then it must be surjective,
suppose that $g:Y\to X$ and $fg=\id_Y$.  For every $y\in Y$,
$y=fg(y)=f(g(y)).$  Therefore, for every $y\in Y$, there exists an
$x\in X$ (namely, $x=g(y)$) with $f(x)=y$.  This says $f$ is surjective.

Conversely, if $f$ is surjective, define $g:Y\to X$ as follows:  for
every $y\in Y$, choose an element $x\in X$ with $f(x)=y$.  This is
possible since $f$ is surjective.  Define $g(y)=x$.  Then,
$fg(y)=f(x)=y$, so $g$ is a right inverse for $f$.
\ea
\ep

\bp Prove that if $f:X\to Y$ has a left inverse $g:Y\to X$ and a right
inverse $h:Y\to X$, then $g=h$.
\ba
To see that if $f$ has both a left and a right inverse, then they are
the same, suppose that $g,h:Y\to X$ and $fg=\id_Y$ and $hf=\id_X$.  We
have $hf=\id_X\Rightarrow (hf)g=g \Rightarrow h(fg)=g \Rightarrow
h(\id_Y)=g \Rightarrow h=g.$
\ea
\ep




\end{document}