%% Process me in latex2e.

% BEGIN PREAMBLE

\documentclass[12pt]{article}
\pagestyle{empty}   % no page numbers
\nofiles % no aux file


% fonts:
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{latexsym}  % latex2e symbol package

% if needed, to get the format right:
 \addtolength{\textwidth}{4mm}
 \addtolength{\oddsidemargin}{-2mm}
 \addtolength{\textheight}{20mm}
 \addtolength{\topmargin}{-10mm}



\newcommand\PP{\mathcal{P}}

\newcommand\RRR{{\mathbb R}} 
\newcommand\QQQ{{\mathbb Q}} 

\newcommand\dom{\mathrm{dom}}
\newcommand\ran{\mathrm{ran}}

\newcommand\eqcard{\approx}  % = in cardinality

% an itemize-like environment, without such large spacing
\newenvironment{itemizz}{\begin{itemize}\setlength{\itemsep}{-1mm}}
{\end{itemize}}

% END PREAMBLE

\begin{document}


\begin{center}
MATH 770 HOMEWORK 2 \\
{\it Semester I, 2006-2007} \\
{\it Due October 5}
\end{center}


For 6,7, use your informal knowledge of the real numbers;
8,9,10 can be worked using the axioms we've already discussed.


\bigskip

\textbf{6.} Define 1-1 maps from $\RRR$ into $\PP(\omega)$
and from $\PP(\omega)$ into $\RRR$.  This does not require the
Axiom of Choice, so you should give an explicit definition of the maps,
but in mapping $\RRR$ into $\PP(\omega)$, you may assume that it's
well-known that there's a (computable) bijection from $\omega$
onto $\QQQ$.  Going the other way, you might observe:
$\PP(\omega) \eqcard 2^\omega \eqcard 
\mbox{the Cantor set} \subset \RRR$; the second $\eqcard$ is
a homeomorphism.

\bigskip


\textbf{7.}
Prove that the following are equivalent for an ordinal $\alpha$:
\begin{itemizz}
\item[1.] $\alpha$ is isomorphic to a subset of $\RRR$.
\item[2.] $\alpha$ is isomorphic to a subset of $\QQQ$ which is
closed as a subset of $\RRR$.
\item[3.] $\alpha$ is countable.
\end{itemizz}
\textit{Hint.}
$(2) \to (1)$ is trivial.
$(1) \to (3)$ holds because an uncountable well-ordered subset of $\RRR$
would yield an uncountable family of disjoint open intervals,
which is impossible because $\QQQ$ is countable and dense in $\RRR$.
For $(3) \to (2)$, you can induct on $\alpha$; note that your set must
be unbounded when $\alpha$ is a limit ordinal and compact when
$\alpha$ is a successor.

\textit{Remark.}  The countable compact
Hausdorff spaces are precisely the countable successor ordinals
with the order topology.


\bigskip


\textbf{8.} 
Prove that a set $A$ is finite
iff there is a relation $<$ such that $<$ and its
inverse relation $>$ both well-order $A$ (i.e.,
in the total order $<$, every non-empty subset of $A$ has
both a least and a greatest element).
The ``official'' definition of ``finite'' is I.11.12.


\bigskip

\textbf{9.}
Observe that the justification given in \S I.7
for $\dom(R)$ and $\ran(R)$ required the specific definition
$\langle x,y \rangle = \{\{x\}, \{x,y\}\}$, whereas
the proof, using Replacement,
that $A \times B$ exists, works with any notion of pairing.
Now, suppose that $(x,y)$ is any set we construct from
$x,y$ for which we can prove:
$$
\forall x,y,z,t [ (x,y) = (z,t) \to x = z \ \wedge \  y = t] \ \ .
$$
Prove (using Replacement) that we can form $\dom(R)$ and $\ran(R)$.


\bigskip

\textbf{10.}
Let $<$ and $\prec$ be relations such that 
$<$ totally orders $S$ strictly and
$\prec$ totally orders $T$ strictly.
Let $\vartriangleleft$ be their lexicographic product on $S \times T$.
Prove that 
$\vartriangleleft$ totally orders $S \times T$ strictly and
that if also $<$ , $\prec$ well-order $S$ , $T$ , respectively, then
$\vartriangleleft$ well-orders $S \times T$.



\end{document}