\documentclass[12pt,twoside]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{graphics}
\input{macros-course}
\begin{document}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}

\newcommand{\solution}[1]{}
\pset{7}{October 20, 1998}{Start of class on October 27, 1998}

%\newcommand{\solution}[1]{\bigskip #1}
%\psol{7}{October 30, 1998}

\centerline{\bf Read sections 4.1, 4.2, and 4.3 in Rosen.}

\begin{problems}

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

%  Largely stolen from Fall 97.

\problem {\bf (10 points)} For each of the functions below, determine
whether the function is injective, whether it is surjective, and
whether it is bijective.  No proofs are required.

\begin{problemparts}
\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ defined by
$f(x)=e^x$

\solution{ The function is injective because $e^x = e^y$ if and only
if $x = y$.  The function is not surjective, because $e^x$ never takes
on non-positive values.  The function is not bijective, because it is
not surjective.  }

\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}^+$
defined by $f(x)=e^x$.  (Here $\mathbb{R}^+$ denotes the set of
positive real numbers.)

\solution{The function is injective as before, but is now also surjective
because for every $y \in \mathbb{R}^+$, there exists an $x$ (namely $x
= \ln y$) such that $y = e^x$.  Therefore, the function is bijective.}

\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ defined
by $(x+1)/(x^2+1)$

\solution{ The function is not injective, because $f(0) = f(1) = 1$.
The function is not surjective, because the function never takes on
large positive or negative values.  The function is not bijective
because it is neither injective nor surjective.}

\problempart The function $f : \mathbb{R} \mapsto \mathbb{R}$ defined
by

