\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{3: Problems on Proof Techniques/Sizes of Sets}{Due Friday, Week 2}

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

\begin{enumerate}

\item  Find the flaw\footnote{Note: a flaw is not noticing that the conclusion is wrong.  Rather, a flaw is finding some way in which the proof \textbf{methods} or \textbf{logic} fails here.  In other words: as mathematicians, we want to believe that anything that we \textbf{prove} is \textbf{true}!  So, if someone comes up with a claimed ``proof'' of something we know is false, we really want to find a flaw in their proof!} in the following proof:
\begin{thm}
On a certain island, there are $n\geq 2$ cities, some of which are connected by roads. If each city is connected by a road to at least one other city, then you can travel from any city to any other city along the roads.
\end{thm}
\begin{proof}
We proceed by induction on $n$. 

Base case: The claim is clearly true for $n=1, 2$.

Inductive step: Suppose the claim is true for an island with $n=k$ cities. To prove that it's also true for $n=k+1$, we add another city to this island. This new city is connected by a road to at least one of the old cities, from which you can get to any other old city by the inductive hypothesis. Thus you can travel from the new city to any other city, as well as between any two of the old cities. This proves that the claim holds for $n=k+1$, so by induction it holds for all $n$.
\end{proof}

\item Suppose that $f: \mathbb{N} \to \mathbb{N}$ is a strictly increasing\footnote{A function $f$ is called \textbf{strictly increasing} if for any pair $x,y$ of possible inputs to $f$, we have $x<y\ \Rightarrow f(x) < f(y)$.} function with the following two properties:
\begin{itemize}
\item $f(2) = 2$.
\item $f(mn) = f(m) \cdot f(n)$.
\end{itemize}

Prove that $f(n) = n$ for every $n \in \mathbb{N}$.

\item Pick out twenty distinct numbers from the set
\begin{align*}
\{1, 4, 7, 10, 13, 16, 19, \ldots, 97, 100\}.
\end{align*}
Prove that no matter how you make those choices, you will have chosen two numbers whose sum is 104.

\item Pick any set of $n+1$ distinct numbers from the set $[2n] = \{1,2,3,\ldots 2n\}$.  Prove that no matter how you make those choices, you have chosen two numbers that are relatively prime.

\item    Let $A, B, C$ be a triple of sets, $f: A \to B$ an injective function, and $g: B \to C$ another injective function.  Prove that $g \circ f$, the function that takes in any element $a \in A$ and outputs the result $g(f(a)) \in C$, is an injective function.

\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}$?  
\end{enumerate}
\end{document}