\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 22 Questions}
\begin{document}
\maketitle
\begin{enumerate}
\item [1.] Let $A$ and $B$ be sets, and suppose there is an injective function $f:A \rightarrow B$. Can you construct a surjective function $g:B \rightarrow A$?
\vskip 0.2in
{\bf Solution:} Yes we can, so long as $A$ is nonempty. Pick some fixed element $x$ in $A$. The fact that $f:A \rightarrow B$ is injective means that for every $b\in B$, there is at most one $a\in A$ such that $f(a)=b$. Then we can construct a surjective function $g:B \rightarrow A$ defined by the property that
\begin{itemize}
\item If $b\in \text{im}(f)$, then let $g(b)$ be the unique element such that $f(g(b))=b$.
\item If $b\notin \text{im}(f)$, then let $g(b)=x$.
\end{itemize}
Note that this construction wouldn't work if $A$ were empty. For example, if $A=\emptyset$ and $B=\{1, 2, 3\}$, then there are $3^0=1$ functions from $A$ to $B$, and $0^3=0$ functions from $B$ to $A$.
\vskip 0.2in
\item [2.] Let $A$ and $B$ be sets, and suppose there is a surjective function $g:B\rightarrow A$. Can you construct an injective function $f:A \rightarrow B$?
\vskip 0.2in
{\bf Solution:} Yes you can, but doing so requires the \emph{Axiom of Choice}. The fact that $g:A \rightarrow B$ is surjective means that for every $b\in B$, there is at least one $a\in A$ such that $g(a)=b$. So for each $b\in B$, choose\footnote{This is the step which requires the Axiom of Choice.} some element $a\in g^{-1}(b)$ and declare that $f(b)$ is equal to that $a$. The result is an injective function, because $f(b)$ satisfies the property that $g(f(b))=b$ - therefore if $f(b)=f(b')$ then $g(f(b))=g(f(b'))$ which means $b=b'$.
\vskip 0.2in
\item [3.] Prove that
$$|2^{\mathbb{N}}|=|2^{\mathbb{N}}\times 2^{\mathbb{N}}|$$
by finding an explicit bijection. (Remember that $2^A$ is the set of functions from $A$ to $\{0,1\}$.)
\vskip 0.2in
\begin{proof}
In this proof, `function' will be used to mean a function $\mathbb{N}\rightarrow\{0,1\}$. Given any function $f$, define functions $f_{\mathrm{odd}}$ and $f_{\mathrm{even}}$ by
$$f_{\mathrm{odd}}(n)=f(2n-1) \hskip 1in f_{\mathrm{even}}(n)=f(2n)$$
Then we have
$$H: 2^{\mathbb{N}}\rightarrow 2^{\mathbb{N}}\times 2^{\mathbb{N}}$$
$$f\mapsto (f_{\mathrm{odd}}, f_{\mathrm{even}})$$
If $f$ and $g$ are functions such that $(f_{\mathrm{odd}}, f_{\mathrm{even}})=(g_{\mathrm{odd}}, g_{\mathrm{even}})$, then $f(2n-1)=g(2n-1)$ for every $n$ and $f(2n)=g(2n)$ for every $n$. It then follows that $f=g$. Thus, $H$ is injective.

If $(f, g)$ is any pair of functions, then one may consider the function $h$ defined by
$$h(n)=\begin{cases}f\left(\frac{n+1}{2}\right) \hskip 0.2in n \hskip 0.1in \mathrm{ odd}\\
g\left(\frac{n}{2}\right) \hskip 0.2in n \hskip 0.1in \mathrm{ even}
\end{cases}$$
and one sees that $h_{\mathrm{odd}}=f$ and $h_{\mathrm{even}}=g$, i.e. $H(h)=(f,g)$. Thus, $H$ is surjective.
\end{proof}
{\bf Note:} A corollary of this fact is that $|\mathbb{R}|=|\mathbb{R}\times\mathbb{R}|$.
\vskip 0.2in
\item [4.] Let $A, B,$ and $C$ be any three sets, and let $A, B$ be disjoint. Prove that $|C^{A\cup B}|=|C^A\times C^B|$, or written another way,
$$|\mathrm{Fun}(A\cup B, C)|=|\mathrm{Fun}(A, C)\times \mathrm{Fun}(B, C)|$$
\vskip 0.2in
\begin{proof}Given a function $f:A\cup B\rightarrow C$, one obtains functions $f_A:A \rightarrow C$ and $f_B:B\rightarrow C$ by restricting the action of $f$. Thus, we have
$$\Phi: \mathrm{Fun}(A\cup B, C)\rightarrow \mathrm{Fun}(A, C)\times \mathrm{Fun}(B, C)$$
$$f\mapsto (f_A, f_B)$$
Similarly, if one has functions $g:A\rightarrow C$ and $h:B\rightarrow C$, one obtains a function $g\cup h:A\cup B\rightarrow C$ defined by
$$(g\cup h)(x)=\begin{cases}g(x) \hskip 0.2in x\in A\\
h(x) \hskip 0.2in x\in B
\end{cases}$$
Thus, we have
$$\Theta: \mathrm{Fun}(A, C)\times \mathrm{Fun}(B, C)\rightarrow \mathrm{Fun}(A\cup B, C)$$
$$(g,h)\mapsto g\cup h$$
It's easy to check that $\Theta$ and $\Phi$ are inverses of one another, and so both are bijections.
\end{proof}
\vskip 0.2in
\item [5.] (More challenging) Prove that $|C^{A\times B}|=|(C^A)^B|$, or written another way,
$$|\mathrm{Fun}(A\times B, C)|=|\mathrm{Fun}(B, \mathrm{Fun}(A,C))|$$
\vskip 0.2in
\begin{proof}
First, here's a function
$$\Phi:\mathrm{Fun}(B, \mathrm{Fun}(A,C))\rightarrow \mathrm{Fun}(A\times B, C)$$
Suppose that we have a function $f:B\rightarrow \mathrm{Fun}(A,C)$. Then one obtains a function $\Phi(f):A\times B \rightarrow C$ by
$$\Phi(f)(a,b)=(f(b))(a)$$
Next, here's a function
$$\Theta:\mathrm{Fun}(A\times B, C)\rightarrow \mathrm{Fun}(B, \mathrm{Fun}(A,C))$$
Suppose that we have a function $g:A\times B\rightarrow C$. Then we obtain a function $\Theta(g):B \rightarrow \mathrm{Fun}(A,C)$ by
$$(\Theta(g)(b))(a)=g(a,b)$$
It's fairly easy to check that $\Phi$ and $\Theta$ are inverses of one another.
\end{proof}
\end{enumerate}
\end{document}