\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{multicol}
\usepackage{amsmath}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage[table]{xcolor}
\usepackage[all,arc]{xy}
\usepackage{color, colortbl}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.15in}
\setlength{\evensidemargin}{.15in}
\setlength{\textwidth}{6.2in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.6in}


\input{preamble.tex}

\begin{document}

\homework{1: Sizes of Infinity}{Due Tuesday, week 2, at the start of class}


\section*{Checkdown problem.}
\begin{enumerate}
\item In class, we defined what it means for a function from $\mathbb{N} \to \mathbb{N}$ to be injective.  
\begin{enumerate}
\item Create two distinct functions $f, g: \mathbb{N} \to \mathbb{N}$, that are both injective.  Create a third function $h: \mathbb{N} \to \mathbb{N}$ that is not injective.
\item Given two functions $f, g$, we can form their \textbf{composition}, $f \circ g$, as the function formed by first applying $g$ and then $f$ to any input.  For example, if $g(x) = x^2$ and $f(x) = x+1$, the function $f\circ g(x)$ is just $x^2 + 1$.

Take the three functions $f, g, h$ that you created in part $a$.  Is the composition $f \circ g$ an injective function?  How about $f \circ h$?
\end{enumerate}
\end{enumerate}

\section*{Extra-credit problems.}

\begin{enumerate}
 \setcounter{enumi}{1}
\item Can there ever be more words than numbers?

Specifically: let's suppose that we're limiting ourselves to the 26-character Latin alphabet, and that the only kinds of things that can be \textbf{words} are finite strings of characters from the Latin alphabet.  So things like
\begin{multicols}{2}
\begin{itemize}
\item rabbit
\item barglearglesnarg
\item ssss
\item froyo
\end{itemize}
\end{multicols}
are all possibly words.  Call the set of all possible words $\mathbb{W}$.  Is the set $\mathbb{W}$ the same cardinality as $\mathbb{N}$?   Prove your claim.
\end{enumerate}

\end{document}