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

\newcommand{\R}{\mathcal{R}}

\usepackage[utf8]{inputenc}
\title{Math 220.201 Class 18 Questions}
\begin{document}
\maketitle
\begin{enumerate}
\item [1.] For each of the following pairs of sets $A, B$, determine whether there are functions from $A$ to $B$ which are one-to-one (injective), onto (surjective), or both (bijective). Do the same with functions from $B$ to $A$.
\vskip 0.2in
{\bf Note:} For each of these cases, there exist plenty of functions $A \rightarrow B$ which are neither injective nor surjective.
\vskip 0.2in
\begin{enumerate}
\item $A=\{1, 2, 3, 4, 5\}$ and $B=\{6, 7, 8, 9\}$.
\vskip 0.2in
{\bf Solution:} There exist plenty of surjective functions $f:A \rightarrow B$ (if you are curious, there are 240 of them). One example is given by $f(1)=6, f(2)=7, f(3)=8, f(4)=9, f(5)=9$. Written as ordered pairs, this is $\{(1, 6), (2, 7), (3, 8), (4, 9), (5, 9)\}$.

There are plenty of injective functions $g:B \rightarrow A$ (if you are curious, there are 120 of them). One example is given by $g(6)=1, g(7)=2, g(8)=3, g(9)=4$. Written as ordered pairs, this is $\{(6,1), (7,2), (8,3), (9,4)\}$.
\vskip 0.2in
\item $A=\mathbb{N}=\{1, 2, 3, \ldots\}$ and $B=\{2n:n\in\mathbb{N}\}=\{2, 4, 6, 8, \ldots\}$.
\vskip 0.2in
{\bf Solution:} There are plenty of bijective functions between these two sets. One such function $f:A \rightarrow B$ is given by $f(1)=2, f(2)=4, f(3)=6, f(4)=8, \ldots,$ and in general $f(n)=2n$ for each $n\in A$.

