1 files changed, 294 insertions, 0 deletions
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