\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}

\newcommand\from{\colon}
\newcommand\R{\mathbb{R}}
\newcommand\Z{\mathbb{Z}}
\newcommand{\cl}{\mathbf{K}}


\begin{document}
\begin{center}
\Large{Math 101 Group Project \#2}

{Cardinality}
\end{center}
\


Let $A$ and $B$ denote sets.  We say $A$ and $B$ have the same {\bf
cardinality} and write $A \sim B$ iff there is a bijection between $A$ and
$B$.  We write $A \preceq B$ and say that $A$ has smaller cardinality
than
$B$ iff there is a one-to-one function from $A$ to $B$.  A set $A$ is
countable iff $A \preceq \mathbb Z^+$.


\begin{enumerate}
\item
Let $A$ and $B$ be two disjoint countable sets.  Show that their union $A
\cup B$ is countable.

\item
As sketched in class, show that the Cartesian product $A \times B$ of two
countable sets $A$ and $B$ is countable.  Give details of what this lets you
conclude about the rationals.

\item
As sketched in class, show that the open unit interval (0,1) is not
countable.  Discuss what cardinality you think the set of all colors of the
spectrum has.  How about the set of all the possible words you
could make up to name colors using the English alphabet?

\item
A real number $a$ is called algebraic if there is a polynomial $p(x)$ with
rational coefficents such that $p(a)=0$.  Give some examples.  Do
there exist non-algebraic reals?  Show that there are actually
uncountably many.  They are called transcendental numbers because,
as Euler put it, ``they transcend the power of algebraic methods.''
Even though you can show in this way that there must be lots, it turns
out to be quite a bit harder to produce any specific examples.

\item
Cantor's Theorem says that the power set $\wp (A)$ of any set
$A$ satisfies $A \prec \wp (A)$, meaning that $A \preceq \wp
(A)$ but $A \not \sim \wp (A)$.  Give a proof of this by
mimicking the proof we did in class that $\wp (\mathbb Z^+)$
is uncountable.

\item
Let $S$ be a collection of sets.  Show that $\sim$ defines an equivalence
relation on $S$.  An equivalence class of sets under $\sim$ is sometimes
called a cardinal.  How many different cardinals do you think
there are?

\item
Let $S$ be a collection of sets.  Must $\preceq$ define a
partial order on
$S$?  Explain.


\item
The Shr$\rm \ddot o$der-Bernstein Theorem states that if $A \preceq B$
and $B
\preceq A$, then $A \sim B$.  Give a proof by filling in the details of the
following sketch.  Let $f:A \to B$ and $g:B \to A$ denote bijections.  Call
$x \in A$ the parent of $f(x) \in B$ and call $y \in B$ the parent of $g(y)
\in B$.  Each $x \in A$ has an infinite sequence of descendants, namely,
$f(x), g(f(x)), f(g(f(x))),$ etc. and similarly for $y \in B$.  We say
each tern in such a sequence is an ancestor of all the following
terms.  If you keep tracing back the ancestry of an element in either
$A$ or $B$ back as far as possible, then there are only three
possibilities:  you come to an element of $A$ with no parent (these
orphans are exactly $A-g(B)$); or you come to an element of $B$ with
no parent; or the lineage goes back forever.   Partition $A$ and $B$
accordingly and find three one-to-one functions that combine to give
the desired one-to-one correspondence from $A$ to $B$.  Note: try
drawing a figure to illustrate what is happening.

\item
Show that $\mathbb R$ has the same cardinality as
$\wp (\mathbb Z^+)$, the power set of the positive
integers.  With Cantor's Theorem in mind, we can think of
this as saying that $\mathbb R$ is bigger than $\mathbb
Z^+$.  Is there anything in between?  That is, does there
exist a set $X$ such that $\mathbb Z^+ \preceq X \preceq
\mathbb R$ with neither $X \sim \mathbb Z^+$ nor $X \sim
\mathbb R$?  In 1878, Cantor conjectured there is no such set
$X$.  Hilbert put this conjecture, called the continuum
hypothesis, at the top of the famous list he made in 1900
of the most important unsolved problems for the new
century.  Based on G$\rm \ddot o$del's work of 1939,
Paul Cohen finally showed in 1963 that this question is
formally undecidable.  In other words, he proved that, with
the axioms, proof techniques, and set theory accepted by
most mathematicians, it is impossible to prove the
continuum hypothesis and it is impossible to disprove the
continuum hypothesis.


\item
Make up questions that would be suitable for a hour exam in this course.

\end{enumerate}

\end{document}


