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

\begin{document}
\pset{8}{March 30, 1999}{Tuesday, April 6}

{\bf Reading assignment}: Rosen sections 4.1-4.3, 5.5-5.6, pages and
76-78, Fall 97 lecture notes 14-15, and Spring 99 lecture notes on 
cardinality.  

%% topics to cover:
%% Infinite Sets
%% Countable vs. Uncountable sets.
%% Sum/Product rules
%% Permutations
%% Inclusion/Exclusion.

\begin{problems}

\problem {\bf (20 Points)}
In this problem we will prove the remarkable fact that
there exist mathematical functions that computers, no matter how powerful,
simply cannot compute.  We will do this through countability arguments.
\bparts
\ppart 

Show that the set of finite length binary strings is countable.

\ppart 

From your answer to the previous part, 
what can you conclude about the countability of the set of all
computer programs?  

\ppart 
Show that set of {\em infinite} length binary strings is uncountable.

\ppart 
A function is a decision function if it maps finite length 
bit strings into the range $\{0,1\}$.       
Let $F$ be the set consisting of {\em all possible} decision functions. 
Show that the set $F$ is uncountable.

\ppart 

A function is computable if there is a computer program that
computes it.  From your answers to the previous parts, 
prove that there are decision functions that are not
computable.  That is, no computer program can compute it.  
(Hint: compare your answer from the second part to the the
answer you just got from the previous part)

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem{\bf (15 points)}

We would like to show that there is a bijection from the unit line $[0,1]$ 
to the unit sphere (all points that have distance exactly one from the 
origin in three dimensional space).  We know that we can do this by giving
two injections.

\bparts

\ppart (5 points) 
Show that there is an injection from the unit line to the unit sphere.

\ppart (10 points) 
Show that there is an injection from the unit sphere to the unit line.

\ppart (Extra Credit) Give a bijection from the unit
line to the unit sphere.

\eparts  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (15 Points)}

Recall from lecture that if $A_1, \ldots, A_k$ is a collection of
{\em finite} sets, then the product $A_1 \times A_2 \times \cdots
\times A_k$ is finite, and hence countable. In this problem we consider
what happens if you take a product $A_1 \times  A_2 \times A_3 \cdots$ of 
an infinite collection of finite sets.  {\em Assume that none of the
sets is empty.}

\bparts 

\ppart
Under what conditions (if there are any) is the product 
$A_1 \times  A_2 \times A_3 \cdots$ finite?  That is, for what kinds
of sets $A_1, A_2, \ldots$ is the product finite.  Please justify your
answer.


\ppart
Under what conditons (if there are any) is the product 
$A_1 \times  A_2 \times A_3 \cdots$ infinite, but countable?  
That is, for what kinds
of sets $A_1, A_2, \ldots$ is the product countably infinite?  
Please justify your answer.

\ppart
Under what conditons (if there are any) is the product 
$A_1 \times  A_2 \times A_3 \cdots$ uncountable?  
That is, for what kinds
of sets $A_1, A_2, \ldots$ is the product uncountable?  
Please justify your answer.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem {\bf (10 Points)}

Consider the set of finite directed acyclic graphs no two of which
are isomorphic to each other.  Here finite means that there are a
finite number of vertices.  Show that this set is countable. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\problem {\bf (15 Points)}

Denote by $\{0,1\}^n$ the set of all bit strings of length $n$.

\bparts

\ppart

How many functions are there with domain $\{0,1\}^m$ and range
$\{0,1\}^n$?

\ppart

How many functions with domain and range $\{0,1\}^n$ 
are {\em not permutations}?

\ppart

A value $x$ is called a {\em fixed point} of a function $f$ if
$f(x) = x$.  
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em no} 
fixed points?

\ppart 
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em at least one} 
fixed point?

\ppart
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em exactly one} 
fixed point?

\ppart 
How many functions from $\{0,1\}^n$ to $\{0,1\}^n$ have {\em at least two} 
fixed points?

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem{\bf (15 points)}

Compute the number of 0's at the right hand end of the decimal 
representation of $100!$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem {\bf (10 Points)}

Using the principle of inclusion-exclusion, show that there are fewer than 
50,000 prime numbers less than or equal to 210,000.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{problems}

\end{document}




