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

\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{\divides}{\ \vert \ }
\newcommand{\st}{ \ : \ } % such that

\newcommand{\exheading}[1]{\section*{Exercise #1}}
\newcounter{exnum}
% \setcounter{exnum}{1} % default 0 start
\newcommand{\exercise}{
    \stepcounter{exnum} 
    \exheading{\theexnum}
    }



%%%%
\title{MAT 108: Problem Set 2}
\author{(ADD NAME)}
\date{Due 1/24/23 at 11:59 pm on Canvas}

\begin{document}

\maketitle


\paragraph{Reminders:}
\begin{itemize}
\item Put your name at the top!
\item You will receive feedback on PS1 by next Tuesday, 1/24. PS1 revisions are due Friday, 1/27 at 11:59 pm.
\item Dr.~Zhang will be away all of next week (no instructor office hours). I will be in Germany, where the time is 9 hours ahead of California. You may email me your questions, and I will respond once daily as usual. The TA will still hold his office hours. 
\end{itemize}


\paragraph{Another reminder} Figuring out how to prove something should feel like doing a puzzle. Writing down and expressing your proof should feel like you're trying to write in a new language. Trust the process!


\paragraph{How much detail is needed?} In PS2, you no longer need to cite the axioms / propositions from Chapter 1. For example, it's clear to the audience (e.g.\ your classmates) that $-0 = 0$. 

On the other hand, in Chapter 2, we defined the natural numbers $\N$ using a set of axioms that are not very obvious to your peers. You should cite these axioms as you use them.

%%%%



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

\textbf{Prove that $1 \in \N$ via a proof by contradiction. Then, deduce that that if $n \in \N$, then $n+1 \in \N$. }

\begin{remark}
The phrase \emph{deduce that} here is indicating that the second statement follows quite immediately from the first.
\end{remark}


\solution

% INSERT YOUR SOLUTION HERE






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

\begin{definition}
Let $m, n \in \Z$. If $m - n \in \N$, then we say $n$ \emph{is less than} $m$, and write $n < m$. We also say $m$ \emph{is greater than} $n$, and write $m > n$. 
\end{definition}

\textbf{Prove that there exists no integer $x$ such that $0 < x < 1$. }


\solution

% INSERT YOUR SOLUTION HERE





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\exercise
Use induction to prove that for any $n \in \N$, the following formula holds:
\[
    1 + 2 + 3 + \ldots + (n-1) + n = \frac{n(n+1)}{2}.
\]






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

\begin{definition}
Let $p \in \N$.  If the only $k\in \N$ such that $k \divides p$ are $k = 1$ and $k=p$, then $p$ is \emph{prime}.
\end{definition}

\textbf{Prove that there are infinitely many prime numbers. }

\begin{remark}
We haven't rigorously discussed the term \emph{infinite} just yet. We will discuss cardinality in detail in a few weeks. For now, \emph{infinite} means \emph{not finite}. 

You should begin by assuming there are finitely many prime numbers, so that you can label them $p_1, p_2, p_3, \ldots, p_n$ for some finite $n\in\N$. Then try to derive a contradiction.
\end{remark}

You may use the following Lemma without proof:

\begin{lemma}
Let $p$ be a prime number, and let $m \in \N$. If $p$ divides $m$, then $p$ does not divide $m+1$. 
\end{lemma} 

(Proving this lemma will be easier once we've developed the language of \emph{modular arithmetic} later on in the course.)


\solution

% INSERT YOUR SOLUTION HERE




\end{document}