\documentclass[11pt,onecolumn,fleqn]{article}

\usepackage[latin1]{inputenc}
\usepackage{bbm}
\usepackage{enumerate}
\usepackage[hang,flushmargin]{footmisc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{stmaryrd}
\usepackage{xcolor}
\usepackage{pdflscape}
\usepackage{tikz-cd}
\usepackage{hyperref}

\usepackage{bussproofs}
\newcommand{\TagC}[1]{\RightLabel{\scriptsize #1}}

\theoremstyle{definition}
\newtheorem*{theorem}{Theorem}
\newtheorem*{lemma}{Lemma}
\newtheorem*{corollary}{Corollary}
\newtheorem*{proposition}{Proposition}
\newtheorem*{definition}{Definition}
\newtheorem*{example}{Example}

\setlength{\oddsidemargin}{0px}
\setlength{\textwidth}{460px}
\setlength{\voffset}{-1.5cm}
\setlength{\textheight}{20cm}
\setlength{\parindent}{0px}
\setlength{\parskip}{10pt}

\newcommand{\TT}{$\checkmark$}
\newcommand{\FF}{$\times$}

\newcommand{\points}[1]{\hfill {\bf \color{darkgray} [#1 points]}}
\newcommand{\onepoint}{\hfill {\bf \color{darkgray} [1 point]}}
\newcommand{\pointseach}[1]{\hfill {\bf \color{darkgray} [#1 points each]}}

\DeclareMathOperator{\circhat}{\widehat{\circ}}

\begin{document}
\thispagestyle{empty}
\begin{center}
{\Huge
15-151 Homework 10
}

Please submit in class at 8:00am on Wednesday 9th August

\textit{If you want feedback on your completed project background section, then\\
you must submit it in class at 8:00am on Tuesday 8th August}
\end{center}

\subsection*{Exercises}

\begin{enumerate}[1.]
\item The goal of this question is to prove that the cartesian proudct of two countably infinite sets is countably infinite.
\begin{enumerate}[(a)]
\item Prove that the function $e : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ defined by
$$e(m,n) = 2^m(2n+1)-1 \text{ for all } (m,n) \in \mathbb{N} \times \mathbb{N}$$
is a bijection.
\points{4}

\item Explain why part (a) implies that $\mathbb{N} \times \mathbb{N}$ is countably infinite.
\onepoint

\item Suppose $X$ and $Y$ are countably infinite sets, and let $f : \mathbb{N} \to X$ and $g : \mathbb{N} \to Y$ be bijections. Define a new function $f \times g : \mathbb{N} \times \mathbb{N} \to X \times Y$ by
$$(f \times g)(m,n) = (f(m),g(n)) \text{ for all } (m,n) \in \mathbb{N} \times \mathbb{N}$$
Prove that $f \times g$ is a bijection.
\points{5}

\item With sets and functions as defined in (a) and (c), find a bijection $\mathbb{N} \to X \times Y$ expressed in terms of the functions $e$, $f$ and $g$.
\points{3}

\item Prove that $\mathbb{Z} \times \mathbb{Z}$ is countably infinite.
\points{2}
\end{enumerate}

\item Let $X$ be the set of all infinite sequences of $0$s and $1$s, i.e.
$$X = \{ (a_0, a_1, a_2, \dots) \mid a_k \in \{ 0,1 \} \text{ for all } k \in \mathbb{N} \}$$
Prove that $X$ is uncountably infinite.
\points{10}
\end{enumerate}

\vfill

\textit{This assignment is continued on the next page.}

\newpage
\subsection*{Project milestones}

{\color{red} Please submit your work for the project milestone separately from your homework.}

\begin{itemize} \vspace{-10pt}
\item \textit{(Optional but recommended.)} Write a list of the definitions and preliminary results that you intend to include in your project's background section. If you want to receive feedback on this, you should upload the list to the `Course project background summary' assignment on Canvas by 6:00pm on Saturday 5th August.

\item Write the background and main result sections of your project.
\points{10}
\end{itemize}

\textit{If you want feedback on your background and/or main result sections, you should hand this work in during class on Tuesday 8th August.}

\subsection*{Optional problems}

You do not need to attempt these problems. If you do, then your score out of $35$ on these questions (plus the two optional problems from Homework 9) will replace your lowest homework score from Homeworks 1 through 8.

\begin{enumerate}[Opt 1.] \vspace{-10pt}
\setcounter{enumi}{2}
\item Let $n,k \in \mathbb{N}$. Find and prove an expression for the number of injective functions $[n] \to [k]$.

\points{7}

\item Find a bijection $f : [0,1) \to (0,1)$, where

$ $ \hfill $[0,1) = \{ x \in \mathbb{R} \mid 0 \le x < 1 \} \quad \text{and} \quad (0,1) = \{ x \in \mathbb{R} \mid 0 < x < 1 \}$ \points{7}

\item Find a partition of $\mathbb{N}$ into countably many countably infinite sets. (That is, find a collection $X_0, X_1, X_2, X_3, \dots$ of subsets of $\mathbb{N}$ which are all countably infinite, are pairwise disjoint, and such that every natural number is an element of $X_n$ for some $n \in \mathbb{N}$.)
\points{7}
\end{enumerate}

\end{document}