\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 20 Questions}
\begin{document}
\maketitle
\begin{enumerate}
\item [1.]
\begin{enumerate}
\item Let $\mathbb{Q}^+$ denote the set of positive rational numbers. Prove that there exists a surjective function $\mathbb{N}\times \mathbb{N} \rightarrow \mathbb{Q}^+$.
\vskip 0.2in
{\bf Solution:} There's such a function $f:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{Q}^+$ given by
$$f((a,b))=a/b$$
It is surjective because every positive rational number can be written as a fraction with positive numerator and denominator.
\vskip 0.2in
\item Deduce that there exists a surjective function $\mathbb{Z}\times \mathbb{N}\rightarrow \mathbb{Q}$.
\vskip 0.2in
{\bf Solution:} One can again define a function $f:\mathbb{Z}\times\mathbb{N}\rightarrow\mathbb{Q}$ by $f((a,b))=a/b$. It is well-defined as $b\neq 0$. It is surjective because every rational number can be written as a fraction (with top and bottom both integers) with positive denominator.
\vskip 0.2in
\item Show that there is an injective function $\mathbb{Q}\rightarrow \mathbb{Z}\times \mathbb{N}$.
\vskip 0.2in
{\bf Solution:} Any rational number $q$ can be written \emph{uniquely} in the form $q=\frac{a}{b}$ where $b>0$ and $a, b$ have no common factors. Because this is unique, we get a function $\mathbb{Q}\rightarrow \mathbb{Z}\times \mathbb{N}$. The function is clearly injective because two different rational numbers can't be given by the same fraction.
\vskip 0.2in
\end{enumerate}

\item [2.] For any integer $k$, let $k^{\mathbb{N}}$ denote the set of functions $\mathbb{N} \rightarrow \{1, 2, \ldots, k\}$. We'll prove in class today that $2^{\mathbb{N}}$ is \emph{uncountable}.
\begin{enumerate}
\item Explain why there is a bijection between $2^{\mathbb{N}}$ and $\mathcal{P}(N)$, the \emph{power set} of $\mathbb{N}$.
\vskip 0.2in
{\bf Solution:} Consider the function $\theta:2^{\mathbb{N}}\rightarrow\mathcal{P}(\mathbb{N})$ given as follows. Suppose that $f\in 2^{\mathbb{N}}$. Then $f^{-1}(1)$ is a subset of $\mathbb{N}$, and we let $\theta(f)=f^{-1}(1)$.

In the other direction, consider the function $\varphi:\mathcal{P}(\mathbb{N})\rightarrow 2^{\mathcal{N}}$ given as follows. Suppose that $S\in\mathcal{P}(\mathbb{N})$. Then one may define a function $\varphi(S);\mathcal{N}\rightarrow \{1,2\}$ by
$$(\varphi(S))(n)=\begin{cases}
1\hskip 0.2in n\in S\\
2\hskip 0.2in n\notin S
\end{cases}$$
Let $\varphi(S)$ be this function.

