\documentclass[11pt, twoside]{article}

\usepackage{multirow}

\usepackage{graphics}
\usepackage{psfig}

\input{macros-course}

%\newcommand{\nand}{|}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Printing the page layout parameters

\printlayout

\askaboutsolutions

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

\ifshowsolutions
  \newcommand{\reading}[1]{}
%
  \newcommand{\handoutlabel}{sol7-5}
  \newcommand{\handouttitle}{Problem Set 7.5 Solutions}
  \newcommand{\handoutdate}{April, 2000}
  \newcommand{\collaboration}{}
  \newcommand{\titlebar}{\handout{\handoutlabel}{\handouttitle}{\handoutdate}}
%
\else 
  \newcommand{\reading}[1]{%
%    \mbox{}\\ %
    \hrule\mbox{} \\ %\bigskip %
    #1%
%    \mbox{} \\ %\bigskip %
    \hrule %
    %\vfill\mbox{}\newpage%
    }
%
  \newcommand{\handoutlabel}{ps7-5}
  \newcommand{\handouttitle}{Problem Set 7.5}
  \newcommand{\handoutdate}{April 4, 2000}
  \newcommand{\duedate}{Never}
  \newcommand{\collaboration}{\collaborationnote}
  \newcommand{\titlebar}{%
    \handout{\handoutlabel}{\handouttitle}{\handoutdate}
    \centerline{{\bf Due  Date: \duedate.}}
    \vspace*{\baselineskip}}
%
\fi

\renewcommand{\solution}[1]{%
  \ifshowsolutions %
  \textbf{Solution.} \par %
  #1
  \mbox{} \\
  \mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
  \raisebox{-0.25\baselineskip}{$\square$}%
  \hspace*{1ex}\ignorespaces\hrulefill%
  \nopagebreak%
  \fi}


%\newcommand{\solutionname}{Solution}
%\renewenvironment{solution}[1][\solutionname]{%
%  \par
%  \normalfont
%  \topsep6\p@\@plus6\p@ \trivlist
%  \item[\hskip\labelsep\bfseries
%    #1\@addpunct{.}]~~\ignorespaces
%}{%
%\mbox{} \\
%\mbox{}\hrulefill\hspace*{1ex}\ignorespaces%
%\raisebox{-0.25\baselineskip}{$\square$}%
%\hspace*{1ex}\ignorespaces\hrulefill%
%\nopagebreak%
%}

%\renewcommand{\solution}[1]{%
%  %\begin{solution}
%    #1
%  %\end{solution}
%  }

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

\begin{document}

\titlebar

\reading{%
  \vspace{-2\baselineskip}
  \begin{description}\itemsep 0\baselineskip
  \item[Self-study:] \mbox{} \\
%    Rosen, Section 1.8, on the growth of functions. \\
%    Self-study problems: 3,7,9,11,13,15,17,19,23,31
    
  \item[Reading:] \mbox{} \\[-\baselineskip]
    \vspace*{-0.5\baselineskip}
    \begin{description}\itemsep 0\baselineskip
%    \item[Rosen:] Sections 5.1, 5.2, 5.3, 4.1, 4.2
%    \item[6.042 Fall 97 Lecture notes (available from course webpage):] %
%      Lectures 9--12
    \end{description}
  \end{description}
  }

\section*{Problems:}

\begin{problems}


%%%%%%% Problem %%%%%%%%
% source: fall95 ps7
% topic: combinatorics, morse code, ?is this a ``stars and bars'' problem?

\problem
Morse code is a system for representing an alphabet with dots and
dashes.  The arrangements of dots and dashes is then transmitted using
eletrical pulses of varying lengths or analogous mechanical or visual
signals. For example, the letter A may be represented by dash-dot-dot
and the letter B by dash-dot.  Since it takes time and effort to
transmit, the code must be as compact as possible. For a compact code
what is the maximum number of dots/dashes required by any character if
we wish to represent
\bparts
\ppart the letters A,B,$\ldots$,Z?
\ppart the letters A,B,$\ldots$,Z,a,b,$\ldots$,z,0,1,$\ldots$,9? 
\ppart Given that two dots in a row can get confused with a dash, how many 
different characters can you represent with $k$ dots/dashes that have no consecutive dots?
\ppart Suppose a dot takes 1 seconds, a dash takes 3 seconds, and each must
be followed by a 1 second interval of silence.  How many morse symbol
sequences have sending times less than k seconds (including the last
interval of silence)? 
\eparts
Hint: For parts c) and d) determine and solve a recurrence
conditioning on the value of the first symbol.


