\documentstyle[12pt,twoside]{article}

\newcommand{\problem}{%
  \paragraph{Problem}}
\newcommand(\solution}{%
  \paragraph{Solution}}

\begin{document}


\begin{problems}

%BEGIN Kavita's problems
% Fall 1998


%**************
%   PSET 7    *
%**************

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

\problem {\bf (20 points)} 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{problemparts}

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

\problem {\bf (20 points)} A real number is {\em algebraic} if it is
the root of a polynomial with rational coefficients.  A number that is
not algebraic is called {\em transcendental}.

\begin{problemparts}

\problempart Prove that the set of polynomials of degree $d$ with
rational coefficients is countable, for all $d \geq 1$.

\solution{ There is a natural bijection between degree $d$ polynomials
and elements of the set $(\mathbb{Q} \setminus \{ 0 \}) \times
\mathbb{Q}^d$.  Specifically, a degree $d$ polynomial is mapped to an
element of this set by arranging the coefficients in a $(d+1)$-tuple.
The set of rational numbers, $\mathbb{Q}$, was shown to be countable in
lecture.  In the preceding problem, we showed that a finite product of
countable sets is countable.  Therefore, the set $(\mathbb{Q} \setminus
\{ 0 \}) \times \mathbb{Q}^d$ is countable.  The bijection then implies
that the degree $d$ polynomials are countable.
}

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

\solution{ Each specific polynomial of degree $d$ has a finite number
of roots, according to the fact in the problem statement.  There are a
countable number of polynomials of degree $d$, according to the
previous problem part.  Since the union of a countable collection of
finite sets is countable, the set of all real roots of degree $d$
polynomials with rational coefficients is countable.
}

\problempart Prove that the set of algebraic numbers is countable.

\solution{The set of algebraic numbers is the union over all $d$ of
all the roots of polynomials of degree $d$.  This is a countable union
of countable sets, and is therefore countable.}

\problempart Prove there exists at least one transcendental number.

\solution{ The set of real number is uncountable.  The subset of
algebraic numbers is countable.  Therefore, the algebraic numbers form
a proper subset of the real numbers, and so there is at least one
transcendental number.}

\end{problemparts}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%END   Kavita's problems

%BEGIN Joe's problems
\problem %source: spring00 ps7-5
% source: fall97 ps7
% topic: infinity
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}
}

%END   Joe's problems

%BEGIN Ray's problems

%%%%%%%%%%%%%%%%  S99 ps8

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

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


{\bf Alternative Solution:} 
Some students noticed that finite length binary strings can be thought
of as natural numbers represented base $2$.  Therefore, an injective mapping
from finite length binary strings to natural numbers can be constructed as
follows:
\[
f(b_0b_1b_2...b_n)= 2^{n+1}+(b_0+b_12+b_22^2+...+b_n2^n)
\]
i.e. we map a string of bits to a natural number that it represents
in binary, except that we add $2^{n+1}$ term to make sure that bit
strings of different length get mapped to a different natural number
(Otherwise strings $0010$, $010$, $10$ would all map to the same number).
You can check that $f$ is an injection from $B$ to $\naturals$ and hence
$B$ is countable.  

You can also easily modify $f$ to be a bijection if instead of adding
$2^{n+1}$ term to the right side, you add $2^{n+1}-1$.  }


\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 computer programs is countable.  }


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

\solution{We construct a bijection from the set $B'$ of infinite length binary
strings to the power set of the natural numbers $P(\naturals)$.  Since
$P(\naturals)$ is uncountable, it will then follow that $B'$ 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 \in{B'}$ 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:B'\rightarrow{P(\naturals)}$ 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\in P(\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 (because
the set of all finite length bit strings was infinite and countable),
hence we can think of decision functions as mapping natural numbers to
the range $\{0,1\}$, i.e. to single bits.

It is easy to see a 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
both injective and surjective, it is also 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 spoon-feeding...
(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

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


%%%%%%%%%%%%%% S99 ps8

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


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


\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 {\bf (10 Points)}

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.


 }
 


%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset6 problem6 spring98 countable, uncountable set via diagonalization

\problem 
Consider the set of binary strings of infinite length (strings of zeroes and
ones).  Prove that the set of such strings with at most $501$ ones in them
is countable. 
(Hint: how might you list these numbers?) 

