\documentclass[12pt,a4paper]{amsart}
%%%%%%%%%%% Here is where you tell LaTeX to use packages. Each
%%%%%%%%%%% package gives you access to different commands and
%%%%%%%%%%% functionality. Most of them are unnecessary for the
%%%%%%%%%%% mathematics in this document.

%%%%%%%%%%% If you hadn't figured out, the % symbol automatically
%%%%%%%%%%% nulls out all subsequent characters on that line. So
%%%%%%%%%%% it's used for commenting code.
\usepackage{hyperref}
\usepackage{tikz}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{framed}
\usepackage{multicol}
\usepackage[OT2,T1]{fontenc}
\usepackage{graphicx}
\usepackage[all]{xy}
\usepackage{color}
\usepackage{mathrsfs}
\usepackage{mathtools}

%%%%%%%%%%% Determining margins and spacing.
\setlength\topmargin{-0.3in}
\addtolength{\oddsidemargin}{-.625in}
	\addtolength{\evensidemargin}{-.625in}
	\addtolength{\textwidth}{1.25in}
\setlength\footskip{1in}

%%%%%%%%%%% I think this command enables `sections'
\numberwithin{equation}{section}

%%%%%%%%%%% This command allows you to label things as `theorem',
%%%%%%%%%%% `conjecture', etc.
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{question}{Question}[theorem]
\newtheorem{example}{Example}[theorem]


\usepackage[utf8]{inputenc}
\title{Math 220.201 Class 15 Questions}
\begin{document}
\maketitle
{\bf Remember:} if $A$ and $B$ are sets, then a \emph{relation} from $A$ to $B$ is a subset $R\subseteq A\times B$.

A \emph{function} is a subset $f\subseteq A\times B$ such that for each $a\in A$, there is \emph{exactly one} $b\in B$ such that $(a,b)\in f$. We also use the notation $f(a)=b$, and write $f:A \rightarrow B$ to say `$f$ is a function from $A$ to $B$. The subset $f\subseteq A\times B$ is called the \emph{graph} of the function.

$A$ is called the \emph{domain} of $f$.

$B$ is called the \emph{codomain} of $f$.

The \emph{image} of a set $C\subseteq A$ (written $f(C)$) is the set $\{b\in B|\exists c\in C, f(c)=b\}$.

The \emph{range} of $f$ is $f(A)$.

The \emph{preimage} of a set $D\subseteq B$ (written $f^{-1}(D)$) is the set $\{a\in A|f(a)\in D\}$.
\begin{enumerate}
\item Prove that the function $f:[0,\infty) \rightarrow \mathbb{R}$ defined by $f(x)=x^2$ is injective, but not surjective.
\vskip 0.2in
\begin{proof}
First we prove that it is injective. Suppose that $x_1, x_2\in [0, \infty)$ are such that $f(x_1)=f(x_2)$. Then $x_1^2=x_2^2$, and so $(x_1-x_2)(x_1+x_2)=0$. This means that either $x_1=-x_2$ (impossible unless $x_1=x_2=0$) or $x_1=x_2$. Either way, $x_1=x_2$, and so the function is injective.

To prove the function is not surjective, we see that any negative real number is not in the image. For example, there is no $x\in [0,\infty)$ such that $f(x)=-5$.
\end{proof}
\vskip 0.2in
\item Prove that the function $f:\mathbb{R} \rightarrow [0,\infty)$ defined by $f(x)=x^2$ is surjective, but not injective.
\vskip 0.2in
\begin{proof}
First we prove that it is surjective. We must show that for any $y\in [0,\infty)$, there is some $x\in\mathbb{R}$ such that $x^2=y$. Just pick $x=\sqrt{y}$.\footnote{This proof assumed that we already had the function $\sqrt{}$. To complete the proof without using this: we can find some small number $a$ such that $a^2<y$ and some very large number $b$ such that $b^2>y$. Since the function $f(x)=x^2$ is continuous, the Intermediate Value Theorem tells us there is some number $x$ between $a$ and $b$ such that $x^2=y$.}

To prove the function is not injective, notice that $f(3)=f(-3)=9$. These are two different inputs which give the same output, which means the function is not injective.
\end{proof}
\vskip 0.2in
\item Prove that the function $f:\mathbb{R} \rightarrow (0,\infty)$ defined by $f(x)=2^x$ is injective. (You can also prove that it is surjective without using logarithms, but it involves the Intermediate Value Theorem.)
\vskip 0.2in
\begin{proof}
Suppose that $x_1, x_2\in\mathbb{R}$ are any numbers such that $f(x_1)=f(x_2)$. Then $2^{x_1}=2^{x_2}$, and so $2^{x_1-x_2}=1$. But if $x_1-x_2>0$, then $2^{x_1-x_2}>1$, and if $x_1-x_2<0$, then $2^{x_1-x_2}<1$. Therefore it must be that $x_1-x_2=0$, and so $x_1=x_2$. This proves that the function is injective.
\end{proof}
\vskip 0.2in
\item Remember that for any positive integer $n$, $\mathbb{Z}_n=\{[0], [1], \ldots, [n-1]\}$ is the set of \emph{equivalence classes} for the equivalence relation `$\equiv \pmod{n}$'.
\begin{enumerate}
\item Prove that the function $f:\mathbb{Z} \rightarrow \mathbb{Z}_5$ defined by $f(x)=[x]$ is surjective, but not injective. (This isn't a trick question, it is just to check that you understand the definitions.
\vskip 0.2in
\begin{proof}
Pick any element of $\mathbb{Z}_5$ - i.e., an equivalence class of elements in $\mathbb{Z}$. It contains at least one element $x\in\mathbb{Z}$. Then this equivalence class is $[x]$. And so $f(x)=[x]$. Hence, the function $f$ is surjective. It is not injective, though - for example, $1$ and $6$ both map to the class $[1]$.
\end{proof}
\vskip 0.2in
\item Prove that the function $f:\mathbb{Z}_5 \rightarrow \mathbb{Z}_5$ defined by $f([x])=[3x+1]$ is a bijection.
\begin{proof}
First we'll prove that it's injective. Suppose that $[x]$ and $[y]$ are two equivalence classes (represented by integers $x$ and $y$) such that $[3x+1]=[3y+1]$. This means that
$$3x+1 \equiv 3y+1\pmod{5}$$
Then $5\mid (3y+1)-(3x+1)$. This means $5\mid 3(y-x)$. Since $5$ is prime, and $5\nmid 3$, this means $5|y-x$, and so $x\equiv y\pmod{5}$. So $[x]=[y]$. Hence, the function is injective.
\vskip 0.1in
Now we prove it's surjective. Suppose that $[y]$ is an equivalence class, where $y\in\mathbb{Z}$.. We must show that $[y]=[3x+1]$ for some $x\in\mathbb{Z}$. If we let $x=2y-2$, then
$$3x+1=3(2y-2)+1=6y-5 \equiv 6y \equiv y\pmod{5}$$
and so we get $[y]=[3x+1]$. Therefore, the function is surjective.
\end{proof}
\end{enumerate}
\end{enumerate}
\end{document}