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

\title{Math 101\\Solution and Commentary\\for the Second Group Project}
\author{Stefan Karpinski}

\newcommand{\A}{A}
\renewcommand{\a}{a}

\newcommand{\Question}[1]{\subsection*{Question #1}}
\newcommand{\Problem}[1]{\subsection*{Problem #1}}
\newcommand{\Parts}[1]{\paragraph*{Parts #1}}
\newcommand{\Questions}[1]{\subsection*{Questions #1}}
\newcommand{\Problems}[1]{\subsection*{Problems #1}}
\newcommand{\Part}[1]{\paragraph*{Part #1}}

\newcommand{\RP}{\mathbb{R}\mathrm{P}}
\newcommand{\inter}{\cap}
\newcommand{\Inter}{\bigcap}
\newcommand{\C}{\mathbb{C}}
\newcommand{\e}{\mathrm{e}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\st}{\text{ \textit{s.t.} }}
\newcommand{\fa}{\forall}
\newcommand{\union}{\cup}
\newcommand{\Union}{\bigcup}
\newcommand{\K}{\mathcal{K}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\CP}{\mathbb{C}\mathrm{P}}
\newcommand{\Alg}{\mathbb{A}}
\newcommand{\te}{\exists\:}
\newcommand{\Z}{\mathbb{Z}}

\newtheorem{Definition}{Definition}
\newtheorem*{Definition*}{Definition}
\newtheorem{Theorem}{Theorem}
\newtheorem*{Theorem*}{Theorem}
\newtheorem{Claim}[Theorem]{Claim}
\newtheorem*{Claim*}{Claim}
\newtheorem{Corollary}[Theorem]{Corollary}
\newtheorem*{Corollary*}{Corollary}
\newtheorem{Lemma}[Theorem]{Lemma}
\newtheorem*{Lemma*}{Lemma}
\newtheorem{Proposition}[Theorem]{Proposition}
\newtheorem*{Proposition*}{Proposition}


\begin{document}

\maketitle

\Part{1.}

If $A$ and $B$ are countable then we can index them by $\N$:
\begin{align*}
A & = \{ a_{0}, a_{1}, \dots \} \\
B & = \{ b_{0}, b_{1}, \dots \}.
\end{align*}
Then we can define
\begin{align*}
c_{n} = \left\{\begin{array}{c@{\quad\text{if}\quad}l} a_{n/2} & 2 \mid n ,\\ b_{(n-1)/2} & 2 \nmid n .\end{array}\right.
\end{align*}
Then because $A$ and $B$ are distinct, we know that all the $c_{n}$ are distinct.
Thus we have shown that we can index $A \union B$ by $\N$ simply as
\begin{align*}
A \union B = \{ c_{0}, c_{1}, \dots \}.
\end{align*}
\Part{2.}

If we enumerate $A$ and $B$ as above, we can write out the elements of $A \times B$
in an infinite ``table''
\begin{align*}
\begin{matrix} (a_{0},b_{0}) & (a_{0},b_{1}) & (a_{0},b_{2}) & \dots  \\  (a_{1},b_{0}) & (a_{1},b_{1}) & (a_{1},b_{2}) & \dots  \\  (a_{2},b_{0}) & (a_{2},b_{1}) & (a_{2},b_{2}) & \dots  \\  \vdots & \vdots & \vdots & \ddots \end{matrix}
\end{align*}
Then we can enumerate the entire teble by traversing diagonals up
and left repeatedly
\begin{align*}
A \times B = \{ (a_{0},b_{0}), (a_{1},b_{0}), (a_{0},b_{1}), 
(a_{2} ,b_{0} ), (a_{1} ,b_{1} ), (a_{0} ,b_{2} ), \dots \}
\end{align*}
Thus $A \times B$ is countable.

\Part{3.}

The idea of the proof is that we begin with any list of decimals expansions
of reals in the interval $(0,1)$:
\begin{align*}
 & 1 \mapsto 0.\underline{1}23456789\dots \\
 & 2 \mapsto 0.7\underline{7}7777777\dots \\
 & 3 \mapsto 0.31\underline{4}159265\dots \\
 & 4 \mapsto 0.100\underline{0}00000\dots \\
 & 5 \mapsto 0.2468\underline{1}0121\dots \\
 & \vdots
\end{align*}
Whatever we may have crammed onto this list in whatever clever way we may have
constructed it, we can always construct a decimal which is not on this list by
going down the diagonal and changing each digit.  This may be acheived more
specifically by taking the not-necessarily-new diagonal decimal $d$ (in this case
$d = 0.17401\dots$, with digits those underlined above) and changing each of its
digits, so that the new number given is different from the $n$\/th listed
decimal at the $n$\/th decimal place, so that our new number cannot be on the
list we started with. For example, we could take our new decimal $n =
0.25319\dots$ in this case.

There are two annoying problems to be addressed (and they both stem from the
essential flaw with decimal expansion which makes decimals usually more
irritating and painful to deal with in abstract mathematics than is worthwhile
for the conceptual ease they afford): while we know by the principle of nested
closed intervals for the real line that every decimal expansion corresponds to a
real number, this correspondence is \textit{not} injective (but it is surjective).  It
doesn't fail by very much, but the failure is enough to make things really
annoying. The problem is that we have
\begin{align*}
1.\overline{0} & = 0.\overline{9} \\
0.12345679\overline{0} & = 0.12345678\overline{9}
\end{align*}
where the overline means that those digits (only one in each case here) repeat
forever.  Fortunately these are the only cases---the worst that injectivity ever
fails is by sending two decimal expansions to the same real number, never three
of four or more---and only pairs of otherwise matching numbers ending in
repeating $0$ or $9$ will get paired like this.  So the fear is that while our new
decimal expansion $n$ my not be one of the decimal expansions on the list, it
might represent the same real number in $(0,1)$ as one of the decimals on the
list.  We can fix this by never changing the digit $0$ in $d$ to $9$ in $n$ and vice
versa.  (Convince yourself that this fixes the problem.)

The other problem is that we could concievably end up with $n = 0.9999\dots$,
which is not in $(0,1)$ at all so we have not even produced the decimal expansion
of a new real number in $(0,1)$.  This is of course related to the previous
problem but is not \textit{a priori} fixed by the solution to the other problem.
However, we don't need to change our procedure at all, we merely need assert
that our list of decimal expansions must begin with say $0.9000\dots$, so that $n =
0.9999\dots$ becomes impossible.  This does not affect our proof that $(0,1)$ is
uncountable since if we were hoping to list all the reals in $(0,1)$ then $0.9$ will
surely be in that list at some point.  All we've done here is move it to the
front of the list which is clearly harmless.

\begin{center}---\textit{beginning of rant and rave}---\end{center}

These nitpicking, silly little problems and their inelegant fixes are one of
the reasons why no one uses decimal expansions in mathematics.  It's just messy.
Moreover, if we're dealing with a rational number then, while we know that we
\textit{can} write out an exact decimal expansion for that number (allowing repeating
degits at the end, which is also messy of course), fractional form (especially
reduced fractional form) tells us far more about the mathematical properties of
that number than the decimal form does.  If we're dealing with an irrational
number then we can't even hope to write out an exact decimal expansion (since
the expansion never terminates and never repeats), whereas most of the
irrationals that one deals with are expressible exactly with radicals (possibly
nested radicals).  There are so few numbers which occur often but aren't exactly
expressible that we have simply named the most important ones: $\pi$,\/ $\e$---and I
can't even think of any more.

The question of which algebraic numbers---i.e. numbers which are roots of
rational polynomials---can and cannot be expressed exactly with radicals is a
very interesting one which is answered using Galois Theory in Math $123$. This is
widely considered some of the most beautiful material in all of mathematics,
and is really worth taking if you have the time and the interest. Math $122$ is
absolutely wonderful stuff too: groups, rings, fields and the better parts of
linear algebra ($21b$ is definitely the worse parts of linear algebra).

The one advantage that decimal representation does offer, which is precisely
what makes it so popular with everyone besides mathematicians, is that it lets
you immediately tell how big the number in question is.  You can immediately see
which two integers it lies between, and which tenths of integers, etc.  In the
real world we don't really care about exact expressions for insoluable
algebraics (algebraic numbers which cannot be expressed with radicals) or even
about the number-theoretic properties of rational numbers.  Numbers are for
most people just a way of measuring how big things are.  So we want primarily
to be able to tell how big our numbers are as easily and quickly as possible.
Decimals allow precisely that.

\begin{center}---\textit{end of rant and rave}---\end{center}

The colors of the spectrum as conventionally thought of form a continuum and
hence have the cardinality of the continuum---i.e. the real numbers.  Whether
the actually are a continuum of possible colors is a question which quantum
mechanics throws into doubt and I don't really know enough about the matter to
say whether color is completely quantized or whether there are bits of
uncountable continuum in the spectrum.  On the other hand, we can list all
possible words written in the standard Roman alphabet (or any other finite
alphabet for that matter) in what is known as lexicographic order.
Lexicographic order begins with words of length $0$---there's only one, the
empty string (and we're not really considering it here), then words of length
$1$---there are $k$ of them if our alphabet has $k$ symbols---then the $k^{2}$ words of
length $2$, etc. Since there are only fintitely many words of a given length, we
will eventually get to all of the words of any length.  So there must be only
countably many possibly names for colors. The obvious conclusion is that we
could never possibly name all the colors of the spectrum even if we were
somehow able to define an infinite number of color names.

\Part{4.}

The algebraic numbers are countable.  To show this, we begin by showing that
there are only countably many polynomials with rational coefficients.  We can
list the rational polynomials.  To do this we consider a polynomial as a
``word'' spelled out by its coefficients.  A word of length $n$ corresponds to a
polynomial of degree $n$ (the degree of a non-constant polynomial is the
greatest power of $x$ with non-zero coefficient; the degree of a constant
polynomial is $0$).  However we cannot use lexicographic order since the
``alphabet'' in this situation is $\Q$ and is not finite so there are no longer
only finitely many words of a given length. However, there are only countably
many words of a given length (since the set of words of length $n$ with alphabet
$A$ is just the set of ordered $n$-tuples and elements of $A$---i.e. $A^{n} = A \times
\dots \times A$---which is countable). Suppose that we write $p_{n,m}$ for the $m$\/th
polynomial of degree $n$.  Then we can write all of the rational polynomials in
a table:
\begin{align*}
\begin{matrix} p_{0,1} & p_{0,2} & p_{0,3} & \dots  \\  p_{1,1} & p_{1,2} & p_{1,3} & \dots  \\  p_{2,1} & p_{2,2} & p_{2,3} & \dots  \\  \vdots & \vdots & \vdots & \ddots \end{matrix}
\end{align*}
From here we can list them all as before by traversing diagonals up and right:
\begin{align*}
\begin{matrix} p_{0,1} & p_{1,1} & p_{0,2} & p_{2,1} & p_{1,2} & p_{0,3} & \dots \end{matrix}
\end{align*}
So, having established that the rational polynomials themselves are countable
we use this to show that the algebraic numbers---i.e. the roots of rational
polynomials---are also countable.  Each polynomial of degree $n$ has at most $n$
different roots in the complex plane.  So in our previous list, we can just
replace each polynomial by the list of its roots and get a list of all the
possible roots of polynomials.  The only consideration is that each algebraic
number is listed repeatedly (a lot of times---i.e. infinitely many times
each). However, that's not a problem since we've produced a surjection from
the natural numbers to the algebraic numbers, which is sufficient to show
countability of the algebraic numbers.  We already know that $\R$ is uncountable
and now we've extablished that $\Alg$ (the standard notation for the algebraic
numbers) is countable, so $\R - \Alg$---the transcendental numbers---must be
uncountable to account for the missing stuff (like the black matter in the
universe that the cosmologists are scrambling to find).

\Part{5.}

Let $A$ be a set.  Suppose that we have a surjection $f\colon  A \rightarrow 2^{A}$.  (Here, as
usual, $2^{A}$ denotes the power set of $A$.)  Then we may consider the set
\begin{align*}
T = \{ x \in A : x \notin f(x) \}.
\end{align*}
$T \in 2^{A}$ (since $T \subseteq A$) and $f$ is surjective so there exists $t \in A$
such that $f(t) = T$. The killer question is ``is $t$ an element of $T$ or not?''  If
it is then it shouldn't be and if it isn't then it should be.  This is the
quintessential contradiction.  Cantor, you genius.

\Part{6.}

The identity function on a given set shows reflexivity of $\sim$.  Since the
composition of bijections is a bijection, $\sim$ is also transitive.  Finally, $\sim$
is symmetric since bijections are invertible and the inverse of a bijection is
also a bijection.

To put it mildly, there are \textbf{\/a lot} of cardinals.  There are so many
cardinals that the cardinals cannot be put into a set. If we could form the
set of all cardinals then what we would really have is a set containing a
bunch of equivalence classes---i.e. sets---in which every possible set appears
somewhere---including (and here's the kicker) the presumed set of all
cardinals.  So we have a set being an element of one of its elements and
that is the sort of problematic situation that is disallowed by every sane
model of set theory including the ``naive'' one that we've been using in this
class.  Recall that this sort of situation is problematic because it allows
the construction of things like ``the set of all sets that don't contain
themselves'' or whatever your favorite deviant non-set might be.

\Part{7.}

It is quickly clear that $\preceq$ is reflexive and transitive (by the same
arguments as the first part of $6$). A much deeper question is whether it
satisfies the final property of partial orders: does $A \preceq B$ and $B \preceq
A$ imply $A \sim B$?  The Schr\"oder-Bernstein Theorem is the affirmative answer to
this question.

An even deeper question is whether $\preceq$ actually forms a
total order on any collection of sets $S$. It requires an additional and
somewhat controversial (though very widely accepted) axiom, known as the Axiom
of Choice, to show that this is in fact the case and that any pair of sets are
comparable by the $\preceq$ relation.

\Part{8.}

Sorry, I wrote this all out with $X$ and $Y$ instead of $A$ and $B$ and now I don't
want to change it so let $f\colon  X \rightarrow Y$ and $g\colon  Y \rightarrow X$ be injections and
forget about $A$ and $B$.  Denote the elements of $X$ which originate in $X$ by $X_{X}$
and those that originate in $Y$ by $X_{Y}$.  Denote the elements of $X$ which have
infinte ancestry by $X_{\infty}$. Similarly we define $Y_{X}$,\/ $Y_{Y}$ and $Y_{\infty}$.
Clearly these are all pairwise disjoint and moreover,
\begin{align*}
X & = X_{X} \union X_{Y} \union X_{\infty} \\
Y & = Y_{X} \union Y_{Y} \union Y_{\infty}.
\end{align*}

 Now a little notation.  If $A \subseteq X$ and $h\colon  X \rightarrow Y$, we write $h|_{A}$ for the
function $h|_{A} \colon A \rightarrow Y$ that ``agrees'' with $h$.  This is known as the
restriction of $h$ to $A$.  If $B \subseteq Y$ such that the image of $h|_{A}$ is
contained in $B$ we may also write simply $h|_{A}$ for the doubly restricted
function $h|_{A} \colon A \rightarrow B$.  (Doubly restricted since both its domain and
range are restricted, not just the domain as in the previous case.) This is
not technically the same function but restricting the range in this manner
doesn't really change anything essential about the function so we allow
ourselves this convenient little notational ambiguity.

With this notation, we may observe that the functions
\begin{align*}
f|_{X_X}  & \colon X_{X} \rightarrow Y_{X} \\
g^{-1} |_{X_Y} & \colon X_{Y} \rightarrow Y_{Y} \\
f|_{X_\infty} & \colon X_{\infty} \rightarrow Y_{\infty} \\
g^{-1} |_{X_\infty} & \colon X_{\infty} \rightarrow Y_{\infty}
\end{align*}
are all bijections with respective inverses
\begin{align*}
f^{-1} |_{Y_X} & \colon Y_{X} \rightarrow X_{X} \\
g|_{Y_Y} & \colon Y_{Y} \rightarrow X_{Y} \\
f^{-1} |_{X_\infty} & \colon Y_{\infty} \rightarrow X_{\infty} \\
g|_{X_\infty} & \colon Y_{\infty} \rightarrow X_{\infty}
\end{align*}
This is actually more functions than we need and we can ``glue'' them together
in two different ways to get two possible obvious choices for bijections from
$X$ to $Y$ (ok maybe they're not that obvious):
\begin{align*}
h(x) = \left\{\begin{array}{c@{\quad\text{if}\quad}l} f(x) & x \in X_{X} \union X_{\infty},\\ g^{-1}(x) & x \in X_{Y}.\end{array}\right.
\end{align*}
or
\begin{align*}
k(x) = \left\{\begin{array}{c@{\quad\text{if}\quad}l} f(x) & x \in X_{X},\\ g^{-1}(x) & x \in X_{Y} \union X_{\infty}.\end{array}\right.
\end{align*}
These have inverse bijections
\begin{align*}
h^{-1}(y) = \left\{\begin{array}{c@{\quad\text{if}\quad}l} f^{-1}(y) & y \in Y_{X} \union Y_{\infty},\\ g(y) & y \in Y_{Y}.\end{array}\right.
\end{align*}
and
\begin{align*}
k^{-1}(y) = \left\{\begin{array}{c@{\quad\text{if}\quad}l} f^{-1}(y) & y \in Y_{X},\\ g(y) & y \in Y_{Y} \union Y_{\infty}.\end{array}\right.
\end{align*}

 I know this may seem really confusing, but its not as bad as it seems. Just
read it over again slowly and think about it for a while.  Then take two
Aspirin and call me in the morning.

\Part{9.}

Rather than trying to directly produce a bijection between $\R$ and $2^{\Z^+}$,\/ I
will instead produce an injection each way and then the Schr\"oder-Bernstein
Theorem (part $8$) tells us how to make a bijection from this pair of
injections.

First I'll cook up the injection from $2^{\Z^+}$ into $\R$.\/  $A$ subset of $\Z^{+}$ can
be considered as a sequence of zeros and ones:
\begin{align*}
\{5\} & \longleftrightarrow (0, 0, 0, 0, 1, 0, 0, 0, \dots) \\
\{1, 3, 5, 7, \dots\} & \longleftrightarrow (1, 0, 1, 0, 1, 0, 1, 0, \dots) \\
\{2, 4, 6, 8, \dots\} & \longleftrightarrow (0, 1, 0, 1, 0, 1, 0, 1, \dots).
\end{align*}
The $n$\/th element of the sequence on the right is $1$ if and only if $n$ is an
elment of the set on the left.  Well this is suddenly very suggestive of
decimal expansions.  We may make a function $2^{\Z^+} \rightarrow \R$ by sending
\begin{align*}
\{5\} & \mapsto 0.00001000\dots \\
\{1, 3, 5, 7, \dots\} & \mapsto 0.10101010\dots \\
\{2, 4, 6, 8, \dots\} & \mapsto 0.01010101\dots
\end{align*}
If the decimal expansions are considered as binary ``decimal'' expansions
(properly called just binary expansions) then this is not injective since it
sends $\{1\} \mapsto 0.1\overline{0}$ and $\{2,3,4,\dots\} \mapsto 0.0\overline{1}$ but in
binary $0.1\overline{0} = 0.0\overline{1}$ so injectivity fails.  But if we
use any base besides $2$, we no longer have this problem since $0.1\overline{0}
\neq 0.0\overline{1}$ in other bases.

Now we need an injection from $\R$ to $2^{\Z^+}$.  We know that $\Q$ is countable so
let $f\colon  \Z^{+} \rightarrow \Q$ be a bijection.  We know from the contruction of the reals
by Dedekind cuts that a real number is (by definition) uniquely identified by
the set of rational numbers which are strictly less then it---i.e. its
Dedekind cut.  A Dedekind cut is a subset of $\Q$ but via $f$ we may turn it into
a subset of $\Z^{+}$.  This gives us an injective function from $\R$ to $2^{\Z^+}$:
\begin{align*}
x \mapsto \{ n \in \Z^{+} : f(n) < x \}.
\end{align*}
Convince yourself that this is injective.

I'm not sure what to say about the continuum hypothesis.  It's famous.  It's
been proven unprovable.  There's not much to say to that except ``Wow.  Crazy,
man.''  	

\Part{10.}

You know the deal here.



\end{document}