We have defined functions $\theta:2^{\mathbb{N}}\rightarrow\mathcal{P}(\mathbb{N})$ and $\varphi:\mathcal{P}(\mathbb{N})\rightarrow 2^{\mathcal{N}}$. We will now show they are inverse functions. First, we show that $\varphi(\theta(f))=f$ for any $f\in 2^{\mathbb{N}}$. For any $n\in\mathbb{N}$,
$$(\varphi(\theta(f)))(n)=\begin{cases}
1\hskip 0.2in n\in f^{-1}(1)\\
2\hskip 0.2in n\notin f^{-1}(1)
\end{cases}$$
It is clear that the function $\varphi(\theta(f))$ is equal to $f$. Now we check that $\theta(\varphi(S))=S$. $\theta(\varphi(S))=\varphi(S)^{-1}(1)$ which equals $S$ by the definition of $\varphi$. Thus, $\theta(\varphi(S))=S$ as desired.
\vskip 0.2in
\item Show that there is a surjective function $10^{\mathbb{N}} \rightarrow [0,1]$, where $[0,1]$ is the interval of real numbers $x$ such that $0\le x\le 1$.
\vskip 0.2in
{\bf Solution:} We'll instead consider functions from $\mathbb{N}$ to the set $\{0, 1, 2, \ldots, 9\}$, as that set is bijective with $10^{\mathbb{N}}$. Consider the function which sends a function
$$f:\mathbb{N}\rightarrow \{0, 1, 2, \ldots, 9\}$$
to the sum $\sum\limits_{n=1}^{\infty}\frac{f(n)}{10^n}$. In other words, it sends the function $f(-)$ to the decimal number
$$f(-)\mapsto 0.f(1)f(2)f(3)f(4)\ldots$$
This function is surjective because every real number in $[0,1]$ has a decimal representation of this form (for the number 1, note that 1=0.999...).
\vskip 0.2in
\item Show that, for any positive integer $k$, there is a surjective function $k^{\mathbb{N}} \rightarrow [0,1]$.
\vskip 0.2in
{\bf Solution:} Do the same thing but base $k$ instead of base 10.
$$f(-)\mapsto \sum\limits_{n=1}^{\infty}\frac{f(n)}{k^n}$$
\vskip 0.2in
\end{enumerate}
\item [3.] Let $S \subset \mathcal{P}(\mathbb{N})$ be the set of \emph{finite} subsets of $\mathbb{N}$. Prove that $S$ is denumerable.
{\bf Solution 1:}
\begin{lemma}
Let $A_1, A_2, A_3, \ldots$ be a sequence of disjoint, denumerable sets. Then $A_1\cup A_2\cup A_3\cup \cdots$ is denumerable.
\end{lemma}
\begin{proof} [Proof of Lemma]
The assumption is that there is a bijection $f_n:\mathbb{N}\rightarrow A_n$ for every $n\in\mathbb{N}$. Then there is a bijection
$$\mathbb{N}\times\mathbb{N}\rightarrow \bigcup\limits_{n=1}^{\infty}A_n$$
which maps $\{n\}\times \mathbb{N}$ bijectively to $A_n$. Compose this with the bijection\footnote{We constructed this in a previous class, but for completeness I will describe it here. The inverse bijection $f:\mathbb{N}\times\mathbb{N}\rightarrow \mathbb{N}$ is given by
$$f((i,j))=\frac{(i+j)(i+j+1)}{2}-i+1$$
Another possible bijection $g:\mathbb{N}\times \mathbb{N}\rightarrow \mathbb{N}$ is by the formula
$$g((i,j))=2^{i-1}(2j-1)$$} $\mathbb{N}\rightarrow \mathbb{N}\times\mathbb{N}$ and we obtain a bijection $\mathbb{N}\rightarrow \bigcup\limits_{n=1}^{\infty}A_n$.
\end{proof}
\begin{lemma}
Let $S_1, S_2, S_3, \ldots$ be a sequence of nonempty, disjoint, finite sets. Then $S_1\cup S_2\cup S_3\cup \cdots$ is denumerable.
\end{lemma}
\begin{proof}
Let $a_n$ be the size of set $S_n$ for each $n$. Then we can form bijections
$$\{1, 2, \ldots, a_1\} \rightarrow S_1$$
$$\{a_1+1, a_1+2, \ldots, a_1+a_2\}\rightarrow S_2$$
$$\{a_1+a_2+1, a_1+a_2+2, \ldots, a_1+a_2+a_3\}\rightarrow S_3$$
$$\vdots$$
Putting these together gives a bijection from $\mathbb{N}$ to $S_1\cup S_2\cup S_3\cup \cdots$.
\end{proof}
\begin{proof} [Proof of Question 3]
For each $n$, let $A_n$ denote the set of $n$-element subsets of $\mathbb{N}$. By the first Lemma, it suffices to show that, for any $n$, $A_n$ is denumerable.
\vskip 0.2in
For every natural number $m\ge n$, let $B_m$ be the set of $n$-element subsets of $\mathbb{N}$ with largest element equal to $m$. So for example, $B_n$ consists of a single element, $B_{n+1}$ consists of $n+1$ elements, and so on. Then $A_n$ is the disjoint union of $B_n, B_{n+1}, B_{n+2}, \ldots$ and each $B_m$ is finite and nonempty. By the second Lemma, it follows that $A_n$ is denumerable, as desired.
\end{proof}
\vskip 0.2in
{\bf Solution 2:} There is a function
$$f:S\rightarrow \mathbb{Q}$$
which is given by $f(S)=\sum\limits_{n\in S}\frac{1}{10^n}$. This is easily seen to be an injective function, because no rational number has two different finite-length decimal representations. Thus, $|S|\le |\mathbb{Q}|$. Since $\mathbb{Q}$ is denumerable, and $S$ is an infinite set, $S$ is also denumerable.
\end{enumerate}
\end{document}