%%%%%%% Problem %%%%%%%%
% source: spring96 ps7
% topic: combinatorics, balls in boxes

\problem 
How many ways are there to distribute eight balls into six distinct
boxes with the first two boxes having collectively at most four balls if
\bparts
\ppart the balls are identical?
\ppart the balls are distinct?
\eparts


%%%%%%% Problem %%%%%%%%
% source: fall95 ps7
% topic: combinatorics, counting relations

\problem
On a set of $n$ elements how many of the following are there
\bparts
\ppart relations?
\ppart symmetric relations?
\ppart reflexive relations?
\ppart symmetric and reflexive relations?
\ppart symmetric or reflexive relations?
\ppart equivalence relations (this problem is for extra credit)?
\eparts


%%%%%%% Problem %%%%%%%%
% source: fall95 ps7
% topic: combinatorics, summations

\problem
Prove that 
\[ {\displaystyle \sum_{k=1}^n}k\left(\begin{array}{c} n\\ k\end{array}\right) = n2^{n-1} \]
\bparts
\ppart using a combinatorial argument.
\ppart by finding a closed form for $ {\displaystyle \sum_{k=1}^n}\left(\begin{array}{c} n\\ k\end{array}\right)kx^k$ and evaluating it at $x=1$.
\eparts


%%%%%%% Problem %%%%%%%%
% source: fall94 ps7 bonus problem
% topic: combinatorics, geometry

\problem  
Consider $n$
points located on a circle, and consider the $n\choose 2$ chords
connecting the points.  Assuming that no three chords with distinct
endpoints intersect at a single point, how many points of intersection
among the chords are there in the interior of the circle?


%%%%%%% Problem %%%%%%%%
% source: fall94 ps7
% topic: combinatorics

%%		from M&R, # 4.3.21 and 4.3.22
\problem 
A computer operating system requires file names to be exactly four letters
long; uppercase and lowercase letters are distinct.
\begin{problemparts}
\problempart
How many possible file names are there?
\problempart
The operating system is changed so that uppercase and lowercase are no
longer distinct.  Figure out the new number of file names in two ways:
applying the division rule to {\bf (a)} and directly.
\problempart
The operating system is changed so that file names may be {\em up to\/}
four letters long.  Repeat {\bf (a)} and {\bf (b)}.  Can the division
rule still be used?
\end{problemparts}


%%%%%%% Problem %%%%%%%%
% source: fall94 ps7
% topic: combinatorics

\problem
Without using the formula for $n \choose k$,
give a combinatorial argument to prove that the identity
\[
{s-1\choose 0} + {s\choose 1} + \cdots + {s+n-2\choose n-1}+ {s+n-1\choose n} 
= 
{s+n\choose n}
\]
holds, where $s$ and $n$ are positive integers.
(\hint If $X$ is an $(s+n)$-set\footnote{That is, a set containing
$s+n$ elements}
and $Y=\{ y_1, y_2, \ldots, y_n\}$ is a specific $n$-subset of $X$, 
what is the number of $n$-subsets of $X$ for which $y_r$ is the first member
of $Y$ not in the subset?)


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

\problem
A pizza house is having a promotional sale. Their commercial reads:\\
``... buy $2$ large pizzas at regular price, get up to $11$ toppings for 
each pizza absolutely free. That's $4194304$ different ways to design your
order!!!! ...''

\bparts
\ppart	Show that $4194304 = \displaystyle \left( \sum_{k=0}^{11}{11 \choose
k} \right)^2$ is actually wrong 
and give the right answer for the number of ways that you can 
choose toppings for the two pizzas.

\ppart	Now assume that you can choose any number of the same 
topping as long as the total number of toppings is no more than $11$.
(That is, you can have $2$ meatball, $4$ ham and $5$ sausage toppings if 
you are truly a meat lover.) How many different ways can you now choose
toppings for your two pizzas?

\eparts


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

\problem 

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

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

\eparts


%%%%%%% Problem %%%%%%%%
% source: spring96 ps7
% topic: combinatorics, algebraic manipulation

