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

{\bf Solution: } 
Let $B_n$ denote the set of binary strings of length $n$.
This set has exactly $2^n$ elements.  So can list all finite binary
strings by first listing the elements of $B_1$, then the elements of
$B_2$, then the elements of $B_3$, etc,.  We can do this since each
set $B_i$ has a finite number of elements. 

\ppart 

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

{\bf Solution: }
Since every computer program can be represented as a finite string of
bits (e.g. machine language code), it follows that the set of all
computer programs is countable.

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

{\bf Solution: }
We construct a bijection from set of infinite length binary strings to the
power set of the natural numbers.  Since the power set of the natural numbers
is uncountable, it will then follow that the set of all infinite length
binary strings is uncountable.  

\medskip

We need to associate a subset of the naturals with each infinite length
binary string.  Let $b=b_0 b_1 b_2 b_3\ldots $ be an infinite length binary
string (here each $b_i \in \{0,1\}$).  We associate with this string the
set $S = \{ i \ | \ b_i = 1 \}$.  That, is if the $i$-th bit position (from
the left) of the bit string is a 1, then we include $i$ in our subset.  
Now, if two infinite 
length binary strings are different, then clearly they map to different
subsets.  Moreover, for every subset of the naturals, we can associate a 
corresponding binary string.    

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

{\bf Solution: }
From part a, we know that there is a bijection from the set of all finite
length bit strings to the set of natural numbers, hence we can think of
decision functions as mapping natural numbers to single bits.  Now, we
give a bijection between the set of all decision functions and the set of
all infinite length bit strings, which by part c, implies that the set of
decision functions is uncountable.  

\medskip

Let $f$ be a decision function.  We map $f$ to an infinite length 
string as follows.  We set bit $i$ of the string to be $f(i)$.  That
is, our infinite length bit string will be $f(1) f(2) f(3) \ldots $.
Now, observe that this mapping is a bijection.  In particular, suppose 
we have two different decision functions $f$ and $g$.  Since they are
different, they must give a different output on some particular input.
Suppose that this particular input is the number $j$.  That is,
$f(j) \neq g(j)$.  Then, the corresponding infinite length binary strings
will differ in the $j-th$ position.  This shows that the function is
injective.  Now, if we have an infinite length bit string 
$b_0 b_1 b_2 \ldots$, then we can map it to the decision function $f$ 
defined as: $f(0) = b_0, f(1) = b_1, f(2) = b_2, \ldots$.  Therefore,
the mapping function is surjective.  Since it's injective and surjective,
it must be bijective.

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

{\bf Solution: } Since there are only countably many computer programs,
but uncountably many decision functions, there are more decision functions
than computer programs.  Hence there must be some decision function which
cannot be computed by a computer program.

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

{\bf Solution: }
Suppose that a finite number of these have more than one element, 
and the remaining number have one element.  Then, the product will 
be finite.  This holds because we know that: 
\[ |A_1 \times A_2 \times \cdots| = |A_1| \times |A_2| \times \cdots \]
Therefore, if a finite number, say $l$, of the sets $A_1, A_2, \ldots$
have more than one element, and the maximum size of any set if $m$, then
the total number of elements in the product is bounded by $m^l$ -- which
is finite.

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

{\bf Solution}  The product will never be countably infinite!  In the
next part of the problem, we show that if an infinite number of sets
$A_i$ have more than one element, then the product is uncountable.  
The other case was covered in part a.  Since these two cases exhaust all
possible cases, there is no other possibility.

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

{\bf Solution: }
if an infinite number of sets $A_i$ have more than one element, then the 
product is uncountable.  Let $B_1, B_2, \ldots$ denote the sets among the
$A_i's$ that have more than one element.  That is each, $B_i$ uniquely
corresponds to some set $A_j$ that has more than one element.  Now,
if we can show that $B_1 \times B_2 \times \cdots $ is uncountable, then 
this implies that $A_1 \times A_2 \times \cdots$ is uncountable because 
all we did to get from the $A_i$'s to the $B_i$'s was to remove all the
$A_j$'s with one element, and one element sets don't add to the number of
elements in the product.    
 
