From 18a1af1b1fbc5ae3572e011b267caa7bef293f62 Mon Sep 17 00:00:00 2001 From: Holden Rohrer Date: Fri, 29 Apr 2022 18:54:17 -0400 Subject: added all new homework for Neha's class --- gupta/hw8.tex | 312 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 312 insertions(+) create mode 100644 gupta/hw8.tex (limited to 'gupta/hw8.tex') 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 -- cgit