\documentclass[12pt,twoside]{article}

\def\handouttype{problemset}

\usepackage{psfig}
\usepackage{changebar}
%\newcommand{\cbstart}{\chgbarbegin}
%\newcommand{\cbend}{\chgbarend}

\input{macros-course}

\def\cent{{\not\!\mathrm{c}}}

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

\askaboutsolutions

\ifshowsolutions 
  \usepackage[dark,first,bottom]{draftcopy}
  \draftcopyName{Solutions}{155}
  \typeout{}
  \typeout{Solutions *INCLUDED*}
  \renewcommand{\solution}[1]{
    \textbf{Solution.} \par %
    #1
    \mbox{} \\
    \mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
    \raisebox{-0.25\baselineskip}{$\square$}%
    \hspace*{1ex}\ignorespaces\hrulefill%
  }
\else
  \typeout{}
  \typeout{Solutions *NOT INCLUDED*}
  \renewcommand{\solution}[1] {
  }
\fi
    

%\renewcommand{\solution}[1]{%
%  \ifshowsolutions %
%%  \cbstart
%%  \cbend
%  \nopagebreak%
%  \else
%%  \vspace*{2in}
%    \fi}

\newcommand{\problembreak}{%
  \ifshowsolutions %
  \newpage
  \else
  \newpage
  \fi%
}

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

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\tutref}{tut9}
\newcommand{\tutnum}{9}
\newcommand{\tutdate}{April 7, 2000}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\handout{\tutref}{Mini-Quiz \tutnum}{\tutdate}

\begin{enumerate}
\item Write your name:

\bigskip

\item %
  (Rosen, Section 1.7, Problem 35) Show that if $A$ is an uncountable set
  and $A \subseteq B$, then $B$ is uncountable.

  \vspace*{3in}

\end{enumerate}

\newpage
\thispagestyle{empty}

\mbox{}

\setcounter{page}{0}

\newpage
\handout{\tutref}{Tutorial \tutnum~Problems}{\tutdate}

\begin{problems}


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

%%%%%%% Problem %%%%%%%%
% source: spring95, ps7
% topic: basic combinatorics

\problem 

% comment out/remove following before going to press
%{\bf Basic Combinatorics, low difficulty:}

\bparts
\ppart How many ways can $2n$ people be divided into $n$ pairs?

\solution{
$\displaystyle (2n)!/ n! 2^n$.

Consider all the ways of ordering the $2n$ people in a line. There are
$(2n)!$ ways of doing this. Now group them into pairs based on the
linear order, i.e. group the first and second persons, group the third
and fourth persons,..., group the $(2n-1)$th and $2n$th persons. Thus
each linear order gives us a unique grouping into pairs. But observe
that two different linear orders could give rise to the same grouping
into pairs. So let us now count the number of linear orders that give
rise to the same grouping into pairs. Given a grouping into pairs, to
generate a linear order we need to order each pair (there are $2^n$
ways to do this) and then order the $n$ pairs (there are $n!$ ways to
do this). Hence $n! 2^n$ linear orders give the same grouping into
pairs. Thus the total number of ways $2n$ people can be divided into
$n$ pairs is $ (2n)!/ n! 2^n$.

\iffalse
First we pick $n$ leaders from the $2n$ people. 
There are ${2n \choose n}$ ways to do this. 
Then we pair the remaining $n$ people with the $n$ leaders. That gives
us $n!$ different ways for each choice of leaders. However,
${2n \choose n}n!$ will be overcounting, since for any fixed pairing,
we count each pair twice depending on who is the leader.
 So for any valid pairing, we counted it $2^n$ times.
Therefore, the answer should be
 $\displaystyle {2n \choose n} n! /2^n$.

\fi
}

\ppart How many ways can you choose $n$ out of $2n$ objects, given that
$n$ of the $2n $ objects are identical?

\solution{
The answer is $2^n$, since you can pick any subset from the $n$
nonidentical objects, and make up the rest with the identical ones. And the
number of subsets of $n$ different objects is $2^n$. 
}

\eparts


%%%%%%% Problem %%%%%%%%
% source: spring98 ps7
% topic: combinations, standard stars and bars

\problem

