\magnification=\magstep1
\centerline{Mathematics 242 -- Principles of Analysis}
\centerline{Selected Solutions -- Problem Set 2}
\centerline{September 20, 2004}
\bigskip
\noindent
Section 6/8.  Let $R$ be the relation on ${\bf R}^2$, defined by
$$(a,b)R(c,d) \Leftrightarrow a + d = b + c$$
First, we show that $R$ is an equivalence relation.  First, it
is reflexive since $a + b = b + a$ implies $(a,b)R(a,b)$ for 
all $(a,b)$.  Next, it is symmetric, since if $(a,b)R(c,d)$
then $a + d = b + c$.  Hence $c + b = d + a$ so $(c,d)R(a,b)$.
Finally, it is transitive since if $(a,b)R(c,d)$ and $(c,d)R(e,f)$
then $a + d = b + c$ and $c + f = d + e$.  These equations imply
that $a + d + f = b + c + f = b + d + e$, so $a + f = b + e$, which
shows $(a,b)R(e,f)$.  The equivalence class of $(7,3)$ is the 
set of all $(x,y)$ such that $(x,y)R(3,7)$, or $x + 3 = y + 7$.
This is the line defined by the equation $y = x - 7$ in the plane.
\bigskip
\noindent
Section 7/8.  Note that the problem asks for functions $f : {\bf N} \to {\bf N}$.
This means that the domains and ranges must be subsets of the set
of natural numbers ${\bf N} = \{1,2,3,\ldots\}$. 
\item{a)}  The function $$f(n) = \cases{1 & if $n = 1$\cr
                                       n-1 & if $n \ge 2$\cr}$$
is not injective since $f(1) = f(2) = 1$.  But it is surjective, since
every natural number is in its range.
\item{b)}  An injective, but not surjective function is 
$f(n) = 2n$.  The range is the set of even natural numbers, so $f$ is 
not surjective.  But $f$ is injective since $f(n_1) = f(n_2)$
implies $2n_1 = 2n_2$, so $n_1 = n_2$.
\item{c)}  A function that is neither injective nor surjective
is 
$$f(n) = \cases{n & if $n$ is even\cr
          2n & if $n$ is odd\cr}$$
The range is the set of even natural numbers, so $f$ is not
surjective.  Moreover, $f$ is not injective, since $f(2) = f(1) = 2$.
\item{d)}  $f(n) = n$ is bijective.
\bigskip
\noindent
Section 7/10.  
\item{a)}  We want an example where $f : A \to B$ and $f^{-1}(f(C)) \ne C$
for some $C \subseteq A$.  Let $f(x) = x^2$, and let $C=\{1\}$.  We
have $f^{-1}(f(C)) = \{x : x^2 = 1\} = \{-1, 1\}$.
\item{b)}  We want an example where $f(f^{-1}(D)) \ne D$ for some subset
$D \subset B$.  Let $f(x) = x^2$ again, and take $D = \{-1\}$.
Then $f^{-1}(D) = \{x : x^2 = -1\} = \emptyset$ (as long as we take
the domain of $f$ to be the set of real numbers, or a subset of the reals).
Hence $f(f^{-1}(D)) = \emptyset \ne D$.
\item{c)} We want an example where $f(C_1 \cap C_2) \ne f(C_1) \cap f(C_2)$
for subsets $C_1, C_2 \subset A$.  Take $f(x) = x^2$ again, and 
let $C_1 = \{1\}$, $C_2 = \{-1\}$.  Then $f(C_1 \cap C_2) = \emptyset$,
but $f(C_1) = f(C_2) = \{1\}$, so $f(C_1) \cap f(C_2) = \{1\}$.  
\bigskip
\noindent
Section 7/12.  Let $f : A \to B$.
\item{a)}  We want to show that $f$ injective implies $f^{-1}(f(C))$
for all subsets $C \subset A$.  We know $C \subseteq f^{-1}(f(C))$ for
all mappings.  Hence, we must show that $f$ injective implies
$f^{-1}(f(C)) \subseteq C$.  Let $x \in f^{-1}(f(C))$.  By definition,
this means $f(x) \in f(C)$, so $f(x) = f(x')$ for some $x'\in C$.
Since $f$ is injective, this implies $x = x'$, so $x \in C$.  
We have shown $f^{-1}(f(C)) \subseteq C$.
\item{b)}  Similarly, we want to show  that $f$ surjective
implies that $f(f^{-1}(D)) = D$ for all $D\subseteq B$.
We know that $f(f^{-1}(D)) \subset D$ for all mappings $f$ and 
all $D$.  So, we need to show that $f$ surjective
implies that $D \subseteq f(f^{-1}(D))$.  So let $y \in D$.
Since $D \subset B$ and $f$ is surjective, this means
that $y = f(x)$ for some $x \in A$.  But then by definition,
this implies that $x \in f^{-1}(D)$, and $y = f(x) \in f(f^{-1}(D))$.
This shows that $D \subseteq f(f^{-1}(D))$. 
\bigskip
\noindent
Section 7/13.
We assume that $f,g$ are injective.  Let $g(f(x)) = g(f(x'))$.
Since $g$ is injective, $f(x) = f(x')$.  But then, since
$f$ is injective, $x = x'$.  This shows that the composition
$g \circ f$ is injective also.
\bigskip
\noindent
Section 7/20.
\item{a)}  If $f: A \to B$ has a left inverse function $g$ and
$f(x) = f(x')$, then $x = g(f(x)) = g(f(x')) = x'$.  This implies
that $f$ is injective.  Conversely, suppose $f$ is injective.
For each $y \in B$, $y$ is either equal to $f(x)$ for some
$x \in A$ or else $y \ne f(x)$ for all $x \in A$.  In the first
case, since $f$ is injective, there is only one such $x$,
so we can define $g(y) = x$, where $x$ is the unique
element of $A$ for which $f(x) = y$.  If $y \ne f(x)$ for 
all $x \in A$, then pick some $a \in A$ arbitrarily and
define $g(y) = a$.  Doing this we get a function $g : B \to A$,
and $g(f(x)) = x$ for all $x \in A$.  Hence $g$ is a left inverse
of $f$.
\item{b)}  If $f : A \to B$ has a right inverse function $g$,
then $f(g(y)) = y$ for all $y \in B$.  This says that every
$y \in B$ is in the range of $f$, so $f$ is surjective.
Conversely, if $f$ is surjective, then we must construct
a right inverse function $g$.  To do this, since $f$
is surjective, for every $y \in B$, there exists (at least
one) $x \in A$ such that $f(x) = y$.  For each $y$, 
pick any one such $x$ and define $g(y) = x$.  This gives
 a function $g : B \to A$ with $f(g(y)) = y$ for all $y \in B$.
Hence $g$ is a right inverse for $f$.  
\bye