\problem Prove the following identities both by algebraic manipulation and
by giving a combinatorial argument:
\bparts
\ppart \[{n \choose r}{r \choose k} = {n \choose k}{n-k \choose r-k}\]
\ppart \[{2n \choose 2} = 2{n \choose 2} + n^2\]
\ppart \[ \sum_{k=0}^n 2^k {n \choose k} = 3^n\]
\eparts


%%%%%%% Problem %%%%%%%%
% source: spring98 ps7
% topic: combinations

\problem

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.


%%%%%%% Problem %%%%%%%%
% source: spring98 ps8
% topic: combinatorics

\problem 
Solve the following counting problems.

\begin{problemparts}
\problempart Suppose that Theory Moose starts at position $(0, 0)$.  At
any time, he can step north (incrementing the first coordinate) or
step east (incrementing the second coordinate).  In how many different
ways can he reach position $(n, n)$, where $n$ is a non-negative
integer?

\solution{Theory Pig must take $2n$ steps in total.  Of these, he must
choose a subset of $N$ to be north steps.  This gives $\binom{2n}{n}$
different ways to reach $(n, n)$.}

\problempart How many different ways are there to list the numbers $1,
2, \ldots, 2n$ such that the even numbers appear in increasing order
and the odd numbers appear in decreasing order?

\solution{ There are $(2n)!$ ways to list the numbers $1, 2, \ldots,
n$.  We can define a $n!$-to-1 mapping that takes an arbitrary listing
to a listing in which the even numbers are sorted in increasing order
and the odd numbers remain as before.  Thus, by the quotient rule
there are $(2n)!/n!$ listings in which the even numbers appear in
increasing order.  Similarly, we can define an $n!$-to-1 mapping that
takes a listing in which the even numbers appear in increasing order
and the odd numbers are in an arbitrary order to a listing in which
the even numbers appear in increasing order (as before) and the odd
numbers appear in decreasing order.  Therefore, there are

\begin{eqnarray*}
\frac{(2n)!}{n! \ n!} & = & \binom{2n}{n}
\end{eqnarray*}

listings in which the even numbers are increasing and the odd numbers
are decreasing.
}

\problempart Describe a bijection that maps each one of Theory Pig's
paths to a listing of the numbers $1, 2, \ldots 2n$ with even numbers
increasing and odd numbers decreasing.

\solution{Each time Theory Pig take a step north, write down an even
number, starting with 2 and working up.  Each time Theory Pig takes a
step east, write an odd number, starting with $2n-1$ and working down.}

\end{problemparts}


%%%%%%% Problem %%%%%%%%
% source: fall95 ps7
% topic: binomial coefficients in large polynomials

\problem
Find the coefficient of 
\bparts
\ppart $x^{10}$ in $(x+(1/x))^{100}$.
\ppart $x^8y^9$ in $(3x+2y)^{17}$.
\ppart $x^k$ in $(x^2 - (1/x))^{100}$.
\eparts


%%%%%%% Problem %%%%%%%%
% source: fall94 ps7
% topic: combinatorics, binomial theorem

\problem We wish to prove the identity
\[\sum_{r=0}^n{n\choose r}^2 = {2n\choose n}\ ,\]
for $n\in\naturals$.

\begin{problemparts}
\problempart Use the binomial theorem and the fact that
\[(1+x)^n(1+x^{-1})^n = x^{-n}(1+x)^{2n}\] to prove the identity.

\problempart Consider a set of $2n$ objects, of which $n$ are red and
$n$ are blue.  Use the fact that \[{n\choose r}^2 = {n\choose
r}{n\choose n-r}\] to give a combinatorial proof of the identity.
\end{problemparts}


%%%%%%% Problem %%%%%%%%
% source: fall94 ps7
% topic: binomial theorem

\problem Let $n, r\in\naturals$.
Use the binomial theorem to evaluate the expressions
\[\sum_{k=0}^{n}{n\choose k}r^k 
\;\;\mbox{ and }\;\;
\sum_{k=0}^{n}{n\choose k}(-r)^k\ .\]
%	(\hint $(-1)^k = \pm (-1)^{n-k}$.)
Use your analysis to conclude that if $r$ is odd, then
\[\left. 2^{n-1} \;\right| \sum_{\stackrel{\scriptstyle k=0}{k {\mathrm{\ even}}}}^{n}{n\choose k}r^{k}\ .\]

Note that if $r=1$, this sum simply counts the number of even-sized
subsets of an $n$-set, which we know is exactly $2^{n-1}$.


