% Descriptive Set Theory and Forcing, A. Miller revised 4-2001
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}
\raggedbottom
%%%%%%%%% Citations %%%%%%%%%%%%
\newwrite\citeno
\immediate\openout\citeno=dstfor.cit
\def\site#1{{\cite{#1}}\write\citeno{#1 \thepage}}
%% This writes a file "dstfor.cit" with page numbers where papers are cited
%% See bibliography "Cite on page: "
%% I used external program to put page numbers after bibitem
%%%%%%%% Indexing %%%%%%%%%%%%
\newcommand{\indexentry}[2]{\par\noindent #1 \hrulefill\ #2}
\def\dex#1{{\bf #1}\index{#1}} % is boldface too much? could be \it
\def\sdex#1{\index{#1}} % silent version
%% if command characters give trouble use ? in place of \ in sdex
%% index writes to file *.idx
%% to make final index: substitute "\" for "?" then sort
%%%%%%%%% Theorems and Style %%%%%%%%%%%%%%
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{question}[theorem]{{\bf Question}}
\newcommand{\sector}[1]{\newpage\section{#1}
\markboth{#1}{Descriptive Set Theory and Forcing}}
\newcommand{\claim}{\par\bigskip\noindent {\bf Claim: }}
%%%%%%%%% Symbols %%%%%%%%%%%%%
\newcommand{\val}[1]{[\kern-2.5pt| \; #1\; |\kern-2.25pt]}
\mathchardef\wtilde="0365
\newcommand{\bpi}[2]{\vtop{\hbox{${\bf\Pi}^{#1}_{#2}$} \kern-4pt
\hbox{\kern1pt$\wtilde$}\kern-6pt}}
\newcommand{\bsig}[2]{\vtop{\hbox{${\bf\Sigma}^{#1}_{#2}$} \kern-4pt
\hbox{\kern1pt$\wtilde$}\kern-6pt}}
\newcommand{\bdel}[2]{\vtop{\hbox{${\bf\Delta}^{#1}_{#2}$} \kern-4pt
\hbox{\kern1pt$\wtilde$}\kern-6pt}}
\newcommand{\name}[1]{ \stackrel{\circ}{#1} }
\newcommand{\finseq}{\omega^{<\omega} }
\newcommand{\irrationals}{\mathbb P}
\newcommand{\integers}{\mathbb Z}
\newcommand{\cantorset}{\cantorspace}
\newcommand{\comp}[1]{\sim{#1}\-}
\newcommand{\borel}{{\rm Borel}}
\newcommand{\ord}{{\rm ord}}
\newcommand{\rank}{{\rm rank}}
\newcommand{\st}{{\rm stone}}
\newcommand{\dom}{{\rm domain}}
\newcommand{\base}{{\cal B}}
\newcommand{\ordinals}{{\rm OR}}
\newcommand{\tzero}{T^0}
\newcommand{\tone}{T^{>0}}
\newcommand{\bool}{{\mathbb B}}
\newcommand{\emptyseq}{\langle\rangle}
\newcommand{\disj}{\mathop{\vee}}
\newcommand{\MA}{{\rm MA}}
\newcommand{\dense}{{\cal D}}
\newcommand{\ideal}{{\cal I}}
\newcommand{\famly}{{\cal F}}
\newcommand{\fbool}{{\mathbb F}}
\newcommand{\posetq}{{\mathbb Q}}
\newcommand{\one}{{\mathbb 1}}
\newcommand{\interior}{{\rm int}}
\newcommand{\cl}{{\rm cl}}
\newcommand{\meager}{{\rm meager}}
\newcommand{\fin}{{\rm FIN}}
\newcommand{\cof}{{\rm cof}}
\newcommand{\cov}{{\rm cov}}
\newcommand{\sleq}{\preceq}
\newcommand{\embed}{\preceq}
\newcommand{\strictembed}{\prec}
\newcommand{\fleq}{\unlhd}
\newcommand{\fless}{\lhd}
\newcommand{\rmiff}{\mbox{ iff }}
\newcommand{\rmor}{\mbox{ or }}
\newcommand{\rmand}{\mbox{ and }}
\newcommand{\diam}{{\rm diam}}
\newcommand{\lin}{{\rm line}}
\newcommand{\notE}{\not\!\!E}
\newcommand{\hyp}{{\rm hyp}}
\newcommand{\semihyp}{{\rm semihyp}}
\newcommand{\arrow}{\rightarrow}
\newcommand{\bairespace}{\omega^{\omega}}
\newcommand{\cantorspace}{2^{\omega}}
\newcommand{\concat}{{\;\hat{ }\;}}
\newcommand{\continuum}{{\mathfrak c}}
\newcommand{\cross}{\times}
\newcommand{\forces}{\mid\vdash}
\newcommand{\infsets}{[\omega]^{\omega}}
\newcommand{\Intersect}{\bigcap}
\newcommand{\intersect}{\cap}
\newcommand{\poset}{{\mathbb P}}
\newcommand{\rationals}{{\mathbb Q}}
\newcommand{\reals}{{\mathbb R}}
\newcommand{\seq}{\omega^{< \omega}}
\newcommand{\superset}{\supset}
\newcommand{\Union}{\bigcup}
\newcommand{\union}{\cup}
\newcommand{\Conj}{\mathop{\bigwedge\kern -6pt\bigwedge}}
\newcommand{\conj}{\mathop{\wedge}}
\newcommand{\eq}{\approx}
\newcommand{\isom}{\simeq}
\newcommand{\res}{\upharpoonright}
\newcommand{\propsub}{\subsetneqq}
\newcommand{\pp}{{\mathfrak p}}
\newcommand{\prm}{\rm}
%\renewcommand{\cal}{\mathcal}
\newcommand{\proof}{\par\noindent{Proof}:\par}
\newcommand{\qed}{\nopagebreak\par\noindent\nopagebreak$\blacksquare$\par}
\makeindex
\begin{document}
\pagestyle{empty}
\vskip 3in
\begin{center}
\Huge
Descriptive Set Theory
\end{center}
\begin{center}
\Huge
and
\end{center}
\begin{center}
\Huge
Forcing:
\end{center}
\bigskip
\begin{center}
{\Large How to prove theorems about Borel sets\\ }
{\Large the hard way. }
\end{center}
\vskip 3in
\begin{flushright}
Arnold W. Miller\\
Department of Mathematics\\
480 Lincoln Dr.\\
Van Vleck Hall\\
University of Wisconsin\\
Madison, WI. 53706\\
miller@math.wisc.edu\\
http://www.math.wisc.edu/$\sim$miller\\
\end{flushright}
\newpage
This page left blank.
\newpage
\setcounter{page}{0}
\begin{center}
Note to the readers
\end{center}
Departing from the usual
author's statement-I would like to say that I am not responsible
for any of the mistakes in this document. Any mistakes here are
the responsibility of the reader. If anybody wants to point out
a mistake to me, I promise to respond by saying ``but you know what
I meant to say, don't you?"
These are lecture notes from a course I gave at the University of
Wisconsin during the Spring semester of 1993. Some knowledge of
forcing is assumed as well as a modicum of elementary
Mathematical Logic, for example, the Lowenheim-Skolem Theorem.
The students in my class had a one semester course,
introduction to mathematical logic covering the completeness
theorem and incompleteness theorem,
a set theory course using Kunen \site{kunenbk}, and a model theory
course using Chang and Keisler \site{changk}. Another good
reference for set theory is Jech \site{jech}. Oxtoby \site{oxt}
is a good reference for the basic material concerning
measure and category on the real line. Kuratowski \site{kur}
and Kuratowski and Mostowski \site{kurmos} are
excellent references for classical descriptive set theory.
Moschovakis \site{mosch} and Kechris \site{kechris} are more modern
treatments of descriptive set theory.
The first part is devoted to the general area of Borel hierarchies,
a subject which has always interested me.
The results in section \ref{cohen} and
\ref{random} are new and answer questions from my thesis.
I have also included (without permission)
an unpublished result of Fremlin (Theorem \ref{frem}).
Part II is devoted to results concerning the low projective
hierarchy. It ends with a theorem of Harrington from
his thesis that is consistent to have $\bpi12$ sets of
arbitrary size.
The general aim of part III and IV is to get to Louveau's theorem.
Along the way
many of the classical theorems of descriptive set theory are
presented ``just-in-time'' for when they are needed. This technology
allows the reader to keep from overfilling his or her memory storage
device.
I think
the proof given of Louveau's Theorem \ref{louv} is also a little different.
\footnote{In a randomly infinite Universe, any event occurring here and
now with finite probability must be occurring simultaneously at
an infinite number of other sites in the Universe. It is hard to
evaluate this idea any further, but one thing is certain: if it
is true then it is certainly not original!--
The Anthropic Cosmological
Principle, by John Barrow and Frank Tipler.}
Questions
like ``Who proved what?'' always interest me, so I have included
my best guess here. Hopefully, I have managed to offend a large
number of mathematicians.
\hfill AWM April 1995
\bigskip\bigskip\bigskip
Added April 2001:
Several brave readers ignored my silly joke in the first paragraph and sent
me corrections and comments. Since no kind act should go unpunished, let me
say that any mistakes introduced into the text are their fault.
\newpage
\tableofcontents
\newpage
\setcounter{page}{1}
\pagestyle{headings}
\sector{What are the reals, anyway?}
Let $\omega=\{0,1,\ldots\}$ and let $\bairespace$ \sdex{$\bairespace$}
(\dex{Baire space}) be the
set of functions from $\omega$ to $\omega$. Let $\finseq$ \sdex{$\finseq$}
be the set
of all finite sequences of elements of $\omega$.
$|s|$\sdex{$|s|$} is the length of $s$, $\langle\rangle$ is the empty sequence,
and for $s\in\finseq$ and $n\in\omega$ let $s\concat n$\sdex{$s?concat n$}
denote the
sequence which starts out with $s$ and has one more element $n$ concatenated
onto the end.
The basic open sets
of $\bairespace$ are the sets of the form: \sdex{$[s]$}
$$[s] =\{x\in\bairespace : s\subseteq x\}$$
for $s\in\finseq$. A subset of $\bairespace$ is open iff it is the union
of basic open subsets. It is \dex{separable} (has a countable dense subset)
since it is \dex{second countable} (has a countable basis).
The following defines a complete metric on
$\bairespace$:
$$d(x,y)=\left\{\begin{array}{ll}
0 & \mbox{if $x=y$}\\
{1\over n+1} & \mbox{ if $x\res n = y\res n$ and $x(n)\not= y(n)$}
\end{array}\right. $$
\dex{Cantor space} $\cantorspace$\sdex{$\cantorspace$}
is the subspace of $\bairespace$ consisting
of all functions from $\omega$ to $2=\{0,1\}$. It is compact.
\begin{theorem} \label{eul} (Baire \site{baire})
$\bairespace$ is homeomorphic to the irrationals $\irrationals$.
\end{theorem}
\proof
First replace $\omega$ by the integers $\integers$. We will construct
a mapping from $\integers^\omega$ to $\irrationals$.
Enumerate the rationals $\rationals=\{q_n: n\in\omega\}$.
Inductively construct a sequence of open intervals
$\langle I_s : s\in \integers^{<\omega}\rangle$ satisfying the
following:
\begin{enumerate}
\item $I_{\langle\rangle}=\reals$,
and for $s\not= \langle\rangle$ each $I_s$ is a nontrivial open interval
in $\reals$ with rational endpoints,
\item for every $s\in \integers^{<\omega}$ and
$n\in \integers\;\;\; I_{s\concat n}\subseteq I_s$,
\item the right end point of $I_{s\concat n}$ is the left end point of
$I_{s\concat n+1}$,
\item $\{I_{s\concat n}: n\in \integers\}$ covers
all of $I_s$ except for their endpoints,
\item the length of $I_s$ is less than $1\over |s|$ for
$s\not= \langle\rangle$, and
\item the $n^{th}$ rational $q_n$ is an endpoint of
$I_t$ for some $|t|\leq n+1$.
\end{enumerate}
Define the function $f:\integers^{\omega}\arrow\irrationals$ as
follows. Given $x\in\integers^{\omega}$ the set
$$\Intersect_{n\in\omega}I_{x\res n}$$
must consist of a singleton
irrational. It is nonempty because
$$\mbox{closure}(I_{x\res n+1})\subseteq I_{x\res n}.$$
It is a singleton
because their diameters shrink to zero.
So we can define $f$ by
$$\{f(x)\}=\Intersect_{n\in\omega}I_{x\res n}.$$
The function $f$ is one-to-one because if $s$ and $t$ are incomparable
then $I_s$ and $I_t$ are disjoint. It is onto since for every
$u\in\irrationals$ and $n\in\omega$ there is a unique $s$ of
length $n$ with $u\in I_s$. It is a homeomorphism because
$$f([s])=I_s\intersect\irrationals$$
and the sets of the form $I_s\intersect\irrationals$ form a basis
for $\irrationals$.
\qed
Note that the map given is also an order isomorphism from
$\integers^\omega$ with the lexicographical order to $\irrationals$
with it's usual order.
We can identify $\cantorspace$ with $P(\omega)$, the set of all
subsets of $\omega$, by identifying a subset with its characteristic
function. Let $F=\{x\in\cantorspace: \forall^{\infty} n\; x(n)=0\}$
(the quantifier $\forall^{\infty}$ stands for ``for all but finitely
many $n$''). $F$ corresponds to the finite sets and so
$\cantorspace\setminus F$ corresponds to the infinite subsets of
$\omega$ which we write as $\infsets$.\sdex{$\infsets$}
\begin{theorem}
$\bairespace$ is homeomorphic to $\infsets$.
\end{theorem}
\proof
Let $f\in\bairespace$ and define $F(f)\in\cantorspace$ to be
the sequence of 0's and 1's determined by:
$$F(f)=0^{f(0)}\concat 1 \concat 0^{f(1)}\concat 1\concat 0^{f(2)}
\concat 1 \concat\cdots$$
where $0^{f(n)}$ refers to a string of length $f(n)$ of zeros.
The function $F$ is a one-to-one onto map from $\bairespace$ to
$\cantorspace\setminus F$. It is a homeomorphism because
$F([s])=[t]$ where
$t= 0^{s(0)}\concat 1 \concat 0^{s(1)}\concat 1\concat 0^{s(2)}
\concat 1 \concat\cdots\concat 0^{s(n)}\concat 1$ where $|s|=n+1$.
Note that sets of the form $[t]$ where $t$ is a finite sequence ending
in a one form a basis for $\cantorspace\setminus F$.
\qed
I wonder why $\bairespace$ is called Baire space?
The earliest mention
of this I have seen is in Sierpi\'{n}ski \site{sierp1928}
where he refers to $\bairespace$ as the 0-dimensional
space of Baire. Sierpi\'{n}ski also says that Frechet was the first
to describe the metric $d$ given above. Unfortunately,
Sierpi\'{n}ski \site{sierp1928} gives very few
references.\footnote{I am indebted to John C. Morgan II for
supplying the following reference and comment. ``Baire
introduced his space in Baire \site{baire99}. Just as coefficients
of linear equations evolved into matrices the sequences of natural
numbers in continued fraction developments of irrational numbers
were liberated by Baire's mind to live in their own world."}
The classical
proof of Theorem \ref{eul}
is to use ``continued fractions'' to get the correspondence.
Euler \site{euler} proved that every
rational number gives rise to a finite continued fraction and
every irrational number gives rise to an infinite continued fraction.
Brezinski \site{brez} has more on the history of continued fractions.
My proof of Theorem \ref{eul} allows me to remain
blissfully ignorant\footnote{ It is impossible for a man to learn
what he thinks he already knows.-Epictetus }
of even the elementary theory of continued fractions.
Cantor space, $\cantorspace$, is clearly named so because it is
homeomorphic to Cantor's middle two thirds set.
\newpage\part{On the length of Borel hierarchies}
\section{Borel Hierarchy}
\bigskip
Definitions.
For $X$ a topological space define $\bsig01$ to
be the open
subsets of $X$. For $\alpha>1$ define
$A\in\bsig0\alpha$ iff there exists a sequence $\langle B_n:n\in\omega\rangle$
with each $B_n\in\bsig0{\beta_n}$ for some $\beta_n<\alpha$ such that
$$A=\Union_{n\in\omega}\comp{B_n}$$
where $\comp{B}$ is the complement of $B$ in $X$, i.e.,
$\comp{B}=X\setminus B$. Define
$$\bpi0\alpha=\{\comp{B}: B\in\bsig0\alpha\}$$
and
$$\bdel0\alpha=\bsig0\alpha\intersect\bpi0\alpha.$$
The Borel
subsets of $X$ are defined
by $\borel(X)=\Union_{\alpha<\omega_1}\bsig0\alpha(X)$. It is clearly
the smallest family of sets containing the open subsets of $X$ and
closed under countable unions and complementation.
\sdex{$\comp{B}$}
\sdex{$?bpi0\alpha$}
\sdex{$?bdel0\alpha$}
\sdex{$\borel(X)$}
\sdex{$?bsig0\alpha$}
\begin{theorem}
$\bsig0\alpha$ is closed under countable unions,
$\bpi0\alpha$ is closed under countable intersections,
and $\bdel0\alpha$ is closed under complements.
For any $\alpha$,
$$\bpi0\alpha(X)\subseteq \bsig0{\alpha+1}(X)\rmand
\bsig0\alpha(X)\subseteq \bpi0{\alpha+1}(X).$$
\end{theorem}
\proof
That $\bsig0\alpha$ is closed under countable unions is clear from its
definition. It follows from
DeMorgan's laws by taking complements that
$\bpi0\alpha$ is closed under countable intersections.
\qed
\begin{theorem} \label{map}
If $f:X\arrow Y$ is continuous and $A\in\bsig0\alpha(Y)$, then
$f^{-1}(A)$ is in $\bsig0\alpha(X)$.
\end{theorem}
This is an easy induction since it is true for open sets
($\bsig01$) and $f^{-1}$ passes over complements and unions.
\qed
Theorem \ref{map} is also, of course,
true for $\bpi0\alpha$ or $\bdel0\alpha$
in place of $\bsig0\alpha$.
\begin{theorem} \label{subsp}
Suppose $X$ is a subspace of $Y$, then
$$\bsig0\alpha(X)=\{A\intersect X: A \in \bsig0\alpha(Y)\}.$$
\end{theorem}
\proof
For $\bsig01$ it follows from the definition of subspace.
For $\alpha>1$ it is an easy induction.
\qed
The class of sets
$\bsig02$ is also referred to as $F_\sigma$ and the
class $\bpi02$ as $G_\delta$.
Theorem \ref{subsp} is
true for $\bpi0\alpha$
in place of $\bsig0\alpha$, but not in general for $\bdel0\alpha$.
For example, let $X$ be the rationals in $[0,1]$ and Y be [0,1].
Then since $X$ is countable every subset of $X$ is
$\bsig02$ in $X$ and hence $\bdel02$ in $X$.
If $Z$ contained in $X$
is dense and codense then $Z$ is $\bdel02$ in $X$
(every subset of $X$ is),
but there is no $\bdel02$ set $Q$ in $Y=[0,1]$ whose intersection
with $X$ is $Z$.
(If $Q$ is $G_\delta$ and $F_\sigma$ and contains $Z$ then
its comeager, but
a comeager $F_\sigma$ in $[0,1]$ contains an interval.)
\sdex{$F_\sigma$}
\sdex{$G_\delta$}
\begin{theorem} For $X$ a topological space and
$\bpi01(X)\subseteq \bpi02(X)$
(i.e., closed sets are $G_\delta$), then
\begin{enumerate}
\item $\bpi0\alpha(X)\subseteq \bpi0{\alpha+1}(X)$,
\item $\bsig0\alpha(X)\subseteq \bsig0{\alpha+1}(X)$, and hence
\item $\bpi0\alpha(X)\union \bsig0\alpha(X)\subseteq \bdel0{\alpha+1}(X)$
\item $\bsig0\alpha$ is closed under finite intersections,
\item $\bpi0\alpha$ is closed under finite unions, and
\item $\bdel0\alpha$ is closed under finite intersections, finite
unions, and complements.
\end{enumerate}
\end{theorem}
\proof
Induction on $\alpha$. For example, to see that
$\bsig0\alpha$ is closed under finite intersections,
use that
$$(\Union_{n\in\omega} P_n)\intersect (\Union_{n\in\omega} Q_n)
=\Union_{n,m\in\omega} (P_n \intersect Q_m) $$
It follows by
DeMorgan's laws that
$\bpi0\alpha$ is closed under finite unions.
$\bdel0\alpha$ is closed under finite intersections, finite
unions, and complements since it is the intersection of the
two classes.
\qed
In metric spaces closed sets are $G_\delta$, since
$$C=\Intersect_{n\in\omega}\{x: \exists y \in C\;\;d(x,y)<{1\over n+1}\}$$
for $C$ a closed set.
The assumption that closed sets are $G_\delta$ is necessary since
if
$$X=\omega_1+1$$
with the order topology, then the closed set
consisting of the singleton point $\{\omega_1\}$ is not $G_\delta$;
in fact, it is not in the \dex{$\sigma$-$\delta$-lattice}
generated by the open sets
(the smallest family containing the open sets and closed under
countable intersections and countable unions).
Williard \site{will} gives an example which
is a second countable Hausdorff space.
Let $X\subseteq\cantorspace$ be any nonBorel set. Let $\cantorspace_*$
be the space $\cantorspace$ with the smallest topology containing
the usual topology and $X$ as an open set. The family of
all sets of the form $(B\intersect X)\union C$ where $B,C$ are
(ordinary) Borel subsets of $\cantorspace$ is
the $\sigma$-$\delta$-lattice
generated by the open subsets of $\cantorspace_*$,
because:
$$\Intersect_n(B_n\intersect X)\union C_n=
(\;(\Intersect_nB_n\union C_n)\intersect X)\union \Intersect_n C_n$$
$$\Union_n (B_n\intersect X)\union C_n=
((\Union_n B_n)\intersect X)\union \Union_n C_n.$$
Note that $\comp{X}$ is not in this $\sigma$-$\delta$-lattice.
M.Laczkovich has pointed out to me that the class
$\bpi03(X)$ where for the ordered space
$X=\omega _1 +1$ is not closed under finite unions:
The elements of $\bpi03$ are of the form
$\cap_{n=1}^\infty A_n$ where each $A_n$ is either open
or $F_\sigma$. This implies that $\bpi03$ contains the
open sets and the closed sets. However, the union of an open
set and a closed set is not necessarily in $\bpi03$.
Let $A$ be the set of isolated points of $\omega _1 +1$
and let $B=\{ \omega _1 \}$.
Then $A$ is open and $B$ is closed. But $A\cup B\notin \bpi03$.
Suppose $A\cup B=\cap_{n=1}^\infty A_n$,
where each $A_n$ is either open or $F_\sigma$. If $A_n$ is open
then $\omega _1 \in A_n$ implies that $A_n$ contains an unbounded
closed subset of $\omega _1$. If $A_n$ is $F_\sigma$ then
$A\subseteq A_n$ implies the same. Therefore $\cap _n A_n$ also
contains an unbounded closed subset of $\omega _1$. Thus
$A\cap B$ contains a countable limit point, which is
impossible.
\begin{theorem}\label{leb}
(Lebesgue \site{leb}) For every $\alpha$ with $1\leq\alpha<\omega_1$
$$\bsig0\alpha(\cantorspace)\not=\bpi0\alpha(\cantorspace).$$
\end{theorem}
The proof of this is a diagonalization argument applied to a
\dex{universal set}.
We will need the following lemma.
\begin{lemma}\label{univ}
Suppose $X$ is second countable (i.e. has a countable base), then
for every $\alpha$ with $1\leq\alpha<\omega_1$ there exists
a universal $\bsig0\alpha$ set $U\subseteq \cantorspace\cross X$,
i.e., a set $U$ which is $\bsig0\alpha(\cantorspace\cross X)$ such
that for every $A\in\bsig0\alpha(X)$ there exists $x\in\cantorspace$
such that $A=U_x$ where $U_x=\{y\in X: (x,y)\in U\}$.
\end{lemma}
\proof
The proof is by induction on $\alpha$. Let
$\{B_n:n\in\omega\}$ be a countable base for $X$.
For $\alpha=1$ let
$$U=\{(x,y): \exists n \;(x(n)=1 \conj y\in B_n)\}=
\Union_n(\{x:x(n)=1\}\cross B_n).$$
For $\alpha>1$ let $\beta_n$ be a sequence which sups up to $\alpha$
if $\alpha$ a limit, or equals $\alpha-1$ if $\alpha$ is a successor.
Let $U_n$ be a universal $\bsig0{\beta_n}$ set.
Let $$\langle n,m \rangle=2^n(2m+1)-1$$ be the usual pairing function
which gives a recursive bijection between $\omega^2$ and $\omega$.
For any $n$ the map $g_n:\cantorspace\cross X\arrow \cantorspace\cross X$
is defined by $(x,y)\mapsto (x_n,y)$ where $x_n(m)=x(\langle n,m\rangle)$.
This map is continuous so if we define $U_n^*=g_n^{-1}(U_n)$, then
$U_n^*$ is $\bsig0{\beta_n}$, and because the map $x\mapsto x_n$ is onto
it is also a universal $\bsig0{\beta_n}$ set. Now define $U$ by:
$$U=\Union_n \comp{U_n^*}.$$
$U$ is universal for $\bsig0\alpha$ because given any sequence
$B_n\in\bsig0{\beta_n}$ for $n\in\omega$ there exists $x\in\cantorspace$ such
that for every $n\in\omega$ we have that $B_n=(U_n^*)_{x}=(U_n)_{x_n}$ (this
is because the map $x\mapsto \langle x_n:n<\omega\rangle$ takes
$\cantorspace$ onto $({\cantorspace})^\omega$.) But then
$$U_x=(\Union_n \comp{U_n^*})_x= \Union_n \comp{(U_n^*)_x}
=\Union_n\comp(B_n).$$
\qed
\par\noindent Proof of Theorem \ref{leb}:
Let $U\subseteq\cantorspace\cross\cantorspace$ be a universal
$\bsig0\alpha$ set. Let
$$D=\{x:\langle x,x\rangle\in U\}.$$
$D$ is the continuous preimage of $U$ under the map
$x\mapsto \langle x,x\rangle$, so it is $\bsig0\alpha$, but
it cannot be $\bpi0\alpha$ because if it were, then there would
be $x\in\cantorspace$ with $\comp{D}=U_x$ and then
$x\in{D}$ iff $\langle x,x\rangle\in U$ iff $x\in U_x$ iff
$x\in \comp{D}$.
\qed
\sdex{$\ord(X)$}
Define $\ord(X)$ to be the least $\alpha$ such that
$\borel(X)=\bsig0\alpha(X)$. Lebesgue's theorem says
that $\ord(X)=\omega_1$. Note that $\ord(X)=1$ if
$X$ is a discrete space and that $\ord(\rationals)=2$.
\begin{corollary} For any space $X$ which contains a homeomorphic
copy of $\cantorspace$ (i.e., a perfect set) we have that
$\ord(X)=\omega_1$, consequently
$\bairespace$, $\reals$, and any uncountable complete separable
metric space have $\ord=\omega_1$.
\end{corollary}
\proof
If the Borel hierarchy on $X$ collapses, then by Theorem \ref{subsp}
it also collapses on all subspaces of $X$.
Every uncountable complete separable
metric space contains a \dex{perfect set} (homeomorphic copy of $\cantorspace$).
To see this suppose $X$ is an uncountable complete separable
metric space.
Construct a family of open sets
$\langle U_s: s\in 2^{<\omega}\rangle$ such that
\begin{enumerate}
\item $U_s$ is uncountable,
\item $\cl(U_{s\concat 0})\intersect \cl(U_{s\concat 1})=\emptyset$,
\item $\cl(U_{s\concat i})\subseteq U_s$ for i=0,1, and
\item diameter of $U_s$ less than $1/|s|$
\end{enumerate}
Then the map $f:\cantorset\arrow X$ defined so that
$$\{f(x)\}=\Intersect_{n\in\omega}U_{x\res n}$$
gives an embedding of $\cantorset$ into $X$.
\qed
Lebesgue \site{leb} used universal functions instead of sets, but
the proof is much the same. Corollary \ref{univdel}
of Louveau's Theorem shows that
there can be no Borel set which is universal for all
$\bdel0\alpha$ sets. Miller \site{ctblmod} contains
examples from model theory of Borel sets of arbitrary high
rank.
The notation ${\bf \Sigma^0_\alpha}, \Pi^0_\beta$ was first popularized
by Addison \site{addison}. I don't know if the ``bold face''
and ``light face''
notation is such a good idea, some copy machines wipe it out. Consequently,
I use
$$\bsig0\alpha$$
which is blackboard boldface.
\sector{Abstract Borel hierarchies}
Suppose $F\subseteq P(X)$ is a family of sets.
Most of the time we would like to think of $F$ as a countable
\dex{field of sets}
(i.e. closed under complements
and finite intersections) and so analogous to the family of
clopen subsets of some space.
We define the classes $\bpi0\alpha(F)$
analogously. Let $\bpi00(F)=F$ and for every $\alpha>0$ define
$A\in\bpi0\alpha(F)$ iff there exists $B_n\in\bpi0{\beta_n}$ for some
$\beta_n<\alpha$ such that
$$A=\Intersect_{n\in\omega}\comp{B_n}.$$
Define
\begin{itemize}
\item $\bsig0\alpha(F)=\{\comp{B}: B\in \bpi0\alpha(F)\}$,
\item $\bdel0\alpha(F)=\bpi0\alpha(F)\intersect \bsig0\alpha(F)$,
\item $\borel(F)=\Union_{\alpha<\omega_1}\bsig0\alpha(F)$, and
\item let $\ord(F)$ be the least $\alpha$ such
that $\borel(F)=\bsig0\alpha(F)$.
\end{itemize}
\sdex{$?bsig0\alpha(F)$}
\sdex{$?bpi0\alpha(F)$}
\sdex{$?bdel0\alpha(F)$}
\sdex{$\borel(F)$}
\begin{theorem} \label{bbm}
(Bing, Bledsoe, Mauldin \site{bbm}) Suppose $F\subseteq P(\cantorspace)$
is a countable family such that
$\borel(\cantorspace)\subseteq \borel(F)$. Then $\ord(F)=\omega_1$.
\end{theorem}
\begin{corollary} \label{bbmcor}
Suppose $X$ is any space containing a perfect set and
$F$ is a countable family of subsets of $X$ with
$\borel(X)\subseteq Borel(F)$. Then $\ord(F)=\omega_1$.
\end{corollary}
\proof
Suppose $\cantorspace\subseteq X$ and let
$\hat{F}=\{A\intersect\cantorspace: A\in F\}$.
By Theorem \ref{subsp} we have that
$\borel(\cantorspace)\subseteq \borel(\hat{F})$ and
so by Theorem \ref{bbm} we know $\ord(\hat{F})=\omega_1$.
But this implies $\ord(F)=\omega_1$.
\qed
The proof of Theorem \ref{bbm} is a generalization of Lebesgue's
universal set argument. We need to prove the following two
lemmas.
\begin{lemma}\label{univ2}
(Universal sets) Suppose $H\subseteq P(X)$ is countable
and define
$$R=\{A\cross B : A\subseteq\cantorspace \mbox{ is clopen and } B\in H\}.$$
Then for every $\alpha$ with $1\leq\alpha<\omega_1$ there exists
$U\subseteq\cantorspace\cross X$ with $U\in \bpi0\alpha(R)$ such that
for every $A\in \bpi0\alpha(H)$ there exists $x\in\cantorspace$ with
$A=U_x$.
\end{lemma}
\proof
This is proved exactly as Theorem \ref{univ}, replacing the basis
for $X$ with $H$.
Note that when we replace $U_n$ by $U_n^*$ it is necessary to
prove by induction on $\beta$ that for every set $A\in \bpi0\beta(R)$ and
$n\in\omega$ that
the set $$A^*=\{(x,y):(x_n,y)\in A\}$$ is also in $\bpi0\beta(R)$.
\qed
\begin{lemma} \label{diag}
Suppose $H\subseteq P(\cantorspace)$, $R$ is
defined as in Lemma \ref{univ2}, and
$$\borel(\cantorspace)\subseteq \borel(H).$$ Then for
every set $A\in\borel(R)$ the set
$D=\{x: (x,x)\in A\}$ is in $\borel(H)$.
\end{lemma}
\proof
If $A=B\cross C$ where $B$ is clopen and $C\in H$, then
$D=B\intersect C$ which is in $\borel(H)$ by assumption.
Note that
$$\{x: (x,x)\in \Intersect_n A_n\}=\Intersect_n\{x:(x,x)\in A_n\}$$
and
$$\{x: (x,x)\in \comp A\}=\comp\{x: (x,x)\in A\},$$ so the result follows
by induction.
\qed
\par\noindent Proof of Theorem \ref{bbm}:
Suppose $\borel(H)=\bpi0\alpha(H)$ and let
$U\subseteq\cantorspace\cross\cantorspace$ be universal for
$\bpi0\alpha(H)$ given by Lemma \ref{univ2}. By Lemma \ref{diag}
the set $D=\{x:(x,x) \in U\}$ is in $\borel(H)$ and hence
its complement is in $\borel(H)=\bpi0\alpha(H)$. Hence we get
the same old contradiction: if $U_x=\comp D $, then
$x\in D$ iff $x\notin D$.
\qed
\begin{theorem}\label{rec}
(Rec{\l}aw) If $X$ is a second countable space
and $X$ can be mapped continuously onto the unit interval,
$[0,1]$, then $\ord(X)=\omega_1$.
\end{theorem}
\proof
Let $f:X\arrow [0,1]$ be continuous and onto. Let
$\base$ be a countable base for $X$ and let
$H=\{f(B):B\in\base\}$. Since the preimage of an open subset
of $[0,1]$ is open in $X$ it is clear that
$\borel([0,1])\subseteq\borel(H)$. So by Corollary~\ref{bbmcor}
it follows that $\ord(H)=\omega_1$. But $f$ maps the Borel
hierarchy of $X$ directly over to the hierarchy generated by $H$,
so $\ord(X)=\omega_1$.
\qed
Note that if $X$ is a discrete space of cardinality the continuum
then there is a continuous map of $X$ onto $[0,1]$ but
$\ord(X)=1$.
The Cantor space $\cantorspace$ can be mapped continuously onto
$[0,1]$ via the map
$$x\mapsto \sum_{n=0}^{\infty} {x(n)\over 2^{n+1}}.$$
This map is even one-to-one except at countably many points
where it is two-to-one. It is also easy to see that $\reals$ can
be mapped continuously onto $[0,1]$ and
$\bairespace$ can be mapped onto $\cantorspace$. It follows that in
Theorem \ref{rec} we may replace $[0,1]$ by $\cantorspace$,
$\bairespace$, or $\reals$.
Myrna Dzamonja points out that any completely regular space $Y$
which contains a perfect set can be mapped onto $[0,1]$. This is
true because if $P\subseteq Y$ is perfect, then there is
a continuous map $f$ from $P$ onto $[0,1]$. But since $Y$ is completely
regular this map extends to $Y$.
Rec{\l}aw did not publish his result, but I did, see Miller \site{proj}
and \site{survey2}.
\sector{Characteristic function of a sequence}
The idea of a \dex{characteristic function} of a sequence of sets
is due to Kuratowski and generalized the notion of a characteristic
function of a set introduced by de le Vall\'{e}e-Poussin.
The general notion was introduced by
Szpilrajn \site{marcz}. He also exploited it
in Szpilrajn \site{marcz2}.
Szpilrajn changed his name to Marczewski soon after the outbreak
of World War II most likely to hide from the Nazis. He kept the
name Marczewski for the rest of his life.
Suppose $F\subseteq P(X)$ is a countable field of sets
(i.e. $F$ is a family of sets which is closed under complements in $X$
and finite intersections).
Let $F=\{A_n:n\in\omega\}$.
Define $c:X\arrow\cantorspace$ by
$$c(x)(n)=\left\{\begin{array}{ll}
1 & \mbox{if $x\in A_n$}\\
0 & \mbox{if $x\notin A_n$}
\end{array}\right.$$
Let $Y=c(X)$, then there is a direct correspondence
between $F$ and
$$\{C\intersect Y:\; C\subseteq\cantorspace \mbox{ clopen } \}.$$
In general, $c$ maps $X$ into $2^{|F|}$.
\begin{theorem} (Szpilrajn \site{marcz2}) \label{charseq}
If $F\subseteq P(X)$ is a
countable field of sets,
then there exists a subspace $Y\subseteq\cantorspace$ such
that $\ord(F)=\ord(Y)$.
\end{theorem}
\proof
If we define $x\eq y$ iff $\forall n\; (x\in A_n$ iff $y\in A_n)$, then
we see that members of $\borel(F)$ respect $\eq$. The preimages
of points of $Y$ under $c$ are exactly the equivalence classes of
$\eq$. The map $c$ induces a bijection between $X/\eq$ and $Y$ which
takes the family $F$ exactly to a clopen basis for the topology on $Y$.
Hence $\ord(F)=\ord(Y)$.
\qed
The following theorem says that bounded Borel hierarchies must have a top.
\begin{theorem} (Miller \site{borelhier})
Suppose $F\subseteq P(X)$ is a field of sets and
$$ord(F)=\lambda$$
where $\lambda$ is a countable limit ordinal. Then there exists
$B\in\borel(F)$ which is not in $\bpi0\alpha(F)$ for any
$\alpha<\lambda$.
\end{theorem}
\proof
By the characteristic function of a sequence of sets argument
we may assume without loss of generality that
$$F=\{C\intersect Y: \mbox{ $C\subseteq 2^\kappa$ clopen }\}.$$
A set $C\subseteq 2^\kappa$ is clopen iff it is a finite union
of sets of the form $$[s]=\{x\in 2^\kappa: s\subseteq x\}$$ where
$s:D\arrow 2$ is a map with $D\in [\kappa]^{<\omega}$ (i.e. $D$ is a
finite subset of $\kappa$). Note that by induction for every
$A\in\borel(F)$ there exists an $S\in [\kappa]^{\omega}$ (called
a support of $A$) with the property that
for every $x,y\in 2^\kappa$ if $x\res S =y\res S$ then
$(x\in A$ iff $y\in A)$. That is to say, membership in $A$ is
determined by restrictions to $S$.
\begin{lemma}
There exists a countable
$S\subseteq \kappa$ with the properties that
$\alpha<\lambda$ and $s:D\arrow 2$ with $D\in [S]^{<\omega}$ if
$\ord(Y\intersect [s])>\alpha$ then there exists
$A$ in $\bsig0\alpha(F)$ but not in $\bdel0\alpha(F)$ such that
$A\subseteq [s]$ and $A$ is supported by $S$.
\end{lemma}
\proof
This is proved by a Lowenheim-Skolem kind of an argument.
\qed
By permuting $\kappa$ around we may assume without loss of generality
that $S=\omega$. Define
$$T=\{s\in\finseq: \ord(Y\intersect [s])=\lambda\}.$$
Note that $T$ is a tree, i.e., $s\subseteq t\in T$ implies $s\in T$.
Also for any $s\in T$ either $s\concat 0\in T$ or $s\concat 1 \in T$,
because
$$[s]=[s\concat 0]\union [s\concat 1].$$
Since $\langle\rangle\in T$ it must be that $T$ has an infinite branch.
Let $x:\omega\arrow 2$ be such that $x\res n\in T$ for all $n<\omega$.
For each $n$ define $$t_n=(x\res n)\concat (1-x(n))$$ and note that
$$2^\kappa=[x]\union \Union_{n\in\omega} [t_n]$$
is a partition of $2^\kappa$ into clopen sets and one closed set $[x]$.
\bigskip
\claim For every $\alpha<\lambda$ and $n\in\omega$
there exists $m>n$ with $$\ord(Y\intersect [t_m]) >\alpha.$$
\proof
Suppose not and let $\alpha$ and $n$ witness this. Note that
$$[x\res n]=[x]\union\Union_{n\leq m<\omega} [t_m].$$
Since $\ord([x\res n]\intersect Y)=\lambda$ we know there exists
$A\in\bsig0{\alpha+1}(F)\setminus \bdel0{\alpha+1}(F)$ such
that $A\subseteq [x\res n]$ and $A$ is supported by $S=\omega$.
Since $A$ is supported by $\omega$ either $[x]\subseteq A$
or $A$ is disjoint from $[x]$. But
if $\ord([t_m]\intersect Y)\leq\alpha$ for each $m>n$,
then
$$A_0=\Union_{n\leq m <\omega} (A\intersect [t_m])$$
is $\bsig0\alpha(F)$ and $A=A_0$ or $A=A_0\union [x]$ either of which
is $\bsig0\alpha(F)$ (as long as $\alpha>1$).
This proves the Claim. \qed
The claim allows us to construct a set which is not at a level below
$\lambda$ as follows. Let $\alpha_n<\lambda$ be a sequence unbounded
in $\lambda$ and let $k_n$ be a distinct sequence with
$\ord([t_{k_n}]\intersect Y)\geq \alpha_n$. Let
$A_n\subseteq [t_{k_n}]$ be in $\borel(F)\setminus\bdel0{\alpha_n}(F)$.
Then $\union_n A_n$ is not at any level bounded below $\lambda$.
\qed
\begin{question}
Suppose $R\subseteq P(X)$ is a ring of sets, i.e., closed
under finite unions and finite intersections. Let $R_\infty$
be the $\sigma$-ring generated by $R$, i.e., the smallest family
containing $R$ and closed under countable unions and countable
intersections. For $n\in\omega$ define $R_n$ as follows.
$R_0=R$ and let $R_{n+1}$ be the family of countable
unions (if $n$ even) or family of countable intersections (if $n$ odd)
of sets from $R_n$. If $R_\infty=\Union_{n<\omega}R_n$, then
must there be $n<\omega$ such that $R_\infty=R_n$?
\end{question}
\sector{Martin's Axiom}
The following result is due to Rothberger \site{roth}
and Solovay \site{jensol}\site{marsol}. The forcing we use is
due to Silver.
However, it is probably just another view of Solovay's `almost disjoint
sets forcing'. \sdex{Martin's Axiom}
\begin{theorem}
\label{silverlem}
Assuming Martin's Axiom if $X$ is any second countable
Hausdorff space of cardinality less than the continuum,
then $\ord(X)\leq 2$ and, in fact,
every subset of $X$ is $G_\delta$.
\end{theorem}
\proof
Let $A\subseteq X$ be arbitrary and let $\base$ be a countable
base for the topology on $X$.
The partial order $\poset$ is defined as follows.
$p\in \poset$ iff $p$ is a finite consistent set of sentences of the
form
\begin{enumerate}
\item $``x \notin \name{U}_n\mbox{''}$ where $x\in X\setminus A$ or
\item $``B\subseteq \name{U}_n\mbox{''}$ where $B\in\base$ and $n\in\omega$.
\end{enumerate}
Consistent means that there is not a pair of sentences
$``x \notin \name{U}_n\mbox{''},``B\subseteq \name{U}_n\mbox{''}$ in $p$
where $x\in B$. The ordering on $\poset$ is reverse containment,
i.e. $p$ is stronger than $q$, $p\leq q$ iff $p\supseteq q$.
The circle in the notation $\name{U}_n$'s means that it is the name for
the set $U_n$ which will be determined by the generic filter.
For an element $x$ of the ground model we should use
$\check{x}$ to denote the canonical name of $x$, however to make
it more readable we often just write $x$. \sdex{$?check{x}$}
\sdex{$?name{U}_n$} For standard references on forcing see
Kunen \site{kunenbk} or Jech \site{jech}.
We call this forcing \dex{Silver forcing}.
\claim $\poset$ satisfies the ccc.
\proof
Note that since $\base$ is countable there are only countably many
sentences of the type $``B\subseteq \name{U}_n\mbox{''}$. Also if
$p$ and $q$ have exactly the same sentences of this type then
$p\union q\in \poset$ and hence $p$ and $q$ are compatible.
It follows that $\poset$ is the countable union of filters and
hence we cannot find an uncountable set of pairwise incompatible
conditions.
\qed
For $x\in X\setminus A$ define
$$D_x=\{p\in\poset: \exists n \; ``x\notin \name{U}_n\mbox{''}\in p\}.$$
For $x\in A$ and $n\in\omega$ define
$$E_x^n=\{p\in\poset: \exists B\in \base \;
x\in B \rmand ``B\subseteq \name{U}_n\mbox{''}\in p\}.$$
\claim $D_x$ is dense for each $x \in X\setminus A$ and
$E_x^n$ is dense for each $x \in A$ and $n\in\omega$.
\proof
To see that $D_x$ is dense let $p\in\poset$ be
arbitrary. Choose $n$ large enough so that
$\name{U_n}$ is not mentioned in $p$, then
$(p\union \{``x\notin \name{U}_n\mbox{''}\})\in \poset$.
To see that $E_x^n$ is dense let $p$ be arbitrary and let
$Y\subseteq X\setminus A$ be the set of elements of $X\setminus A$
mentioned by $p$. Since $x\in A$ and $X$ is Hausdorff there
exists $B\in \base$ with $B\intersect Y=\emptyset$ and
$x\in B$. Then $q=(p\union\{``B\subseteq \name{U}_n\mbox{''}\})\in \poset$ and
$q\in E_x^n$.
\qed
Since the cardinality of $X$ is less than the continuum we can
find a $\poset$-filter $G$ with the property that
$G$ meets each $D_x$ for $x \in X\setminus A$ and each
$E_x^n$ for $x \in A$ and $n\in\omega$.
Now define
$$U_n=\Union\{B: ``B\subseteq \name{U}_n\mbox{''}\in G\}.$$
Note that $A=\Intersect_{n\in\omega}U_n$ and so $A$ is
$G_\delta$ in $X$.
\qed
Spaces $X$ in which every subset is $G_\delta$ are called
\dex{Q-sets}.
The following question was raised during an email correspondence
with Zhou.
\begin{question}
Suppose every set of reals of
cardinality $\aleph_1$ is a $Q$-set. Then is
${\pp}>\omega_1$, i.e., is it true that for every
family ${\cal F}\subseteq\infsets$ of size $\omega_1$
with the finite intersection property there exists an
$X\in\infsets$ with $X\subseteq^* Y$ for all $Y\in {\cal F}$?
\end{question}
It is a theorem of Bell \site{bell} that ${\pp}$ is the
first cardinal for which MA for $\sigma$-centered forcing
fails. Another result along this line due to Alan Taylor
is that ${\pp}$ is the cardinality of the smallest set of
reals which is not a
$\gamma$-set, see Galvin and Miller \site{galmil}.
\sdex{${?
pp}$}
Fleissner and Miller \site{qsets} show it is consistent
to have a $Q$-set whose union with the rationals is not
a $Q$-set.
For more information on Martin's Axiom see Fremlin \site{frembook}.
For more on Q-sets, see Fleissner \site{fleiss1} \site{fleiss2},
Miller \site{survey1} \site{survey2}, Przymusinski \site{przym},
Judah and Shelah \site{qsetzero} \site{qsetsier}, and
Balogh \site{balogh}.
\sector{Generic $G_\delta$}
It is natural\footnote{ `Gentlemen, the great thing about this,
like most of the
demonstrations of the higher mathematics, is that it can
be of no earthly use to anybody.'
-Baron Kelvin}
to ask
\begin{center}
``What are the possibly lengths of
Borel hierarchies?''
\end{center} In this section we present a way of
forcing a generic $G_\delta$.
Let $X$ be a Hausdorff space with a countable
base $\base$. Consider the following forcing notion.
$p\in\poset$ iff it is a finite consistent set of sentences
of the form:
\begin{enumerate}
\item ``$B\subseteq \name{U}_n$'' where $B\in\base$ and $n\in\omega$, or
\item ``$x\notin \name{U}_n$'' where $x\in X$ and $n\in\omega$, or
\item ``$x\in \Intersect_{n<\omega}\name{U}_n$'' where $x\in X$.
\end{enumerate}
Consistency means that we cannot say that both
``$B\subseteq \name{U}_n$''
and ``$x\notin \name{U}_n$'' if it happens that $x\in B$ and we cannot
say both ``$x\notin \name{U}_n$''
and ``$x\in \Intersect_{n<\omega}\name{U}_n$''. The ordering is reverse
inclusion.
A $\poset$ filter $G$ determines a $G_\delta$ set $U$ as follows:
Let $$U_n=\Union\{B\in\base: ``B\subseteq \name{U}_n\mbox{''}\in G\}.$$
Let $U=\Intersect_n U_n$. If $G$ is $\poset$-generic over $V$, a
density argument shows that for every $x\in X$ we have that
$$x\in U \rmiff``x\in \Intersect_{n<\omega}\name{U}_n\mbox{''}\in G.$$
Note that $U$ is not in $V$ (as long as $X$ is infinite).
For suppose $p\in\poset$ and $A\subseteq X$ is in $V$ is such
that
$$p\forces \name{U}=\check{A}.$$
Since $X$ is infinite there exist $x\in X$ which is not mentioned
in $p$. Note that
$p_0=p\union\{``x\in \Intersect_{n<\omega}\name{U}_n\mbox{''}\}$ is consistent
and also
$p_1=p\union\{``x\notin \name{U}_n\mbox{''}\}$ is consistent
for all sufficiently large $n$ (i.e. certainly for $U_n$ not mentioned
in $p$.) But $p_0\forces x\in \name{U}$ and $p_1\forces x\notin \name{U}$,
and since $x$ is either in $A$ or not in $A$ we arrive at
a contradiction.
In fact, $U$ is not $F_\sigma$ in the extension (assuming $X$ is uncountable).
To see this we will first need to prove that $\poset$ has ccc.
\begin{lemma}
$\poset$ has ccc.
\end{lemma}
\proof
Note that $p$ and $q$ are compatible iff
$(p\union q)\in\poset$ iff $(p\union q)$ is a consistent set of
sentences.
Recall that there are three types of sentences:
\begin{enumerate}
\item $B\subseteq \name{U}_n$
\item $x\notin \name{U}_n$
\item $x\in \Intersect_{n<\omega}\name{U}_n$
\end{enumerate}
where $B\in\base$, $n\in\omega$, and $x\in X$.
Now if for contradiction $A$ were an uncountable antichain, then
since there are only countably many sentences of type 1 above
we may assume that all $p\in A$ have the same set of type 1 sentences.
Consequently for each distinct pair $p,q\in A$ there must be
an $x\in X$ and $n$ such that either
$``x\notin \name{U}_n\mbox{''}\in p$ and
$``x\in \Intersect_{n<\omega}\name{U}_n\mbox{''}\in q$ or vice-versa.
For each $p\in A$ let $D_p$ be the finitely many elements of $X$
mentioned by $p$ and let $s_p:D_p\arrow\omega$ be defined
by
$$s_p(x)=\left\{\begin{array}{ll}
0 & \mbox{if $``x \in \Intersect_{n<\omega}\name{U}_n\mbox{''}\in p$ }\\
n+1 & \mbox{if $``x\notin \name{U}_n\mbox{''}\in p$}
\end{array}\right.$$
But now $\{s_p:p\in A\}$ is an uncountable family of pairwise
incompatible finite partial functions from $X$ into $\omega$ which is
impossible. ($\fin(X,\omega)$ has the ccc, see Kunen \site{kunenbk}.)
\sdex{$?fin(X,\omega)$}
\qed
If $V[G]$ is a generic extension of a model $V$ which contains a
topological space $X$, then we let
$X$ also refer to the space in $V[G]$ whose
topology is generated by the open subsets of $X$ which are in $V$.
\begin{theorem} (Miller \site{borelhier}) \label{switch}
Suppose $X$ in $V$ is an uncountable
Hausdorff space with countable base $\base$ and
$G$ is $\poset$-generic over $V$. Then in $V[G]$
the $G_\delta$ set $U$ is not $F_\sigma$.
\end{theorem}
\proof
We call this argument the old switcheroo.
Suppose for contradiction
$$p\forces \Intersect_{n\in\omega} \name{U}_n=\Union_{n\in\omega} \name{C}_n
\mbox{ where $\name{C}_n$ are closed in $X$ }.$$
For $Y\subseteq X$ let $\poset(Y)$ be the elements of
$\poset$ which only mention $y\in Y$ in type 2 or 3 statements.
Let $Y\subseteq X$ be countable such that
\begin{enumerate}
\item $p\in \poset(Y)$ and
\item for every $n$ and
$B\in\base$ there exists a maximal antichain $A\subseteq \poset(Y)$
which decides the statement ``$B\intersect \name{C}_n=\emptyset$''.
\end{enumerate}
Since $X$ is uncountable there exists $x\in X\setminus Y$.
Let
$$q=p\union \{``x\in \Intersect_{n\in\omega}\name{U}_n\mbox{''}\}.$$
Since $q$ extends $p$, clearly
$$q\forces x\in \Union_{n\in\omega} \name{C}_n$$
so there exists $r\leq q$ and $n\in\omega$ so that
$$r\forces x\in \name{C}_n.$$
Let $$r=r_0\union \{``x\in \Intersect_{n\in\omega}\name{U}_n\mbox{''}\}$$
where $r_0$ does not mention $x$. Now we do the switch. Let
$$t=r_0\union \{``x\notin \name{U}_m\mbox{''}\}$$
where $m$ is chosen sufficiently large so that $t$ is a consistent
condition. Since
$$t\forces x\notin \Intersect_{n\in\omega}\name{U}_n$$
we know that
$$t\forces x\notin \name{C}_n.$$
Consequently there exist $s\in \poset(Y)$ and $B\in \base$
such that
\begin{enumerate}
\item $s$ and $t$ are compatible,
\item $s\forces B\intersect \name{C}_n=\emptyset$, and
\item $x\in B$.
\end{enumerate}
But $s$ and $r$ are compatible, because $s$ does not mention $x$.
This is a contradiction since
$s\union r\forces x\in \name{C}_n$ and
$s\union r\forces x\notin \name{C}_n$.
\qed
\sector{$\alpha$-forcing}
In this section we generalize the forcing which produced a
generic $G_\delta$ to arbitrarily high levels of the Borel
hierarchy. Before doing so we must prove some elementary
facts about well-founded trees.
Let $\ordinals$ denote the class of all ordinals. \sdex{$\ordinals$}
Define $T\subseteq Q^{<\omega}$ to be a \dex{tree} iff
$s\subseteq t\in T$ implies $s\in T$. Define the \dex{rank function}
$r:T\arrow \ordinals\union\{\infty\}$ of $T$ as follows:
\begin{enumerate}
\item $r(s)\geq 0$ iff $s\in T$,
\item $r(s)\geq \alpha+1$ iff $\exists q\in Q\;\; r(s\concat q)\geq \alpha$,
\item $r(s)\geq \lambda$ (for $\lambda$ a limit ordinal)
iff $r(s)\geq\alpha$ for every $\alpha<\lambda$.
\end{enumerate}
Now define $r(s)=\alpha$ iff $r(s)\geq\alpha$ but not
$r(s)\geq\alpha+1$ and $r(s)=\infty$ iff $r(s)\geq\alpha$
for every ordinal $\alpha$.
Define $[T]=\{x\in Q^\omega:\forall n \; \; x\res n\in T\}$. \sdex{$[T]$}
We say that $T$ is \dex{well-founded} iff $[T]=\emptyset$.
\begin{theorem} \label{tree}
$T$ is well-founded iff $r(\langle\rangle)\in \ordinals$.
\end{theorem}
\proof
%Note that if $s\subseteq t\in T$ then $r(t)\leq r(s)$ (regarding
%$\infty \geq \alpha$ for every ordinal $\alpha$.
It follows
easily from the definition that if $r(s)$ is an ordinal,
then
$$r(s)=\sup\{r(s\concat q)+1:q\in Q\}.$$
Hence, if $r(\langle\rangle)=\alpha\in \ordinals$ and $x\in [T]$, then
$$r(x\res (n+1))< r(x\res n)$$
is a descending sequence of ordinals.
On the other hand, if $r(s)=\infty$ then for some $q\in Q$ we must
have $r(s\concat q)=\infty$. So if $r(\langle\rangle)=\infty$
we can construct
(using the axiom of choice) a sequence $s_n\in T$ with
$r(s_n)=\infty$ and $s_{n+1}=s_{n}\concat x(n)$. Hence $x\in\ [T]$.
\qed
Definition. $T$ is a \dex{nice $\alpha$-tree} iff
\begin{enumerate}
\item $T\subseteq \finseq$ is a tree,
\item $r:T\arrow (\alpha+1)$ is its rank function
($r(\langle\rangle)=\alpha$),
\item if $r(s)>0$, then for every $n\in\omega\;\; s\concat n\in T$,
\item if $r(s)=\beta$ is a successor ordinal, then for every $n\in\omega
\;\; r(s\concat n)=\beta-1$, and
\item if $r(s)=\lambda$ is a limit ordinal, then $r(s\concat 0)\geq 2$
and $r(s\concat n)$ increases to $\lambda$ as $n\arrow\infty$.
\end{enumerate}
It is easy to see that for every $\alpha<\omega_1$ nice $\alpha$-trees
exist. For $X$ a Hausdorff space with countable base, $\base$, and $T$
a nice
$\alpha$-tree ($\alpha\geq 2$), define the partial order
$\poset=\poset(X,\base,T)$ which we call \dex{$\alpha$-forcing}
as follows:
\bigskip
\par\noindent $p\in\poset$ iff $p=(t,F)$ where
\begin{enumerate}
\item $t:D\arrow\base$ where $D\subseteq \tzero=\{s\in T: r(s)=0\}$
is finite,
\item $F\subseteq \tone\cross X$ is finite where
$$\tone=T\setminus \tzero=\{s\in T: r(s)>0\},$$
\item if $(s,x),(s\concat n,y)\in F$, then $x\not=y$, and
\item if $(s,x)\in F$ and $t(s\concat n)=B$, then $x\notin B$.
\end{enumerate}
The ordering on $\poset$ is given by $p\leq q$ iff $t_p\supseteq t_q$ and
$F_p\supseteq F_q$.
\sdex{$\tzero$}
\sdex{$\tone$}
\begin{lemma}
$\poset$ has ccc.
\end{lemma}
\proof
Suppose $A$ is uncountable antichain. Since there are only countably
many different $t_p$ without loss we may assume that there exists
$t$ such that $t_p=t$ for all $p\in A$. Consequently for $p,q\in A$
the only thing that can keep $p\union q$ from being a condition is that
there must be an $x\in X$ and an $s,s\concat n\in \tone$ such that
$$(s,x),(s\concat n,x)\in (F_p\union F_q).$$
But now for each $p\in A$ let $H_p:X\arrow [\tone]^{<\omega}$ be
the finite partial function defined by
$$H_p(x)=\{s\in \tone: (s,x)\in F_p\}$$
where domain $H_p$ is $\{x:\exists s\in \tone \; (s,x)\in F_p\}$.
Then $\{H_p:p\in A\}$ is an uncountable antichain in the order
of finite partial functions from $X$ to $[\tone]^{<\omega}$, a countable set.
\qed
Define for $G$ a $\poset$-filter the set $U_s\subseteq X$ for $s\in T$
as follows:
\begin{enumerate}
\item for $s\in \tzero$ let $U_s=B$ iff $\exists p\in G$ such that
$t_p(s)=B$ and
\item for $s\in \tone$ let
$U_s=\Intersect_{n\in\omega} \comp U_{s\concat n}$
\end{enumerate}
Note that $U_s$ is a $\bpi0\beta(X)$-set where $r(s)=\beta$.
\begin{lemma} \label{easydense}
If $G$ is $\poset$-generic over $V$ then in $V[G]$ we have
that for every $x\in X$ and $s\in \tone$
$$x\in U_s\iff\exists p\in G\; (s,x)\in F_p.$$
\end{lemma}
\proof
First suppose that $r(s)=1$ and note that the following set is dense:
$$D=\{p\in\poset: (s,x)\in F_p \rmor
\exists n\exists B\in\base \; x\in B \rmand t_p(s\concat n)=B\}.$$
To see this let $p\in\poset$ be arbitrary.
If $(s,x)\in F_p$ then $p\in D$ and we are already done.
If $(s,x)\notin F_p$ then let
$$Y=\{y:(s,y)\in F_p\}.$$
Choose $B\in \base$ with $x\in B$ and $Y$ disjoint from
$B$. Choose $s\concat n$ not in the domain of $t_p$, and
let $q=(t_q,F_p)$ be defined by $t_q=t_p\union (s\concat n, B)$.
So $q\leq p$ and $q\in D$. Hence $D$ is dense.
Now by definition $x\in U_s$ iff
$x\in\Intersect_{n\in\omega}\comp U_{s\concat n}$. So let
$G$ be a generic filter and $p\in G\intersect D$. If
$(s,x)\in F_p$ then we know that for every $q\in G$ and
for every $n$, if $t_q(s\concat n)=B$ then $x\notin B$. Consequently,
$x\in U_s$. On the other hand if $t_p(s\concat n)=B$ where
$x\in B$, then
$x\notin U_s$ and for every $q\in G$ it must be that $(s,x)\notin F_q$
(since otherwise $p$ and $q$ would be incompatible).
\bigskip
Now suppose $r(s)>1$. In this case note that the following set is dense:
$$E=\{p\in \poset: (s,x)\in F_p \rmor \exists n\;
(s\concat n,x)\in F_p\}.$$
To see this let $p\in\poset$ be arbitrary. Then either
$(s,x)\in F_p$ and already $p\in E$ or by choosing $n$ large enough
$q=(t_p,F_p\union\{(s\concat n,x)\})\in E$. (Note $r(s\concat n)>0$.)
Now assume the result is true for all $U_{s\concat n}$.
Let $p\in G\intersect E$. If $(s,x)\in F_p$ then for every
$q\in G$ and $n$ we have $(s\concat n, x)\notin F_q$ and so by
induction $x\notin U_{s\concat n}$ and so $x\in U_s$.
On the other hand if $(s\concat n, x)\in F_p$, then
by induction $x\in U_{s\concat n}$ and so $x\notin U_s$, and
so again for every $q\in G$ we have
$(s,x)\notin F_q$.
\qed
The following lemma is the heart of the old \dex{switcheroo} argument
used in Theorem \ref{switch}. Given any $Q\subset X$ define the
$\rank(p,Q)$ as follows:
$$\rank(p,Q)=\max\{r(s): (s,x)\in F_p \mbox{ for some } x\in X\setminus Q\}.$$
\begin{lemma}\label{rank} (Rank Lemma). For any $\beta\geq 1$ and
$p\in \poset$ there exists $\hat{p}$ compatible with $p$ such that
\begin{enumerate}
\item $\rank(\hat{p},Q)<\beta+1$ and
\item for any $q\in\poset$ if $\rank(q,Q)<\beta$, then
$$\mbox{$\hat{p}$ and $q$ compatible implies $p$ and $q$ compatible.}$$
\end{enumerate}
\end{lemma}
\proof
Let $p_0\leq p$ be any extension which satisfies:
for any $(s,x)\in F_p$ and $n\in\omega$, if
$r(s)=\lambda>\beta$ is a limit ordinal and $r(s\concat n)<\beta+1$, then
there exist $m\in\omega$ such that $(s\concat n\concat m,x)\in F_{p_0}$.
Note that since $r(s\concat n)$ is increasing to $\lambda$
there are only finitely many $(s,x)$ and $s\concat n$ to
worry about. Also $r(s\concat n\concat m)>0$ so
this is possible to do.
Now let $\hat{p}$ be defined as follows:
$$t_{\hat{p}}=t_p$$ and
$$F_{\hat{p}}=\{(s,x)\in F_{p_0}: x\in Q \rmor
r(s)<\beta+1\}.$$
Suppose for contradiction that there exists $q$ such that
$\rank(q,Q)<\beta$, $\hat{p}$ and $q$ compatible, but $p$
and $q$ incompatible.
Since $p$ and $q$ are incompatible either
\begin{enumerate}
\item there exists $(s,x)\in F_q$ and $t_p(s\concat n)=B$ with $x\in B$, or
\item there exists $(s,x)\in F_p$ and $t_q(s\concat n)=B$ with $x\in B$, or
\item there exists $(s,x)\in F_p$ and $(s\concat n, x)\in F_q$, or
\item there exists $(s,x)\in F_q$ and $(s\concat n, x)\in F_p$.
\end{enumerate}
(1) cannot happen since $t_{\hat{p}}=t_p$ and so $\hat{p},q$ would be
incompatible. (2) cannot happen since $r(s)=1$ and $\beta\geq 1$ means that
$(s,x)\in F_{\hat{p}}$ and so again $\hat{p}$ and $q$ are incompatible.
If (3) or (4) happens for $x\in Q$ then again (in case 3)
$(s,x)\in F_{\hat{p}}$
or (in case 4) $(s\concat n, x)\in F_{\hat{p}}$ and so $\hat{p},q$
incompatible.
So assume $x\notin Q$. In case (3) by the definition of
$\rank(q,Q)<\beta$ we know that $r(s\concat n)<\beta$.
Now since $T$ is a nice tree we know that either
$r(s)\leq\beta$ and so $(s,x)\in F_{\hat{p}}$ or $r(s)=\lambda$ a
limit ordinal. Now if $\lambda\leq \beta$ then $(s,x)\in F_{\hat{p}}$.
If $\lambda>\beta$ then by our construction of $p_0$ there exist $m$ with
$(s\concat n\concat m,x)\in F_{\hat{p}}$ and so $\hat{p},q$ are incompatible.
Finally in case (4) since $x\notin Q$ and so $r(s)<\beta$ we have
that $r(s\concat n)<\beta$ and so
$(s\concat n, x)\in F_{\hat{p}}$ and
so $\hat{p},q$ are incompatible.
\qed
Intuitively, it should be that statements of small rank are forced by
conditions of small rank. The next lemma will make this more precise.
Let $L_{\infty}(P_\alpha: \alpha<\kappa)$ be the infinitary propositional
logic with $\{P_\alpha: \alpha<\kappa\}$ as the atomic sentences.
\sdex{$L_{\infty}(P_\alpha: \alpha<\kappa)$}
Let $\Pi_0$-sentences be the atomic ones, $\{P_\alpha: \alpha<\kappa\}$.
For any $\beta>0$ let $\theta$ be a
\dex{$\Pi_\beta$-sentence} iff there exists
$\Gamma\subseteq \Union_{\delta<\beta}\Pi_\delta$-sentences and
$$\theta=\Conj_{\psi\in \Gamma}\neg \psi.$$
Models for this propositional language can naturally be regarded
as subsets $Y$ of $\kappa$ where we define
\begin{enumerate}
\item $Y\models P_\alpha$ iff $\alpha\in Y$,
\item $Y\models \neg\theta$ iff not $Y\models\theta$, and
\item $Y\models \Conj \Gamma$ iff
$Y\models\theta$ for every $\theta\in \Gamma$.
\end{enumerate}
\begin{lemma} (Rank and Forcing Lemma)\label{forcing}
Suppose $\rank:\poset\arrow\ordinals$ is any function on
a poset $\poset$ which satisfies the Rank Lemma \ref{rank}.
Suppose $\forces_{\poset}\name{Y}\subset\kappa$ and for
every $p\in\poset$ and $\alpha<\kappa$ if
$$p\forces \alpha\in \name{Y}$$
then there exist $\hat{p}$ compatible with $p$ such that
$\rank(\hat{p})=0$ and
$$\hat{p}\forces\alpha\in \name{Y}.$$
Then for every $\Pi_\beta$-sentence $\theta$ (in the ground model)
and every $p\in\poset$, if
$$p\forces``\name{Y}\models\theta\mbox{''}$$
then there exists $\hat{p}$ compatible with $p$ such
that $\rank(\hat{p})\leq\beta$ and
$$\hat{p}\forces``\name{Y}\models\theta\mbox{''}.$$
\end{lemma}
\proof
This is one of those lemmas whose statement is longer than its proof.
The proof is induction on $\beta$ and for $\beta=0$ the conclusion
is true by assumption. So suppose $\beta>0$ and
$\theta=\Conj_{\psi\in \Gamma}\neg \psi$ where
$\Gamma\subseteq \Union_{\delta<\beta}\Pi_\delta$-sentences.
By the rank lemma there exists $\hat{p}$ compatible with
$p$ such that $\rank(\hat{p})\leq\beta$ and for every
$q\in\poset$ with $\rank(q)<\beta$ if
$\hat{p},q$ compatible then ${p},q$ compatible.
We claim that
$$\hat{p}\forces``\name{Y}\models\theta\mbox{''}.$$
Suppose not. Then there exists $r\leq \hat{p}$ and
$\psi\in\Gamma$ such that
$$r\forces``\name{Y}\models\psi\mbox{''}.$$
By inductive assumption there exists $\hat{r}$ compatible with
$r$ such that
$$\rank(\hat{r})<\beta$$
such that
$$\hat{r}\forces``\name{Y}\models\psi\mbox{''}.$$
But $\hat{r},\hat{p}$ compatible implies
$\hat{r},p$ compatible, which is a contradiction because
$\theta$ implies $\neg\psi$ and so
$$p\forces``\name{Y}\models\neg\psi\mbox{''}.$$
\qed
Some earlier uses of rank in forcing arguments occur in Steel's
forcing, see Steel \site{steel}, Friedman \site{frieds},
and Harrington \site{harrsharp}.
It also occurs in Silver's analysis of the collapsing
algebra, see Silver \site{silver}.
In Miller \site{gensous} $\alpha$-forcing for all $\alpha$
is used to construct generic Souslin sets.
\sector{Boolean algebras}
In this section we consider the length of Borel hierarchies
generated by a subset of a {complete boolean algebra}. We
find that the generators of the complete boolean algebra
associated with $\alpha$-forcing generate it in exactly
$\alpha+1$ steps. We start by presenting some background
information.
Let $\bool$ be a \dex{cBa}, i.e, complete boolean algebra. This means
that in addition to being a boolean algebra, infinite sums and
products, also exist; i.e., for any $C\subseteq \bool$ there
exists $b$ (denoted $\sum C$) such that
\begin{enumerate}
\item $c\leq b$ for every $c\in C$ and
\item for every $d\in \bool$ if
$c\leq d$ for every $c\in C$, then $b\leq d$.
\end{enumerate}
Similarly we define $\prod C=-\sum _{c\in C}-c$ where
$-c$ denotes the complement of $c$ in $\bool$.
A partial order $\poset$ is \dex{separative} iff for any
$p,q\in\poset$ we have
$$p\leq q \rmiff\forall r\in\poset (r\leq p
\mbox{ implies $q,r$ compatible}).$$
\begin{theorem} (Scott, Solovay see \site{jech}) \label{ss}
A partial order $\poset$ is separative iff
there exists a cBa $\bool$ such that $\poset\subseteq\bool$
is dense in $\bool$, i.e. for every $b\in\bool$
if $b>0$ then there exists $p\in\poset$ with $p\leq b$.
\end{theorem}
It is easy to check that the $\alpha$-forcing $\poset$ is
separative (as long as $\base$ is infinite):
If $p\not\leq q$ then either
\begin{enumerate}
\item $t_p$ does not extend $t_q$, so there exists $s$ such
that $t_q(s)=B$ and either $s$ not in the
domain of $t_p$ or $t_p(s)=C$ where $C\not=B$ and so in either case
we can find $r\leq p$ with $r,q$ incompatible, or
\item $F_p$ does not contain $F_q$, so there exists
$(s,x)\in (F_q\setminus F_p)$ and we can either add
$(s\concat n,x)$ for sufficiently large $n$ or add
$t_r(s\concat n)=B$ for some sufficiently large $n$ and
some $B\in \base$ with $x\in B$ and get $r\leq p$ which
is incompatible with $q$.
\end{enumerate}
The elegant (but as far as I am concerned mysterious) approach
to forcing using complete boolean algebras contains the following
facts:
\begin{enumerate}
\item for any sentence $\theta$ in the forcing language
$$\val{\theta}=\sum\{b\in\bool: b\forces\theta\}=
\sum\{p\in\poset: p\forces\theta\}$$
where $\poset$ is any dense subset of $\bool$,
\item $p\forces\theta$ iff $p\leq\val{\theta}$,
\item $\val{\neg\theta}=-\val{\theta}$,
\item $\val{\theta\conj\psi}=\val{\theta}\conj\val{\psi}$,
\item $\val{\theta\disj\psi}=\val{\theta}\disj\val{\psi}$,
\item for any set $X$ in the ground model,
$$ \val{\forall x\in \check{X}\;\theta(x)}=
\prod_{x\in X}\val{\theta(\check{x}}.$$
\end{enumerate}
\par\noindent Definitions. For $\bool$ a cBa and
$C\subseteq \bool$ define:
$\bpi00(C)=C$ and
$\bpi0\alpha(C)=\{\prod\;\Gamma: \Gamma\subseteq
\{-c:c\in\Union_{\beta<\alpha}\bpi0\beta(C)\}\}$ for $\alpha>0$.
\medskip
$\ord(\bool)=\min\{\alpha:\exists C\subseteq \bool$ countable with
$\bpi0\alpha(C)=\bool\}$. \sdex{$?ord(?bool)$}
\begin{theorem}(Miller \site{borelhier}) \label{boolord}
For every $\alpha\leq\omega_1$ there exists a countably generated
ccc cBa $\bool$ with $\ord(\bool)=\alpha$.
\end{theorem}
\proof
Let $\poset$ be $\alpha$-forcing and $\bool$ be the cBa given by
the Scott-Solovay Theorem~\ref{ss}. We will show that
$\ord(\bool)=\alpha+1$.
Let
$$C=\{p\in\poset: F_p=\emptyset\}.$$
$C$ is countable and we claim that $\poset\subseteq\bpi0\alpha(C)$.
Since $\bool=\bsig01(\poset)$ this will imply that
$\bool=\bsig0{\alpha+1}(C)$ and so $\ord(\bool)\leq\alpha+1$.
First note that for any $s\in T$ with $r(s)=0$ and $x\in X$,
$$\val{x\in U_s}=\sum\{p\in C: \exists B\in\base\; t_p(s)=B\rmand
x\in B\}.$$
By Lemma \ref{easydense}
we know for generic filters $G$
that for every $x\in X$ and $s\in \tone$
$$x\in U_s\iff\exists p\in G\; (s,x)\in F_p.$$
Hence $\val{x\in U_s}=\langle \emptyset,\{(s,x)\}\rangle$ since
if they are not equal, then
$$b= \val{x\in U_s}\;\Delta\;\langle \emptyset,\{(s,x)\}\rangle>0,$$
but letting $G$ be a generic ultrafilter with $b$ in it would lead
to a contradiction.
We get that for $r(s)>0$:
$$\langle \emptyset,\{(s,x)\}\rangle=\val{x\in U_s}=
\val{x\in \Intersect_{n\in\omega}\comp U_{s\concat n}}=
\prod_{n\in\omega} -\val{x\in U_{s\concat n}}.$$
Remembering that for $r(s\concat n)=0$ we have
$\val{x\in U_{s\concat n}}\in \bsig01(C)$, we see
by induction that for every $s\in \tone$ if $r(s)=\beta$ then
$$\langle \emptyset,\{(s,x)\}\rangle\in \bpi0\beta(C).$$
For any $p\in \poset$
$$p=\langle t_p,\emptyset\rangle\conj\prod_{(s,x)\in F_p}
\langle \emptyset,\{(s,x)\}\rangle .$$
So we have that $p\in\bpi0{\alpha}(C)$.
\bigskip
Now we will see that $\ord(\bool) > \alpha$. We use the following
Lemmas.
$\bool^+$ are the nonzero elements of $\bool$. \sdex{$?bool^+$}
\begin{lemma}\label{rankbool1}
If $r:\poset\arrow\ordinals$ is a rank function, i.e. it satisfies
the Rank Lemma~\ref{rank} and in addition $p\leq q$ implies
$r(p)\leq r(q)$, then if $\poset$ is dense in the cBa $\bool$
then $r$ extends to $r^*$ on $\bool^+$:
$$r^*(b)=\min\{\beta\in\ordinals: \exists C\subseteq \poset: b=\sum C
\rmand \forall p\in C\; r(p)\leq\beta\}$$
and still satisfies the Rank Lemma.
\end{lemma}
\proof
Easy induction.
\qed
\begin{lemma} \label{rankbool2}
If $r:\bool^+\arrow\ord$ is a rank function and $E\subseteq \bool$
is a countable collection of rank zero elements, then for any
$a\in\bpi0\gamma(E)$ and $a\not=0$ there exists $b\leq a$
with $r(b)\leq\gamma$.
\end{lemma}
\proof
To see this let $E=\{e_n:n\in\omega\}$
and let $\name{Y}$ be a name for the set in the generic extension
$$Y=\{n\in\omega: e_n\in G\}.$$
Note that $e_n=\val{n\in \name{Y}}$.
For elements $b$ of $\bool$ in the complete subalgebra generated by
$E$ let us associate sentences $\theta_b$
of the infinitary propositional logic $L_\infty(P_n:n\in\omega)$
as follows:
$$\theta_{e_n}=P_n$$
$$\theta_{-b}=\neg\theta_b$$
$$\theta_{\prod R}=\Conj_{r\in R}\theta_r$$
Note that $\val {Y\models\theta_b}=b$ and if $b\in \bpi0\gamma(E)$ then
$\theta_b$ is a $\Pi_\gamma$-sentence.
The Rank and Forcing Lemma \ref{forcing} gives us,
by translating
\par $p\forces Y\models\theta_b$ into $p\leq \val{Y\models\theta_b}=b$) that:
\begin{quote}
For any $\gamma\geq 1$ and $p\leq b\in\bpi0\gamma(E)$ there exists a $\hat{p}$
compatible with $p$ such that $\hat{p}\leq b$ and
$r(\hat{p})\leq\gamma$.
\end{quote}
\qed
Now we use the lemmas to see that $\ord(\bool) > \alpha$.
Given any countable
$E\subseteq\bool$,
let $Q\subseteq X$ be countable so that
for any $e\in E$ there exists $H\subseteq\poset$ countable
so that $e=\sum H$ and for every $p\in H$
we have $\rank(p,Q)=0$. Let $x\in X\setminus Q$ be arbitrary;
then we claim:
$$\val{x\in U_{\emptyseq}}\notin\bsig0{\alpha}(E).$$
We have chosen $Q$ so that $r(p)=\rank(p,Q)=0$ for any $p\in E$
so the hypothesis of
Lemma \ref{rankbool2} is satisfied.
Suppose for contradiction
that
$$\val{x\in U_{\emptyseq}}=b\in\bsig0\alpha(E).$$
Let
$b=\sum_{n\in\omega}b_n$ where each $b_n$ is $\bpi0{\gamma_n}(C)$
for some $\gamma_n<\alpha$. For some n and $p\in\poset$ we would
have $p\leq b_n$. By Lemma \ref{rankbool2} we have that there
exists
$\hat{p}$ with $\hat{p}\leq b_n\leq b=\val{x\in U_{\emptyseq}}$ and
$\rank(\hat{p},Q)\leq\gamma_n$. But by the definition of
$\rank(\hat{p},Q)$ the pair $({\emptyseq},x)$ is not in $F_{\hat{p}}$,
but this contradicts
$$\hat{p}\leq b_n\leq b=\val{x\in U_{\emptyseq}}=
\langle \emptyset, \{({\emptyseq},x)\}\rangle.$$
\bigskip
This takes care of all countable successor ordinals.
(We leave the case of $\alpha=0,1$ for the reader to contemplate.)
For $\lambda$ a
limit ordinal take $\alpha_n$ increasing to $\lambda$ and let
$\poset=\sum_{n<\omega}\poset_{\alpha_n}$ be the direct sum,
where $\poset_{\alpha_n}$ is $\alpha_n$-forcing. Another way to
describe essentially the same thing is as follows:
Let $\poset_{\lambda}$ be $\lambda$-forcing. Then take $\poset$ to be
the subposet
of $\poset_{\lambda}$ such that $\emptyseq$ doesn't occur, i.e.,
$$\poset=\{p\in\poset_{\lambda}: \neg\exists x\in X\;\;
(\emptyseq,x)\in F_p\}.$$
Now if $\poset$ is dense in the cBa $\bool$, then $\ord(\bool)=\lambda$.
This is easy to see, because for each $p\in\poset$ there exists
$\beta<\lambda$ with $p\in\bpi0\beta(C)$. Consequently,
$\poset\subseteq\Union_{\beta<\lambda}\bpi0\beta(C)$ and
so since $\bool=\bsig01(\poset)$ we get $\bool=\bsig0\lambda(C)$.
Similarly to the other argument we see that for any countable
$E$ we can choose a countable $Q\subseteq X$ such for any
$s\in T$ with $2\leq r(s)=\beta<\lambda$ (so $s\not=\emptyseq$) we have that
$\val{x\in U_s}$ is not $\bsig0\beta(E)$. Hence
$\ord(\bool)=\lambda$.
For $\ord(\bool)=\omega_1$ we postpone until section \ref{ord1}.
\qed
\sector{Borel order of a field of sets}
In this section we use the Sikorski-Loomis representation theorem
to transfer the abstract Borel hierarchy on a complete boolean
algebra into a field of sets.
A family $F\subseteq P(X)$ is a \dex{$\sigma$-field} iff it contains
the empty set and is closed under countable unions and complements
in $X$. $I\subseteq F$ is a \dex{$\sigma$-ideal} in $F$ iff
\begin{enumerate}
\item $I$ contains the empty set,
\item $I$ is closed under countable unions,
\item $A\subseteq B\in I$ and $A\in F$ implies $A\in I$, and
\item $X\notin I$.
\end{enumerate}
$F/I$ is the countably complete boolean algebra
formed by taking $F$ and modding out by $I$, i.e. $A\eq B$ iff
$A\Delta B\in I$. \sdex{$F/I$}
For $A\in F$ we use $[A]$ or $[A]_I$ to denote the equivalence
class of $A$ modulo $I$. \sdex{$[A]_I$}
\begin{theorem}(Sikorski,Loomis, see \site{sikor} section 29)
\label{sikorthm}
For any countably complete boolean algebra $B$ there exists
a $\sigma$-field $F$ and a $\sigma$-ideal $I$ such that
$B$ is isomorphic to $F/I$.
\end{theorem}
\proof
Recall that the Stone space of $B$, $\st(B)$, is the space of ultrafilters
$u$ on $B$ with the topology generated by the clopen sets
of the form: \sdex{$\st(B)$}
$$[b]=\{u\in\st(B): b\in u\}.$$
This space is a compact Hausdorff space in which the field of clopen sets
exactly corresponds to $B$. $B$ is countably complete means that
for any sequence
$$\{ b_n:n<\omega\}\mbox{ in }B$$
there exists
$b\in B$ such that $b=\sum_{n\in\omega} b_n$. This translates to
the fact that given any countable family of clopen sets $\{C_n:n\in\omega\}$
in $\st(B)$ there exists a clopen set $C$ such that
$\Union_{n\in\omega}C_n\subseteq C$ and the closed set
$C\setminus \Union_{n\in\omega}C_n$ cannot contain a clopen set, hence
it has no interior, so it is nowhere dense. Let $F$ be the $\sigma$-field
generated by the clopen subsets of $\st(B)$. Let $I$ be the $\sigma$-ideal
generated by the closed nowhere dense subsets of $F$
(i.e. the ideal of meager sets). The Baire
category theorem implies that no nonempty open subset of a compact
Hausdorff space is meager, so
$st(B)\notin I$ and the same holds for any nonempty clopen subset of
$\st(B)$. Since the countable union of clopen sets is equivalent to
a clopen set modulo $I$ it follows that the map $C\mapsto [C]$ is
an isomorphism taking the clopen algebra of $\st(B)$ onto $F/I$.
\qed
Shortly after I gave a talk about my boolean algebra result
(Theorem \ref{boolord}),
Kunen pointed out the following result.
\begin{theorem}
(Kunen see \site{borelhier}) For every $\alpha\leq\omega_1$
there exists a field
of sets $H$ such that $\ord(H)=\alpha$.
\end{theorem}
\proof
Clearly we only have to worry about $\alpha$ with $2<\alpha<\omega_1$.
Let $\bool$ be the complete boolean algebra given by Theorem~\ref{boolord}.
Let $\bool\isom F/I$ where $F$ is a $\sigma$-field of sets and
$I$ a $\sigma$-ideal. Let $C\subseteq F/I$ be a countable
set of generators. Define
$$H=\{A\in F: [A]_I\in C\}.$$
By induction on $\beta$ it is easy to prove that for any $Q\in F$:
$$Q\in \bsig0\beta(H) \rmiff [Q]_I\in \bsig0\beta(C).$$
From which it follows that $\ord(H)=\alpha$.
\qed
Note that there is no claim that the family $H$ is countable.
In fact, it is consistent (Miller \site{borelhier}) that
either $\ord(H)\leq 2$ or $\ord(H)=\omega_1$
for every countable $H$.
\sector{CH and orders of separable metric spaces}
In this section we prove that assuming CH that there
exists countable field of sets of all possible Borel orders,
which we know is equivalent to existence of separable
metric spaces of all possible orders.
We will need a sharper form of the representation theorem.
\begin{theorem}(Sikorski, see \site{sikor} section 31)\label{sikorccc}
$\bool$ is a countably generated ccc cBa iff there exists
a ccc $\sigma$-ideal $I$ in $\borel(\cantorspace)$ such that
$\bool\isom\borel(\cantorspace)/I$. Furthermore if
$\bool$ is generated by the countable set $C\subseteq\bool$, then
this isomorphism can be taken so as to map the
clopen sets mod $I$ onto $C$.
\end{theorem}
\proof
To see that $\borel(\cantorspace)/I$ is countably generated is
trivial since the clopen sets modulo $I$ generate it.
A general theorem of Tarski is
that any $\kappa$-complete $\kappa$-cc boolean algebra
is complete.
For the other direction, we may assume by using the Sikorski-Loomis
Theorem, that $\bool$ is $F/J$ where $F$ is a $\sigma$-field
and $J$ a $\sigma$-ideal in $F$. Since $\bool$ is countably
generated there exists $C_n\in F$ for $n\in\omega$ such that
$\{[C_n]:n\in\omega\}$ generates $F/J$ where
$[C]$ denotes the equivalence class of $C$ modulo $J$. Now
let $h:X\arrow\cantorspace$ be defined by
$$h(x)(n)=\left\{\begin{array}{ll}
1 & \mbox{if $x\in C_n$}\\
0 & \mbox{if $x\notin C_n$}
\end{array}\right.$$
and define $\phi:\borel(\cantorspace)\arrow F$ by
$$\phi(A)=h^{-1}(A).$$
Define $I=\{A\in\borel(\cantorspace):\phi(A)\in J\}$.
Finally, we claim that
$$\hat{\phi}:\borel(\cantorspace)/I\arrow F/I
\mbox{ defined by }\hat{\phi}([A]_I)=[\phi(A)]_J$$
is an isomorphism of the two boolean algebras.
\qed
For $I$ a $\sigma$-ideal in $\borel(\cantorspace)$ we say that
$X\subseteq\cantorspace$ is an \dex{$I$-Luzin set} iff for every
$A\in I$ we have that $X\intersect A$ is countable. We say that
$X$ is \dex{super-$I$-Luzin} iff $X$ is $I$-Luzin and for every
$B\in\borel(\cantorspace)\setminus I$ we have that
$B\intersect X\not=\emptyset$. The following Theorem was
first proved by Mahlo \site{mahlo} and later by Luzin \site{luz} for
the ideal of meager subsets of the real line.
Apparently, Mahlo's paper was overlooked and hence these
kinds of sets have always been referred to as Luzin sets.
\begin{theorem} (Mahlo \site{mahlo}) CH. \label{mah}
Suppose $I$ is a $\sigma$-ideal in $\borel(\cantorspace)$ containing
all the singletons. Then there exists a super-$I$-Luzin set.
\end{theorem}
\proof
Let $$I=\{A_\alpha:\alpha<\omega_1\}$$ and let
$$\borel(\cantorspace)\setminus I=\{B_\alpha:\alpha<\omega_1\}.$$
Inductively choose $x_\alpha\in\cantorspace$ so that
$$x_\alpha\in B_\alpha\setminus (\{x_\beta:\beta<\alpha\}\union
\Union_{\beta<\alpha}A_\alpha).$$
Then $X=\{x_\alpha:\alpha<\omega_1\}$ is a super-$I$-Luzin set.
\qed
\begin{theorem} (Kunen see \site{borelhier})
Suppose $\bool=\borel(\cantorspace)/I$ is a cBa, $C\subseteq\bool$
are the clopen mod $I$ sets,
$ord(C)=\alpha>2$, and $X$ is
super-$I$-Luzin. Then $\ord(X)=\alpha$.
\end{theorem}
\proof
Note that the $\ord(X)$ is the minimum $\alpha$ such that
for every $B\in\borel(\cantorspace)$ there exists
$A\in\bpi0\alpha(\cantorspace)$ with $A\intersect X=B\intersect X$.
Since $\ord(C)=\alpha$ we know that given any Borel set $B$
there exists a $\bpi0\alpha$ set
$A$ such that $A\Delta B\in I$. Since $X$ is Luzin we know
that $X\intersect (A\Delta B)$ is countable. Hence there exist countable
sets $F_0,F_1$ such that
$$X\intersect B= X\intersect ((A\setminus F_0)\union F_1).$$
But since $\alpha>2$ we have that $((A\setminus F_0)\union F_1)$ is
also $\bpi0\alpha$ and hence $\ord(X)\leq\alpha$.
On the other hand for any $\beta<\alpha$ we know there exists
a Borel set $B$ such that for every $\bpi0\beta$ set $A$ we have
$B\Delta A\notin I$ (since $\ord(C)>\beta$).
But since $X$ is super-$I$-Luzin we have that for every
$\bpi0\beta$ set $A$ that $X\intersect (B\Delta A)\not=\emptyset$ and
hence $X\intersect B\not= X\intersect A$. Consequently,
$\ord(X)>\beta$.\qed
\begin{corollary}
(CH) For every $\alpha\leq\omega_1$ there exists a separable
metric space $X$ such that $\ord(X)=\alpha$.
\end{corollary}
While a graduate student at Berkeley I had obtained the result
that it was consistent with
any cardinal arithmetic to assume that for every $\alpha\leq\omega_1$
there exists a separable metric space $X$ such that $\ord(X)=\alpha$.
It never occurred to me at the time to ask what CH implied. In fact,
my way of thinking at the time was that
proving something from CH is practically the same as just showing
it is consistent. I found out in the real world
(outside of Berkeley) that they are considered very differently.
In Miller \site{borelhier} it is shown that
for every $\alpha<\omega_1$ it is consistent there
exists a separable metric space of order $\beta$ iff
$\alpha<\beta\leq\omega_1$. But the general question
is open.
\begin{question}
For what $C\subseteq\omega_1$ is it consistent that
$$C=\{\ord(X): X \mbox{ separable metric } \}?$$
\end{question}
\sector{Martin-Solovay Theorem}
In this section we the theorem below. The technique of proof
will be used in the next section to produce a boolean algebra
of order $\omega_1$. \sdex{Martin-Solovay Theorem}
\begin{theorem} (Martin-Solovay \site{marsol}) \label{marsolthm}
The following are equivalent for an infinite cardinal $\kappa$:
\begin{enumerate}
\item $\MA_\kappa$, i.e., for any poset $\poset$ which is ccc
and family $\dense$ of dense subsets of $\poset$ with
$|\dense|<\kappa$ there exists a $\poset$-filter $G$ with
$G\intersect D\not=\emptyset$ for all $D\in\dense$
\item For any ccc $\sigma$-ideal $I$ in $\borel(\cantorset)$
and $\ideal\subset I$ with $|\ideal|<\kappa$ we have that
$$\cantorspace\setminus \Union\ideal\not=\emptyset.$$
\end{enumerate}
\end{theorem} \sdex{$\MA_\kappa$}
\begin{lemma} \label{martinlem}
Let $\bool=\borel(\cantorspace)/I$ for some ccc $\sigma$-ideal $I$ and
let $\poset=\bool\setminus\{0\}$. The following are equivalent
for an infinite cardinal $\kappa$:
\begin{enumerate}
\item for any family $\dense$ of dense subsets of $\poset$ with
$|\dense|<\kappa$ there exists a $\poset$-filter $G$ with
$G\intersect D\not=\emptyset$ for all $D\in\dense$
\item for any family $\famly\subseteq\bool^\omega$ with
$|\famly|<\kappa$ there exists an ultrafilter $U$ on
$\bool$ which is $\famly$-complete, i.e., for every
$\langle b_n:n\in\omega\rangle\in \famly$
$$\sum_{n\in\omega}b_n\in U\rmiff \exists n \; b_n\in U$$
\item for any $\ideal\subset I$ with $|\ideal|<\kappa$
$$\cantorspace\setminus \Union\ideal\not=\emptyset$$
\end{enumerate}
\end{lemma}
\proof
To see that (1) implies (2) note that for any
$\langle b_n:n\in\omega\rangle\in\bool^\omega$ the set
$$D=\{p\in\poset: p\leq -\sum_n b_n \rmor\exists n\; p\leq b_n\}$$
is dense. Note also that any filter extends to an ultrafilter.
To see that (2) implies (3) do as follows.
Let H$_{\gamma}$ stand for the family of sets whose
transitive closure has cardinality less than the regular
cardinal $\gamma$, i.e. they
are hereditarily of cardinality less than $\gamma$. \sdex{H$_{\gamma}$}
The set H$_{\gamma}$ is a natural model
of all the axioms of set theory except possibly the
power set axiom, see Kunen \site{kunenbk}.
Let $M$ be an elementary substructure of
H$_{\gamma}$ for sufficiently large $\gamma$
with $|M|<\kappa$, $I\in M$, $\ideal\subseteq M$.
Let $\famly$ be all the $\omega$-sequences of Borel sets which
are in $M$. Since $|\famly|<\kappa$ we know there exists
$U$ an $\famly$-complete ultrafilter on $\bool$.
Define $x\in\cantorset$ by the
rule:
$$ x(n)=i \rmiff [\{y\in\cantorspace: y(n)=i\}]\in U.$$
\claim For every Borel set $B\in M$:
$$x\in B\rmiff [B]\in U.$$
\proof
This is true for subbasic clopen sets by definition.
Inductive steps just use that $U$ is an M-complete ultrafilter.
\qed
\bigskip
To see that (3) implies (1), let $M$ be an elementary substructure of
H$_{\gamma}$ for sufficiently large $\gamma$
with $|M|<\kappa$, $I\in M$, $\dense\subseteq M$. Let
$$\ideal=M\intersect I.$$
By (3) there exists
$$x\in \cantorset\setminus\Union\ideal.$$
Let $\bool_M=\bool\intersect M$. Then define
$$G=\{[B]\in\bool_M: x\in B\}.$$
Check $G$ is a $\poset$ filter which meets every $D\in\dense$.
\qed
This proves Lemma \ref{martinlem}.
\bigskip
To prove the theorem it necessary to do a \dex{two step iteration}.
Let $\poset$ be a poset and $\name{\posetq}\in V^\poset$ be the
$\poset$-name of a poset, i.e.,
$$\forces_\poset\posetq \mbox{ is a poset.}$$
Then we form the poset
$$\poset * \name{\posetq}= \{(p,\name{q}):
p\forces \name{q}\in\name{\posetq}\}$$
ordered by $(\hat{p},\hat{q})\leq (p,q)$ iff $\hat{p}\leq p$ and
$\hat{p}\forces \hat{q}\leq q$.\sdex{$?poset * ?name{?posetq}$}
In general there are two problems
with this. First, $\poset * \name{\posetq}$ is
a class. Second, it does not satisfy antisymmetry:
$x\leq y$ and $y\leq x$ implies $x=y$. These can be solved
by cutting down to a sufficiently large set of nice names and
modding out by the appropriate equivalence relation. Three of the main
theorems are:
\begin{theorem}
If $G$ is $\poset$-generic over $V$ and $H$ is
$\posetq^G$-generic over $V[G]$, then
$$G*H=\{(p,q)\in \poset * \name{\posetq}: p\in G, q^G\in H\}.$$
is a $\poset * \name{\posetq}$ filter generic over $V$.
\end{theorem}
\begin{theorem}
If $K$ is a $\poset * \name{\posetq}$-filter generic over $V$, then
$$G=\{p:\exists q\;(p,q)\in K\}$$
is $\poset$-generic over $V$ and
$$H=\{q^G:\exists p \; (p,q)\in K\}$$ is $\posetq^G$-generic over $V[G]$.
\end{theorem}
\begin{theorem} (Solovay-Tennenbaum \site{solten})
If $\poset$ is ccc and $\forces_\poset $``$\name{\posetq}$ is ccc'', then
$\poset * \name{\posetq}$ is ccc.
\end{theorem}
For proofs of these results, see Kunen \site{kunenbk} or Jech \site{jech}.
Finally we prove Theorem \ref{marsolthm}. (1) implies (2) follows
immediately from Lemma \ref{martinlem}. To see (2) implies (1) proceed
as follows.
Note that $\kappa\leq \continuum$, since (1) fails
for $\fin(\continuum^+,2)$. \sdex{$?fin(?continuum^+,2)$}
We may also assume that
the ccc poset $\poset$ has
cardinality less than $\kappa$.
Use a Lowenheim-Skolem argument to obtain a set $Q\subseteq\poset$
with the properties that $|Q|<\kappa$, $D\intersect Q$ is dense
in $Q$ for every
$D\in\dense$, and for every $p,q\in Q$ if $p$ and $q$ are compatible
(in $\poset$)
then there exists $r\in Q$ with $r\leq p$ and $r\leq q$.
Now replace $\poset$ by $Q$. The last condition on $Q$ guarantees
that $Q$ has the ccc.
Choose $X=\{x_p:p\in\poset\}\subseteq\cantorspace$ distinct elements
of $\cantorset$.
If $G$ is $\poset$-filter generic over $V$ let
$\posetq$ be Silver's forcing for forcing a $G_\delta$-set,
$\Intersect_{n\in\omega}U_n$, in $X$ such that
$$G=\{p\in\poset: x_p\in \Intersect_{n\in\omega}U_n\}.$$
Let $\base\in V$ be a countable base for $X$.
A simple description of $\poset * \name{\posetq}$ can
be given by:
$$(p,q)\in \poset * \name{\posetq}$$
iff
$p\in\poset$ and
$q\in V$ is a finite set of consistent sentences of the form:
\begin{enumerate}
\item $``x \notin \name{U}_n\mbox{''}$ where $x\in X$ or
\item $``B\subseteq \name{U}_n\mbox{''}$ where $B\in\base$ and $n\in\omega$.
\end{enumerate}
with the additional requirement that whenever the sentence
$``x \notin \name{U}_n\mbox{''}$ is in $q$ and $x=x_r$, then
$p$ and $r$ are incompatible (so $p\forces r\notin G$).
Note that if $D\subseteq \poset$ is dense in $\poset$, then
$D$ is predense in $\poset * \name{\posetq}$, i.e., every
$r\in \poset * \name{\posetq}$ is compatible with an element of $D$.
Consequently, it is enough to find sufficiently generic filters
for $\poset * \name{\posetq}$. By Lemma \ref{martinlem}
and Sikorski's Theorem~\ref{sikorccc} it is enough to see that
if $\poset * \name{\posetq}\subseteq \bool$ is dense in the ccc cBa algebra
$\bool$, then $\bool$ is countably generated. Let
$$C=\{\val{B\subseteq U_n}:B\in\base, n\in\omega\}.$$
We claim that $C$ generates $\bool$. To see this, note that
for each $p\in\poset$
$$\val{x_p\in \intersect_n U_n}=\prod_{n\in\omega}\val{x_p\in U_n}$$
$$\val{x_p\in U_n}=\sum_{B\in\base, x_p\in B}\val{B\subseteq U_n}$$
furthermore
$$(p,\emptyset)=\val{x_p\in \intersect_n U_n}$$
and so it follows that every element of $\poset * \name{\posetq}$
is in the boolean algebra generated by $C$ and so since
$\poset * \name{\posetq}$ is dense in $\bool$ it follows that
$C$ generates $\bool$.
\qed
Define $X\subseteq\cantorspace$ to be
a generalized $I$-Luzin set for an ideal $I$ in the Borel sets iff
$|X|=\continuum$ and $|X\intersect A|<\continuum$
for every $A\in I$.
It follows from the Martin-Solovay Theorem \ref{marsolthm} that
(assuming that the continuum is regular)
MA is equivalent to
for every ccc ideal $I$ in the Borel subsets of $\cantorspace$ there
exists a generalized $I$-Luzin set.
Miller and Prikry \site{prikmil} show that it is necessary to assume
the continuum is regular in the above observation.
\sector{Boolean algebra of order $\omega_1$}
Now we use the Martin-Solovay technique to produce a countably \label{ord1}
generated ccc cBa with order $\omega_1$. Before doing so we
introduce a countable version of $\alpha$-forcing which will be
useful for other results also. It is similar
to one used in Miller \site{cat} to give a simple
proof about generating sets in the category algebra.
Let
$T$ be a nice tree of rank $\alpha$ ($2\leq\alpha<\omega_1$).
Define
$$\poset_\alpha=\{p:D\arrow\omega: D\in [\omega]^{<\omega},
\forall s,s\concat n\in D\;\; p(s)\not=p(s\concat n)\}.$$
This is ordered by $p\leq q$ iff $p\supseteq q$. \sdex{$?poset_?alpha$}
For $p\in\poset_\alpha$ define
$$\rank(p)=\max\{r_T(s):s\in\dom(p)\}$$
where $r_T$ is the rank function on $T$. \sdex{$\rank(p)$}
\begin{lemma} \label{littlerank} $\rank:\poset_\alpha\arrow \alpha+1$
satisfies the
Rank Lemma \ref{rank}, i.e, for every $p\in\poset_\alpha$ and
$\beta\geq 1$ there exists $\hat{p}\in\poset_\alpha$ such that
\begin{enumerate}
\item $\hat{p}$ is compatible with $p$,
\item $\rank(\hat{p})\leq\beta$, and
\item for any $q\in\poset_\alpha$ if $\rank(q)<\beta$ and
$\hat{p}$ and $q$ are compatible, then $p$ and $q$ are compatible.
\end{enumerate}
\end{lemma}
\proof
First let $p_0\leq p$ be such that for every $s\in\dom(p)$ and $n\in\omega$
if $$r_T(s\concat n)<\beta<\lambda=r_T(s)$$ then there exists
$m\in\omega$ with $p_0(s\concat n\concat m)=p(s)$.
Note that $$r_T(s\concat n)<\beta<\lambda=r_T(s)$$ can happen only when
$\lambda$ is a limit ordinal and for any such $s$ there can be at most
finitely many $n$ (because $T$ is a nice tree).
Now let
$$E=\{s\in\dom(p_0): r_T(s)\leq\beta\}$$
and define
$\hat{p}= p_0\res E$. It is compatible with $p$ since $p_0$ is stronger
than both. From its definition it has rank $\leq\beta$. So let
$q\in\poset_\alpha$ have $\rank(q)<\beta$ and be incompatible with
$p$. We need to show it is incompatible with $\hat{p}$. There are
only three ways for $q$ and $p$ to be incompatible:
\begin{enumerate}
\item $\exists s\in \dom(p)\intersect\dom(q)\;\; p(s)\not=q(s)$,
\item $\exists s\in\dom(q)\;\exists s\concat n\in \dom(p)
\;\; q(s)=p(s^\concat n)$, or
\item $\exists s\in\dom(p)\;\exists s\concat n\in \dom(q)
\;\; p(s)=q(s^\concat n)$.
\end{enumerate}
For (1) since $\rank(q)<\beta$ we know $r_T(s)<\beta$ and hence
by construction $s$ is in the domain of $\hat{p}$ and so $q$ and
$\hat{p}$ are
incompatible. For (2) since $$r_T(s\concat n)2$,
this means $\ord(Y)=\alpha+1$.
To get $Y$ of order $\lambda$ for
a limit $\lambda<\omega_1$ just take a clopen separated
union of sets whose order increases to $\lambda$.
\qed
Now we clean up a loose end from Miller \site{borelhier}.
In that paper we had shown that assuming MA for every $\alpha<\omega_1$
there exists a separable metric space $X$ with
$\alpha\leq \ord(X)\leq\alpha+2$ or something silly like that.
Shortly afterwards, Fremlin supplied the missing arguments to
show the following.
\begin{theorem} \label{frem}
(Fremlin \site{fremlin}) MA implies that for every
$\alpha$ with $2\leq\alpha\leq\omega_1$ there exists
a second countable Hausdorff space $X$
with $\ord(X)=\alpha$.
\end{theorem}
\proof
Since the union of less than continuum many meager sets is meager, the
Mahlo construction \ref{mah} gives us a set $X\subseteq Q_\alpha$
of cardinality $\continuum$ such that for every Borel set
$B\in\borel(Q_\alpha)$ we have that $B$ is meager iff
$B\intersect X$ has cardinality less than $\continuum$.
Letting $\base$ be defined as in the proof of Theorem
\ref{luzinset} we see that:
$\alpha+1$ is
minimal such that for every
$B\in\borel(Q_\alpha)$ there exists a $\bsig0{\alpha+1}(\base)$ set $A$
such that such that $(B\Delta A)\intersect X$ has cardinality less
than $\continuum$.
What we need to see to complete the proof is that:
for
every $Z\subseteq X$ of cardinality less than $\continuum$ there
exists a $\bsig02(\base)$ set $F$ such that $F\intersect X=Z$.
\begin{lemma} (MA)
For any $Z\subseteq Q_\alpha$ of cardinality less than $\continuum$,
there exists $\langle D_n:n\in\omega\rangle$ such that:
\begin{enumerate}
\item $D_n$ is predense in $\poset_\alpha$,
\item $p\in D_n$ implies $\dom(p)\subseteq\tzero_\alpha$, and
\item $Z\intersect \Intersect_{n\in\omega}\Union_{s\in D_n}[s]=\emptyset$.
\end{enumerate}
\end{lemma}
\proof
Force with the following poset
$$P=\{(F,\langle p_n:nn\}$
to do the job.
\qed
By applying the Lemma we get that for
every $Z\subseteq X$ of cardinality less than $\continuum$ there
exists a $\bsig02(\base)$ set $F$ which is meager in
$Q_\alpha$ and such that $Z\subseteq F\intersect X$. But since
$F$ is meager we know
$F\intersect X$ has cardinality less than $\continuum$.
By Theorem \ref{silverlem} every subset of $r(F\intersect X)$
is a relative $\bsig02$ in $Y$, so
there exists an $F_0$ a $\bsig02(\base)$ set such that
$Z=(F\intersect X)\intersect F_0$.
This proves Theorem \ref{frem}.
\qed
\sector{Cohen real model}
I have long wondered if there exists an uncountable \label{cohen}
separable metric space of order $2$ in the Cohen real model.
I thought there weren't any.
We already
know from Theorem \ref{luzinset} that since there is an uncountable
Luzin set in Cohen real model that for every $\alpha$ with
$3\leq\alpha\leq\omega_1$ there is an
uncountable separable metric space $X$ with $\ord(X)=\alpha$.
\begin{theorem} \label{cohenmodel}
Suppose $G$ is $\fin(\kappa,2)$-generic over $V$
where $\kappa\geq\omega_1$.
Then in
$V[G]$ there is a
separable metric space $X$ of cardinality $\omega_1$
with $\ord(X)=2$.
\end{theorem}
\proof
We may assume that $\kappa=\omega_1$. This is because
$\fin(\kappa,2)\cross\fin(\omega_1,2)$ is isomorphic
to $\fin(\kappa,2)$ and so by the product lemma we may
replace $V$ by $V[H]$ where $(H,G)$ is
$\fin(\kappa,2)\cross\fin(\omega_1,2)$-generic over $V$.
We are going to use the fact that forcing with
$\fin(\omega_1,2)$ is equivalent to any finite support
$\omega_1$ iteration of countable posets.
The main idea of the proof is to construct an Aronszajn tree of perfect sets,
a technique first used by Todorcevic (see Galvin and Miller \site{galmil}).
We construct an \dex{Aronszajn tree} $(A,\fleq)$ and a family of
perfect sets $([T_s]:s\in A)$ such that $\supseteq$ is the
same order as $\fleq$. We will then show that if $X=\{x_s:s\in A\}$
is such that $x_s\in [T_s]$, then the order of $X$ is $2$.
In order to insure the construction can keep going at limit ordinals
we will need to use a fusion argument. Recall that a perfect set
corresponds to the infinite branches $[T]$ of a \dex{perfect tree}
$T\subseteq 2^{<\omega}$, i.e., a tree with the property that
for every $s\in T$ there exist a $t\in T$ such that both
$t\concat 0\in T$ and $t\concat 1\in T$. Such a $T$ is called
a \dex{splitting node} of $T$. There is a natural correspondence of
the splitting nodes of a perfect tree $T$ and $2^{<\omega}$.
Given two perfect trees $T$ and $T^\prime$ and $n\in\omega$ define
$T\leq_n T^\prime$ \sdex{$T?leq_n T^?prime$}
iff $T\subseteq T^\prime$ and the first $2^{n$ and thus in $T$.
\qed
By identifying $\fin(\omega_1,2)$ with
$\sum_{\alpha<\omega_1}\fin(\omega,2)$ we may assume that
$$G=\langle G_\alpha:\alpha<\omega_1\rangle$$
where $G_\beta$ is
$\fin(\omega,2)$-generic over $V[G_\alpha:\alpha<\beta]$
for each $\beta<\omega_1$.
Given an Aronszajn tree $A$ we let $A_\alpha$ \sdex{$A_\alpha$}
\sdex{$A_{<\alpha}$} be the nodes of $A$ at
level $\alpha$, i.e.
$$A_\alpha=\{s\in A: \{t\in A: t\fless s\}\mbox{ has order type } \alpha\}$$
and
$$A_{<\alpha}=\Union_{\beta<\alpha} A_\beta.$$
We use $\langle G_\alpha:\alpha<\omega_1\rangle$ to construct
an Aronszajn tree $(A,\fleq)$ and a family of
perfect sets $([T_s]:s\in A)$ such that
\begin{enumerate}
\item $s\fleq t$ implies $T_s\supseteq T_t$,
\item if $s$ and $t$ are distinct elements of $A_\alpha$, then
$[T_s]$ and $[T_t]$ are disjoint,
\item every $s\in A_\alpha$ has infinitely many distinct extensions
in $A_{\alpha+1}$,
\item for each $s\in A_{<\alpha}$ and
$n<\omega$ there exists $t\in A_\alpha$ such that $T_t\leq_n T_s$,
\item for each $s\in A_\alpha$ and $t\in A_{\alpha+1}$ with
$s\fless t$, we have that
$[T_t]$ is a generic perfect subset of $[T_s]$ obtained by using $G_\alpha$
(explained below in Case 2), and
\item $\{T_s:s\in A_{<\alpha}\}\in V[G_\beta:\beta<\alpha]$.
\end{enumerate}
The first three items simply say that $\{[T_s] : s\in A\}$
and its ordering by $\subseteq$ determines
$(A,\sleq)$, so what we really have here is an Aronszajn tree of perfect sets.
Item (4) is there in order to allow the construction to proceed at
limits levels.
Item (5) is what we do a successor levels and guarantees the set we
are building has order $2$. Item (6) is a consequence of the construction
and would be true for a closed unbounded set of ordinals no matter what we
did anyway.
Here are the details of our construction.
\bigskip
\par\noindent Case 1. $\alpha$ a limit ordinal.
The construction is done uniformly enough so that we already have
that
$$\{T_s:s\in A_{<\alpha}\}\in V[G_\beta:\beta<\alpha].$$
Working in $V[G_\beta:\beta<\alpha]$ choose a sequence $\alpha_n$
for $n\in\omega$ which strictly increases to $\alpha$. Given
any $s_n\in A_{\alpha_n}$ we can choose by inductive hypothesis
a sequence $s_m\in A_{\alpha_m}$ for $m\geq n$ such that
$$T_{s_{m+1}}\leq_m T_{s_m}.$$
If $T=\Intersect_{m>n} T_{s_m}$, then by Lemma \ref{fusion} we
have that $T\leq_nT_{s_n}$. Now let $\{T_t:t\in A_\alpha\}$
be a countable collection of perfect trees so that for
every $n$ and $s\in A_{\alpha_n}$ there exists $t\in A_\alpha$
with $T_t\leq_n T_s$. This implies item (4) because
for any $s\in A_{<\alpha}$ and $n<\omega$ there exists some
$m\geq n$ with $s\in A_{<\alpha_m}$ hence by inductive hypothesis
there exists $\hat{s}\in A_{\alpha_m}$ with $T_{\hat{s}}\leq_n T_s$
and by construction there exists $t\in A_\alpha$
with $T_t\leq_m T_{\hat{s}}$ and so $T_t\leq_n T_s$ as desired.
\bigskip
\par\noindent Case 2. Successor stages.
Suppose we already have constructed
$$\{T_s:s\in A_{<\alpha+1}\}\in V[G_\beta:\beta<\alpha+1].$$
Given a perfect tree $T\subseteq 2^{<\omega}$ define the countable
partial order $\poset(T)$ as follows. $p\in\poset(T)$ iff $p$
\sdex{$?poset(T)$}
is a finite subtree of $T$ and $p\leq q$ iff $p\supseteq q$ and
$p$ is an end extension of $q$, i.e., every new node of $p$ extends
a terminal node of $q$. It is easy to see that if $G$ is $\poset(T)$-generic
over a model $M$, then
$$T_G=\Union\{p: p\in G\}$$
is a perfect subtree of $T$. Furthermore, for any $D\subseteq [T]$
dense open in $[T]$ and
coded in $M$, $[T_G]\subseteq D$.
i.e., the branches of $T_G$ are Cohen reals (relative to $T$) over $M$.
This means that for any Borel set $B\subseteq [T]$ coded in $M$,
there exists an clopen set $C\in M$ such that
$$C\intersect [T_G]=B\intersect [T_G].$$
To see why this is true let $p\in\poset(T)$ and $B$ Borel. Since
$B$ has the Baire property relative to $[T]$
by extending each terminal node of $p$,
if necessary, we can obtain $q\geq p$ such that for every terminal
node $s$ of $q$ either $[s]\intersect B$ is meager in $[T]$
or $[s]\intersect {B}$
is comeager in $[T]\intersect [s]$.
If we let
$C$ be union of all $[s]$ for $s$ a terminal node of $q$
such that $[s]\intersect {B}$
is comeager in $[T]\intersect [s]$, then
$$q\forces B\intersect T_G= C\intersect T_G.$$
To get $T_G\leq_n T$ we could instead force with
$$\poset(T,n)=\{p\in\poset(T):
p \mbox{ end extends the first $2^{1$ and $p\forces\name{B}\in \bpi0\alpha(X)$.
Let $\beta_n$ be a sequence which is either constantly $\alpha-1$
if $\alpha$ is a successor or which is unbounded in $\alpha$ if
$\alpha$ is a limit.
By the usual forcing facts there exists a sequence of names
$\langle B_n:n\in\omega\rangle$ such that
for each $n$, $$p\forces B_n\in\bpi0{\beta_n},$$ and
$$p\forces B=\Intersect_{n<\omega}\comp{B_n}.$$
Then for every $x\in X$
$$p\forces \check{x}\in B$$ iff
$$\forall n\in\omega\;\; p\forces x\in\comp{B_n}$$ iff
$$\forall n\in\omega\;\forall q\leq p\;\; q\not\forces x\in{B_n}.$$
Consequently,
$$\{x\in X: p\forces x\in \name{B}\}=\Intersect_{n\in\omega}
\Intersect_{q\leq p} \comp{\{x: q\forces \check{x}\in\name{B_m}\}}.$$
\qed
Now let us prove the Theorem. Suppose
$V\models$``$\ord(X)=\alpha$''. Then in $V[G]$ for any Borel
set $B\in\borel(X)$
$$B=\Union_{p\in G}\{x\in X: p\forces \check{x}\in \name{B}\}.$$
By the lemma, each of the sets
$\{x\in X: p\forces \check{x}\in \name{B}\}$ is a Borel set in $V$, and since
$\ord(X)=\alpha$, it is a $\bsig0\alpha$ set. Hence, it
follows that $B$ is a $\bsig0\alpha$ set.
So, $V[G]\models\ord(X)\leq\alpha$. To see that
$\ord(X)\geq\alpha$ let $\beta<\alpha$ and suppose
in $V$ the set $A\subseteq X$ is $\bsig0\beta$ but not
$\bpi0\beta$. This must remain true in $V[G]$ otherwise
there exists a $p\in G$ such
that
$$p\forces\mbox{``$\check{A}$ is $\bpi0\beta$''}$$
but by the lemma
$$\{x\in X:p\forces \check{x}\in \check{A}\}=A$$
is $\bpi0\beta$ which is a contradiction.
\qed
Part of this argument is similar to one used by Judah and Shelah
\site{qsetzero}
who showed that it is consistent to have a Q-set which does not
have strong measure zero.
It is natural to ask if there are spaces of order $2$
of higher cardinality.
\begin{theorem} \label{cohenmodel2}
Suppose $G$ is $\fin(\kappa,2)$-generic over $V$
where $V$ is a model of CH and $\kappa\geq\omega_2$.
Then in
$V[G]$ for every separable metric space $X$ with
$|X|>\omega_1$, we have $\ord(X)\geq 3$.
\end{theorem}
\proof
This will follow easily from the next lemma.
\begin{lemma} (Miller \site{maponto}) \label{mapping}
Suppose $G$ is $\fin(\kappa,2)$-generic over $V$
where $V$ is a model of CH and $\kappa\geq\omega_2$.
Then $V[G]$ models that for every
$X\subseteq\cantorspace$ with $|X|=\omega_2$ there
exists a Luzin set $Y\subseteq\cantorspace$ and a
one-to-one continuous function $f:Y\arrow X$.
\end{lemma}
\proof
Let $\langle \tau_\alpha:\alpha<\omega_2\rangle$ be a sequence
of names
for distinct elements of $X$. For each
$\alpha$ and $n$ choose a maximal antichain $A_n^\alpha\union B_n^\alpha$
such that
$$p\forces \tau_\alpha(n)=0 \mbox{ for each $p\in A_n^\alpha$ and}$$
$$p\forces \tau_\alpha(n)=1 \mbox{ for each $p\in B_n^\alpha$}.$$
Let $X_\alpha\subseteq\kappa$ be union of domains of elements
from $\Union_{n\in\omega}A^\alpha_n\union B^\alpha_n$.
Since each $X_\alpha$ is
countable we may as well assume that the
$X_\alpha$'s form a $\Delta$-system, i.e. there exists $R$ such
that $X_\alpha\intersect X_\beta=R$ for every $\alpha\not=\beta$.
We can assume that $R$ is the empty set. The
reason is we can just replace $A^\alpha_n$ by
$$\hat{A}^\alpha_n=\{p\res (\comp{R}):p\in A^\alpha_n \rmand
p\res R\in G\}$$
and similarly for $B^\alpha_n$. Then let $V[G\res R]$ be the new
ground model.
Let
$$\langle j_\alpha:X_\alpha\arrow \omega:\alpha<\omega_2\rangle$$
be a sequence of bijections in the ground model.
Each
$j_\alpha$ extends to an order preserving map from $\fin(X_\alpha,2)$ to
$\fin(\omega,2)$. By CH, we may as well assume that
there exists a single sequence, $\langle (A_n,B_n):n\in\omega\rangle$,
such that every $j_\alpha$ maps
$\langle A^\alpha_n,B^\alpha_n:n\in\omega\rangle$
to $\langle (A_n,B_n):n\in\omega\rangle$.
The Luzin set is
$Y=\{y_\alpha:\alpha<\omega_2\}$
where $y_\alpha(n)=G(j_\alpha^{-1}(n))$. The continuous
function, $f$, is the map determined by
$\langle (A_n,B_n):n\in\omega\rangle$:
$$f(x)(n)=0 \rmiff \exists m \; \; x\res m\in A_n.$$
This proves the Lemma.
\qed
If $f:Y\arrow X$ is one-to-one continuous function from a Luzin
set $Y$, then $\ord(X)\geq 3$. To see this assume that
$Y$ is dense and let
$D\subseteq Y$ be a countable dense subset of $Y$. Then
$D$ is not $G_\delta$ in $Y$. This is because any $G_\delta$
set containing $D$ is comeager and therefore must meet $Y$ in an uncountable
set. But note that $f(D)$ is a countable set which cannot be
$G_\delta$ in $X$, because $f^{-1}(f(D))$ would be
$G_\delta$ in $Y$ and since $f$ is one-to-one we have $D=f^{-1}(f(D))$.
This proves the Theorem.
\qed
It is natural to ask about the cardinalities of sets of various orders
in this model. But note that there is a trivial way to get a large
set of order $\beta$. Take a clopen separated union of a large
Luzin set (which has order 3) and a set of size $\omega_1$ with
order $\beta$. One possible way to strengthen the notion of
order is to say that a space $X$ of cardinality
$\kappa$ has essential order $\beta$ iff every nonempty
open subset of $X$ has order $\beta$ and cardinality $\kappa$.
But this is also open to a simple trick of combining a small set
of order $\beta$ with a large set of small order. For example,
let $X\subseteq\cantorspace$ be a clopen separated
union of a Luzin set of cardinality $\kappa$ and set of cardinality
$\omega_1$ of order $\beta\geq 3$.
Let $\langle P_n:n\in\omega\rangle$ be a sequence of disjoint nowhere
dense perfect subsets of $\cantorspace$ with the property that for
every $s\in 2^{<\omega}$ there exists $n$ with $P_n\subseteq [s]$.
Let $X_n\subseteq P_n$ be a homeomorphic copy of $X$ for each $n<\omega$.
Then $\Union_{n\in\omega} X_n$ is a set of cardinality $\kappa$ which
has essential order $\beta$.
With this cheat in mind let us define a stronger notion of order.
A separable metric space $X$ has \dex{hereditary order} $\beta$ iff
every uncountable $Y\subseteq X$ has order $\beta$. We begin
with a stronger version of Theorem \ref{luzinset}.
\begin{theorem}\label{cohenluz}
If there exists a Luzin set $X$ of cardinality $\kappa$, then for
every $\alpha$ with $2<\alpha<\omega_1$ there exists a separable
metric space $Y$ of cardinality $\kappa$ which is hereditarily of
order $\alpha$.
\end{theorem}
\proof
This is a slight modification of the proof of Theorem \ref{luzinset}.
Let $\posetq_\alpha$ \sdex{$?posetq_\alpha$} be the following partial
order. Let
$\langle \alpha_n:n\in\omega\rangle$ be a sequence such that
if $\alpha$ is a limit ordinal, then $\alpha_n$ is a cofinal increasing
sequence in $\alpha$ and if $\alpha=\beta+1$ then $\alpha_n=\beta$
for every $n$.
The rest of the proof is same except we use $\posetq_{\alpha+1}$ instead
of $\poset_\alpha$ for successors and $\posetq_\alpha$ for limit
$\alpha$ instead of taking a clopen separated union. By using the direct
sum (even in the successor case) we get a stronger property for
the order. Let
$$\hat{Q}_\alpha=\prod{Q_{\alpha_n}}$$ be the closed subspace of
\sdex{$?hat{Q}_\alpha$}
$$\prod_{n\in\omega}\omega^{T_{\alpha_n}}$$
and let $\base$ be the collection of clopen subsets of $Q_\alpha$ which
are given by rank zero conditions of $\posetq(\alpha)$, i.e.,
all rectangles of the form $\prod_{n\in\omega}[p_n]$ such
that
$p_n\in \posetq_{\alpha_n}$ with $\dom(p)\subseteq\tzero_\alpha$
and $p_n$ the trivial condition for all but finitely many $n$.
As in the proof of Theorem \ref{luzinset} we get that
the order of $\{[B]:B\in\base\}$ as a subset
of $\borel(\hat{Q}_\alpha)/\meager(\hat{Q}_\alpha)$
is $\alpha$. Because
we took the direct sum we get the
stronger property that for any nonempty clopen set $C$ in $\hat{Q}_\alpha$
the order of $\{[B\intersect C]:B\in\base\}$ is $\alpha$.
But know given $X$ a Luzin set in $\hat{Q}_\alpha$ we know that for any
uncountable $Y\subseteq X$ there is a nonempty clopen set
$C\subseteq\hat{Q}_\alpha$ such that $Y\intersect C$ is a super-Luzin
set relative to $C$. (The \dex{accumulation points} of $Y$, the set of
all points all of whose neighborhoods contain uncountably many points of
$Y$, is closed and uncountable, therefore must have nonempty interior.)
If $C$ is a nonempty clopen set in the interior of the accumulation points
of $Y$, then since $\{[B\intersect C]:B\in\base\}$ is $\alpha$,
we have by the proof of Theorem \ref{luzinset}, that the order of $Y$ is
$\alpha$.
\qed
\begin{theorem} \label{cohen1}
Suppose that in $V$ there is a separable metric space,
$X$, with hereditary order $\beta$ for some $\beta\leq\omega_1$.
Let
$G$ be $\fin(\kappa,2)$-generic over $V$ for any
$\kappa\geq\omega$.
Then in $V[G]$ the space $X$ has hereditary order $\beta$.
\end{theorem}
\proof
In $V[G]$ let $Y\subseteq X$ be uncountable.
For contradiction, suppose that
$$p\forces \ord(\name{Y})\leq\alpha\rmand |\name{Y}|=\omega_1$$
for some $p\in \fin(\kappa,2)$ and $\alpha<\beta$.
Working in $V$ by the usual
$\Delta$-system argument we can get $q\leq p$ and
$$\langle p_x : x\in A\rangle$$
for some $A\in [X]^{\omega_1}$ such that
and $p_x\leq q$ and
$$p_x\forces \check{x}\in \name{Y}$$
for each $x\in A$ and
$$dom(p_x)\intersect dom(p_y)=dom(q)$$
for distinct $x$ and $y$ in $A$.
Since $A$ is uncountable we know that in $V$ the order of $A$ is
$\omega_1$. Consequently, there exists $R\subseteq A$ which is
$\bsig0\alpha(A)$ but not $\bpi0\alpha(A)$. We claim that in $V[G]$
the set $R\intersect Y$ is not $\bpi0\alpha(Y)$. If not, there
exists $r\leq q$ and $\name{S}$ such that
$$r\forces \mbox{``}\name{Y}\intersect R= \name{Y}\intersect \name{S}
\rmand \name{S}\in \bpi0\alpha(A)\mbox{''}.$$
Since Borel sets are coded by reals there exists
$\Gamma\in[\kappa]^\omega\intersect V$
such that for any $x\in A$ the statement ``$\check{x}\in \name{S}$''
is decided by conditions in $\fin(\Gamma,2)$ and also
let $\Gamma$ be large enough to contain the domain of $r$.
Define
$$T=\{x\in A: q\forces \check{x}\in \name{S}\}.$$
According to Lemma \ref{cohlem} the set $T$ is $\bpi0\alpha(A)$.
Consequently, (assuming $\alpha\geq 3$) there are uncountably
many $x\in A$ with $x \in R\Delta T$. Choose such an $x$ which
also has the property that $dom(p_x)\setminus dom(q)$ is disjoint
from $\Gamma$. This can be done since the $p_x$ form a
$\Delta$ system. But now, if $x\in T\setminus R$, then
$$r\union p_x\forces \mbox{``}\check{x}\in \name{Y}\intersect \name{S}
\rmand x\notin \name{Y}\intersect \check{R}\mbox{''}.$$
On the other hand, if $x\in R\setminus T$, then
there exists $\hat{r}\leq r$ in $\fin(\Gamma,2)$ such that
$$\hat{r}\forces \check{x}\notin \name{S}$$
and consequently,
$$\hat{r}\union p_x\forces
\mbox{``}\check{x}\notin \name{Y}\intersect \name{S}
\rmand x\in \name{Y}\intersect \check{R}\mbox{''}.$$
Either way we get a contradiction and the result is proved.
\qed
\begin{theorem}\label{cohen2}
(CH) There exists $X\subseteq\cantorspace$ such that
$X$ has hereditary order $\omega_1$.
\end{theorem}
\proof
By Theorem \ref{boolord} there exists a countably generated
ccc cBa $\bool$ which has order $\omega_1$. For any $b\in\bool$
with $b\not=0$ let $\ord(b)$ be the order of the boolean algebra
you get by looking only at $\{c\in\bool: c\leq b\}$. Note that
in fact $\bool$ has the property that for every $b\in\bool$
we have $\ord(b)=\omega_1$. Alternatively, it easy to show that
any ccc cBa of order $\omega_1$ would have to contain
an element $b$ such that every $c\leq b$ has order $\omega_1$.
By the proof
of the Sikorski-Loomis Theorem \ref{sikorthm} we know that
$\bool$ is isomorphic to $\borel(Q)/\meager(Q)$ where
$Q$ is a ccc compact Hausdorff space with a basis of
cardinality continuum.
Since $Q$ has ccc, every open dense set
contains an open dense set which is a countable union of
basic open sets. Consequently, by using CH, there exists a
family $\famly$ of meager sets
with $|\famly|=\omega_1$ such that
every meager set is a subset of one in $\famly$.
Also note that for any nonmeager Borel set $B$ in $Q$ there
exists a basic open set $C$ and $F\in\famly$ with
$C\setminus F\subseteq B$.
Hence by Mahlo's construction (Theorem \ref{mah}) there
exists a set $X\subseteq Q$ with the property that for
any Borel subset $B$ of $Q$
$$|B\intersect X|\leq\omega \rmiff B \mbox{ meager.} $$
Let $\base$ be a countable field of clopen subsets of
$Q$ such that
$$\{[B]_{\meager(Q)}:B\in\base\}$$
generates $\bool$. Let
$$R=\{X\intersect B: B\in\base\}.$$
If $\tilde{X}\subseteq \cantorspace$ is the image of $X$ under
the characteristic
function of the sequence $\base$ (see Theorem \ref{charseq}),
then $\tilde{X}$ has hereditary order $\omega_1$. Of course
$\tilde{X}$ is really just the same as $X$ but retopologized using
$\base$ as a family of basic open sets. Let $Y\in[X]^{\omega_1}$.
Since $\ord(p)=\omega_1$ for any basic clopen set the following
claim shows that
the order of $Y$ (or rather the image of $Y$ under the
characteristic function of the sequence $\base$) is $\omega_1$.
\claim There exists a basic clopen $p$ in $Q$ such that for every
Borel $B\subseteq p$,
$$|B\intersect Y|\leq\omega \rmiff B \mbox{ meager.} $$
\proof
Let $p$ and $q$ stand for nonempty basic clopen sets. Obviously
if $B$ is meager then $B\intersect Y$ is countable, since
$B\intersect X$ is countable. To prove the other direction,
suppose for contradiction that for every $p$ there exists
$q\leq p$ and Borel $B_q\subseteq q$ such that $B_q$ is comeager
in $q$ and $B_q\intersect Y$ is countable. By using ccc there exists
a countable dense family $\Sigma$ and $B_q$ for $q\in \Sigma$
with
$B_q\subseteq q$ Borel and comeager
in $q$ such that $B_q\intersect Y$ is countable. But
$$B=\Union \{B_q:q\in \Sigma\}$$
is a comeager Borel set which meets $Y$ in a countable set. This
implies that $Y$ is countable since $X$ is contained in $B$ except
for countable many points.
\qed
\begin{theorem} \label{cohenmod2}
Suppose $G$ is $\fin(\kappa,2)$-generic over $V$
where $V$ is a model of CH and $\kappa\geq\omega$.
Then
in $V[G]$
there exists a separable metric space $X$ with
$|X|=\omega_1$ and hereditarily of order $\omega_1$.
\end{theorem}
\proof
Immediate from Theorem \ref{cohen1} and \ref{cohen2}.
\qed
Finally, we show that there are no large spaces of hereditary order
$\omega_1$ in the Cohen real model.
\begin{theorem} \label{cohenmodel3}
Suppose $G$ is $\fin(\kappa,2)$-generic over $V$
where $V$ is a model of CH and $\kappa\geq\omega_2$.
Then
in $V[G]$
for every separable metric space $X$ with
$|X|=\omega_2$ there exists $Y\in [X]^{\omega_2}$ with
$\ord(Y)<\omega_1$.
\end{theorem}
\proof
By the argument used in the proof of Lemma \ref{mapping}
we can find
$$\langle G_\alpha:\alpha<\omega_2\rangle\in V[G]$$
which is
$\sum_{\alpha<\omega_2}\fin(\omega,2)$-generic over
$V$ and
a $\fin(\omega,2)$-name $\tau$ for an element of $\cantorspace$ such
that $Y=\{\tau^{G_\alpha}:\alpha<\omega_2\}$ is subset of
$X$. We claim that $\ord(Y)<\omega_1$.
Let $${\famly}=\{\val{\tau\in C}: C\subseteq\cantorset \mbox{ clopen }\}$$
where boolean values are in
the unique complete boolean algebra $\bool$ in which $\fin(\omega,2)$
is dense.
Let $\fbool$ be the complete subalgebra of $\bool$ which is generated
by $\famly$. First note that the order of $\famly$ in $\fbool$ is
less than $\omega_1$. This is because $\fbool$ contains a countable dense
set:
$$D=\{\prod\{c\in {\fbool}:p\leq c\}: p\in \fin(\omega,2)\}.$$
Since $D$ is countable and $\bsig01(D)={\fbool}$, it follows that
the order of $\famly$ is countable.
I claim that the order of $Y$ is essentially less than or equal
to the order of $\famly$ in ${\fbool}$.
\begin{lemma}\label{boolborel}
Let $\bool$ be a cBa, $\tau$ a $\bool$-name for an element of
$\cantorset$, and
$$\famly=\{\val{\tau\in C}: C\subseteq\cantorset \mbox{ clopen }\}.$$
Then for each $B\subseteq\cantorspace$ a $\bpi0\alpha$ set coded in $V$
the boolean value
$
\val{\tau\in\check{B}}
$
is $\bpi0\alpha({\famly})$ and conversely, for every
$c\in \bpi0\alpha({\famly})$ there exists a
$B\subseteq\cantorspace$ a $\bpi0\alpha$ set coded in $V$ such
that
$
c = \val{\tau\in\check{B}}
.$
\end{lemma}
\proof
Both directions of the lemma are simple inductions.
\qed
Now suppose the order of $\famly$ in ${\fbool}$ is $\alpha$.
Let $B\subseteq\cantorspace$ be any Borel set coded in $V[G]$.
By ccc there exists $H=G\res\Sigma$ where $\Sigma\subseteq\kappa$
is countable set in $V$ such that $B$ is coded in $V[H]$. Consequently,
since we could replace $V$ with $V[H]$ and delete countably many elements
of $Y$ we may as well assume that $B$ is coded in the ground model.
Since the order of $\famly$ is $\alpha$ we have by the lemma
that there exists a $\bpi0\alpha$ set $A$ such that
$$\val{\tau\in \check{A}} = \val{\tau\in \check{B}}.$$
It follows that
$$Y\intersect A= Y\intersect B$$
and hence order of $Y$ is less than or equal to $\alpha$
(or three since we neglected countably many elements of $Y$).
\qed
\sector{The random real model}
In this section we consider the question of \label{random}
Borel orders in the random real model. We conclude with a few
remarks about perfect set forcing.
A set $X\subseteq\cantorspace$ is a \dex{Sierpi\'{n}ski set} iff
$X$ is uncountable and for every measure zero set
$Z$ we have $X\intersect Z$ countable. Note that
by Mahlo's Theorem \ref{mah} we know that under CH
Sierpi\'{n}ski sets exists. Also it is easy to see that in the
random real model, the set of reals given by the generic
filter is a Sierpi\'{n}ski set.
\begin{theorem}
(Poprougenko \site{pop}) \label{pop}
If $X$ is Sierpi\'{n}ski, then $\ord(X)=2$.
\end{theorem}
\proof
For any Borel set $B\subseteq\cantorspace$ there exists
an $F_\sigma$ set with $F\subseteq B$ and $B\setminus F$
measure zero.
Since $X$ is Sierpi\'{n}ski $(B\setminus F)\intersect X=F_0$ is
countable, hence $F_\sigma$. So
$$B\intersect X= (F\union F_0)\intersect X.$$
\qed
I had been rather hoping that every uncountable separable metric
space in the random real model has order either 2 or $\omega_1$.
The following result shows that this is definitely not the case.
\begin{theorem} \label{rand}
Suppose $X\in V$ is a subspace of $\cantorset$ of order $\alpha$
and $G$ is measure algebra $2^\kappa$-generic over $V$, i.e.
adjoin $\kappa$ many random reals.
Then $V[G]\models \alpha\leq\ord(X)\leq\alpha+1$.
\end{theorem}
The result will easily follow from the next two lemmas.
Presumably, $\ord(X)=\alpha$ in $V[G]$,
but I haven't been able to prove this. Fremlin's proof
(Theorem \ref{frem}) having filled up one such missing gap,
leaving this gap here restores a certain
cosmic balance of ignorance.\footnote{All things I thought I knew;
but now confess,
the more I know I know, I know the less.- John Owen (1560-1622)}
Clearly, by the usual ccc arguments, we may assume
that $\kappa=\omega$ and $G$ is just a random real.
In the following lemmas boolean values $\val{\theta}$ will
be computed in the measure algebra $\bool$ on $\cantorspace$.
Let $\mu$ \sdex{$\mu$} be the usual product measure on $\cantorspace$.
\begin{lemma} \label{random1}
Suppose $\epsilon$ a real, $b\in\bool$, and
$\name{U}$ the name of a $\bpi0\alpha$
subset of $\cantorspace$ in $V[G]$. Then the set
$$\{x\in\cantorspace: \mu(b\conj\val{\check{x}\in\name{U}})\geq\epsilon\}$$
is $\bpi0\alpha$ in $V$.
\end{lemma}
\proof
The proof is by induction on $\alpha$.
\bigskip
Case $\alpha=1$.
\par\noindent
If $\name{U}$ is a name for a closed set, then
$$\val{\check{x}\in \name{U}}=\prod_{n\in\omega}\val{[x\res n]\intersect
\name{U}\not=\emptyset}.$$
Consequently,
$$\mu(b\conj\val{\check{x}\in\name{U}})\geq\epsilon$$
iff
$$\forall n\in\omega\;\;\mu(b\conj\val{[x\res n]\intersect
\name{U}\not=\emptyset})\geq\epsilon$$
and the set is closed.
\bigskip
Case $\alpha>1$.
\par\noindent Suppose $\name{U}=\Intersect_{n\in\omega}\comp{\name{U_n}}$
where
each $\name{U_n}$ is a name for a $\bpi0{\alpha_n}$ set
for some $\alpha_n<\alpha$. We can assume that the sequence
$\comp{U_n}$ is descending.
Consequently,
$$\mu(b\conj\val{\check{x}\in\check{U}})\geq\epsilon$$
iff
$$\mu(b\conj\val{\check{x}\in\Intersect_{n\in\omega}\comp{\name{U_n}} })
\geq\epsilon $$
iff
$$ \forall n \in \omega \;\;
\mu(b\conj\val{\check{x}\in\comp{\name{U_n}} })
\geq\epsilon $$
iff
$$ \forall n \in \omega \;\;
\mbox{ not }\mu(b\conj\val{\check{x}\in{\name{U_n}} })
>\mu(b)-\epsilon. $$
iff
$$ \forall n \in \omega \;\;
\mbox{ not }\exists m\in \omega\;\;\mu(b\conj\val{\check{x}\in{\name{U_n}} })
\geq\mu(b)-\epsilon+1/m $$
By induction, each of the sets
$$\{x\in\cantorspace: \mu(b\conj\val{\check{x}\in{\name{U_n}} })
\geq\mu(b)-\epsilon+1/m\}$$
is $\bpi0{\alpha_n}$ and so the result is proved.
\qed
It follows from this lemma that if $X\subseteq\cantorspace$ and
$V\models$``$\ord(X)>\alpha$'', then
$V[G]\models$``$\ord(X)>\alpha$''. For suppose $F\subseteq\cantorspace$
is $\bsig0\alpha$ such that for every $H\subseteq\cantorspace$ which
is $\bpi0\alpha$ we have $F\intersect X\not= H\intersect X$.
Suppose for contradiction that
$$b\forces \mbox{``}\name{U}\intersect \check{X}=\check{F}\intersect \check{X}
\rmand
\name{U}\mbox{ is } \bpi0\alpha\mbox{''}.$$
But then
$$\{x\in\cantorspace: \mu(b\conj\val{\check{x}\in\check{U}})=\mu(b)\}$$
is a $\bpi0\alpha$ set which must be equal to $F$ on $X$, which is
a contradiction.
To prove the other direction of the inequality we will use the following
lemma.
\begin{lemma} \label{random2}
Let $G$ be $\bool$-generic
(where $\bool$ is the measure algebra on $\cantorspace$)
and $r\in\cantorspace$ is the associated
random real. Then for any $b\in\bool$
$$b\in G \rmiff
\forall^\infty n\; \mu([r\res n]\conj b)\geq {3\over 4}\mu([r\res n]).$$
\end{lemma}
\proof
Since $G$ is an ultrafilter it is enough to show that
$b\in G$ implies
$$\forall^\infty n\; \mu([r\res n]\conj b)\geq {3\over 4}\mu([r\res n]).$$
Let $\bool^+$ be the nonzero elements of $\bool$.
To prove this it suffices to show:
\claim For any $b\in\bool^+$ and
for every $d\leq b$ in $\bool^+$ there exists a tree
$T\subseteq 2^{<\omega}$ with $[T]$ of positive measure, $[T]\leq d$,
and
$$\mu([s]\intersect b)\geq {3\over 4}\mu([s])$$
for all but finitely many $s\in T$.
\proof
Without loss we may assume that $d$ is a closed set and
let $T_d$ be a tree such that $d=[T_d]$. Let $t_0\in T_d$ be such
that $$\mu([t_0]\intersect [T_d])\geq {9\over 10}\mu([t_0]).$$
Define a subtree $T\subseteq T_d$ by $r\in T$ iff $r\subseteq t_0$ or
$t_0\subseteq r$ and
$$\forall t\;( t_0\subseteq t\subseteq r\mbox{ implies } \mu([t]\intersect b)
\geq{3\over 4}\mu([t])\;).$$
So we only need to see that $[T]$ has positive measure. So suppose
for contradiction that $\mu([T])=0$. Then for some sufficiently large
$N$
$$\mu(\Union_{s\in T\intersect 2^N} [s])\leq {1\over 10}\mu([t_0]).$$
For every $s\in T_d\intersect 2^N$ with $t_0\subseteq s$, if
$s\notin T$ then there exists $t$ with $t_0\subseteq t\subseteq s$ and
$\mu([t]\intersect b)<{3\over 4}\mu([t])$. Let $\Sigma$ be a maximal
antichain of $t$ like this. But note that
$$[t_0]\intersect [T_d]\subseteq \Union_{s\in 2^N\intersect T}[s]\union
\Union_{t\in\Sigma}([t]\intersect b).$$
By choice of $\Sigma$
$$\mu(\Union_{s\in\Sigma}[s]\intersect b)\leq {3\over 4}\mu([t_0])$$
and by choice of $N$
$$\mu(\Union_{s\in 2^N\intersect T}[s])\leq {1\over 10}\mu([t_0])$$
which contradicts the choice of $t_0$:
$$\mu([t_0]\intersect [T_d])\leq ({1\over 10}+{3\over 4})
\mu([t_0])=\footnote{Trust me on this, I have been teaching a lot
of Math 99 ``College Fractions''.}
\;\;{17\over 20}\mu([t_0])<{9\over 10} \mu([t_0]).$$
This proves the claim and the lemma.
\qed
In effect, what we have done in Lemma \ref{random2} is reprove
the Lebesgue density theorem, see Oxtoby \site{oxt}.
So now suppose that the order of $X$ in $V$ is $\leq \alpha$.
We show that it is $\leq \alpha+1$ in $V[G]$. Let $\name{U}$ be
any name for a Borel subset of $X$ in the extension. Then
we know that $x\in U^G$ iff $\val{\check{x}\in \name{U}}\in G$.
By Lemma \ref{random1} we know that
for any $s\in 2^{<\omega}$ the set
$$B_s=\{x\in X:
\mu([s]\intersect \val{\check{x}\in \name{U}})\geq {3\over 4}\mu([s])\}$$
is a Borel subset of $X$ in the ground model and hence is
$\bpi0\alpha(X)$. By Lemma \ref{random2} we have
that for any $x\in X$
$$x\in U \rmiff \forall^\infty n \; \; x\in B_{r\res n}$$
and so $U$ is $\bsig0{\alpha+1}(X)$ in V[G].
This concludes the proof of Theorem \ref{rand}.
\qed
Note that this result does allow us to get sets of order
$\lambda$ for any countable limit ordinal $\lambda$ by taking a
clopen separated union of a sequence of sets whose order goes up $\lambda$.
Also a Luzin set $X$ from the ground model has order $3$ in the random
real extension. Since $(\ord(X)=3)^V$ we know that
$(3\leq \ord(X)\leq 4)^{V[G]}$. To see that $(\ord(X)\leq 3)^{V[G]}$ suppose
that $B\subseteq X$ is Borel in $V[G]$. The above proof shows that
there exists Borel sets $B_n$ each coded in $V$ (but the sequence
may not be in $V$) such that
$$x\in B \rmiff \forall^{\infty} n \;\; x\in B_n.$$
For each $B_n$ there exists an open set $U_n\subseteq X$
such that $B_n\Delta U_n$ is countable. If we let
$$C=\Union_{n\in\omega}\Intersect_{m>n} U_m$$
then $C$ is $\bsig03(X)$ and $B\Delta C$ is countable. Since
subtracting and adding a countable set from a $\bsig03(X)$ is
still $\bsig03(X)$ we have that $B$ is $\bsig03(X)$ and so
the order of $X$ is $\leq 3$ in $V[G]$.
\begin{theorem} \label{randlast}
Suppose $V$ models CH and $G$ is measure algebra on $2^\kappa$-generic
over $V$ for some $\kappa\geq \omega_2$. Then in $V[G]$ for
every $X\subseteq \cantorspace$ of cardinality $\omega_2$
there exists $Y\in [X]^{\omega_2}$ with $\ord(Y)=2$.
\end{theorem}
\proof
Using the same argument as in the proof of Theorem \ref{cohenmodel3}
we can get a Sierpi\'{n}ski set $S\subseteq\cantorspace$ of cardinality
$\omega_2$ and a term $\tau$ for any element of $\cantorspace$ such
that $Y=\{\tau^r:r\in S\}$ is a set of distinct elements of
$X$. This Sierpi\'{n}ski set has two additional properties:
every element of it is random over the ground model and
it meets every set of positive measure, i.e. it is a
super Sierpi\'{n}ski set.
We will show that the order of $Y$ is $2$.
\begin{lemma}
Let $\famly\subseteq\bool$ be any subset
of a measure algebra $\bool$ closed under finite conjunctions.
Then $\bpi02(\famly)=\bsig02(\famly)$, i.e. $\famly$ has order $\leq 2$.
\end{lemma}
\proof
Let $\mu$ be the measure on $\bool$.
\medskip
\noindent (1) For any $b\in\bpi01(\famly)$ and real $\epsilon>0$
there exists $a\in\famly$ with $b\leq a$ and $\mu(a-b)<\epsilon$.
pf:\footnote{Pronounced `puff'.} $\;\; b=\prod_{n\in\omega} a_n$.
Let $a=\prod_{n0$
there exists $a\in\bsig01(\famly)$ with $b\leq a$ and $\mu(a-b)<\epsilon$.
pf: $b=\sum_{n<\omega}b_n$. Applying (1) we get $a_n\in\famly$ with
$b_n\leq a_n$ and $$\mu(a_n-b_n)<{\epsilon\over{2^n}}.$$
Then let $a=\sum_{n\in\omega} a_n$.
\bigskip
Now suppose $b\in\bsig02(\famly)$. Then by applying (2) there exists
$a_n\in\bsig01(\famly)$ with $b\leq a_n$ and $\mu(a_n-b)<1/n$.
Consequently, if $a=\prod_{n\in\omega}a_n$, then $b\leq a$ and
$\mu(a-b)=0$ and so $a=b$.
\qed
Let $${\famly}=\{\val{\tau\in C}: C\subseteq\cantorset \mbox{ clopen }\}$$
where boolean values are in the measure algebra $\bool$ on
$\cantorspace$.
Let $\fbool$ be the complete subalgebra of $\fbool$ which is generated
by $\famly$.
Since the order of $\famly$ is $2$, by Lemma \ref{boolborel}
we have
that for any Borel set $B\subseteq Y$ there exists a $\bsig02(Y)$ set
$F$ such that $y\in B$ iff $y\in F$ for all but countably many $y\in Y$.
Thus we see that the order of $Y$ is $\leq 3$. To get it down
to $2$ we use the following lemma. If $B=(F\setminus F_0)\union F_1$ where
$F_0$ and $F_1$ are countable and $F$ is $\bsig02$, then by the lemma
$F_0$ would be $\bpi02$ and thus $B$ would be $\bsig02$.
\begin{lemma}
Every countable subset of $Y$ is $\bpi02(Y)$.
\end{lemma}
\proof
It suffices to show that every countable subset of $Y$ can be covered
by a countable $\bpi02(Y)$ since one can always subtract a countable
set from a $\bpi02(Y)$ and remain $\bpi02(Y)$.
For any $s\in 2^{<\omega}$ define
$$b_s=\val{s\subseteq \tau}.$$
Working in the ground model let $B_s$ be a Borel
set with $[B_s]_{\bool}=b_s$. Since the
Sierpi\'{n}ski set consists only of reals random over the ground
model we know that for every $r\in S$
$$r\in B_s\rmiff s\subseteq \tau^r.$$
Also since the Sierpi\'{n}ski set meets every Borel set of positive measure
we know that for any $z\in Y$ the set $\Intersect_{n<\omega}B_{z\res n}$
has measure zero. Now let $Z=\{z_n:n<\omega\}\subseteq Y$ be arbitrary
but listed with infinitely many repetitions. For each $n$ choose $m$ so
that
if $s_n=z_n\res m$, then $\mu(B_{s_n})<1/{2^n}$.
Now for every $r\in S$ we have that
$$r\in\Intersect_{n<\omega}\Union_{m>n} B_{s_m} \rmiff
\tau^r\in\Intersect_{n<\omega}\Union_{m>n} [s_m]. $$
The set $H=\Intersect_{n<\omega}\Union_{m>n} [s_m]$ covers $Z$ and
is $\bpi02$.
It has countable intersection with $Y$ because
the set $\Intersect_{n<\omega}\Union_{m>n} B_{s_m}$ has
measure zero.
This proves the Lemma and Theorem \ref{randlast}.
\qed
%%%%%%%%%%%%%%% sacks model %%%%%%%%%%%%%%%
\bigskip\bigskip\bigskip
\begin{center}
Perfect Set Forcing
\end{center}
\bigskip
\sdex{perfect set forcing}
In the iterated \dex{Sack's real model} the continuum is
$\omega_2$ and every set $X\subseteq\cantorspace$
of cardinality $\omega_2$ can
be mapped continuously onto $\cantorspace$ (Miller \site{maponto}).
It follows from Rec{\l}aw's
Theorem \ref{rec}
that in this model every separable metric space of cardinality
$\omega_2$ has order $\omega_1$. On the other hand this
forcing (and any other with the Sack's property) has the property
that every meager set in the extension is covered by a meager set
in the ground model and every measure set in the extension is covered
by a measure zero set in the ground model (see Miller \site{someprop}).
Consequently, in this model there are Sierpi\'{n}ski sets and Luzin sets
of cardinality $\omega_1$. Therefore in the iterated Sacks real
model there are separable metric spaces of cardinality $\omega_1$
of every order $\alpha$ with $2\leq\alpha<\omega_1$. I do not know
if there is an uncountable separable metric space which is hereditarily
of order $\omega_1$ in this model.
Another way to obtain the same orders is to use the construction
of Theorem 22 of Miller \site{borelhier}. What was done there implies
the following:
\begin{quote}
For any model $V$ there
exists a ccc extension $V[G]$ in which every uncountable separable
metric space has order $\omega_1$.
\end{quote}
If we apply this result $\omega_1$ times with a finite support extension,
we get a model, $V[G_\alpha:\alpha<\omega_1]$, where there are
separable metric spaces of all orders of cardinality $\omega_1$,
but every separable metric space of cardinality $\omega_2$ has
order $\omega_1$.
To see the first fact note that $\omega_1$ length finite
support iteration always adds
a Luzin set. Consequently, by Theorem \ref{cohenluz},
for each $\alpha$ with
$2<\alpha<\omega_1$ there
exists a separable metric space of cardinality $\omega_1$
which is hereditarily of order $\alpha$. Also there is such an
$X$ of order $2$ by the argument used in Theorem \ref{cohenmodel}.
On the other hand if $X$ has cardinality $\omega_2$ in
$V[G_\alpha:\alpha<\omega_1]$, then for some $\beta<\omega_1$ there
exists and uncountable $Y\in V[G_\alpha:\alpha<\beta]$
with $Y\subseteq X$. Hence $Y$ will have order $\omega_1$ in
$V[G_\alpha:\alpha<\beta+1]$ and
by examining the proof it is easily seen that it remains of order
$\omega_1$ in $V[G_\alpha:\alpha<\omega_1]$.
\sector{Covering number of an ideal}
This section is a small diversion.\footnote{All men's gains are the fruit
of venturing. Herodotus BC 484-425.}
It is motivated by
Theorem \ref{marsolthm} of Martin and Solovay.
Define for any ideal $I$ in $\borel(\cantorspace)$
$$\cov(I)=\min\{|\ideal|: \ideal\subseteq I, \; \Union\ideal=\cantorset\}.$$
The following theorem is well-known. \sdex{$\cov(I)$}
\begin{theorem} \label{count}
For any cardinal $\kappa$ the following are equivalent:
\begin{enumerate}
\item \dex{MA$_\kappa$(ctbl)}, i.e. for any countable poset, $\poset$,
and family $\dense$ of dense subsets of $\poset$ with $|\dense|<\kappa$
there exists a $\poset$-filter $G$ with $G\intersect D\not=\emptyset$
for every $D\in\dense$, and
\item $\cov(\meager(\cantorset))\geq\kappa$.
\end{enumerate}
\end{theorem} \sdex{$\cov(\meager(\cantorset))$}
\proof
MA$_\kappa$(ctbl) implies $\cov(\meager(\cantorset))\geq\kappa$, is easy
because if $U\subseteq\cantorspace$ is a dense open set, then
$$D=\{s\in 2^{<\omega}: [s]\subseteq U\}$$
is dense in $2^{<\omega}$.
$\cov(\meager(\cantorset))\geq\kappa$ implies MA$_\kappa$(ctbl) follows
from the fact that any countable poset, $\poset$, either contains
a dense copy of $2^{<\omega}$ or contains a $p$ such that
every two extensions of $p$ are compatible.
\qed
\begin{theorem} \label{cofcov}
(Miller \site{ctlbcof}) $\cof(\cov(\meager(\cantorset)))>\omega$, e.g.,
it is impossible to have $\cov(\meager(\cantorset))=\aleph_\omega$.
\end{theorem}
\proof
Suppose for contradiction that $\kappa=\cov(\meager(\cantorset))$ has
countable cofinality and let $\kappa_n$ for $n\in\omega$ be a cofinal
sequence in $\kappa$. Let $\langle C_\alpha:\alpha<\kappa\rangle$ be
a family of closed nowhere dense sets which cover $\cantorset$.
We will construct a sequence $P_n\subseteq\cantorset$
of perfect sets with the properties that
\begin{enumerate}
\item $P_{n+1}\subseteq P_n$,
\item $P_n\intersect \Union\{C_\alpha:\alpha<\kappa_n\}=\emptyset$, and
\item $\forall \alpha<\kappa\;\;\;C_\alpha\intersect P_n$ is nowhere dense
in $P_n$.
\end{enumerate}
This easily gives a contradiction, since $\Intersect_{n<\omega}P_n$ is
nonempty and disjoint from all $C_\alpha$, contradicting the
fact that the $C_\alpha$'s cover $\cantorspace$.
We show how to obtain $P_0$, since the argument easily relativizes to show
how to obtain $P_{n+1}$ given $P_n$. Since
$\cov(\meager(\cantorset))>\kappa_n$ there exists a countable sequence
$$D=\{x_n:n\in\omega\}\subseteq\cantorspace$$
such that $D$ is dense and for every $n$
$$x_n\notin\Union_{\alpha<\kappa_n}C_\alpha.$$
Consider the following forcing notion $\poset$.
$$\poset=\{(H,n): n\in\omega \rmand H\in [D]^{<\omega}\}$$
This is ordered by $(H,n)\leq (K,m)$ iff
\begin{enumerate}
\item $H\supseteq K$,
\item $n\geq m$, and
\item for every $x\in H$ there exists $y\in K$ with $x\res m= y\res m$.
\end{enumerate}
Note that $\poset$ is countable.
For each $n\in\omega$ define $E_n\subseteq\poset$ by $(H,m)\in E_n$
iff
\begin{enumerate}
\item $m>n$ and
\item $\forall x\in H \exists y\in H\;
x\res n=y\res n$ but $x\res m\not=y\res m$.
\end{enumerate}
and for each $\alpha<\kappa_0$ let
$$F_\alpha=\{(H,m)\in\poset: \forall x\in H\;\;
[x\res m]\intersect C_\alpha=\emptyset\}.$$
For $G$ a $\poset$-filter, define $X\subseteq D$ by
$$X=\Union\{H: \exists n\; (H,n)\in G\}$$
and let $P=cl(X)$.
It easy to check that the $E_n$'s are dense and if $G$ meets each
one of them, then $P$ is perfect (i.e. has no isolated points).
The $F_\alpha$ for $\alpha<\kappa_0$ are
dense in $\poset$. This is because $D\intersect C_\alpha=\emptyset$
so given $(H,n)\in\poset$ there exists $m\geq n$ such that
for every $x\in H$ we have $[x\res m]\intersect C_\alpha=\emptyset$
and thus $(H,m)\in F_\alpha$. Note that if
$G\intersect F_\alpha\not=\emptyset$, then
$P\intersect C_\alpha=\emptyset$. Consequently, by Theorem \ref{count},
there exists a $\poset$-filter $G$ such that $G$ meets
each $E_n$ and all $F_\alpha$ for $\alpha<\kappa_0$.
Hence $P=cl(X)$ is a perfect set which is disjoint from
each $C_\alpha$ for $\alpha<\kappa_0$. Note also that
for every $\alpha<\kappa$ we have that $C_\alpha\intersect D$ is
finite and hence $C_\alpha\intersect X$ is finite and
therefore $C_\alpha\intersect P$ is nowhere dense in $P$.
This ends the construction of $P=P_0$ and since the $P_n$ can
be obtained with a similar argument, this proves the Theorem.
\qed
\begin{question}
(Fremlin) Is the same true for the measure zero ideal in place of
the ideal of meager sets?
\end{question}
Some partial results are known (see Bartoszynski, Judah, Shelah
\site{barto}\site{barto2}\site{barto3}).
\begin{theorem}
(Miller \site{ctlbcof}) It is consistent that
$\cov(\meager(2^{\omega_1}))=\aleph_\omega$.
\end{theorem}
\proof
In fact, this holds in the model obtained by forcing with
$\fin(\aleph_\omega,2)$ over a model of GCH. \sdex{$?fin(\aleph_\omega,2)$}
\bigskip
$\cov(\meager(2^{\omega_1}))\geq\aleph_\omega$: Suppose
for contradiction that
$$\{C_\alpha:\alpha<\omega_n\}\in V[G]$$
is a family
of closed nowhere dense sets covering $2^{\omega_1}$.
Define
$$E_\alpha=\{s\in \fin(\omega_1,2): [s]\intersect C_\alpha=\emptyset\}.$$
Using ccc, there exists $\Sigma\in[\aleph_\omega]^{\omega_n}$
in $V$ with
$$\{E_\alpha:\alpha<\omega_n\}\in V[G\res\Sigma].$$
Let $X\subseteq \aleph_\omega$ be a set in $V$ of cardinality $\omega_1$
which is disjoint from $\Sigma$. By the product lemma
$G\res X$ is $\fin(X,2)$-generic over $V[G\res \Sigma]$. Consequently,
if $H:\omega_1\arrow 2$ corresponds to $G$ via an isomorphism
of $X$ and $\omega_1$, then $H\notin C_\alpha$ for every
$\alpha<\omega_n$.
\bigskip
$\cov(\meager(2^{\omega_1}))\leq\aleph_\omega$: Note that for
every uncountable $X\subseteq\omega_1$ such that $X\in V[G]$ there exists
$$n\in\omega \rmand Z\in[\omega_1]^{\omega_1}\intersect V[G\res\omega_n]$$
with $Z\subseteq X$. To see this, note that for every $\alpha\in X$ there
exists $p\in G$ such that $p\forces \alpha\in X$
and $p\in\fin(\omega_n,2)$ for some $n\in\omega$. Consequently, by ccc,
some $n$ works for uncountably many $\alpha$.
Consider the family
of all closed nowhere dense sets $C\subseteq 2^{\omega_1}$ which
are coded in some $V[G\res\omega_n]$ for some $n$. We claim that
these cover $2^{\omega_1}$. This follows from above,
because for any $Z\subseteq\omega_1$ which is infinite the
set
$$C=\{x\in 2^{\omega_1}: \forall \alpha\in Z \;\; x(\alpha)=1\}$$
is nowhere dense.
\qed
\begin{theorem}
(Miller \site{ctlbcof}) It is consistent that
there exists a ccc $\sigma$-ideal $I$ in
$\borel(\cantorset)$ such that $\cov(I)=\aleph_\omega$.
\end{theorem}
\proof
Let $\poset=\fin(\omega_1,2)*\name{\posetq}$ where $\name{\posetq}$
is a name for the Silver forcing which codes up generic filter
for $\fin(\omega_1,2)$
just like in the proof of Theorem \ref{marsolthm}. Let
$\prod_{\alpha<\aleph_{\omega}}\poset$ be the direct sum (i.e. finite
support product) of $\aleph_{\omega}$ copies of $\poset$. Forcing
with the direct sum adds a
filter $G=\langle G_\alpha:\alpha<\aleph_{\omega} \rangle$
where each $G_\alpha$ is $\poset$-generic. In general,
a direct sum is ccc iff every finite subproduct is ccc. This follows by
a delta-system argument. Every finite product of $\poset$ has
ccc, because $\poset$ is $\sigma$-centered, i.e., it is the countable
union of centered sets.
Let $V$ be a model of GCH and
$G=\langle G_\alpha:\alpha<\aleph_{\omega} \rangle$
be $\prod_{\alpha<\aleph_{\omega}}\poset$ generic over $V$.
We claim that in $V[G]$ if $I$ is the $\sigma$-ideal given by Sikorski's
Theorem \ref{sikorthm} such that $\prod_{\alpha<\aleph_{\omega}}\poset$ is
densely embedded into $\borel(\cantorset)/I$ then
$\cov(I)=\aleph_\omega$.
First define,
$m_\poset$, to be the cardinality of the minimal failure
of MA for $\poset$, i.e., the least $\kappa$ such that
there exists a family $|\dense|=\kappa$ of dense subsets of
$\poset$ such that there is no $\poset$-filter meeting all
the $D\in\dense$. \sdex{$m_?poset$}
\begin{lemma}
In $V[\langle G_\alpha:\alpha<\aleph_{\omega}\rangle]$ we have that
$m_\poset=\aleph_\omega$.
\end{lemma}
\proof
Note that for any set $D\subset\poset$ there exists a set
$\Sigma\in[\aleph_\omega]^{\omega_1}$ in $V$ with
$D\in V[\langle G_\alpha:\alpha\in\Sigma\rangle]$. So if
$|\dense|=\omega_n$ then there exists
$\Sigma\in[\aleph_\omega]^{\omega_n}$ in $V$ with
$\dense\in V[\langle G_\alpha:\alpha\in\Sigma\rangle]$.
Letting $\alpha\in\aleph_\omega\setminus \Sigma$ we get
$G_\alpha$ a $\poset$-filter meeting every $D\in\dense$.
Hence $m_\poset\geq\aleph_\omega$.
On the other hand:
\claim For every
$X\in[\omega_1]^{\omega_1}\intersect
V[\langle G_\alpha:\alpha<\aleph_{\omega}\rangle]$ there exists $n\in\omega$
and $Y\in [\omega_1]^{\omega_1}\intersect
V[\langle G_\alpha:\alpha<\aleph_{n}\rangle]$ with $Y\subseteq X$.
\proof
For every $\alpha\in X$ there exist $p\in G$ and $n<\omega$ such that
$p\forces \check{\alpha}\in \name{X}$ and $\dom(p)\subseteq\aleph_n$.
Since $X$ is uncountable there is one $n$ which works for uncountably
many $\alpha\in X$.
\qed
It follows from the Claim that there is no $H$ which is
$\fin(\omega_1,2)$ generic over all the models
$V[\langle G_\alpha:\alpha<\aleph_{n}\rangle]$, but forcing with $\poset$
would add such an $H$ and so $m_\poset\leq\aleph_\omega$ and
the Lemma is proved. \qed
\begin{lemma}
If $\poset$ is ccc and dense in the cBa $\borel(\cantorset)/I$,
then $m_\poset=\cov(I)$.
\end{lemma}
\proof
This is the same as Lemma \ref{martinlem} equivalence of (1) and (3),
except you have to check that $m$ is the same for both
$\poset$ and $\borel(\cantorset)/I$.
\qed
Kunen \site{kunenma} showed that least cardinal for which MA fails
can be a singular cardinal of cofinality $\omega_1$, although
it is impossible for it to have cofinality $\omega$ (see Fremlin
\site{frembook}).
It is still
open whether it can be a singular cardinal of cofinality
greater than $\omega_1$ (see Landver \site{landver}).
Landver \site{landver2} generalizes Theorem \ref{cofcov}
to the space $2^\kappa$ with basic clopen sets of
the form $[s]$ for $s\in 2^{<\kappa}$. He uses a generalization
of a characterization
of $\cov(\meager(\cantorspace))$ due to Bartoszynski \site{barto4}
and Miller \site{char}.
\newpage \part{Analytic sets}
\section{Analytic sets}
Analytic sets were discovered by Souslin when he encountered a mistake
of Lebesgue. Lebesgue had erroneously proved that the Borel sets
were closed under projection. I think the mistake he made was
to think that the countable intersection commuted with projection.
A good reference is the volume devoted to analytic sets edited by
Rogers \site{anal}. For the more classical viewpoint
of operation-A, see Kuratowski \site{kur}. For the whole
area of descriptive set theory and its history, see
Moschovakis \site{mosch}.
\bigskip
Definition. A set $A\subseteq\bairespace$ is $\Sigma^1_1$ iff
\sdex{$\Sigma^1_1$}
there exists a recursive
$$R\subseteq \Union_{n\in\omega}(\omega^n\cross\omega^n)$$
such that for all $x\in\bairespace$
$$x\in A \rmiff \exists y \in\bairespace\;\forall n\in\omega\;\;
R(x\res n, y\res n).$$
A similar definition applies for $A\subseteq \omega$ and also
for $A\subseteq \omega\cross\bairespace$ and so forth. For
example, $A\subseteq\omega$ is $\Sigma^1_1$ iff there
exists a recursive $R\subseteq \omega\cross \finseq$ such that
for all $m\in\omega$
$$m\in A \rmiff \exists y \in\bairespace\;\forall n \in\omega\;\;
R(m, y\res n).$$
A set $C\subseteq\bairespace\cross\bairespace$ is $\Pi_1^0$ iff
\sdex{$\Pi_1^0$}
there exists a recursive predicate
$$R\subseteq \Union_{n\in\omega}(\omega^n\cross\omega^n)$$ such that
$$C=\{(x,y):\forall n \; R(x\res n, y\res n)\}.$$ That means basically
that $C$ is a recursive closed set.
The $\Pi$ classes are the complements of the $\Sigma$'s and
$\Delta$ is the class of sets which are both $\Pi$ and $\Sigma$.
The relativized classes, e.g. $\Sigma^1_1(x)$ are obtained by
\sdex{$\Sigma^1_1(x)$}
allowing $R$ to be recursive in $x$, i.e., $R\leq_T x$. The boldface
classes, e.g., $\bsig11$, $\bpi11$, are obtained by taking arbitrary $R$'s.
\sdex{$?bsig11$} \sdex{$?bpi11$}
\begin{lemma}
$A\subseteq\bairespace$ is $\Sigma^1_1$ iff there exists
set $C\subseteq\bairespace\cross\bairespace$ which is $\Pi_1^0$
and $$A=\{x\in\bairespace: \exists y \in \bairespace\;\; (x,y)\in C\}.$$
\end{lemma}
\begin{lemma} \label{catchall} The following are all true:
\begin{enumerate}
\item For every $s\in\finseq$ the basic
clopen set $[s]=\{x\in\bairespace: s\subseteq x\}$ is $\Sigma^1_1$,
\item if $A\subseteq \bairespace\cross\bairespace$ is $\Sigma^1_1$,
then so is
$$B=\{x\in\bairespace: \exists y\in\omega \;(x,y)\in A\},$$
\item if $A\subseteq \omega\cross\bairespace$ is $\Sigma^1_1$,
then so is
$$B=\{x\in\bairespace: \exists n\in\omega \;(n,x)\in A\},$$
\item if $A\subseteq \omega\cross\bairespace$ is $\Sigma^1_1$,
then so is
$$B=\{x\in\bairespace: \forall n\in\omega \;(n,x)\in A\},$$
\item if $\langle A_n: n\in\omega\rangle$ is sequence of
$\Sigma_1^1$ sets given by the recursive predicates
$R_n$ and $\langle R_n: n\in\omega\rangle$ is (uniformly)
recursive, then both
$$\Union_{n\in\omega} A_n \rmand \Intersect_{n\in\omega} A_n
\mbox{ are } \Sigma_1^1.$$
\item if the graph of $f:\bairespace\arrow\bairespace$ is
$\Sigma^1_1$ and
$A\subseteq \bairespace$ is $\Sigma^1_1$, then $f^{-1}(A)$
is $\Sigma^1_1$.
\end{enumerate}
\end{lemma}
Of course, the above lemma is true with $\omega$ or $\omega\cross\bairespace$,
etc., in place of $\bairespace$. It also relativizes to
any class $\Sigma^1_1(x)$. It follows
from the Lemma that every Borel subset of $\bairespace$ is $\bsig11$
and that the continuous pre-image of $\bsig11$ set is $\bsig11$.
\begin{theorem}
There exists a $\Sigma^1_1$ set $U\subseteq \bairespace\cross\bairespace$
which is universal for all $\bsig11$ sets, i.e., for every
$\bsig11$ set $A\subseteq\bairespace$ there exists $x\in\bairespace$
with $$A=\{y:(x,y)\in U\}.$$ \sdex{universal for $?bsig11$ sets}
\end{theorem}
\proof
There exists $C\subseteq\bairespace\cross\bairespace\cross\bairespace$
a $\Pi_1^0$ set which is universal for $\bpi01$ subsets
of $\bairespace\cross\bairespace$. Let $U$ be the projection of
$C$ on its second coordinate.
\qed
Similarly we can get $\Sigma^1_1$ sets contained in $\omega\cross\omega$
(or $\omega\cross\bairespace$) which are universal for $\Sigma^1_1$ subsets
of $\omega$ (or $\bairespace$).
The usual diagonal argument shows that
there are $\Sigma^1_1$ subsets of $\bairespace$ which are not $\bpi11$ and
$\Sigma^1_1$ subsets of $\omega$ which are not $\Pi^1_1$.
\begin{theorem}\label{normal} \sdex{Normal form for $\Sigma^1_1$}
(Normal form) A set $A\subseteq\bairespace$
is $\Sigma^1_1$ iff there exists a recursive map
$$\bairespace\arrow 2^{\finseq}\;\; x\mapsto T_x$$
such that $T_x\subseteq\finseq$ is a tree for every $x\in\bairespace$,
and $x\in A$ iff $T_x$ is ill-founded. By recursive map we
mean that there is a Turing machine $\{e\}$ such that
for $x\in\bairespace$ the machine $e$ computing with an oracle
for $x$, $\{e\}^x$ computes the characteristic function of $T_x$.
\end{theorem}
\proof
Suppose
$$x\in A \rmiff \exists y \in\bairespace\;\forall n\in\omega\;\;
R(x\res n, y\res n).$$
Define
$$T_x=\{s\in \finseq: \forall i \leq |s|\;\; R(x\res i, s\res i)\}.$$
\qed
A similar thing is true for $A\subseteq\omega$, i.e.,
$A$ is $\Sigma^1_1$ iff there is a uniformly recursive list
of recursive trees $\langle T_n:n<\omega\rangle$ such that
$n\in A$ iff $T_n$ is ill-founded.
The connection between $\Sigma^1_1$ and well-founded trees, gives
us the following:
\begin{theorem} \label{mostow}
(Mostowski's Absoluteness) Suppose $M\subseteq N$ are two
transitive models of ZFC$^*$ and $\theta$ is $\bsig11$ sentence
with parameters in $M$. Then \sdex{Mostowski's Absoluteness}
$$M\models\theta \rmiff N\models\theta.$$
\end{theorem}
\proof
ZFC$^*$ is a nice enough finite fragment of ZFC to know that
trees are well-founded iff they have rank functions (Theorem \ref{tree}).
$\theta$ is $\bsig11$ sentence \sdex{ZFC$^*$}
with parameters in $M$ means there exists $R$ in $M$ such that
$$\theta=\exists x\in\bairespace \forall n \; R(x\res n).$$
This means that for some tree $T\subseteq\finseq$ in $M$
$\theta$ is equivalent to ``$T$ has an infinite branch''.
So if $M\models\theta$ then $N\models\theta$ since a branch
$T$ exists in $M$. On the other hand if
$M\models\neg\theta$, then
$$M\models\exists r:T\arrow\ordinals\mbox{ a rank function''}$$
and then for this same $r\in M$
$$N\models r:T\arrow\ordinals\mbox{ is a rank function''}$$
and so $N\models\neg\theta$. \qed
\sector{Constructible well-orderings}
G\"odel proved the axiom of choice relatively consistent with ZF
by producing a definable well-order of the constructible universe.
He announced in G\"odel \site{god} that if V=L,
then there exists an uncountable $\Pi^1_1$ set without perfect subsets.
Kuratowski wrote down a
proof of the theorem below but the manuscript was lost during
World War II (see Addison \site{addison2}).
A set is $\Sigma^1_2$ iff it is the projection of a $\Pi_1^1$ set.
\sdex{$\Sigma^1_2$}
\begin{theorem} \label{delluz}
[\dex{V=L}] There exists a $\Delta^1_2$
well-ordering of $\bairespace$. \sdex{$\Delta^1_2$ well-ordering}
\end{theorem}
\proof
Recall the definition of G\"odel's Constructible sets $L$.
$L_0=\emptyset$, $L_\lambda=\Union_{\alpha<\lambda}L_\alpha$ for
$\lambda$ a limit ordinal, and $L_{\alpha+1}$
is the definable subsets of $L_\alpha$. Definable means
with parameters from $L_\alpha$. $L=\Union_{\alpha\in\ordinals}L_\alpha$.
The set $x$ is constructed before $y$, \sdex{$x<_cy$}
($x<_cy$) iff the least $\alpha$ such that $x\in L_\alpha$ is less
than the least $\beta$ such that $y\in L_\beta$, or $\alpha=\beta$
and the ``least'' defining formula for $x$ is less than the one
for $y$. Here ``least'' basically boils down to lexicographical order.
Whatever the exact formulation of $x<_c y$ is it satisfies:
$$x<_cy\rmiff L_\alpha\models x<_cy$$
where $x,y\in L_\alpha$ and $L_\alpha\models$ZFC$^*$ where
ZFC$^*$ is a sufficiently large finite fragment of ZFC. (Actually,
it is probably enough for $\alpha$ to be a limit ordinal.)
Assuming $V=L$, for $x,y\in\bairespace$ we have that $x<_cy$ iff
there exists $E\subseteq\omega\cross\omega$ and $\name{x},\name{y}\in\omega$
such that letting $M=(\omega,E)$ then
\begin{enumerate}
\item $E$ is extensional and well-founded,
\item $M\models$ZFC$^*$+ V=L
\item $M\models \name{x}<_c\name{y}$,
\item for all $n,m\in\omega\;\;\;(x(n)=m$
iff $M\models \name{x}(\name{n})=\name{m}$), and
\item for all $n,m\in\omega$ ($y(n)=m$ iff
$M\models \name{y}(\name{n})=\name{m}$).
\end{enumerate}
The first clause guarantees (by the Mostowski collapsing lemma) that
$M$ is isomorphic to a transitive set. The second, that this transitive
set will be of the form $L_\alpha$. The last two clauses guarantee
that the image under the collapse of $\name{x}$ is $x$ and
$\name{y}$ is $y$.
Well-foundedness of $E$ is $\Pi^1_1$. The remaining clauses are
all $\Pi^0_n$ for some $n\in\omega$. Hence, we have given a
$\Sigma^1_2$ definition of $<_c$. But a total ordering $<$
which is $\Sigma^1_n$ is $\Delta^1_n$, since
$x\not< y$ iff $y=x$ or $y:\kappa\cross\omega\arrow\kappa$
be a pairing function. For $s\in \kappa^n$ let $s_0\in\kappa^n$
and $s_1\in\omega^n$ be defined by $s(i)=$.
Let $T^*$ be the tree defined by
$$T^*=\Union_{n\in\omega}\{(s,t)\in \kappa^n\cross\omega^n:
(s_0,s_1,t)\in T\}.$$
Then $p[T^*]=\{y:\exists x\in\bairespace \;(x,y)\in A\}$.
\begin{theorem} \label{shoentree}
(Shoenfield \site{shoen}) If $A$ is a $\Sigma^1_2$ set, then $A$ is
$\omega_1$-Souslin set coded in L, i.e. $A=p[T]$
where $T\in L$.
\end{theorem}
\proof
From the construction of $T^*$ it is clear that is enough to
see this for $A$ which is $\Pi^1_1$.
We know that a countable tree is well-founded
iff there exists a rank function $r:T\arrow\omega_1$.
Suppose
$$x\in A\rmiff \forall y \exists n \;\;(x\res n,y\res n)\notin T$$
where $T$ is a recursive tree. So defining
$T_x=\{t: (x\res |t|,t)\in T\}$ we have that
$x\in A$ iff $T_x$ is well-founded (Theorem \ref{normal}).
The $\omega_1$ tree $\hat{T}$ is just the tree of partial rank functions.
Let $\{s_n:n\in\omega\}$ be a recursive listing of $\finseq$ with
$|s_n|\leq n$. Then for every $N<\omega$,
and $(r,s)\in \omega_1^N\cross\omega^N$ we have $(r,t)\in\hat{T}$ iff
$$ \forall n,mr(m) .$$
Then $A=p[\hat{T}]$. To see this, note that if
$x\in A$, then $T_x$ is well-founded and so it has a rank function
and therefore there exists $r$ with $(x,r)\in [\hat{T}]$ and
so $x\in p[\hat{T}]$. On the other hand if $(x,r)\in[\hat{T}]$,
then $r$ determines a rank function on $T_x$ and so $T_x$ is well-founded
and hence $x\in A$.
\qed
\begin{theorem} \label{shoenabs} \sdex{Shoenfield Absoluteness}
(Shoenfield Absoluteness \site{shoen}) If $M\subseteq N$ are transitive models
of ZFC$^*$ and ${\omega_1}^N\subseteq M$, then for any $\Sigma^1_2(x)$
sentence $\theta$ with parameter $x\in M$
$$M\models\theta \rmiff N\models\theta.$$
\end{theorem}
\proof
If $M\models\theta$, then $N\models\theta$, because $\bpi11$ sentences
are absolute. On the other hand suppose $N\models\theta$. Working
in $N$ using the proof of Theorem \ref{shoentree} we get
a tree $T\subseteq\omega_1^{<\omega}$ with
$T\in L[x]$ such that $T$ is ill-founded, i.e., there exists
$r\in [T]$. Note that $r$ codes a witness to a $\Pi^1_1(x)$
predicate and a rank function showing the tree corresponding to
this predicate is well-founded. Since for some
$\alpha<\omega_1$, $r\in\alpha^\omega$ we see that
$$T_\alpha=T\intersect \alpha^{<\omega}$$
is ill-founded. But $T_\alpha\in M$ (since by assumption
$(\omega_1)^N\subseteq M$) and so by the absoluteness of well-founded
trees, $M$ thinks that $T_\alpha$ is ill-founded. But a branch
thru $[T]$ gives a witness and a rank function showing that $\theta$ is
true, and consequently, $M\models\theta$.\qed
\sector{Mansfield-Solovay Theorem}
\begin{theorem} \label{mansol}
(Mansfield \site{mansf}, Solovay \site{solov})
If $A\subseteq\bairespace$ is a $\bsig12$ set with constructible
parameter which contains a nonconstructible element of $\bairespace$,
then $A$ contains a perfect set which is coded in $L$.
\end{theorem} \sdex{Mansfield-Solovay Theorem}
\proof
By Shoenfield's Theorem \ref{shoentree}, we may assume
$A=p[T]$ where $T\in L$ and
$T\subseteq \Union_{n<\omega}\omega_1^n\cross\omega^n$.
Working in $L$ define the following decreasing sequence of
subtrees as follows.
$T_0=T$,
$T_\lambda=\Intersect_{\beta<\lambda}T_\beta$, if $\lambda$ a limit ordinal, and
$T_{\alpha+1}=\{(r,s)\in T_\alpha: \exists (r_0,s_0), (r_1,s_1)\in T_\alpha$
such that
$(r_0,s_0), (r_1,s_1)$ extend $(r,s)$, and $s_0$ and $s_1$ are incompatible$\}$.
Each $T_\alpha$ is tree, and for $\alpha<\beta$ we have
$T_\beta\subseteq T_\alpha$. Thus there exists some $\alpha_0$ such
that $T_{\alpha_0+1}=T_{\alpha_0}$.
\claim $[T_{\alpha_0}]$ is nonempty.
\proof
Let $(x,y)\in [T]$ be any pair with $y$ not constructible. Since
$A=p[T]$ and $A$ is not a subset of $L$, such a pair must exist.
Prove by induction on $\alpha$ that $(x,y)\in [T_\alpha]$.
This is easy for $\alpha$ a limit ordinal. So suppose
$(x,y)\in [T_\alpha]$ but $(x,y)\notin [T_{\alpha+1}]$. By the
definition it must be that there exists $n<\omega$ such
that $(x\res n,y\res n)=(r,s) \notin T_{\alpha+1}$. But
in $L$ we can define the tree:
$$T_{\alpha}^{(r,s)}=\{(\hat{r},\hat{s})\in T_{\alpha}:
(\hat{r},\hat{s})\subseteq
(r,s) \rmor (r,s) \subseteq (\hat{r},\hat{s})\}$$
which has the property that $p[T_{\alpha}^{(r,s)}]=\{y\}$. But by
absoluteness of well-founded trees, it must be that
there exists $(u,y_0)\in [T_{\alpha}^{(r,s)}]$ with $(u,y_0)\in L$.
But then $y_0=y\in L$ which is a contradiction.
This proves the claim. \qed
Since $T_{\alpha_0+1}=T_{\alpha_0}$, it follows that
for every $(r,s)\in T_{\alpha_0}$ there exist
$$(r_0,s_0), (r_1,s_1)\in T_{\alpha_0}$$ such that
$(r_0,s_0), (r_1,s_1)$ extend $(r,s)$ and $s_0$ and $s_1$ are incompatible.
This allows us to build by induction (working in $L$):
$$\langle (r_\sigma,s_\sigma):\sigma\in 2^{<\omega}\rangle$$
with $(r_\sigma,s_\sigma)\in T_{\alpha_0}$ and for each
$\sigma\in 2^{<\omega}$
$(r_{\sigma_0},s_{\sigma_0}), (r_{\sigma_1},s_{\sigma_1})$ extend
$(r_{\sigma},s_{\sigma})$ and $s_{\sigma_0}$ and $s_{\sigma_1}$ are
incompatible. For any $q\in\cantorspace$ define
$$x_q=\Union_{n<\omega}r_{q\res n}
\rmand y_q=\Union_{n<\omega}s_{q\res n}.$$
Then we have that $(x_q,y_q)\in [T_{\alpha_0}]$ and
therefore $P=\{y_q:q\in \cantorspace\}$ is a perfect set such that
$$P\subseteq p[T_{\alpha_0}]\subseteq p[T]=A$$ and $P$ is coded
in $L$.\qed
This proof is due to Mansfield. Solovay's
proof used forcing. Thus we have
departed\footnote{``Consistency is the hobgoblin of little minds.
With consistency
a great soul has simply nothing to do.'' Ralph Waldo Emerson.}
from our theme of giving forcing proofs.
\sector{Uniformity and Scales}
Given $R\subseteq X\cross Y$ we say that $S\subseteq X\cross Y$ uniformizes
$R$ iff
\begin{enumerate}
\item $S\subseteq R$,
\item for all $x\in X$ if there exists $y\in Y$ such that
$R(x,y)$, then there exists $y\in Y$ such that $S(x,y)$, and
\item for all $x\in X$ and $y,z\in Y$ if $S(x,y)$ and $S(x,z)$, then
$y=z$.
\end{enumerate}
Another way to say the same thing is that $S$ is a subset of $R$ which
is the graph of a function whose domain is the same as $R$'s.
The $\Pi^1_1$ sets have the \dex{uniformization property}.
\begin{theorem} \label{uniform}
(Kondo \site{kondo})
Every $\Pi^1_1$ set $R$ can be uniformized
by a $\Pi^1_1$ set $S$.
\end{theorem}
Here, $X$ and $Y$ can be taken to be either $\omega$ or $\bairespace$ or
even a singleton $\{0\}$. In this last case, this amounts to
saying for any nonempty $\Pi_1^1$ set $A\subseteq\bairespace$ there
exists a $\Pi^1_1$ set $B\subseteq A$ such that $B$ is a singleton,
i.e., $|B|=1$. The proof of this Theorem is to use a property which
has become known as the \dex{scale property}.
\begin{lemma}\label{scale}
(scale property) For any $\Pi^1_1$ set $A$ there exists
$\langle \phi_i:i<\omega\rangle$ such that
\begin{enumerate}
\item each $\phi_i:A\arrow\ordinals$,
\item for all $i$ and $x,y\in A$ if $\phi_{i+1}(x)\leq\phi_{i+1}(y)$, then
$\phi_{i}(x)\leq\phi_{i}(y)$,
\item for every $x,y\in A$ if $\forall i \;\;\phi_i(x)=\phi_i(y)$, then $x=y$,
\item for all $\langle x_n:n<\omega\rangle\in A^{\omega}$ and
$\langle \alpha_i:i<\omega\rangle\in \ordinals^{\omega}$ if
for every $i$ and for all but finitely many
$n\;\;\phi_i(x_n)=\alpha_i$, then there exists $x\in A$ such
that $\lim_{n\arrow\infty}x_n=x$ and for each $i$
$\phi_i(x)\leq\alpha_i$,
\item there exists $P$ a $\Pi^1_1$ set such that
for all $x,y\in A$ and $i$
$$P(i,x,y)\rmiff \phi_i(x)\leq \phi_i(y)$$
and
for all $x\in A$, $y\notin A$, $i\in\omega$ $P(i,x,y)$, and
\item there exists $S$ a $\Sigma^1_1$ set such that
for all $x,y\in A$ and $i$
$$S(i,x,y)\rmiff \phi_i(x)\leq \phi_i(y)$$
and
for all $y\in A$, $x$, $i\in\omega$
if $S(i,x,y)$, then $x\in A$.
\end{enumerate}
\end{lemma}
Another way to view a scale is from the point of view of
the relations on $A$ defined by $x\leq_i y$ iff $\phi_i(x)\leq\phi_i(y)$.
These are called \dex{prewellorderings}.
They are well orderings
if we mod out by $x\equiv_iy$ which is defined by
$$x\equiv_iy\rmiff x\leq_iy \rmand y\leq_ix . $$
The second item says that
these relations get finer and finer as $i$ increases.
The third item says that in the ``limit'' we get a linear order.
The fourth item is some sort of continuity condition.
And the last two items are the definability properties of the
scale.
Before proving the lemma, let us deduce uniformity from it.
We do not use the last item in the lemma. First let us show that
for any nonempty $\Pi_1^1$ set $A\subseteq\bairespace$ there
exists a $\Pi^1_1$ singleton $B\subseteq A$. \sdex{$\Pi^1_1$ singleton}
Define
$$x\in B\rmiff x\in A\rmand\forall n \forall y\; P(n,x,y).$$
Since $P$ is $\Pi^1_1$ the set $B$ is $\Pi_1^1$. Clearly
$B\subseteq A$, and also by item (2) of the lemma, $B$ can have at
most one element. So it remains to show that $B$ is nonempty.
Define $\alpha_i=\min\{\phi_i(x):x\in A\}$. For each
$i$ choose $x_i\in A$ such that $\phi_i(x_i)=\alpha_i$.
\claim If $n>i$ then $\phi_i(x_n)=\alpha_i$.
\proof
By choice of $x_n$ for every $y\in A$ we have $\phi_n(x_n)\leq \phi_n(y)$.
By item (2) in the lemma, for every $y\in A$ we have that
$\phi_i(x_n)\leq \phi_i(y)$ and hence $\phi_i(x_n)=\alpha_i$.
\qed
By item (4) there exists $x\in A$ such that $\lim_{n\arrow\infty}x_n=x$ and
$\phi_i(x)\leq\alpha_i$ all $i$. By the minimality of $\alpha_i$ it
must be that $\phi_i(x)=\alpha_i$. So $x\in B$ and we are done.
Now to prove a more general case of uniformity suppose that
$R\subseteq\bairespace\cross\bairespace$ is $\Pi^1_1$. Let
$\phi_i:R\arrow \ordinals$ be scale given by
the lemma and
$$P\subseteq \omega\cross (\bairespace\cross\bairespace)\cross
(\bairespace\cross\bairespace)$$ be the $\Pi_1^1$ predicate given by
item (5). Then define the $\Pi^1_1$ set
$S\subseteq \bairespace\cross\bairespace$ by
$$(x,y)\in S\rmiff
(x,y)\in R\rmand\forall z \forall n\; P(n,(x,y),(x,z)).$$
The same proof shows that $S$ uniformizes $R$.
The proof of the Lemma will need the following two elementary facts
about well-founded trees. For $T,\hat{T}$ subtrees of $Q^{<\omega}$ we
say that $\sigma:T\arrow \hat{T}$ is a \dex{tree embedding} iff
for all $s,t\in T$ if $s\subset t$ then $\sigma(s)\subset \sigma(t)$.
Note that $s\subset t$ means that $s$ is a proper initial segment of $t$.
\sdex{$s\subset t$}
Also note that tree embeddings need not be one-to-one. We write
$T\embed\hat{T}$ iff there exists a tree embedding from $T$ into $\hat{T}$.
\sdex{$T?embed?hat{T}$}
We write $T\strictembed\hat{T}$ iff there is a tree embedding which
takes the root node of $T$ to a nonroot node of $\hat{T}$.
\sdex{$T?strictembed?hat{T}$}
Recall that $r:T\arrow\ordinals$ is a rank function iff
for all $s,t\in T$ if $s\subset t$ then $r(s)>r(t)$. Also
the rank of $T$ is the minimal ordinal $\alpha$ such that
there exists a rank function $r:T\arrow\alpha+1$.
\begin{lemma} \label{emb1}
Suppose $T\embed\hat{T}$ and $\hat{T}$ is well-founded,
i.e., $[\hat{T}]=\emptyset$, then $T$ is well-founded and rank of
$T$ is less than or equal to rank of $\hat{T}$.
\end{lemma}
\proof
Let $\sigma:T\arrow\hat{T}$ be a tree embedding and
$r:\hat{T}\arrow\ordinals$ a rank function. Then
$r\circ \sigma$ is a rank function on $T$.
\qed
\begin{lemma}\label{emb2}
Suppose $T$ and $\hat{T}$ are well founded trees and
rank of $T$ is less than or equal rank of $\hat{T}$, then
$T\embed \hat{T}$.
\end{lemma}
Let $r_T$ and $r_{\hat{T}}$ be the canonical rank functions on
$T$ and $\hat{T}$ (see Theorem \ref{tree}). Inductively
define $\sigma:T\intersect Q^{n}\arrow\hat{T}\intersect Q^{n}$,
so as to satisfy $r_T(s)\leq r_{\hat{T}}(\sigma(s))$.\qed
Now we a ready to prove the existence of scales (Lemma \ref{scale}).
Let $$\omega_1^{-}=\{-1\}\union\omega_1$$ be well-ordered in the obvious
way. Given a well-founded tree $T\subseteq\finseq$ with rank function
$r_T$ extend $r_T$ to all of $\finseq$ by defining $r_T(s)=-1$ if
$s\notin T$. Now suppose $A\subseteq\bairespace$ is $\Pi_1^1$ and
$x\in A$ iff $T_x$ is well-founded (see Theorem \ref{normal}).
Let $\{s_n:n<\omega\}$ be a recursive listing of $\finseq$ with
$s_0=\emptyseq$. For each $n<\omega$ define
$\psi_n:A\arrow \omega_1^-\cross\omega\cross\cdots\omega_1^-\cross\omega$
by
$$\psi_n(x)=\langle r_{T_x}(s_0), x(0), r_{T_x}(s_1), x(1),\ldots,
r_{T_x}(s_{n}), x(n)\rangle.$$
The set $\omega_1^-\cross\omega\cross\cdots\omega_1^-\cross\omega$ is
well-ordered by the lexicographical order. The scale
$\phi_i$ is just obtained by mapping the range of $\psi_i$ order
isomorphically
to the ordinals. (Remark: by choosing $s_0=\emptyseq$, we guarantee that
the first
coordinate is always the largest coordinate, and so
the range of $\psi_i$ is less than or equal to $\omega_1$.)
Now we verify the properties.
For item (2): if $\psi_{i+1}(x)\leq_{lex}\psi_{i+1}(y)$, then
$\psi_{i}(x)\leq_{lex}\psi_{i}(y)$. This is true because we
are just taking the lexicographical order of a longer sequence.
For item (3): if $\forall i \;\;\psi_i(x)=\psi_i(y)$, then $x=y$.
This is true, because
$$\psi_i(x)=\psi_i(y)\mbox{ implies }x\res i=y\res i.$$
For item (4):
Suppose $\langle x_n:n<\omega\rangle\in A^{\omega}$ and
for every $i$ and for all but finitely many
$n\;\;\psi_i(x_n)=t_i$. Then since $\psi_i(x_n)$
contains $x_n\res i$ there must be
$x\in\bairespace$ such that $\lim_{n\arrow\infty}x_n=x$. Note
that since $\{s_n:n\in\omega\}$ lists every element of $\finseq$,
we have that for every $s\in \finseq$ there exists $r(s)\in\ordinals$
such that $r_{T_{x_n}}(s)=r(s)$ for all but finitely many $n$. Using
this and $$\lim_{n\arrow\infty}T_{x_n}=T_x$$ it follows that
$r$ is a rank function on $T_x$. Consequently $x\in A$. Now
since $r_{T_x}(s)\leq r(s)$, it follows that
$\psi_i(x)\leq_{lex}t_i$.
For item (5),(6): The following set is $\Sigma^1_1$:
$$\{(T,\hat{T}): T,\hat{T} \mbox{ are subtrees of }\finseq,
T\embed \hat{T}\}.$$
Consequently, assuming that $T,\hat{T}$ are well-founded, to
say that $r_T(s)\leq r_{\hat{T}}(s)$ is equivalent to
saying there exists a tree embedding which takes $s$ to $s$.
Note that this is
$\Sigma^1_1$. This shows that it is possible to define a $\Sigma^1_1$
set $S\subseteq \omega\cross\bairespace \cross\bairespace$
such that for every
$x,y\in A$ we have $(n,x,y)\in S$ iff
$$\langle r_{T_x}(s_0), x(0), r_{T_x}(s_1), x(1),\ldots,
r_{T_x}(s_{n}), x(n)\rangle$$
is lexicographically less than or equal to
$$\langle r_{T_y}(s_0), y(0), r_{T_y}(s_1), y(1),\ldots,
r_{T_y}(s_{n}), y(n)\rangle.$$
Note that if $(n,x,y)\in S$ and $y\in A$ then $x\in A$, since
$T_y$ is a well-founded tree and $S$ implies $T_x\embed T_y$, so
$T_x$ is well-founded and so $x\in A$.
To get the $\Pi_1^1$ relation $P$ (item (5)), instead of
saying $T$ can be embedded into $\hat{T}$ we say that
$\hat{T}$ cannot be embedded properly into $T$,i.e.,
$\hat{T}\not\strictembed T$ or in other words,
there
does not exists a tree embedding $\sigma:\hat{T}\arrow T$ such
that $\sigma(\emptyseq)\not=\emptyseq$. This is a $\Pi^1_1$ statement.
For $T$ and $\hat{T}$ well-founded trees saying that
rank of $T$ is less than or equal to $\hat{T}$ is equivalent to saying
rank of $\hat{T}$ is not strictly smaller than the rank of $T$.
But by Lemma \ref{emb2} this is equivalent to the nonexistence
of such an embedding. Note also that if $x\in A$ and
$y\notin A$, then we will have $P(n,x,y)$ for every $n$.
This is because $T_y$ is not well-founded and so
cannot be embedded into the well-founded tree $T_x$.
This finishes the proof of the Scale Lemma \ref{scale}.
\qed
The scale property was invented by Moschovakis \site{playful}
to show how determinacy
could be used to get
uniformity properties\footnote{I have yet to see any problem,
however complicated, which, when you looked
at it in the right way, did not become
still more complicated. Poul Anderson}
in the higher projective classes.
He was building on earlier ideas of Blackwell, Addison, and
Martin. The 500 page book by Kuratowski and Mostowski \site{kurmos}
ends with a proof of the uniformization theorem.
\sector{Martin's axiom and Constructibility}
\begin{theorem}
(G\"{o}del see Solovay \site{solov}) If V=L, there exists
uncountable $\Pi_1^1$ set $A\subseteq\bairespace$ which
contains no perfect subsets.
\end{theorem}
\proof
Let $X$ be any uncountable $\Sigma^1_2$ set containing no
perfect subsets. For example, a $\Delta^1_2$ Luzin set
would do (Theorem \ref{delluz}). Let $R\subset\bairespace\cross\bairespace$
be $\Pi_1^1$ such that $x\in X$ iff $\exists y\; R(x,y)$.
Use $\Pi^1_1$ uniformization (Theorem \ref{uniform}) to get
$S\subseteq R$ with the property that
$X$ is the one-to-one image of $S$ via the projection map
$\pi(x,y)=x$. Then $S$ is an uncountable $\Pi^1_1$ set which
contains no perfect subset. This is because if $P\subseteq S$ is
perfect, then $\pi(P)$ is a perfect subset of $X$.\qed
Note that it is sufficient to assume that $\omega_1=(\omega_1)^L$.
Suppose $A\in L$ is defined by the $\Pi^1_1$ formula $\theta$.
Then let $B$ be the set which is defined by $\theta$ in $V$.
So by $\Pi^1_1$ absoluteness $A=B\intersect L$. The set
$B$ cannot contain a perfect set since the sentence:
$$\exists T\mbox{ $T$ is a perfect tree and } \forall x\;
(x\in [T]\mbox{ implies } \theta(x))$$
is a $\Sigma^1_2$ and false in $L$ and so by Shoenfield absoluteness
(Theorem \ref{shoenabs}) must be false in $V$. It follows then
by the Mansfield-Solovay Theorem \ref{mansol} that $B$ cannot contain
a nonconstructible real and so $A=B$.
Actually, by tracing thru the actual definition of $X$ one can
see that the elements of the uniformizing set $S$ (which is what $A$ is)
consist
of pairs $(x,y)$ where $y$ is isomorphic to some $L_\alpha$ and
$x\in L_\alpha$. These pairs are reals which witness
their own constructibility,
so one can avoid using the Solovay-Mansfield Theorem.
\begin{corollary}
If $\omega_1=\omega_1^L$, then there exists a $\Pi^1_1$ set
of constructible reals which contains no perfect set.
\end{corollary}
\begin{theorem}
(Martin-Solovay \site{marsol}) Suppose
MA + $\neg$CH + $\omega_1=(\omega_1)^L$.
Then every $A\subseteq\cantorspace$ of cardinality $\omega_1$ is
$\bpi11$.
\end{theorem}
\proof
Let $A\subseteq\cantorspace$ be a uncountable $\Pi^1_1$ set of constructible
reals and let $B$ be an arbitrary subset of $\cantorset$ of cardinality
$\omega_1$. Arbitrarily well-order the two sets,
$A=\{a_\alpha:\alpha<\omega_1\}$ and $B=\{b_\alpha:\alpha<\omega_1\}$.
By Theorem \ref{silverlem} there exists two sequences
of $G_\delta$ sets $\langle U_n:n<\omega\rangle$ and
$\langle V_n:n<\omega\rangle$ such that
for every $\alpha<\omega_1$ for every $n<\omega$
$$a_\alpha(n)=1\rmiff b_\alpha\in U_n$$
and
$$b_\alpha(n)=1\rmiff a_\alpha\in V_n.$$
This is because the set $\{a_\alpha: b_\alpha(n)=1\}$, although
it is an arbitrary subset of $A$, is relatively $G_\delta$ by
Theorem \ref{silverlem}.
But note that $b\in B$ iff $\forall a\in \cantorset$
$$ [\forall n \; (a(n)=1 \rmiff b\in U_n)]
\mbox{ implies }
[a\in A \rmand
\forall n \;(b(n)=1 \rmiff a\in U_n)].$$
Since $A$ is $\Pi^1_1$ this definition of $B$ has the form:
$$\forall a ([\bpi03]\mbox{ implies } [\Pi^1_1 \rmand \bpi03])$$
So $B$ is $\bpi11$. \qed
Note that if every set of reals of size $\omega_1$ is $\bpi11$ then
every $\omega_1$ union of Borel sets is $\bsig12$. To see this
let $\langle B_\alpha:\alpha<\omega_1\rangle$ be any sequence of Borel sets.
Let $U$ be a universal $\bpi11$ set and let
$\langle x_\alpha:\alpha<\omega_1\rangle$ be a sequence such that
$$B_\alpha=\{y\;:\;(x_\alpha,y)\in U\;\}.$$
Then
$$y\in \Union_{\alpha<\omega_1}B_\alpha \rmiff
\exists x\;\; x \in\{x_\alpha:\alpha<\omega_1\}\conj (x,y)\in U.$$
But $\{x_\alpha:\alpha<\omega_1\}$ is $\bpi11$ and so the union
is $\bsig12$.
\sector{$\Sigma^1_2$ well-orderings}
\begin{theorem}
(Mansfield \site{manfield}) If $(F,\lhd)$ is a $\Sigma^1_2$
well-ordering, i.e.,
$$F\subseteq\bairespace \rmand \lhd\subseteq F^2$$
are both $\Sigma^1_2$, then $F$ is a
subset of $L$.
\end{theorem}
\proof
We will use the following:
\begin{lemma}
Assume there exists $z\in \cantorset$ such that $z\notin L$.
Suppose $f:P\arrow F$ is a 1-1 continuous function from
the perfect set $P$ and both $f$ and $P$ are coded in $L$,
then there exists $Q\subseteq P$ perfect and
$g:Q\arrow F$ 1-1 continuous so that both $g$ and $Q$ are
coded in $L$ and for every $x\in Q$ we have
$g(x)\lhd f(x)$.
\end{lemma}
\proof
(Kechris \site{kechris3}) First note that
there exists $\sigma:P\arrow P$ an autohomeomorphism
coded in $L$ such that for every $x\in P$ we have $\sigma(x)\not=x$ but
$\sigma^2(x)=x$. To get this let $c:\cantorset\arrow \cantorset$ be
the complement function, i.e., $c(x)(n)=1-x(n)$ which just switches
0 and 1. Then $c(x)\not=x$ but $c^2(x)=x$. Now if
$h:P\arrow\cantorset$ is a homeomorphism coded in $L$, then
$\sigma=h^{-1}\circ c \circ h$ works.
Now let $A=\{x\in P: f(\sigma(x))\lhd f(x)\}$. The set $A$ is
a $\bsig12$ set with code in $L$. Now since $P$ is coded in $L$ there
must be a $z\in P$ such that $z\notin L$. Note that $\sigma(z)\notin L$
also. But either
$$f(\sigma(z))\lhd f(z) \rmor f(z)=f(\sigma^2(z))\lhd f(\sigma(z))$$
and so either $z\in A$ or $\sigma(z)\in A$.
In either case $A$ has a nonconstructible member and so by the
Mansfield-Solovay Theorem \ref{mansol} the set $A$ contains a perfect
set $Q$ coded in $L$.
Let $g=f\circ \sigma$.\qed
Assume there exists $z\in F$ such that $z\notin L$. By the
Mansfield-Solovay Theorem there exists
a perfect set $P$ coded in $L$ such that $P\subseteq F$.
Let $P_0=P$ and $f_0$ be the identity function. Repeatedly apply
the Lemma to obtain $f_n:P_n\arrow F$ so that for every
$n$ and $P_{n+1}\subseteq P_n$, for every $x\in P_{n+1}$
$f_{n+1}(x)\lhd f_n(x)$. But then
if $x\in\Intersect_{n<\omega}$ the sequence $\langle f_n(x):n<\omega\rangle$
is a descending $\lhd$ sequence with contradicts the fact that
$\lhd$ is a well-ordering.
\qed
Friedman \site{fried} proved the weaker result that if there
is a $\bsig12$ well-ordering of the real line, then
$\bairespace\subseteq L[g]$ for some $g\in \bairespace$.
\sector{Large $\Pi^1_2$ sets}
A set is $\bpi12$ iff it is the complement of a $\bsig12$ set.
\sdex{$?bpi12$} Unlike $\bsig12$ sets which cannot have
size strictly in between $\omega_1$ and the continuum
(Theorem \ref{mansol}), $\bpi12$ sets can be
practically anything.\footnote{It's life Jim, but not as we know it.-
Spock of Vulcan}
\begin{theorem}\label{harring}
(Harrington \site{harring}) Suppose $V$ is a model of
set theory which satisfies $\omega_1=\omega_1^L$ and
$B$ is arbitrary subset of $\bairespace$ in $V$. Then
there exists a ccc extension of $V$, $V[G]$, in which
$B$ is a $\bpi12$ set.
\end{theorem}
\proof
Let $\poset_B$ be the following poset. $p\in\poset_B$ iff
$p$ is a finite consistent set of sentences of the form:
\begin{enumerate}
\item ``$[s]\intersect \name{C}_n =\emptyset$'', or
\item ``$x\in \name{C}_n$, where $x\in B$.
\end{enumerate}
This partial order is isomorphic to Silver's view of
almost disjoint sets forcing (Theorem \ref{silverlem}).
So forcing with $\poset_B$ creates an $F_\sigma$ set
$\Union_{n\in\omega}C_n$ so that
$$\forall x\in \bairespace\intersect V
(x\in B\rmiff x\in \Union_{n<\omega}C_n).$$
Forcing with the direct sum of $\omega_1$ copies of
$\poset_B$, $\prod_{\alpha<\omega_1}\poset_B$, we have that
$$\forall x\in \bairespace\intersect V[\langle G_\alpha:\alpha<\omega_1\rangle]
(x\in B\rmiff
x\in\Intersect_{\alpha<\omega_1}\union_{n<\omega}C_n^\alpha).$$
One way to see this is as follows.
Note that in any case
$$B\subseteq\Intersect_{\alpha<\omega_1}\union_{n<\omega}C_n^\alpha.$$
So it is the other implication which needs to be proved.
By ccc, for any $x\in V[\langle G_\alpha:\alpha<\omega_1\rangle]$ there
exists $\beta<\omega_1$ with $x\in V[\langle G_\alpha:\alpha<\beta\rangle]$.
But considering $V[\langle G_\alpha:\alpha<\beta\rangle]$ as the new ground
model, then $G_\beta$ would be $\poset_B$- generic over
$V[\langle G_\alpha:\alpha<\beta\rangle]$ and hence if $x\notin B$ we
would have $x\notin\union_{n<\omega}C_n^\beta$.
Another argument will be given in the proof of the next lemma.
\begin{lemma}
Suppose $\langle c_\alpha:\alpha<\omega_1$ be a sequence in $V$
of elements of $\bairespace$ and
$\langle a_\alpha:\alpha<\omega_1\rangle$ is a sequence in
$V[\langle G_\alpha:\alpha<\omega_1\rangle]$ of elements of
$\cantorspace$.
Using Silver's forcing
add a sequence of $\bpi02$ sets $\langle U_n:n<\omega\rangle$
such that
$$\forall n\in\omega\forall\alpha<\omega_1
(a_\alpha(n)=1 \rmiff c_\alpha\in U_n).$$
Then
$$V[\langle G_\alpha:\alpha<\omega_1\rangle][\langle U_n:n<\omega\rangle]
\models
\forall x\in\bairespace\; (x\in B\rmiff
x\in\Intersect_{\alpha<\omega_1}\union_{n<\omega}C_n^\alpha).$$
\end{lemma}
\proof
The lemma is not completely trivial, since adding the
$\langle U_n:n<\omega\rangle$ adds
new elements of $\bairespace$ which may somehow sneak into the $\omega_1$
intersection.
Working in $V$ define $p\in \posetq$ iff
$p$ is a finite set of consistent sentences of the form:
\begin{enumerate}
\item ``$[s]\subseteq U_{n,m}$'' where $s\in\finseq$, or
\item ``$c_\alpha\in U_{n,m}$''.
\end{enumerate}
Here we intend that $U_n=\intersect_{m\in\omega}U_{n,m}$.
Since the $c$'s are in $V$ it is clear that the partial order $\posetq$
is too.
Define
$$\poset=\{(p,q)\in (\prod_{\alpha<\omega_1}\poset_B) \cross \posetq
:\mbox{ if ``$c_\alpha\in U_{n,m}$''$\in q$, then $p\forces a_\alpha(n)=1\}$}.$$
Note that $\poset$ is a semi-lower-lattice, i.e., if
$(p_0, q_0)$ and $(p_1, q_1)$ are compatible elements of $\poset$,
then $(p_0\union p_1, q_0\union q_1)$ is their greatest lower bound.
This is another way to view the iteration, i.e,
$\poset$ is dense in the usual iteration.
Not every iteration has
this property, one which Harrington calls ``innocuous''.
Now to prove the lemma, suppose for contradiction that
$$(p,q)\forces \name{x}\in \Intersect_{\alpha<\omega_1}\union_{n<\omega}
C_n^\alpha
\rmand \name{x}\notin B.$$
To simplify the notation, assume $(p,q)=(\emptyset,\emptyset)$.
Since $\poset$ has the ccc a sequence of
Working in $V$ let $\rangle A_n:n\in \omega\langle$ be a sequence of
maximal antichains of $\poset$ which decide $\name{x}$, i.e.
for $({p},{q})\in A_n$ there exists
$s\in \omega^n$ such that
$$({p},{q})\forces \name{x}\res n=\check{s}.$$
Since $\poset$ has the ccc, the $A_n$ are countable and we can find an
$\alpha<\omega$ which does not occur in the support of any ${p}$ for any
$({p},{q})$ in $\Union_{n\in\omega}A_n$. Since $x$ is forced to be in
$\union_{n<\omega} C_n^\alpha$ there exists $(p,q)$ and $n\in\omega$
such that $$(p,q)\forces \name{x}\in C_n^\alpha.$$
Let ``$x_i\in C_n^\alpha$'' for $i2$ is similar.
\qed
We say that $(B,\delta)$ is a \dex{Borel metric space} iff $B$ is Borel,
$\delta$ is a metric on $B$,
and for every $\epsilon\in\rationals$ the set
$$\{(x,y)\in B^2:\delta(x,y)\leq\epsilon\}$$
is Borel.
\begin{theorem}\label{bormet}
(Harrington \site{harshemar}) If $(B,\delta)$ is a Borel metric space,
then either $(B,\delta)$ is separable (i.e., contains a countable
dense set) or for some $\epsilon>0$ there exists a perfect set
$P\subseteq B$ such that $\delta(x,y)>\epsilon$ for every
distinct $x,y\in P$.
\end{theorem}
\proof
By relativizing the proof to an arbitrary parameter we may assume that
$B$ and the sets $\{(x,y)\in B^2:\delta(x,y)\leq\epsilon\}$ are
$\Delta^1_1$.
\begin{lemma} \label{overmetric}
For any $\epsilon\in\rationals^+$ if $A\subseteq B$ is $\Sigma^1_1$ and
the diameter of $A$ is less than $\epsilon$, then there exists a
$\Delta^1_1$ set $D$ with diameter less than $\epsilon$ and
$A\subseteq D\subseteq B$.
\end{lemma}
\proof
This follows from Lemma \ref{overflow}, since
$$\theta(x,y)\;\; \rmiff\;\; \delta(x,y)<\epsilon \rmand x,y\in B$$
is a $\Pi^1_1$ formula.\qed
For any $\epsilon\in\rationals^+$ look at
$$Q_\epsilon=\Union\{D\in\Delta^1_1: D\subseteq B \rmand
\diam(D)<\epsilon\}.$$
Note that $Q$ is a $\Pi_1^1$ set. If for every $\epsilon\in\rationals^+$
$Q_\epsilon=B$, then since there are only countably many $\Delta^1_1$ sets,
$(B,\delta)$ is separable and we are done. On the other hand
suppose for some $\epsilon\in\rationals^+$ we have that
$$P_\epsilon=B\setminus Q_\epsilon\not=\emptyset.$$
\begin{lemma}
For every $c\in V\intersect B$
$$P_\epsilon\forces \delta(\name{a},\check{c})>\epsilon/3$$
where $\forces$ is Gandy forcing and $\name{a}$ is a name for
the generic real (see Lemma \ref{real}).
\end{lemma}
\proof
Suppose not. Then there exists $P\leq P_\epsilon$ such that
$$P\forces \delta(a,c)\leq\epsilon/3.$$
Since $P$ is disjoint from $Q_\epsilon$ by Lemma \ref{overmetric} we
know that the diameter of $P$ is $\geq\epsilon$. Let
$$R=\{(a_0,a_1): a_0,a_1\in P\rmand \delta(a_0,a_1)>(2/3)\epsilon\}.$$
Then $R$ is in $\poset$ and by Lemma \ref{pair}, if $a$ is $\poset$-generic
over $V$ with $a\in R$, then $a_0$ and $a_1$ are each separately
$\poset$-generic over $V$. But $a_0\in R$ and $a_1\in R$ means
that $\delta(a_0,c)\leq \epsilon/3$ and $\delta(a_1,c)\leq \epsilon/3$.
But by absoluteness $\delta(a_0,a_1)>(2/3)\epsilon$. This contradicts
the fact that $\delta$ must remain a metric by absoluteness.
\qed
Using this lemma and Lemma \ref{perfect} is now easy to get a perfect
set $P\subseteq B$ such that $\delta(x,y)>\epsilon/3$ for each
distinct $x,y\in P$. This proves Theorem \ref{bormet}.\qed
\begin{theorem}(van Engelen, Kunen, Miller \site{ekm}) \label{collinear}
For any $\bsig11$ set $A$ in the plane, either $A$ can
be covered by countably many lines or there exists a perfect set
$P\subseteq A$ such that no three points of P are collinear.
\end{theorem}\sdex{collinear points}
\proof
This existence of this proof was pointed out to me by
Dougherty, Jackson, and Kechris. The proof in \site{ekm} is
more elementary.
By relativizing the proof
we may as well assume that $A$ is $\Sigma^1_1$.
\begin{lemma} \label{line}
Suppose $B$ is a $\Sigma^1_1$ set lying on a line in the plane.
Then there exists a $\Delta^1_1$ set
$D$ with $B\subseteq D$ such that all points of $D$ are collinear.
\end{lemma}
\proof
This follows from Lemma \ref{overflow} since
$$\theta(x,y,z)\;\; \rmiff \;\; x,y,\rmand z \mbox{ are collinear}$$
is $\Pi^1_1$ (even $\Pi^0_1$).\qed
Define
$$\comp{P}=\Union\{D\subseteq \reals^2: D\in\Delta^1_1 \rmand
\mbox{ all points of $D$ are collinear}\}.$$
It is clear that $\comp{P}$ is $\Pi^1_1$ and therefore $P$ is
$\Sigma^1_1$. If $P\intersect A=\emptyset$, then $A$ can be
covered by countably many lines.
So assume that
$$Q=P\intersect A\not=\emptyset.$$
For any two distinct points
in the plane, $p$ and $q$, let $\lin(p,q)$ be the unique
line on which they lie.
\begin{lemma} \label{line2}
For any two distinct points
in the plane, $p$ and $q$, with $p,q\in V$
$$Q\forces \name{a}\notin \lin(\check{p},\check{q}).$$
\end{lemma}
\proof
Suppose for contradiction that there exists $R\leq Q$
such that
$$R\forces \name{a}\in \lin(\check{p},\check{q}).$$
Since $R$ is disjoint from
$$\Union\{D\subseteq \reals^2: D\in\Delta^1_1 \rmand
\mbox{ all points of $D$ are collinear}\}$$
it follows from Lemma \ref{line} that not all triples of
points from $R$ are collinear.
Define the nonempty $\Sigma^1_1$ set
$$S=\{a:a_0,a_1,a_2 \in R\rmand a_0,a_1,a_2 \mbox{ are not collinear}\}$$
where $a=(a_0,a_1,a_2)$ via some standard tripling function.
Then $S\in\poset$ and by the obvious generalization of Lemma \ref{pair}
each of the $a_i$ is $\poset$-generic if $a$ is. But this is a
contradiction since all $a_i\in \lin(p,q)$ which makes them collinear.
\qed
The following Lemma is an easy generalization of Lemma \ref{perfect}
so we leave the proof to the reader.
\begin{lemma}\label{line3}
Suppose $M$ is a countable transitive model of ZFC$^*$ and
$\poset$ is a partially ordered set in $M$. Then there
exists $\{G_x: x\in\cantorset\}$, a ``perfect'' set of $\poset$-filters,
such that for every $x,y,z$ distinct, we have that $(G_x,G_y,G_z)$ is
$\poset\cross\poset\cross\poset$-generic over $M$.
\end{lemma}
Using Lemma \ref{line2} and \ref{line3} it is easy to get (just as in
the proof of Theorem \ref{piequiv}) a perfect set of triply generic
points in the plane, hence no three of which are collinear. This proves
Theorem \ref{collinear}. \qed
Obvious generalizations of Theorem \ref{collinear} are:
\begin{enumerate}
\item Any $\bsig11$ subset of $\reals^n$ which cannot be covered
by countably many lines contains a perfect set all of whose points
are collinear.
\item Any $\bsig11$ subset of $\reals^2$ which cannot be covered
by countably many circles contains a perfect set which does not
contain four points on the same circle.
\item Any $\bsig11$ subset of $\reals^2$ which cannot be covered
by countably many parabolas contains a perfect set which does not
contain four points on the same parabola.
\item For any $n$ any $\bsig11$ subset of $\reals^2$ which
cannot be covered by countably many polynomials of degree $\beta$. Clearly,
$$E=\Intersect_{\alpha<\omega_1}E_\alpha$$
and for any limit ordinal $\lambda$
$$E_\lambda=\Intersect_{\alpha<\lambda}E_\alpha.$$
While there is no reason to expect that any of the
$E_\alpha$ are equivalence relations, we use the boundedness
theorem to show that many are.
\begin{lemma}
For unboundedly many $\alpha<\omega_1$ the binary relation
$E_\alpha$ is an equivalence relation.
\end{lemma}
\proof
Note that every $E_\alpha$ must be reflexive, since $E$ is reflexive and
$E=\Intersect_{\alpha<\omega_1}E_\alpha$.
The following claim
will allow us to handle symmetry.
\claim For every $\alpha<\omega_1$ there exists $\beta<\omega_1$ such
that for every $x,y$
\begin{center}
if $xE_\alpha y$ and $y\notE_\alpha x$, then
$x\notE_\beta y$.
\end{center}
\proof
Let
$$A=\{T_{xy}: xE_\alpha y \rmand y\notE_\alpha x\}.$$
Then $A$ is a Borel set. Since $y\notE_\alpha x$ implies
$y\notE x$ and hence $x\notE y$, it follows that
$A\subseteq WF$. By the Boundedness Theorem \ref{bounded}
there exists $\beta<\omega_1$ such that $A\subseteq WF_{<\beta}$.
\qed
The next claim is to take care of transitivity.
\claim For every $\alpha<\omega_1$ there exists $\beta<\omega_1$ such
that for every $x,y,z$
\begin{center}
if $xE_\alpha y$ and $yE_\alpha z$,
and $x\notE_\alpha z$, then either $x\notE_\beta y$ or
$y\notE_\beta z$.
\end{center}
\proof
Let
$$B=\{T_{xy}\oplus T_{yz}: xE_\alpha y,\;\; yE_\alpha z,
\rmand x\notE_\alpha z\}.$$
The operation $\oplus$ on a pair of trees
$T_0$ and $T_1$ is defined by
$$T_0\oplus T_1=\{(s,t): s\in T_0, \;\; t\in T_1, \rmand |s|=|t|\}.$$
Note that the rank of $T_0\oplus T_1$ is the minimum of the
rank of $T_0$ and the rank of $T_1$. (Define the rank function on
$T_0\oplus T_1$ by taking the minimum of the rank functions on the
two trees.)
The set $B$ is Borel because the relation $E_\alpha$ is.
Note also that since $x\notE_\alpha z$ implies $x\notE z$ and
$E$ is an equivalence relation, then either
$x\notE y$ or $y\notE z$. It follows that either
$T_{xy}\in WF$ or $T_{yz}\in WF$ and so in either case
$T_{xy}\oplus T_{yz}\in WF$ and so $B\subseteq WF$. Again, by
the Boundedness Theorem there is a $\beta<\omega_1$ such
that $B\subseteq WF_{<\beta}$ and this proves the Claim.
\qed
Now we use the Claims
to prove the Lemma. Using the usual Lowenheim-Skolem argument
we can find arbitrarily large countable ordinals $\lambda$ such
that for every $\alpha<\lambda$ there is a $\beta<\lambda$ which
satisfies both Claims for $\alpha$. But this means that
$E_\lambda$ is an equivalence relation. For suppose
$xE_\lambda y$ and $y\notE_\lambda x$. Then since
$E_\lambda=\Intersect_{\alpha<\lambda}E_\alpha$ there must be
$\alpha<\lambda$ such that $xE_\alpha y$ and $y\notE_\alpha x$.
But by the Claim there exist $\beta<\lambda$ such that
$x\notE_\beta y$ and hence $x\notE_\lambda y$, a contradiction.
A similar argument using the second Claim works for transitivity.
\qed
Let $G$ be any generic filter over $V$ with the property that
it collapses $\omega_1$ but not $\omega_2$. For example, Levy forcing
with finite partial functions from $\omega$ to $\omega_1$
(see Kunen \site{kunenbk} or Jech \site{jech}).
Then $\omega_1^{V[G]}=\omega_2^V$. By absoluteness, $E$ is still
an equivalence relation and for any $\alpha$ if $E_\alpha$ was
an equivalence relation in $V$, then it still is one in $V[G]$.
Since
$$E_{\omega_1^V}=\Intersect_{\alpha<\omega_1^V}E_\alpha$$
and the intersection of equivalence relations is an equivalence
relation, it follows that the Borel relation $E_{\omega_1^V}$ is
an equivalence relation. So now suppose that
$E$ had more than $\omega_2$ equivalence classes in $V$. Let
$Q$ be a set of size $\omega_2$ in $V$ of pairwise E-inequivalent
reals. Then $Q$ has cardinality $\omega_1$ in $V[G]$ and
for every $x\not= y\in Q$ there exists $\alpha<\omega_1^V$ with
$x\notE_\alpha y$. Hence it must be that the elements of $Q$ are in different
$E_{\omega_1^V}$ equivalence classes. Consequently, by Silver's Theorem
\ref{piequiv} there exists a perfect set $P$ of
$E_{\omega_1^V}$-inequivalent reals. Since in $V[G]$ the equivalence
relation $E$ refines $E_{\omega_1^V}$, it must be that the elements
of $P$ are pairwise $E$-inequivalent also. The following is a
$\bsig12$ statement:
$$V[G]\models \exists P \mbox{ perfect }\forall x\forall y\;\;
(x,y\in P \rmand x\not=y) \arrow x\notE y .$$
Hence, by Shoenfield Absoluteness \ref{shoenabs},
$V$ must think that there is a perfect set of $E$-inequivalent
reals.
A way to avoid taking a generic extension of the universe is
to suppose Burgess's Theorem is false. Then let
$M$ be the transitive collapse of an elementary substructure of
some sufficiently large $V_\kappa$ (at least large enough
to know about absoluteness and Silver's Theorem).
Let $M[G]$ be obtained as in the above proof by Levy collapsing
$\omega_1^M$. Then we can conclude as above that $M$ thinks
$E$ has a perfect set of inequivalent elements, which contradicts
the assumption that $M$ thought Burgess's Theorem was false.
\qed
By Harrington's Theorem \ref{harring} it is consistent to
have $\bpi12$ sets of arbitrary cardinality, e.g it
is possible to have $\continuum=\omega_{23}$ and
there exists a $\bpi12$ set $B$ with $|B|=\omega_{17}$.
Hence, if we define
$$xEy \rmiff x=y \rmor x,y\notin B$$
then we get $\bsig12$ equivalence relation with exactly
\sdex{$?bsig12$ equivalence relation}
$\omega_{17}$ equivalence classes, but since the continuum is
$\omega_{23}$ there is no perfect set of $E$-inequivalent reals.
See Burgess \site{burgess2} \site{burgess3} and Hjorth \site{hjorth}
for more results on
analytic equivalence relations. For further results
concerning projective equivalence relations
see Harrington and Sami \site{harsami}, Sami \site{sami},
Stern \site{stern} \site{stern2}, Kechris \site{kechris2},
Harrington and Shelah
\site{harrshel}, Shelah \site{shelah}, and Harrington, Marker, and
Shelah \site{harshemar}.
\sector{Louveau's Theorem}
Let us define codes for Borel sets in our usual way of thinking of
them as trees with basic clopen sets attached to the terminal nodes.
\sdex{Louveau's Theorem}
Definitions
\begin{enumerate}
\item Define $(T,q)$ is an $\alpha$-code iff $T\subseteq \finseq$
\sdex{$\alpha$-code}
is a tree of rank $\leq\alpha$ and $q:\tzero\arrow\base$ is
a map from the terminal nodes, $\tzero$, of $T$ (i.e. rank zero nodes) to
a nice base, $\base$, for the clopen sets of $\bairespace$, say
all sets of the form $[s]$ for $s\in \finseq$ plus the empty set.
\item Define $S^s(T,q)$ and $P^s(T,q)$ for $s\in T$ by induction on the
rank of $s$ as follows. For $s\in\tzero$ define
$$P^s(T,q)=q(s) \rmand S^s(T,q)=\comp{q(s)}.$$
For $s\in\tone$ define
$$P^s(T,q)=\Union\{ S(T,q)^{s\concat m}: {s\concat m}\in T\} \rmand
S^s(T,q)=\comp{P^s(T,q)}.$$
\item Define
$$P(T,q)=P^{\emptyseq}(T,q)\rmand S(T,q)=S^{\emptyseq}(T,q)$$
the $\Pi^0_\alpha$ set and the $\Sigma^0_\alpha$ set
coded by $(T,q)$, respectively. ($S$ is short for
Sigma and $P$ is short for Pi.) \sdex{$P(T,q)$} \sdex{$S(T,q)$}
\item Define $C\subseteq\bairespace$ is $\Pi^0_\alpha(\hyp)$ iff
\sdex{$\Pi^0_\alpha(\hyp)$}
it has an $\alpha$-code which is hyperarithmetic.
\item $\omega_1^{CK}$ is the first nonrecursive ordinal.
\sdex{$\omega_1^{CK}$}
\end{enumerate}
\begin{theorem}\label{louv}
(Louveau \site{louveau}) If $A,B\subseteq\bairespace$ are $\Sigma^1_1$
sets, $\alpha<\omega_1^{CK}$, and $A$ and $B$ can be separated
by $\bpi0{\alpha}$ set, then $A$ and $B$ can be separated by
a $\Pi^0_\alpha(\hyp)$-set.
\end{theorem}
\begin{corollary}
$\Delta^1_1\intersect {\bpi0\alpha}= \Pi^0_\alpha(\hyp)$
\end{corollary}
\begin{corollary}\label{section}
(\dex{Section Problem}) If $B\subseteq\bairespace\cross\bairespace$ is
Borel and $\alpha<\omega_1$ is such that
$B_x\in\bsig0\alpha$ for every
$x\in\bairespace$, then
$$B\in \bsig0\alpha(\{D\cross C: D\in\borel({\bairespace})
\rmand C \mbox{is clopen}\}).$$
\end{corollary}
Note that the converse is trivial.
This result was proved by Dellecherie for $\alpha=1$ who conjectured
it in general. Saint-Raymond proved it for $\alpha=2$ and
Louveau and Saint-Raymond independently proved it for $\alpha=3$ and
then Louveau proved it in general. In their paper \site{loust}
Louveau and Saint-Raymond give a different proof of it.
We will need the following lemma.
\begin{lemma} \label{defdelta}
For $\alpha<\omega_1^{CK}$ the following sets are $\Delta_1^1$:
$\{y:\;\; y$ is a $\beta$-code for some $\beta<\alpha\}$,
$\{(x,y):\;\;y$ is a $\beta$-code for some $\beta<\alpha$ and $x\in P(T,q)\}$
,
and
$\{(x,y):\;\;y$ is a $\beta$-code for some $\beta<\alpha$ and $x\in S(T,q)\}.
$
\end{lemma}
\proof
For the first set it is enough to see that $WF_{<\alpha}$ the set of
trees of rank $<\alpha$ is $\Delta^1_1$.
Let $\hat{T}$ be a recursive tree of rank $\alpha$. Then
$T\in WF_{<\alpha}$ iff $T\strictembed \hat{T}$ shows that
$WF_{<\alpha}$ is $\Sigma^1_1$. But since $\hat{T}$ is well-founded
$T\strictembed \hat{T}$ iff $\neg(\hat{T}\embed T)$ and so it is
$\Pi^1_1$. For the second set just use an argument similar
to Theorem~\ref{hypcode}. The third set is just the complement
of the second one.\qed
Now we prove Corollary \ref{section} by induction on $\alpha$.
By relativizing
the proof to a parameter we may assume $\alpha<\omega_1^{CK}$ and
that $B$ is $\Delta^1_1$. By taking complements we may assume that
the result holds for $\Pi^0_\beta$ for all $\beta<\alpha$.
Define
$$R(x,(T,q)) \rmiff (T,q)\in \Delta^1_1(x),\;\;
(T,q) \mbox{ is an $\alpha$-code},
\rmand P(T,q)=B_x.$$
where $P(T,q)$ is the $\Pi^0_\alpha$ set coded by $(T,q)$. Note that by the
relativized version of Louveau's Theorem for every $x$ there exists
a $(T,q)$ such that $R(x,(T,q))$. By $\Pi^1_1$-uniformization
(Theorem~\ref{uniform})
there exist a $\Pi^1_1$ set $\hat{R}\subseteq R$ such that for every
$x$ there exists a unique $(T,q)$ such that $\hat{R}(x,(T,q))$.
Fix $\beta<\alpha$ and
$n<\omega$ and define
$B_{\beta,n}(x,z)$ iff there exists $(T,q)\in \Delta^1_1(x)$ such that
\begin{enumerate}
\item $\hat{R}(x,(T,q))$,
\item $\rank_T(\langle n\rangle)=\beta$ and
\item $z\in P^{\langle n\rangle}(T,q)$.
\end{enumerate}
Since quantification over $\Delta^1_1(x)$ preserves $\Pi^1_1$
(Theorem \ref{gandy2}),
$\hat{R}$ is $\Pi^1_1$, and the rest is $\Delta^1_1$ by Lemma \ref{defdelta},
we see that $B_{\beta,n}$ is $\Pi^1_1$.
But note that
$\neg B_{\beta,n}(x,z)$ iff there exists $(T,q)\in \Delta^1_1(x)$ such that
\begin{enumerate}
\item $\hat{R}(x,(T,q))$,
\item $\rank_T(\langle n\rangle)\not=\beta$, or
\item $z\in S^{\langle n\rangle}(T,q)$.
\end{enumerate}
and consequently, $\comp{B_{\beta,n}}$ is $\Pi^1_1$ and therefore
$B_{\beta,n}$ is $\Delta_1^1$. Note that every cross section
of $B_{\beta,n}$ is
a $\bpi0\beta$ set and so by induction (in case $\alpha>1$)
$$B_{\beta,n}\in \bpi0\alpha(\{D\cross C: D\in\borel(\bairespace)
\rmand C \mbox{is clopen}\}).$$
But then $$B=\Union_{n<\omega,\beta<\alpha}B_{\beta,n}$$ and so
$$B\in \bsig0\alpha(\{D\cross C: D\in\borel(\bairespace)
\rmand C \mbox{is clopen}\}).$$
Now to do the case for $\alpha=1$, define for every
$n\in\omega$ and $s\in\finseq$
$B_{s,n}(x,z)$ iff there exists $(T,q)\in \Delta^1_1(x)$ such that
\begin{enumerate}
\item $\hat{R}(x,(T,q))$,
\item $\rank_T(\langle n\rangle)=0$,
\item $q(\langle n\rangle)=s$, and
\item $z\in [s]$.
\end{enumerate}
As in the other case $B_{s,n}$ is $\Delta^1_1$.
Let $z_0\in [s]$ be arbitrary, then define the Borel set
$C_{s,n}=\{x:(x,z_0)\in B_{s,n}\}$.
Then $B_{s,n}=C_{s,n}\cross [s]$ where
But now
$$B=\Union_{n<\omega, s\in\finseq} B_{s,n}$$
and so
$$B\in \bsig01(\{D\cross C: D\in\borel(\bairespace)
\rmand C \mbox{ clopen}\}).$$
\qed
Note that for every $\alpha<\omega_1$ there exists a
$\bpi11$ set $U$ which is universal for all $\bdel0\alpha$
sets, i.e., every cross section of $U$ is $\bdel0\alpha$ and
every $\bdel0\alpha$ set occurs as a cross section of $U$.
To see this, let $V$ be a $\Pi^0_\alpha$ set which is universal for
$\bpi0\alpha$ sets. Now put
$$(x,y)\in U \rmiff y\in V_{x_0} \rmand \forall z (z\in V_{x_0}\rmiff
z\notin V_{x_1}) $$
where $x=(x_0,x_1)$ is some standard pairing function. Note also
that the complement of $U$ is also universal for all
$\bdel0\alpha$ sets, so there is a $\bsig11$ which
is universal for all $\bdel0\alpha$ sets. Louveau's Theorem
implies that there can be no Borel set universal for all
$\bdel0\alpha$ sets.
\begin{corollary} \label{univdel}
There can be no Borel set universal for all
$\bdel0\alpha$ sets.
\end{corollary}\sdex{$?bdel0\alpha$-universal set}
In order to prove this corollary we will need the following lemmas.
A space is Polish iff it is a separable complete metric space.
\begin{lemma}\label{sierchar}
If $X$ is a $0$-dimensional
Polish space, then there exists a closed set $Y\subseteq\bairespace$
such that $X$ and $Y$ are homeomorphic.
\end{lemma}
\proof
Build a tree $\langle C_s:s\in T\rangle$ of nonempty clopen sets
indexed by a tree $T\subseteq\finseq$ such that
\begin{enumerate}
\item $C_{\emptyseq}=X$,
\item the diameter of $C_s$ is less that $1/|s|$ for $s\not=\emptyseq$, and
\item for each $s\in T$ the clopen set $C_s$ is the disjoint union
of the clopen sets $$\{C_{s\concat n}:s\concat n\in T\}.$$
\end{enumerate}
If $Y=[T]$ (the infinite branch of $T$), then $X$ and $Y$ are homeomorphic.
\qed
I am not sure who proved this first.
I think the argument for
the next lemma comes
from a theorem about Hausdorff that lifts the difference hierarchy
on the $\bdel02$-sets to the $\bdel0\alpha$-sets. This
presentation is taken from
Kechris \site{kechris} {\it mutatis mutandis}.\footnote{
Latin for plagiarized.}
\begin{lemma} \label{haushomeo}
For any sequence
$\langle B_n:n\in\omega\rangle$
of Borel subsets of $\bairespace$ there exists $0$-dimensional Polish
topology, $\tau$, which contains the standard topology and each
$B_n$ is a clopen set in $\tau$.
\end{lemma}
\proof
This will follow easily from the next two claims.
\claim Suppose $(X,\tau)$ is a 0-dimensional Polish space and
$F\subseteq X$ is
closed, then there exists a 0-dimensional Polish topology
$\sigma\supseteq \tau$ such that $F$ is clopen in $(X,\sigma)$.
(In fact, $\tau\union\{F\}$ is a subbase for $\sigma$.)
\proof
Let $X_0$ be $F$ with the subspace topology given by $\tau$
and $X_1$ be $\comp{F}$ with the subspace topology. Since $X_0$ is
closed in $X$ the complete metric on $X$ is complete when restricted
to $X_0$.
Since $\comp{F}$ is open there is another metric which is complete
on $X_1$. This is a special case of Alexandroff's Theorem
which says that a $G_\delta$ set in a completely metrizable space is
completely metrizable in the subspace topology. In this case the
complete metric $\hat{d}$ on $\comp{F}$ would be defined by
$$\hat{d}(x,y)=d(x,y)+\left|{1\over d(x,F)}- {1\over d(y,F)}\right|$$
where $d$ is a complete metric on $X$ and $d(x,F)$ is the distance
from $x$ to the closed set $F$.
Let
$$(X,\sigma)=X_0\oplus X_1$$
be the discrete topological sum, i.e.,
$U$ is open iff $U=U_0\union U_1$ where $U_0\subseteq X_0$ is open in $X_0$
and $U_1\subseteq X_1$ is open in $X_1$.
\qed
\claim If $(X,\tau)$ is a Hausdorff space and $(X,\tau_n)$ for
$n\in\omega$ are 0-dimensional Polish topologies extending $\tau$, then
there exists a 0-dimensional Polish topology $(X,\sigma)$ such that
$\tau_n\subseteq \sigma$ for every $n$. (In fact
$\Union_{n<\omega}\tau_n$ is a subbase for $\sigma$.)
\proof
Consider the 0-dimensional Polish space
$$\prod_{n\in\omega}(X,\tau_n).$$
Let $f:X\arrow \prod_{n\in\omega}(X,\tau_n)$ be the embedding
which takes each $x\in X$ to the constant sequence $x$
(i.e., $f(x)=\langle x_n:n\in\omega\rangle$ where $x_n=x$ for every $n$).
Let $D\subseteq\prod_{n\in\omega}(X,\tau_n)$ be the range of $f$, the
set of constant sequences. Note that $f:(X,\tau)\arrow (D,\tau)$ is
a homeomorphism. Let $\sigma$ be the topology on $X$ defined by
\begin{center}
$U\in \sigma$ iff there exists $V$ open in $\prod_{n\in\omega}(X,\tau_n)$ with
$U=f^{-1}(V)$.
\end{center}
Since each $\tau_n$ extends $\tau$ we get that $D$ is a closed subset
of $\prod_{n\in\omega}(X,\tau_n)$. Consequently, $D$ with the subspace
topology inherited from $\prod_{n\in\omega}(X,\tau_n)$ is Polish.
It follows that $\sigma$ is a Polish topology on $X$.
To see that $\tau_n\subseteq\sigma$ for every $n$ let
$U\in\tau_N$ and define
$$V=\prod_{nN}X.$$
Then $f^{-1}(V)=U$ and so $U\in\sigma$.\qed
We prove Lemma \ref{haushomeo} by induction on the rank of the
Borel sets. Note that by the second Claim it
is enough to prove it for one Borel set at a time. So suppose
$B$ is a $\bsig0\alpha$ subset of $(X,\tau)$. Let
$B=\Union_{n\in\omega}B_n$ where each $B_n$ is $\bpi0\beta$ for
some $\beta<\alpha$. By induction on $\alpha$ there exists
a 0-dimensional Polish topology $\tau_n$ extending $\tau$ in
which each $B_n$ is clopen. Applying the second Claim gives
us a 0-dimensional topology $\sigma$ extending $\tau$ in which each
$B_n$ is clopen and therefore $B$ is open. Apply the first Claim
to get a 0-dimensional Polish topology in which $B$ is clopen.
\qed
\proof
(of Corollary \ref{univdel}). The idea of this proof is to reduce it to
the case of a $\bdel0\alpha$ set universal for $\bdel0\alpha$-
sets, which is easily seen to be impossible by the standard diagonal
argument.
Suppose $B$ is a Borel set which is universal
for all $\bdel0\alpha$ sets. Then by the Corollary~\ref{section}
$$B\in \Delta^0_\alpha(\{D\cross C: D\in\borel(\bairespace)
\rmand C \mbox{ is clopen}\}).$$
By Lemma \ref{haushomeo} there exists a 0-dimensional Polish topology $\tau$
such that if $$X=(\bairespace,\tau)$$ then
$B$ is $\bdel0\alpha(X\cross\bairespace)$. Now by Lemma \ref{sierchar}
there exists a closed set $Y\subseteq\bairespace$ and a homeomorphism
$h:X\arrow Y$. Consider
$$C=\{(x,y)\in X\cross X: (x,h(y))\in B\}.$$
The set $C$ is $\bdel0\alpha$ in $X\cross X$ because it is
the continuous preimage of the set $B$ under the map $(x,y)\mapsto (x,h(y))$.
The set $C$ is also universal for $\bdel0\alpha$ subsets of
$X$ because the set $Y$ is closed. To see this for $\alpha>1$ if
$H\in\bdel0\alpha(Y)$, then $H\in\bdel0\alpha(\bairespace)$,
consequently there exists $x\in X$ with $B_x=H$. For $\alpha=1$ just
use that disjoint closed subsets of $\bairespace$ can be separated by
clopen sets.
Finally, the set $C$ gives a contradiction by the usual
diagonal argument:
$$D=\{(x,x): x\notin C\}$$
would be $\bdel0\alpha$ in $X$ but cannot be a cross section of $C$.
\qed
\begin{question}
(Mauldin) Does there exists a $\Pi^1_1$ set which is universal
for all $\bpi11$ sets which are not Borel?\footnote{This
was answered by Greg Hjorth \site{hjorth2}, who showed it
is independent.}
\end{question}
We could also ask for the complexity of a set which is universal
for $\bsig0\alpha\setminus \bdel0\alpha$ sets.
\sector{Proof of Louveau's Theorem}
Finally, we arrive at our last section.
The following summarizes how I feel now.
\begin{quote}
You are walking down the street minding your own business and someone
stops you and asks directions. Where's xxx hall? You don't
know and you say you don't know. Then they point at the next street and
say: Is that xxx street? Well by this time you feel kind of
stupid so you say, yea yea that's xxx street, even though you haven't
got the slightest idea whether it is or not. After all, who wants
to admit they don't know where they are going or where they are.
\end{quote}
\bigskip
For $\alpha<\omega_1^{CK}$ define $D\subseteq\bairespace$
is $\Sigma^0_\alpha(\semihyp)$ \sdex{$\Sigma^0_\alpha(\semihyp)$}
iff there exists $S$ a $\Pi_1^1$ set of hyperarithmetic reals
such that every
element of $S$ is a $\beta$-code for some $\beta<\alpha$ and
$$D=\Union\{P(T,q): (T,q)\in S\}.$$
A set is $\Pi^0_\alpha(\semihyp)$ iff it is the complement of
\sdex{$\Pi^0_\alpha(\semihyp)$}
a $\Sigma^0_\alpha(\semihyp)$ set. The
$\Pi^0_0(\semihyp)$ sets are just the usual clopen basis
($[s]$ for $s\in\finseq$ together with
the empty set) and $\Sigma^0_0(\semihyp)$ sets are their complements.
\begin{lemma}
$\Sigma^0_\alpha(\semihyp)$ sets are $\Pi^1_1$ and
consequently $\Pi^0_\alpha(\semihyp)$ sets are $\Sigma^1_1$.
\end{lemma}
\proof
$x\in \Union\{P(T,q): (T,q)\in S\}$ iff there exists $(T,q)\in \Delta^1_1$
such that
$(T,q)\in S$ and $x\in P(T,q)$.
Quantification over
$\Delta_1^1$ preserves $\Pi^1_1$ ( see Corollary \ref{gandy2} )
and Lemma \ref{defdelta} implies that ``$x\in P(T,q)$'' is $\Delta^1_1$.
\qed
We will need the following reflection principle in order to prove
the Main Lemma \ref{louvmain}.
A predicate $\Phi\subseteq P(\omega)$ is called $\Pi_1^1$ on
$\Pi_1^1$ iff for any $\Pi^1_1$ set $N\subseteq\omega\cross\omega$
the set $\{e:\Phi(N_e)\}$ is $\Pi_1^1$
(where $N_e=\{n:(e,n)\in N\}$). \sdex{$\Pi_1^1$ on $\Pi_1^1$}
\begin{lemma}\label{reflect} \sdex{$\Pi^1_1$-Reflection}
(Harrington \site{harshemar} Kechris \site{kecref})
$\Pi^1_1$-Reflection. Suppose
$\Phi(X)$ is $\Pi_1^1$ on
$\Pi_1^1$ and Q is a $\Pi^1_1$ set.
If $\Phi(Q)$, then
there exists a $\Delta^1_1$ set $D\subseteq Q$ such that $\Phi(D)$.
\end{lemma}
\proof
By the normal form theorem \ref{normal} there is a recursive mapping
$e\arrow T_e$ such that $e\in Q$ iff $T_e$ is well-founded.
Define for $e\in\omega$
$$N_e^0=\{\hat{e}: T_{\hat{e}}\embed T_e\}$$
$$N_e^1=\{\hat{e}: \neg(T_e\strictembed T_{\hat{e}})\}$$
then $N^0$ is $\Sigma^1_1$ and $N^1$ is $\Pi^1_1$. For
$e\in Q$ we have $N_e^0=N_e^1=D_e\subseteq Q$ is $\Delta^1_1$;
and for $e\notin Q$ we have that $N_e^1=Q$. If we assume for
contradiction that $\neg\Phi(N_e^1)$ for all $e\in Q$, then
$$e\notin Q \rmiff \phi(N_e^1).$$
But this would mean that $Q$ is $\Delta^1_1$ and this proves
the Lemma.\qed
Note that a $\Pi^1_1$ predicate need not be $\Pi_1^1$ on
$\Pi_1^1$ since the predicate
$$\Phi(X)=\mbox{``}0\notin X\mbox{''}$$
is $\Delta^0_0$ but not $\Pi_1^1$ on
$\Pi_1^1$. Some examples of $\Pi^1_1$ on $\Pi^1_1$ predicates
$\Phi(X)$ are
$$\Phi(X)\rmiff \forall x\notin X\;\; \theta(x)$$
or
$$\Phi(X)\rmiff \forall x,y\notin X\;\; \theta(x,y)$$
where $\theta$ is a $\Pi^1_1$ sentence.
\begin{lemma}\label{louvmain}
Suppose $A$ is $\Sigma^1_1$ and $A\subseteq B\in\Sigma^0_\alpha(\semihyp)$,
then there exists $C\in \Sigma^0_\alpha(\hyp)$ with
$A\subseteq C\subseteq B$.
\end{lemma}
\proof
Let $B=\Union\{P(T,q): (T,q)\in S\}$ where $S$ is a $\Pi^1_1$ set of
hyperarithmetic $<\alpha$-codes. Let $\hat{S}\subseteq\omega$
be the $\Pi^1_1$ set of $\Delta_1^1$-codes for elements of $S$, i.e.
\begin{center}
$e\in\hat{S}$ iff $e$ is a $\Delta^1_1$-code for $(T_e,q_e)$ and
$(T_e,q_e)\in S$.
\end{center}
Now define the predicate $\Phi(X)$ for $X\subseteq\omega$ as follows:
\begin{center}
$\Phi(X)$ iff $X\subseteq \hat{S}$ and $A\subseteq\Union_{e\in X}P(T_e,q_e)$.
\end{center}
The predicate $\Phi(X)$ is $\Pi^1_1$ on $\Pi_1^1$ and
$\Phi(\hat{S})$. Therefore by reflection (Lemma \ref{reflect})
there exists a $\Delta^1_1$ set $D\subseteq \hat{S}$ such that
$\Phi(D)$. Define
$(T,q)$ by
$$T=\{e\concat s: e\in D \rmand s\in T_e\}\;\;\;\;\;\;\;
q(e\concat s)=q_e(s) \mbox{ for } e\in D \rmand s\in \tzero_e.$$
Since $D$ is $\Delta^1_1$ it is easy to check that $(T,q)$ is
$\Delta^1_1$ and hence hyperarithmetic. Since $\Phi(D)$ holds
it follows that $C=S(T,q)$ the $\Sigma^0_\alpha(\hyp)$ set coded
by $(T,q)$ has the property that $A\subseteq C$ and since $D\subseteq\hat{S}$
it follows that $C\subseteq B$.
\qed
Define for $\alpha<\omega_1^{CK}$ the $\alpha$-topology by taking for
basic open sets the family \sdex{$\alpha$-topology}
$$\Union\{\Pi^0_\beta(\semihyp):\beta<\alpha\}.$$
As usual, $\cl_\alpha(A)$ denotes the closure of the set $A$ in the
$\alpha$-topology. \sdex{$?cl_\alpha(A)$}
The 1-topology is just the standard topology on $\bairespace$. The
$\alpha$-topology has its basis certain special $\Sigma^1_1$ sets
so it is intermediate between the standard topology and the Gandy
topology corresponding to Gandy forcing.
\begin{lemma}\label{semihyp}
If $A$ is $\Sigma^1_1$, then $\cl_\alpha(A)$ is $\Pi^0_\alpha(\semihyp)$.
\end{lemma}
\proof
Since the $\Sigma_{\beta}^0(\semihyp)$ sets for $\beta<\alpha$ form
a basis for the $\alpha$-closed sets,
$$\cl_\alpha(A)=\Intersect\{X\supseteq A:\exists\beta<\alpha\;\;
X\in\Sigma_{\beta}^0(\semihyp)\}.$$
By Lemma \ref{louvmain} this same intersection can be written:
$$\cl_\alpha(A)=\Intersect\{X\supseteq A:\exists\beta<\alpha\;\;
X\in\Sigma_{\beta}^0(\hyp)\}.$$
But now define $(T,q)\in Q$ iff $(T,q)\in \Delta^1_1$, $(T,q)$
is a $\beta$-code for some $\beta<\alpha$, and
$A\subseteq S(T,q)$. Note that $Q$ is a $\Pi^1_1$ set and consequently,
$\cl_\alpha(A)$ is a $\Pi^0_\alpha(\semihyp)$ set, as desired.
\qed
Note that it follows from the Lemmas that for $A$ a $\Sigma^1_1$
set, $\cl_\alpha(A)$ is a $\Sigma^1_1$ set which is a basic open
set in the $\beta$-topology for any $\beta>\alpha$.
Let $\poset$ be Gandy forcing, i.e., the partial order of all
nonempty $\Sigma^1_1$ subsets of $\bairespace$ and let
$\name{a}$ be a name for the real obtained by forcing with
$\poset$, so that by Lemma \ref{real}, for any $G$ which is
$\poset$-generic, we have that $p\in G$ iff $a^G\in p$.
\begin{lemma} \label{louvforce}
For any $\alpha<\omega_1^{CK}$, $p\in\poset$, and $C\in{\bpi0\alpha}$
(coded in $V$) if
$$p\forces \name{a}\in C,$$
then
$$cl_\alpha(p)\forces \name{a}\in C.$$
\end{lemma}
\proof
This is proved by induction on $\alpha$.
For $\alpha=1$ recall that the $\alpha$-topology is the standard topology
and $C$ is a standard closed set. If $p\forces \name{a}\in C$, then it
better be that $p\subseteq C$, else there exists $s\in\finseq$ with
$q=p\intersect [s]$ nonempty and $[s]\intersect C=\emptyset$. But
then $q\leq p$ and $q\forces\name{a}\notin C$. Hence $p\subseteq C$
and since $C$ is closed, $\cl(p)\subseteq C$. Since
$\cl(p)\forces a\in\cl(p)$, it follows that
$\cl(p)\forces a\in C$.
For $\alpha>1$ let
$$C=\Intersect_{n<\omega} \comp{C_n}$$
where each $C_n$ is
${\bpi0{\beta}}$ for some $\beta<\alpha$. Suppose for contradiction
that
$$cl_\alpha(p)\not\forces \name{a}\in C$$
Then for some $n<\omega$ and
$r\leq cl_\alpha(p)$ it must be that
$$r\forces \name{a}\in C_n.$$
Suppose that $C_n$ is ${\bpi0{\beta}}$ for some $\beta<\alpha$. Then
by induction
$$\cl_\beta(r)\forces \name{a}\in C_n.$$
But $\cl_\beta(r)$ is a $\Pi^0_\beta(\semihyp)$ set by Lemma \ref{semihyp}
and hence a basic open set in the $\alpha$-topology. Note that since
they force contradictory information
($\cl_\beta(r)\forces \name{a}\notin C$ and $p\forces \name{a}\in C$)
it must be that $\cl_\beta(r)\intersect p=\emptyset$, (otherwise
the two conditions would be compatible in $\poset$).
But since $\cl_\beta(r)$ is $\alpha$-open this means that
$$\cl_\beta(r)\intersect\cl_\alpha(p)=\emptyset$$
which contradicts the
fact that $r\leq \cl_\alpha(p)$.
\qed
Now we are ready to prove Louveau's Theorem \ref{louv}.
Suppose $A$ and $B$ are $\Sigma^1_1$ sets and $C$ is
a $\bpi0\alpha$ set with $A\subseteq C$ and
$C\intersect B=\emptyset$. Since $A\subseteq C$ it follows
that
$$A\forces \name{a}\in C.$$
By Lemma \ref{louvforce} it follows that
$$\cl_\alpha(A)\forces \name{a}\in C.$$
Now it must be that $\cl_\alpha(A)\intersect B=\emptyset$, otherwise
letting $p=\cl_\alpha(A)\intersect B$ would be a condition of
$\poset$ such that
$$p\forces \name{a}\in C$$
and
$$p\forces\name{a}\in B$$
which would imply that $B\intersect C\not=\emptyset$ in the generic
extension. But by absoluteness $B$ and $C$ must remain disjoint.
So $\cl_\alpha(A)$ is a $\Pi_\alpha(\semihyp)$-set (Lemma \ref{semihyp})
which is disjoint from the set $B$ and thus by applying Lemma \ref{louvmain}
to its complement there exists a $\Pi^0_\alpha(\hyp)$-set $C$
with $\cl_\alpha(A)\subseteq C$ and $C\intersect B=\emptyset$.
\qed
The argument presented here is partially from Harrington \site{harlouv},
but contains even more simplification brought about by using
forcing and absoluteness. Louveau's Theorem is also
proved in Sacks \site{sack}, Mansfield and Weitkamp \site{manweit}
and Kanovei \site{kanovei}. For a generalization to higher
levels of the projective hierarchy using determinacy, see
Hjorth \site{hjorth3}.
\bigskip\bigskip\bigskip
\begin{center}
Elephant Sandwiches
\end{center}
A man walks by a restaurant. Splashed all over are signs saying
``Order any sandwich'', ``Just ask us, we have it'', and ``All
kinds of sandwiches''.
Intrigued, he walks in and says to the
proprietor, ``I would like an elephant sandwich.''
The proprietor
responds ``Sorry, but you can't have an elephant sandwich.''
``What do you mean?'' says the man, ``All your signs say to order
any sandwich. And here the first thing I ask for, you don't
have.''
Says the proprietor ``Oh we have elephant. Its just that
here it is 5pm already and I just don't want to start another
elephant.''
%%%%%%%% references and index %%%%%%%%%%%
\newpage
\addtocontents{toc}{ }
\addtocontents{toc}{\protect\bigskip}
\addtocontents{toc}{ }
\addtocontents{toc}{References \hfill \thepage}
\begin{thebibliography}{99}
\bibitem{addison}
J.W.Addison, Separation principles in the hierarchies of classical
and effective descriptive set theory, Fundamenta Mathematicae, 46(1959),
123-135.
Cited on page:
9
\bibitem{addison2}
J.W.Addison, Some consequences of the axiom of constructibility,
Fundamenta Mathematicae, 46(1957), 337-357.
Cited on page:
82
\bibitem{baire99}
R.Baire, Sur la th\'{e}orie des ensembles, Comptes Rendus
Academie Science Paris,
129(1899), 946-949.
Cited on page:
3
\bibitem{baire}
R.Baire, Sur la repr\'{e}sentation des fonctions discontinues (2me partie),
Acta Mathematica, 32(1909), 97-176.
Cited on page:
1
\bibitem{balogh}
Z.Balogh, There is a $Q$-set space in ZFC,
Proceedings of the American Mathematical Society, 113(1991), 557-561.
Cited on page:
17
\bibitem{barto4}
T.Bartoszynski, Combinatorial aspects of measure and category,
Fundamenta Mathematicae, 127(1987), 225-239.
Cited on page:
77
\bibitem{barto}
T.Bartoszynski, On covering of real line by null sets,
Pacific Journal of Mathematics, 131(1988),1-12.
Cited on page:
75
\bibitem{barto2}
T.Bartoszynski, H.Judah, S.Shelah,
The cofinality of cardinal invariants related to measure and category,
Journal of Symbolic Logic, 54(1989), 719-726.
Cited on page:
75
\bibitem{barto3}
T.Bartoszynski, H.Judah,
On the cofinality of the smallest covering of the real line by meager sets,
Journal of Symbolic Logic, 54(1989), 828-832.
Cited on page:
75
\bibitem{barwise}
J.Barwise, {\bf Admissible sets and structures}, Springer-Verlag, 1975.
Cited on page:
106
\bibitem{bell}
M.Bell, On the combinatorial principal P(c), Fundamenta Mathematicae,
114(1981), 149-157.
Cited on page:
17
\bibitem{bbm}
R.H.Bing, W.W.Bledsoe, R.D.Mauldin, Sets generated by rectangles,
Pacific J. Math., 51(1974, 27-36.
Cited on page:
10
\bibitem{brez}
C.Brezinski, {\bf History of Continued Fractions and Pad\'{e} Approximants},
Springer-Verlag, 1991.
Cited on page:
3
\bibitem{burgess}
J.Burgess, Infinitary languages and descriptive set theory, PhD
University of California, Berkeley, 1974.
Cited on page:
125
\bibitem{burgess2}
J.Burgess, Equivalences generated by families of Borel sets, Proceedings
of the American Mathematical Society, 69(1978), 323-326.
Cited on page:
129
\bibitem{burgess3}
J.Burgess, Effective enumeration of classes in a $\Sigma^1_1$ equivalence
relation, Indiana University Mathematics Journal, 28(1979), 353-364.
Cited on page:
129
\bibitem{changk}
C.C.Chang, H.J.Keisler,
{\bf Model Theory}, North Holland, 1973.
Cited on page:
0
\bibitem{ems}
F.van Engelen, A.Miller, J.Steel, Rigid Borel sets and
better quasiorder theory, Contemporary Mathematics
(American Mathematical Society), 65(1987), 199-222.
Cited on page:
112
\bibitem{euler}
L.Euler, De fractionibus continuis dissertatio, Comm. Acad. Sc. Imp. St.
P\'{e}tersbourg, 9(1737), 98-137.
Cited on page:
3
\bibitem{ekm}
F.van Engelen, K.Kunen, A.Miller, Two remarks about analytic sets,
Lecture Notes in Mathematics, Springer-Verlag, 1401(1989), 68-72.
Cited on page:
121
\bibitem{erdkm}
P.Erdos, K.Kunen, R.Mauldin,
Some additive properties of sets of real numbers,
Fundamenta Mathematicae, 113(1981), 187-199.
Cited on page:
112
\bibitem{feng}
Q.Feng, Homogeneity for open partitions of pairs of reals, Transactions
of the American Mathematical Society, 339(1993), 659-684.
Cited on page:
123
\bibitem{qsets}
W.Fleissner, A.Miller, On Q-sets, Proceedings of the American
Mathematical Society, 78(1980), 280-284.
Cited on page:
17
\bibitem{fleiss1}
W.Fleissner,
Current research on $Q$ sets,
in {\bf Topology, Vol. I (Proc. Fourth Colloq., Budapest, 1978)},
Colloq. Math. Soc. Janos Bolyai, 23(1980), 413-431.
Cited on page:
17
\bibitem{fleiss2}
W.Fleissner, Squares of $Q$ sets,
Fundamenta Mathematicae, 118(1983), 223-231.
Cited on page:
17
\bibitem{fremlin}
D.H.Fremlin, On the Baire order problem, Note of 29.4.82.
Cited on page:
51
\bibitem{frembook}
D.H.Fremlin, {\bf Consequences of Martin's Axiom}, Cambridge University
Press, 1984.
Cited on page:
17
77
\bibitem{fried}
H.Friedman, PCA well-orderings of the line, Journal of Symbolic Logic,
39(1974), 79-80.
Cited on page:
97
\bibitem{frieds}
S.Friedman, Steel Forcing and Barwise compactness,
Annals of Mathematical Logic, 22(1982), 31-46.
Cited on page:
27
\bibitem{galmil}
F.Galvin, A.Miller, $\gamma$-sets and other singular sets of real
numbers, Topology and Its Applications, 17(1984), 145-155.
Cited on page:
17
52
\bibitem{gandy}
R.O.Gandy, Proof of Mostowski's conjecture,
Bulletin de L'Academie Polonaise des Science, 8 (1960), 571-575.
Cited on page:
109
\bibitem{god}
K.G\"odel, The consistency of the axiom of choice and of the
generalized continuum hypothesis, Proceedings of the National
Academy of Science, 24(1938), 556-557.
Cited on page:
82
\bibitem{harrsilv}
L.Harrington, A powerless proof of a Theorem of Silver,
handwritten note dated 11-76.
Cited on page:
113
\bibitem{harlouv}
L.Harrington, Theorem (A. Louveau), handwritten note undated,
circa 1976.
Cited on page:
141
\bibitem{harring}
L.Harrington, Long projective well-orderings,
Annals of Mathematical Logic, 12(1977), 1-24.
Cited on page:
98
101
\bibitem{harrsharp}
L.Harrington, Analytic determinacy and $0^{\#}$,
Journal of Symbolic Logic, 43(1978), 685-693.
Cited on page:
27
\bibitem{harsami}
L.Harrington, R.Sami,
Equivalence relations, projective and beyond, Logic Colloquium 78,
ed Boffa et al, North Holland 1979, 247-263.
Cited on page:
129
\bibitem{harrshel}
L.Harrington and S.Shelah, Counting equivalence classes for
co-$\kappa$-Souslin equivalence relations, in {\bf Logic Colloquium 80},
North Holland, 1982, 147-152.
Cited on page:
113
129
\bibitem{harshemar}
L.Harrington, D.Marker, S.Shelah, Borel orderings,
Transactions of the American Mathematical Society, 310(1988), 293-302.
Cited on page:
119
123
129
137
\bibitem{hinman}
P.Hinman, {\bf Recursion-Theoretic Hierarchies}, Springer-Verlag, 1978.
Cited on page:
106
\bibitem{hjorth}
G.Hjorth, Thin equivalence relations and effective decompositions,
Journal of Symbolic Logic, 58(1993), 1153-1164.
Cited on page:
129
\bibitem{hjorth2}
G.Hjorth, Universal co-analytic sets,
Proceedings of the American Mathematical Society,
124(1996), 3867-3873.
Cited on page:
136
\bibitem{hjorth3}
G.Hjorth,
Two applications of inner model theory to the study of
$\Sigma^1_2$ sets, Bulletin of Symbolic Logic, 2(1996), 94-107.
Cited on page:
141
\bibitem{jech}
T.Jech, {\bf Set Theory}, Academic Press, 1978.
Cited on page:
0
16
28
40
128
\bibitem{jensol}
R.B.Jensen, R.M.Solovay, Some applications of almost disjoint sets,
in {\bf Mathematical Logic and Foundations of Set Theory},
ed by Y.Bar Hillel, 1970, North Holland, 84-104.
Cited on page:
16
\bibitem{qsetzero}
H.Judah, S.Shelah,
$Q$-sets do not necessarily have strong measure zero,
Proceedings of the American Mathematical Society, 102 (1988), 681-683.
Cited on page:
17
58
\bibitem{qsetsier}
H.Judah, S.Shelah, $Q$-sets, Sierpi\'{n}ski sets, and rapid filters,
Proceedings of the American Mathematical Society, 111(1991), 821-832.
Cited on page:
17
\bibitem{kanovei}
V.G.Kanove\u\i,
Topologies generated by effectively Suslin sets and their applications in
descriptive set theory, Russian Mathematical Surveys, 51(1996),
385-417.
Cited on page:
118
141
\bibitem{kondo}
M.Kond\v{o}, Sur l'uniformisation des compl\'{e}mentaires analytiques et
les ensembles projectifs de la seconde classe, Japan J. Math. 15(1939),
197-230.
Cited on page:
90
\bibitem{kecref}
A. Kechris,
Spector second order classes and reflection,
in {\bf Generalized recursion theory, II }, North Holland 1978,
Studies Logic Foundations Math., 94(1978), 147-183.
Cited on page:
137
\bibitem{kechris2}
A.Kechris, On transfinite sequences of projective sets with an application
to ${\bf\Sigma}^1_2$ equivalence
relations, in {\bf Logic Colloquium '77} ed by Macintyre et al,
North Holland, 1978, 155-160.
Cited on page:
129
\bibitem{kechris3}
A. Kechris,
The perfect set theorem and definable wellorderings of the continuum,
Journal of Symbolic Logic, 43(1978),
630-634.
Cited on page:
97
\bibitem{kecmar}
A.S.Kechris, D.A.Martin, Infinite games and effective descriptive
set theory, in {\bf Analytic sets}, ed by C.A.Rogers, Academic
Press, 1980.
Cited on page:
113
\bibitem{kechris}
A.S.Kechris,
{\bf Classical descriptive set theory}, Graduate Texts in Mathematics, 156,
Springer-Verlag, New York, 1995.
Cited on page:
0
133
\bibitem{kleene}
S.Kleene, Hierarchies of number-theoretic predicates, Bulletin of
the American Mathematical Society, 63(1955), 193-213.
Cited on page:
104
\bibitem{kunenbk}
K.Kunen, {\bf Set Theory },
North Holland, 1980.
Cited on page:
0
16
19
39
40
128
\bibitem{kunmil}
K. Kunen, A.Miller, Borel and projective sets from the point of view of
compact sets, Mathematical Proceedings of the Cambridge Philosophical
Society, 94(1983), 399-409.
Cited on page:
56
\bibitem{kunenma}
K.Kunen,
Where MA first fails,
Journal of Symbolic Logic, 53(1988), 429-433.
Cited on page:
77
\bibitem{kur}
K.Kuratowski, {\bf Topology}, vol 1, Academic Press, 1966.
Cited on page:
0
78
\bibitem{kurmos}
K.Kuratowski, A.Mostowski, {\bf Set theory, with an introduction to
descriptive set theory}, North Holland, 1976.
Cited on page:
0
94
\bibitem{landver}
A.Landver,
Singular $\sigma$-dense trees,
Journal of Symbolic Logic, 57(1992), 1403-1416.
Cited on page:
77
\bibitem{landver2}
A.Landver,
Baire numbers, uncountable Cohen sets and perfect-set forcing,
Journal of Symbolic Logic, 57(1992), 1086-1107.
Cited on page:
77
\bibitem{leb}
H.Lebesgue, Sur les fonctions repr\'{e}sentables analytiquement,
Journal de Math\'{e}mati\-ques Pures et Appliqu\'{e}s, 1(1905), 139-216.
Cited on page:
7
9
\bibitem{louvsilv}
A. Louveau,
Relations d'equivalence dans les espaces polonais,
Collection: General logic seminar, (Paris, 1982-83), 113-122,
Publ. Math. Univ. Paris VII.
Cited on page:
113
\bibitem{louveau}
A.Louveau, A separation theorem for $\Sigma^1_1$ sets,
Transactions of the American Mathematical Society, 260(1980), 363-378.
Cited on page:
130
\bibitem{loust}
A.Louveau, J.Saint Raymond, Borel classes and closed games: Wadge-type
and Hurewicz-type results, Transactions of the American Mathematical
Society, 304(1987), 431-467.
Cited on page:
131
\bibitem{louvlin}
A. Louveau, Two results on Borel orders,
Journal of Symbolic Logic, 54(1989), 865-874.
Cited on page:
123
\bibitem{louvbor}
A.Louveau, Classifying Borel Structures, in
{\bf Set Theory of the Continuum}, ed by Judah et al.,
Springer-Verlag, 1992, 103-112.
Cited on page:
123
\bibitem{luz}
N.Luzin, Sur un probl\`eme de M. Baire, Comptes Rendus Hebdomaddaires Seances
Academie Science Paris, 158(1914), 1258-1261.
Cited on page:
35
\bibitem{mahlo}
P.Mahlo, \"Uber Teilmengen des Kontinuums von dessen Machtigkeit,
Sitzungsberichte der Sachsischen Akademie der Wissenschaften zu Leipsiz,
Mathematisch Naturwissenschaft\-liche Klasse 65, (1913), 283-315.
Cited on page:
35
36
\bibitem{manfield}
R.Mansfield, The non-existence of $\Sigma^1_2$ well-ordering of
the Baire space, Fundamenta Mathematicae, 86(1975), 279-282.
Cited on page:
97
\bibitem{mansf}
R.Mansfield, Perfect subsets of definable sets of real numbers,
Pacific Journal of Mathematics, 35(1970), 451-457.
Cited on page:
88
\bibitem{manweit}
R.Mansfield, G.Weitkamp, {\bf Recursive Aspects of Descriptive Set
Theory}, Oxford University Press (1985).
Cited on page:
113
141
\bibitem{marsol}
D.A.Martin, R.M.Solovay, Internal Cohen extensions,
Annals of Mathematical Logic, 2(1970), 143-178.
Cited on page:
16
38
95
\bibitem{borelhier}
A.Miller, On the length of Borel hierarchies, Annals of Mathematical Logic,
16(1979), 233-267.
Cited on page:
13
19
29
34
36
37
49
50
72
\bibitem{cat}
A.Miller, On generating the category algebra and the Baire order problem,
Bulletin de L'Academie Polonaise des Science, 27(1979), 751-755.
Cited on page:
43
\bibitem{gensous}
A.Miller, Generic Souslin sets, Pacific Journal of Mathematics,
97(1981), 171-181.
Cited on page:
27
\bibitem{someprop}
A.Miller, Some properties of measure and category, Transactions of
the American
Mathematical Society, 266(1981), 93-114. Corrections and additions to
some properties of measure and category, Transactions of the American
Mathematical Society, 271(1982), 347-348.
Cited on page:
72
\bibitem{ctlbcof}
A.Miller, The Baire category theorem and cardinals of countable cofinality,
Journal of Symbolic Logic, 47(1982), 275-288.
Cited on page:
73
75
76
\bibitem{char}
A.Miller, A characterization of the least cardinal for which the Baire
category theorem fails, Proceedings of the American Mathematical
Society, 86(1982), 498-502.
Cited on page:
77
\bibitem{maponto}
A.Miller, Mapping a set of reals onto the reals, Journal of Symbolic Logic,
48(1983), 575-584.
Cited on page:
58
72
\bibitem{ctblmod}
A.Miller, The Borel classification of the isomorphism class of a
countable model,
Notre Dame Journal of Formal Logic, 24(1983), 22-34.
Cited on page:
9
\bibitem{survey1}
A.Miller, Special subsets of the real line,
in {\bf Handbook of set-theoretic topology},
North Holland, 1984, 201-233.
Cited on page:
17
\bibitem{prikmil}
A.Miller, K. Prikry, When the continuum has cofinality $\omega_1$,
Pacific Journal of Mathematics, 115(1984), 399-407.
Cited on page:
42
\bibitem{infcomb}
A.Miller, Infinite combinatorics and definability,
Annals of Pure and Applied Mathematical Logic, 41(1989), 179-203.
Cited on page:
112
\bibitem{proj}
A.Miller, Projective subsets of separable metric spaces,
Annals of Pure and Applied Logic, 50(1990), 53-69.
Cited on page:
12
\bibitem{survey2}
A.Miller, Special sets of reals, in {\bf Set Theory of the Reals},
ed Haim Judah, Israel Mathematical Conference Proceedings,
vol 6(1993), 415-432, American Math Society.
Cited on page:
12
17
\bibitem{playful}
Y.Moschovakis, Uniformization in a playful universe, Bulletin of
the American Mathematical Society, 77(1971), 731-736.
Cited on page:
94
\bibitem{mosch}
Y.Moschovakis, {\bf Descriptive set theory}, North Holland 1980.
Cited on page:
0
78
\bibitem{oxt}
J.C.Oxtoby, {\bf Measure and category}, Springer-Verlag, 1971.
Cited on page:
0
68
\bibitem{pop}
G.Poprougenko, Sur un probl/`{e}me de M. Mazurkiewicz, Fundamenta
Mathematicae, 15(1930), 284-286.
Cited on page:
65
\bibitem{przym}
T.Przymusinski, The existence of $Q$-sets is
equivalent to the existence of strong $Q$-sets,
Proceedings of the American Mathematical Society, 79(1980), 626-628.
Cited on page:
17
\bibitem{anal}
C.A.Rogers
et al, editors, {\bf Analytic Sets}, Academic Press, 1980.
Cited on page:
78
\bibitem{roth}
F.Rothberger, On some problems of Hausdorff and of Sierpi\'{n}ski,
Fundamenta Mathematicae, 35(1948), 29-46.
Cited on page:
16
\bibitem{sack}
G.Sacks, {\bf Higher Recursion Theory}, Springer-Verlag, 1990.
Cited on page:
141
\bibitem{sami}
R.Sami, On $\Sigma_1^1$ equivalence relations with Borel
classes of bounded rank,
Journal of Symbolic Logic, 49(1984), 1273-1283.
Cited on page:
129
\bibitem{shelah}
S. Shelah, On co-$\kappa $-Souslin relations,
Israel Journal of Mathematics, 47(1984), 139-153.
Cited on page:
129
\bibitem{shoen}
J.Shoenfield, The problem of predicativity, Essays on the foundations
of mathematics, Magnes press, Hebrew University, Jerusalem, 1961,
132-139.
Cited on page:
86
87
\bibitem{sierp1928}
W.Sierpi\'{n}ski, {\bf Introduction to general topology},
University of Toronto Press, 1934, translated from original
Polish version of 1928.
Cited on page:
3
\bibitem{sikor}
R. Sikorski, {\bf Boolean Algebras}, Springer-Verlag New York,
1969, 3rd edition.
Cited on page:
33
35
\bibitem{silver}
J.Silver, Counting the number of equivalence classes of Borel
and coanalytic equivalence relations,
Annals of Mathematical Logic, 18(1980), 1-28.
Cited on page:
27
113
\bibitem{Solecki}
S.Solecki, Covering analytic sets by families of closed sets,
Covering analytic sets by families of closed sets,
Journal of Symbolic Logic, 59(1994), 1022-1031.
Cited on page:
123
\bibitem{solov}
R.M.Solovay, On the cardinality of $\Sigma^1_2$ sets of reals, in
{\bf Foundations of Mathematics}, Biulof et al eds., Springer-Verlag
(1969), 58-73.
Cited on page:
88
95
\bibitem{solten}
R.M.Solovay, S.Tennenbaum, Iterated Cohen extensions and Souslin's problem,
Annals of Mathematics, 94(1971), 201-245.
Cited on page:
40
\bibitem{spector}
C.Spector, Hyperarithmetical quantifiers, Fundamenta Mathematicae,
48(1960), 313-320.
Cited on page:
109
\bibitem{marcz}
E.Szpilrajn, Sur l'\'{e}quivence des suites d'ensembles et
l'\'{e}quivence des fonctions, Fundamenta Mathematicae, 26(1936),
302-326.
Cited on page:
13
\bibitem{marcz2}
E.Szpilrajn, The characteristic function of a sequence of sets
and some of its applications, Fundamenta Mathematicae, 31(1938),
207-223.
Cited on page:
13
\bibitem{steel}
J.R.Steel, Forcing with tagged trees,
Annals of Mathematical Logic, 15(1978), 55-74.
Cited on page:
27
\bibitem{stern}
J.Stern,
Perfect set theorems for analytic and coanalytic equivalence relations,
in {\bf Logic Colloquium '77} ed by Macintyre et al,
North Holland, 1978, 277-284.
Cited on page:
129
\bibitem{stern2}
J. Stern,
Effective partitions of the real line into Borel sets of bounded rank,
Annals of Mathematical Logic, 18 (1980), 29-60.
Cited on page:
129
\bibitem{tod}
S.Todorcevic, Two examples of Borel partially ordered sets with the
countable chain condition, Proceedings of the American Mathematical
Society, 112(1991), 1125-1128.
Cited on page:
124
\bibitem{will}
S.Williard, {\bf General Topology}, Addison-Wesley, 1970.
Cited on page:
6
\end{thebibliography}
\twocolumn
\pagestyle{myheadings}
\markboth{Index}{Index}
\markright{Index}
\addtocontents{toc}{ }
\addtocontents{toc}{Index \hfill \thepage}
\addtocontents{toc}{ }
\indexentry{$(\sum_{\alpha <\omega _1}\poset_\alpha ) *\name{\posetq}$}{45}
\indexentry{$2^{\omega }$}{1}
\indexentry{$A_\alpha $}{53}
\indexentry{$A_{<\alpha }$}{53}
\indexentry{$F/I$}{33}
\indexentry{$F_\sigma $}{5}
\indexentry{$G_\delta $}{5}
\indexentry{$I$-Luzin set}{35}
\indexentry{$L_{\infty }(P_\alpha : \alpha <\kappa )$}{26}
\indexentry{$P(T,q)$}{130}
\indexentry{$Q_\alpha $}{49}
\indexentry{$S(T,q)$}{130}
\indexentry{$T\embed\hat{T}$}{92}
\indexentry{$T\leq_n T^\prime$}{52}
\indexentry{$T\strictembed\hat{T}$}{92}
\indexentry{$T^0$}{23}
\indexentry{$T^{>0}$}{23}
\indexentry{$T_\alpha $}{49}
\indexentry{$WF$}{125}
\indexentry{$WF_{<\alpha }$}{125}
\indexentry{$WO$}{113}
\indexentry{$[A]_I$}{33}
\indexentry{$[T]$}{22}
\indexentry{$[\omega ]^{\omega }$}{2}
\indexentry{$[s]$}{1}
\indexentry{$\Delta ^1_1$-codes}{109}
\indexentry{$\Delta ^1_2$ well-ordering}{82}
\indexentry{$\Delta _0$-formulas}{84}
\indexentry{$\Pi ^0_\alpha ({\rm hyp})$}{130}
\indexentry{$\Pi ^0_\alpha ({\rm semihyp})$}{137}
\indexentry{$\Pi ^1_1$ equivalence relations}{113}
\indexentry{$\Pi ^1_1$ singleton}{91}
\indexentry{$\Pi ^1_1$-Reduction}{107}
\indexentry{$\Pi ^1_1$-Reflection}{137}
\indexentry{$\Pi _1^0$}{78}
\indexentry{$\Pi _1^1$ on $\Pi _1^1$}{137}
\indexentry{$\Pi _\beta $-sentence}{26}
\indexentry{$\Sigma ^0_\alpha ({\rm semihyp})$}{137}
\indexentry{$\Sigma ^1_1$ equivalence relations}{125}
\indexentry{$\Sigma ^1_1$}{78}
\indexentry{$\Sigma ^1_1(x)$}{78}
\indexentry{$\Sigma ^1_2$}{82}
\indexentry{$\Sigma ^1_{2}=\Sigma ^{HC}_1$}{84}
\indexentry{$\Sigma _1$-formula}{84}
\indexentry{$\alpha $-code}{130}
\indexentry{$\alpha $-forcing}{23}
\indexentry{$\alpha $-topology}{139}
\indexentry{$\bdel0\alpha $-universal set}{133}
\indexentry{$\bdel0\alpha $}{4}
\indexentry{$\bdel0\alpha (F)$}{10}
\indexentry{$\bool^+$}{30}
\indexentry{$\bpi0\alpha $}{4}
\indexentry{$\bpi0\alpha (F)$}{10}
\indexentry{$\bpi11$}{78}
\indexentry{$\bpi12$}{98}
\indexentry{$\bsig0\alpha $}{4}
\indexentry{$\bsig0\alpha (F)$}{10}
\indexentry{$\bsig11$}{78}
\indexentry{$\bsig12$ equivalence relation}{129}
\indexentry{$\check{x}$}{16}
\indexentry{$\cl_\alpha (A)$}{139}
\indexentry{$\fin(X,\omega )$}{19}
\indexentry{$\fin(\aleph _\omega ,2)$}{75}
\indexentry{$\fin(\continuum^+,2)$}{40}
\indexentry{$\fin(\kappa ,2)$}{49}
\indexentry{$\hat{Q}_\alpha $}{60}
\indexentry{$\kappa $-Borel}{102}
\indexentry{$\kappa $-Souslin}{102}
\indexentry{$\kappa $-Souslin}{86}
\indexentry{$\mu $}{65}
\indexentry{$\name{U}_n$}{16}
\indexentry{$\omega ^{<\omega } $}{1}
\indexentry{$\omega ^{\omega }$}{1}
\indexentry{$\omega _1^{CK}$}{130}
\indexentry{$\ord(\bool)$}{29}
\indexentry{$\poset * \name{\posetq}$}{40}
\indexentry{$\poset(T)$}{54}
\indexentry{$\poset_\alpha$}{43}
\indexentry{$\posetq_\alpha $}{60}
\indexentry{$\sigma $-$\delta $-lattice}{6}
\indexentry{$\sigma $-field}{33}
\indexentry{$\sigma $-ideal}{33}
\indexentry{$\sim {B}\discretionary {-}{}{}$}{4}
\indexentry{$\sum_{\alpha <\omega _1}\poset_\alpha $}{45}
\indexentry{$m_\poset$}{76}
\indexentry{$s\concat n$}{1}
\indexentry{$s\subset t$}{92}
\indexentry{$x<_cy$}{82}
\indexentry{${\ pp}$}{17}
\indexentry{${\rm Borel}(F)$}{10}
\indexentry{${\rm Borel}(X)$}{4}
\indexentry{${\rm Borel}(X)/{\rm meager}(X)$}{48}
\indexentry{${\rm MA}_\kappa $}{38}
\indexentry{${\rm OR}$}{22}
\indexentry{${\rm cov}(I)$}{73}
\indexentry{${\rm cov}({\rm meager}(2^{\omega }))$}{73}
\indexentry{${\rm meager}(X)$}{49}
\indexentry{${\rm ord}(X)$}{8}
\indexentry{${\rm rank}(p)$}{43}
\indexentry{${\rm stone}(B)$}{33}
\indexentry{$|s|$}{1}
\indexentry{Aronszajn tree}{52}
\indexentry{Baire space}{1}
\indexentry{Borel metric space}{119}
\indexentry{Borel-Dilworth Theorem}{123}
\indexentry{Boundedness Theorem}{126}
\indexentry{Cantor space}{1}
\indexentry{Fusion}{52}
\indexentry{Gandy forcing}{113}
\indexentry{H$_{\gamma }$}{39}
\indexentry{HC}{84}
\indexentry{Kleene Separation Theorem}{104}
\indexentry{Louveau's Theorem}{130}
\indexentry{MA$_\kappa $(ctbl)}{73}
\indexentry{Mansfield-Solovay Theorem}{88}
\indexentry{Martin's Axiom}{16}
\indexentry{Martin-Solovay Theorem}{38}
\indexentry{Mostowski's Absoluteness}{80}
\indexentry{Normal form for $\Sigma ^1_1$}{80}
\indexentry{Q-sets}{17}
\indexentry{Sack's real model}{72}
\indexentry{Section Problem}{130}
\indexentry{Shoenfield Absoluteness}{87}
\indexentry{Sierpi\'{n}ski set}{65}
\indexentry{Silver forcing}{16}
\indexentry{Souslin-Luzin Separation}{102}
\indexentry{Spector-Gandy Theorem}{109}
\indexentry{V=L}{82}
\indexentry{ZFC$^*$}{81}
\indexentry{accumulation points}{60}
\indexentry{cBa}{28}
\indexentry{characteristic function}{13}
\indexentry{code for a hyperarithmetic set}{104}
\indexentry{collinear points}{121}
\indexentry{direct sum}{45}
\indexentry{field of sets}{10}
\indexentry{hereditarily countable sets}{84}
\indexentry{hereditary order}{59}
\indexentry{hyperarithmetic subsets}{104}
\indexentry{nice $\alpha $-tree}{22}
\indexentry{perfect set forcing}{72}
\indexentry{perfect set}{8}
\indexentry{perfect tree}{52}
\indexentry{prewellorderings}{91}
\indexentry{prewellordering}{107}
\indexentry{rank function}{22}
\indexentry{scale property}{90}
\indexentry{second countable}{1}
\indexentry{separable}{1}
\indexentry{separative}{28}
\indexentry{splitting node}{52}
\indexentry{super Luzin set}{49}
\indexentry{super-$I$-Luzin}{35}
\indexentry{switcheroo}{25}
\indexentry{tree embedding}{92}
\indexentry{tree}{22}
\indexentry{two step iteration}{39}
\indexentry{uniformization property}{90}
\indexentry{universal for $\bsig11$ sets}{79}
\indexentry{universal set}{7}
\indexentry{well-founded}{22}
\end{document}