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


\mathchardef\wtilde="0365
\def\aa{\mathcal{A}}
\def\al{\alpha}
\def\be{\beta}
\def\borel{{\rm Borel}}
\def\bpi#1#2{\vtop{\hbox{${\bf\Pi}^{#1}_{#2}$} \kern-4pt  \hbox{\kern1pt$\wtilde$}\kern-6pt}}
\def\bsig#1#2{\vtop{\hbox{${\bf\Sigma}^{#1}_{#2}$} \kern-4pt \hbox{\kern1pt$\wtilde$}\kern-6pt}}
\def\cantorspace{2^\om}
\def\cc{\continuum}
\def\continuum{{\mathfrak c}}
\def\dd{\mathfrak{d}}
\def\dense{{\cal D}}
\def\de{\delta}
\def\ga{\gamma}
\def\ka{\kappa}
\def\om{\omega}
\def\ord{{\rm ord}}
\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}

\begin{document}

\noindent Last revised:  \today

\begin{flushright}
A.Miller\\
Spring 2014\\
\end{flushright}

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

\begin{theorem}\label{leb}
(Lebesgue 1905 see \cite{dstfor} Thm 2.5) For every $\alpha$ with
$1\leq\alpha<\omega_1$
  $$\bsig0\alpha(\cantorspace)\not=\bpi0\alpha(\cantorspace).$$
\end{theorem}

\begin{theorem} \label{bbm}
(Bing, Bledsoe, Mauldin see \cite{dstfor} Thm 3.2) Suppose
$F\subseteq P(\cantorspace)$ is a countable family such that
$\borel(\cantorspace)\subseteq \borel(F)$.  Then $\ord(F)=\omega_1$.
\end{theorem}

\begin{theorem}\label{rec}
(Rec{\l}aw see see \cite{dstfor} Thm 3.5 \cite{survey} Thm 17)
If $X$ is a second countable space
and $X$ can be mapped continuously onto the unit interval,
$[0,1]$, then $\ord(X)=\omega_1$.
\end{theorem}

\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})
(MA$_{\om_1}$)  $\starpi(\al)\neq\starsi(\al)$ for every $\al<\om_2$.
\end{theorem}

\begin{theorem}
(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}

\begin{thm}
(Rao \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}

\begin{thm}
(Kunen \cite{kunen}) 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}

\begin{thm}
(Bing, Bledsoe, Mauldin \cite{BBM}) 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}

\begin{thm}
(Miller \cite{hier}) 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}


\begin{thm}
(\cite{hier}) For any countable $\al$ it is consistent
to have a separable metric space $X$ in which every subsets
is Borel and the order of $X$ is $\al$.
\end{thm}

\begin{thm}
(\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}


\begin{thm}
(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})
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}

\begin{thm}
(Miller \cite{todo}) The answer to question 4.6 \cite{univ} is no. If
we drop the condition that $k$ above is Borel in Theorem \ref{thmborel}
it is consistent that there be no such $F$ Borel.
\end{thm}

\begin{thm}
(\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.
$$G(x,y,z)=F(h(x),k(y),l(z))$$
$$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))$$
\end{thm}

\begin{thm}
(\cite{univ}) 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{thm}

\begin{thm}
(Miller \cite{todo})
The answer to question 7.13 \cite{univ} is yes.
If there is a Borel Sierpinski universal and $2^{<\cc}=\cc$,
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}

\begin{thm}
(Galvin, Mycielski, Solovay \cite{galvin}) 
(a) $X$ is countable iff Black has a winning strategy in G(X).
(b) $X$ does not have strong measure zero iff White has a winning strategy in
the game $G(X)$.
\end{thm}

\begin{thm}
(\cite{galvin}) $X$ has strong measure zero iff for any dense $G_\de$ set
$D$ there exists $z$ such that $z+X\su D$.
\end{thm}

\begin{thm} (Cancino, Guzm\'an, Miller \cite{irr})
$\dd\leq \ss$. Any irredundant family $\aa\su [\om]^\om$ with
$|\aa|<\dd$ is not maximal.  Irredundant means no element of
$\aa$ is covered mod finite by a finite union of other elements
of $\aa$.
\end{thm}

\begin{thm}
(\cite{irr}) It is consistent with the continuum arbitrarily large
to have maximal irredundant families of size $\om_1$.
\end{thm}

\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}

\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}

\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}

\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}

\begin{thm}
(Miller \cite{todo}) (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}


\begin{thm}
(Mostowski) If $\theta$ is a $\Sigma_\al^0$ formula of $L_{\om_1,\om}(\rho)$,
then the set of models of $\theta$ is a $\Sigma_\al^0$ Borel
subset of $X_\rho$.  Where $X_\rho$ is the Polish space of 
$\rho$-structures with universe $\om$.
\end{thm}


\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}

\begin{thm}
(Vaught \cite{vaught}) Any $\Sigma_\al^0$ subset of $X_\rho$ which
is closed under isomorphism is the set of models of a
$\Sigma_\al^0$ sentence of $L_{\om_1,\om}(\rho)$
\end{thm}

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

\begin{thm}
(Douglas E. Miller \cite{doug}) If $B$ is also invariant, then
$$B=\bigcup_{\ga \mbox{ even }} C_\be^*\sm C_{\be+1}^*$$
\end{thm}

\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}

\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{irr}
Jonathan Cancino, Osvaldo Guzm\'an, Arnold W. Miller; Irredundant Generators,
eprint June 2013 revised Apr 2014.
\par\url{http://www.math.wisc.edu/~miller/res/irr.pdf}

\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{galvin} Galvin, Fred; Mycielski, Jan; Solovay, Robert M.;
Strong measure zero and infinite games, eprint Feb 2014.
\url{GalvinMycielskiSolovay.pdf}

\bibitem{hjorth}
Hjorth, G.; An orbit that is exactly $\Sigma_{\lambda +1}$,
handwritten note Feb 1995.

\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{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{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{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{todo} Miller, Arnold W.; in prep April 2014.

\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{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.

\end{thebibliography}

\end{document}