%%%%%%% Problem %%%%%%%%
% source: fall94 ps7
% topic: binomial coefficients

\problem
Calculate the coefficient of 
\begin{problemparts}
\problempart $x^5$ in $(1+x)^{11}$;
\problempart $a^2b^8$ in $(a+b)^{10}$;
\problempart $a^6b^6$ in $(a^2+b^3)^5$;
\problempart $x^3$ in $(3+4x)^6$.
\end{problemparts}


%%%%%%% Problem %%%%%%%%
% source: spring98 ps7
% topic: binomial coefficients and the product rule

\problem

Prove that

\[ \sum_{a=0}^n \sum_{b=0}^{n-a} \frac {n!}{a!b!(n-a-b)!} = 3^n \ . \]

\medskip

[Hint: find a formula for $(x+y+z)^n$ and then set $x=y=z=1$.]


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

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


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

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


%%%%%%% Problem %%%%%%%%
% source: fall98 ps7, fall97 ps7, spring97 ps7
% topic: infinity, algebraic numbers, diagonalization, Cantor

\problem A real number is {\em algebraic} if it is the root of a
polynomial with rational number coefficients.  Algebraic numbers form
an important part in the study of (what else) modern algebra.  A
number that is not algebraic is called {\em transcendental}.
\bparts

\ppart Let $S_1,S_2,S_3,\ldots$ be a collection of countably many
sets.  Suppose each $S_i$ is countable.  Prove $\cup S_i$ is
countable.

\ppart Prove that for any particular $d$, the set of degree $d$
polynomials with rational coefficients is countable.

\ppart Prove that the set of all roots of degree $d$ polynomials with
rational coefficients is countable (you may use the fact that a degree
$d$ polynomial has at most $d$ roots).

\ppart Prove that the set of algebraic numbers (which is just the
union of the sets in the previous part) is countable.

\ppart Prove that there is a trancendental number.

\eparts

This proof was originally given by Cantor (who invented
diagonalization).  A lot of mathematicians of the time rejected it
because it didn't exhibit any particular trancendental number (it is
{\em non-constructive}.  Since then, people have demonstrated that
many important numbers (e.g. $e$ and $\pi$) are trancendental.


% optional?
 I stated in class that to prove countability it suffices
to show that there is a surjection from $\naturals$ to a set.  Prove
this statement.  That is, Suppose that $S$ is not finite and we have a
surjection $f:\naturals \rightarrow S$.  Prove that there is a
bijection from $\naturals$ to $S$.

This proves that there is no countably infinite set ``smaller'' than
$\naturals$.  Since we know that (by definition) there is no set that
is ``bigger'', we have shown that all countably infinite sets are the same
size.


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

\problem 
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:}

}

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

\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 are more decision functions
than computer programs.  Hence there must be some decision function which
cannot be computed by a computer program.}

\eparts


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

\problem 

Show that any set of finite digraphs, no two of which are isomorphic to
each other, is countable.

\solution{Let's define an \emph{integer digraph} to be a digraph whose
vertices are precisely the set of integers $\set{1,2,\dots,n}$ for some $n
\in \naturals$.  Every finite digraph is obviously isomorphic to an
integer digraph.  So if $A$ is some set of finite digraphs no two of which
are isomorphic, then there is an injection from $A$ to the set, $D$, of
all integer digraphs.  Hence, if we show that $D$ is countable, it will
follow that $A$ is countable.

To show that $D$ is countable, let $D_n$ be the set of all integer
digraphs with $n$ vertices.  But each graph in $D_n$ can be uniquely
represented by an $n \times n$ adjacency matrix.  Since there are $n^2$
single bit entries in the adjacency matrix ($0$ or $1$), it follows that
there can be at most $2^{n^2}$ adjacency matrices.  So $D_n$ is of finite
size $2^{n^2}$.  But $D= \bigcup_{n\in\naturals} D_n$, and we know, by a
similar argument to problem (1a), that the union of a countable number of
finite sets is countable.

{\bf Alternative Solution:}

Some students argued this claim a little differently.  Namely, if $D'$
is some set of finite digraphs, no two of which are isomorphic to each
other, then there $D' \,\mbox{\it inj}\, M$, where $M$ is a set of all
binary matrices.  An injection $f:D'\rightarrow{M}$ associates each
digraph with its adjacency matrix.  If no two digraphs in $D'$ are
isomorphic to each other, $f$ is an injection.  Furthermore,
$M\,\mbox{\it inj}\, B$, where $B$ is the set of finite binary strings,
where the injection between $M$ and $B$ concatenates all rows (or
columns) of the binary matrix in a single binary string.  And now
since we know that $B$ is countable, i.e. $B\,\mbox{\it inj}\, \naturals$
(problem 1 part (a)), it follows that $D'\,\mbox{\it inj}\, \naturals$,
i.e.  $D'$ is countable.
}	

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