% comment out/remove following before going to press
%{\bf Stars and Bars, low difficulty:}

Calculate the number of ways to place 11 {\em indistinguishable} balls in four 
{\em distinguishable} boxes so that each box contains at least one,
but no  more than four, balls.

\solution{
First place one ball in each box.  Then we must distribute 7 balls in four
boxes in such a way that no more than three balls are in the same box.

We use inclusion/exclusion

Number of ways to place 7 balls in 4 boxes:
${7+4-1 \choose 7} = {10 \choose 7}$.

Number of ways to place 7 balls in 4 boxes such that there are four balls
in a box =  number of ways to choose box with four balls * number of ways
to place remaining three balls in remaining three boxes =
$4 \cdot {5 \choose 3}$.

Number of ways to place 7 balls in 4 boxes such that there are five balls
in a box = $4 \cdot {4 \choose 2}$.

Number of ways to place 7 balls in 4 boxes such that there are six balls
in a box = $4 \cdot {3 \choose 1}$.

Number of ways to place 7 balls in 4 boxes such there are seven
balls in a box = 4.

So the total number of ways is

${10 \choose 7} - 4 \left({5 \choose 3} +
{4 \choose 2}+{3 \choose 1} +1 \right) = 40$
}


%%%%%%% Problem %%%%%%%%
% source: spring99 ps8
% topic: infinity, incomputable functions

\problem 

% comment out/remove following before going to press
%{\bf Infinity, more interesting (OPTION 2 [longer]):}

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.

\solution{
Let $B_n$ denote the set of binary strings of length $n$.
This set has exactly $2^n$ elements.  Therefore the set of finite
length binary strings $B=\bigcup_{n\in\naturals}B_n$ is a union of
countable number of finite sets.  We know from Lecture 13 that such
union is countable.

Namely, one can easily list all elements of $B$ 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?  

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

Namely, the mapping which represents computer programs as finite
strings of bits is an injection.  Hence there is a surjection from the
set of finite strings of bits to the set of computer programs.  From
(a) we know that there is a surjection from the set of natural numbers
to the set of finite strings of bits.  By transitivity of surjective
mapping, there is a surjection between natural numbers and computer
programs.  Hence the set of all comptuer programs is countable.  
}

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

