\documentclass[12pt]{article}

\usepackage{amssymb,amsmath,amsthm} 
\usepackage{color}
\usepackage{verbatim}

%%% Margins %%%
\setlength{\topmargin}{0pt}
\setlength{\headheight}{0pt}
\setlength{\headsep}{0pt}
\setlength{\topskip}{0pt}
\setlength{\footskip}{0pt}
\setlength{\oddsidemargin}{-20pt}
\setlength{\textheight}{9in}
\setlength{\textwidth}{6.7in}
\setlength{\parindent}{0pt}
\setlength{\parskip}{4ex}

%%% Macros %%%
% Some macros to get you started
\DeclareMathOperator{\Vol}{Vol}
\DeclareMathOperator{\im}{im}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\QQ}{\mathbb{Q}}




\begin{document}

\pagestyle{empty}

\begin{center}
{\large MATH 108 Fall 2019 \ -  \ {\bf Problem Set 6}}

% Put your name and section here.
{\large due November 8}
\end{center}


\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item For each pair of sets $A$ and $B$, and subset $\Gamma \subseteq A \times B$ determine if $\Gamma$ is the graph of a function from $A$ to $B$.  Justify your answer.
	 \begin{enumerate}
	  \item $A = B = \RR$ and $\Gamma = \{(x,y) \in \RR^2 \mid x = y^2 \}$.
	  \item $A = B = \RR$ and $\Gamma = \{(x,y) \in \RR^2 \mid y = x^2 \}$.
      \item $A = B = \RR$ and $\Gamma = \{(x,y) \in \RR^2 \mid y = \sqrt{x} \}$.
	  \item $A = B = \ZZ$ and $\Gamma = \{(n,0) \mid n \in \ZZ \}$.
	  \item $A = \ZZ$, $B = \{0\}$ and $\Gamma = \{(n,0) \mid n \in \ZZ \}$.
	  \item $A = B = \ZZ/5\ZZ$ and $\Gamma = \{(a,b) \mid a = \overline{2}b \}$.
	 \end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item\label{inj} For each function $f$, determine if it is injective.  If yes, find a {\em left-inverse} of $f$, which is a function $g$ such that $g \circ f$ is the identity.
	 \begin{enumerate}
	  \item $f:\RR \to \RR^2$ defined by $f(x) = (x,x)$.
	  \item $f:\RR^2 \to \RR$ defined by $f(x,y) = x+y$.
	  \item $f:\ZZ \to \ZZ$ defined by $f(x) = 2x$.
	  \item $f:\RR \to \RR$ defined by $f(x) = e^x$.
	  \item $f:\ZZ \to \{0\}$ defined by $f(x) = 0$.
	 \end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Let $f:A \to B$ and $g:B \to C$.
     \begin{enumerate}
	  \item Prove that if $g \circ f$ is injective then $f$ is injective.
	  \item Give an example of $f$ and $g$ where $g \circ f$ is injective but $g$ is not injective.
	 \end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Let $S$ be a set with partial order $\sqsubseteq$ and $T$ be a set with partial order $\preceq$.  A function $f:S\to T$ is called {\em order-embedding} if it satisfies the property that $x \sqsubseteq y$ if and only if $f(x) \preceq f(y)$.  Prove that if $f$ is order-embedding then $f$ injective.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Let $a$ and $m$ be integers with $0 < a < m$.  Let $f:\ZZ/m\ZZ \to \ZZ/m\ZZ$ be the function defined by $f(\overline{x}) = \overline{a}\cdot \overline{x}$.  Prove that $f$ is injective if and only if $\gcd(a,m) = 1$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{enumerate}
\end{document}