\solution{
{\bf Solution:}
Let $A$ be the set of infinite binary strings with at most $501$ ones 
in them.
For any arbitrary $x>0$, only a finite number of elements of $A$
have all of their ones occur before the $x$th digit.
(i.e., only 2 have all ones before the $2$nd digit, specifically
$1000000$\dots and $000000$\dots)  Let $A_x$ be the set of those elements in $A$
such that all of their ones occur before the $x$th digit.
Each $A_x$ is a finite set, and a subset of $A$.
For any element $a \in A$, look at the position of the last one in $a$.
If that one is in position $i$ then $a \in A_{i+1}$.  Therefore, every 
element of $A$ appears in at least one $A_x$.  
To list all of the elements in $A$, first list all of the elements
in $A_1$, then all of the elements in $A_2$, then all of the
elements in $A_3$ etc, removing duplicates.
Since each $A_x$ is finite, the list is a valid list.
Thus a list has been generated for all elements in
$A$ and therefore $A$ is countable.
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%pset6 problem7 spring98 countable, uncountable set via diagonalization

\problem
Consider the set of binary strings of infinite length (strings of zeroes
and ones).  Define $A_n$ to be the set of binary strings such that, at any
point in the string, at most $1/n$ of the preceding numbers can be $1$.
So $A_1$ is the set of all binary strings of infinite length, since at any
point, at most all of the preceding numbers can be $1$.  $A_2$ is the set
of strings such that at any point, at most half of the preceding terms
can be $1$.  For instance, the first element of every string in $A_2$ must
be 0, and of the first three elements, at most $1$ can be $1$.  In general,
the first $n-1$ elements of $A_n$ must be $0$.  
As a further example, the string $010101000$... $ \in A_2$, but the string
$0101011000$... $\not\in A_2$. 

Prove that $A_{501}$ is uncountable.

\solution{
{\bf Solution:}
The proof is by diagonalization.  Assume for the purposes of
contradiction that the set is countable.  Then there must be
a way to list the elements in order.  Construct such a list, using
a mapping function such that $f(i)$ represents the $i$th element in
the list.  Now construct a number $a$ as follows.  For each $f(i)$, set
the $501(i)$th element of $a$ to be the opposite of the $501(i)$th element
of $f(i)$.  For all elements of $a$ not set in this manner, set them to $0$. 
Since at any point, there are at least $500$ zeroes for every one, $a$ is 
in $A_{501}$.  Therefore it must appear in this list at $a = f(j)$.  However,
$f(j)$ and $a$ differ on the $501(j)$th element of the string, so
$a \neq f(j)$, and a contradiction is reached.  Therefore $a$ cannot be in
the list and the elements of $A_{501}$ cannot be listed, therefore $A_{501}$ is
uncountable.
}

%END   Ivan's problems

%BEGIN George's problems
%%%%%%%%%%%%%%  Fall 2000 PS 8.5    %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%

\problem 
% fall98 ps7, edited
% infinity, sets

Prove or disprove the following statements about sets.

\ppart The product of a finite number of countable sets is countable.

\solution{\textbf{Solution: }
The statement is true.  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.
}

\ppart A countable union of countable sets is countable.

\solution{\textbf{Solution: }
This statement is true.  Let $\{ S_i, i \in \mathbb{N} \}$ 
be a collection of countable sets.  Write 
$S = \bigcup _{i \in \mathbb{N}} S_i$.  Since each $S_i$ is countable, 
there are bijections $f_i: \mathbb{N} \to S_i$ for all 
$i \in \mathbb{N}$.  The map $f:\mathbb{N} \times \mathbb{N} \to S$ 
given by $f(i, j) = f_i(j)$ is surjective.  Since 
$\mathbb{N} \times \mathbb{N}$ is a product of two countable sets, it is 
countable.  It follows that $S$ must be countable.
}
 
  
%%%%%%%%%%%%%%  Fall 2000   PS 8.5  %%%%%%%%%%%%%%   %%%%%%%%%%%%%%%
\problem
% fall97 ps7, Rosen 1.8 / 30
% infinity

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.

\solution{\textbf{Solution: }
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   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%END   Tina's problems


\end{problems}

\end{document}