\vskip 0.2in
\item $A=\mathbb{N}$ and $B=\{a+b\sqrt{2}:a\in\mathbb{N}, b\in\{0, 1, 2\}\}$.
\vskip 0.2in
{\bf Solution:} Again, there are plenty of bijective functions from $A$ to $B$. Here is an example. (I've drawn double-headed arrows to indicate that the function has an inverse.)
$$1\longleftrightarrow 1 \hskip 0.5in 2\longleftrightarrow 1+\sqrt{2} \hskip 0.5in 3\longleftrightarrow 1+2\sqrt{2}$$
$$4\longleftrightarrow 2 \hskip 0.5in 5\longleftrightarrow 2+\sqrt{2} \hskip 0.5in 6\longleftrightarrow 2+2\sqrt{2}$$
$$7\longleftrightarrow 3 \hskip 0.5in 8\longleftrightarrow 3+\sqrt{2} \hskip 0.5in 9\longleftrightarrow 3+2\sqrt{2}$$
$$\vdots$$
\vskip 0.2in
\item $A=\mathbb{N}$ and $B=\mathbb{Z}=\{\ldots, -2, -1, 0, 1, 2, \ldots \}$.
\vskip 0.2in
{\bf Solution:} Again, there is a bijection. Here's a way to reorder the elements of $\mathbb{Z}$ so that this becomes clear
$$\mathbb{Z}=\{\ldots, -2, -1, 0, 1, 2, \ldots\}=\{0, 1, -1, 2, -2, 3, -3, \ldots\}$$
\vskip 0.2in
\item $A=\mathbb{N}$, $B=\{2, 3, 5, 7, 11, \ldots\}$ is the set of prime numbers.
\vskip 0.2in
{\bf Solution:} Even in this case, the two functions are in bijective correspondence. In fact, here is a more general fact.
\begin{theorem}
Let $S$ be any infinite subset of $\mathbb{N}$. Then there is a bijection $f:\mathbb{N} \rightarrow S$.
\end{theorem}
\begin{proof}
Define a sequence of elements $x_1, x_2, x_3, \ldots\in S$ by the property that
$$x_n=\text{the least element of }(S-\{x_1, \ldots, x_{n-1}\})$$
For each $n$, $S-\{x_1, \ldots, x_{n-1}\}$ is a nonempty\footnote{Because $S$ is infinite} subset of $\mathbb{N}$, and so because $\mathbb{N}$ is well-ordered, $S-\{x_1, \ldots, x_{n-1}\}$ has a least element. Thus, $x_n$ is well-defined for each $n$.

This sequence $x_1, x_2, x_3, \ldots$ defines a function $f:\mathbb{N} \rightarrow S$ by the formula $f(n)=x_n$. We claim this function is both injective and surjective, hence bijective.
\begin{itemize}
\item Injectivity: for any two natural numbers $m, n$ with $m<n$, we have $x_m<x_n$ by definition. Hence, the function is injective.
\item Surjectivity: Suppose, for a contradiction, that there is some element $x\in S$ which is not in the image of this function - i.e not equal to any $x_i$. Since $S$ is a subset of $\mathbb{N}$, $x\in\mathbb{N}$. Therefore, there are only finitely many elements of $\mathbb{N}$ which are less than $x$. It follows that there is some $n$ such that $x_n>x$. But this contradicts the definition of $x_n$ as the least element of $S-\{x_1, \ldots, x_{n-1}\}$, because $x$ is an element of $S-\{x_1, \ldots, x_{n-1}\}$. Therefore, we have reached a contradiction, and so no such $x$ exists. Therefore, the function is surjective.
\end{itemize}
\end{proof}
\footnote{It's not true if $S$ is an ordered set in bijection with $\mathbb{N}$, then you can always construct the bijection $\mathbb{N}\rightarrow S$ in the way described above. See \emph{ordinal numbers} if you are curious.}
\end{enumerate}
\vskip 0.2in
\item [2.] Can you come up with a rigorous definition of what it means for a set to have `size $n$'?
\vskip 0.2in
\begin{definition}
A set $S$ has size $n$ if there exists a bijection $\{1, 2, \ldots, n\} \rightarrow S$.
\end{definition}
\vskip 0.2in
\item [3.] What about what it means for a set to be `infinite'?
\vskip 0.2in
\begin{definition}
A set $S$ is infinite if, for every $n\in\mathbb{N}$, there does not exist any bijection $\{1, 2, \ldots, n\} \rightarrow S$.
\end{definition}
\vskip 0.2in
\item [4.] Let $m$ and $n$ be two positive integers such that $m\le n$, and suppose that $S$ is a set and there's an injection $\{1, \ldots, n\} \rightarrow S$. Prove that if there is an injection $S \rightarrow \{1, \ldots, m\}$, then $m=n$.
\vskip 0.2in
\begin{proof}
$n\le |S|\le m$. So $n\le m$ and $m\le n$, which implies $m=n$.
\end{proof}


\vskip 0.2in
\item [5.] Let $S$ be a set and suppose that there is a bijection $f:\mathbb{N} \rightarrow S$. Prove that if $T$ is any infinite subset of $S$, then there is a bijection $S \rightarrow T$.
\vskip 0.2in
\begin{proof}
$f^{-1}$ is a bijection from $S$ to $\mathbb{N}$. We may consider the set $f^{-1}(T)\subset \mathbb{N}$. By the theorem proved in 1(e), there exists a bijective function $g:\mathbb{N}\rightarrow f^{-1}(T)$. Then consider the function $f\circ g \circ f^{-1}: S\rightarrow T$. The following diagram may make it easier to visualize.
$$\xymatrix{\mathbb{N}\ar[d]_{g} & S\ar[l]_{f^{-1}}\ar[d]^{f\circ g\circ f^{-1}}\\
f^{-1}(T)\ar[r]^{f} & T
}$$
It is a composition of three bijections, and therefore it is a bijection.
\end{proof}
%\vskip 1.5in
%\item Come up with sets $A, B, C$ and functions $g, h:A \rightarrow B$ and $f:B \rightarrow C$ such that $f\circ g = f\circ h$ but $g\neq h$.

\end{enumerate}
\end{document}