\begin{eqnarray*}
f(x) & = & \left\{
\begin{array}{cl}
1/x & \text{for $x \neq 0$} \\
0 & \text{for $x = 0$.}
\end{array}
\right.
\end{eqnarray*}

\solution{ The function is injective, because $f(x) = f(y)$ if and
only if $x = y$.  The function is surjective, because for all $y \in
\mathbb{R}$, there exists an $x$ (namely $x = 1 / y$ or $x = 0$) such
that $f(x) = y$.  Therefore, the function is also bijective.}

\end{problemparts}


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

\problem {\bf (10 points)} Suppose that $f$ is a function of the form
$f: A \mapsto B$, and $g$ is a function of the form $g: B \mapsto C$.
The composed function $g \circ f$ has domain $A$, range $C$, and is
defined by $(g \circ f)(a) = g(f(a))$.

\begin{problemparts}

\problempart Prove that if the composition $g \circ f$ is a bijection,
then $f$ is an injection and $g$ is a surjection.

\solution{
\begin{proof}
Suppose that $g \circ f$ is a bijection.

Assume for the purpose of contradiction that $f$ is not an injection.
Then there exist elements $a_1, a_2 \in A$, such that $f(a_1) =
f(a_2)$.  This implies that $g(f(a_1)) = g(f(a_2))$.  Therefore, $g
\circ f$ is not an injection and thus not a bijection.  This is a
contradiction; therefore, $f$ must be an injection.

Now assume for the purpose of contradiction that $g$ is not a
surjection.  Then there exists an element $c \in C$ such that for all
$b \in B$, $g(b) \neq c$.  Therefore, for all $a \in A$, $g(f(a)) \neq
c$.  This implies that $g \circ f$ is not a surjection and thus not a
bijection.  This is again a contradiction; therefore $g$ must be a
surjection.
\end{proof}
}

\problempart If $f$ is an injection and $g$ is a surjection, then is
$g \circ f$ necessarily a bijection?

\solution{
No.  For example, consider the following setup.

\begin{eqnarray*}
A & = & \{ 1 \} \\
B & = & \{ 1, 2 \} \\
C & = & \{ 1, 2 \} \\
\\
f(x) & = & x \\
g(x) & = & x
\end{eqnarray*}

In this case, $f$ is injective, $g$ is surjective, but $g \circ f$ is
not bijective.  }

\end{problemparts}

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

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

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

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

\problempart Prove there exists at least one transcendental number.

\end{problemparts}

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

% Wantonly stolen from Brualdi.

\problem {\bf (15 points)} Prove that among every set of $52$
integers, there exists a pair with sum or difference divisible by 100.

\solution{ We assign each of the 52 numbers to one of 51 bins, which
are defined as follows.

First, we define 49 ``ordinary'' bins.  Let bin 1 contain numbers
congruent to 1 or 99 modulo 100.  Let bin 2 contain numbers congruent
to 2 to 98 modulo 100.  Continuing in this vein, let bin 49 contain
numbers congruent to 49 or 51 modulo 100.  Now we define two
``special'' bins.  Let bin 0 contain numbers congruent to 0 modulo
100, and let bin 50 contain numbers congruent to 50 modulo 100.

By the Pigeonhole Principle, at least two numbers are assigned to the
same bin.  If two numbers are assigned to an ordinary bin and are
congruent modulo 100, then their difference is divisible by 100.  If
two numbers are assigned to an ordinary bin and are not congruent
modulo 100, then their sum is divisible by 100.  If two numbers are
assigned to a special bin, then both their sum and their difference is
divisible by 100.
}

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

%  These are mostly stolen from Brualdi.

\problem {\bf (25 points)} Theory Pig has often complained that the
name ``Pigeonhole Principle'' is verbose and awkward.  He proposes the
more concise term ``Pig Principle'' for the same idea.  Recently, he
devised a couple problems involving this idea in order to promote his
terminology.

\begin{problemparts}
\problempart Suppose that $m$ pigs are lined up, and each pig is given
one or more tasty treats.  Prove that there is always a set of pigs
that are consecutive in the lineup and that all together receive a
number of treats that is a multiple of $m$.

For example, suppose that there are $m = 5$ pigs, and that they
receive 1, 6, 2, 7, and 9 treats respectively.  Then the claim holds
in this case, because the second, third, and fourth pigs received $6 +
2 + 7 = 15$ treats altogether, and 15 is a multiple of 5.

\solution{ Let $P_i$ be the total number of treats given out to the
first $i$ pigs.  There are two cases.  In the first case, suppose that
at least one of $P_1, P_2, \ldots, P_m$ is congruent to 0 modulo $m$.
In particular, suppose that $P_j$ is congruent to 0 modulo $m$.  This
implies that the number of treats received by the first $j$ pigs is a
multiple of $m$, and so the claim holds.  In the second case, suppose
that none of $P_1, P_2, \ldots, P_m$ is congruent to 0 modulo $m$.
Then each of the $m$ terms $P_1, P_2, \ldots, P_m$ is congruent to one
of the $m-1$ values $1, 2, \ldots, m-1$ modulo $m$.  By the Pig
Principle, there are at least two terms $P_j$ and $P_k$ that are
congruent to the same value modulo $m$.  Thus pigs $j+1, j+2, \ldots,
k$ received a total of $P_k - P_j$ treats, which is a multiple of $m$.
}

\problempart Suppose that during each day of an 13-week term, a
certain theoretically-inclined pig receives at least one affectionate
pat.  However, suppose that this pig never receives more than 12 pats
in any one of the 13 weeks, on account of his being underappreciated
by the TA staff.  Prove that there exists a sequence of consecutive
days during which the pig receives exactly 25 affectionate pats.

\solution{ Let $P_i$ be the total number of pats that the pig receives
in the first $i$ days.  Since he gets least one pat every day, the
sequence $P_1, P_2, \ldots, P_{91}$ is strictly increasing.  Since he
gets at most 12 pats per week, the final term, $P_{91}$, is at most $13
\cdot 12 = 156$.  Now the sequence $P_1 + 25, P_2 + 25, \ldots, P_{91}
+ 25$ is also strictly increasing, and the largest term, $P_{91} + 25$,
is at most $156 + 25 = 181$.  Therefore, the 182 values $P_1, \ldots,
P_{91}$ and $P_1 + 25, \ldots, P_{91} + 25$ all lie between 1 and 181.
By the Pig Principle, at least two of these values must be the same.
Since no two of the numbers $P_1, \ldots, P_{91}$ are equal, and no
two of the numbers $P_1 + 25, \ldots, P_{91} + 25$ are equal, there
must be an $i$ and a $j$ such that $P_i = P_j + 25$.  This implies
that on days $j+1, j+2, \ldots i$, the pig receives exactly 25
affectionate pats.

\bigskip

Fat chance.
}

\end{problemparts}

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

\end{problems}
\end{document}

