\documentclass{article} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{enumerate} \usepackage{ifthen} \usepackage{graphicx} \usepackage{color} \setlength{\unitlength}{0.1in} \setlength{\oddsidemargin}{-0.35in} \setlength{\evensidemargin}{-0.35in} \setlength{\topmargin}{-0.6in} \setlength{\headheight}{0.0in} \setlength{\headsep}{0.0in} \setlength{\topskip}{0.0in} \setlength{\textheight}{9.8in} \setlength{\textwidth}{7.2in} \newcommand{\comp}{ \,{\scriptstyle \stackrel{\circ}{}}\, } \newcommand{\nullset}{\mathrm{O}\!\!\!\!\big/\,} \newcommand{\divides}{\,\Big|\,} \newcommand{\myspace}{\mbox{\parbox[c][0.35in]{0.35in}{\hfill}}} \newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}} \begin{document} %\pagestyle{empty} \noindent \parbox{2in}{\bf Math 3110} \hfill {\Large \bf Test \#1} \hfill \parbox{2in}{\bf \hfill February $22^{\mathrm{nd}}$, 2010} \vspace{0.3in} \noindent {\large\bf Name:} \underline{\color{red}\Large\sc Answer Key}\\ Don't merely state answers, prove your statements. {\bf Be sure to show your work!} \vspace{0.2in} \noindent {\bf \large 1. (10 points)} Let $S=\mathbb{R}-\{0\}$ (the set of non-zero reals). For $x,y \in S$, define $x \star y = x^{-1}y$. [Example: $5 \star 10 = 10/5 = 2$] \begin{enumerate}[(a)] \item Is $S$ closed with respect to $\star$? \vspace{0.1in} Yes. Suppose that $x,y \in S$. This means that $x$ and $y$ are non-zero real numbers. Thus $x^{-1}=1/x$ is a non-zero real number and so $x \star y = x^{-1}y$ is a non-zero real number (a non-zero real times a non-zero real is a non-zero real). Thus $x \star y \in S$. \vspace{0.1in} \item The operation $\star$ is {\bf not} associative. Give a example which shows this. \vspace{0.1in} To show $\star$ fails to be associative, we need to find a single example where associativity does not work. Let's try (somewhat randomly) $3,2,1 \in S$. Then $(3 \star 2)\star 1 = (3^{-1}2)\star 1 = (2/3) \star 1 = (2/3)^{-1}1 = 3/2$ whereas $3 \star (2 \star 1) = 3 \star (2^{-1}1) = 3 \star (1/2) = 3^{-1}(1/2)=1/6$. Thus $(3 \star 2) \star 1 \not= 3 \star (2 \star 1)$. Thus $\star$ is not associative. {\it Note:} In general, $x \star y = x^{-1}y=y/x$ so $x \star (y \star z) = x \star (z/y) = (1/x)(z/y) = z/(xy)$ whereas $(x \star y) \star z = (y/x) \star z = (x/y)z = (zx)/y$. Thus any numbers $x,y,z$ where $x\not= \pm1$ would have worked. \vspace{0.1in} \end{enumerate} \noindent {\bf\large 2. (15 points)} Here are 3 collections of subsets of $\mathbb{Z}$. 2 of these collections are {\bf not} partitions -- {\bf explain why they fail to be partitions}. 1 of these collections is a partition -- {\bf describe the corresponding equivalence relation}. \begin{enumerate}[(a)] \item $\{-1,-2,-3,\dots \}$ and $\{ 1^2, 2^2, 3^2, 4^2, \dots \}$ \vspace{0.1in} A partition is a collection of non-empty, disjoint subsets, which when unioned together give the whole set. Notice that $\{ -1,-2,\dots \} \cup \{ 1^2,2^2,\dots \} = \{ \dots, -3,-2,-1,1,4,9,16,\dots \}$ is missing a lot of integers [In particular, $0$ is missing]. So these sets do not form a partition of $\mathbb{Z}$. \vspace{0.1in} \item $\{\dots,-6,-3,0,3,6,9,\dots\}=\{3k \,|\, k \in \mathbb{Z} \}$,\\ $\{\dots,-5,-2,1,4,7,\dots\}=\{3k+1 \,|\, k \in \mathbb{Z} \}$, and\\ $\{\dots,-4,-1,2,5,8,\dots\}=\{3k+2 \,|\, k \in \mathbb{Z} \}$. \vspace{0.1in} If these sets are unioned together we get all of the integers. They are certainly non-empty sets. Finally, they are disjoint (they do not share any elments). Thus these sets partition $\mathbb{Z}$. Although I did not expect this from anyone taking the test, I will give a more detailed proof. First, it is obvious that all three sets are non-empty: $0,1,2$ are elements of each of the respective sets. Next, suppose $m \in \mathbb{Z}$. Then the division algorithm states that there are {\bf unique} integers $q,r \in \mathbb{Z}$ such that $m =3q+r$ where $0 \leq r <3$. Thus $m=3q$, $3q+1$, or $3q+2$. So $m$ belongs to one of these sets. Finally, since the remainder, $r$, is unique $m$ belongs to {\bf exactly one} of these sets (i.e. they are disjoint). \vspace{0.1in} \item $\{\dots,-3,-2,-1,0\}$ and $\{0,1,2,3,\dots \}$ \vspace{0.1in} Although the union of these sets is all of $\mathbb{Z}$, the sets are not disjoint (both contain $0$). Thus these sets do not partition $\mathbb{Z}$. \vspace{0.1in} \end{enumerate} \noindent {\bf\large 3. (15 points)} One-to-one and onto. \begin{enumerate}[(a)] \item Let $f : A \rightarrow B$ and $g : B \rightarrow A$. Suppose that $g \circ f$ is bijective. Prove {\bf ONE} of the following: \hfill i. $f$ is injective (i.e. one-to-one). \hfill ii. $g$ is surjective (i.e. onto). \hfill \hfill \vspace{0.1in} Proof of i. Suppose that $f(x)=f(y)$. Then $g(f(x))=g(f(y))$ so that $g \circ f(x) = g \circ f(y)$. However, $g \circ f$ is bijective. Thus it is one-to-one (injective). Therefore, $x=y$. Thus $f$ is one-to-one as well. \vspace{0.1in} Proof of ii. Suppose that $y \in A$ (the codomain of $g$). We know that $g \circ f$ is bijective. Thus $g \circ f$ is onto (surjective). Therefore, there exists some $z \in A$ such that $g \circ f(z)=y$. Let $x=f(z) \in B$. We have that $g(x)=g(f(z))=g \circ f(z)=y$. Therefore, $g \circ f$ is onto. \vspace{0.1in} \item Let $h:\mathbb{Z} \rightarrow \mathbb{Z}$ be defined by $h(x)=2x$. Is $h$ one-to-one? Is $h$ onto? {\bf Prove your answers.} \vspace{0.1in} Suppose $h(x)=h(y)$ for some integers $x,y$. Then $2x=2y$ and so $x=y$. Thus $h$ is one-to-one. On the other hand, $h$ is not onto. Notice that the range of $h$ is all {\bf even} integers (not all integers) so the range is not equal to the codomain. OR more concretely, suppose $h(x)=1$. Then $2x=1$ and so $x=1/2$. But $1/2 \not\in \mathbb{Z}$. Therefore, $1$ is not in the range of $h$. Thus $h$ is not onto. {\it Note:} $h(x)=2x$ is both one-to-one and onto if we change its domain and codomain to $\mathbb{R}$ (the real numbers). \vspace{0.1in} \end{enumerate} \noindent {\bf\large 4. (20 points)} Quick Proofs \begin{enumerate}[(a)] \item Using induction, show that $n < 2^n$ for all {\bf non-negative} integers $n$. {\it Hint:} $1+ 2^n \leq 2^n + 2^n$.\\ {\bf YOU MUST USE INDUCTION!} \vspace{0.1in} Base case $n=0$: $0<1=2^0$ thus the inequality holds for $n=0$ (the smallest {\bf non-negative} integer). Inductive step: Suppose that $n<2^n$ for some non-negative integer $n$. Then $n+1<2^n+1$ since we assumed $n<2^n$. Then $n+1<2^n+1<2^n+2^n=2(2^n)=2^{n+1}$ since $1<2^n$ for all non-negative integers $n$ (we will just use this fact, however, it too can be proven using induction). Thus we showed that $n<2^n$ for $n=0$ and that $n<2^n$ implies $n+1<2^{n+1}$ for each non-negative integer $n$. Therefore, by induction, $n<2^n$ for all non-negative integers $n$. \vspace{0.1in} \item Let $f:A \rightarrow B$ and $S_1,S_2 \subseteq A$. Show that $f(S_1) \cup f(S_2) \subseteq f(S_1 \cup S_2)$. \vspace{0.1in} Suppose $x \in f(S_1) \cup f(S_2)$. Then either $x \in f(S_1)$ or $x \in f(S_2)$. This means that either there exists some $s \in S_1$ such that $x=f(s)$ or there exists some $s \in S_2$ such that $x=f(s)$. Therefore, there exists some $s \in S_1$ or $s \in S_2$ such that $x=f(s)$. Thus there exists some $s \in S_1 \cup S_2$ such that $x=f(s)$. Therefore, by definition, $x \in f(S_1 \cup S_2)$. So we have shown that all the elements in $f(S_1) \cup f(S_2)$ are also in $f(S_1 \cup S_2)$. Therefore, $f(S_1) \cup f(S_2) \subseteq f(S_1 \cup S_2)$. \vspace{0.1in} \end{enumerate} \noindent {\bf\large 5. (20 points)} Divisibility \begin{enumerate}[(a)] \item Use the Euclidean algorithm to find $(4,11)=d$ (i.e. GCD of 4 and 11). Then use your work to backtrack through the algorithm and find integers $x$ and $y$ such that $4x+11y=d$ \vspace{0.1in} $11$ divided by $4$ is $2$ remainder 3: $11=(2)4+3$. Next, $4$ divided by $3$ is 1 remainder $1$: $4=(1)3+1$. Finally, $3$ divided by $1$ is $3$ remainder $0$. The Euclidean algorithm says that the last non-zero remainder is the GCD. Thus the GCD of $4$ and $11$ is $1$. Next, we will use the facts: $(-1)3+4=1$, $(-2)4+11=3$ to find a linear combination of $4$ and $11$ which gives us $1$. Start with $(-1)3+4=1$ and replace $3$ with $(-2)4+11$. This gives us $(-1)[(-2)4+11]+4=1$ so that $(3)4+(-1)11=1$. \vspace{0.1in} \item Suppose $ax+by=6$ for some integers $a,b,x,y$. What are the possible value(s) of $(a,b)$? \vspace{0.1in} We have a theorem which states (for $a,b \in \mathbb{Z}$ not both 0): $\{ ax+by \;|\; x,y \in \mathbb{Z} \} = \{ kd \;|\; k \in \mathbb{Z} \}$ where $d$ is the GCD of $a$ and $b$. In words, every linear combination of $a$ and $b$ is a multiple of the GCD and conversely every multiple of the GCD can be written as a linear combination of $a$ and $b$. Therefore, $6$ must be a multiple of the gcd of $a$ and $b$. Thus we can conclude that the GCD of $a$ and $b$ is $1,2,3,$ or $6$. \vspace{0.1in} \item Let $a,b,c \in \mathbb{Z}$ such that $a$ and $b$ are relatively prime, $a \,\Big| \, c$, and $b \,\Big|\, c$. Show that $ab \,\Big|\, c$. \vspace{0.1in} Since $a$ and $b$ are relatively prime (i.e. their GCD is $1$), there exists $x,y \in \mathbb{Z}$ such that $ax+by=1$. Next, since $a$ and $b$ divide $c$, there exists $k,\ell \in \mathbb{Z}$ such that $ak=c$ and $b\ell=c$. Thus $c=c \cdot 1 = c(ax+by) = cax+cby = (\ell b)ax + (k a)by = ab(\ell x+ ky)$. Thus $ab$ divides $c$ since $\ell x+ky \in \mathbb{Z}$. \vspace{0.1in} \end{enumerate} \noindent {\bf\large 6. (20 points)} Workin' mod 6 \begin{enumerate}[(a)] \item Finish filling out the following addition and multiplication tables for $\mathbb{Z}_6$ (operations are addition and multiplication ``mod 6''): \vspace{0.1in} \noindent \begin{tabular}{|c|||c|c|c|c|c|c|} \hline $+$ & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline \hline \hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ \hline 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ \hline 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ \hline 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ \hline 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \hline \end{tabular} \hspace{0.2in} \begin{tabular}{|c|||c|c|c|c|c|c|} \hline $\times$ & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline \hline \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ \hline 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ \hline 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ \hline 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ \hline 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ \hline 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \hline \end{tabular} \vspace{0.1in} \item For each $x \in \mathbb{Z}_6$, either find $x^{-1}$ or write ``DNE'' (if the multiplicative inverse does not exist). \begin{tabular}{|l|l|l|l|l|l|} \hline \parbox[c][0.5in]{0.75in}{$0^{-1} = \mathrm{DNE}$} & \parbox[c][0.5in]{0.75in}{$1^{-1} = 1$} & \parbox[c][0.5in]{0.75in}{$2^{-1} = \mathrm{DNE}$} & \parbox[c][0.5in]{0.75in}{$3^{-1} = \mathrm{DNE}$} & \parbox[c][0.5in]{0.75in}{$4^{-1} = \mathrm{DNE}$} & \parbox[c][0.5in]{0.75in}{$5^{-1} = 5$} \\ \hline \end{tabular} \vspace{0.1in} For example, there is no number such that $2x=1$ mod $6$, so $2$ has no multiplicative inverse. On the other hand, $5 \cdot 5=1$ mod $6$ so $5$ is its own multiplicative inverse. \vspace{0.1in} \item For each $x \in \mathbb{Z}_6$, either find $-x$ or write ``DNE'' (if the additive inverse does not exist). \begin{tabular}{|l|l|l|l|l|l|} \hline \parbox[c][0.5in]{0.75in}{$-0 = 0$} & \parbox[c][0.5in]{0.75in}{$-1 = 5$} & \parbox[c][0.5in]{0.75in}{$-2 = 4$} & \parbox[c][0.5in]{0.75in}{$-3 = 3$} & \parbox[c][0.5in]{0.75in}{$-4 = 2$} & \parbox[c][0.5in]{0.75in}{$-5 = 1$} \\ \hline \end{tabular} \vspace{0.1in} Every number has an additive inverse (mod anything). For example, $2+4=0$ mod $6$ so $2$ is the additive inverse of $4$ and $4$ is the additive inverse of $2$. \vspace{0.1in} \item Compute $2^{-1}(5-1)+3$ or explain why this is undefined. \vspace{0.1in} This is undefined since $2$ has no multiplicative inverse mod 6 (i.e. $2^{-1}$ does not exist). \vspace{0.1in} \item Compute $5^{-1}(3+4)-2$ or explain why this is undefined. \vspace{0.1in} $5^{-1}(3+4)-2 = 5(3+4)-2 = 5(1)-2=5-2=3$ (using $5^{-1}=5$ and $3+4=1$ mod 6). Alternatively $5^{-1}(3+4)-2 =5(7)-2=35-2=33=3$ mod 6. We can perform the all of the operations (with the exception of division) using regular integer arithmetic. \vspace{0.1in} \end{enumerate} \end{document}