path: root/gupta/hw8.tex

\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