\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}


%%% Environments %%%
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{define}{Definition}
\newtheorem{remark}[define]{Remark}
\newtheorem{example}{Example}
\newtheorem{question}{Question}
\newtheorem{algorithm}{Algorithm}

\numberwithin{equation}{section}

%%% 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 Winter 2019 \ -  \ {\bf Problem Set 5}}

% Put your name and section here.
{\large due February 22}
\end{center}


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

	\item Using modular arithmetic, prove that for all postive integers $n$,
	 \begin{enumerate}
	  \item $10^n - 1$ is divisible by 3.
	  \item $n^4 + 2n^3 - n^2 - 2n$ is divisible by 4.
	  \item $1^n + 2^n + 3^n + 4^n$ is divisible by 5.
	 \end{enumerate}

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

	\item The ``Cancellation Law'' for $\ZZ/m\ZZ$ is the statement: For all $x,y,z \in \ZZ$, if $xy \equiv xz \pmod{m}$ and $x \not\equiv 0 \pmod{m}$ then $y \equiv z \pmod{m}$.
	 \begin{enumerate}
	  \item Prove that if $m$ is prime then the Cancellation Law for $\ZZ/m\ZZ$ is true.
	  \item Prove that if $m$ is composite then the Cancellation Law for $\ZZ/m\ZZ$ is false.
	 \end{enumerate}
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Let $A$ and $B$ be subsets of $\ZZ$. In the poset $(\mathcal{P}(\ZZ),\subseteq)$, prove that the greatest lower bound of $\{A,B\}$ is $A \cap B$.
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Let $A$ be the set of divisors of 36,
	 $A = \{1,2,3,4,6,9,12,18,36\}$. 
	 Draw the Hasse diagram for the poset $(A, |)$.

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

	\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 For each function $f$ in Problem \ref{inj}, determine if it is surjective.  If yes, find a {\em right-inverse} of $f$, which is a function $g$ such that $f \circ g$ is the identity.

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

	\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 Find an example of $f$ and $g$ where $g \circ f$ is injective but $g$ is not injective.
	 \end{enumerate}

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

	 \item For each pair of sets, find a bijection from the first to the second.
	 \begin{enumerate}
	  \item $\NN_1$ and $\NN_0$.
	  \item $\RR^2$ and $\CC$.
	  \item $\ZZ$ and $\NN_0$.
	  \item $\{x \in \RR \mid -1 < x < 1\}$ and $\RR$.
	 \end{enumerate}
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\end{enumerate}
\end{document}


