\documentclass{article} \usepackage{amsmath} \usepackage{amsfonts} \usepackage{enumerate} \usepackage{ifthen} \usepackage{graphicx} \setlength{\unitlength}{0.1in} \setlength{\oddsidemargin}{0.0in} \setlength{\evensidemargin}{0.0in} \setlength{\topmargin}{0.0in} \setlength{\headheight}{0.0in} \setlength{\headsep}{0.0in} \setlength{\topskip}{0.0in} \setlength{\textheight}{8.9in} \setlength{\textwidth}{6.5in} \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{\hskip 3.0 truein}\\ Don't merely state answers, prove your statements. {\bf Be sure to show your work!} \begin{description} \item[\large 1. (\underline{\hskip 0.35 truein}/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{4in} \item The operation $\star$ is {\bf not} associative. Give a example which shows this. \end{enumerate} \newpage \item[\large 2. (\underline{\hskip 0.35 truein}/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{3in} \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{3in} \item $\{\dots,-3,-2,-1,0\}$ and $\{0,1,2,3,\dots \}$ \vspace{3in} \end{enumerate} \newpage \item[\large 3. (\underline{\hskip 0.35 truein}/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: \begin{enumerate}[i.] \item $f$ is injective (i.e. one-to-one). \item $g$ is surjective (i.e. onto). \vspace{4in} \end{enumerate} \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{3in} \end{enumerate} \newpage \item[\large 4. (\underline{\hskip 0.35 truein}/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{3.5in} \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)$. \end{enumerate} \newpage \item[\large 5. (\underline{\hskip 0.35 truein}/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{3in} \item Suppose $ax+by=6$ for some integers $a,b,x,y$. What are the possible value(s) of $(a,b)$? \vspace{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$. \end{enumerate} \newpage \item[\large 6. (\underline{\hskip 0.35 truein}/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 \mbox{} \hspace{-0.6in} \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 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline 2 & 2 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline 3 & 3 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline 4 & 4 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline 5 & 5 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \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 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline 3 & 0 & 3 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline 4 & 0 & 4 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \hline 5 & 0 & 5 & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} & \varspace{0.3in}{0.2in} \\ \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} = $} & \parbox[c][0.5in]{0.75in}{$1^{-1} = $} & \parbox[c][0.5in]{0.75in}{$2^{-1} = $} & \parbox[c][0.5in]{0.75in}{$3^{-1} = $} & \parbox[c][0.5in]{0.75in}{$4^{-1} = $} & \parbox[c][0.5in]{0.75in}{$5^{-1} = $} \\ \hline \end{tabular} \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 = $} & \parbox[c][0.5in]{0.75in}{$-1 = $} & \parbox[c][0.5in]{0.75in}{$-2 = $} & \parbox[c][0.5in]{0.75in}{$-3 = $} & \parbox[c][0.5in]{0.75in}{$-4 = $} & \parbox[c][0.5in]{0.75in}{$-5 = $} \\ \hline \end{tabular} \vspace{0.1in} \item Compute $2^{-1}(5-1)+3$ or explain why this is undefined. \vspace{2in} \item Compute $5^{-1}(3+4)-2$ or explain why this is undefined. \end{enumerate} \end{description} \end{document}