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