1 files changed, 312 insertions, 0 deletions
diff --git a/gupta/hw8.tex b/gupta/hw8.tex
new file mode 100644
index 0000000..400ab7b
--- /dev/null
+++ b/gupta/hw8.tex
@@ -0,0 +1,312 @@
+\newfam\bbold
+\def\bb#1{{\fam\bbold #1}}
+\font\bbten=msbm10
+\font\bbsev=msbm7
+\font\bbfiv=msbm5
+\textfont\bbold=\bbten
+\scriptfont\bbold=\bbsev
+\scriptscriptfont\bbold=\bbfiv
+\font\bigbf=cmbx12 at 24pt
+
+\def\answer{\smallskip{\bf Answer.}\par}
+\def\endproof{\leavevmode\hskip\parfillskip\vrule height 6pt width 6pt
+depth 0pt{\parfillskip0pt\medskip}}
+\let\endanswer\endproof
+\def\section#1{\vskip18pt plus 6pt minus 6pt\vskip0pt plus 1in\goodbreak\vskip 0pt plus -1in%
+\noindent{\bf #1}}
+\let\impl\to
+\def\nmid{\hskip-3pt\not\hskip2.5pt\mid}
+\def\problem#1{\bigskip\par\penalty-100\item{#1}}
+
+\headline{\vtop{\hbox to \hsize{\strut Math 2106 - Dr. Gupta\hfil Due Thursday
+2022-03-17 at 11:59 pm}\hrule height .5pt}}
+
+\centerline{\bigbf Homework 8 - Holden Rohrer}
+\bigskip
+
+\noindent{\bf Collaborators:} None
+
+\section{Hammack 12.4: 2, 4, 6, 8}
+
+\problem{2.} Suppose $A = \{1,2,3,4\},$ $B = \{0,1,2\},$ $C=\{1,2,3\}.$
+Let $f: A\to B$ be
+$$f = \left\{(1,0), (2,1), (3,2), (4,0) \right\},$$
+and $g: B\to C$ be $g = \left\{(0,1),(1,1),(2,3)\right\}.$ Find
+$g\circ f.$
+
+\answer
+
+$g\circ f = \left\{(0,0), (1,0), (2,2)\right\}.$
+
+\endanswer
+
+\problem{4.} Suppose $A = \{a,b,c\}.$ Let $f: A\to A$ be the function $f
+= \left\{(a,c), (b,c), (c,c)\right\},$ and let $g: A\to A$ be the
+function $g = \left\{(a,a), (b,b), (c,a)\right\}.$ Find $g\circ f$ and
+$f\circ g.$
+
+\answer
+
+$g\circ f = \left\{(a,a), (b,a), (c,a)\right\},$ and $f\circ g =
+\left\{(a,c), (b,c), (c,c)\right\}.$
+
+\endanswer
+
+\problem{6.} Consider the functions $f,g: \bb R\to \bb R$ defined as
+$f(x) = {1\over x^2+1}$ and $g(x) = 3x+2.$ Find the formulas for $g\circ
+f$ and $f\circ g.$
+
+\answer
+
+$f\circ g = {1\over (3x+2)^2+1}$ and $g\circ f = {3\over x^2+1}+2.$
+
+\endanswer
+
+\problem{8.} Consider the functions $f,g: \bb Z\times \bb Z \to \bb
+Z\times \bb Z$ defined as $f(m,n) = (3m-4n, 2m+n)$ and $g(m,n) = (5m+n,
+m).$ Find the formulas for $g\circ f$ and $f\circ g.$
+
+\answer
+
+$g\circ f = (3m-4(5m+n), 2m+n)$ and $f\circ g = (5(2m+n)+(3m-4n), 2m+n).$
+
+\section{Hammack 12.5: 6, 8}
+
+\problem{6.}
+The function $f: \bb Z\times\bb Z \to \bb Z\times\bb Z$ defined by the
+formula $f(m,n) = (5m+4n,4m+3n)$ is bijective. Find its inverse.
+
+\answer
+$f(m,n) = (r,s) = (5m+4n,4m+3n).$ Thus, $4r-5s = n$ and $4s-3r = m,$
+so the inverse is $g(r,s) = (4r-5s, 4s-3r).$
+\endanswer
+
+\problem{8.} Is the function $\theta: {\cal P}(\bb Z)\to {\cal P}(\bb
+Z)$ defined as $\theta(X) = \overline X$ bijective? If so, what is its
+inverse?
+
+\answer
+Yes, $\theta$ is bijective. This was proven in the last homework.
+
+The inverse $\theta^{-1}$ is $\theta$ since $\theta(\theta(X)) = X.$
+\endanswer
+
+\section{Hammack 12.6: 6, 7, 8, 12, 14}
+
+\problem{6.} Given a function $f: A\to B$ and a subset $Y\subseteq B,$
+is $f(f^{-1}(Y)) = Y$ always true? Prove or give a counterexample.
+
+\answer
+Let $f: \bb R\to\bb R$ be $f(x) = 1.$ $f(f^{-1}(\{2\})) = f(\emptyset) =
+\emptyset \neq \{2\}.$
+\endanswer
+
+\problem{7.} Given a function $f: A\to B$ and subsets $W,X\subseteq A,$
+prove $f(W\cap X)\subseteq f(W)\cap f(X).$
+
+\answer
+Let there be a function $f: A\to B$ and subsets $W, X\subseteq A.$
+Let $b\in f(W\cap X).$ We will show that $b\in f(W)\cap f(X)$ to show
+that $f(W\cap X)\subseteq f(W)\cap f(X).$
+From the definition of image, there is $a\in W\cap X$ s.t. $b = f(a).$
+Since $a\in W,$ $b \in f(W),$ and from $a\in X,$ $b\in f(X).$
+Therefore, $b\in f(W)\cap f(X).$
+\endanswer
+
+\problem{8.} Given a function $f: A\to B$ and subsets $W,X\subseteq A,$
+then $f(W\cap X) = f(W)\cap f(X)$ is false in general. Produce a
+counterexample.
+
+\answer
+Let $W = \{1\}$ and $X = \{2\},$ and $f(x) = 0.$
+We have $W\cap X = \emptyset,$ so $f(W\cap X) = \emptyset.$
+However, $f(W) = f(W) = \{0\} = f(W)\cap f(X).$
+This disproves $f(W\cap X) = f(W)\cap f(X)$ in general.
+\endanswer
+
+\problem{12.} Consider $f: A\to B.$ Prove that $f$ is injective if and
+only if $X = f^{-1}(f(X))$ for all $X\subseteq A.$ Prove that $f$ is
+surjective if and only if $f(f^{-1}(Y)) = Y$ for all $Y\subseteq B.$
+
+\answer
+
+Let $f: A\to B.$ We will show that $f$ is injective if and only if $X =
+f^{-1}(f(X))$ for all $X\subseteq A.$
+
+
+\smallskip
+$(\Rightarrow)$
+
+We will show this by contraposition.
+Let there be $X\in A$ such that $f^{-1}(f(X)) \neq X.$
+We will show that $f$ is not injective by showing that for some $x, y\in
+A,$ where $x\neq y,$ $f(x) = f(y).$
+
+For all $x\in X,$ we have $y = f(x) \in f(X)$ and $f(x) = y,$ so $x\in
+f^{-1}(f(X)),$
+Therefore, we know there is $z\not\in X$ such that $z\in f^{-1}(f(X)).$
+Therefore, $f(z) \in f(X),$ and for some $w\in X,$ $f(z) = f(w),$ and
+$w\neq z,$ so $f$ is not injective.
+
+\smallskip
+$(\Leftarrow)$
+
+Assume that for all $X\subseteq A,$ $f^{-1}(f(X)) = X.$
+We will show that $f$ is injective.
+Let $x,y\in A$ such that $f(x) = f(y).$
+We will show that $x = y.$
+
+From $f(x) = f(y),$ we know $f(\{x\}) = f(\{y\}),$ so $f^{-1}(f(\{x\}))
+= \{x\} = \{y\} = f^{-1}(f(\{y\})),$
+so $x = y.$
+
+
+\medskip
+We will now show that $f$ is surjective if and only if $f(f^{-1}(Y)) =
+Y$ for all $Y\subseteq B.$
+
+\smallskip
+$(\Rightarrow)$
+
+Let $f$ be surjective.
+Let $Y\subseteq B.$
+We will show that $f(f^{-1}(Y)) = Y.$
+
+Since $f$ is surjective, for all $y\in Y,$ there is $x\in A$ such that
+$f(x) = y,$ so $f(f^{-1}(Y)) \supseteq Y.$
+Also, for all $z\in f(f^{-1}(Y)),$ we know $z = f(x)$ where $f(x) = y$
+for some $y\in Y.$
+From these, $z = y \in Y,$ so $f(f^{-1}(Y)) \subseteq Y$ and therefore
+$f(f^{-1}(Y)) = Y.$
+
+\smallskip
+$(\Leftarrow)$
+
+Assume that for all $Y\subseteq B,$ $f(f^{-1}(Y)) = Y.$
+We will show that $f$ is surjective.
+To show that $f$ is surjective, we take $b\in B$ and show that we have
+$a\in A$ such that $f(a) = b.$
+
+$f(f^{-1}(\{b\})) = \{b\},$ and $f^{-1}(\{b\})$ is not empty because if
+it were, $f(f^{-1}(\{b\})) = f(\emptyset) = \emptyset \neq \{b\}.$
+Therefore, we pick $a\in f^{-1}(\{b\})$ and note that $f(a) = b,$ so $f$
+is surjective.
+
+\endanswer
+
+\problem{14.} Let $f: A\to B$ be a function, and $Y\subseteq B.$ Prove
+or disprove: $f^{-1}(f(f^{-1}(Y))) = f^{-1}(Y).$
+
+\answer
+Let $f: A\to B$ be a function, and $Y\subseteq B.$
+We will show that $f^{-1}(f(f^{-1}(Y))) = f^{-1}(Y).$
+
+$(\subseteq)$
+
+Let $x\in f^{-1}(f(f^{-1}(Y))).$
+We will show that $x\in f^{-1}(Y).$
+
+From definition of preimage, $f(x) \in f(f^{-1}(Y)),$ and from
+definition of image, $x\in f^{-1}(Y).$
+
+$(\supseteq)$
+
+Let $x\in f^{-1}(Y).$
+We will show that $x\in f^{-1}(f(f^{-1}(Y))).$
+
+From definition of preimage, for some $y\in Y,$ $f(x) = y,$ and
+$y\in f(f^{-1}(Y)).$
+And thus we have $x\in f^{-1}(f(f^{-1}(Y))).$
+We have shown that $f^{-1}(f(f^{-1}(Y))) = f^{-1}(Y).$
+
+\endanswer
+
+\section{Hammack 13.1: 2, 6, 14}
+
+\problem{2.} Show that sets $\bb R$ and $(\sqrt 2,\infty)$ have equal
+cardinality by describing a bijection from one to the other.
+
+\answer
+Let $f: \bb R \to (\sqrt 2,\infty)$ be $f(x) = e^x+\sqrt 2.$ We will
+show that $f$ is surjective, injective, and therefore bijective.
+
+\smallskip
+(Injective)
+
+Let $x,y\in\bb R$ such that $f(x) = f(y).$ We will show that $x = y.$
+$e^x+\sqrt 2 = e^y+\sqrt 2,$ so $e^x = e^y,$ and $x = y.$
+We have shown that $f$ is injective.
+
+\smallskip
+(Surjective)
+
+Let $y\in (\sqrt 2,\infty).$
+We will show there exists $x\in\bb R$ such that $f(x) = y.$
+We set $x$ to $\ln(y-\sqrt2),$ and obtain $f(x) =
+e^{\ln(y-\sqrt2)}+\sqrt2 = y-\sqrt2+\sqrt2 = y.$
+We have shown that $f$ is surjective.
+
+We now know that $f$ is bijective.
+\endanswer
+
+\problem{6.} Show that sets $\bb N$ and $S = \{{\sqrt 2\over n}: n\in\bb
+N\}$ have equal cardinality by describing a bijection from one to the
+other.
+
+\answer
+Let $f: \bb N \to S$ be defined $f(n) = {\sqrt 2\over n}.$
+
+\smallskip
+(Injective)
+
+Let $m,n\in\bb N$ such that $f(m) = f(n).$
+We will show that $m = n.$
+We obtain ${\sqrt2\over m} = {\sqrt 2\over n},$ and thus $m = n.$
+We have shown that $f$ is injective.
+
+\smallskip
+(Surjective)
+
+Let $s\in S.$
+We will show that there exists $n\in\bb N$ so that $f(n) = s.$
+By definition of $S,$ we know that there is $m\in\bb N$ such that $s =
+{\sqrt 2\over m}.$
+Letting $n = m,$ we have $f(n) = {\sqrt 2\over n} = s.$
+We have shown that $f$ is surjective.
+
+We now know that $f$ is bijective.
+\endanswer
+
+\problem{14.} Show that sets $\bb N\times\bb N$ and $S=\{(n,m)\in\bb
+N\times\bb N : n\leq m\}$ have equal cardinality by describing a
+bijection from one to the other.
+
+\answer
+Let us have $f:\bb N\times\bb N\to S$ defined as $f(n,m) = (n, n+m-1).$
+We will show that $f$ is bijective by showing that $f$ is injective and
+surjective.
+This will show that $|\bb N\times\bb N| = |S|.$
+
+\smallskip
+(Injective)
+
+Let $(n,m), (k,l)\in\bb N\times\bb N$ such that $f(n,m) = f(k,l).$
+$(n, n+m-1) = (k, k+l-1) \to n = k, n+m-1 = k+l-1.$
+Substituting $n = k$ into the latter constraint, $m = l.$
+Thus, $(n,m) = (k,l),$ and $f$ is injective.
+
+\smallskip
+(Surjective)
+
+Let $(n,m)\in S.$
+$(n, m-n+1)\in \bb N\times \bb N$ because $n\in\bb N$ from definition of
+$S$ and $n\leq m\to 1\leq m-n+1$ (and integer closure).
+
+$$f(n, m-n+1) = (n, n+(m-n+1)-1) = (n,m),$$
+so $f$ is surjective.
+
+We now know that $f$ is bijective.
+
+\endanswer
+
+\bye