\documentclass[12pt]{article}
\usepackage[dvips]{graphicx}
\usepackage{enumerate}
\usepackage{ifthen}
\usepackage{amsmath}
\usepackage{amssymb}

%\pagestyle{empty}
\topmargin -1in
%\topmargin -0.25in
\oddsidemargin -0.5in
\evensidemargin -0.5in
\textheight 9.25in
\textwidth 7.25in 

\newcommand{\comp}{ \,{\scriptstyle \stackrel{\circ}{}}\, } 
\newcommand{\nullset}{\mathrm{O}\!\!\!\!\big/\,}

\begin{document}

\noindent \hfill
\fbox{\fbox{\parbox{7.2in}{{\scshape{Math 3110 \hfill Homework \#1 Answers}} }}} \hfill \\

\vspace{-0.2in}

\begin{description}
   \item[Appendix \#22] Negate the following: ``For every real number $r$, the
   square of $r$ is nonnegative.''

   {\bf Answer:} ``There exists a real number $r$ such that $r$ is negative.'' ...or less
   words and more symbols... ``$\exists$ $r \in \mathbb{R}$ s.t. $r^2<0$.''

   [Of course, our answer is a false statement since $r^2 \geq 0$ $\forall$ $r \in \mathbb{R}$.]

   \item[1.1 \#14] Let $C = \{ x \,|\, x=3r-1 \mathrm{\;for\;some\;} r\in\mathbb{Z}\}$
   and $D = \{ x \,|\, x=3s+2 \mathrm{\;for\;some\;} s\in\mathbb{Z}\}$. Show that $C=D$.

   {\bf proof:} Suppose that $x \in C$ $\Rightarrow$ $\exists$ $r \in \mathbb{Z}$ s.t.
   $x=3r-1$. But $x = 3r - 1 = 3(r-1)+2$ and $r-1 \in \mathbb{Z}$ since $r \in \mathbb{Z}$.
   Thus (setting $s=r-1$) we get that $x=3s+2$ where $s \in \mathbb{Z}$ and thus $x \in D$
   $\therefore$ $C \subseteq D$.

   Next, suppose that $x \in D$ $\Rightarrow$ $\exists$ $s \in \mathbb{Z}$ s.t.
   $x=3s+2$. But $x = 3s + 2 = 3(s+1)-1$ and $s+1 \in \mathbb{Z}$ since $s \in \mathbb{Z}$.
   Thus (setting $r=s+1$) we get that $x=3r-1$ where $r \in \mathbb{Z}$ and thus $x \in C$
   $\therefore$ $D \subseteq C$.

   Finally, since $C \subseteq D$ and $D \subseteq C$, we can conclude that $C=D$.

   \item[1.1 \#30] Show that $A \cup B = A \cup (B-A)$.

   {\bf proof:} Suppose that $x \in A \cup (B-A)$ $\Rightarrow$ $x \in A$ or $x \in B-A$
   $\Rightarrow$ $x \in A$ or ($x \in B$ and $x \not\in A$) $\Rightarrow$ $x \in A$ or 
   $x \in B$ $\Rightarrow$ $x \in A \cup B$ $\therefore$ $A \cup (B-A) \subseteq A \cup B$.

   Suppose that $x \in A \cup B$. Notice that either $x \in A$ or $x \not\in A$. 
   Consider two cases:
   \begin{itemize}
      \item $x \in A$ $\Rightarrow$ $x \in A \cup C$ where $C$ could be anything -- like, for
      example, $C = B-A$ $\therefore$ $x \in A \cup (B-A)$. 
   
      \item $x \not\in A$ $\Rightarrow$ $x \in B$ since $x \in A \cup B$ (so $x \in A$ or 
      $x \in B$) and $x \not\in A$. So we have that $x \in B$ and $x \not\in A$ $\Rightarrow$
      $x \in B-A$ and so $x \in C \cup (B-A)$ for any set $C$ -- like, for example, $C = A$.   
      $\therefore$ $x \in A \cup (B-A)$. 
   \end{itemize}
   $\therefore$ $A \cup B \subseteq A \cup (B-A)$.    

   Finally, since $A \cup B \subseteq A \cup (B-A)$ and $A \cup (B-A) \subseteq A \cup B$,
   we can conclude that $A \cup B = A \cup (B-A)$.

\item[1.2 \#4a,c,d,i] Let $f:\mathbb{Z} \rightarrow \mathbb{Z}$ (both the domain and codomain 
     of $f$ is $\mathbb{Z}$). For each map, prove or disprove: $f$ is one-to-one and prove or 
     disprove: $f$ is onto.
   \begin{description}
      \item[\#4a] $f(x) = 2x$: 

      $f$ is one-to-one -- proof: suppose that $f(x)=f(y)$ $\Rightarrow$ $2x=2y$ $\Rightarrow$
      $x=y$. Thus $f$ is injective.

      $f$ is not onto -- proof: suppose that $f(x)=1$ then $2x=1$ and thus $x=1/2$. But 
      $1/2 \not\in \mathbb{Z}$ $\therefore$ $1$ is not in the image of $f$ (so $f$ is not
      onto).

\newpage

      \item[\#4c] $f(x) = x+3$:

      $f$ is one-to-one -- proof: suppose that $f(x)=f(y)$ $\Rightarrow$ $x+3=y+3$ 
      $\Rightarrow$ $x=y$. Thus $f$ is injective.
   
      $f$ is onto -- proof: suppose that $y \in \mathbb{Z}$ then $y-3 \in \mathbb{Z}$ and
      $f(y-3) = (y-3)+3 = y$. Thus $y$ is in the image of $f$. Therefore, the image of $f$
      contains all possible integers and thus $f$ is onto.

      {\bf Alternate proof:} Let $g:\mathbb{Z} \rightarrow \mathbb{Z}$ be defined by 
      $g(x)=x-3$. Notice that $(f \comp g)(x) = f(g(x)) = f(x-3) = x$ and $(g \comp f)(x)
      =g(f(x)) = g(x+3) = x$. Therefore, $f\comp g = id_\mathbb{Z} = g \comp f$. Thus
      $f$ is invertible (with inverse $f^{-1} =g$) and so $f$ is bijective (both one-to-one
      and onto).

      \item[\#4d] $f(x)=x^3$:

      $f$ is one-to-one -- proof: suppose that $f(x)=f(y)$ $\Rightarrow$ $x^3=y^3$ 
      $\Rightarrow$ $x=y$. Thus $f$ is injective.

      $f$ is not onto -- proof: suppose that $f(x)=2$ $\Rightarrow$ $x^3=2$ $\Rightarrow$
      $x = \sqrt[3]{2} \not\in \mathbb{Z}$ $\therefore$ $2$ is not in the image of $f$.

      \item[\#4i] $\displaystyle{f(x) = \left\{ \begin{array}{ll} x & x \mathrm{\;is\;even} \\
      \frac{x-1}{2} & x \mathrm{\;is\;odd} \end{array} \right.}$:

      $f$ is not one-to-one -- proof: $f(1) = (1-1)/2 = 0 = f(0)$.

      $f$ is onto -- proof: suppose that $y \in \mathbb{Z}$. Then $2y+1 \in \mathbb{Z}$ and
      $2y+1$ is odd $\therefore$ $f(2y+1) =  ((2y+1)-1)/2 = y$. Thus every integer is 
      in the range of $f$ $\therefore$ $f$ is surjective.
   \end{description}

   \item[1.2 \#22] Let $f:A \rightarrow B$ and $A,B \not= \nullset$. Let $S_1,S_2 \subseteq A$.
   \begin{enumerate}[(a)]
      \item Show $f(S_1 \cup S_2) = f(S_1) \cup f(S_2)$.

      {\bf proof:} Let $y \in f(S_1 \cup S_2)$ $\Rightarrow$ $\exists$ $x \in S_1 \cup S_2$
      s.t. $f(x)=y$ $\Rightarrow$ $y = f(x)$ where $x \in S_1$ or $x \in S_2$. If $x \in S_1$,
      then $y = f(x) \in f(S_1)$ and if $x \in S_2$, then $y = f(x) \in f(S_2)$ $\therefore$
      $y \in f(S_1) \cup f(S_2)$ $\therefore$ $f(S_1 \cup S_2) \subseteq f(S_1) \cup f(S_2)$.

      Now suppose that $y \in f(S_1) \cup f(S_2)$ $\Rightarrow$ $y \in f(S_1)$ or 
      $y \in f(S_2)$. If $y \in f(S_1)$, then $\exists$ $x \in S_1$ s.t. $f(x)=y$ and
      if $y \in f(S_2)$, then $\exists$ $x \in S_2$ s.t. $f(x)=y$. Therefore, $\exists$
      $x \in S_1$ or $x \in S_2$ s.t. $f(x)=y$ $\therefore$ $\exists$ $x \in S_1 \cup S_2$
      s.t. $f(x)=y$. Thus $y \in f(S_1 \cup S_2)$ $\therefore$ 
      $f(S_1) \cup f(S_2) \subseteq f(S_1 \cup S_2)$.

      Finally, we conclude that $f(S_1) \cup f(S_2) = f(S_1 \cup S_2)$.

      \item Show $f(S_1 \cap S_2) \subseteq f(S_1) \cap f(S_2)$

      {\bf proof:} Let $y \in f(S_1 \cap S_2)$ $\Rightarrow$ $\exists$ $x \in S_1 \cap S_2$
      s.t. $f(x)=y$. Thus $x \in S_1$ and $x \in S_2$ and $f(x)=y$. So
      $y \in f(S_1)$ and $y \in f(S_2)$ $\therefore$ $y \in f(S_1) \cap f(S_2)$. Thus
      $f(S_1 \cap S_2) \subseteq f(S_1) \cap f(S_2)$.

      \item Give an example where $f(S_1 \cap S_2) \not= f(S_1) \cap f(S_2)$.

      Let $A = B = \{1,2 \}$ and $f:A \rightarrow B$ where $f(1)=f(2)=1$.
      In addition, let $S_1=\{1\}$ and $S_2=\{2\}$. Then,
      $f(S_1 \cap S_2) = f(\nullset) = \nullset$ but 
      $f(S_1)\cap f(S_2) = \{1\} \cap \{1\} = \{1\}$ $\therefore$ 
      $f(S_1 \cap S_2) \not= f(S_1) \cap f(S_2)$.

      {\bf Note:} Any map which is not one-to-one will furnish us with an example.
      In fact, we can prove the following statement:

\newpage

      Let $f:A\rightarrow B$ be a map. Then $f$ is injective if and only if for all 
      $S_1,S_2 \subseteq A$ we have that $f(S_1 \cap S_2) = f(S_1) \cap f(S_2)$.

      {\bf proof:} Suppose that $f$ is injective and $S_1,S_2 \subseteq A$. We already know
      from part (b) that $f(S_1 \cap S_2) \subseteq f(S_1) \cap f(S_2)$. We need to show the
      reverse inclusion. Suppose that $y \in f(S_1) \cap f(S_2)$ $\Rightarrow$ 
      $y \in f(S_1)$ and $y \in f(S_2)$ $\Rightarrow$ $\exists$ $x_1 \in S_1$ and $x_2 \in S_2$
      s.t. $y=f(x_1)=f(x_2)$. But $f$ is injective $\therefore$ $x_1=x_2$. So $x_1$ is in both
      $S_1$ and $S_2$. Thus $x_1 \in S_1 \cap S_2$ and so $y \in f(S_1 \cap S_2)$ 
      $\therefore$ $f(S_1) \cap f(S_2) \subseteq f(S_1 \cap S_2)$. So we have shown that $f$
      injective implies that $f(S_1) \cap f(S_2) = f(S_1 \cap S_2)$ ($\forall$ 
      $S_1,S_2 \subseteq A$).

      Now suppose that $f$ is not injective. We need to show that $\exists$ 
      $S_1,S_2 \subseteq A$ s.t. $f(S_1 \cap S_2) \not= f(S_1) \cap f(S_2)$. Well, $f$ is
      not injective $\therefore$ $\exists$ $x_1,x_2 \in A$, $x_1 \not= x_2$ s.t. 
      $f(x_1)=f(x_2)$ (for convenience set $y=f(x_1)=f(x_2)$). Now consider $S_1 = \{x_1\}$
      and $S_2 = \{x_2\}$. Then $f(S_1 \cap S_2) = f(\nullset) = \nullset$ and
      $f(S_1) \cap f(S_2) = \{y\} \cap \{y\} = \{y\}$. Therefore, 
      $f(S_1 \cap S_2) \not= f(S_1) \cap f(S_2)$. So we have shown that if $f$ fails to be
      injective, then $f$ will fail to preserve set intersections.

      \item Show that $f(S_1) - f(S_2) \subseteq f(S_1-S_2)$.

      {\bf proof:} Suppose that $y \in f(S_1) - f(S_2)$ $\Rightarrow$ $y \in f(S_1)$ and
      $y \not\in f(S_2)$ $\therefore$ $\exists$ $x \in S_1$ s.t. $f(x)=y$. Notice that if
      $x \in S_2$ then $y = f(x) \in f(S_2)$ $\therefore$ $x \not\in S_2$ and so 
      $x \in S_1 - S_2$ and thus $y = f(x) \in f(S_1-S_2)$ $\therefore$ 
      $f(S_1) - f(S_2) \subseteq f(S_1-S_2)$.

      \item Give an example where $f(S_1) - f(S_2) \not= f(S_1-S_2)$.

      Again consider $A = B = \{1,2\}$ and $f:A \rightarrow B$ defined by $f(1)=f(2)=1$.
      Let $S_1 = A$ and $S_2 = \{2\}$. Then $f(S_1) - f(S_2) = \{1\} - \{1\} = \nullset$
      and $f(S_1-S_2) = f(\{1,2\}-\{2\}) = f(\{1\}) = \{1\}$ $\therefore$
      $f(S_1) - f(S_2) \not= f(S_1-S_2)$.

      {\bf Note:} Again, any map which is not one-to-one will furnish us with 
      an example. In fact, we can prove the following statement:

      Let $f:A\rightarrow B$ be a map. Then $f$ is injective if and only if for all 
      $S_1,S_2 \subseteq A$ we have that $f(S_1 - S_2) = f(S_1) - f(S_2)$.

      {\bf proof:} Suppose that $f$ is injective and $S_1,S_2 \subseteq A$. We already know
      from part (d) that $f(S_1) - f(S_2) \subseteq f(S_1-S_2)$. We need to show the
      reverse inclusion. Suppose that $y \in f(S_1-S_2)$ $\Rightarrow$ 
      $\exists$ $x \in S_1-S_2$ s.t. $y=f(x)$. In particular, $x \in S_1$ and so 
      $y=f(x) \in f(S_1)$ Now suppose $y \in f(S_2)$ $\Rightarrow$
      $\exists$ $z \in S_2$ s.t. $y=f(z)$. But $f$ is injective $\therefore$ since $f(x)=f(z)$
      we have that $x=z$ and so $x \in S_2$. This is impossible since $x \in S_1-S_2$ 
      (and thus $x \not \in S_2$). Therefore, $y \not\in f(S_2)$ and thus 
      $y \in f(S_1)-f(S_2)$ $\therefore$ $f(S_1 - S_2) \subseteq f(S_1) - f(S_2)$. So we have
      shown that $f$ injective implies that $f(S_1 - S_2) = f(S_1) - f(S_2)$ ($\forall$ 
      $S_1,S_2 \subseteq A$).

      Now suppose that $f$ is not injective. We need to show that $\exists$ 
      $S_1,S_2 \subseteq A$ s.t. $f(S_1 - S_2) \not= f(S_1) - f(S_2)$. Well, $f$ is
      not injective $\therefore$ $\exists$ $x_1,x_2 \in A$, $x_1 \not= x_2$ s.t. 
      $f(x_1)=f(x_2)$ (for convenience set $y=f(x_1)=f(x_2)$). Now consider $S_1 = \{x_1,x_2\}$
      and $S_2 = \{x_2\}$. Then $f(S_1) - f(S_2) = \{y\}-\{y\} = \nullset$ and
      $f(S_1-S_2) = f(\{x_1,x_2\}-\{x_2\}) = f(\{x_1\}) = \{y\}$. Therefore, 
      $f(S_1 - S_2) \not= f(S_1) - f(S_2)$. So we have shown that if $f$ fails to be
      injective, then $f$ will fail to preserve set differences.
   \end{enumerate}
\end{description}


\end{document}
