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/hw7.tex | 294 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 294 insertions(+) create mode 100644 gupta/hw7.tex (limited to 'gupta/hw7.tex') diff --git a/gupta/hw7.tex b/gupta/hw7.tex new file mode 100644 index 0000000..231e3fd --- /dev/null +++ b/gupta/hw7.tex @@ -0,0 +1,294 @@ +\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{\medskip\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{\par\penalty-100\item{#1}} + +\headline{\vtop{\hbox to \hsize{\strut Math 2106 - Dr. Gupta\hfil Due Thursday +2022-03-03 at 11:59 pm}\hrule height .5pt}} + +\centerline{\bigbf Homework 7 - Holden Rohrer} +\bigskip + +\noindent{\bf Collaborators:} None + +\section{Hammack 11.3: 2, 4} + +\problem{2.} +List all the partitions of the set $A = \{a,b,c\}.$ Compare your answer +to the answer to Exercise 6 of Section 11.2 +\answer +All partitions are $\{\{\{a,b,c\}\}, \{\{a,b\},\{c\}\}, +\{\{a\},\{b,c\}\}, \{\{b\}, \{a,c\}\}, \{\{a\},\{b\},\{c\}\}\}.$ +There is exactly one of these for each of the equivalence relations on +exercise 6. +\endanswer + +\problem{4.} +Suppose $P$ is a partition of set $A.$ Define a relation $R$ on $A$ by +declaring $xRy$ if and only if $x, y \in X$ for some $X\in P.$ Prove $R$ +is an equivalence relation on $A.$ +Then prove that $P$ is the set of equivalence classes of $R.$ +\answer +We want to show that $R$ is an equivalence relation. We will show that +it is reflexive, symmetric, and transitive. + +\smallskip +(Reflexive) + +Let $a\in A.$ We will show that $aRa.$ +$P$ is a partition of $A,$ so $\bigcup_{p\in P} p = A,$ and so there +must be $X\in A$ s.t. $a,a\in X.$ +We thus obtain $aRa.$ + +\smallskip +(Symmetric) + +Let $a,b\in A$ such that $aRb.$ We will show that $bRa.$ +From the definition of $R,$ there is $X\in P$ s.t. $a\in X$ and $b\in +X.$ +Since $b,a\in X,$ $bRa.$ + +\smallskip +(Transitive) +Let $a,b,c\in A$ such that $aRb$ and $bRc.$ We will show tht $aRc.$ +From the definition of $R,$ there are $X,Y\in P$ s.t. $a,b\in X$ and +$b,c\in Y,$ but if we assume $X\neq Y,$ since $P$ is a partition, $X\cap +Y = \emptyset,$ so either $b\not\in X$ or $b\not\in Y,$ so we must know +that $X = Y.$ +Therefore, $c\in X,$ ($a,c\in X$) and $aRc.$ + +\medskip +We also want to show that the equivalence classes of $R$ is $P.$ +Let $Q$ be the equivalence classes of $R,$ defined as +$\{\{x\in A: xRa\} : a\in A\}.$ +We will show that $P = Q.$ + +\smallskip +$(Q\subseteq P)$ + +Let $a\in A.$ +By definition of $Q,$ $X = \{x\in A: xRa\} \in Q.$ +$xRa$ iff $x,a\in Y$ for some $Y\in P.$ + +We will show that $X\subseteq Y$ and $Y\subseteq X$ to show that $X = +Y$ and thus $X\in P.$ + +$x\in X$ gives $xRa,$ so $x\in Y,$ so $X\subseteq Y.$ +$x\in Y$ gives $xRa,$ so $x\in X,$ and $Y\subseteq X.$ +Therefore, $X = Y,$ and we have shown $Q\subseteq P.$ + +\smallskip +$(Q\supseteq P)$ + +Let $a\in A.$ +As established earlier, for some $X\in P,$ the element $a\in X,$ and +$xRa$ iff $x\in X,$ so $X = \{x\in A: xRa\} \in Q,$ proving $P\subseteq +Q.$ + +We have now shown that $R$ is an equivalence relation and the +equivalence classes of $R$ is $P.$ + +\endanswer + +\section{Hammack 11.4: 4, 6} + +\problem{4.} +Write the addition and multiplication tables for $\bb Z_6.$ +\answer + +{\tabskip5pt +\line{\hfil +\vbox{\halign{&\strut $#$\cr + \times &[0]&[1]&[2]&[3]&[4]&[5]\cr + [0] &[0]&[0]&[0]&[0]&[0]&[0]\cr + [1] &[0]&[1]&[2]&[3]&[4]&[5]\cr + [2] &[0]&[2]&[4]&[0]&[2]&[4]\cr + [3] &[0]&[3]&[0]&[3]&[0]&[3]\cr + [4] &[0]&[4]&[2]&[0]&[4]&[2]\cr + [5] &[0]&[5]&[4]&[3]&[2]&[1]\cr +}} +\hfil +\vbox{\halign{&\strut $#$\cr + + &[0]&[1]&[2]&[3]&[4]&[5]\cr + [0]&[0]&[1]&[2]&[3]&[4]&[5]\cr + [1]&[1]&[2]&[3]&[4]&[5]&[0]\cr + [2]&[2]&[3]&[4]&[5]&[0]&[1]\cr + [3]&[3]&[4]&[5]&[0]&[1]&[2]\cr + [4]&[4]&[5]&[0]&[1]&[2]&[3]\cr + [5]&[5]&[0]&[1]&[2]&[3]&[4]\cr +}}\hfil +}} +\endanswer + +\problem{6.} +Suppose $[a],[b]\in\bb Z_6,$ and $[a]\cdot[b]=[0].$ Is it necessarily +true that either $[a] = [0]$ or $[b]=[0]?$ + +\answer +No, it isn't. $[4],[3]\in\bb Z_6,$ and $[4]\neq [0]$ and $[3]\neq [0],$ +but $[4]\cdot[3]=[12]=[0].$ +\endanswer + +\section{Hammack 12.1: 4, 6, 9, 12} + +\problem{4.} +There are eight different functions $f: \{a,b,c\}\to\{0,1\}.$ List them +all. Diagrams will suffice. +\answer +$\{(a,0), (b,0), (c,0)\}$ + +$\{(a,0), (b,0), (c,1)\}$ + +$\{(a,0), (b,1), (c,0)\}$ + +$\{(a,0), (b,1), (c,1)\}$ + +$\{(a,1), (b,0), (c,0)\}$ + +$\{(a,1), (b,0), (c,1)\}$ + +$\{(a,1), (b,1), (c,0)\}$ + +$\{(a,1), (b,1), (c,1)\}$ + +\endanswer + +\problem{6.} +Suppose $f: \bb Z \to \bb Z$ is defined as $f = \{(x,4x+5) : x\in\bb +Z\}.$ State the domain, codomain and range of $f.$ Find $f(10).$ +\answer +The domain and codomain are $\bb Z,$ and the range is $\{4x+5 : x\in\bb +Z\}.$ +$f(10) = 45.$ +\endanswer + +\problem{9.} +Consider the set $f=\{(x^2,x), x\in\bb R\}.$ Is this a function from +$\bb R$ to $\bb R?$ Explain. +\answer +$(1,-1)\in f,$ and $(1,1)\in f,$ so this is not a function because it +has multiple outputs for one input. +\endanswer + +\problem{12.} +Is the set $\theta = \{\left((x,y),(3y,2x,x+y)\right) : x,y\in\bb R\}$ a +function? If so, what is its domain, codomain, and range? +\answer +The domain is $\bb R^2,$ the codomain is $\bb R^3,$ and the range is +$\{(3y,2x,x+y) : x,y\in\bb R\} = \{(x,y,z)\in\bb R^3 : 6z-3y-2x = 0\}.$ +\endanswer + +\section{Hammack 12.2: 4, 12, 14} + +\problem{4.} +A function $f: \bb Z \to \bb Z \times \bb Z$ is defined as $f(n) = (2n, +n+3).$ Verify whether this function is injective and whether it is +surjective. +\answer +This function is injective but not surjective. + +\smallskip +(Injective) + +Let $m,n\in\bb Z$ such that $f(n)=f(m)$ or $(2n,n+3)=(2m,m+3).$ +Therefore, $2n=2m \to n = m.$ + +\smallskip +(Surjective) + +$(0, 4) \not\in f(\bb Z),$ so this function is not surjective. + +\endanswer + +\problem{12.} +Consider the function $\theta:\{0,1\}\times\bb N \to \bb Z$ defined as +$\theta(a,b) = a-2ab+b.$ Is $\theta$ injective? Is it surjective? +Bijective? Explain. +\answer + +\smallskip +(Injective) + +Let $a,c\in\{0,1\}$ and $b,d\in\bb N$ such that $\theta(a,b) = +\theta(c,d).$ We will show that $a=c$ and $b=d.$ +We will deal with three cases: + +($a=1$ and $c=1$) + +$\theta(1,b) = 1-2b+b = 1-2d+d = \theta(1,d).$ +The equality $1-2b+b = 1-2d+d$ becomes $b = d,$ showing that the +function is injective. + +($a=0$ and $c=0$) + +$\theta(0,b) = b = d = \theta(0,d),$ easily showing that $b=d$ and the +function is injective. + +(WLOG, $a=1$ and $c=0$) + +$\theta(1,b) = 1-2b+b = d = \theta(0,d).$ +With $b,d\in\bb Z,$ $b+d \geq 2,$ so the rearranged equation +$1 = b+d$ is impossible. + +\smallskip +(Surjective) + +Let $n\in\bb Z.$ We will show that for some $a\in\{0,1\}$ and $b\in\bb +N,$ $\theta(a,b) = n.$ +We will deal with two cases: + +($n > 0$) + +Let $a = 0$ and $b = n.$ +$\theta(0,n) = 0-2(0)(n)+n = n.$ + +($n \leq 0$) + +Let $a = 1$ and $b = -n+1.$ +$\theta(1, -n+1) = 1-2(1)(-n+1) + (-n+1) = 1+2n-2-n+1 = n.$ + +Because $\theta$ is both injective and surjective, it is bijective. +\endanswer + +\problem{14.} +Consider the function $\theta: {\cal P}(\bb Z) \to {\cal P}(\bb Z)$ +defined as $\theta(X) = \bar X.$ Is $\theta$ injective? Is it +surjective? Bijective? Explain. +\answer + +$\theta$ is injective and surjective. + +\smallskip +(Injective) + +Let $X$ and $Y$ be subsets of $\bb Z$ such that $\theta(X) = \theta(Y).$ +$\bar X = \bar Y$ implies $\bar{\bar X} = +\bar{\bar Y}$ and $X = Y.$ + +\smallskip +(Surjective) + +Let $X$ be a subset of $\bb Z.$ $\bar X$ maps through $\theta$ to +$X.$ $\theta(\bar X) = \bar{\bar X} = X.$ + +We have shown that $\theta$ is injective, surjective, and, therefore, +bijective. + +\endanswer + +\bye -- cgit