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

\parskip1.5ex
\parindent0pt

\begin{document}

\tutorial{tutorial6}{Problems Solutions 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

Recall that a function is an injection if $f(x) = f(y) \rightarrow x=y$
and a surjection if $ \forall y \in \reals \exists x (fx)=y$.
A function is a bijection if it is a surjection and an injection and the
inverse only exists if it's a bijection.

\bparts
\ppart 

\begin{itemize}
\item $f(x)=e^x$

injection? yes 
if $ e^x = e^y \rightarrow \ln e^x = \ln e^y \rightarrow x=y$

surjection?  No because $e^x$ is never negative.

bijection? no.

No inverse

\item $f(x)=x^2+3$
injection? no because $f(x) = f(-x) $ even though $x \neq -x$


surjection?  No because $x^2+3$ is never negative.

bijection? no.

No inverse.

\item $f(x)=(x^2+1)/(x^2+2)$

injection? no because $f(x) = f(-x) $ even though $x \neq -x$

surjection?  No because $(x^2+1)/(x^2+2)$ is never negative.

bijection? no.

No inverse.

\end{itemize}

\ppart

$f(x) = x$

To show a function is an equivalence relation, we need to show that it's 
reflexive, symmetric, and transitive.  Pairs in this relation are $(x, f(x)) \in R$.

$R$ is reflexive because 
$(x, f(x)) \in R \rightarrow (x,x) \in R $.


$R$ is symmetric because 
$(x, f(x)) \in R \rightarrow (x, x) \in R \rightarrow (f(x), x) \in R$

$R$ is transitive because 
\begin{eqnarray*}
(x, f(x)) \in R \wedge (f(x), f(f(x))) \in R &\\
\rightarrow &(x, x) \in R \wedge (x, f(x)) \in R \\
\rightarrow &(x, x) \in R \wedge (x, x) \in R \\
\rightarrow &(x, x) \in R \\
\rightarrow &(f(x), x) \in R \\
 \rightarrow &(f(f(x)), f(x)) \in R \\
\end{eqnarray*}


\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$.

Let the pigeons be elements $s \mod 1997$ where $s \in S$, and 
the holes be the numbers $0 \ldots 1996$.  


Since there are more than 1997 elements of $S$, some hoel must have two numbers,
say $s_i$ and $s_j$, with $i$ and $j$ 7's respectively.  Without loss of
generality, assume that $i<j$.

$s_j - s_i = 77 \ldots 700\ldots0$ where there are $j-i$ 7's and $i$ 0's.
So, $s_j - s_i = s_{j-i} \cdot 10^i$.  


Since $s_j \mod 1997 = r = s_i \mod 1997$, 
$s_j - s_i \mod 1997 = 0$, so $1997 \mid (s_j - s_i)$.  Since $1997 $ doesn't
divide $10^i$, it must divide $s_{j-i}$, so $1997 \mid s_{j-i}$.. 

\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.\\ 

Recall that a function is a relation which is a set of ordered pairs.  Normally
when we think of functions, we think of things like $f(x) = x^2$ which have
a pattern to the pairs, but we  could just as easily randomly assign $f(i)$ 
for
each $(i, f(i))$.  In order to do this, we'd have to explicitly enumerate 
the pairs. Since there are an infinite number of natural numbers,
would require infinite space.

\section{The Power of Power Sets}

{ \bf Solutions to this will be available later (I'll mail people to 
let you know when they're done.) }

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

\begin{problemparts}

\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|$.
\end{problemparts}

\end{document}
