path: root/gupta/hw7.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{\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