Let's consider the case that each $B_i$ has exactly two elements.  
Denote by $\beta^i_1. \beta^i_0$ the two elements in the set $B_i$.  We 
will give
a bijection from the set of infinite length binary string to the product
$B_1  \times B_2 \times \cdots $.  Since the set of infinite length binary
strings is uncountable, we will have shown uncountability of the infinite
product of the $B_i's$.  Now, let $b_1 b_2 b_3 \ldots $ be an infinite 
length binary string.  We must associate this string with an element of
the infinite cross product of the $B_i$'s.  We associate with 
$b_1 b_2 b_3 \ldots $ the element 
$(\beta^1_{b_1}, \beta^2_{b_2}, \beta^3_{b_3}, \ldots )$.  
This gives us a bijection.

Now, the only remaining case is that some of the $B_i$'s might have 
more than two elements.  However, if all the $B_i's$ have at least
two elements, then the resulting product will have at least as many
elements as the product when each $B_i$ had exactly two elements.  Therefore
we have that the product of the $B_i$'s are uncountable in this case
as well.  

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

{\bf Solution: }  Let's denote by $D_n$ the set of all directed acyclic 
graphs with $n$ vertices.  Now, observe that number of graphs with $n$
vertices is bounded by $2^{n^2}$.  This holds because each graph with
$n$ vertices can be represented by an $n \times n$ adjacency matrix.  
The entries in this matrix can be either $0$ or $1$.  Since there are
$n^2$ entries in the adjacency matrix, it follows that there can be 
at most $2^{n^2}$ adjacency matrices.  Now, the number if directed
acyclic graphs with $n$ vertices is definitely no bigger than the total
number of graphs with $n$ vertices.  Hence, there are at most $2^{n^2}$
directed acylic graphs with $n$ vertices, which means that 
$|D_n| \leq 2^{n^2}$ -- hence $D_n$ is finite.  
We now show how to enumerate all the possible directed acyclic graphs.  
First list all the elements
of $D_1$.  We can do this since $D_1$ is finite.  Then list all elements
of $D_2$, followed by $D_3$, etc,.  Since each of these sets is finite,
every set is listed fully.

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



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

{\bf Solution:} 
There are $2^m$ elements in the domain.  There are $2^n$ elements in
the range.  For every element in the domain, we thus have $2^n$ choices
for what we can map it to.  Therefore, by the product rule, there are
at most $(2^m)^{(2^n)}$ possible functions 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}?

{\bf Solution:} 
There are $2^n$ elements in both the domain and range.  Hence there
are a total of $(2^n)^{(2^n)}$ functions.  Now, of these functions
we know that $(2^n)!$ are permutations.  Hence the remaining are not
permutations.  The total number of functions with domain and range 
$\{0,1\}^n$ that are not {\em permutations} is $(2^n)^{(2^n)} - (2^n)!.$

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

{\bf Solution:} 
We have $2^n$ elements in the domain, and they can each possibly 
be mapped to $2^n - 1$ elements in the range (any element but 
themselves).  Therefore, there are $(2^n)^{(2^n - 1)}$ total functions
with no fixed points.


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

{\bf Solution:} 
There are $(2^n)^{(2^n)}$ functions total, and $(2^n)^{(2^n - 1)}$ have
no fixed points.  Therefore, the remaning  
$(2^n)^{(2^n)} - (2^n)^{(2^n - 1)}$ have at least one fixed point.

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

{\bf Solution:} 
Let's fix a particular point for our fixed point.  Now let's consider where
the remaining $2^n - 1$ points can be mapped.  Each one can be mapped to 
any spot but itself -- thus it can be mapped to at most $2^n - 1$ spots.
For each particular fixed point, there are $(2^n - 1)^{(2^n - 1)}$ functions.
Since there are $2^n$ possible choices for the particular fixed point,
the total number of functions with exactly one fixed point is  
$(2^n)((2^n - 1)^{(2^n - 1)})$ 


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

Now, there are $(2^n)^{(2^n)} - (2^n)^{(2^n - 1)}$ with at least one
fixed point.  Of these functions, $(2^n)((2^n - 1)^{(2^n - 1)})$ have
exactly one fixed points.  Therefore, the remaining 
\[ (2^n)^{(2^n)} - (2^n)^{(2^n - 1)} - (2^n)((2^n - 1)^{(2^n - 1)}) \]
have 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}




