\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
%END   Joe's problems

%BEGIN Ray's problems



%%%%%%%%%%%%%% 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)
%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

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

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


\end{problems}

\end{document}