\problem 

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

%%%%%%% Problem %%%%%%%%
% source: fall98 ps7
% topic: infinity, sets

\problem 
 Prove or disprove the following statements
about sets.  (We use ``collection'' as a synonym for ``set'' to make
some of the statements easier to read.)

\begin{problemparts}

\problempart The product of a finite collection of countable sets is
countable.

\solution{
The statement is true.  

\begin{proof}
The proof is by induction.  Let $P(n)$ be the proposition that the
product of $n$ countable sets is countable.  In the base case, $P(1)$
is true because the product of a single countable set is itself.  In
the inductive step, for $n \geq 1$ assume $P(n)$ to prove $P(n+1)$.
The product of $n+1$ countable sets $S_1, S_2, \ldots, S_{n+1}$ can be
written as shown below.

\[
(S_1 \times S_2 \times \ldots \times S_{n}) \quad \times \quad S_{n+1}
\]

The first term is a countable set by induction, and the second term is
a countable set by definition.  The product of two countable sets is
countable, as shown in lecture.  Therefore, the product of $n+1$
countable sets is countable.  This shows that $P(n)$ implies $P(n+1)$,
and the claim is proved by induction.
\end{proof}
}

\problempart The product of a countable collection of finite sets is
countable.

\solution{ The statement is false.

We will construct a bijection between the product of a
countable number of finite sets and the power set of the natural
numbers.  Since the latter is uncountable, the former must be
uncountable as well.

Consider the countable collection of finite sets $S_1 = S_2 = \ldots =
\{ 0, 1 \}$.  The product $S_1 \times S_2 \times \ldots$ consists of
all infinite binary sequences, e.g. $( 0, 1, 1, 0, 1, \ldots)$.  There
is a natural bijection between such infinite binary sequences and the
power set of the natural numbers.  In particular, let the sequence
$(b_0, b_1, \ldots)$ correspond to the set of all natural numbers $i$
such that $b_i = 1$.  This bijection implies that the set of infinite
binary sequences is uncountable.}

\problempart The set of all finite subsets of a countable set is
countable.

\solution{
The statement is true.

\begin{proof}
Let $S$ be a countable set.  For $k \geq 0$, let $S_k$ be the set of
$k$-element subsets of $S$.  The set of all finite subsets of $S$ is
then the union of the sets $S_k$ for $k \geq 0$.  We will prove below
that every set $S_k$ is countable.  This will imply that the set of
all finite subsets of $S$ is a union of a countable collection of
countable sets and is therefore countable.

All that remains is to show that $S_k$, the set of $k$-element subsets
of $S$, is countable for all $k \geq 0$.  We prove this by
establishing an injection from $S_k$ to $S^k$, the product of the set
$S$ with itself taken $k$ times.  In particular, the injection maps
the set $\{ s_1, s_2, \ldots s_k \} \in S_k$ to the tuple $(s_1, s_2,
\ldots, s_k) \in S^k$, where the elements in the tuple are ordered in
an arbitrary way.  Since $S^k$ is countable, the injection implies
that $S_k$ is also countable.


\end{proof}
}

\problempart Suppose that the intersection of a countable collection
of sets is finite.  Then there exists a finite subcollection of the
sets with finite intersection.

\solution{ The statement is false.

Let $S_k$ be the set of integers divisible by $k$, for $k \geq 1$.
The intersection of this countable family of sets is finite; in fact,
the intersection is $\{ 0 \}$, since zero is the only integer
divisible by every positive integer.  However, there is no finite
subfamily of sets $S_k$ with finite instersection.  In particular, the
intersection of the finite subfamily

\[
S_{a_1} \cap S_{a_2} \cap \ldots \cap S_{a_n}
\]

contains all integers of the form $m \cdot a_1 \cdot a_2 \cdots a_n$
where $m \in \mathbb{Z}$.  }


\end{problems}

\end{document}

\endinput

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% DONE !!! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

