\documentclass[12pt]{amsart}

\usepackage{amsmath, amssymb, amsthm}
\usepackage[margin=0.5in]{geometry}
\usepackage[pdflang={en-US}]{hyperref}
\usepackage[shortlabels]{enumitem}

\usepackage{tikz}

\renewcommand{\thesection}{\Alph{section}}

\newcommand{\scs}[1]{\begin{scshape}#1\end{scshape}}
\newcommand{\inv}{^{-1}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\nmod}[1][n]{\left(\text{mod}\ #1\right)}

\newtheorem*{theorem}{Theorem}
\newtheorem{proposition}{Proposition}
\theoremstyle{definition}
\newtheorem*{definition}{Definition}
\newtheorem{problem}{}
\newtheorem*{challenge}{Challenge}
\newtheorem*{example}{Example}

\newcommand{\thm}[1]{\begin{theorem}#1\end{theorem}}
\newcommand{\prop}[1]{\begin{proposition}#1\end{proposition}}
\newcommand{\prob}[1]{\begin{problem}#1\end{problem}}
\newcommand{\dfn}[1]{\begin{definition}#1\end{definition}}
\newcommand{\chal}[1]{\begin{challenge}#1\end{challenge}}
\newcommand{\eg}[1]{\begin{example}#1\end{example}}

\newcommand{\abs}[1]{\left| #1 \right|}

\title{Functions}
\date{April 20, 2022}

\begin{document}\ 

\vspace{-.25in}

\maketitle

\vspace{-.2in}

\prob{
Let $A$, $B$, and $C$ be sets.
Suppose $f: A \to B$ and $g:B \to C$ are both surjective.
Finish proving that $g \circ f: A \to C$ is surjective.

\begin{proof}
Let $A$, $B$, and $C$ be sets.
Suppose $f: A \to B$ and $g:B \to C$ are both surjective.
If $C = \emptyset$, then $g \circ f$ is trivially surjective.
To deal with the other case, suppose $C \neq \emptyset$.
Let $ c \in C$.

\vfill


\noindent Thus $(g\circ f)(a) = c$.
Therefore $g \circ f$ is surjective.
\end{proof}
}

\prob{
Let $A$, $B$, and $C$ be sets.
Suppose $f: A \to B$ and $g:B \to C$ are both injective.
Finish proving that $g \circ f: A \to C$ is injective.

\begin{proof}
Let $A$, $B$, and $C$ be sets.
Suppose $f: A \to B$ and $g:B \to C$ are both injective.
If $A = \emptyset$, then $g \circ f$ is trivially injective.
To deal with the other case, suppose $A \neq \emptyset$.
Let $a_1, a_2 \in A$ and suppose $(g\circ f)(a_1) = (g\circ f)(a_2)$.

\vfill


\noindent Thus $a_1= a_2$.
Therefore $g \circ f$ is injective.
\end{proof}
}

%\noindent \hrulefill

\dfn{
If $f: A \to B$ is both injective and surjective, then it is called a \textbf{bijection}. 
}

If there is a bijection between sets $A$ and $B$, then the sets must be the same size.
For example, Let $A = \{a, b, c\}$ and let $B = \{1, 2, 3\}$.
It is easy to find bijection between $A$ and $B$: $\{ (a,1), (b, 2), (c,3) \}$.
This turns out to give a good definition of the size (or cardinality) of a set.

\dfn{
Let $A$ and $B$ be sets.
Then we say $A$ and $B$ have the same \textbf{cardinality} and write $\abs{A} = \abs{B}$ if there is a bijection between $A$ and $B$.
}

The definition matches our expectations for sizes finite sets.
Things get a little stranger when dealing with infinite sets.
Note first that your proofs above show that the relation of having equal cardinality is transitive.
You should be able to quickly prove that the relation is both relexive and symmetric and hence is an equivalence relation.

\newpage

\prob{
Let $A = \{ 2n: n \in \ZZ \}$ and $B = \{ 2n+1: n \in \ZZ \}$.
For each of the following statements find a bijection that proves the statement is true.
\begin{enumerate}[a)]
\item $\abs{\ZZ} = \abs{A}$

\vspace{.75in}

\item $\abs{A} = \abs{B}$

\vspace{.75in}


\item $\abs{\NN} = \abs{\ZZ}$

\vspace{.75in}

\end{enumerate}
}

%\newpage

\thm{[Shr\"oder-Bernstein]
Let $A$ and $B$ be sets.
If there is an injective function from $A$ to $B$ and another injective function from $B$ to $A$, then there is a bijection between $A$ and $B$. 
}

\prob{
We can use the Shr\"oder-Bernstein theorem to prove that $\abs{\ZZ} = \abs{\QQ}$.
We just need to:
\begin{enumerate}[a)]
\item Produce an injective function from $\ZZ$ to $\QQ$.

\vspace{1in}

\item (Harder) Produce an injective function from $\QQ$ to $\ZZ$. 

\vfill

\end{enumerate} 
}

\prob{
Prove that $\abs{\NN} = \abs{\QQ}$.
}

\vspace{1.5in}

\prob{
Do you think all infinite sets have the same cardinality?
}

\end{document}