\solution{
We construct a bijection from the 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.

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 $f(b) = S = \{ i \ | \ b_i = 1 \}$.  That is, we
include $i$ in $S=f(b)$ if and only if the $i$-th bit position (from
the left) of $b$ is 1.  Such mapping $f$ is a bijection: It is an
injection because if two infinite length binary strings are different,
then clearly they map to different subsets.  Furthermore, it is a
surjection because for every subset $S\subset\naturals$, there is a
binary string $b$ s.t. $f(b)=S$, namely $b=b_0b_1b_2b_3\ldots$ where
$b_i$ is defined as $0$ if $i\not\in{S}$ and $1$ if $i\in{S}$.

{\bf Alternative Solution:}
One can also show that the set $B'$ is uncountable directly by a
diagonalization argument.

Assume $B'$ is countable and let $b^{(1)},b^{(2)},b^{(3)},b^{(4)},...$
be a list of all elements of $B'$.  By diagonalization, we will
construct an element $b=b_0b_1b_2b_3...\in{B'}$ s.t. $b\neq b^{(i)}$
for all $i\in\naturals$ as follows: $j$-th bit of $b$ is defined as
the opposite of the $j$-th bit of string $b^{(j)}$.  Obviously, so
defined $b$ is not equal to any $b^{(i)}$ from the list because for
every $i$, the $i$-th bit of $b^{(i)}$ is different than the $i$-th
bit of $b$.  Therefore, the list $b^{(1)},b^{(2)},b^{(3)},b^{(4)},...$
is {\it not} a list of all elements in $B'$, and thus the assumption
that $B'$ is countable leads to a contradiction.  
}

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

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

It is an easy bijection between a set of such mappings and a power set
of the natural numbers.  Namely, we associate with a decision function
$f$ a set $S=\{i\in\naturals\mbox{ s.t. }f(i)=1\}$.  Clearly, this is
an injection and a surjection.  Therefore, since the power set of the
set of natural numbers is uncountable then so is the set of decision
functions.

{\bf Alternative Solution:} We can 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.  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 a decision function $f$ defined as
$f(0) = b_0, f(1) = b_1, f(2) = b_2, \ldots$, will be mapped to that
string.  Therefore, the mapping function is surjective.  Since it's
injective and surjective, it must be bijective.
{\bf Alternative Solution 2:} 

Some students gave a diagonalization argument for why $F$ is
uncountable: Assume otherwise and let $\{f_1,f_2,f_3,...\}$ be the
list of all elements of $F$.  From part (a) we know that $B$, the set
of all finite length binary strings is countable, so there must exist
a bijection $g:B\rightarrow\naturals$.  Now, define a decision
function $f:B\rightarrow\{0,1\}$ as follows:
\[
f(s)=\mbox{ the opposite of }f_{g(s)}(s)
\]
Then $f$ is different from all $f_i$'s because for all
$i\in\naturals$, $h$ differs from $f_i$ on string $s=g^{-1}(i)$.


{\bf Alternative Solution 3:} 

One can also argue, as some students did, that $F$ is uncountable by
showing the bijection between $F$ and the set, $P(B)$, of all subsets of
$B$.  The bijection associates with $f\in{F}$ a set of strings $b \in B$
s.t. $f(b)=1$.  Then, since by part (a) there is a bijection between $B$
and $\naturals$, there must be a bijection between $P(B)$ and
$P(\naturals)$.  By transitivity of bijective relation between sets, there
is a bijection then between $F$ and $P(\naturals)$.  Hence $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 is a
decision function that is not computable.
% STAS: repetitions...
% That is, there is no computer program that computes it.  

% \ignore{ % STAS: Too much spoonfeeding...
% (Hint: compare your answer from the second part to the the answer you
% just got from the previous part)}

\solution{
Since there are only countably many computer programs,
but uncountably many decision functions, there can be no surjection
from the set of computer programs to the set of decision functions (In
fact, this means that there is {\it more} decision functions than
computer programs).  In particular, if we associate a computer program
to a decision function which this program is computing\footnote{If a
program is not computing any decision function, associate it with a
trivial decision function $f(b)=0$, for all finite bit strings $b$.},
this association is not a surjection either.  Therefore there must be
some decision function which is not computed by any computer program.
}

\eparts


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

\end{problems}

\end{document}

\end{input}

%%%%%%%%%%%%%% DONE %%%%%%%%%%%%%%%%%%

%%%%%%% Problem %%%%%%%%
% source: fall97 ps7
% topic: infinity

\problem

% comment out/remove following before going to press
%{\bf Infinity, standard (OPTION 1):}

Let ${\cal S}_i, 1 \leq i \leq \infty$ be a 
family of countable sets.
Prove that ${\displaystyle \bigcup}^\infty_{i=1} {\cal S}_i$ is countable.

\solution{
\begin{proof}
Since each  $S_i$ is countable, it's elements can be listed in a sequence.
Let $s_{ik}$ be the $kth$ element in the listing of $S_i$. 
We list the sets in the following array

\[ \begin{array}{ccccc}
s_{11} & s_{12}  & s_{13} & s_{14} & \cdots \\
s_{21} & s_{22}  & s_{23} & s_{24} & \cdots \\
s_{31} & s_{32}  & s_{33} & s_{34} & \cdots \\
s_{41} & s_{42}  & s_{43} & s_{44} & \cdots \\
\cdots & \cdots  & \cdots & \cdots & \cdots \\
\end{array} \]

We can count the elements using the
dove-tailed interleaving shown in class, to get the listing for their
union. The resulting list is $\{ s_{11}, s_{12}, s_{21}, s_{13},
s_{22}, s_{31}, \ldots \}$. 

Since we have been able to give a valid listing, $ {\displaystyle
\bigcup}^\infty_{i=1} {\cal S}_i $ is countable.
\end{proof}
}


%%%%%%% Problem %%%%%%%%
% source: fall97 ps7, Rosen? sec. 1.8, problem 30
% topic: infinity

\problem

% comment out/remove following before going to press
%{\bf Infinity, standard (OPTION 2):}

Use a diagonalization argument to show that the set of functions from
the positive integers to the set $\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$ is
uncountable.
\newline
\solution{
\begin{proof}
Assume, for the purposes of contradiction, that this set is countable.
Then there is a listing of the function in the set,
 $f_1, f_2,\ldots$.  Now define $f$ such that $f(i) = (f_i(i)+5) \mod 10$.
Then $f$ is not in the list, because $f$ differs from each $f_i$
in the $i$th value.  We have established a contradiction.  We conclude that
the set is uncountable.
\end{proof}
}


%%%%%%% Problem %%%%%%%%
% source: spring99 ps8
% topic: infinity, sets

\problem 

% comment out/remove following before going to press
%{\bf Infinity, more interesting (OPTION 1):}

Let $A_1,A_2,\dots$ be an infinite sequence of nonempty, finite sets.
For any $k\in \naturals$, the product $A_1 \times A_2 \times \cdots
\times A_k$ is finite, and hence countable.  In this problem we
consider countability of the \emph{infinite} product $P ::= A_1 \times
A_2 \times A_3 \times \cdots$, which is a set of infinite strings
$(a_1,a_2,a_3,...)$ such that $a_i\in{A_i}$ for all $i \in \mathbb{N}$.

\bparts 

\ppart State a simple necessary-and-sufficient condition for $P$ to be
finite.

\solution{
The product can be finite exactly when some finite number, $n$,
of the sets $A_i$ have more than one element, and the others have one
element.  It is easy to see that the condition is necessary, i.e. that
if there is no such number $n$ then $P$ is infinite.  To show that our
condition is also sufficient, say that $A_{i_1},\dots,A_{i_n}$ are the
sets with more than one element.  Let $f$ be the function which maps
any element of the infinite product into the $n$-tuple consisting of
the elements in positions $i_1,\dots,i_n$.  It is easy to see that $f$
is a bijection from the infinite product to the finite product
$A_{i_1} \times \dots\times A_{i_n}$.  Since a finite product of
finite sets is itself a finite set, we conclude from the bijection
that the infinite product is also a finite set.
}

\bigskip
\ppart
Show that $P$ is countable iff it is finite.

\solution{
Clearly, if $P$ is finite then it is countable.  We need to show also
that if it is countable than it is finite.  We will prove the
counterpositive of that claim, i.e. that if it is infinite than it is
uncountable.  Because the condition stated in part (a) was sufficient
for $P$ to be finite, it follows that if $P$ is infinite than there is
an infinite number of sets $A_i$ with more than one element.

We show that if an infinite number of sets $A_i$ have more than one
element, then the set $P$ which is the product of all $A_i$'s is
uncountable.  Let $A'_1, A'_2, \ldots$ denote the sets among the
$A_i's$ that have more than one element.  That is each, $A'_i$
uniquely corresponds to some set $A_j$ that has more than one element.
Now, if we can show that $P'=A'_1\times A'_2\times\cdots $ is
uncountable, then this implies that $P=A_1\times A_2\times\cdots$ is
uncountable too: It is easy to construct a bijection between $P$ and
$P'$, similar to the one used in part (a).

For every $i$, we can denote the elements of $A'_i$ as $\{a^i_0,a^i_1,
\dots, a^i_{k_i}\}$, where $|A'_i|=k_i+1$ and $k_i \geq 1$.  We will give an
injection $f$ from the set $B'$ of infinite length binary strings to set
$P'$.  Since from problem (1c) we know that the set $B'$ is uncountable,
this will imply that $P'$ is also uncountable.\footnote{In case this is
not obvious: We know that a set $A$ is countable if and only if there is
an injection from $A$ to $\naturals$ (e.g. Problem 1 in section 6 of
Handout 38).  Therefore, if $P'$ was countable than there would be an
injection $g$ from $P'$ to $\naturals$ and then $g\circ{f}$ would be an
injection from $B'$ to $\naturals$, and hence $B'$ would be countable too.
Contradiction.} Define $f:B'\rightarrow{P'}$,
$f(b_1b_2b_3\dots)=(a^1_{b_1},a^2_{b_2},a^3_{b_3},\dots)$.  Clearly, $f$
is an injection, which ends the proof.  }

\eparts


