\documentstyle[12pt,twoside,amsfonts,amstex]{article}
\input{macros-course-tutorials}

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial6}{Problems for Tutorial 6}{March 17, 1997}

\section{Warmups}
\bparts
\ppart Determine whether each of the following functions, 
$f : \reals \rightarrow \reals$, is an injection, surjection or a bijection.
Also, give the inverse if it exists.
\begin{itemize}
\item $f(x)=e^x$
\item $f(x)=x^2+3$
\item $f(x)=(x^2+1)/(x^2+2)$
\end{itemize}
\ppart What is the only function on a set $A$ that is also an equivalence 
relation?
\eparts


\section {Seven Pigeons}

\noindent Let $S$ be the set of numbers $7, 77, 777, \ldots$. Prove that there
is an element of $S$ that is divisible by $1997$.

\section {Uncomputable Functions}

\noindent A computable function from the naturals to the naturals is a finite 
piece of code (in your favourite programming language). 
The code takes as input a natural
number and outputs a natural number. Prove that not all functions $f$
from the naturals to the naturals are computable.\\ 

\section{The Power of Power Sets}
Let $G$ be the set of all functions $f: \naturals \rightarrow \{0,1 \}$.

\bparts

\ppart Prove that $|G| = |2^{\naturals}|$.  
\ppart Let $U$ be an uncountable set and $C$ any countable subset of $U$.
Prove that $U-C$ is uncountable.
\ppart Prove that $|2^{\naturals}| = |(0,1)|$ and conclude that
$|2^{\naturals}| = |\reals|$.

\eparts   
\end{document}
