\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\homework{5: More Cardinality}{Due Friday, Week 3}

Do \textbf{three} of the \textbf{six} problems below!

\begin{enumerate}
\item A real number $r$ is called \textbf{algebraic} if and only if there is some degree $n$ and integer constants $a_0, \ldots a_n$ such that $r$ is a root\footnote{A \textbf{root} of a polynomial is a number you can plug into that polynomial and get 0.  For example, 2 is a root of the polynomial $x^2 - 4$, because plugging in $2$ for $x$ yields 0.} of the following polynomial:
\begin{align*}
a+0 + a_1x + \ldots + a_nx^n.
\end{align*} 
Most numbers you know are algebraic: for example, all of $\mathbb{Q}$ is (they're roots of the polynomial $qx - p$), as is $\sqrt{2}$ (it's a root of $x^2 - 2$).

Prove or disprove the following statement: $\mathbb{N}$ has the same cardinality (size) as $\mathcal{A}$, the collection of all algebraic numbers.

\item Define the \textbf{Cantor set} $\mathcal{C}$ as follows:
\begin{itemize}
\item Start with the interval $[0,1]$. Call this set $C_0$.
\item Remove the middle-third of this set, so that you have $[0, 1/3]$ and $[2/3, 1]$ left over.  Call this set $C_1$.
\item Remove the middle-third of those two sets, so that you have $[0, 1/9], [2/9, 1/3], [2/3, 7/9], [8/9, 1]$ left over.  Call this set $C_2$.
\item Repeat this process!
\end{itemize}
Define $\mathcal{C},$ the Cantor set, as the set made by taking all of the elements $x$ such that $x$ is in $C_i$, for every $i$.
\begin{enumerate}
\item Find an element in $\mathcal{C}$.
\item Show that $\mathcal{C}$ contains infinitely many elements.
\item Can you make a bijection between $\mathcal{C}$ and $[0,1]$?
\end{enumerate}
\item  Let $X$ denote the set made out of all possible sequences of natural numbers with finite length: i.e. for every element $x$ of $X$, there is some length $k$ such that $x$ looks like some string $(n_0, n_1, \ldots n_k)$, where the $n_1\ldots n_k$'s are all natural numbers.  Is this set the same cardinality as $\mathbb{N}$? 
\item  Let $Y$ denote the set made out of all possible sequences of natural numbers of infinite length: i.e. for every element $y$ of $Y$, $y$ looks like some string $(n_0, n_1, \ldots)$, where the elements $n_i$ are natural numbers.  Is this set the same cardinality as $\mathbb{N}$?
\item We say that a set is \textbf{countably infinite} if there is a bijection from that set to $\mathbb{N}$.  Suppose that $A_1, A_2, A_3, \ldots $ is a sequence of countably infinite sets.  Define
\begin{align*}
B = A_1\cup A_2 \cup A_3\cup \ldots = \bigcup_{n=1}^\infty A_n.
\end{align*}
Show that $|B| = |\mathbb{N}|$.
\item Given sets $A,B,C$ and functions $f: A \to B, g: B\to C$, form the function $h = g \circ f : A \to C$.  In other words, $h$ is the function from $A$ to $C$ defined by $h(a) = g(f(a))$.

For each of the following claims, provide a proof or a disproof:
\begin{enumerate}
\item If $h$ is injective, then $f$ is injective.
\item If $h$ is injective, then $g$ is injective.
\item If $h$ is surjective, then $f$ is surjective.
\item If $h$ is surjective, then $g$ is surjective.
\end{enumerate}
\end{enumerate}
\end{document}