\documentstyle[12pt,amstex,twoside]{article}
\input{macros-course}

\begin{document}
\pset{7}{March   18, 1997}{March 31, 1997}

{\bf Reading:} Rosen 4.2.  Lecture notes 10,11,12

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Show that for all odd natural numbers $m$ there exists an $n \geq 1$ such
that $m \mid 2^n - 1$. 

\problem  Jelly beans of 8 different colors are in 6 jars.  There are 20
jelly beans of each color.  Use the pigeonhole principle to prove
that there is some jar that contains at least two beans each from two
two different colors of jelly beans.

\problem Let $F$ be the set of all functions $f: \reals \rightarrow
\{0,1\}$.  Show that there is a bijection from $2^{\reals}$ to $F$.
This is another reason for denoting power-set by $2^{\reals}$.  More
generally, $A^B$ is used to denote the set of all functions from $B$
to $A$ (in particular, for set theorists who only care about
cardinalities, $2$ denotes a two-element set).

\problem  Let $P$ be a relation on a finite set $S$ that makes $S$ into a poset.
Define a function $f$ on $S$ by $f(x) =$ the number of elements $y$ of $S$
for which $(x, y) \in P$.  Define $R$ to be the relation
$\{ (x, y): x, y \in S $ and $ f(x) \geq f(y) \}$. 
\bparts
\ppart  Prove that $R$ also makes $S$ into a poset. 
\ppart  Prove that $P \subseteq R$.
\eparts

\problem Minimal elements of posets.
\bparts

\ppart Let $(S,R)$ be a poset.  Show that $(S, R^{-1})$ is also a poset, where
$R^{-1}$ is the inverse of $R$.  

\ppart In class we used piegonhole to show that any finite poset has a
minimum element.  Give a pigeonhole-free proof using induction on the
size of the poset (that is, number of elements in the underlying set).

\ppart Combining the previous two parts, prove that every poset has a
{\em maximal} element that is not less than or equal to any other.
\eparts


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


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

\long\def\comment#1{}
\comment{
\begin{problemparts}


\ppart Let $S_k = \{n \mid |f([n])|\ge k\}$.  Prove that every $S_k$
is nonempty.

\ppart Define the function $g(k)$ to be the smallest value $n$ such
that $|f([n])| \ge k$.  Prove that $g(k)$ is well defined (ie,
specifies a unique number that exists).

\ppart Define $h(k)=f(g(k))$.  Prove that $h$ is a bijection from
$\naturals$ to $S$.

\end{problemparts}
}
\end{problems}

\end{document}
% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
% LocalWords:  Posets poset countability ie
