% todo: could publish omega1-borel here
% list of open problems at the end

\documentclass[12pt]{article}
\usepackage{amssymb,latexsym,hyperref}


\def\pair(#1,#2){\la #1, #2 \ra}
\def\comb(#1,#2){ \left( \begin{array}{c} #1 \\ #2  \end{array} \right) }
\def\rmif{\mbox{ if }}

\def\supp{\mbox{supp}}
\def\concat{\hat{\phantom{aa}}}
\def\cn{\mbox{CN}}
\def\rank{\mbox{rank}}
\def\nn{\mathcal{N}}
\def\rr{\mathcal{R}}
\def\bool{\mbox{bool}}
\def\graph{\mbox{graph}}

\def\cof{\mbox{cof}}
\def\calc{\mathcal{C}}
\def\lam{\lambda}
\def\elemsub{\preceq}
\def\rank{\mbox{rank}}
\def\concat(#1){\hat{\phantom{a}}#1}
\def\continuum{{\mathfrak c}}
\def\Sig#1{\Sigma_#1}
\def\cantorspace{2^\omega}
\def\Intersect{\bigcap}
\def\Union{\bigcup}
\def\intersect{\cap}
\def\cross{\times}
\def\ep{\epsilon}
\def\aa{\mathcal{A}}
\def\al{\alpha}
\def\bb{\mathcal{B}}
\def\be{\beta}
\def\borel{{\rm Borel}}
  \mathchardef\wtilde="0365
\def\bde#1#2{\vtop{\hbox{${\bf\Delta}^{#1}_{#2}$} \kern-4pt  \hbox{\kern1pt$\wtilde$}\kern-6pt}}
\def\bpi#1#2{\vtop{\hbox{${\bf\Pi}^{#1}_{#2}$} \kern-4pt  \hbox{\kern1pt$\wtilde$}\kern-6pt}}
\def\bsi#1#2{\vtop{\hbox{${\bf\Sigma}^{#1}_{#2}$} \kern-4pt \hbox{\kern1pt$\wtilde$}\kern-6pt}}
\def\ccal{\mathcal{C}}
\def\conj{\mathop{\bigwedge}}
\def\cc{{\mathfrak c}}
\def\dd{\mathfrak{d}}
\def\dense{{\cal D}}
\def\de{\delta}
\def\diffeven{\mbox{Diffeven}}
\def\diffodd{\mbox{Diffodd}}
\def\disj{\mathop{\bigvee}}
\def\ff{\mathcal{F}}
\def\forces{{\;\Vdash}}
\def\ga{\gamma}
\def\gg{{\mathcal{G}}}
\def\hh{\mathcal{H}}
\def\ka{\kappa}
\def\la{\langle}
\def\name#1{\stackrel{\circ}{#1}}
\def\nam{{\mathcal N}}
\def\om{\omega}
\def\ord{{\rm ord}}
\def\poset{{\mathbb P}}
\def\pow{\mathcal{P}}
\def\proof{\par\noindent proof:\par}
\def\proves{\vdash}
\def\qed{\nopagebreak\par\noindent\nopagebreak$\Box$\par}
\def\rationals{{\mathbb Q}}
\def\ra{\rangle}
\def\reals{{\mathbb R}}
\def\res{\upharpoonright}
\def\rmand{\mbox{ and }}
\def\rmiff{\mbox{ iff }}
\def\rmor{\mbox{ or }}
\def\si{\sigma}
\def\sm{{\setminus}}
\def\ss{\mathfrak{s}_{mm}}
\def\starpi(#1){{\bf \Pi}^*_{#1}}
\def\starsi(#1){{\bf \Sigma}^*_{#1}}
\def\st{\;:\;} % such that
\def\su{\subseteq}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{thm}[theorem]{Theorem}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{question}[theorem]{Question}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{example}[theorem]{Example}
\newtheorem{define}[theorem]{Definition}

\begin{document}

\begin{flushright}
A.Miller\\
Spring 2014\\
last revised August 10, 2017\\
(still working on it)
\end{flushright}

\begin{center}
{\large Borel hierarchies}
\end{center}

These are lecture notes from a course I gave in the spring
semester of 2014\footnote{\url{http://www.math.wisc.edu/~miller/old/m873-14/}}.  
The following results are new:
\begin{itemize}
\item \ref{remark4.6} $\;$
It is consistent that the Borel subsets of the plane are
not contained in any bounded level of the $\si$-algebra generated
by the abstract rectangles.
\item \ref{bbmanswer} $\;$ It is consistent
that for some $\ka$ every family of size $\ka$ of sets of reals is included in
a countably generated $\si$-algebra but not necessarily at a
bounded level.
\item \ref{answer7.13} If $2^{<\cc}=\cc$ and there is a Borel
universal map, then
 there is a map $H:2^\om\times 2^\om\to 2^\om$ such that for every $\ka<\cc$ and $G:\ka\times\ka\to\ka$
 there are $x_\al\in 2^\om$ for $\al<\ka$ such that for all $\al,\be,\ga<\ka$
 $\;\;G(\al,\be)=\ga$ iff $H(x_\al,x_\be)=x_\ga$.
\item \ref{newunion} $\;$ CH implies that for any $\al_0$ with
$3\leq \al_0<\om_1$ there are $X_0,X_1\su 2^\om$ 
with $\ord(X_0)=\al_0=\ord(X_1)$ and $\ord(X_0\cup X_1)=\al_0+1$.
\end{itemize}
  
Also the proof of Theorem \ref{newproof} is new.   I have omitted
some of the results proved in lecture but only when the proof
I gave is identical to that found in the literature.

% The last section will??? contain a summary of many other results that
% I did not lecture on, as well as, some open ??? questions.


\tableofcontents

\section{Classical Results}

This section contains the Theorem of Lebesgue
which uses universal sets
and a diagonal argument to show that the length of the Borel hierarchy
is as long as possible, $\om_1$.  We also give some results
of Bing, Beldsoe, and Mauldin and of Rec{\l}aw which I think
of as generalizations of Lebesgue's Theorem.

First we review some standard terminology and results.
The Baire space is $\om^\om=\{x \;|\; x:\om\to\om\}$ where
$\om=\{0,1,2,\ldots\}$.  For $s\in \om^{<\om}=\bigcup_{n<\om} \om^n$
a finite sequence define a basic clopen set:
$$[s]=\{x\in\om^\om\;:\; s\su x\}$$
The Baire space is homeomorphic to the irrationals and is a zero
dimensional Polish space,
i.e., completely metrizable separable with a clopen basis.
One complete metric is $d(x,y)=\frac{1}{n}$ where $n$ is the
least with $x\res n \neq y\res n$.

The Cantor space $2^\om\su \om^\om$ is homeomorphic to the
middle thirds set
$$\{\sum_{n=0}^\infty \frac{2x(n)}3 \;:\; x\in 2^\om\}$$

\noindent The Borel hierarchy is described as follows:

\medskip
$\mbox{ open }= \bsi01 = G$

\medskip$\mbox{ closed }= \bpi01 = F$

\medskip$\bpi02 = G_\de =$ countable intersections of open sets

\medskip$\bsi02 = F_\si =$ countable unions of closed sets

\medskip$\bsi03 = G_{\de\si} =$ countable unions of $G_\de$ sets

\medskip$\bsi0\al=\{\;\bigcup_{n<\om} A_n \;:\; A_n\in \bpi0{<\al}\;\}$

\medskip$\bpi0\al=\{\;\bigcap_{n<\om} A_n \;:\; A_n\in \bsi0{<\al}\;\}$

\medskip $G_{\de\si}$, $G_{\de\si\de}$, \ldots, $\;\;\;\;F_{\si\de}$, 
$F_{\si\de\si}$ \ldots

\bigskip\noindent
The Borel sets are the smallest $\si$-algebra containing the open
sets.  In a metric space $F\su G_\de$ ($\bpi01\su\bpi02$), i.e., 
every closed set is
the countable intersection of open sets.\footnote{If $C$ is closed, then 
$C=\bigcap_n U_n$ where
$U_n=\{x\;:\; \exists y\in C\; d(x,y)<\frac1n\}$.}
It follows that in a metric space for $1\leq \al<\be$ that 
$$\bsi0\al\cup \bpi0\al\;\su\; \bsi0\be\cap \bpi0\be\;=\;^{def}\bde0\be$$

\begin{example}(Willard 1971 \cite{willard}) 
There are nice spaces in which closed sets are $G_{\de\si}$ but not
$G_\de$.
\end{example}
\proof
Suppose $(X,\tau)$
is a space for which closed sets are $G_\de$ and $G_{\de\si}\neq G_\de$.
Fix $A\in G_{\de\si}\sm G_\de$.  Let $\tau_A$ be the smallest topology
containing $\tau$ and the complement of $A$, $\sim A=^{def}X\sm A$.
Then the closed
sets of $\tau_A$ are a subset of $G_{\de\si}(\tau_A)$ but not
of $G_{\de}(\tau_A)$.

$U\in \tau_A$ iff there are $V,W\in\tau$ with $U=(V\cap \sim A)\cup W$.
$A$ is closed in $\tau_A$
but is not the countable intersection of $\tau_A$ open sets, else
$$A=\bigcap_{n<\om} (V_n\cap\sim A)\cup W_n$$ 
But then $A=\bigcap_{n<\om} W_n$, but $A$ is not $G_\de$.
\qed

The equation
$$\bigcup_n P_n \;\cap\; \bigcup_m Q_m\;=\; \bigcup_{n,m}\;P_n\cap Q_m$$
shows by induction that 
\begin{itemize}
\item $\bsi0\al$ is closed under finite intersections and
\item $\bpi0\al$ is closed under finite unions.
\end{itemize}
Another easy proposition is that for $f:X\to Y$ a continuous map:
\begin{itemize}
\item If $A\in\bsi0\al(Y)$, then 
$f^{-1}(A)\in\bsi0\al(X)$.
\item If $A\in\bpi0\al(Y)$, then 
$f^{-1}(A)\in\bpi0\al(X)$.
\end{itemize}

Note that $2^\om$ is naturally homeomorphic to  $2^\om\times 2^\om$ via
the map $x\mapsto ( y,z )$ where $y(n)=x(2n)$ and $z(n)=x(2n+1)$.
We use $x=\la y,z\ra$ to denote the pairing map.  Similarly
$(2^\om)^\om$ is homeomorphic to $2^\om$ via
$x=\la x_n : n<\om\ra$ where $x_n(m)=x(\la n,m\ra)$
and $\la n,m\ra = 2^n(2m+1)-1$ is a bijection between
$\om\times\om$ and $\om$.

\begin{theorem}\label{leb}
(Lebesgue 1905 see \cite{dstfor} Thm 2.5) For every countable $\alpha>0$ 
  $$\bsi0\alpha( 2^\om )\not=\bpi0\alpha( 2^\om ).$$
\end{theorem}

This follows from the existence of universal sets and a diagonal argument.


\bigskip\noindent {\bf Universal Sets Lemma.}
{\it  For every countable $\al>0$ there exists
$U\su 2^\om\times 2^\om$ which is $\bsi0\al$ and universal for
$\bsi0\al$-sets, i.e., for every $V\su 2^\om $ which is $\bsi0\al$ there
exists $x\in 2^\om$ such that $V=U_x=^{def}\{y\;:\; (x,y)\in U\}$.}

\proof
Note that $U\in \bsi0\al$ implies $U_x\in \bsi0\al$ for all $x\in 2^\om$.
To see this let
$f:2^\om \to 2^\om\times 2^\om$ be defined by
$f(y)=(x,y)$, then $U_x=f^{-1}(U)$.

\bigskip\noindent Case $\al=1$.

Let $\{C_n:n<\om\}$ list all clopen subsets of $2^\om$.  Define
$$(x,y)\in U\rmiff \exists n\; (x(n)=1\rmand y\in C_n).$$
Note that $U=\bigcup_{n<\om}(\{x:x(n)=1\}\times C_n)$.

\bigskip\noindent Case $\al>1$.

Let $\{\al_n:n<\om\}$ list with infinitely many
repetitions the nonzero elements of $\al$.
Let $U^{\al_n}$ be a universal $\bsi0\al_n$ set.
Define $U$ by
$$(x,y)\in U \rmiff \exists n \; (x_n,y)\notin  U^{\al_n}$$
Note that $\sim U^{\al_n}$ is a universal $\bpi0\al_n$ set.
For each fixed $n$ the set
$$\{(x,y)\;:\; (x_n,y)\in U^{\al_n}\}$$
is $\bsi0\al_n$ because it is the preimage of $U^{\al_n}$
under a continuous map, namely $(x,y)\mapsto (x_n,y)$.
Hence it is easy to verify that $U$ is a universal $\bsi0\al$
set.
\qed

\bigskip\noindent {\bf The Diagonal Argument}.
Suppose $U\su 2^\om \times 2^\om$ is a universal $\bsi0\al$
set.  Let
$$D=\{x\in 2^\om\;:\; (x,x)\notin U\}.$$
Then $D$ is $\bpi0\al$ because it is the continuous preimage
of $\sim U$ under the map $x\mapsto (x,x)$.  However
$D\neq U_x$ for any $x\in 2^\om$ so $D$ is not $\bsi0\al$.

This proves Theorem \ref{leb}.
\qed

Define $\ord(X)$ to the least ordinal such
that $\bsi0\al(X)=\borel(X)$.  Hence $\ord(2^\om)=\om_1$.

\begin{cor}
If $X$ is any topological space which contains a homeomorphic
copy of $2^\om$, then $\ord(X)=\om_1$.  More generally, if
$Y\su X$ is subspace, then $\ord(Y)\leq \ord(X)$.
\end{cor}
\proof
If $Y\su X$, then 
$$\bsi0\al(Y)=\{B\cap Y\;:\;B\in \bsi0\al(X)\}$$
and
$$ \borel(Y)=\{B\cap Y\;:\; B\in\borel(X)\}.$$
\qed

Suppose $\hh\su\pow(Y)$ define $\Sig\al(\hh)$ as follows:

\noindent $\Sig0(\hh)=\{\sim A\;:\; A\in\hh\}$ and for $\al>0$ 
$$\Sig\al(\hh)=\{\bigcup_{n<\om}\sim A \;:\; A_n\in \bigcup_{\be<\al}
\Sig\be(\hh)\}$$
We let $\borel(\hh)$ be the $\si$-algebra generated by $\hh$ and
let $\ord(\hh)$ be the least $\al$ with $\Sig\al(\hh)=\borel(\hh)$.

\begin{theorem} \label{bbm}
(Bing, Bledsoe, Mauldin \cite{BBM} also \cite{dstfor} Thm 3.2
\cite{survey} Thm 18) Suppose
$\hh\subseteq \pow( 2^\om )$ is a countable family such that
$\borel( 2^\om )\subseteq \borel(\hh)$.  Then $\ord(\hh)=\om_1$,
i.e., the $\si$-algebra generated by $\hh$ has $\om_1$ many levels.
\end{theorem}

To prove this theorem we will need the following two lemmas.
Given a countable $\hh\subseteq P(\cantorspace)$ let
$$\ff=\{C\cross A \;:\; C\subseteq \cantorspace\;\mbox{ is clopen}  \rmand A\in \hh \}
\;\;\su\;\;\pow(2^\om\times 2^\om).$$

\begin{lemma} (Universal sets)  \label{univ}
For each $\alpha$ with $1\leq\alpha<\omega_1$ there exists a set 
$U\in\Sigma_\alpha(\ff)$ which is universal for $\Sigma_\alpha(\hh)$ sets,
i.e., for every $A\in\Sigma_\alpha(\hh)$, there exists $x\in\cantorspace$
such that $A=\{y: (x,y)\in U\}$.
\end{lemma}
\proof

For $\alpha=1$:  Let $\hh=\{A_n:n\in\omega\}$ let
$$U=\Union_{n\in\omega}\{x: x(n)=1\}\cross (\cantorspace\setminus A_n).$$

For $\alpha>1$:  Let $x\mapsto \langle x_n:n\in\omega\rangle$ be
a nice recursive coding taking
$\cantorspace\rightarrow(\cantorspace)^\omega$.  Let $\beta_n$ for
$n\in\omega$ be cofinal in $\alpha$, and $U_n\in\Sigma_{\beta_n}(\ff)$
be universal for $\Sigma_{\beta_n}(\hh)$ sets.   Define
$U_n^{\prime}$ by $(x,y)\in U_n^{\prime}$ iff $(x_n,y)\in U_n$.
It is easy to check that $U_n^\prime$ is also
$\Sigma_{\beta_n}(\ff)$ and universal for $\Sigma_{\beta_n}(\hh)$.
But now taking
$$U=\Union_{n\in\omega}(\cantorspace\setminus U_n^\prime)$$
gives us a set in
$\Sigma_\alpha(\ff)$ which is universal for $\Sigma_\alpha(\hh)$ sets.
\qed

\begin{lemma} (Diagonalization) \label{diag}
Suppose
that every clopen set is in Borel($\hh$).
Then for every $B\in$Borel($\ff$) the set $\{x:(x,x)\in B\}$
is in Borel($\hh$).
\end{lemma}
\proof
For $B=C\cross A$ where $A\in \hh$ and $C\subseteq \cantorspace$ is clopen,
note that $$\{x:(x,x)\in B\}=C\intersect A.$$   Since by assumption
$C\in$Borel($\hh$), we have the lemma for elements of $\ff$.
To do Borel($\ff$) is an easy induction.
\qed

Now we give a proof of Theorem \ref{bbm}.  Suppose
Borel($\hh)=\Sigma_\alpha(\hh)$. By Lemma \ref{univ} there exist
$U$ in Borel($\ff$) which is universal for $\Sigma_\alpha(\hh)$
and hence Borel($\hh$). By Lemma \ref{diag} the set
$$D=\{x:(x,x)\notin U\}$$
is in Borel($\hh$).  But this means that
for some $x$ that $D=\{y:(x,y)\in U\}$.  But then
$x\in D$ iff $x\notin D$.
\qed

\begin{theorem}\label{rec}
(Rec{\l}aw 1993 see \cite{dstfor} Thm 3.5 \cite{survey} Thm 17)
If $X$ is a second countable space
and $X$ can be mapped continuously onto any
space containing $2^\om$,
then $\ord(X)=\omega_1$.
\end{theorem}
\proof
By going to a subspace of $X$ we may
that there is an $f:X\rightarrow \cantorspace$ which is one-to-one, 
onto, and continuous.
Let $\calc$ be a countable open basis for $X$ containing
the pre-images under $f$ of the clopen subsets of $2^\om$. 
Let
  $$\hh=\{f(C)\;:\; C\in\cal C\}.$$
Since it is clear
that $\hh$ contains all clopen sets, by Theorem \ref{bbm}, the
$\ord(\hh)=\omega_1$.  But the map $f$ takes the Borel hierarchy
of $X$ directly over to the hierarchy on Borel($\hh$), so $\ord(X)=\omega_1$.
\qed

\begin{remark}
Rec{\l}aw's result is also true, $\ord(X)=\om_1$, if we only assume that 
there is a Borel map onto map $f:X\to 2^\om$.
\end{remark}

To see this let $\cal C$ be a countable open basis for $X$ and
let $\cal B$ be the pre-images under $f$ of the clopen subsets of $2^\om$.
Let ${\cal G} ={\cal C}\cup {\cal B}$ and
$\hh=\{f(C)\;:\; C\in{\cal G}\}$.  Then $\ord(\hh)=\om_1$ by Theorem \ref{bbm}.
And so $\ord({\cal G})=\om_1$.  This means that $\ord(X)=\om_1$, since
$\borel({\cal G})=\borel(X)$ and $\bsi01(X)\su \Sig1({\cal G})$ implies
$\ord({\cal G})\leq\ord(X)$.  To see this note that if $\al=\ord(X)$, then
$$\borel({\cal G})=\borel(X)=\bsi0\al(X)\su\Sig\al({\cal G})\su 
\borel({\cal G}).$$

An extension of Rec{\l}aw's result to Souslin (operation A) sets
appears in Miller \cite{proj}.

\begin{remark}
It is relatively consistent
to have $X,Y\su 2^\om$ and $f:X\to Y$ continuous,
one-to-one, and onto such that $\ord(X)=2$ and $\ord(Y)=3$.
\end{remark}

\proof
To see this note that 
it is relatively consistent to have a $Q$-set $H$ of size
$\om_1$ which is concentrated
on a countable set $E$ (Fleissner and Miller \cite{qsets}).
Let $Y=H\cup E=\{y_\al:\al<\om_1\}$ and $H=\{x_\al:\al<\om_1\}$
be one-to-one enumerations.  
Put $X=\{\la x_\al,y_\al\ra:\al<\om_1\}$
and let $f$ be projection onto the second coordinate, i.e., $f(\la x,y\ra)=y$.
$X$ is a $Q$-set so has order 2 and it easy to check that $Y$ has order 3.
\qed

%??? maybe put in some more remarks open questions.  Maybe should
%check if Luzin set of size omega1 is there and hence Y's of
%all borel orders.???

In the iterated Sack real model the continuum is $\om_2$ and
for every $X\su 2^\om$ of size $\om_2$ there is a continuous
onto map $f:X\to 2^\om$ (see Miller \cite{map}) and hence
$\ord(X)=\om_1$.  So in the Sacks real model every set of reals
of size continuum has order $\om_1$.

\begin{cor}
If $X$ is separable, metric, but not zero-dimensional,
then $\ord(X)=\om_1$.
\end{cor}

\proof
Suppose $\ord(X)<\om_1$.  Let $d$ be any metric on $X$ and
$x\in X$ arbitrary.  There must be arbitrarily small
$\ep>0$ such that there is no $y\in X$ with $d(x,y)=\ep$.
Otherwise the map $y\mapsto d(x,y)$ has a nontrivial interval
in its image.
\qed

Any zero-dimensional separable metric space is homeomorphic
to a subspace of $2^\om$.  See Kechris \cite{kechris} page 38.


\section{The \texorpdfstring{$\om_1$}{omega-1}-Borel hierarchy}

\bigskip\noindent
Define the levels of the
$\om_1$-Borel hierarchy of subsets of $2^\om$ as follows:

\begin{enumerate}
\item $\starsi(0)=\starpi(0)=$ clopen subsets of $2^\om$
\item $\starsi(\al)=\{\bigcup_{\be<\om_1}A_\be\st (A_\be:\be<\om_1)\in
(\starpi(<\al))^{\om_1}\}$
\item $\starpi(\al)=\{2^\om\sm A \st A\in \starsi(\al)\}$
\item  $\starpi(<\al)=\bigcup_{\be<\al}\starpi(\be)$
$\;\;\;\;\starsi(<\al)=\bigcup_{\be<\al}\starsi(\be)$
\end{enumerate}

\noindent The length of this hierarchy is
the smallest $\al\geq 1$ such that
$$\starpi(\al)=\starsi(\al).$$

\begin{theorem} (Miller \cite{omega1}) \label{ma-hier}
(MA$_{\om_1}$)  $\starpi(\al)\neq\starsi(\al)$ for every $\al<\om_2$.
\end{theorem}

We prove this using the following two lemmas.  A well-known consequence
of MA$_{\om_1}$ is that every subset $Q\su 2^\om$
of size $\om_1$ is a
Q-set, i.e., for every subset $X\su Q$ there is a
$G_\de$ set $G\su 2^\om$ with $G\cap Q=X$ 
(see Fleissner and Miller \cite{qsets}).

\begin{lemma}\label{qset} Suppose there exists a Q-set
of size $\om_1$. Then
there exists an onto map $F:2^\om\to 2^{\om_1}$ such
for every subbasic clopen set $C\su 2^{\om_1}$
the set $F^{-1}(C)$ is either $G_\de$ or $F_\si$.
\end{lemma}
\proof
Fix $Q=\{u_\al\in 2^\om\st\al<\om_1\}$ a Q-set.
Let $G\su 2^\om\times 2^\om$ be a universal
$G_\de$ set, i.e., $G$ is $G_\de$ and for every $G_\de$ set
$H\su 2^\om$ there exists $x\in 2^\om$ with $G_x=H$.
Define $F$ as follows, given $x\in 2^\om$ let
$$F(x)(\alpha)=1 \rmiff  u_\al\in G_x $$
If $C$ is a subbasic clopen set, then for some $\al$ and $i=0$ or $i=1$
$$C_{\al,i}=\{p\in 2^{\om_1}\st p(\al)=i\}.$$
Then for $i=1$
$$F^{-1}(C_{\al,1})=\{x\st u_\al\in G_x \}$$
which is a $G_\de$  set.  
Since $C_{\al,0}$ is the complement of $C_{\al,1}$ we have that
$F^{-1}(C_{\al,0})$ is an $F_{\si}$-set

Finally, we note that since $Q$ is a Q-set, i.e., every
subset is a relative $G_\de$, it follows that $F$ is onto.
\qed

The next Lemma is true without any additional
assumptions beyond ZFC.  Its proof is a generalization
of Lebesgue's 1905 proof
(see Kechris \cite{kechris} p.168) for the standard Borel hierarchy.

\begin{lemma}\label{univstar}
For any $\al$ with $0<\al<\om_2$ there exists a $\starsi(\al)$ set
$U\su 2^{\om_1}\times 2^\om$ which is universal for
$\starsi(\al)$ subsets of $2^\om$, i.e., for any $Q\su 2^\om$ which
is $\starsi(\al)$ there exists $p\in 2^{\om_1}$ with
$U_p=Q$.  Similarly, there is a universal $\starpi(\al)$ set.
\end{lemma}
\proof
The proof is by induction on $\al$.  Note that the complement
of a universal $\starsi(\al)$ set is a universal $\starpi(\al)$-set.

For $\al=1$, $\starsi(\al)$ is just the open sets. There is a
universal open set $V\su 2^\om\times 2^\om$.  Put
$$U=\{(p,x)\in 2^{\om_1}\times 2^\om\st (p\res \om,x)\in V\}$$

For $\al$ such that $2\leq \al<\om_2$ proceed as follows.
Let $(\de_\be<\al:\be<\om_1)$ have
the property that for every $\ga<\al$ there are $\om_1$  many
$\de_\be \geq \ga$.  It follows that for every $\starsi(\al)$
set $Q\su 2^\om$ there is
$(Q_\be\in \starpi(\de_\be)\st \be<\om_1)$ with
$$Q=\bigcup_{\be<\om_1}Q_\be.$$
By induction, there are
$U_\be\su 2^{\om_1}\times 2^\om$ universal $\starpi(\de_\be)$
sets.  Let $a:\om_1\times\om_1\to\om_1$ be a bijection.
For each $\be$ define
$$\pi_\be: 2^{\om_1}\times 2^\om\to  2^{\om_1}\times 2^\om,\;\;
(p,x)\mapsto (q,x)$$
where $q(\al)=p(a(\be,\al))$.
Put
$$U=\bigcup_{\be<\om_1}\pi_\be^{-1}(U_\be)$$
then $U$ will be a universal $\starsi(\al)$ set.
\qed

Now we prove Theorem \ref{ma-hier}.  Suppose for contradiction, that
every $\om_1$-Borel set is $\starsi(\al)$ for some fixed
$\al<\om_2$.  Let $U\su 2^{\om_1}\times 2^\om$ be a universal
$\starsi(\al)$ and define
$$V=\{(x,y)\in 2^\om\times 2^\om\st (F(x),y)\in U\}.$$
Then $V$ is an $\om_1$-Borel set (although not necessarily at
the $\starsi(\al)$) because the preimage of any
clopen box $C\times D$ is $\om_1$-Borel by Lemma \ref{qset}.
Define
$$D=\{x:(x,x)\notin V\}.$$
But then $D$ is $\om_1$-Borel but not $\starsi(\al)$.  We see
this by the usual
diagonal argument that if $D=U_p$, then since $F$ is onto
there would be $x\in 2^\om$ such that $F(x)=p$ but then
$$x\in D \rmiff (F(x),x)\notin U \rmiff x\notin U_p
\rmiff x\notin D.$$
\qed

\begin{remark}
In the Cohen real model this hierarchy has order either
$\om_1+1$ or $\om_1+2$, I am not sure which.
\end{remark}

\begin{remark}
Note that in the proof $V\su 2^\om\times 2^\om$ is a
$\starsi(2+\al)$-set, since the preimage of a clopen set
under $F$ is ${\bf\Delta}_3^0$.  Hence for levels $\al\geq\om$
the set $V$ is a $\starsi(\al)$ set which is universal 
for $\starsi(\al)$ sets.
\end{remark}

\begin{remark}
Our result easily generalizes to show that MA implies
that for any $\ka$ a cardinal with $\om\leq \ka <|2^\om|$ the
$\ka$-Borel hierarchy has length $\ka^+$.  This implies 
that assuming MA for any $\ka_1<\ka_2$ there are $\ka_2$-Borel sets
which are not $\ka_1$-Borel.\footnote{Since $\ka_2$-Borel sets at level
$\ka_1^+$ or higher cannot be $\ka_1$-Borel.}
It is also true for the Cohen real model that
for $\om\leq \ka_1<\ka_2<|2^\om|$ that there are $\ka_2$-Borel sets
which are not $\ka_1$-Borel.
\end{remark}

\begin{prop} (\cite{omega1})
If $\pow(2^\om)=\om_1$-Borel, then $\pow(2^\om)=\starsi(\al)$
for some $\al<\om_2$.
\end{prop}

\proof
Suppose not and let $P_\al$ for $\al<\om_2$ be pairwise
disjoint homeomorphic copies of $2^\om$.  For each
$\al$ let $A_\al\su P_\al$ be such that $A_\al\notin\starsi(\al)$.
Then $$A=^{def}\bigcup_{\al<\om_2}A_\al$$ is not $\om_1$-Borel.
\qed

Steprans \cite{steprans} showed that it is relatively
consistent with ZFC that
$$\starpi(3)=\starsi(3)=\pow(2^\om)\rmand \starpi(2)\neq\starsi(2)$$
and the continuum is $\aleph_{\om_1}$.
Carlson \cite{carlson} showed:



\begin{theorem}
(Carlson) If every subset of $2^\om$ is $\om_1$-Borel, then the cofinality
of the continuum must be $\om_1$.
\end{theorem}
\proof
Let $B_\al\su 2^\om$ for $\al<\cc$ list all (ordinary) Borel sets.
Let $X_\al\in[2^\om]^\om$ for $\al<\cc$ be a family of pairwise disjoint
infinite countable sets.  For each $\al$ choose $Z_\al\su X_\al$ such
that $B_\be\cap X_\al\neq Z_\al$ for every $\be<\al<\cc$.   Put
$Z=\bigcup_{\al<\cc}Z_\al$.  We claim that if $\cof(\cc)>\om_1$ then
$Z$ is not $\om_1$-Borel.  This will follow easily from the following

\par\bigskip\noindent {\bf Claim}.  For any $C\su 2^\om$ an $\om_1$-Borel
set, there are (ordinary) Borel sets $C_\al$ for $\al<\om_1$ such that for
any $x\in 2^\om$ there is a closed unbounded $Q\su\om_1$ such 
that for every $\al\in Q$  ($x\in C$ iff $x\in C_\al$).

\proof
We code $\om_1$-Borel sets with well-founded trees.
For  $T\su \om_1^{<\om}$ a well-founded tree let $T^*$ be
the rank zero or terminal nodes of $T$.  To simplify matters
assume that for every $s\in T\sm T^*$ all immediate
extensions of $s$, i.e., $s\concat(\al)$,  are in $T$.
Let $\calc$ be the clopen subsets of $2^\om$.
Given $c:T^*\to \calc$
define $H(s,(T,c))\su 2^\om$ for $s\in T$ by the rank of $s$.

\begin{itemize}
\item $H(s,(T,c))=c(s)$ for $s\in T^*$ and otherwise
\item $H(s,(T,c))=\bigcap_{\al<\om_1}\sim H(s\concat(\al),(T,c))$
\end{itemize}

Now let $C=H(\la\ra,(T,c))$.  For any
$\al<\om_1$ let $T_\al=\al^{<\om}\cap T$, $c_\al=c\res T_\al^*$,
and $C_\al=H(\la\ra,(T_\al,c_\al))$.  Since $\al$ is countable
$C_\al$ is an ordinary Borel set.  Consider any $x\in 2^\om$.
Let $\ka$ be a large enough regular cardinal.  Construct a
continuous $\om_1$ chain $M_\al\elemsub H_\ka$ of countable elementary
substructures satisfying:
\begin{enumerate}
\item $(T,c)\in M_0$ and $x\in M_0$,
\item $M_\al\in M_{\al+1}$
\item $M_\lam=\bigcup_{\al<\lam} M_\al$ for $\lam<\om_1$ limit.
\end{enumerate}
Then automatically $Q=\{M_\be\cap\om_1:\be<\om_1\}$ will be a closed
unbounded set.  Now if $\al=M_\be\cap\om_1$.  Since $(T,c)$ and $x$
are both in $M_\be$ it is easy to see by induction on rank
that for any $s\in T_\al$ that 
$$x\in H(s,(T_\al,c_\al)) \rmiff
x\in H(s,(T,c)).$$

This proves the Claim.

To prove the Theorem suppose for contradiction that $Z=C$ where
$C$ is $\om_1$-Borel and let
$(C_\al:\al<\om_1)$ be given by the Claim.  
If the cofinality of $\cc$ is greater $\om_1$ then for some
$\be<\cc$ we have that $\{C_\al:\al<\om_1\}\su \{B_\al:\al<\be\}$.
But $Z_\be\neq X_\be \cap C_\al$ for every $\al<\om_1$ which is
a contradiction.
\qed





\section{The order of a separable metric space}

\begin{theorem} \label{mainthm}
(Miller \cite{hier} Thm 22) It is relatively consistent
with ZFC that $ord(X)=\om_1$ for all uncountable $X\su 2^\om$.
\end{theorem}

It also consistent with any cardinal arithmetic that for every 
$\al$ with $2\leq\al\leq\om_1$ there is an uncountable
$X\su 2^\om$ with $\ord(X)=\al$.  One can also have model
where these orders are precisely the interval $[\al_0+1,\om_1]$.

The model for this theorem is the $\om_2$ finite support iteration
of the direct sum $\poset$ of $\Pi_\al$-forcings for $\al<\om_1$.

\begin{define} Nice $\al$ tree. \label{nicetree}
For $2\leq\al<\om_1$ we define $T\su\om^{<\om}$ to be a nice
$\al$-tree iff
\begin{enumerate}
\item  it is well-founded tree of rank $\al$, i.e., $\rank_T(\la\ra)=\al$
\item for any $s\in T$ with $\rank_T(s)>0$ we have that
$s\concat(n)\in T$ for all $n<\om$
\item if $\rank_T(s)=\be+1$, then $\rank_T(s\concat(n))=\be$ for all $n$
\item if $\rank_T(s)=\lambda$ a limit ordinal, then for
any $\be<\lambda$ there are at most finitely many $n$ with 
$\rank_T(s\concat(n))\leq \be$.
\end{enumerate} 
\end{define}

\begin{define}\label{defpialpha}
Fix a nice $\al$-tree $T$, let $T^*$ be the terminal nodes of
$T$, i.e., those of rank zero, and let $T^+=T\sm T^*$.
$\Pi_\al$-forcing is the poset
$\poset_\al$ defined as follows:
$p\in\poset_\al$ iff there are finite $p_0\su T^*\cross 2^{<\om}$
and $p_1\su T^+\cross 2^{\om}$ such that $p=p_0\cup p_1$
and $p_0$ is the graph of a partial function and they are
consistent.  Consistency means that 
\begin{itemize}
\item if $(s,x),(s\concat(n),y)\in p_1$ then $x\neq y$ and
\item if $(s,x)\in p_1$ and $(s\concat(n),t)\in p_0$, then $x\notin [t]$.
\end{itemize}
\end{define}

We think of our conditions as attaching elements of $2^\om$ to nodes
of the tree $T$ subject to the condition that no $x$ is
attached to immediately adjacent nodes, i.e., 
$s$ and $s\concat(n)$ are immediately adjacent.
We think of $(s\concat(n),t)\in p_0$ (or equivalently
$p_0(s\concat(n))=t$ since it is a partial function)
as attaching all elements of the clopen
set $[t]=\{x\in 2^\om\;:\; t\su x\}$ 
to the terminal node $s\concat(n)\in T^*$.

\begin{lemma} For any countable ordinal $\al_0$, 
$\;\Pi_{\al_0}$-forcing $\poset_{\al_0}$ has the countable chain condition.
\end{lemma}
\proof
Suppose $A$ is uncountable antichain.  Since there are only countably
many different $p_0$ without loss we may assume that there exists
$r$ such that $p_0=r$ for all $p\in A$.
Consequently for $p,q\in A$
the only thing that can keep $p\cup q$ from being a condition is that
there must be an $x\in 2^\om$ and an $s,s\concat(n)\in T^+$ 
such that
$$(s,x),(s\concat(n),x)\in p\cup q.$$
But now for each $p\in A$ let $H_p:X\to [T^+]^{<\omega}$ be
the finite partial function defined by
$$H_p(x)=\{s\in T^+: (s,x)\in p_1\}$$
where $X=\{x:\exists s\in T^+ \; (s,x)\in p_1\}$.
Then $\{H_p:p\in A\}$ is an uncountable antichain in the order
of finite partial functions from $2^\om$ to $[T^+]^{<\omega}$.
But this is impossible.
\qed
It is easy to see that it has property K, in fact, it is $\si$-centered,
so ccc productive.   It follows that
the direct sum 
$$\poset=^{def}\sum\{\poset_{\al+1}\;\;:\;\;2\leq \al<\om_1\}$$
also has the countable chain condition.

To obtain our model for Theorem \ref{mainthm} start with a countable
transitive model of ZFC, $M$, and do a finite support iteration
of $\poset$ of length $\om_2$, denoted
$\poset^{\om_2}$.   We let $\poset^\al$ be the
iteration of $\poset$ up to length $\al$.

Fix $T$ a nice $\al$-tree for some $\al$.
Given $G$ $\poset_\al$-generic over $M$, for each $s\in T$ define
$U_s^G\su 2^\om$.  For $s\in T^*$ define $U_s^G=[t]$ if there
exists $p\in G$ such that $p_0(s)=t$.  Note that by genericity such
a $t$ will always exist, i.e., for any $q$ there exists $p\leq q$
such that $s$ is in the domain of $p$.  For $s\in T^+$ define
$$U_s^G=\bigcap_{n<\om}\sim U_{s\concat(n)}^G.$$
Note that $U_s^G$ is a $\bpi0\al$-set where $\al=\rank_T(s)$.

\begin{lemma}
For any $x\in 2^\om\cap M$ and $s\in T^+$ and $G$ $\poset_\al$-generic
over $M$
$$x\in U_s^G \rmiff\exists p\in G\;\; (s,x)\in p$$
\end{lemma}
\proof
To simplify notation write $(s,x)\in G$ instead of $\{(s,x)\}\in G$
or there exists $p\in G$ with $(s,x)\in p$.

Fix $x$ and $s$.
It is easy to see that the following sets are dense:

\par\noindent  (if $\rank_T(s)=1$) $D=\{p\in\poset_\al\;:\; (s,x)\in p \rmor \exists
n,t \;\; p_0(s\concat(n))=t \rmand x\in [t]\}$
\par\noindent  (if $\rank_T(s)>1$) $E=\{p\in\poset_\al\;:\; (s,x)\in p \rmor \exists
n \; (s\concat(n),x)\in p\}$

\noindent By definition
$x\in U_s^G$ iff $x\notin U_{s\concat(n)}^G$ for all $n$.

\noindent If $\rank_T(s)>1$, then by induction:

$x\notin U_{s\concat(n)}^G$ for all $n$ iff $(s\concat(n),x)\notin G$ for
all $n$ 

\noindent Since $E$ is dense:

$(s\concat(n),x)\notin G$ for all $n$  iff $(s,x)\in G$.

\noindent If $\rank_T(s)=1$, then

$x\notin U_{s\concat(n)}^G$ for all $n$ iff for all
$p\in G$ if $p_0(s\concat(n))=t$ then $x\notin [t]$.

\noindent Since $D$ is dense:

for all $p\in G$ if $p_0(s\concat(n))=t$ then $x\notin [t]$ iff $(s,x)\in G$.

\qed


\begin{define}
Canonical names.  For any poset $\poset$ the
canonical names $\cn(\poset)$ for an element of
$2^\om$ are defined as follows.  $\tau\in\cn(\poset)$ iff
there exists $(A_n^0,A_n^1\;:\;n<\om)$ such that $A_n^0\cup A_n^1\su\poset$ 
is a maximal antichain and
$$\tau=\{(p,\check{(n,i)})\;:\; n<\om, i<2, \rmand p\in A^i_n\}.$$
\end{define}


\begin{define} Nice conditions.
Let $T_\al$ for $2\leq \al<\om_1$ be the nice $\al$-trees used to
define $\Pi_{\al}$-forcing $\poset_\al$.  $\poset$
For $p\in\poset^\al$ we say the $p$ is nice iff
$p(0)\in\poset$ and
for all $\ga$ with $0<\ga<\al$ $p(\ga)$ is a 
name for a finite set $p_0\cup p_1$ where 
$$p_0:\bigcup_{2\leq\al<\om_1}(\{\al+1\}\times T^\star_{\al+1})\to 2^{<\om}$$ is a
 finite partial map
 and 
$$p_1\su \bigcup_{2\leq\al<\om_1}\{\al+1\}\times (T^+_{\al+1}\times \cn(\poset_\ga))$$
is finite.  For every $\tau$ in the range of $p_1$ there is 
a $t_\tau\in 2^{<\om}$ such that $p\res\ga\forces t_\tau\su\tau$
and for all $\al,s,n,\tau,\si,r$ 
\begin{enumerate}
\item if $(\al,(s,\tau)),(\al,(sn,\si))\in p_1$ then $t_\tau\perp t_\si$
\item if $(\al,(s,\tau))\in p_1$ and 
$p_0(\al,sn)=r\in 2^{<\om}$, then $t_\tau\perp r$.
\end{enumerate}
\end{define}

The nice conditions are dense so from now on we will assume all conditions
are nice.


\begin{define}
Rank.  Given $H\su 2^\om$, nice $p\in\poset^\al$, and $\tau\in\cn(\poset^\al)$ define
$\rank(p,H)$ and $\rank(\tau,H,p)$ by induction on $\al$.
\begin{enumerate}
\item For $\poset_\al$ ($\Pi_\al$-forcing), if $p=p_0\cup p_1\in\poset_\al$
then
$$\rank(p,H)=\max\{\rank_{T_\al}(s)\;:\; \exists x\in 2^\om\sm H\;\; (s,x)\in p_1\}$$
\item For $p\in\poset=\sum\{\poset_{\al+1}\;\;:\;\;2\leq \al<\om_1\}$
$$\rank(p,H)=\max\{\rank(p_\al,H)\;:\;\al<\om_1\}$$
\item For $\ga$ a limit ordinal and $p\in\poset^\ga$
$$\rank(p,H)=\max\{\rank(p\res\be, H)\;:\; \be<\ga\}.$$
\item For $\tau\in\cn(\poset^\ga)$ and $p\in\poset^\ga$,  $\rank(\tau,H,p)$
is the least $\be$ such that for every $n<\om$
$$Q=^{def}\{q\in\poset^\ga\;:\; q\perp p \rmor\rank(q,H)\leq\be\}
\mbox{ decides ``}\tau(n)=0\mbox{''}.$$   By which we mean
$$\{r\in\poset^\ga\;:\; \exists q\in Q\;\;\; r\leq q\rmand 
(q\forces\tau(n)=0 \rmor q\forces\tau(n)=1)\}$$
is dense in $\poset^\ga$. 

\item For $p\in\poset^\ga\star\name\poset$ 
$\;\;\;\;\; N_p(\ga)=\{\tau\;:\; \exists \al<\om_1\;\exists s\in 2^{<\om} \;(\al,(s,\tau)\in p(\ga)\}$
$$\rank(p,H)=\max\{\rank(p\res\ga,H),\rank(\tau,H,p\res\ga)\::\;\tau\in N_p(\ga)\}.$$
\end{enumerate}

\end{define}

A set of conditions $Q$ decides $\theta$ iff for every generic $G$ there
is a $q\in Q\cap G$ which forces $\theta$ or forces $\neg\theta$.


\begin{lemma} (ccc) \label{ccc} For any countable $P\su\poset^\ga$ and 
countable $N\su\cn(\poset^\ga)$ there is a countable $H\su 2^\om$ such that
$\rank(p,H)=0$ for every $p\in P$ and $\rank(\tau,H,1)=0$ for every $\tau\in Q$.
\end{lemma}
\proof
Let $\poset^\ga,P,Q\in\nn \elemsub H_\ka$ where $\nn$ is a countable elementary 
substructure of the hereditarily of cardinality less than $\ka$ sets for
some sufficiently large regular $\ka$.  Take 
$H=\nn\cap 2^\om$.  Then for any $p\in \nn\cap \poset^\ga$ and
$\tau\in\nn\cap\cn(\poset^\ga)$ we have that
$\rank(p,H)=0$ and $\rank(\tau,H,1)=0$. 
% ??? fill in more proof
\qed

\begin{define} $|\cdot|$ abbreviations for $\rank$.
For the next two lemmas (meet \ref{meet} and rank
\ref{rank}) we will
fix a countable $H\su 2^\om$ and use the abbreviations:
$$|p|=\rank(p,H) \;\;\; \rmand \;\;\;|\tau|(p)=\rank(\tau,H,p).$$ 
\end{define}

\begin{lemma}\label{meet}
(Meet lemma) If $G$ is $\poset^\al$-generic over $M$ and
$(q_i\in G:i<N)$ is a finite set with $|q_i|<\be$, then
there exists $q\in G$ with $|q|<\be$ and $q\leq q_i$ for
all $i<N$.
\end{lemma}
\proof

Case $\al=0$ hence $\poset^0=\poset$.  Let $q=\bigcup_{i<N}q_i$.  By definition
of generic filter $\exists p\in G$ with $p\leq q_i$ each $i<N$. 
Hence $p\leq q$ and so $q\in G$.

Case $\al$ a limit ordinal.   There exists $\al_0<\al$ with
$\supp(q_i)\su\al_0$ for $i<N$.  By induction hypothesis there
is $q\res\al_0\in G_{\al_0}$ with $q\res\al_0\leq q_i\res\al_0$ for
each $i<N$ and $|q\res\al_0|<\be$.  Let $q\res[\al_0,\al)$
be identically $1$.

Case $\al+1$ successor.  Suppose $q_i\in G_{\al+1}=G_\al \star G^\al$
which is $\poset_\al\star\name{\poset}$-generic.    Let $\Gamma\su G_\al$ be finite
so that $|r|<\be$ for all $r\in \Gamma$ and for any $\tau_1,\tau_2,s,n$ 
if $(s,\tau_1),(sn,\tau_2)\in \bigcup_{i<N}q_i(\al)$ then there exists
$r\in\Gamma$ such that $r\forces\tau_1\neq\tau_2$ and similarly,
if $(s,\tau)\in \bigcup_{i<N}q_i(\al)$ and $p_0^{q_i}(sn)=t$ for
some $i$, then there exists $r\in\Gamma$ such that $r\forces t\not\su\tau$.
By inductive hypothesis
there is $q\res\al\in G_\al$ with $|q\res\al|<\be$ and
$q\res\al\leq q_i\res\al$ for $i<N$ and $q\res\al\leq r$
for each $r\in\Gamma$.   Then $(q\res\al,\bigcup_{i<N}q_i(\al))$ satisfies
the Lemma.
\qed

\begin{lemma}\label{rank}
(Rank Lemma for $\poset^\al$) 
For every $\be\geq 1$ and $p\in\poset^\al$ there
exists $\hat{p}\in\poset^\al$ compatible with $p$,
$|\hat{p}|\leq\be$, and for every $q\in\poset^\al$ 
with $|q|<\be$, 
\par\noindent if $q,\hat{p}$ compatible, then
$q,{p}$ compatible.
\end{lemma}
\proof
The nontrivial case for this is $\poset^{\al+1}=\poset^\al * \poset$.

\medskip
Assume $p_0\in\poset^\al$, $|p_0|\leq \be$, 
$p_0\forces$``$ \name{C}\su 2^\om$ closed nonempty''
and for every $G$ $\poset^\al$-generic over $M$ with $p_0\in G$
for every $s\in 2^{<\om}$ if
$M[G]\models [s]\cap C=\emptyset$
then there is $q\in G$ with $|q|<\be$ such that 
$q\forces [s]\cap \name{C}=\emptyset$.  We prove the following two
Claims.

\bigskip\noindent Claim 1. For all $G$ $\poset^\al$-generic over $M$ with
$p_0\in G$ for every $s\in 2^{<\om}$ if
$M[G]\models [s]\cap C\neq \emptyset$
then there is $p\in G$ with $|p|\leq \be$ such that 
$p\forces [s]\cap \name{C}\neq\emptyset$.

\proof
Let $p_1\in G$ with $p_1\leq p_0$ and 
$p_1\forces [s]\cap \name{C}\neq\emptyset$.
Define
$$D_{p_1}=\{p\in\poset^\al\;:\; \exists p_2\;\;\; p\leq p_2 \leq p_1
\rmand p\leq\hat{p_2}\}$$
where $\hat{p_2}$ is the condition with $|\hat{p_2}|\leq \be$
given by the induction hypothesis of the Rank Lemma.
$D_{p_1}$ is dense beneath $p_1$ and so it meets $G$.  
Hence there exists $p_2$ with $p_2,\hat{p_2}$ both in $G$.  
Apply the Meet Lemma to get $p\in G$ with $|p|\leq \be$ and
$p\leq p_0$ and $p\leq\hat{p_2}$.   To see that $p$ works
let $G_0$ be $\poset^\al$ generic with $p\in G_0$.  Suppose for
contradiction that in $M[G_0]$ that $[s]\cap C=\emptyset$. Then
since $p_0\in G_0$ we have by assumption that for some $q\in G_0$
with $|q|<\be$ that $q\forces [s]\cap \name{C}=\emptyset$.
Since $\hat{p_2}\in G_0$ it is compatible with $q$.  But by
the definition of $\hat{p_2}$ as witness to Meet Lemma for $p_2$,
it follows that $q$ and $p_2$ are compatible.  But they
are not compatible since $p_2\leq p_1$ and 
$p_1\forces [s]\cap \name{C}\neq \emptyset$.
\qed

\bigskip\noindent Claim 2. Let $p_0\forces$``$\name{x}$ is the
lexicographically least element of $\name{C}$.  
Then $|\name{x}|\leq\be$.
\proof
Let $G$ be $\poset^\al$-generic over $M$ with $p_0\in G$.
Fix any $N<\om$ and let $x\res N=s$.  Hence
$[s]\cap C\neq\emptyset$. Furthermore, if $n_i$ for $i<k$ lists all $n<N$ with
$s(n)=1$ then $[t_i]\cap C=\emptyset$ where
$t_i(n_i)=0$ and $t_i\res n_i = s\res n_i$.  By Claim 1, there
is $p_1\in G$ with $|p_1|\leq\be$ such that 
$p_1\forces [s]\cap \name{C}\neq\emptyset$ and by assumption 
$q_i\in G$ for $i<k$ with
$|q_i|<\be$ such that $q_i\forces [t_i]\cap \name{C}=\emptyset$.  
By the Meet Lemma there is $p\in G$ with $|p|\leq \be$ which extends
$p_1$ and $q_i$ for $i<k$.   Then $p\forces \name{x}\in [s]$.  Since
$N$ and $G$ were arbitrary $|\name{x}|\leq\be$.
\qed

Given $\tau$ a $\poset^\al$-name for an element of $2^\om$, $G$ 
$\poset^\al$-generic over $M$, and $p\in\poset^\al$ (not necessarily
in $G$) let $C(\tau,p)\su 2^\om$ be the following closed set in
$M[G]$:
$$C(\tau,p)=\bigcap\{K_{\hat{\tau}}\;:\; \exists q\in G\;
|q|<\be,\; |\hat{\tau}|(q)<\be,
\rmand p\cup q\forces \tau\in K_{\hat{\tau}}\}$$

By $p\cup q\forces \theta$ we mean that
they are compatible and $r\forces \theta$ for every $r\leq p,q$.
Here $K\su 2^\om\times 2^\om$ is the standard universal closed
set and $K_x$ is the cross section.  

Given any $p\in\poset^\al$ let $p_0=\hat{p}$ be given by the inductive
hypothesis for the Rank Lemma and $\tau$ a name
for an element of $2^\om$.  Let $\name{C}$ be a name for
the closed set $C(\tau,p)$.  Then 

\bigskip\noindent Claim 3. $p_0,\name{C}$ satisfy the assumption
of Claim 1 and 2, namely
\begin{itemize}
\item[(a)] $p_0\forces \name{C}\su 2^\om$ is closed and nonempty
\item[(b)] for any $G$ $\poset^\al$-generic over $M$ with $p_0\in G$ for
any $s\in 2^{<\om}$ then if $[s]\cap C=\emptyset$ in $M[G]$, then
there is $q\in G$ with $|q|<\be$ such that
$q\forces [s]\cap \name{C}=\emptyset$.
\end{itemize}
\proof
We verify (b) first.  Suppose $[s]\cap C=\emptyset$ in $M[G]$.  By compactness
there are finitely many $q_i,\tau_i$ for $i<k$ with
$q_i\in G$, $|q_i|<\be$, $|\tau_i|(q_i)<\be$, each $q_i$ compatible with $p$,
$p\cup q_i\forces \tau\in K_{\tau_i}$, and 
$$\bigcap_{i<k}K_{\tau_i}\cap [s]=\emptyset$$
We claim that for some $N<\om$ for all $(x_i\in [\tau^G_i\res N]: i< k)$ that
$$\bigcap_{i<k}K_{x_i}\cap [s]=\emptyset$$
Otherwise for each $N$ choose $(x_i^N\in [\tau^G_i\res N]: i< k)$ and
$y_N\in [s]\bigcap_{i<k}K_{x_i^N}\cap [s]$.  But by compactness
a subsequence of the $y^N$ converges to some $y\in [s]$ and we
get $(y,\tau_i^G)\in K$ for each $i<k$.  

Let $s_i=\tau_i^G$.  By the Meet Lemma and the definition of
$|\tau_i|(q_i)<\be$ there is a $q\in G$ with $|q|<\be$ such that 
$q\forces \tau_i\res N=s_i$ for
all $i<k$.   It follows that $q\forces [s]\cap \name{C}=\emptyset$.

To prove (a) that $C$ is nonempty, suppose for contradiction that
for some $G$ $\poset^\al$-generic over $M$ with $p_0\in G$ we
have that $C$ is empty.  Then apply part (b) for $s=\la\ra$ the empty
sequence.  Then there is $q\in G$ with $|q|<\be$ and
$q\forces \name{C}=\emptyset$.  But $p_0=\hat{p}$ so
since $\hat{p},q$ are compatible, ${p},q$ are compatible.  But this
is impossible because $p\forces \tau\in \name{C}$ so it cannot
be empty.
\qed

Before getting to the proof of the Rank Lemma for $\poset^{\al+1}$ we
note some properties of the universal $\Pi^0_1$ set $K\su 2^\om\times 2^\om$.
First of all it is easier to think in terms of its complement
$U=\sim K$ which is universal for open sets.  Let $\{s_n:n<\om\}=2^{<\om}$
be a recursive listing and put 
$$y\in U_x \rmiff \exists n \;(x(n)=1 \rmand s_n\su y)$$
For each $n<\om$ there is a recursive level preserving map
$f:(2^\om)^n\to 2^\om$ such that for any sequence $(x_i\in 2^\om:i<n)$
if $f(x_i\in 2^\om:i<n)=y$ then $U_y=\cap_{i<n}U_{x_i}$ and
hence $K_y=\cup_{i<n}K_{x_i}$.  Simply define $f(\vec{x})=y$ by
$$ y(m)=1 \rmiff \;\;\forall i<n\;\exists l<m \;\; (x_i(l)=1 \rmand s_l\su s_m)$$
Note also that $(2^\om)^n$ is natural homeomorphic to $2^\om$ via a
recursive join operator and we use $\vec{x}$ to denote this element
of $2^\om$.

So given $p\in \poset^{\al+1}=\poset^\al * \name{\poset}$ and 
$\be\geq 1$ we let $p=(p\res \al, p(\al))$.  We may assume that
$p(\al)=p_0\cup p_1$ where $p_0:T^*\to 2^{<\om}$ is a finite partial
map and $p_1$ is a finite subset of $T^0\times\nam$ where $\nam$ are
$\poset^\al$ names for elements of $2^\om$ and 
$T^*$ are the terminal nodes of $T$ and $T^0$ are the nonterminal
nonroot nodes.  In addition we may assume for each $(s,\tau)\in p_1$
there is a $t\in 2^{<\om}$ such that
$p\forces t\su \tau$ and the $t$ witness that $p_1$ is a condition,
namely 
\begin{itemize}
\item if $(s,\tau_1),(sn,\tau_2)\in p_1$ then $t_1\perp t_2$
\item if $(s,\tau)\in p_1$ and $p_0(sn)=r$ then $t\perp r$
\end{itemize}
We write $p_1=p_1(\vec{\tau})$ where $\vec{\tau}$ is an $n$-tuple
list all $\tau$ mentioned in $p_1$.  To get $\hat{p}$ for the
Rank Lemma for $\poset^{\al+1}$ let
$$\hat{p}=^{def}(\;\widehat{p\res \al}\,,\, p_0\cup p_1(\vec{\tau}_{lex})\;)$$
where $\vec{\tau}_{lex}$ is a $\poset^\al$ name for the lexicographically
least element of $\name{C}(p\res\al,\vec{\tau})$.

By the claims $|\hat{p}|\leq \be$.   Note that
$C\su \prod_{i<n}[t_i]$ and so $\vec{\tau}_{lex}\in \prod_{i<n}[t_i]$
and so $\hat{p}$ and $p$ are compatible.  Finally we need to
show that if $|q|<\be$ and ${p},q$ incompatible, then $\hat{p},q$ incompatible.
Suppose $p,q$ incompatible.  If $p\res\al,\; q\res\al$ incompatible we
are done by inductive choice of $\widehat{p\res\al}$.  So we
may assume that they are compatible but
$$p\res\al\cup q\res\al\forces p(\al)\perp q(\al)$$
Let $q(\al)=q_0\cup q_1$ where the names occurring in
$q_1$ have rank $<\be$ with respect to $q\res\al$.
Now we detail how the incompatibility $p(\al)\perp q(\al)$ translates
into closed sets.   We may construct $\Sigma$ a finite set of
names for elements of $2^\om$ such that
\begin{itemize}
\item $|\rho|(q\res\al)<\be$ for each  $\rho\in\Sigma$
\item if $(s,\tau_i)\in p_1$ and $q_0(sn)=r$, then for
some $\rho\in\Sigma$ 
$$K_\rho=\{\vec{x}\;:\; x_i\in [r]\}$$
\item if $(s,\si)\in q_1$ and $p_0(sn)=r$, then
some $\rho\in \Sigma$ is name such that for any generic $G$
$$K_{\rho^G}=\left\{
\begin{array}{ll}
\emptyset & \mbox{ if } \si^G\notin [r]\\
(2^\om)^n & \mbox{ otherwise }
\end{array}\right.$$
\item if ($(s,\si)\in q_1$ and $(sn,\tau_i)\in p_1$) or
($(sn,\si)\in q_1$ and $(s,\tau_i)\in p_1$), then some
$\rho\in\Sigma$ is name such that for any generic $G$
$$K_{\rho^G}=\{\vec{x}\;:\; x_i=\si^G\}$$
\end{itemize}
We assume that all $\rho$ in $\Sigma$ arise from the above
requirements and let $\Sigma=\{\rho_i\;:\;i<N\}$.  Then
we have that
$$(p\res\al\cup q\res\al) \forces p(\al)\perp q(\al) \;\;\rmiff\;\;
(p\res\al\cup q\res\al)\forces \vec{\tau}\in \bigcup_{i<N}
K_{\rho_i}$$
Letting $\rho=f(\vec{\rho})$ we get that $|\rho|(q\res\al)<\be$
and
$$(\widehat{p\res\al}\cup q\res\al)\forces \vec{\tau}_{lex}\in
C(\vec{\tau},p\res\al)\su K_\rho=\bigcup_{i<N}
K_{\rho_i}.$$
It follows that $\hat{p},q$ are incompatible and the Rank-Lemma
successor case is proved.
\qed

Here is the main point of the Rank Lemma:

\begin{prop}\label{mainpoint}
Suppose $\tau\in\cn(\poset^{\om_2})$ with $|\tau|(1)=0$, $p\in\poset^{\om_2}$,
and $B(v)$ a $\bpi0\be$-set coded in the ground model $M$ such
that $p\forces B(\tau)$.  If $\hat{p}$ is given by the Rank Lemma
($\hat{p}$ compatible with $p$,
$|\hat{p}|\leq\be$, and for every $q\in\poset^{\om_2}$ 
with $|q|<\be$, if $q,\hat{p}$ compatible, then
$q,{p}$ compatible), then $\hat{p}\forces B(\tau)$.
\end{prop}
\proof

Case $\be=0$. This is true by the definition of $|\tau|(1)=0$.
% ??? more detail


Case $\be>0$.   Let $B(v)=\conj_{n<\om} B_n(v)$ where $B_n(v)$ $\bsi0{\beta_n}$
for some $\be_n<\be$.   If for contradiction $\hat{p}$ does not force $B(\tau)$, then
there exists $q\leq\hat{p}$ and $n<\om$ such that $q\forces \neg B_n$.
By induction there exists $\hat{q}$ compatible with $q$, $|\hat{q}|\leq\be_n$
and $\hat{q}\forces \neg B_n$.  Since $q$ extends $\hat{p}$ it follows
that $\hat{q},\hat{p}$ are compatible. Since $|\hat{q}|\leq\be_n<\be$ we have that
$\hat{q}$ is compatible with $p$.  This is a contradiction since
$p\forces B_n(\tau)$.
\qed

\begin{prop}
Suppose $G$ $\poset^{\om_1}$-generic over $M$.  Then for any $Y\in M$ and
$\al<\om_1^M$ if 
$M\models Y\su 2^\om \rmand |Y|=\om_1$,
then 
$$M[G]\models \forall \al<\om\; \forall V\in\bsi0\al \;\;\;V\cap Y 
\neq U^{G_0}_{\al,\langle\rangle}\cap Y.$$
Here $U^{G_0}_{\al,\langle\rangle}$ is the generic $\bpi0\al$ set added
by the first coordinate's $\Pi_\al$-forcing, namely 
$$U^{G_0}_{\al,\langle\rangle}=\{x\in 2^\om\cap M\;:\; \exists p\in G
\; (\al,(\langle\rangle,x))\in p(0)\}.$$
\end{prop}
\proof
Let $V$ be a universal $\bsi0\al$-set coded in $M$.
Suppose 
$$p_0\forces\forall y\in Y\;\; (y\in V_\tau \rmiff y\in U^{G_0}_{\al,\langle\rangle})$$
Using ccc Lemma \ref{ccc} choose $H\su 2^\om$ countable so that
$|p|=\rank(p_,H)=0$ and $|\tau|=\rank(\tau,H,1)=0$.  Take any $y\in Y\sm H$.
Let $p_1(0)=p(0)\cup (\al,(\langle\rangle,y))$ and 
$p_1\res[1,\om_2)=p_0\res[1,\om_2)$,  Note that
$p_1\forces y\in  U^{G_0}_{\al,\langle\rangle}$ and hence
$p_1\forces y\in V_\tau$.   Now $B(v)=^{def} y\in V_v$ is a $\bsi0\al$ predicate
coded in $M$.  Let $B(v)=\disj_{n<\om}B_n(v)$ where $B_n(v)$ is
a $\bpi0{\be_n}$ predicate with $\be_n<\be$.  Find $p\leq p_1$ and $n<\om$ such
that $p\forces B_n(\tau)$.  By Proposition \ref{mainpoint} there is a
condition $\hat{p}$ compatible with $p$ such that $\hat{p}\forces B_n(\tau)$
and $\rank(\hat{p},H)\leq\be_n<\be$.  By using the meet Lemma \ref{meet}
we may assume $\hat{p}\leq p_0$.  Hence it follows 
$\hat{p}\forces y y\in U^{G_0}_{\al,\langle\rangle}$.  But by the
definition of rank since $y\notin H$, there is some sufficiently large
$m<\om$ such that $r(0)=\hat{p}(0)\cup (\al,(\langle m \rangle,y))$
is consistent.  Letting $r\res[1,\om_2)=\hat{p}\res[1,\om_2)$ leads
to a contradiction:
$$r\forces B_n(\tau)$$
$$r\forces (\disj_{n<\om} B_n(\tau))\rmiff y\in U^{G_0}_{\al,\langle\rangle}$$
$$r\forces y\notin U^{G_0}_{\al,\langle\rangle}$$
\qed

\bigskip\noindent 
{\bf Claim}. $M[G]\models\forall Y\in [2^\om]^{\om_1}\;\;\ord(Y)=\om_1$.

\bigskip
This follows from two standard facts:
\begin{enumerate}
\item $\forall Z\in \pow(\om_1)^{M[G]}\;\;\exists \al_0<\om_2^M\;\; Z\in M[G_{\al_0}]$
\item $\forall G \;\;(\poset^{\om_2})^M$ generic over $M$ $\;\;\forall \al_0<\om_2^M$
$\exists H \;\;(\poset^{\om_2})^{M[G_{\al_0}]}$ generic over 
$M[G_{\al_0}]$ such that $M[G]=M[G_{\al_0}][H]$.
\end{enumerate}

This concludes the proof of Theorem \ref{mainthm}.

\section{The sigma-algebra of abstract rectangles}


\begin{thm}\label{chrectangle}
(Rao 1968 \cite{rao}, Kunen \cite{kunen})  Assume the continuum hypothesis
then every subset of the plane is in the $\si$-algebra generated by
the abstract rectangles.  In fact, at level two.
\end{thm}
\proof
It is enough to see that $\pow(\om_1\times\om_1)=\si\{A\times B\;:\;A,B\su\om_1\}$,
i.e. every subset of $\om_1\times\om_1$ is in the $\si$-algebra
generated by the abstract rectangles. 
\begin{define}
\begin{itemize}
\item $\rr=\{A\times B\;:\;A,B\su\om_1\}$
\item $\Sigma_0(\rr)=\Pi_0(\rr)=\rr$
\item $\Pi_\al(\rr)=\{\om_1\times\om_1\sm P\;:\; P\in\Sigma_\al(\rr)\}$
\item $\Sigma_\al(\rr)=\{\bigcup_{n<\om}P_n\;:\; P_n\in\bigcup_{\be<\al}\Pi_\be(\rr)\}$
\item $\si\{A\times B\;:\;A,B\su\om_1\}=\si\rr=
\bigcup_{\al<\om_1}\Sigma_\al(\rr)=\bigcup_{\al<\om_1}\Pi_\al(\rr)$
\item $\bool(\rr)=$ smallest family containing $\rr$ and closed under finite union and complementation
\end{itemize}
\end{define}

Note that $\bool(\rr)\su \Sigma_1(\rr)\cap \Pi_1(\rr)$.  Also 
$\Sigma_\al(\rr)$ for $\al>0$ is closed under countable union and finite
intersection.

\begin{lemma}
For $f:2^\om\to 2^\om$, the $\graph(f)\in\Pi_1(\{A\times B\;:\; A,B\su 2^\om\})$.
\end{lemma}
\proof
For any $s\in 2^{<\om}$ let $D_s=f^{-1}([s])$.  Then
the following are equivalent for any $x,y\in 2^\om$:
\begin{itemize}
\item $f(x)=y$
\item $\forall s(s\su f(x) \rmiff s\su y)$
\item $\forall s(x\in A_s \rmiff y\in [s]$
\item $(x,y)\in\bigcap_{s\in 2^{<\om}}(D_s\times [s])\cup (\sim D_s\times \sim [s])$
\end{itemize}
\qed
Note that the Lemma is also true for any partial function $f:D\to 2^\om$
for some $D\su 2^\om$.  Since if $\hat{f}\supseteq f$ is total, then
$$\graph(f)=\graph(\hat{f})\cap (D\times 2^\om) \in \Pi_1(\rr).$$

Now we prove Theorem \ref{chrectangle} that $\pow(\om_1\times\om_1)=\Sigma_2(\rr)$.
Suppose $A$ is a subset of $\om_1\times\om_1$ with the property that
$\be\leq\al$ for every $(\al,\be)\in A$.   Let $f_n:\om_1\to\om_1$ be partial
functions for $n<\om$ so that for any $\al<\om_1$
$$\{\be\;:\; (\al,\be)\in A\}=\{f_n(\al)\;:\; n<\om\}.$$ 
It follows that $A=\bigcup_{n<\om}\graph(f_n)$
is $\Sigma_2(\rr)$.  Now any subset of $\om_1\times\om_1$
can be written as a union $A\cup B$ where $B$ has the property that
$\al\leq\be$ for any $(\al,\be)\in B$.  By symmetry $B\in\Sigma_2(\rr)$
and so $(A\cup B)\in\Sigma_2(\rr)$.
\qed


\begin{thm}
(Kunen \cite{kunen} 1968)  Assume Martin's axiom, then
every subset of the plane is in the $\si$-algebra generated by
the abstract rectangles at level two.  In the Cohen real model
or the random real model the well-ordering on the continuum is not
in the $\si$-algebra generated by
the abstract rectangles.
\end{thm}

\begin{thm} 
(Rothberger \cite{roth} 1952) Suppose that $2^{\om}=\om_2$ and
$2^{\om_1}=\om_{\om_2}$ then the $\si$-algebra generated by the abstract
rectangles in the plane is not the power set of the plane. 
\end{thm}
\proof
Let $H_\al$ for $\al<\aleph_{\om_2}$ list all countable subsets of
$\pow(\om_1)$. Let $\si H_\al$ be the $\si$-algebra generated by $H_\al$.
Note that $|\si H_\al|\leq |2^\om|=\om_2$ since $H_\al$ is countable.
For each $\be<\om_2$ choose $X_\al\su \om_1$ with
$X_\al\notin \bigcup_{\al<\aleph_\be}\si H_\al$.
Let $X=\bigcup_{\be<\om_2}\{\be\}\times X_\be$.

\bigskip {\bf Claim}. $X\notin \si\{A\times B\;:\; A\su\om_2 \rmand B\su\om_1\}$.

\bigskip
Suppose for contradiction that 
$$X\in \Sigma_\ga(\{A_n\times B_n\su \om_2\times\om_1\;:\; n<\om \}).$$
It is easy to see that the cross sections satisfy:
$$\forall \be<\om_2 \;\; X_\be\in \Sigma_\ga(\{B_n \;:\;n<\om\}).$$
But if $H_{\al_0}=\{B_n \;:\;n<\om\}$ where $\al_0<\om_{\be_0}$,
then $X_{\be_0}\notin \si H_{\al_0}$,
which is a contradiction.
\qed
Note Rothberger states this result in more generality, this is
the simplest case.


\begin{thm}\label{bbmbdd}
(Bing, Bledsoe, Mauldin \cite{BBM} 1974) If every subset of the plane
is in the $\si$-algebra generated by the abstract rectangles, then
for some countable $\al$ every subset of the plane
is in the $\si$-algebra generated by the abstract rectangles by level
$\al$.
\end{thm}
\proof
This is more general:

\bigskip\noindent {\bf Claim}. For any cardinal $\ka$ if
$\si\{A\times B\;:\; A,B\su\ka\}=\pow(\ka\times\ka)$, then there
exists $\al<\om_1$ such that 
$\Pi_\al(\{A\times B\;:\; A,B\su\ka\})=\pow(\ka\times\ka)$.

\bigskip
Suppose not.
Take $P_\al\su\ka$ for $\al<\om_1$ pairwise disjoint and
cardinality $\ka$.  For each $\al<\om_1$ take
$A_\al\su P_\al \times P_\al$ such that 
$$A_\al\notin \Pi_\al(\{A\times B\;:\; A,B\su \ka\}).$$
Let $A=\bigcup_{\al<\om_1}A_\al$.  
Note that 
for any $\al<\om_1$ $(P_\al\times P_\al)\in \Pi_1$.
It follows that if $A\in\Pi_{\al_0}$, then for any $\al<\om_1$
$A_\al=A\cap (P_\al\times P_\al)\in \Pi_{\al_0}$, which 
is a contradiction.
\qed

\begin{thm}\label{qomega1}
(Miller \cite{hier} \footnote{I proved this on the
plane trip back to Berkeley from the January 1977 AMS-ASL meeting in St. Louis.
It was so cold that year the AMS vowed never to have their January meetings
anywhere but warm places.  It was late at night; the plane was pretty much 
empty and was delayed due to excessive ice on the wings, so they opened up the bar
cart as we sat on the tarmac.}) 
If every subset of a 
separable metric space $X$ is Borel in $X$, then for some countable $\al$ 
every subset of
$X$ is $\Sigma_\al^0$ in $X$.
\end{thm}
For the proof, we will need the following two Lemmas.

\begin{lemma}\label{rectangle}
Suppose there exists $X\su 2^\om$, $X=\{x_\al:\al<\ka\}$, and there exists
$\al<\om_1$ such that for every $\ga<\ka$ every $Y\su \{x_\be:\be<\ga\}$ is
$\bsi0\al$ in $X$.   Then 
$$\Sigma_\al\{A\times B\;:\;A,B\su\ka\}=\pow(\ka\times\ka).$$
\end{lemma}
\proof
Consider any $A\su\ka\times\ka$ such that $\be\leq\al$ for
any $(\al,\be)\in A$.  Let $X=\{x_\al\;:\;\al<\ka\}$ and let
$V\su 2^\om\times 2^\om$ be a universal $\bsi0\al$-set.
For each $\al<\ka$ choose $y_\al\in 2^\om$ distinct such that
$$\forall \be<\ka \;\;\;(\al,\be)\in A \rmiff (y_\al,x_\be)\in V
\rmiff x_\be\in V_{y_\al}.$$
Define $F:\ka\times\ka\to X\times Y$ by $F(\al,\be)=(x_\al,y_\be)$. 
Note that $F$ is a rectangle preserving bijection such that
$F(A)=V\cap (X\times Y)$.   Note that 
$$V\in \bsi0\al\{C_n\times D_n\;:\;n<\om\}$$ where $C_n,D_n$
are clopen subsets of $2^\om$.  It follows that
$$A\in\bsi0\al(\{\al:y_\al\in C_n\}\times \{\be:x_\be\in D_n\}).$$
By a symmetrical argument we can handle any $B\su\ka\times\ka$ where
$\be\geq\al$ for
any $(\al,\be)\in B$, and hence any set of the form $A\cup B$.
\qed

\begin{lemma} \label{diagonal} If $X\su 2^\om$,  every subset of
$X$ is Borel in $X$, $\om<\ka=|X|$, and 
$\si\{A\times B\;:\; A\times B\su \om_1\times\ka\}=\pow(\om_1\times\ka)$, then
$\ord(X)<\om_1$.
\end{lemma}
\proof
Every rectangle $A\times B\su X\times X$ is Borel in $X\times X$, so
every subset of $X\times X$ is Borel in $X$.  If $\ord(X)=\om_1$, then
for every $\al<\om_1$ choose $H_\al\su X$ such that $H_\al\notin \bsi0\al(X)$.
Choose $x_\al\in X$ for $\al<\om_1$ distinct.  Let
$H=\bigcup_{\al<\om_1}\{x_\al\}\times H_\al$.  If 
$H$ is $\bsi0{\al_0}$ in $X\times X$, then $H_\al$ is $\bsi0{\al_0}$ in
$X$ 
for all $\al<\om_1$.  This is a contradiction.
\qed 

\noindent Proof of Theorem \ref{qomega1}:   

Let $X=\{x_\al\;:\;\al<\ka\}$ and prove the Theorem by induction on
$\ka$.  

\bigskip\noindent {\bf Case}. $\ka=\om_1$.  We are done by Lemma \ref{diagonal}
and Theorem \ref{chrectangle} since 
$$\Sigma_2\{A\times B\;:\; A,B\su \om_1\times\om_1\}=\pow(\om_1\times\om_1).$$

\bigskip\noindent {\bf Case}. $\cof(\ka)=\om$.  Let $X=\bigcup_{n<\om}X_n$ pairwise
disjoint and each $|X_n|<\ka$.  By induction $\ord(X_n)<\om_1$ for each $n<\om$.  
Choose countable $\al$ so that $\ord(X_n)\leq\al$ and each $X_n$ is $\bsi0\al$ in $X$.
For any $A\su X$ we have that $A\cap X_n$ is $\bsi0\al$ in $X$ and so
$X\cap A=\bigcup_{n<\om}A\cap X_n$ is $\bsi0\al$ in $X$.

\bigskip\noindent {\bf Case}. $\cof(\ka)>\om_1$.
Define $X_\al=\{x_\be:\be<\al\}$.
Note that $\ord(X_\al)$ for $\al<\ka$ is a nondecreasing
function and so there is a $\be<\om_1$ such that
$\ord(X_\al)\leq\be$ all $\al<\ka$.  Similarly there is a 
countable $\ga\geq\be$
such that every $X_\al$ is $\bsi0\ga$ in $X$.  To see this note that
for $\al<\be$, if $X_\al$ is $\bsi0\ga$ in $X_\be$ and
$X_\be$ is $\bsi0\ga$ in $X$, then $X_\al$ is $\bsi0\ga$ in $X$.
It follows that every $Y\su X$ with $Y\su X_\al$ for some $\al<\ka$
is $\bsi0\ga$ and so by 
Lemma \ref{rectangle} we have that 
$\Sigma_\al\{A\times B\;:\;A,B\su\ka\}=\pow(\ka\times\ka).$
Hence we are done by Lemma \ref{diagonal}.

\bigskip\noindent {\bf Case}. $\cof(\ka)=\om_1$.
Let $\ka_\al$ for $\al<\om_1$ be a cofinal in $\ka$ increasing sequence.

\bigskip {\bf Claim}. There exists $\al_0<\om_1$ such that
$X_{\ka_\al}$ is $\bpi0{\al_0}$ in $X$ for all $\al<\om_1$.
pf: Let $Q=\{(\al,\be)\;:\; \al<\om_1\rmand \be\leq\ka_\al\}\su \om_1\times\ka$.
Then its complement $\sim Q=\{(\al,\be)\;:\; \ka_\al<\be\}$ has countable
cross sections, so there exists partial functions $f_n:\ka\to\om_1$
for $n<\om$ such that for any $\be<\ka$ 
$$\{\al:(\al,\be)\in\sim Q\}=\{f_n(\be):n<\om\}$$
equivalently 
$$\sim Q=\bigcup_{n<\om}\graph(f_n).$$ 
Similar to the proof of Theorem \ref{chrectangle} we get
that 
$$\sim Q\in\Sigma_2(\{A\times B: A\su\om_1, B\su\ka\}.$$ 
And therefor
$Q\in\Pi_2(\{A\times B: A\su\om_1, B\su\ka\}$.  Now since every
rectangle in $X\times X$ is Borel in $X\times X$ we get that
$\{(x_\al,x_\be)\;:\;\be\leq \ka_\al\}$ is Borel in
$X\times X$.  If it is $\bpi0{\al_0}$ in $X\times X$, then
so are all its cross sections and so we are done.
 
\bigskip {\bf Claim}. Suppose $\ord(X_{\ka_\al})=\be_\al$ 
which is countable by induction, then $\sup_{\al<\om_1}\be_\al<\om_1$.
pf: Suppose not and choose $\al_i<\om_1$ for $0<i<\om_1$ 
strictly increasing, so
that $\be_{\al_i}>\al_0$ and $\be_{\al_{i+1}}>\be_{\al_i}+\om$.
For each $i<\om_1$ let $Y_i=X_{\ka_{i+1}}\sm X_{\ka_{i}}$.  The
$Y_i$ are pairwise disjoint, $\ord(Y_i)=\be_{i+1}$, and $Y_i$ is
$\bpi0{\al_0+1}$ in $X$.  Choose $A_i\su Y_i$ which is not
$\bpi0\al_i$ in $Y_i$.   But then $A=\bigcup_{i<\om_1} A_i$
is not Borel in $X$, since $A_i=A\cap Y_i$.

\bigskip
It follows from the second Claim and Lemmas \ref{rectangle} 
and \ref{diagonal} that $\ord(X)<\om_1$.
This proves Theorem \ref{qomega1}.
\qed

\begin{thm}\label{qalpha}
(\cite{hier}) For any countable $\al$ it is consistent
to have a separable metric space $X$ in which every subset
is Borel and the order of $X$ is $\al$.  Furthermore in this model for
successor $\al=\al_0+1\geq 3$ for any $Z\su 2^\om$ if every subset of 
is $\bsi0{\al_0}$ in $Z$, then $Z$ is countable.
\end{thm}

We just prove this for countable successor 
ordinals $\al_0+1$ greater than two.  For limit $\al$ see
\cite{hier}.


\begin{define} $\poset(T,Y,X)$.  Fix countable $\al_0\geq 2$.
This forcing is similar
to $\Pi_{\al_0+1}$ forcing (Definition \ref{defpialpha}).
Assume $Y\su X\su 2^\om$.   Recall that definition uses
a nice $\al_0+1$ tree $T$ which will remain fixed throughout
the proof.  We denote terminal nodes of $T$ by $T^*$ and
interior nodes $T^0=T\sm(\{\langle\rangle\}\cup T^*)$. Then
$p\in \poset(T,Y,X)$ iff $p=p_0\cup p_1$ finite
with $p_0:T^*\to 2^{<\om}$ finite partial and finite
$p_1\su T^0\times X$ subject to the consistency demands:
\begin{itemize}
 \item if $((n),x)\in p_1$, then $x\notin Y$
 \item if $(s,x)\in p_1$ and $(sn,y)\in p_1$, then $x\neq y$
 \item if $(s,x)\in p_1$ and $p_0(sn)=r$, then $x\notin [r]$
\end{itemize}
\end{define}
Note that we only attach elements of $X$ to
the interior nodes of $T$, we do not attach any reals to the top node
$\langle\rangle$ of $T$, and we only attach reals from
$X\sm Y$ to the rank $\al_0$ nodes of $T$, i.e., those of the form $(n)$. 
We remark that $\poset(T,\emptyset,2^\om)$ is the
same as the direct sum of countably many copies of 
$\Pi_{\al_0}$-forcing.
We could think of the first condition as equivalent to putting all 
$(\langle\rangle,y)$ for $y\in Y$ into $p_1$.



\begin{define} $U^G_s$.\label{defU}
Similar to before for a generic $G$ a $\poset(T,Y,X)$-filter, define
$U_s^G\su 2^\om$ for $s\in T$. For $s\in T^*$ define
$U^G_s=[r]$ iff $p_0(s)=r$ for some $p\in G$.  For $s\in T\sm T^*$
define $U^G_s=\bigcap_{n<\om}\sim U^G_{sn}$. 
\end{define}

\begin{lemma}\label{easy}
For $G$ any generic $\poset(T,Y,X)$-filter:
\begin{enumerate}
\item For any $s\in T^0$ and $x\in X$
$x\in U^G_s$ iff $\{(s,x)\}\in G$.
\item $U^G_{\langle\rangle}\cap X=Y$.
\end{enumerate}
\end{lemma}
\proof
For any $s\in T^0$ and $x\in X$ define
$D_{s,x}\su\poset_{\al_0+1}(Y,X)$ by 
$p\in D_{s,x}$ iff 
\begin{itemize}
 \item $(s,x)\in p$ or
 \item $\exists n<\om\;\; (sn,x)\in p_1$ or
 \item $\exists r \in 2^{<\om}\;\; p_0(sn)=r \rmand x\in  [r]$.
\end{itemize}
Then $D_{s,x}$ is dense.  Note for $n<\om$ and $y\in Y$ you
can never add $((n),y)$ however you
will be add $((n,m),y)$ for some sufficiently large $m$. 

(1) Suppose $x\in U_s^G=\bigcap_{n<\om}\sim U_{sn}^G$, then $x\notin U_{sn}^G$
for all $n$.  Hence by induction 
for all $n$ for all $p\in G$  ($(sn,x)\notin p$ or 
$x\notin [p_0(sn)]$) if $\rank_T(s)=1$.   Since $D_{s,x}$ is dense
we have that $\{(s,x)\}\in G$.

Conversely, suppose $\{(s,x)\}\in G$.  Then for every $n<\om$ and $p\in G$
$(sn,x)\notin p$ or 
$x\notin [p_0(sn)]$) if $\rank_T(s)=1$.  So by induction $x\notin U_{sn}^G$
for all $n$ and by definition of $U_s^G$ we have that $x\in U_s^G$.
 
(2) Suppose $y\in Y$.  Fix $n$.  By the definition of $\poset(T,Y,X)$ 
$((n),y)$ is not in any condition.  Hence for any $p$ there exists
$m$ sufficiently large so that $p\cup\{((n,m),y)\}$ is
consistent.  It follows that $y\notin U_{(n)}^G$ and so
$y\in U_{\langle \rangle}^G$.

Conversely, suppose $x\in X\sm Y$.  Then
$\{p\;:\; \exists n\;\;((n),x)\in p \}$
is dense, so $x\in U_{(n)}^G$ for some $n$ and hence 
$y\notin U_{\langle \rangle}^G$.
\qed
Let $M$ be a countable standard model of ZFC+GCH.  Fix $X = 2^\om\cap M$ 
(or any uncountable subset of $2^\om$ in $M$) and $T$ a nice $\al_0+1$-tree in $M$.    
We will iterate  $\poset(T,Y_\al,X)$ for $\al_<\om_2$ with finite support,
diagonalizing to get all $Y\su X$.  An explicit description of this model
is as follows.  

Let $\poset^0=\poset(T,\emptyset,X)$.  

Inductively assume that 
$\poset^\al\su \Sigma_{\be<\al}\poset(T,\emptyset, X)$ (the direct sum).
Suppose $\name{Y}_\al$ is a nice $\poset^\al$-name for a subset of
$X$, i.e., there exists $(A_x^\al:x\in X)$ where $A_x^\al\su \poset^\al$
is countable and
$$\name{Y}_\al=\{(p,\check{x})\;:\; x\in X\rmand p\in A_x^\al\}.$$
Then $p\in\poset^{\al+1}$ iff $p\res\al\in \poset^\al$, 
$p(\al)\in \poset(T,\emptyset,X)$, and if $p(\al)=p_0\cup p_1$, then
whenever $((n),x)\in p_1$ for some $n<\om$ and $x\in X$, then
$$p\res\al\forces x\notin \name{Y}_\al$$
or equivalently $(p\res\al)\perp q$ for all $q\in A^\al_x$.

For $\lambda\leq\om_2$ a limit ordinal
$$\poset^\lambda=\{p\;:\; \forall \al<\lambda \;\;p\res\al\in\poset^\al\rmand
\supp(p)\mbox{ is finite }\}\}.$$
where $\supp(p)=^{def}\{\al<\lambda\;:\;p(\al)\neq 1\}$ is the support of
$p$.
Note that for any $\al<\om_2$, 
$\Sigma_{\be<\al}\poset(T,\emptyset,X)$ has cardinality $\om_1$.
It also has ccc (in fact property K). Note that $p,q\in \poset^\al$ are
compatible iff $p\cup q\in \poset^\al$ iff 
$p\cup q\in \Sigma_{\be<\al}\poset(T,\emptyset,X)$.  For $\al<\om_2$
we may regard 
$$\poset^\al=\{p\in \poset^{\om_2}\;:\; p\res[\al,\om_2) \equiv 1\}.$$
By a standard dovetailing argument in $M$ we may choose the 
sequence of names $\name{Y}_\al$
so that for any $G$ $\poset^{\om_2}$-generic over $M$ for any $Y\su X$
in  $M[G]$ there is an $\al<\om_2^M$ such that $Y_\al^G=Y$.

By Lemma \ref{easy} we have that in $M[G]$ every subset of
$X$ is $\bsi0{\al_0+1}$ in $X$.  Recall that
$\poset^0=\poset(T,\emptyset,X)$.  Let $U_{(0)}^G$ be the generic
$\bpi0\al_0$-set added by $\poset^0$. (Any of the other $U_{(n)}^G$ would
do as well.)   We will show that there is no $\bsi0\al_0$-set $V\su 2^\om$
in $M[G]$ such that $U_{(0)}^G\cap X=V\cap X$.

Given $H\su X$ define
$$\rank(p,H)=\max\{\rank_T(s)\;:\:\exists x\in X\sm H\;\exists\al<\om_2\;\;
(s,x)\in p(\al)\}.$$

Working in $M$ suppose we are given $\Gamma\in\poset^{\om_2}$ countable and 
$\tau$ a nice $\poset^{\om_2}$ for
an element of $2^\om$.   Then by the ccc we can find a countable 
$H\su X$ and countable $K\su\om_2$ with the following properties:
\begin{enumerate}
\item $\rank(p,H)=0$ for all $p\in\Gamma$
\item $\forall n\in \om$  $\;\;\;\{p\in\poset^{\om_2}\;:\;\supp(p)\su K
\rmand \rank(p,H)=0\}$
decides\footnote{Recall that a set conditions $Q$ decides a sentence
$\theta$ iff every generic filter contains a condition in $Q$ which forces
either $\theta$ or its negation.} ``$\tau(n)=0$''.
\item $\forall x\in H\;\forall \al\in K$
$\{p\in\poset^{\al}\;:\;\supp(p)\su K
\rmand \rank(p,H)=0\}$ decides ``$x\in \name{Y}_\al$''.
\end{enumerate}

The analogue of the meet lemma for this forcing is trivial.

\begin{lemma} Meet Lemma. For any $p,q\in\poset^{\om_2}$ 
we have:

$p$ and $q$ are compatible
iff $p\cup q\in\poset^{\om_2}$.

\noindent The union is defined 
by $(p\cup q)(\al)=^{def}p(\al)\cup q(\al)$
for each $\al<\om_2$.
\end{lemma}
\proof
Prove by induction that $(p\cup q)\res\al\in\poset^\al$ and
extends both $p\res\al$ and $q\res\al$.
\qed

The union operation preserves rank and support.

\begin{lemma} Rank Lemma for $H,K$. 
Assume $H,K$ satisfy condition 3 above, i.e., $\forall x\in H\;\forall \al\in K$
$\{p\in\poset^{\al}\;:\;\supp(p)\su K
\rmand \rank(p,H)=0\}$ decides ``$x\in \name{Y}_\al$''.
  Suppose $p\in\poset^{\om_2}$ and
$1\leq\be<\al_0$.   Then there exists $\hat{p}$ compatible with $p$,
$\rank(\hat{p},H)\leq\be$, $\supp(\hat{p})\su K$, and for any 
$q\in\poset^{\om_2}$ with $\rank(q,H)<\be$ and $\supp(q)\su K$,
$(p\perp q \Rightarrow \hat{p}\perp q)$.  
\end{lemma}
\proof
Extend $p$ to $\tilde{p}$ so that for any $\al,s,x,\lambda$ if
$(s,x)\in p(\al)$ and $\rank_T(s)=\lambda$ is a limit ordinal, then
for every $i<\om$ with $\rank_T(si)\leq\be+1<\lambda$ 
there exists $j$ with $(sij,x)\in \tilde{p}(\al)$.  The definition
of nice tree tells us there are at most finitely many such $i$.

Let $G$ be $\poset^{\om_2}$-generic with $\tilde{p}\in G$.  Choose
$\Gamma\su G$ finite so that 
\begin{enumerate}
\item[(a)] $\forall q\in\Gamma\;\;\rank(q,H)=0$ and $\supp(q)\su K$
\item[(b)] if  $((n),x)\in p(\al)$ for some $\al\in K$ and $x\in H$,
then there exists $q\in \Gamma$ such that $q\res\al\forces x\notin \name{Y}_\al$.
\end{enumerate}
Note that in (b) it must be that $p\res\al\forces x\notin \name{Y}_\al$.

Working in $M$ define $\hat{p}$ as follows: for $\al\in K$
$$\hat{p}(\al)=\bigcup\{q(\al)\;:\;q\in\Gamma\}\cup\{(s,x)\in\tilde{p}_1(\al)\;:\;
\rank_T(s)\leq\be\rmor x\in H\}\cup \tilde{p}_0(\al)$$
and $\hat{p}(\al)=1$ for $\al\notin K$.

We prove that $\hat{p}\leq q$ for each $q\in\Gamma$ and $\rank_T(\hat{p})\leq\be$.
Note that $\be<\al_0=\rank_T((n))$ so we have retained no conditions
of the form $((n),x)$ for $x\notin H$, i.e., if $((n),x)\in\hat{p}$, then
$\al\in K$ and $x\in H$. So $\hat{p}\res\al\leq q\res\al$ for some  $q\in\Gamma$
such that $q\res\al\forces x\notin \name{Y}_\al$ and so
$\hat{p}\res\al\forces x\notin \name{Y}_\al$.
This shows that $\hat{p}$ is a condition.

We check that it satisfies the Lemma.  Since $\tilde{p}\leq p$ and
$\tilde{p},\hat{p}$ are both in $G$, we have that $p$ and $\hat{p}$
are compatible.   Suppose $\rank(q,H)<\be$ and
$\supp(q)\su K$.   We need to show that
$p\perp q\rightarrow \hat{p}\perp q$.   Assume $p\perp q$, 
hence $p\cup q$ is not a condition
so there must be $\al\in\supp(p)\cap\supp(q)$ (so $\al\in K$) 
$(p\cup q)\res\al\in\poset^{\al}$, but $p(\al)\cup q(\al)\notin
\poset(T,\name{Y}_\al,X)$.   Therefor at least one of the following
cases occurs:

\bigskip
Case 1. For some $s\in T^*$ we have $p_0(\al)(s)\neq q_0(\al)(s)$.  

\medskip\noindent
But  $\hat{p}_0(\al)(s)=p_0(\al)(s)$, so $\hat{p}(\al)\perp q(\al)$.

\bigskip
Case 2. For some $s,r,n$ with $s\in T^0$ and $sn\in T^*$ and $x\in X$: 
\par\noindent 
($p_0(\al)(sn)=r$ or $q_0(\al)(sn)=r$) and $(s,x)\in p_1(\al)\cup q_1(\al)$,
but $x\in [r]$.

\medskip\noindent
In this case, $\rank_T(s)=1\leq\be$ and hence $(s,x)\in\hat{p}_1(\al)$ 
if $(s,x)\in{p}_1(\al)$.  So if $q_0(\al)(sn)=r$, 
then $\hat{p}(\al)\perp q(\al)$.  The other possibility is that
${p}_0(sn)=r$ and $(s,x)\in q_1(\al)$.  Then since
$\hat{p}_0(sn)={p}_0(sn)$, we also have $\hat{p}(\al)\perp q(\al)$.


\bigskip
Case 3. For some $s,sn\in T^0$ and $x\in X\;\;\;$ 
$(s,x),(sn,x)\in p_1(\al)\cup q_1(\al)$.

\medskip\noindent
In this case, if $x\in H$, then $(s,x),(sn,x)\in \hat{p}_1(\al)\cup q_1(\al)$
and so $\hat{p}(\al)\perp q(\al)$.   Suppose $x\notin H$, then
one of the following occurs:

\medskip\noindent  1. $(sn,x)\in{p}_1(\al)$ and $(s,x)\in q_1(\al)$
\par\noindent      2. $(s,x)\in{p}_1(\al)$ and $(sn,x)\in q_1(\al)$

\medskip
For (1) since $\rank(q,H)<\be$ we have that $\rank_T(sn)<\rank_T(s)<\be$
and so by the definition of $\hat{p}$ we have that $(sn,x)\in\hat{p}_1(\al)$
so $\hat{p}(\al)\perp q(\al)$.   For (2) we have that 
$\rank_T(sn)<\be$ because $\rank(q,H)<\be$.   If $\rank_T(s)\leq\be$,
then $(s,x)\in\hat{p}_1(\al)$ so $\hat{p}(\al)\perp q(\al)$.   Finally
we have the possibility that $\rank_T(s)=\lambda>\be$ a limit ordinal.
In this case we choose $\tilde{p}(\al)$ so that for some $m$
we have that $(snm,x)\in\tilde{p}_1(\al)$.  Since
$\rank_T(snm)<\be$, $(snm,x)\in\hat{p}_1(\al)$, and
therefor $\hat{p}(\al)\perp q(\al)$.
\qed

\begin{lemma}\label{nice}
Suppose $\tau$ a nice $\poset^{\om_2}$ for
an element of $2^\om$ 
and  $H\su X$ and  $K\su\om_2$ are countable 
satisfying
\begin{enumerate}
\item $\forall n\in \om$  $\;\;\{p\in\poset^{\om_2}\;:\;\supp(p)\su K,
 \rank(p,H)=0\}$
decides``$\tau(n)=0$''.
\item $\forall x\in H\;\forall \al\in K$
$\{p\in\poset^{\al}:\supp(p)\su K,
\rank(p,H)=0\}$ decides ``$x\in \name{Y}_\al$''.
\end{enumerate}
Suppose $B(v)$ is a $\bsi0\be$ predicate for $1\leq\be\leq\al_0$ with
parameters from $M$ and $p\in\poset^{\om_2}$ satisfies:
$p\forces B(\tau)$.   Then there exists $\hat{p}$ compatible with $p$,
$\rank(\hat{p},H)<\be$, $\supp(\hat{p})\su K$, and $\hat{p}\forces B(\tau)$.
\end{lemma}
Case $\be=1$.  

Suppose $R\su 2^{<\om}$ is in $M$ and
$p\forces\exists n\in\om\;\; R(\tau\res n)$.   Find $q\leq p$, $n\in\om$,
$t\in 2^n$ such that $R(t)$ and $q\forces \tau\res n=\check{t}$.
Take $G$ $\poset^{\om_2}$-generic with $q\in G$.
By (1) we can choose finite $\Gamma\su G$ such that

for all $m<n$ there is a $r\in\Gamma$ $r\forces$``$\tau(m)=t(n)$''
and 

$\supp(r)\su K$ and $\rank(r,H)=0$ for all $r\in\Gamma$.

\noindent Then $\hat{p}=\bigcup\Gamma$ satisfies the Lemma.

\bigskip\noindent Case $\be\leq\al_0$ a limit ordinal.

Suppose $p\forces$ ``$\exists n\in\om\; B_n(\tau)$'' where
for each $n$ $B_n(v)$ is a $\bpi0{\be_n}$ predicate coded
in $M$ with $\be_n<\be$.  Extend $p$ by $q\leq p$ such that
for some $k$ $q\forces$ ``$B_k(\tau)$''.  Since $\bpi0{\be_k}$
predicates are $\bsi0{\be_{k+1}}$ and $\be_{k+1}<\be$, we have
by induction $\hat{p}$ compatible with $q$ (hence $p$) with
$\rank(\hat{p},H)\leq\be_{k+1}<\be$, $\supp(\hat{p})\su K$,
and $\hat{p}\forces $ ``$B_k(\tau)$''.

\bigskip\noindent Case $1<\be+1\leq\al_0$ a successor ordinal.

Suppose $p\forces$ ``$\exists n\in\om\; B(n,\tau)$'' where
$B(n,v)$ is a $\bpi0{\be}$ predicate coded
in $M$. We may extend $p$ to $p_0\leq p$ so that for some $n$
$p_0\forces B(n,\tau)$.  By the Rank Lemma since $\be<\al_0$ there is some
$\hat{p_0}$ compatible with $p_0$ such that 
$\rank(\hat{p_0},H)\leq\be$, $\supp(\hat{p_0})\su K$, and for any 
$q\in\poset^{\om_2}$ with $\rank(q,H)<\be$ and $\supp(q)\su K$,
$(p_0\perp q \Rightarrow \hat{p_0}\perp q)$.  But then
$\hat{p}_0\forces B(n,\tau)$.  Because if not, by inductive 
hypothesis there would be $q$ compatible with $\hat{p}_0$,
$\rank(q,H)<\be$, $\supp(q)\su K$, and $q\forces \neg B(n,\tau)$.  
But such a $q$ is incompatible with $p_0$ which is a contradiction.
\qed

\begin{lemma}\label{lemmaqset}
Suppose $X=\{x_\al:\al<\om_1\}$ and $Z=\{z_\al:\al<\om_1\}\su 2^\om$
be an arbitrary set of reals in $M$. 
For any $G$ $\poset^{\om_2}$-generic over $M$, then
$$(U^G_{(0)}\times 2^\om)\cap \{(x_\al,z_\al)\;:\;\al<\om_1\}\neq
V\cap \{(x_\al,z_\al)\;:\;\al<\om_1\}$$
for any $V\su 2^\om\times 2^\om$
a $\bsi0{\al_0}$-set coded in $M[G]$
\end{lemma}
\proof
Recall that $U^G_{(0)}$ (\ref{defU})  is one of the ``generic'' $\bpi0{\al_0}$ 
sets determined by the first coordinate, i.e., for $x\in X$ we have that
$x\in U^G_{(0)}$ iff $((0),x)\in p_1(0)$ for some $p\in G$.

Work in $M$.  Let $V\su 2^\om\times (2^\om\times 2^\om)$ be a
universal $\bsi0{\al_0}$-set.   For contradiction, 
suppose there exists $q\in\poset^{\om_2}$ and
$\tau$ is a nice name for an element of $2^\om$  such that
$$q\forces \forall \al<\om_1\;\; (x_\al\in \name{U}_{(0)}
\rmiff (\tau,(x_\al,z_\al)\in V).$$
Choose $H\su X, K\su\om_2$ countable such that $\rank(q,H)=0$,
$\supp(q)\su K$, and satisfying the conditions of Lemma \ref{nice}
for $\tau$.

Fix any $\al\in \om_1$ with $x_\al \notin H$ and
define the $\bsi0{\al_0}$ predicate $B(v)$ by 
$$B(v)\equiv (v,(x_\al,z_\al))\in V.$$
Let $p\leq q$ be defined by only adding $((0),x_\al)$ to
the first coordinate of $q$, i.e.,
$p(0)=q(0)\cup ((0),x_\al)$ and $p\res[1,\om_2)= q\res[1,\om_2)$.
This is possible because $q(0)$ cannot mention $x_\al$
because $\rank(q,H)=0$.  Note that $p\forces B(\tau)$.
By Lemma \ref{nice} there is a $\hat{p}$ compatible with
$p$ such that $\rank(\hat{p},H)<\al_0$ and
$\hat{p}\forces B(\tau)$.  By replacing $\hat{p}$ by $\hat{p}\cup p$
we may assume $\hat{p}\leq p$.  Since $\rank(\hat{p},H)<\al_0$ we
have that $((0),x_\al)$ is not in $\hat{p}_1(0)$.  It follows
by taking a large enough $k$ that $\hat{p}_1(0)\cup\{((0,k),x_\al)\}$
is consistent, i.e., an element of $\poset(T,\emptyset,X)$.
If we define $r$ by $r(0)=\hat{p}(0)\cup \{((0,k),x_\al)\}$ and
$r\res[1,\om_2)=\hat{p}\res [1,\om_2)$ we get a contradiction:
$r\forces ``x_\al\in \name{U}_{(0)}$ iff $B(\tau)$'',
$r\forces B(\tau)$, and 
$r\forces x_\al\in \name{U}_{(0,k)}$.
\qed

Finally we prove Theorem \ref{qalpha}.
Lemma \ref{easy} shows that $\ord(X)\leq\al_0+1$ and
Lemma \ref{lemmaqset} shows that $\ord(X)>\al_0$.
Given any $Z\su 2^\om$ of size $\om_1$ in $M[G]$ there will
be $\de<\om_2$ with $Z\in M[G_\de]$.   We can assume
unbounded many
$Y_\de$ code the empty set, so by replacing $M$ by the 
ground model $M[G_\de]$ and forcing with $\poset^{[\de,\om_2)}$, 
Lemma \ref{lemmaqset} shows that $\ord(Z)>\al_0$.
\qed


\begin{thm}\label{newproof}
(\cite{hier}) For any countable $\al\geq 2$ it is consistent
that every subset of the plane
is in the $\si$-algebra generated by the abstract rectangles
at level $\al$ but for every $\be<\al$ not every subset is at level $\be$.
\end{thm}
\proof
We sketch the proof only for the case of a countable successor 
$\al=\al_0+1\geq 3$.   Start with a countable transitive model $M$ of
ZFC+$2^\om=2^{\om_1}=\om_2$.   Let $X=2^\om\cap M$.  Hence $|X|=\om_2$.
Do a finite support iteration (as in the proof of Theorem \ref{qalpha})
of length $\om_2$ of $\poset(T,\name{Y}_\al,X)$ for $\al<\om_2$ making
sure to have names for all potential subsets of $X$ of size $\leq \om_1$.
It follows from Lemma \ref{rectangle} that $\pow(\om_2\times\om_2)=
\Sigma_{\al_0+1}(\{A\times B\;:\; A,B\su\om_2\}$.

It also follows by a similar proof to Theorem \ref{qalpha} that 
in $M[G]$ there
is no $Z\su 2^\om$ with $|Z|=\om_1$ such that every subset of
$Z$ is $\bsi0{\al_0}$ in $Z$.  So we are done by the following:

\begin{lemma} (Bing, Bledsoe, Mauldin \cite{BBM}) \label{bbmlem} Suppose
$\al<\om_1$, $\om<\ka$, $|2^\ka|=\cc$, and 
$\pow(\ka\times\cc)=\Sigma_\al(\{A\times B\;:\; A\su\ka,\; B\su\cc\}$.
Then there exists $Z\su 2^\om$ with $|Z|=\ka$ and every subset of $Z$ is
$\bsi0{\al}$ in $Z$.
\end{lemma}
\proof
Let $Y_\al\su\ka$ for $\al<\cc$ list all subsets of $\ka$.  Define
$$Y=\{(\be,\al):\be\in Y_\al, \al<\cc\}.$$
Let $\{A_n\times B_n:n<\om\}$ be rectangles with
$Y\in\Sigma_\al( \{A_n\times B_n:n<\om\})$.   Take 
$\psi:\ka\to 2^\om$ to be the Marczewski characteristic function:
$$\psi(\al)(n)=1\rmiff \al\in A_n.$$
Then $Z=\{\psi(\al)\;:\;\al<\ka\}$ has the required property.
Note that the cross sections of a $\bsi0\al$-set are $\bsi0\al$.
\qed

\section{Universal functions}

\begin{thm}\label{mainthmuniv}
(Larson, Miller, Steprans, Weiss \cite{univ}) Suppose
$2^{<\cc}=\cc$ then the following are equivalent:
\par (1) There is a Borel universal function, i.e, 
a Borel function $F:2^\om\times 2^\om\to 2^\om$ such that
for every abstract $G:2^\om\times 2^\om\to 2^\om$ there are
$h:2^\om\to 2^\om$ and $k:2^\om\to 2^\om$ such that for
every $x,y\in 2^\om\;\;$
$G(x,y)=F(h(x),k(y))$.
\par (2) Every subset of the plane
is in the $\si$-algebra generated by the abstract rectangles.
\par Furthermore the universal function has level $\al$ iff every
subset of the plane
is in the $\si$-algebra generated by the abstract rectangles at level $\al$.
\end{thm}

\begin{thm}(\cite{univ})\label{abstractuniv}
If $2^{<\ka}=\ka$, then there is an abstract universal function
$F:\ka\times\ka\to\ka$.
\end{thm}

\begin{thm}(\cite{univ})
It is relatively consistent with ZFC, that there is no abstract
universal function $F:\cc\times\cc\to\cc$.
\end{thm}

\begin{thm}(\cite{univ})\label{thmborel}
There does not exist a Borel function $F:2^\om\times 2^\om\to 2^\om$ such that
for every Borel $G:2^\om\times 2^\om\to 2^\om$ there are $h,k:2^\om\to 2^\om$
such that $k$ is Borel and for every $x,y\in 2^\om$
$$G(x,y)=F(h(x),k(y))$$
\end{thm}

The following two theorems are proved just like Theorems 8 and 9 of Bing, 
Bledsoe, and Mauldin \cite{BBM}
who only stated it for the square case, e.g., $\ka\times\ka$.

\begin{theorem}\label{bbmthm8} 
(Bing, Bledsoe, and Mauldin Theorem 8 for $\ka=\lambda$)
\begin{enumerate}
\item The following are equivalent:
\begin{enumerate}
\item $\bsi0\om_1(\{A\times B:A\su\ka, B\su\lambda\})=\pow(\ka\times\lambda)$
\item for every $\aa\in [\pow(\lambda)]^\ka$ there is 
$\bb\in[\pow(\lambda)]^\om$ and $\al<\om_1$ such that
$\aa\su\bsi0\al(\bb)$
\item for every $\aa\in [\pow(\ka)]^\lambda$ there is $\bb\in[\pow(\ka)]^\om$ 
and $\al<\om_1$ such
that $\aa\su\bsi0\al(\bb)$

\end{enumerate}
\item Suppose $\al<\om_1$, then the following are equivalent:
\begin{enumerate}
\item $\bsi0\al(\{A\times B:A\su\ka, B\su\lambda\})=\pow(\ka\times\lambda)$.
\item for every $\aa\in [\pow(\lambda)]^\ka$ there is 
$\bb\in[\pow(\lambda)]^\om$ such
that $\aa\su\bsi0\al(\bb)$
\item for every $\aa\in [\pow(\ka)]^\lambda$ there is $\bb\in[\pow(\ka)]^\om$ such
that $\aa\su\bsi0\al(\bb)$
\end{enumerate}
\end{enumerate}
\end{theorem}


\begin{theorem}
\label{bbmthm9} 
(Bing, Bledsoe, and Mauldin Theorem 9 for $\ka=\lambda$)
The following are equivalent:
\begin{enumerate}
\item $\bsi0\om_1(\{A\times B:A\su\ka, B\su\lambda\})=\pow(\ka\times\lambda)$
\item for every $\aa\in [\pow(\lambda)]^\ka$ there is $\bb\in[\pow(\lambda)]^\om$ 
and $\al<\om_1$ such
that $\aa\su\bsi0\al(\bb)$
\item there is $\al<\om_1$ such that 
for every $\aa\in [\pow(\lambda)]^\ka$ there is $\bb\in[\pow(\lambda)]^\om$ such
that $\aa\su\bsi0\al(\bb)$
\item there exists $\al<\om_1$ such that 
$\bsi0\al(\{A\times B:A\su\ka, B\su\lambda\})=\pow(\ka\times\lambda)$.
\end{enumerate}
\end{theorem}

\begin{define} $X\su 2^\om$ is a strong $Q_\al$-set iff
\par\noindent 
letting $\bb_0=^{def}\{X\cap C\;:\; C\su 2^\om \mbox{ clopen }\}$ then
\begin{itemize}
\item $\pow(X)=\bsi0\om_1(\bb_0)$ ( $\si$-algebra generated by $\bb_0$ ) and
\item $\forall \bb\supseteq \bb_0$ countable $\ord(\bb)=\al$, i.e.
$\al$ is the least ordinal such that $\bsi0\al(\bb)=\bsi0\om_1(\bb)$.
\end{itemize}
\end{define}
The above definition is the one we use to verify the existence
of a strong $Q_\al$-set in a generic extension. When we force
a generic $\bpi0\al$ set it is not $\bsi0\al$ even when
we add sets from the ground model as new ``clopen'' sets.

\begin{theorem}\label{strongqrectangle}
The following are equivalent for a cardinal $\ka$ such that $2^\ka=\cc$
and $\al<\om_1$:
\begin{enumerate}
\item there exists a strong $Q_\al$-set of cardinality $\ka$
\item $\al$ is the smallest ordinal such
that $$\bsi0\al(\{A\times B:A\su\ka, B\su\cc\})=\pow(\ka\times\cc)$$
\item there is a $Q_\al$-set of size $\ka$ but no $Q_\be$-set 
of size $\ka$ for any $\be<\al$ 
\item $\al$ is the minimal ordinal for which there
is a countable $\bb\su\pow(\ka)$ with
$\bsi0\al(\bb)=\pow(\ka)$
\end{enumerate}
\end{theorem}
\bigskip
\proof
Assume (1).
First note that 
$\Sigma_\al\{A\times B\;: A\su\ka, B\su \cc\}=\pow(\ka\times \cc\}$.
This is proved just like Lemma \ref{rectangle}.  
Namely, let $\{x_\be:\be<\ka\}\su 2^\om$ be a $Q_\al$-set.

Fix $U\su 2^\om \times 2^\om$ a universal $\bsi0\al$ set.
Then for any subset $C\su\ka\times\cc$ 
choose $\{y_\be\in 2^\om:\be<\cc\}$ so that
for each $\ga<\ka$ and $\be<\cc$,
$(x_\ga,y_\be)\in U$ iff $(\ga,\be)\in C$.
Since $U$ is $\bsi0\al$ in the clopen rectangles
in $2^\om\times 2^\om$, it
follows that $C$ is $\bsi0\al$ in the abstract rectangles
on $\ka\times\cc$.

Now suppose for contraction that for some $\be<\al$
$$\;\;\Sigma_\be\{A\times B\;: A\su\ka, B\su \cc\}=\pow(\ka\times \cc\}.$$
Let $C\su\ka\times\cc$ be such that the cross sections of
$C$ list $\pow(\ka)$.  Suppose
$C\in\bsi0\be(\{A_n\times A_m:n,m<\om\})$.  Consider
the Marczewski characteristic function of the sequence
of sets $A_n$, i.e., $f:\cc\to 2^\om$ defined by
$f(\be)(n)=1$ iff $\be\in A_n$. We can assume that
the $A_n$ separate points (by adding a countable sequence of
sets if necessary)
so that $f$ is a 1-1 function.  Let $z_\be=f(\be)$.
The function $f$ maps the abstract sets $A_n$ into relatively 
clopen sets in $Z=\{z_\ga:\ga<\cc\}$.  It follows that
$\{z_\ga:\ga<\ka\}$ is a $Q_\de$-set for some $\de\leq\be<\al$
which contradicts the definition of ``strong'' $Q_\al$-set.

The proof of (2) implies (1) is virtually the same. 
The fact that
$$\bsi0\al(\{A\times B:A\su\ka, B\su\cc\})=\pow(\ka\times\cc)$$
via the Marczewski function gives us a $Q_\al$-set of cardinality
$\ka$.  The minimality of $\al$ gives us that there is
no $Q_\be$-set of size $\ka$ for any $\be<\al$.

(3) and (4) are equivalent by using the Marczewski characteristic
function. 

(1) implies (3):  Let  $\{x_\ga:\ga<\ka\}$ be a strong
$Q_\al$-set and suppose $\{y_\ga:\ga<\ka\}$ is
a $Q_\be$-set for some $\be<\al$.
For any clopen set $C\su 2^\om$ let $C'=\{x_\al:y_\al\in C\}$,
then $\bb=\bb_0\cup\{C':C\mbox{ clopen }\}$ has order $\leq\be$
contradicting the definition of strong $Q_\al$-set.

(3) implies (1):  Any $Q_\al$-set of size $\ka$ must be strong,
otherwise by using the Marczewski characteristic function we
could produce for some $\be<\al$ a $Q_\be$-set of cardinality $\ka$.

\qed

\begin{theorem}
It is consistent that for
every countable $\alpha\geq 2$ there is a strong $Q_\al$-set.
\end{theorem}
\proof
This holds in a model mentioned in  \cite{hier} see Theorem 55 and 52.
Theorem 55 \cite{hier} 
states that it is consistent that for
every countable $\alpha\geq 2$ there is a $Q_\al$-set.
The proof is similar to Theorem 52 in that these sets are all
of different cardinality.  By an analogous argument to
Theorem \ref{qalpha}, in fact, those $Q_\al$-sets are strong
$Q_\al$-sets.   
\qed

\begin{thm}\label{remark4.6}
Remark 4.6 \cite{univ}. 
It is consistent that the Borel subsets of
the plane are not contained in any bounded level of the $\sigma$-algebra 
generated by the
abstract rectangles.  The proof of Theorem \ref{mainthmuniv} 
shows that in this situation, there does not 
exist a Borel function $$F:2^\om\times 2^\om\to 2^\om$$
such that for every Borel $H:2^\om\times 2^\om\to 2^\om$ there
exist functions $g$ and $h$ from $2^\om$ to $2^\om$ such that
$$H(x,y)=F(g(x),h(y))$$
for all $x,y\in 2^\om$. 
Hence, if
we drop the condition that $k$ is Borel in Theorem \ref{thmborel}
it is consistent that there be no such Borel $F$.  
\end{thm}

We show that:
\begin{theorem}
If for unboundedly many $\al<\om_1$ there is
a strong $Q_\al$-set, then there is no  countable $\al_0$ such that
$$ \mbox{Borel}(2^\om\times 2^\om)\su\Sigma_{\al_0}(\{A\times B\;:\; A,B\su 2^\om\}).$$
\proof
Let $U\su 2^\om\times 2^\om$ be a universal $\bsi0{\al_0+1}$-set and
$X$ a strong $Q_{\al_0+1}$-set.   Choose $A_n\times B_n\su 2^\om\times 2^\om$ 
for $n<\om$ so that $U\in\Sigma_{\al_0}(\{A_n\times B_n\;:\; n<\om\}).$
\end{theorem}
Define
$$\hh=\{X\cap C\;:\;C \mbox{ clopen }\su 2^\om\}\cup \{B_n\cap X:n<\om\}.$$

\bigskip\noindent {\bf Claim}. $\ord(\hh)\leq\al_0$, so $X$ is not
a strong $Q_{\al_0+1}$-set.

\proof
For any $Y\su X$ there exists $z\in 2^\om$ such that $U_z\cap X=Y$,
because $U$ is a universal $\Sigma_{\al_0+1}$-set and $X$ is
a $Q_{\al_0+1}$-set.
But any cross section of set in $\Sigma_{\al_0}(\{A_n\times B_n\;:\; n<\om\})$
is a set in $\Sigma_{\al_0}(\{B_n\;:\; n<\om\})$.
It follows that $Y\in\Sigma_{\al_0}(\hh)$.  Hence
$\pow(X)=\Sigma_{\al_0}(\hh)$ and so $\ord(\hh)\leq\al_0$.

This proves the Claim and hence the Theorem.
\qed

The following theorem was proved in May 2017.  
It answers negatively the rectangular form of a question asked
by Bing, Bledsoe, and Mauldin \cite{BBM} in the paragraph just before
Theorem 10, namely, in Theorem \ref{bbmthm9} (2,3) can
we replace ``$\aa\su\bsi0\al(\bb)$'' with ``$\aa\su\bsi0\om_1(\bb)$''?
I want to thank Ashutosh Kumar for bringing the problem to
my attention.  I do not know the answer for the square version of this
question.

\begin{theorem}\label{bbmanswer}
Suppose for unboundedly many $\al<\om_1$ there exists a 
strong $Q_\al$-set, then there exists an uncountable cardinal
$\ka<\cc$ such that 
\begin{enumerate}
\item every family of size $\ka$ of sets of reals is included
in a countably generated $\si$-algebra, 
$\forall \aa\in [\pow(\cc)]^\ka$ $\;\;\exists\bb\in[\pow(\cc)]^\om$ 
 $\;\;\aa\su\bsi0\om_1(\bb)$.
\item there is a family of size $\ka$ of sets of reals which is
not include in a bounded level of any countably generated
$\si$-algebra. $\exists \aa\in [\pow(\cc)]^\ka$ 
$\;\;\forall\bb\in[\pow(\cc)]^\om$ $\forall \al<\om_1$
 $\;\;\aa\not\su\bsi0\al(\bb)$.
\end{enumerate}
\end{theorem}
\proof
Let $\Gamma\su\om_1$ be unbounded so that for every $\al\in\Gamma$
there exists a strong $Q_\al$-set $X_\al\su 2^\om$.  Note
that for $\al<\be$ elements of $\Gamma$ that $|X_\al|<|X_\be|$.
Let $\ka_\al=|X_\al|$ and put $\ka=\sup_{\al\in \Gamma}\ka_\al$.  
Given
any family $\aa\su \pow(\cc)$ of size $\ka$ of write 
$\aa=\bigcup\{\aa_\al:\al\in\Gamma\}$ where $|\aa_\al|=\ka_\al$.
By Theorems \ref{bbmthm9},\ref{strongqrectangle} 
 $\aa_\al$ is included in the $\si$-algebra generated
by a countable set $\bb_\al$,
i.e., $\aa_\al\su \bsi0\al(\bb_\al)$. 
but then $\bigcup\{\bb_\al:\al\in\Gamma\}$
is included in a countably generated $\si$-algebra and hence so
is $\aa$.   This proves item (1).


To prove (2) note that for each $\al\in\Gamma$ there is
$\aa_\al\su\pow(\cc)$ of cardinality $\ka_\al$ which is not in any
countably generated $\si$-algebra at a level before $\al$,
i.e., $\aa_\al\not\su \bsi0\be(\bb)$
for any countable $\bb\su\pow(\cc)$ and $\be<\al$.
It follows that $\aa=\bigcup_{\al\in\Gamma}\aa_\al$ satisfies
(2).

\qed




\section{Universal Functions of Higher Dimension}

The main result of this section is from 
(\cite{univ}).  Universal functions $F$ of higher dimensions reduce
to countably many cases where the only thing that matters is
the arity of the parameter functions, e.g., one of the forms:

$G(x,y)=F(h(x),k(y))$

$G(x,y,z)=F(h(x,y),k(y,z),l(x,z))$

$G(x_1,x_2,x_3,x_4)=F(h(x_2,x_3,x_4),k(x_1,x_3,x_4),
l(x_1,x_2,x_4),i(x_1,x_2,x_3))$

$\ldots$

$G(x_0,\ldots,x_{n})=F(\vec{x}_s:s\in [n+1]^n)$

$\ldots$

\medskip\noindent Furthermore, each of these forms is consistently weaker than
the preceding one.


\def\cantor{{2^\om}}
\begin{define}
A $k$-dimensional universal function is a function $$F:(\cantor)^k \to \cantor$$
such that for every function $G:(\cantor)^k \to \cantor$ there is
$h:\cantor \to \cantor$ such that
$$G(x_1,x_2,\ldots,x_k) = F(h(x_1),h(x_2),\ldots,h(x_k))$$
for all $(x_1,x_2,\ldots,x_k) \in (\cantor)^k$.
\end{define}

\begin{prop}
Suppose $F(x,y)$ is a universal function, then $F(F(x,y),z)$ is
a 3-dimensional universal function.  Similarly the existence of a universal function in 
dimension 2 is
equivalent to the existence of a universal function in dimension k
for any $k>1$.
\end{prop}
\proof
Given $G(x,y,z)$ define $G_0(u,z)=G(u_0,u_1,z)$ using unpairing,
$u=\pair(u_0,u_1)$.  By universality of $F$ there are
$g,h$ with $G_0(u,z)=F(g(u),h(z))$.  Again by universality
of $F$ there are $g_0,g_1$ with $g(\pair(u_0,u_1))=F(g_0(u_0),g_1(u_1))$
and hence $G(x,y,z)=F(F(g_0(x),g_1(y)),h(z))$.

To prove a 3-dimensional implies a 2-dimensional use unpairing,
i.e., put $\hat{F}(u,y)= F(u_1,y,u_2)$ so if $G(x,y)=F(h(x),k(y),j(z))$,
then putting  $\hat{h}(x)=\langle h(x),j(0)\rangle$ we have
$G(x,y)=F(h(x),k(y),j(0))=\hat{F}(\hat{h}(x),k(y)).$

\qed

This proposition is true for either Borel or abstract 
universal functions, but note however that the Baire complexity of
$F(F(x,y),z)$ is higher than that of $F$.   The question
``Is it consistent that the Borel rank in different dimensions
is different ?'', is open.

Juris Steprans recently pointed out (Feb 2017) that the obvious
attempt to prove 
that a 3-dimensional universal function implies the existence of a 
2-dimensional universal function, namely
freezing a coordinate, may not work; i.e.,
putting $\hat{F}(x,y)=F(x,y,z_0)$, because different $G$ might
require different $z_0$.  However, it almost works.
Here is his proof:  
Suppose $F:\ka^3\to\ka$ is universal, i.e., for every 
$G:\ka^3\to\ka$ there are $h,k,j:\ka\to\ka$ such that
$G(x,y,z)=F(h(x),k(y),j(z))$ for all $x,y,z\in\ka$.
Let $A_z\su\ka$ for $z\in\ka$ partition $\ka$ into sets
of size $\ka$.  Define $F_z(x,y)=F(x,y,z)$. 
Then we claim that for some $z$ the
map $F_z$ restricted to $A_z\times A_z$ is universal for
all maps from $A_z\times A_z$ to $\ka$.  Suppose not.
For each $z$ let $G_z:A_z\times A_z \to \ka$ witness 
that it is not universal.  Take any $G:\ka\times\ka\to\ka$ 
which extends all $G_z$.  Since $F$ is universal there are
$h,k,j$ with $G(x,y)=F(h(x),k(y),j(z))$ all $x,y,z\in\ka$.
Letting $z_0=j(0)$ gives us that
$$G_{z_0}(x,y)=G(x,y)=F(h(x),k(y),z_0)=F_{z_0}(h(x),k(y))
\mbox{ for all } x,y\in A_{z_0}$$
which contradicts the choice of $G_{z_0}$.

This argument requires that we restrict to a subset $A_z$
of $\ka$, we don't know if there could be a 3-dimensional
universal $F$ such no $F_z$ is 2-dimensional 
universal with respect to maps on all of $\ka^2$.

We may also consider universal functions $F$ where the parameters
functions are functions of more than one variable, for
example: $$\forall G\;\exists g,h,k\;\forall x,y,z\;\;\;
G(x,y,z)=F(g(x,y),h(y,z),k(z,x)).$$   This form easily
follows from the existence of a dimension 3 universal.
Note that by using pairing functions we can always combine parameter
functions which have the same sequence of variables.
The reader can imagine many variants.
For example,

$G(x,y,z)=F(g(x,y),h(y,z))$

$G(x_1,x_2,x_3,x_4)=F(g_1(x_1,x_2),g_2(x_2,x_3),g_3(x_3,x_4),g_4(x_4,x_1))$

\noindent where we have omitted quantifiers for clarity.
These two variants are equivalent to the existence of
2-dimensional universal function.  To see this in the
first example put $y=0$ and
get

$G(x,z)=F(g(x,0),h(0,z))$.

\noindent In the second example put $x_2=x_4=0$ and get

$G(x_1,x_3)=F(g_1(x_1,0),g_2(0,x_3),g_3(x_3,0),g_4(0,x_1))$.

\noindent
More generally, suppose $F$ and $\vec{x_k}$'s have the property that
for every $G$ there are $g_k$'s such that for all $\vec{x}$
$$G(\vec{x})=F(g_1(\vec{x}_1),\ldots,g_n(\vec{x}_n)).$$
Suppose there are two variables $x$ and $y$ from $\vec{x}$ which
do not simultaneously belong to any $\vec{x}_k$.  Then we
get a universal 2-dimensional function simply by putting
all of the other variables equal to zero.

\begin{prop}
If there  is a $(3,2)$-dimensional universal function, i.e., an $F(x,y,z)$
such that for every $G$ there is $h$ with
$$G(x,y,z)=F(h(x,y),h(y,z),h(z,x))\mbox{ all }x,y,z$$
then for every $n>3$ there is a $(n,2)$-dimensional universal
function $F$, i.e., for every $G$ n-ary there is a binary $h$ with
$$G(x_1,x_2,\ldots,x_n)=F(\la h(x_i,x_j):1\leq i<j\leq n\ra)
\mbox{ all }\vec{x}.$$
$F$ is $\comb(n,2)$-ary.
Conversely, if there is a $(n,2)$-dimensional universal
function for some $n>3$, then there is a $(3,2)$-dimensional universal
function.
\end{prop}
\proof
Consider the case for $n=4$.

Suppose that $F$ is  $(3,2)$-dimensional
universal function.  Given a 4-ary function $G(x,y,z,w)$ for each
fixed $w$ we get a function $h_w(u,v)$ with
$$G(x,y,z,w)=F(h_w(x,y),h_w(y,z),h_w(z,x))\mbox{ for all } x,y,z.$$
But now considering $h(u,v,w)=h_w(u,v)$ we get a function
$k(s,t)$ with $h(u,v,w)=F(k(u,v),k(v,w),k(w,u))$.
Note that

\noindent $\;\;\;\;\;\;G(x,y,z,w)=$

$\;\;\;\;\;\;F(F(k(x,y),k(y,w),k(w,x)),$

$\;\;\;\;\;\;\;\;\;\;\;\;F(k(y,z),k(z,w),k(w,y)),$

$\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;F(k(z,x),k(x,w),k(w,z))).$

\noindent Note that
$k(s,t)$ and $k(t,s)$ can
be combined by pairing and unpairing into a single function $k_1(s,t)$.
From this one can define a $(4,2)$-dimensional
universal function.

For the converse, if $F$ is a $(4,2)$-dimensional
universal function, then for every $G$ 3-ary, there exists
$h$ binary with
$$G(x,y,z)=F(h(x,y),h(y,z),h(x,z),h(x,0),h(y,0),h(z,0)).$$
But note that, for example, $h(x,y)$ and $h(x,0)$ can
be combined into a single function of $h_1(x,y)$.  Hence
we can get a $(3,2)$-dimensional
universal function.
\qed

To state the generalization of these ideas
\begin{define}\label{def29}
Let $U(\ka,m,n)$ mean that we have
a $(m,n)$-dimensional universal function on $\ka$.
This means for $k=\comb(n,m)$ there exists $F:\ka^{k}\to\ka$ such that
for every $G:\ka^m\to\ka$ there is $h:\ka^n\to\ka$
such that
$$G(x_0,x_1,\ldots,x_{m-1})=F\left(h(x_j:j\in Q):Q\in [m]^n\right)
\mbox{ for all } \vec{x}\in \ka^m.
$$

\end{define}

Then the last two propositions can be generalized to show:

\begin{prop}\label{propmn}
For any infinite cardinal $\ka$ and positive integer $n$
\begin{enumerate}
\item $U(\ka,n+1,n)$ implies $\forall m>n\;\; U(\ka,m,n)$.
\item ($\exists m>n\;\; U(\ka,m,n)$) implies $U(\ka,n+1,n)$.
\item $U(\ka,n+1,n)$ implies $U(\ka,n+2,n+1)$
\end{enumerate}
\end{prop}

We show that $U(\ka,n+1,n)$ are the only generalized
multi-dimensional universal functions properties.


\begin{define}\label{def31}
Suppose $\Sigma\su \pow(\{0,1,2,\ldots,n-1\})=\pow(n)$ (the power set of $n$).
Define
$U(\ka,n,\Sigma)$ to mean that there exists
$F:\ka^{\Sigma}\to\ka$ such that
for every $G:\ka^n\to\ka$ there are $h_Q:\ka^{|Q|}\to\ka$
for $Q\in\Sigma$
such that
$$G(x_0,x_1,\ldots,x_{n-1})=F\left(h_Q(x_j:j\in Q):Q\in\Sigma\right)
\mbox{ for all } \vec{x}\in \ka^n.
$$
\end{define}

\begin{prop}
Let $\ka$ be an infinite cardinal, $n\geq 2$, and $\Sigma,\Sigma_0,\Sigma_1$
subsets of $\pow(n)$.
\begin{enumerate}
\item If $\Sigma_0\su \Sigma_1$ , then
$U(\ka,n,\Sigma_0)$ implies $U(\ka,n,\Sigma_1)$.
\item If $Q_0\su Q_1\in\Sigma$, then
$U(\ka,n,\Sigma)$ is equivalent to $U(\ka,n,\Sigma\cup\{Q_0\})$.
\item Suppose $\Sigma$ is closed under taking subsets,
every $k<n$ is in some element of $\Sigma$, and
$\{0,1,2,\ldots,n-1\}\notin\Sigma$.  Let $k+1$ be the size
of the smallest subset of $\{0,1,2,\ldots,n-1\}$ not in $\Sigma$.
Then $U(\ka,n,\Sigma)$ is equivalent to $U(\ka,k+1,k)$.
\end{enumerate}
\end{prop}
\proof
$\;\;\;\;$
(1) This is true because the $F$ which works for $\Sigma_0$ also works
for $\Sigma_1$ by ignoring the values of $h_Q$ for $Q\in \Sigma_1\sm\Sigma_0$.

(2) This is true because given $h_{Q_0},h_{Q_1}$ we may define
a new $\hat{h}_{Q_1}$ by outputting the pairing
$$\hat{h}_{Q_1}( x_j:j\in Q_1)=
\la (h_{Q_0}(x_j:j\in Q_0),(h_{Q_1}(x_j:j\in Q_1)\ra$$

(3)  First note that by (2) we may as well assume that
$\Sigma$ is closed under taking subsets. If some $k$ does
not appear in any element of $\Sigma$, then
$U(\ka,n,\Sigma)$ is trivially false.  If $\{0,1,2,\ldots,n-1\}$
is in $\Sigma$, then $U(\ka,n,\Sigma)$ is trivially true.

So let $R\su\{0,1,\dots n-1\}$ not in $\Sigma$ with $|R|=k+1$.
By choice of $k+1$ all subsets of $R$ of size $k$ are in $\Sigma$.
By setting $x_i=0$ for $i\notin R$, we see that
$U(\ka,k+1,k)$ is true.

Now assume $U(\ka,k+1,k)$ is true.
By Proposition \ref{propmn} we have that $U(\ka,n,k)$ is true and
hence if $\Sigma_0=[n]^k$ then $U(\ka,n,\Sigma_0)$ is true.
But $\Sigma_0\su \Sigma$ and so by (1), $U(\ka,n,\Sigma)$
is true.
\qed


\begin{prop} \label{prop33}
The following are true in ZFC.
\begin{enumerate}
\item $U(\om,2,1)$
\item $U(\om_1,3,2)$
\item $U(\ka,2,1)$ implies $U(\ka^+,3,2)$
\item $U(\ka,n+1,n)$ implies $U(\ka^+,n+2,n+1)$
\item $U(\om_n,n+2,n+1)$ every $n\geq 0$.
\end{enumerate}
\end{prop}
\proof
For (1) see Theorem \ref{abstractuniv}.
We prove (2) and leave 3-5 to the reader.

Suppose that $f:\om^2\to\om$ witnesses
$U(\om,2,1)$.  For any countable ordinal $\de>0$ let
$\de=\{\de_i:i<\om\}$. Define
$$F_0(\de,n,m)=\de_{f(n,m)}.$$
Now suppose $G:\om_1^3\to\om_1$.  Define
$$k(\de)=\sup\{G(\al,\be,\ga)\;:\;\al,\be,\ga\leq\de\}+1$$
For any $\ga<\om_1$ let $\ga^*=k(\ga)$.
Define $g:\om^2\to\om$ by
$$G((\ga+1)_n,(\ga+1)_m,\ga))=\ga^*_{g(n,m)}.$$
By the universality property of $f$ there exists
$h:\om\to\om$ with
$$g(n,m)=f(h(n),h(m)) \mbox{ for every } n,m\in\om.$$
For $\de\leq \ga$
define
$h_1(\de,\ga)=h(k)$ where $\de=(\ga+1)_k$.   Then we have
that
$$\forall \al,\be\leq\ga<\om_1\;\;\;
G(\al,\be,\ga)=F_0(k(\ga),h_1(\al,\ga),h_1(\be,\ga)).$$

Define $F$ as follows:

\medskip
\noindent
$F(\al,\be,\ga,\al^*,\be^*,\ga^*,n_1,m_1,n_2,m_2,n_3,m_3)=$
$$
\left\{
\begin{array}{ll}
F_0(\ga^*,n_1,m_1) & \rmif \al,\be\leq\ga \\
F_0(\be^*,n_2,m_2) & \rmif \ga < \be \rmand \al\leq\be \\
F_0(\al^*,n_3,m_3) & \rmif \be,\ga < \al \\
\end{array}\right.
$$

Then given $G$ we can find $k,h_1,h_2,h_3$ so that

\noindent $G(\al,\be,\ga))=$

$F(\al,\be,\ga,k(\al),k(\be),k(\ga),$

$\;\;\;\;\;\;\;\;\; h_1(\al,\ga),h_1(\be,\ga),\;\;
h_2(\al,\be),h_2(\ga,\be),\;\; h_3(\be,\al),h_3(\ga,\al)).
$

\qed

The $\ka$-Cohen real model is any model of ZFC obtained
by forcing with the poset of finite partial functions from $\ka$ to
2 over a countable transitive ground model satisfying ZFC.

\begin{prop}\label{prop34}
In the $\om_2$-Cohen real model
we have that
$U(\om_1,2,1)$ fails.  Similarly, $U(\om_2,3,2)$
fails in the $\om_3$-Cohen real model.
More generally, we have that
$U(\ga,n+1,n)$ fails in the $\ka$-Cohen real model
when $\ka>\ga\geq \om_n$.
\end{prop}
\proof
We show that $U(\om_2,3,2)$
fails in the $\om_3$-Cohen real model, leaving the rest
to the reader.

Let $M$ be a countable transitive model of ZFC and
in $M$ define $\poset$ to be the poset of finite partial
maps from $\om_3\times\om_3\times\om_3$ into 2.  We claim that if
$G$ is $\poset$-generic over $M$, then there is
no map $F:\om_2\times\om_2\times\om_2\to \om_2$
which is (3,2)-universal for maps
of the form $H:\om\times\om_1\times\om_2\to 2$.

Suppose for contradiction that $F$ is such a map.
By the ccc we may find $\ga_0<\om_3$ with $F\in M[G\res\ga_0^3]$.
Hence we may find maps $h_1:\om\times\om_1\to\om_3$,
$h_2:\om\times\om_2\to\om_3$, and
$h_3:\om_1\times\om_2\to\om_3$ such that
$$H(n,\be,\ga)=^{def}G(n,\be,\ga_0+\ga)=F(h_1(n,\be),h_2(n,\ga),h_3(\be,\ga)).$$
for every $n<\om,\be<\om_1,\ga<\om_2$.
 By ccc we can choose
$\ga_1<\om_2$ such that $h_1\in M[G^*]$ where
$G^*$ is $G$ restricted $\{(\al,\be,\rho)\in\om^3\;:\;\rho\neq \ga_0+\ga_1\}$.
Define $g:\om\times\om_1\to 2$ by
$$g(n,\al)=G(n,\al,\ga_0+\ga_1)$$
Note that we have that $F,h_1\in M[G^*]$, $g$ is
Cohen generic over $M[G^*]$, and
$$g(n,\al)=F(h_1(n,\al),h_2(n,\ga_0+\ga_1),h_3(\al,\ga_0+\ga_1)).$$

Since the extension by $g$ is ccc, we may find $\al_0<\om_1$
such that
$$h_2\in M[G^*][g\res (\om\times\al_0)]=^{def}N.$$
But this is
a contradiction because $g_{\al_0}$ defined by $g_{\al_0}(n)=g(n,\al_0)$
is Cohen generic over $N$.
But $F,h_1,h_2\in N$ and for any $\ga_2<\om_2$ the map $k$ defined by
$$k(n)=F(h_1(n,\al_0),h_2(n,\ga_0+\ga_1),\ga_2)
\mbox{ for all } n<\om$$
is in $N$ and so can never be equal to $g_{\al_0}$.
Thus $h_3(\al_0,\ga_0+\ga_1)=\ga_2$ cannot be defined.
\qed

\begin{cor}
(\cite{univ}) 
Let  $\aleph_\om\leq\ga<\ka$.  In the
$\ka$-Cohen real model we have that
$$U(\om_n,n+2,n+1)+\neg U(\om_n,n+1,n) \mbox{ for all }n>0,$$
and $$\neg U(\ga,n+1,n) \mbox{ for all }n>0 .$$
Hence, in the Cohen real model for every $n\geq 1$ 
there is a universal function on $\om_n$ where the parameter 
functions have arity
$n+1$ but no universal function where the parameters functions have arity $n$.
\end{cor}

\section{Model Theoretic Universal}

\begin{thm}\label{answer7.13}
(Remark 7.13 \cite{univ}.)
If  $2^{<\cc}=\cc$ and there is a Borel universal map, i.e. 
Borel $F:2^\om\times 2^\om\to 2^\om$ such that for
every $G:2^\om\times 2^\om\to 2^\om$ there is $h$ such that
$G(x,y)=F(h(x),h(y))$ for all $x\in 2^\om$,
then there is a Borel map $H$ such that for every cardinal
$\ka<\cc$ 
for every $G: \ka \times \ka \to \ka$ there are 
$x_\al\in 2^\om$ for $\al <\ka$
such that for $\al,\be,\ga<\ka$
$$G(\al,\be)=\ga  \rmiff H(x_\al,x_\be)=x_\ga$$
\end{thm}
\proof

By Theorems \ref{bbmbdd}, Lemma \ref{bbmlem}, and Theorem \ref{mainthmuniv}
there exists $\al<\om_1$, $Z\su 2^\om$ with $|Z|=\cc$ and every $Y\in [Z]^{<\cc}$
is $\bsi0\al$ in $Z$.  Note that by 
Lemma \ref{rectangle} $\;\;\pow(\cc\times\cc)=\si(\{A,B:A,B\su\cc\})$, so
if $X\su Z$ of size $\ka$ then every subset of $X^2$ is 
$\bsi0{\al_0}$ in $X^2$ where $\al_0=\al+\al$.  

Let $X=\{x_\al:\al<\ka\}$.   Given any map $G:\ka\times\ka\to\ka$ define
$$Y_n=\{(x_\al,x_\be)\;:\; G(\al,\be)=\de \rmand x_\de(n)=1\}$$
for each  $n$.
   Let $B_n\su 2^\om\times 2^\om$ be $\bsi0{\al_0}$ so that
$Y_n=B_n\cap(X\times X)$.   Define the Borel map $K$ by
$K(u,v)(n)=1$ iff $(u,v)\in B_n$.  Note that
$$G(\al,\be)=\de\rmiff K(x_\al,x_\be)=x_\de.$$
Let $L$ be Borel and universal for all such maps $K$,  i.e.,
For all Borel $K$ of rank less than $\al_0+1$ there is a $y$
such that $\forall u,v \; K(u,v)=L(y,u,v)$.  Now define
$H((y,u),(y,v))=(y,L(y,u,v))$.  Putting $\hat{x}_\al=(y,x_\al)$ we
have that for every $\al,\be,\de$
$$H(\hat{x}_\al,\hat{x}_\be)=\hat{x}_\de \rmiff G(\al,\be)=\de.$$
\qed


\section{Generic Souslin sets}

\begin{thm}
(Marczewski see Miller\cite{ramsey}) If $I$ is a ccc $\si$-ideal in
the Borel sets then the family of $I$-measurable sets is closed
under the Souslin operation.
\end{thm}

\begin{thm}(\cite{dstfor})
(CH) For any $\al$ with $2\leq \al \leq \om_1$ there is exists
an uncountable $X\su 2^\om$ such that $\ord(X)=\al$ and
every Souslin set in $X$ is Borel in $X$.
\end{thm}

\begin{thm}
(Miller \cite{gensous}) It is consistent to have $X\su 2^\om$ such
that every subset of $X$ is Souslin in $X$ and the Borel order
of $X$ is $\om_1$.
\end{thm}
The set $X$ also has the property that
$\pow(X)$ is not a countably generated $\si$-algebra.


\begin{thm}
(\cite{gensous}) It is relatively consistent with ZFC that for every subset 
$A\su 2^\om\times 2^\om$
there are abstract rectangles $B_s\times C_s$ with
$$A=\bigcup_{f\in\om^\om}\;\bigcap_{n<\om} \;(B_{f\res n}\times C_{f\res n})$$
but not every subset of $2^\om\times 2^\om$ is in the $\si$-algebra
generated by the abstract rectangles.
\end{thm}

\section{Products and Unions}

\begin{thm}
(Sierpinski 1935) Assume CH.   There Luzin sets and Sierpinski
sets whose square can be continuously mapped onto $2^\om$.
\end{thm}

\begin{cor}
(CH) For any  $\al$ with $2\leq \al<\om_1$ there is $X\su 2^\om$ such that
$$\ord(X)=\al \rmand \ord(X^2)=\om_1$$
\end{cor}
\proof
Let $S\su 2^\om$ be a Sierpinski set whose square continuously maps onto $2^\om$.
Let $X_\al$ have order $\al$ (which exists by CH \cite{hier}), then the 
clopen separated union
$X=S\oplus X_\al$ has order $\al$ and its square has order $\om_1$
by Reclaw \ref{rec}.

\begin{thm}
(Miller \cite{special}) (CH) There is an uncountable $\si$-set
$X\su 2^\om$ which is concentrated on a countable set.  ($\si$-set
means $\ord(X)=2$.)
\end{thm}

\begin{thm}
(Fleissner, Miller \cite{qsets}) It is relatively consistent
with ZFC to have an uncountable Q-set which is concentrated on
a countable set.
\end{thm}

\def\dom{\mbox{dom}}

\begin{thm}\label{newunion}
(CH) For any $\al_0$ with 
$3\leq \al_0<\om_1$ there are $X_0,X_1\su 2^\om$ with
$\ord(X_0)=\al_0=\ord(X_1)$ and $\ord(X_0\cup X_1)=\al_0+1$.
\end{thm}
\proof

Let $T$ be a nice $\al_0$-tree (see Definition \ref{nicetree}). 

\begin{define}
Define
$\poset_T$ by $p\in\poset_T$ iff $p:T\to 2$ is a finite partial
function such that for all $s\in T^0$ and $n<\om$ if $s,sn\in\dom(p)$ 
and $p(s)=1$, then $p(sn)=0$.  Define the rank of $p$:
$|p|=\max\{\rank_T(s)\;:\; s\in\dom(p)\}.$
\end{define}

\begin{lemma} Rank Lemma.
For all countable $\be\geq 1$ for all $p\in\poset_T$ there exists
$\hat{p}\in\poset_T$ compatible with $p$, $|\hat{p}|\leq\be$, and
for all $q\in\poset_T$ with $|q|<\be$, 
$({p}\perp q) \rightarrow (\hat{p}\perp q)$.
\end{lemma}
\proof
As usual $\perp$ stands for incompatible.  First extend $p$ to
$p^*$ which has the property that for any $s\in\dom(p)$ 
with $p(s)=1$ and $\rank_T(s)=\lambda$ a limit ordinal greater than
$\be$ and $n$ such
that $\rank_T(sn)<\be$ there exists $m$ such that $p^*(snm)=1$.  Note that by the
definition of nice tree there are at most finitely many $sn$.

Now define $\hat{p}=p*\res\{s\in\dom{p^*}:\rank_T(s)\leq\be\}$.  Suppose
$|q|<\be$ and $p\perp q$.  So one of the following must be true:
\begin{enumerate}
\item There exists $s\in\dom(q)\cap\dom(p)$ with $p(s)\neq q(s)$.
\item There exists $s\in\dom(q)$ and $sn\in\dom(p)$ with $q(s)=1$ and $p(sn)=1$.
\item There exists $s\in\dom(p)$ and $sn\in\dom(q)$ with $p(s)=1$ and $q(sn)=1$.
\end{enumerate}
In the first case since $|q|<\be$ we have that $s\in\dom(\hat{p})$ so
$\hat{p}\perp q$.  In the second case $\rank_T(sn)<\rank_T(s)<\be$ so
again $\hat{p}\perp q$.  In the third case $\rank_T(sn)<\be$ so either
$\rank_T(s)\leq \be$ (so $\hat{p}\perp q$) or 
$\rank_T(s)=\lambda>\be$ a limit ordinal.  By
the construction of $p^*$ there is some $m$ with $p^*(snm)=1$.  Since
$\hat{p}(snm)=1$ and $q(sn)=1$ it follows that $\hat{p}\perp q$.

\qed

\begin{define}
For $G$ sufficiently $\poset_T$-generic, its union, $\bigcup G$, will
be a map from $T$ into $2$.  Let $g$ be the restriction of $\bigcup G$
to $T^*$, the terminal nodes of $T$.  So $g:T^*\to 2$ is defined by
$g(s)=i$ iff $\exists p\in G$ with $p(s)=i$.
\end{define}

\begin{lemma}\label{neat}
Suppose $\al\geq 1$, $B(v)$ is a $\bsi0\al$ predicate on $2^{T^*}$ coded
in $M$, and $p\in\poset_T$.   If $p\forces B(\name{g})$, then there
exists $\hat{p}$ compatible with $p$, $|\hat{p}|<\al$, and
$\hat{p}\forces B(\name{g})$.
\end{lemma}
\proof

Case $\al=1$.  Suppose ($B(v)\iff \exists n \;C_n(v)$) where $C_n$ are
clopen.   Take $q\leq p$ and $n$ so that $q\forces C_n(\name{g})$.
By extending $q$ we may assume that $C_n(f)$ holds for all $f\in T^*$ with
$q\res T^*\su f$.  Then $\hat{p}=^{def}q\res T^*$ is as required.

Case $\al>1$. Suppose ($B(v)\iff \exists n \;B_n(v)$) where $B_n$
is $\bpi0{\be_n}$ for some $\be_n<\al$.   Let $p_1\leq p$ and $n<\om$ be
such that $p_1\forces B_n(\name{g})$.  Let $\hat{p_1}$ be obtained from
the Rank Lemma for $\be=\be_n$.  
Then it must be that $\hat{p_1}\forces B_n(\name{g})$.
Otherwise there exists $p_2\leq \hat{p}_1$ such that 
$p_2\forces \neg B_n(\name{g})$.
By induction there $q$ compatible with $p_2$ (and hence with $\hat{p_1}$),
$|q|<\be_n$ and $q\forces \neg B_n(\name{g})$.  But by the Rank Lemma
such a $q$ would be compatible with $p_1$, contradiction.

\qed

\begin{lemma}
If $B(v)$ is a $\bsi0\al_0$ predicate on $2^{T^*}$ coded
in $M$, then there exists $G$ $\poset_T$-generic over $M$ such 
that $B(g)$ iff $G(\langle\rangle)=0$.
\end{lemma}
\proof
If not, $1\forces$ ``$B(\name{g})\rmiff G(\langle\rangle)=1$''.
Let $p=(\langle\rangle,1)$, so $p\forces G(\langle\rangle)=1$ and
therefor $p\forces B(\name{g})$. 
By the Lemma \ref{neat} there is $q$ compatible with $p$,
$|q|<\al_0$ and $q\forces B(\name{g})$.
But note that $q^*=q\cup \{(\langle\rangle,0)\}$ is a condition
because $\langle\rangle$ is not in the domain of
$q$ since it has rank $\al_0$.   But
$q^*\forces$`` $G(\langle\rangle)=0\rmand B(\name{g})$'' 
which is a contradiction.
\qed

Now we prove Theorem \ref{newunion}.  Let
$M_\be\elemsub H_\ka$ for $\be<\om_1$ be countable elementary substructures
of $H_\ka$ for some sufficiently large regular $\ka$, so that
$\be<\ga$ implies $M_\be\elemsub M_\ga$ and $\pow(\om)\su \bigcup_{\be<\om_1}M_\be$.
Choose $G_\al$ $\poset_T$-generic over $M_\al$ with the property that
for any $B(v)$ a $\bsi0\al_0$ predicate on $2^{T^*}$ for some $\al$
$B(g_\al)$ iff $G_\al(\langle\rangle)=0$.   Let
$X=\{g_\al\in 2^{T^*}:\al<\om_1\}$ and for $i=0,1$ let
$X_i=\{g_\al\;:\; G_\al(\langle\rangle)=i\}$. 
Define $U_s\su 2^{T^*}$ for $s\in T$ as follows.
$U_s=\{x\in 2^{T^*}\;:\; x(s)=1\}$.   For $s\in T^0$
$\;\;\;U_s=\bigcap_{n<\om}\sim U_{sn}$.  Note that if
$\rank_T(s)=\be$ then $U_s$ is $\bpi0\be$.  Therefor
since $U_{\langle\rangle}\cap X= X_1$ we have that 
$X_1$ is a $\bpi0{\al_0}$ subset of $X$ which by construction
is not $\bsi0\al_0$.  So $\ord(X)\geq\al_0+1$.

Define for $p\in\poset_T$
$[p]=\bigcup\{U_s\;:\; p(s)=1\}\cup\bigcup\{\sim U_s\;:\; p(s)=0\}$.
Note that $[p]$ is $\bde0{\al_0+1}$.  For any Borel $B\su 2^{T^*}$ there
is an $\al<\om_1$ with $B$ coded in $M_\al$.  For all $\ga\geq\al$
$G_\ga$ is $\poset_T$-generic over $M_\ga$ and hence
$$g_\ga\in B\rmiff \exists p\in G_\ga\;\; p\forces g_\ga\in B.$$
Note that by Borel absoluteness
$g_\ga\in B\rmiff M_\ga[g_\ga]\models g_\ga\in B.$
Let $$\Sigma=^{def}\{p\in\poset_T\;:\;p\forces \name{g}\in B\}.$$
Let $X^{\geq\al}=\{g_\ga\;:\;\ga\geq\al\}$.  Then 
$$X^{\geq\al}\cap B= X^{\geq\al}\cap \bigcup_{p\in\Sigma}[p].$$  
Since we add and subtract a countable set from any $\bde0{\al_0+1}$ set
and remain $\bde0{\al_0+1}$, we see that $\ord(X)\leq\al_0+1$.

For any $p\in\poset_T$ and $i=0,1$ we have that
$[p]\cap X_i$ is $\bde0\al_0$ since it is either empty (if $p(\langle\rangle)=1-i$)
or equal to $[p^*]\cap X_i$ where $p^*=p\sm\{(\langle\rangle,i)\}$.
It follows that $\ord(X_i)\leq \al_0$.

To get an example with order exactly $\al_0$:  
Either by modifying the above construction or
using the Luzin set argument from \cite{hier} Thm 18, we
can get $Y\su 2^\om$ with
order exactly $\al_0$.
Let $X^+_i=^{def}X_i\oplus Y$ where $\oplus$ means to take
a clopen separated union.  Then $\ord(X_i^+)=\al_0$ and
$X_0^+\cup X_1^+=X\oplus Y$ has order $\al_0+1$.

This proves Theorem \ref{newunion}.   

Note that in case $\al_0$ is a
successor order we can use the above proof to get $Z_0,Z_1$
such that  $\ord(Z_0)=\al_0$,
$\ord(Z_1)=\al_0-1$, and $\ord(Z_0\cup Z_1)=\al_0+1$.
To see this note that since $p(\langle\rangle)=1$ implies
$p(\langle n\rangle)=0$ for all $\langle n\rangle\in\dom(p)$ we have that
$\ord(X_1)\leq\al_0-1$.  Take $Y^\prime$ with $\ord(Y^\prime)=\al_0-1$
and put $Z_0=X_0\oplus Y \oplus \emptyset$ and
$Z_1=X_1\oplus \emptyset \oplus Y^\prime$.

\section{Invariant Descriptive Set Theory}

For $\rho$ a countable similarity type let 
$X_\rho$ be the Polish space of $\rho$-structures with universe
$\om$.   For example if $\rho=\{R,f,U,c\}$ where $R$ is a binary relation
symbol, $f$ a binary operation symbol, $U$ a unary operation symbol and
$c$ a constant symbols then 
$$X_\rho= 2^{\om\times\om}\times \om^{\om\times\om}\times 2^\om \times \om.$$
The language $L_{\om_1,\om}(\rho)$ is obtained by adding countably infinite
conjunctions and disjunctions to the usual first order logical axioms.
For example:
$$\forall y \disj_{n<\om} \exists x_1,x_2,\ldots x_n\; \forall z
(R(z,y)\to \vee_{i=1}^n z=x_i)$$
which says that for every $y$ there are at most finitely many
$z$ with $R(z,y)$.

We consider only formulas with at most finitely many free variables.
Inductively define $\Sigma_\al$ and $\Pi_\al$ formulas as follows:
$\Sigma_0=\Pi_0$ formulas are the ordinary first-order
quantifier free finite formulas.  For $\al>0$ a formula
$\phi(\vec{y})$ is $\Sigma_\al$ iff there are
$\phi_n(\vec{x_n},\vec{y})$ each a $\Pi_{<\al}$ formula and
$$\phi(\vec{y})=\disj_{n<\om}\exists \vec{x_n}\phi_n(\vec{x_n},\vec{y}).$$
A formula $\phi(\vec{y})$ is $\Pi_\al$ iff there are
$\phi_n(\vec{x_n},\vec{y})$ each a $\Sigma_{<\al}$ formula and
$$\phi(\vec{y})=\conj_{n<\om}\forall \vec{x_n}\phi_n(\vec{x_n},\vec{y})$$

\begin{thm}
(Mostowski see Kuratowski \cite{kur} page ???)
If $\theta$ is a $\Sigma_\al$ sentence of 
$L_{\om_1,\om}(\rho)$,
then the set of models of $\theta$ is a $\Sigma_\al^0$ Borel
subset of $X_\rho$.
\end{thm}
\proof
For any $n$ and formula $\theta(\vec{x})$
where $\vec{x}=x_0,\ldots,x_{n-1}$ includes all free variable of $\theta$
and any $s\in \om^n$ consider the models of $\theta(s)$:
$$\{M\in X_\rho \;:\; M\models \theta(s(0),s(1),\ldots,s(n-1))\}$$
Details left to reader.
\qed

\begin{thm}
(Scott 1964 see Barwise \cite{barwise}) For any countable structure
$A$ in a countable similarity type $\rho$, there is a sentence
$\theta$ of  $L_{\om_1,\om}(\rho)$ such that for any countable
$\rho$-structure $B$ 
$$A\simeq B \rmiff B\models \theta$$
\end{thm}

A subset of $X_\rho$ is invariant iff it is closed under isomorphism.
Lopez-Escobar (1965) showed that invariant Borel subsets of
$X_\rho$ are the models of an $L_{\om_1,\om}(\rho)$-sentence.
Vaught proved a hierarchy version of this:

\begin{thm}\label{vaug}
(Vaught \cite{vaught}) Any $\Pi_\al^0$ subset of $X_\rho$ which
is closed under isomorphism is the set of models of a
$\Pi_\al$ sentence of $L_{\om_1,\om}(\rho)$
\end{thm}
\proof
Let $S_\infty\su \om^\om$ be the Polish group of bijections of $\om$.
It's action on $X_\rho$ is isomorphism.  For example, given
$\pi\in S_\infty$ and $R\su\om\times\om$ a binary relation, then
$(\om,R)$ is isomorphic to $(\om,S)$ via $\pi$
where $S$ is defined by
$R(x,y)$ iff $S(\pi(x),\pi(y))$.  $S_\infty \times X_\rho \to X_\rho$
$(\pi, R)\mapsto S$ is a continuous action.

The following is the Vaught transform:
For each $n\in\om$ 
and one-to-one map $s:n\to\om$ define
$(A,s)\in \bb^{*n}$ iff there are comeagerly many $\pi\in [s]$ such
that $\pi^{-1}(A)\in \bb$.
For $n=0$ then $\bb^*$ is the set of all
$A\in X_\rho$ for which there are comeagerly many $\pi\in S_\infty$
such that $\pi^{-1}(A)\in \bb$ (or equivalent comeagerly
many $\pi$ with $\pi(A)\in \bb$).

\begin{lemma} \label{countablestar}
Suppose $(\bb_n\su X_\rho:n<\om)$ and $m<\om$, then
$$(\bigcap_{n<\om}\bb_n)^{*m}=\bigcap_{n<\om}\bb_n^{*m}$$
\end{lemma}
\proof
The countable intersection of comeager sets is comeager.
\qed

\begin{lemma} \label{complement}
Suppose $\bb\su X_\rho$ is Borel and $n<\om$, then for any
$s:n\to\om$ one-to-one, 
$$(A,s)\in \bb^{*n} \;\;\rmiff\;\; \neg \exists t \supseteq s
\;\; (A,t)\in  (\sim\bb)^{*|t|}$$
where $\sim\bb$ is the complement of $\bb$.
\end{lemma}
\proof
For any $(A,s)$ the set $\{\pi\in S_\infty \;:\; \pi^{-1}\in\bb\}$ is
the continuous preimage of a Borel set and hence is Borel and so has
the property of Baire.  For a set with the property of Baire, it either
is comeager or its complement is somewhere comeager.
\qed

\begin{lemma}
For any $n,\al\geq 1$ and $\bb\su X_\rho$ a $\Pi^0_\al$ set,
there is a $\Pi_\al$ formula $\theta(\vec{v})$ such that
for any $A\in X_\rho$ and $s:n\to\om$ one-to-one
$$(A,s)\in \bb^{*n} \rmiff (A,s)\models \theta(s(0),\ldots,s(n-1)).$$
\end{lemma}

\proof
First assume $\al=1$ and $\bb\su X_\rho$ is clopen.
Then for some quantifier-free finite formula
$$\bb=\{A\in X_\rho\;:\; A\models \theta(0,1,2,\ldots, m)\}$$
Without loss, we may assume $m>n$.

Then by definition $(A,s)\in \bb^{*n}$ iff $\{\pi\;:\pi^{-1}(A)\in \bb\}$ is
comeager in $[s]$.   But since $\bb$ is clopen,
$\{\pi\;:\pi^{-1}(A)\in \bb\}$ is
comeager in $[s]$ iff
$\pi^{-1}(A) \in \bb$ for all $\pi\supseteq s$.
But now $\pi^{-1}(A) \in \bb$ iff $\pi^{-1}(A)\models \theta(0,1,2,\ldots, m)$.
iff $A\models \theta(\pi(0),\pi(1),\ldots,\pi(m)$.

Hence we get that $(A,s)\in \bb^{*n}$ iff 

\noindent 
$(A,s)\models \forall v_{n},\ldots, v_m \;\;
(D(s,\vec{v})\rightarrow \theta(s(0),\ldots, s(n-1), v(n),\ldots, v(m)))$

where $D$ is the first-order formula saying that the $v_i$ are distinct
and different from all the $s(j)$.

To finish the case of $\al=1$ just use that if $\bb$ is $\Pi^0_1$ then
$\bb=\bigcap_{m<\om}\bb_m$ where each $\bb_m$ is clopen and 
$\bb^{*n}=\bigcap_{m<\om}\bb_m^{*n}$ by Lemma \ref{countablestar}.

Now assume $\al>1$ and $\bb\su X_\rho$ is $\Sigma^0_\be$ for some
$\be<\al$.  Then $\sim \bb$ is $\Pi^0_\be$ and so by Lemma \ref{complement}:
$(s,A)\in \bb^{*n}$ iff $\neg\exists t\supseteq s\; (A,t)\in (\sim \bb)^{*|t|}$
By induction hypothesis 
$(A,t)\in (\sim \bb)^{*|t|}$ iff $(A,t)\models \theta_m(t(0),\ldots, t(m))$
for some $\Pi_\be$ formula $\theta_m$.  And so, 
$(A,s)\in \bb^{*n}$ iff 

\noindent 
$(A,s)\models \forall v_{n},\ldots, v_m \;\;
(D(s,\vec{v})\rightarrow \neg\theta(s(0),\ldots, s(n-1), v(n),\ldots, v(m)))$

Note that this is a $\Pi_{\be+1}$ formula and so a $\Pi_\al$ formula.
To finish this case if $\bb$ is $\Pi^0_\al$ then $\bb=\bigcap_{m<\om}\bb_m$
where $\bb_m$ is $\Sigma^0_{\be_m}$ for some $\be_m<\al$.  Hence applying
Lemma \ref{countablestar} us the result since the countable conjunction
of $\Pi_\al$ formulas is a $\Pi_\al$ formula.
\qed

Vaught's Theorem \ref{vaug} follows immediately from the Lemma for the
case $n=0$ and $\bb$ invariant, i.e., $\bb^*=\bb$.
It also the case that invariant $\Sigma^0_\al$ sets are the models
of a $\Sigma_\al$ sentence by considering complements.



\begin{thm}
(Hausdorff Difference Hierarchy)  $\bb\in \Delta_{\al+1}^0$ iff
there exists a countable sequence of decreasing $\Pi_\al^0$ sets $\bb_\be$
for $\be<\ga$ such that
$$\bb=\bigcup_{\be \mbox{ even }<\ga} \bb_\be\sm \bb_{\be+1}$$
\end{thm}

For a proof see Kuratowski \cite{kur} page-section ???.

\begin{thm}
(Douglas E. Miller \cite{doug}) If $\bb$ is also invariant, then
$$\bb=\bigcup_{\be \mbox{ even }<\ga} \bb_\be^*\sm \bb_{\be+1}^*$$
\end{thm}
\proof
The dual of the Vaught *-transform is
$\bb^\triangle=\sim(\sim \bb^*)$.  Equivalently $A\in \bb^\triangle$ iff
$\pi(A)\in \bb$ for non-meagerly many $\pi\in S_\infty$.  Two other transforms
are 
$$\bb^+=\{A\;:\; \exists \pi\in S_\infty\;\; \pi(A)\in \bb \}\;\;\rmand\;\;
\bb^-=\{A\;:\; \forall \pi\in S_\infty\;\; \pi(A)\in \bb\}.$$

Note that
\begin{enumerate}
\item $\bb^-\su \bb^*\su \bb^\triangle \su \bb^+$ 
\item $\bb$ is invariant iff $\bb^-=\bb^+$
\item $(\bigcup_{n<\om}\bb_n)^\triangle = \bigcup_{n<\om}\bb_n^\triangle$
\item $\bb_1^*\cap \bb_2^\triangle\su (\bb_1\cap \bb_2)^\triangle$
\item $(\sim \bb)^*=\sim \bb^\triangle$
\item $\bb_1^*\sm \bb_{2}^*=\bb_1^*\;\cap\; \sim( \bb_{2}^*)
=\bb_1^*\cap (\sim \bb_{2})^\triangle\su 
(\bb_1\sm \bb_{2})^\triangle $
\end{enumerate}

To prove the theorem note that
$$\bigcup_{\mbox{ even }\be <\ga} \bb_\be^*\sm \bb_{\be+1}^*\su
\bigcup_{\be} (\bb_\be\sm \bb_{\be+1})^\triangle
=(\bigcup_{\be} \bb_\be\sm \bb_{\be+1})^\triangle
=\bb^\triangle=\bb$$
where these unions are all taken over even $\be<\ga$.
Hence if we let 
$$\diffeven(\bb_\al:\al<\ga)=^{def}\bigcup\{\bb_{\al}\sm \bb_{\al+1}
\;:\;\mbox{ even }\al<\ga\}$$
Then we conclude that
$$\diffeven(\bb_\al^*:\al<\ga)\su \bb.$$

To get the reverse inclusion note that the complement
of a difference set is also a difference set.  To see this we may without
loss of generality assume that $\ga$ is a limit ordinal by padding
with the empty set if necessary.  Then
$\sim \bb=\sim (\bigcup\{\bb_\be\sm \bb_{\be+1}\;:\;\be\mbox{ even }<\ga\}$
is the union of the following sets:
\begin{itemize}
\item $X_\rho\sm \bb_0$
\item $\bb_\be\sm \bb_{\be+1}$ for odd $\be <\ga$
\item $(\cap_{\al<\lambda}\bb_\al)\sm \bb_\lambda$ for limit $\lambda<\ga$
\item $\cap_{\al<\ga}\bb_\al$
\end{itemize}
Let us denote this union as $\diffodd(\bb_\al:\al<\ga)$.
Then by the argument above we get that 
$$\diffodd(\bb_\al^*:\al<\ga)\su\sim\bb$$
But since $\diffeven(\bb_\al^*:\al<\ga)$ 
and $\diffodd(\bb_\al^*:\al<\ga)$ are complements, it
follows that $\bb=\diffeven(\bb_\al^*:\al<\ga)$.
\qed

\begin{cor}
If the isomorphism class of a countable structure is
$\Delta_{\al+1}^0$ then it must be either $\Pi_\al^0$,
$\Sigma_\al^0$, or the difference of two invariant $\Pi_\al^0$
sets.
\end{cor}

\begin{thm}
(Miller \cite{ctblmod}) 
The isomorphism class of a countable
model cannot be properly $\Sigma_1^0$ or properly $\Sigma_2^0$.
For $\lambda$ a countable limit ordinal, it cannot be properly
$\Sigma_\lambda^0$
or properly the difference of two $\Pi_\lambda^0$ sets.
\end{thm}

\begin{thm}
(Miller \cite{ctblmod}, Hjorth \cite{hjorth})
In all other cases of
there are examples of countable structures whose
isomorphism class is properly of that Borel class.
\end{thm}

%\section{Other results on Borel hierarchies}

%In this section we enumerate some results on the length of hierarchies which
%were not lectured on. long borel hierarchies,
%proj set hierarchies, podge 6.1, re-anal, results in lecture notes

\begin{thebibliography}{99}

\bibitem{barwise} Barwise, Jon; Back and forth through infinitary
logic. Studies in model theory, pp. 5-34. MAA Studies in Math., Vol. 8,
Math. Assoc. Amer., Buffalo, N.Y., 1973.

\bibitem{BBM} Bing, R. H.; Bledsoe, W. W.; Mauldin, R. D.;
Sets generated by rectangles.
Pacific J. Math. 51 (1974), 27-36. 

\bibitem{carlson}
Tim Carlson, On $\om_1$-Borel sets, unpublished 1982.

\bibitem{qsets} Fleissner, William G.; Miller, Arnold W.;
On Q Sets,
Proceedings of the American Mathematical Society, 78(1980), 280-284.
\par\url{http://www.math.wisc.edu/~miller/res/qsets.pdf}

\bibitem{hjorth}
Hjorth, G.; An orbit that is exactly $\Sigma_{\lambda +1}$,
handwritten note Feb 1995.
\par\url{http://www.math.wisc.edu/~miller/res/unpub/hjorth.pdf}

\bibitem{kechris} Kechris, Alexander S.;{\bf Classical descriptive set theory.}
Graduate Texts in Mathematics, 156. Springer-Verlag, New York,
1995. xviii+402 pp. ISBN: 0-387-94374-9

\bibitem{kunen} Kunen, Kenneth;  INACCESSIBILITY PROPERTIES OF CARDINALS.
 Thesis
(Ph.D.) Stanford University. 1968.

\bibitem{kur} Kuratowski, topology

\bibitem{hier} Miller, Arnold W.; On the length of Borel hierarchies,
Annals of Math Logic, 16(1979), 233-267.
\par\url{http://www.math.wisc.edu/~miller/res/hier.pdf}

\bibitem{gensous} Miller, Arnold W.; Generic Souslin sets,
Pacific Journal of Mathematics, 97(1981), 171-181.
\par\url{http://www.math.wisc.edu/~miller/res/gensous.pdf}

\bibitem{ctblmod} Miller, Arnold W.;
The Borel classification of the isomorphism class of a countable model,
Notre Dame Journal of Formal Logic, 24(1983), 22-34.
\par\url{http://www.math.wisc.edu/~miller/res/ctblmod.pdf}

\bibitem{map} Miller, Arnold W.;
Mapping a Set of Reals Onto the Reals,
Journal of Symbolic Logic, 48(1983), 575-584.
\par\url{http://www.math.wisc.edu/~miller/res/map.pdf}

\bibitem{special} Miller, Arnold W.; Special subsets of the real line,
in {\bf Handbook of Set Theoretic Topology}, North Holland, (1984), 201-233.
\par\url{http://www.math.wisc.edu/~miller/res/special.pdf}

\bibitem{proj}
Miller, Arnold W.; Projective subsets of separable metric spaces
Annals of Pure and Applied Logic, 50(1990), 53-69. 
\par\url{http://www.math.wisc.edu/~miller/res/proj.pdf}

\bibitem{survey}  Miller, Arnold W.; Special sets of reals,
in {\bf Set Theory of the Reals}, ed Haim Judah, Israel Mathematical
Conference Proceedings, 6(1993), 415-432, American Math Society.
\par\url{http://www.math.wisc.edu/~miller/res/survey.pdf}

\bibitem{dstfor}  Miller, Arnold W.; Descriptive Set Theory and Forcing:
how to prove theorems about Borel sets the hard way, 
Lecture Notes in Logic 4(1995), Springer-Verlag.
New edition 4-2001 now published by Association for Symbolic Logic.
\par\url{http://www.math.wisc.edu/~miller/res/dstfor.pdf}

\bibitem{ramsey} Miller, Arnold W.; Ramsey Theory
\par\url{http://www.math.wisc.edu/~miller/old/m873-96/ramsey.pdf}

\bibitem{omega1} Miller, Arnold W.;
The hierarchy of $\omega_1$-Borel sets,
eprint July 2011 
\par\url{http://www.math.wisc.edu/~miller/res/omega1.pdf}

\bibitem{doug}
Miller, Douglas E.; The invariant $\Pi_\al^0$ separation principle. Trans.
Amer. Math. Soc. 242 (1978), 185-204.

\bibitem{univ} Larson, Paul B.; Miller, Arnold W.;
Steprans, Juris; Weiss, William A.R.;
{\bf Universal Functions}
eprint Apr 2012
\par\url{http://www.math.wisc.edu/~miller/res/univ.pdf}

\bibitem{rao} Rao, B.V.; On discrete Borel spaces and projective
sets. Bull. Amer. Math. Soc. 75 1969 614-617.

\bibitem{roth}  Rothberger, Fritz; A remark on the existence of a denumerable
base for a family of functions. Canadian J. Math. 4, (1952). 117-119. 

\bibitem{steprans}
Steprans, Juris; Cardinal arithmetic and $\aleph_1$-Borel sets.
Proc. Amer. Math. Soc. 84 (1982), no. 1, 121--126.


\bibitem{vaught} Vaught, Robert; Invariant sets in topology and logic.
Collection of articles dedicated to Andrzej Mostowski on his sixtieth birthday,
VII. Fund. Math. 82 (1974/75), 269-294.

\bibitem{willard}  Willard, Stephen Some examples in the theory of Borel sets.
 Fund. Math. 71 (1971), no. 3, 187-191.

\end{thebibliography}

\end{document}
