\documentclass[11pt]{article} \usepackage[utf8]{inputenc} \usepackage[margin=1in]{geometry} \usepackage{enumitem} \usepackage{amsmath, amssymb, amsthm} \usepackage{xcolor} \usepackage{verbatim} % THEOREM ENVIRONMENTS \theoremstyle{definition} \newtheorem*{theorem}{{Theorem}} \newtheorem*{lemma}{{Lemma}} \newtheorem*{proposition}{{Proposition}} \newtheorem*{definition}{{Definition}} \newtheorem*{corollary}{{Corollary}} \newtheorem*{example}{{Example}} \newtheorem*{remark}{{Remark}} \newtheorem*{claim}{{Claim}} \newtheorem*{question}{{Question}} \theoremstyle{plain} \newtheorem*{reminder}{{\textit{Reminder}}} \newtheorem*{hint}{{\textit{Hint}}} % ENVIRONMENTS FOR CITING BOOK STATEMENTS \newcommand{\prop}[1]{\paragraph{Proposition #1}} \newcommand{\axm}[1]{\paragraph{Axiom #1}} \newcommand{\thm}[1]{\paragraph{Theorem #1}} % COMMANDS \newcommand{\solution}{{\color{blue} \textsc{\ \\ Solution.\ \ }}} \newcommand{\revisedsolution}{{\color{blue} \textsc{\ \\ Revised Solution.\ \ }}} \newcommand{\Z}{\mathbb{Z}} % the integers \newcommand{\N}{\mathbb{N}} % natural numbers \newcommand{\R}{\mathbb{R}} % real nubers \newcommand{\Q}{\mathbb{Q}} % rational numbers \newcommand{\divides}{\ \vert \ } \newcommand{\st}{ \ : \ } % such that \newcommand{\inv}{^{-1}} % inverse \newcommand{\img}{\mathrm{im}} % image \newcommand{\into}{\hookrightarrow} % injection \newcommand{\onto}{\twoheadrightarrow} % surjection \newcommand{\map}[1]{\xrightarrow{#1}} % named map \newcommand{\id}{\mathrm{id}} % identity map % SOME ENVIRONMENTS \newcommand{\exheading}[1]{\section*{Exercise #1}} \newcounter{exnum} % \setcounter{exnum}{1} % default 0 start \newcommand{\exercise}{ \stepcounter{exnum} \exheading{\theexnum} } \newcommand{\bea}{\begin{enumerate}[label={(\alph*)}]} \newcommand{\ee}{\end{enumerate}} %%%% \title{MAT 108: Problem Set 6} \author{(ADD NAME)} \date{Due 2/21/23 at 11:59 pm on Canvas} \begin{document} \maketitle \paragraph{Reminders:} \begin{itemize} %\item Put your name at the top! \item Your homework submission must be typed up in full sentences, with proper mathematical formatting. Handwritten homework submissions will receive a score of 0. Solutions containing incomplete sentences or poor formatting will lose points. \item You will receive feedback on PS5 by next Tuesday, 2/21. PS4 revisions are due Friday, 2/24 at 11:59 pm. Underneath your old solution, type \vspace{-3mm} \begin{verbatim} \revisedsolution \end{verbatim} \vspace{-7mm} and then type your revised solution. \end{itemize} \begin{remark} The word \textbf{map} is sometimes used interchangeably with \textbf{function}. For example, $e: \Z \to \R$ is a \emph{map} from $\Z$ to $\R$. We can also say that ``$e$ \emph{maps} $1_{\Z}$ to $1_{\R}$," meaning that the function $e$ sends $1_{\Z}$ to $1_{\R}$. \end{remark} \begin{remark} For Exercises 1 and 2 below, we view $\Z/2\Z, \Z/3\Z,$ and $\Z/6\Z$ as sets with the structure of addition $(+)$. Note that 0 is the additive identity in each case. \end{remark} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \exercise In class, we discussed \emph{injectivity} and \emph{embeddings}. \begin{definition} Let $A$ and $B$ be sets. A function $f: A \to B$ is \emph{injective} if for every $b \in \img(f)$, there is a unique $a \in A$ such that $f(a) = b$. In this case, we may say that $f$ maps $A$ \emph{into} $B$. We may also write $f: A \into B$. \end{definition} We say that an injective function $f:A \to B$ is an \emph{embedding} if it allows us to identify $A$ with the subset $f(A) \subset B$ in a way that the structures of $A$ and $B$ agree. For example, $e: \Z \into \R$ is an embedding because it preserves addition, multiplication, and ordering. In other words, an \emph{injection} is a statement about a function $f$ from one set to another. If the sets have extra structure which is preserved by $f$, then $f$ may be called an \emph{embedding}. \bea \item Create addition and multiplication tables for $\Z/2\Z$, $\Z/3\Z$, and $\Z/6\Z$. \textit{ To typeset these, modify the tables we used in the previous PS.} \item Define \textit{embeddings} $i: \Z/2\Z \into \Z/6\Z$ and $j: \Z/3\Z \into \Z/6\Z$. \textit{Make sure you check for yourself that your map is actually an embedding, i.e.\ respects addition. You do not need to write down a proof that your maps are embeddings, though.} \item Define an embedding $f: \Z/2\Z \times \Z/3\Z \into \Z/6\Z$ by explicitly stating where each element is sent under the function $f$. \textit{Again, make sure to check for yourself that your map is actually an embedding. Typeset this as an organized table, by modifying the templates used in the previous PS.} \ee \solution %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \exercise In this exercise, you will learn about \emph{surjectivity} and \emph{projections}. \begin{definition} Let $A$ and $B$ be sets. A function $g: A \to B$ is \emph{surjective} if for every $b \in B$, there exists an $a \in A$ such that $g(a) = b$. In this case, we may say that $g$ maps $A$ \emph{onto} $B$. We may also write $g: A \onto B$. \end{definition} (Take a moment to compare the definition of \emph{surjectivity} to the definition of \emph{injectivity}.) We will talk about the definition of a \emph{projection} later in this course, after we've carefully talked about compositions of maps. But for now, you may use the following alternate definition: \begin{definition} A surjective map $\pi: A \onto B$ is a \emph{projection} if there exists and embedding $\iota: B \into A$ such that $\pi \circ \iota = \id_B$. \end{definition} Here, $\circ$ indicates, as usual, function composition. For example, you'd compute the composite function $\pi \circ \iota$ via the two-step process \[ A \map{\iota} B \map{\pi} A. \] The map $\id_A$ is the \emph{identity map on $A$}, i.e.\ the map $a \mapsto a$ for all $a \in A$. \bea \item Define a projection $p: \Z/6\Z \onto \Z/2\Z$ and prove that it is indeed a projection. \item Define a projection $q: \Z/6\Z \onto \Z/3\Z$ and prove that it is indeed a projection. \item In the previous exercise, you defined an injective function $f$. Note that it is also surjective (if you did it correctly). Describe the functions $p \circ f$ and $q \circ f$. \emph{However you decide to describe these functions, whether explicitly or descriptively, the reader should be able to compute the image of every element in the domain after having read your description.} \ee \solution %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \exercise The \emph{Pigeonhole Principle} is a powerful tool in mathematics. And yes, this is a technical term. \begin{lemma}[Pigeonhole Principle] (Let $n,m \in \N$.) If you have $n$ pigeons and $m$ cubby holes, and $n > m$, then no matter how you put the pigeons in the holes, there will be a hole with more than one pigeon. \end{lemma} Use the Pigeonhole Principle to show that there does not exist an injective map \[ \Z/2\Z \times \Z/3\Z \times \Z/5\Z \into \Z/15\Z. \] \solution %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \exercise We are all used to the \emph{Euclidean metric} on $\R^2 := \R \times \R$, denoted $\Vert \cdot \Vert$. This is the measure of distance where the distance between two points $(x_0, y_0), (x_1, y_1)$ is given by \[ \Vert (x_1, y_1) - (x_0, y_0) \Vert = \sqrt{(x_1 - x_0)^2 + (y_1 - y_0)^2}. \] We can define a different metric on $\R^2$, called the \emph{Manhattan metric}, denoted $\Vert \cdot \Vert_{1}$. The \emph{Manhattan distance} between $(x_0, y_0), (x_1, y_1)$ is given by \[ \Vert (x_1, y_1) - (x_0, y_0) \Vert_{1} = |x_1-x_0| + |y_1 - y_0|. \] \begin{remark} The subscript ``1" has to do with the fact that $\Vert \cdot \Vert_1$ is called the $L_1$-norm and comes from a whole family of norms, one for each natural number, plus infinity. The Euclidean norm is the $L_2$-norm. \end{remark} \bea \item Prove that ``Manhattan distance" is actually a distance function. \item Prove that the Manhattan distance between any two points is always at least the Euclidean distance between them, i.e. \[ \Vert (x_1, y_1) - (x_0, y_0) \Vert_1 \geq \Vert (x_1, y_1) - (x_0, y_0) \Vert. \] for any two points $(x_0, y_0), (x_1, y_1) \in \R^2$. \ee \end{document}