\documentclass[11pt]{article}
\usepackage[utf8]{inputenc}
\usepackage{graphicx}

\usepackage[margin=1in]{geometry}
\usepackage{enumitem}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{xcolor}

% 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{\Z}{\mathbb{Z}} % the integers
\newcommand{\N}{\mathbb{N}} % natural numbers
\newcommand{\R}{\mathbb{R}} % real numbers
\newcommand{\divides}{\ \vert \ }
\newcommand{\st}{ \ : \ } % such that
\newcommand{\inv}{^{-1}} % inverse

\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{\bei}{\begin{enumerate}[label=(\roman*)]}
\newcommand{\ee}{\end{enumerate}}

\renewcommand{\implies}{\Rightarrow} % shorter implies arrow


\newcommand{\mz}[1]{{\color{magenta} #1}} % mz comments to self


\title{MAT 108 PS07}
\author{Melissa Zhang}
\date{Due Monday, May 18, 2026 at 9:00 pm on Gradescope}

\begin{document}

\maketitle


\section*{Instructions}

There are three goals for this problem set:
\begin{itemize}
    \item Maintain good mathematical writing form, as always.
    \item Reinforce familiarity with injectivity, surjectivity, bijectivity, and inverses of functions.
    \item Gain experience thinking about more abstract distance functions. 
\end{itemize}


\noindent Here are some reminders about best practices:
\begin{itemize}
    \item You absolutely must write in full, connected English sentences. Whenever possible, do not start a sentence with mathematical symbols. Do not use symbols like $\implies$, $\forall$, $\exists$, $\therefore$, etc.\ (except when explicitly discussing statements about logic). 
    \item Your solution must be \emph{neat}. You \textbf{will} be graded on style, which includes  mathematical style and professionalism. 
    \item It is your responsibility to mark where your solutions for each problem begins on Gradescope so that the TA and reader can properly grade your solutions. 
\end{itemize}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Ungraded exercise}
Read Section 10.2 to remind yourself of how to work with the absolute value function. We will be assuming these propositions without further comment.






%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise
Determine whether the function is injective, surjective, bijective, or none of the above. Justify your assertions. 

\bea

\item $f: \Z \to \Z$, $n \mapsto n^2$
\item $f: \Z \to \Z_{\geq 0}$, $n \mapsto n^2$
\item $f: \N \to \N$, $n \mapsto n^2$
\item $f: \R \to \R$, $x \mapsto 3x+1$
\item $f: \R_{\geq 0} \to \R$, $x \mapsto 3x+1$
\item $f: \Z \to \Z$, $x \mapsto 3x+1$

\ee





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise

\bea

\item Prove that $q: \Z/8\Z \to \Z/4\Z$, $[n] \mapsto [n]$, is surjective but not injective. Define two different right inverses $j_1, j_2$ for $q$.

\item Prove that $i: \Z/4\Z \to \Z/8\Z$, $[n] \mapsto [2n]$ is well-defined and injective, but not surjective. Define two different left inverses $p_1, p_2$ for $i$. 

\ee


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise

Prove that if a function $f: A \to B$ of sets is bijective, then its inverse is unique. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise
Prove that if $g\circ f$ is bijective, then $g$ is surjective and $f$ is injective. 



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise

Recall that $d: X \times X \to \R$ is a \emph{distance function} if all of the following hold:
\begin{itemize}
    \item $d(x,y) = 0$ iff $x = y$
    \item $d(x,y) \geq 0$ for all $x,y \in X$ (we could have just written $d: X \times X \to \R_{\geq 0}$)
    \item $d(x,y) = d(y,x)$
    \item $d(x,y) + d(y,z) \geq d(x,z)$ for all $x,y,z \in X$
\end{itemize}

Let $\Z[x]$ be the set of polynomials in the indeterminate variable $x$ with coefficients in the integers.
An arbitrary polynomial in $\Z[x]$ can be written as 
\[
    a(x) = \sum_{i=0}^\infty a_i x^i
\]
where there is some $N$ such that for all $i> N$, $a_i = 0$. 

%The largest $i$ such that $a_i \neq 0$ is called the degree of $a(x)$, denoted by $\deg(a(x))$. 


Define a candidate metric function 
\begin{align*}
    \Vert \cdot \Vert : \Z[x] & \to \R \\
        a(x) & \mapsto \sum_{i=0}^\infty |a_i|\cdot  10^{-i}
\end{align*}
and the associated candidate distance function 
\[
    d(a(x),b(x)) = \Vert a(x)-b(x) \Vert.
\]


\bea
    \item Prove that $d$ is indeed a distance function. 
    \item Find an infinite subset of polynomials $\{f_k\}_{k=1}^\infty \subset \Z[x]$ such that $\Vert f_k \Vert = 1$ for all $k$.
\ee




\end{document}